Problem:
 Score : 400 points    Problem Statement There are N cells arranged in a row, numbered 1, 2, \ldots, N from left to right.  Tak lives in these cells and is currently on Cell 1 . He is trying to reach Cell N by using the procedure described below.  You are given an integer K that is less than or equal to 10 , and K non-intersecting segments [L_1, R_1], [L_2, R_2], \ldots, [L_K, R_K] .
Let S be the union of these K segments.
Here, the segment [l, r] denotes the set consisting of all integers i that satisfy l \leq i \leq r .   When you are on Cell i , pick an integer d from S and move to Cell i + d . You cannot move out of the cells.   To help Tak, find the number of ways to go to Cell N , modulo 998244353 .      Constraints  2 \leq N \leq 2 \times 10^5  1 \leq K \leq \min(N, 10)  1 \leq L_i \leq R_i \leq N  [L_i, R_i] and [L_j, R_j] do not intersect ( i \neq j )  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  K  L_1  R_1  L_2  R_2  :  L_K  R_K       Output Print the number of ways for Tak to go from Cell 1 to Cell N , modulo 998244353 .        Sample Input 1 5 2
1 1
3 4      Sample Output 1 4  The set S is the union of the segment [1, 1] and the segment [3, 4] , therefore S = \{ 1, 3, 4 \} holds.  There are 4 possible ways to get to Cell 5 :   1 \to 2 \to 3 \to 4 \to 5 ,  1 \to 2 \to 5 ,  1 \to 4 \to 5 and  1 \to 5 .        Sample Input 2 5 2
3 3
5 5      Sample Output 2 0  Because S = \{ 3, 5 \} holds, you cannot reach to Cell 5 .
Print 0 .       Sample Input 3 5 1
1 2      Sample Output 3 5       Sample Input 4 60 3
5 8
1 3
10 15      Sample Output 4 221823067  Note that you have to print the answer modulo 998244353 .

Solution (Python):
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


class Bit:

    def __init__(self, a):
        if hasattr(a, "__iter__"):
            le = len(a)
            self.n = 1 << le.bit_length()
            self.values = values = [0] * (self.n + 1)
            values[1:le + 1] = a[:]
            for i in range(1, self.n):
                values[i + (i & -i)] += values[i]
        elif isinstance(a, int):
            self.n = 1 << a.bit_length()
            self.values = [0] * (self.n + 1)
        else:
            raise TypeError

    
    def add(self, i, val):
        n, values = self.n, self.values
        while i <= n:
            values[i] += val
            i += i & -i

    
    def sum(self, i):
        values = self.values
        res = 0
        while i > 0:
            res += values[i]
            i -= i & -i
        return res

    
    def bisect_left(self, v):
        n, values = self.n, self.values
        if v > values[n]:
            return None
        i, step = 0, n >> 1
        while step:
            if values[i + step] < v:
                i += step
                v -= values[i]
            step >>= 1
        return i + 1


def main():

    N, K = in_nn()
    LR = []
    for i in range(K):
        l, r = in_nn()
        LR.append((l, r))

    init_dp = [0] * N
    init_dp[0] = 1
    init_dp[1] = -1
    bit = Bit(init_dp)

    mod = 998244353
    for i in range(1, N + 1):
        for k in range(K):
            l, r = LR[k]
            now = bit.sum(i) % mod
            bit.add(i + l, now)
            bit.add(i + r + 1, -now)

    print(bit.sum(N) % mod)


if __name__ == '__main__':
    main()

Solution (Python):

class BIT:
  def __init__(self, n):
    self.n = n
    self.bit = [0]*(n+1)
    self.el = [0]*(n+1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.bit[i]
      i -= i & -i
    return s
  def add(self, i, x):
    
    self.el[i] += x
    while i <= self.n:
      self.bit[i] += x
      i += i & -i
  def get(self, i, j=None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i-1)

mod = 998244353
N, K = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(K)]
A.sort()
dp = BIT(N)
dp.add(1,1)
for i in range(2,N+1):
  for l,r in A:
    if i-l<=0:
      continue
    if i-r>0:
      dp.add(i,dp.get(i-r,i-l)%mod)
    else:
      dp.add(i,dp.sum(i-l)%mod)
print(dp.el[-1]%mod)

Solution (Python):
n, k = map(int, input().split())
mod = 998244353
lr = []
s = set()
for i in range(k):
  l,r = map(int, input().split())
  for j in range(l,r+1):
    s.add(j)
  lr.append([l,r])

dp = [0 for i in range(n+1)]
dp[1] = 1
tot = [0 for i in range(k)]

for i in range(1,n+1):
  for j in range(k):
    l,r = lr[j][0],lr[j][1]
    if i-l < 1:
      continue
    tot[j] += dp[i-l]
    if i-r > 1:
      tot[j] -= dp[i-r-1]
    dp[i] += tot[j]
    dp[i] %= mod
print (dp[n])

Solution (Python):
z=[]
inp=list(map(int,input().split()))
n=inp[0]
k=inp[1]
for i in range(k):
    inp=list(map(int,input().split()))
    z.append(inp)
z.sort()
cum=[0]*(n+1)
cum[1]=1
for i in range(2,n+1):
    ans=0
    for j in range(len(z)):
        if i-z[j][1]>=1:
            ans+=cum[i-z[j][0]]-cum[i-z[j][1]-1]
        elif i-z[j][0]>=1 and i-z[j][1]<1:
            ans+=cum[i-z[j][0]]
        else:
            break
    cum[i]=cum[i-1]+ans
    cum[i]=cum[i]%998244353
print ((cum[-1]-cum[-2])%998244353)

Solution (Python):
N,K = map(int, input().split())

MOD = 998244353

PAT = []
for _ in range(K):
  l,r = map(int, input().split())
  PAT.append((l,r))
  
IMOS = [0] * (N+10)
IMOS[1] = 1
for i in range(0,N):
  if IMOS[i] == 0:
    continue
  for l,r in PAT:
    if i+l > N+1:
      continue
    IMOS[i+l] += IMOS[i]
    if i+r-1 > N+1:
      continue
    IMOS[i+r+1] -= IMOS[i]
  
  IMOS[i+1] += IMOS[i]
  IMOS[i+1] %= MOD
  
print((IMOS[N] - IMOS[N-1]) % MOD)

Solution (Python):
n,k=map(int,input().split())
s=[]
p=998244353
for i in range(k):
    l,r=map(int,input().split())
    s.append([l,r])
k=len(s)
dp=[0]*(3*n)
dp[1]=1
dp[2]=-1
for i in range(1,n):
    dp[i]=(dp[i-1]+dp[i])%p
    for j in range(k):
        l,r=s[j][0],s[j][1]
        dp[i+l]=(dp[i+l]+dp[i])%p
        dp[i+r+1]=(dp[i+r+1]-dp[i])%p

dp[n]=dp[n-1]+dp[n]

print(dp[n]%p)

Solution (Python):
N, K = map(int, input().split())


data0 = [0]*(N+1)
data1 = [0]*(N+1)

def _add(data, k, x):
    while k <= N:
        data[k] += x
        k += k & -k
def add(l, r, x):
    _add(data0, l, -x*(l-1))
    _add(data0, r, x*(r-1))
    _add(data1, l, x)
    _add(data1, r, -x)


def _get(data, k):
    s = 0
    while k:
        s += data[k]
        s %= MOD
        k -= k & -k
    return s
def query(l, r):
    return _get(data1, r-1) * (r-1) + _get(data0, r-1) - _get(data1, l-1) * (l-1) - _get(data0, l-1)

MOD = 998244353


lr = [list(map(int, input().split())) for _ in range(K)]

dp = [0] * (N+10)
add(1, 2, 1)
for i in range(1, N+1):
    dp[i] = query(i, i+1) % MOD
    for l, r in lr:
        if i+l > N+1: continue
        add(l+i, min(i+r+1, N+1), dp[i])
    

print(dp[N])

Solution (Python):
class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
 
    def to_sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= (i & -i)
        return s
 
    def add(self, i, x):
        while i <= self.n:
            self.data[i] += x
            i += (i & -i)
 
    def get(self, i, j):
        return self.to_sum(j)-self.to_sum(i-1)

N,K = map(int,input().split());MOD = 998244353
S = []
for i in range(K):
  temp = list(map(int,input().split()))
  S.append(temp)

Tree = BIT(N) 
Tree.add(1,1) 
for i in range(1,N+1):
  for l,r in S:
    
    if i-r >= 1:
      temp = Tree.get(i-r,i-l)
    elif i-l >= 1:
      temp = Tree.get(1,i-l)
    else:
      temp = 0
    Tree.add(i,temp%MOD)
ans = Tree.get(N,N)%MOD
print(ans)

Solution (Python):
def main():
    n, k = map(int,input().split())
    listS = []
    M = 998244353
    for i in range(k):
        l,r = map(int,input().split())
        
        
        listS.append((l,r))
    
    dp = [0] * n
    dp[0] = 1
    sm = 0
    for i in range(n):
        sm += dp[i] % M
        for lr in listS:
            if lr[0] + i < n:
                dp[i+lr[0]] += sm
            if i + lr[1] + 1 < n :
                dp[i+lr[1]+1] -= sm
            
            

        
    ans = dp[-1]%M
    if ans < 0:ans=0

    print(ans)
    
    

if __name__=='__main__':
    main()

Solution (Python):
N, K = map(int, input().split())
LR = []
for k in range(K):
    LR.append(list(map(int, input().split())))

kMod = 998244353

counts = [0] * N
counts[0] = 1
window_sums = [0] * K

for i in range(1, N):
    for k in range(K):
        l, r = LR[k]
        leave, enter = i-r-1, i-l
        if leave >= 0:
            window_sums[k] -= counts[leave]
        if enter >= 0:
            window_sums[k] += counts[enter]
        window_sums[k] %= kMod
    counts[i] = sum(window_sums) % kMod
print(counts[-1])

Solution (Python):
N,K = map(int,input().split())
move = [tuple(map(int,input().split())) for i in range(K)]
mod = 998244353

dp = [0 for i in range(N)]
imos = [0 for i in range(N)]
imos[0] = 1
dp[0] = 1

for i in range(1,N):
    for l,r in move:
        L = i-r
        R = i-l
        if R<0:
            continue
        L = max(L,0)
        if L>=1:
            dp[i] += imos[R]- imos[L-1]
        else:
            dp[i] += imos[R]
        dp[i] %= mod
    imos[i] = dp[i] + imos[i-1]
    imos[i] %= mod

print(dp[N-1])

Solution (Python):
mod = 998244353
N,K = map(int,input().split())

D = [list(map(int,input().split())) for _ in range(K)]
D.sort()

dp = [0]*N
dp[0] = 1
if D[0][0]<N:
    dp[D[0][0]] = 1

    for n in range(D[0][0],N-1):
        dp[n+1] = dp[n]
        for i in range(K):
            L,R = D[i]
            if n-L+1>=0:
                dp[n+1] += dp[n-L+1]
            if n-R+1>0:
                dp[n+1] -= dp[n-R]
            dp[n+1] %= mod
print(dp[N-1])

Solution (Python):
from sys import stdin,stdout
def ws(pos,win):
    l,r=win
    l1=pos-r
    r1=pos-l
    l=max(l1,0)
    r=max(r1,0)
    
    sm=ps[r]-(ps[l-1] if l>=1 else 0)
    return (sm+M)%M
n,k=list(map(int,stdin.readline().split()));w=[];s=[];M=998244353
for _ in range(k):
    x,y=list(map(int,stdin.readline().split()))
    w+=[[x,y]]
dp=[0]*(n+1);dp[1]=1;ps=[0,1]
for i in range(2,n+1):
    for win in w:
        ans=ws(i,win)
        dp[i]=(dp[i]+ans)%M
    ps+=[ps[-1]+dp[i]]


print(dp[n])

Solution (Python):
mod = 998244353
def main():
  n, k =  map(int, input().split())
  query= []
  for i in range(k):
    query.append(list(map(int, input().split())))
  dp = [0]*(n + 1)
  dp[1] = 1
  for i in range(2, n+1):
    dp[i] += dp[i-1]
    for lr in query:
      if i-lr[0] <= 0:
        continue
      else:
        dp[i] += dp[i-lr[0]]-dp[max(0, i-lr[1]-1)]
        dp[i] %= mod
  print((dp[n]-dp[n-1])%mod)
  
if __name__ == "__main__":
  main()

Solution (Python):
MOD = 998244353
N, K = map(int, input().split())
L = []
R = []
for k in range(K):
    l, r = map(int, input().split())
    L += [l]
    R += [r]

memo = [0 for i in range(N+2)]
memo[1] = 1
memo[2] = -1
cusum = 0
for i in range(1, N+1):
    cusum = (cusum + memo[i]) % MOD
    
    for k in range(K):
        l, r = L[k], R[k]
        
        
        memo[min(i+l, N+1)] += cusum
        memo[min(i+r+1, N+1)] -= cusum
    



print(cusum % MOD)

Solution (Python):

import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

M = 998244353
n,k = ip()
seg = [ip() for i in range(k)]
dp = [0]*(n+1)
pre = [0]*(n+1)

dp[1] = 1
pre[1] = 1
for i in range(2,n+1):
    for l,r in seg:
        a,b = max(i-r,1),i-l
        dp[i] += (pre[b] - pre[a-1])%M
    pre[i] += (pre[i-1]+dp[i])%M
print(dp[n]%M)

Solution (Python):
import math
import collections
def main():

    N, K = map(int, input().split())
    mod = 998244353
    d = dict()
    cnt = collections.defaultdict(int)
    for _ in range(K):
        l, r = map(int, input().split())
        d[(1-r, 1-l)] = 0
    cnt[1] = 1

    for i in range(2, N+1):
        temp = dict()
        for p in d:
            if p[1]+1 <= N:
                temp[(p[0]+1, p[1]+1)] = d[p]
                if p[0] in cnt: temp[(p[0]+1, p[1]+1)] -= cnt[p[0]]
                if p[1]+1 in cnt: temp[(p[0]+1, p[1]+1)] += cnt[p[1]+1]
            else:
                temp[(p[0]+1, N)] = d[p]
                if p[0] in cnt: temp[(p[0]+1, p[1]+1)] -= cnt[p[0]]
        d = temp
        
        cnt[i] = sum(d[v] for v in d) % mod
        
    return cnt[N]



if __name__ == '__main__':
    print(main())

Solution (Python):
import sys

input = sys.stdin.readline
N, K = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(K)]
P = 998244353

class SegmentTree:
    def __init__(self, n, segfunc=min, ele=10**10):
        self.ide_ele = ele
        self.num = pow(2, (n-1).bit_length())
        self.seg = [self.ide_ele] * 2 * self.num
        self.segfunc = segfunc

    def init(self, init_val):
        
        for i in range(len(init_val)):
            self.seg[i+self.num-1] = init_val[i]
        
        for i in range(self.num - 2, -1, -1):
            self.seg[i] = self.segfunc(self.seg[2*i+1], self.seg[2*i+2])

    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])

    def query(self, p, q):
        if q <= p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p > 1:
            if p & 1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q & 1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res


dp = SegmentTree(N, segfunc=lambda x, y: x+y%P, ele=0)
dp.update(0, 1)
for i in range(1, N):
    tmp = 0
    for l, r in LR:
        tmp = (tmp + dp.query(max(0, i - r), max(0, i - l + 1)))%P
    dp.update(i, tmp)
print(dp.seg[N - 1 + dp.num - 1])

Solution (Python):
n,k=map(int,input().split())
import sys
mod=998244353 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict 
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  
  
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright
from fractions import Fraction as frac  






dp=[0]*(n*2+10)

S=[0]*(n*2+10)
K=[list(map(int,input().split())) for i in range(k)]
for x,y in K:
  S[x]+=1
  S[y+1]-=1

for i in range(1,n):
    dp[i]= (dp[i-1]+S[i])%mod
    if dp[i]==0:continue
    for x,y in K:
        S[i+x]+= dp[i] % mod
        S[i+y+1]-= dp[i] % mod

print(dp[n-1]%mod)

Solution (Python):
n, k = list(map(int, input().split()))
period = [list(map(int, input().split())) for _ in range(k)]

dp = [0] * (2*n+1)
dp_cumsum = [0] * (2*n+1)
mod = 998244353

dp[n+1] = 1
dp_cumsum[n+1] = 1

for idx in range(n+2, 2*n+1):
    for l, r in period:
        
        dp[idx] += dp_cumsum[idx - l] - dp_cumsum[idx - r - 1]

    dp[idx] %= mod
    dp_cumsum[idx] = (dp_cumsum[idx-1] + dp[idx]) % mod

print(dp[n+n])

Solution (Python):
import sys
input = sys.stdin.readline

MOD = 998244353
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            self.tree[i] %= MOD
            i += i & -i

def main():
    n, k = map(int, input().split())
    lr = [list(map(int, input().split())) for _ in range(k)]
    bit = Bit(n + 1)
    bit.add(1, 1)
    for i in range(2, n + 2):
        for l, r in lr:
            plus = bit.sum(i - l) - bit.sum(i - r - 1)
            bit.add(i, plus)
    
    print((bit.sum(n) - bit.sum(n - 1)) % MOD)
    
main()

Solution (Python):
n,k= map(int, input().split())
a= [list(map(int, input().split())) for i in range(k)]
s=[]


mod=998244353

dp=[0]*(n+6)

for j in range(k):
    l = a[j][0]
    r = a[j][1]
    dp[l+1] += 1
    dp[r+2] -= 1


for i in range(1,n+1):
    dp[i+1]+=dp[i]
    dp[i+1]%=mod
    x=dp[i+1]
    for j in range(k):
        l=a[j][0]
        r=a[j][1]
        if l+i<=n:
            dp[i + l + 1] += x
        if r+i<=n:
            dp[i + 2 + r] -= x



print(dp[n]%mod)

Solution (Python):
n,k=map(int,input().split())
l=[list(map(int,input().split())) for i in range(k)]
x=[0]*(n+1)
x[0]=1
l.sort()
t=0
for i in range(1,n+1):
    for j in range(k):
        if i-l[j][1]>0:
            t+=x[i-l[j][0]]-x[i-l[j][1]-1]
        elif i-l[j][0]>=0:
            t+=x[i-l[j][0]]
        t=t%998244353
        x[i]=t
print(x[n-1])

Solution (Python):
class BIT(object):
    def __init__(self, N, init=0, mod=1):
        self.N = N
        self.bit = [init for _ in range(N)]
        self.mod = mod

    def add(self, k, w):
        x = k
        while x < self.N:
            self.bit[x] += w % self.mod
            self.bit[x] %= self.mod
            x |= x + 1

    def sum(self, k):
        s = 0
        x = k - 1
        while x >= 0:
            s += self.bit[x]
            s %= self.mod
            x = (x & (x + 1)) - 1
        return s

MOD = 998244353
n, k = map(int, input().split())
seg = [list(map(int, input().split())) for _ in range(k)]
bit = BIT(n, mod=MOD)
bit.add(0, 1)

for i in range(1, n):
    x = 0
    for l, r in seg:
        x += (bit.sum(max(0, i - l + 1)) - bit.sum(max(0, i - r))) % MOD
        x %= MOD
    bit.add(i, x)
print((bit.sum(n) - bit.sum(n - 1)) % MOD)

Solution (Python):


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

class RangeUpdate:
    def __init__(self, n):
        self.p = Bit(n + 1)
        self.q = Bit(n + 1)

    def add(self, s, t, x):
        t += 1
        self.p.add(s, -x * s)
        self.p.add(t, x * t)
        self.q.add(s, x)
        self.q.add(t, -x)

    def sum(self, s, t):
        t += 1
        return (self.p.sum(t) + self.q.sum(t) * t - \
               self.p.sum(s) - self.q.sum(s) * s) % mod


mod = 998244353

N, K, *LR = map(int, open(0).read().split())

LR = list(zip(*[iter(LR)] * 2))

dp = RangeUpdate(N)
dp.add(1, 1, 1)
for i in range(1, N + 1):
    for l, r in LR:
        dp.add(i + l, i + r, dp.sum(i, i))

print(dp.sum(N, N))

Solution (Python):
import sys
N, K = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(K)]
MOD = 998244353

dp = [0] * (N + 1)
dp[1] = 1

def add(k, x):
    while k <= N:
        dp[k] += x
        dp[k] %= MOD
        k += k & -k


def get(k):
    s = 0
    while k:
        s += dp[k]
        k -= k & -k
    return s

for i in range(1, N + 1):
    for l, r in X:
        add(i + l, get(i))
        add(i + r + 1, -get(i))

print(get(N) % MOD)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque


def read():
    N, K = map(int, input().strip().split())
    LR = []
    for i in range(K):
        l, r = map(int, input().strip().split())
        LR.append((l, r))
    return N, K, LR


def solve(N, K, LR, MOD=998244353):
    LR.sort()
    q = deque()
    for l, r in LR:
        for a in range(l, r+1):
            q.append(a)
    dp = [0 for i in range(N+1)]
    dp[1] = 1
    sdp = [0 for i in range(N+1)]
    sdp[1] = 1
    for i in range(2, N+1):
        for l, r in LR:
            a = max(1, i-r)
            b = min(i-l, i-1)
            if a <= b:
                dp[i] += sdp[b] - sdp[a-1]
                dp[i] %= MOD
        sdp[i] = sdp[i-1] + dp[i]
        sdp[i] %= MOD
    return dp[N]


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Solution (Python):
n,k = map(int,input().split())
MOD = 998244353
l = []
r = []
for i in range(k):
  tmp1, tmp2 = map(int, input().split())
  l.append(tmp1)
  r.append(tmp2)

array = [0] * (n+1)

array[1] = 1

count = 0
for i in range(1, n+1):
  count += array[i]
  count %= MOD
  for j in range(k):
    if i + l[j] <= n:
      array[i+l[j]] += count
      array[i+l[j]] %= MOD
      
    if i + r[j] + 1 <= n:
      array[i+r[j]+1] -= count
      array[i+r[j]+1] %= MOD
      
print(array[-1])

Solution (Python):
def main():
    mod = 998244353
    N, K = map(int, input().split())
    LR = []
    for _ in range(K):
        l, r = map(int, input().split())
        LR.append((l, r))
    LR.sort()
    dp = [0] * N
    dp[0] = 1
    z = 0
    for i in range(1, N):
        for l, r in LR:
            if i - l >= 0:
                z += dp[i - l]
            if i - r - 1 >= 0:
                z -= dp[i - r - 1]
        z %= mod
        dp[i] = z

    return dp[-1]

print(main())

Solution (Python):


N, K = map(int, input().split())

mod = 998244353

dp = [0] * N
dp[0] = 1

LR = [list(map(int, input().split())) for i in range(K)]
X = [0] * K

for i in range(1, N):
  for j in range(K):
    if i - LR[j][0] >= 0:
      X[j] += dp[i - LR[j][0]]
    if i - LR[j][1] > 0:
      X[j] -= dp[i - LR[j][1] - 1]
    X[j] %= mod
  dp[i] = sum(X) % mod
print(dp[-1])

Solution (Python):
n,k = map(int,input().split())


lr = [list(map(int,input().split())) for i in range(k)]





mod = 998244353
temp = 0
dp = [0]*(2*n)
dp[n] = 1
s = [0]*n + [1]*n

for i in range(n+1,2*n):
    for j in lr:
        dp[i] += (s[i-j[0]]-s[i-j[1]-1]) % mod
    s[i] = (dp[i] + s[i-1]) % mod



print(dp[n*2-1] % mod)

Solution (Python):
N , K = map(int, input().split())

S = []
for i in range(K):
  L, R = map(int, input().split())
  S.append((L, R))
dp = [0 for i in range(N+1)]
sumdp = [0 for i in range(N+1)]
sumdp[1] = 1
dp[1] = 1
for i in range(2,N+1):
  buf = 0
  for L, R in S:
    if i-L < 0:
      continue
    l = max(0, i-R-1)
    r = i-L
    
    buf += sumdp[r]-sumdp[l]
    
    buf %= 998244353
  dp[i] = buf
  sumdp[i] = sumdp[i-1] + buf
  
print(dp[N])

Solution (Python):
n,k=map(int,input().split())
B=[[0]*2 for i in range(k)]
for i in range(k):
  B[i]=list(map(int,input().split()))
mod=998244353
A=[0]*(n+1)
A[0]=1
a=1
for i in range(n):
  for j in range(k):
    A[min(n,i+B[j][0])]=(A[min(n,i+B[j][0])]+a)%mod
    A[min(n,i+B[j][1]+1)]=(A[min(n,i+B[j][1]+1)]-a)%mod
  a=a+A[i+1]
print(A[-2]%mod)

Solution (Python):






def modinv(n,p):
    return pow(n,p-2,p)

def main():
    
    

    mod = 998244353
    dp = [0] * (200005)
    suffix = [0] * (200005)
    segments = []

    n, k = [int(x) for x in input().split()]
    for i in range(k):
        segments.append([int(x) for x in input().split()])

    segments.sort()

    dp[n] = 1
    suffix[n] = 1
    not_possible = False
    for x in range(n-1, 0, -1):
        for l, r in segments:
            if x + l > n:
                
                break
            if x + r > n:
                r = n - x
            
            
            
            dp[x] = (dp[x] + (suffix[x+l] - suffix[x+r+1])) % mod
            suffix[x] = (dp[x] + suffix[x+1]) % mod

            
            
            
            
            
        if suffix[x] == 0:
            suffix[x] = suffix[x+1]

    print(dp[1])


py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange

import os, sys
from io import IOBase, BytesIO

BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0
    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s
    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)

class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s:self.buffer.write(s.encode('ascii'))
            self.read = lambda:self.buffer.read().decode('ascii')
            self.readline = lambda:self.buffer.readline().decode('ascii')

sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')

if __name__ == '__main__':
   main()

Solution (Python):
MOD=998244353
N,K=map(int,input().split())

lrlist=[]
for _ in range(K):
  l,r=map(int,input().split())
  lrlist.append((l,r))


class SegTree:
  
  def __init__(self, init_val, segfunc, ide_ele):
    
    
    
    
    
    
    n = len(init_val)
    self.segfunc = segfunc
    self.ide_ele = ide_ele
    self.num = 1 << (n - 1).bit_length()
    self.tree = [ide_ele] * 2 * self.num
    
    for i in range(n):
      self.tree[self.num + i] = init_val[i]
    
    for i in range(self.num - 1, 0, -1):
      self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

  
  def update(self, k, x):
    
    
    
    k += self.num
    self.tree[k] = x
    while k > 1:
      self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
      k >>= 1

  
  def query(self, l, r):
    
    
    
    res = self.ide_ele
    l += self.num
    r += self.num
    while l < r:
      if l & 1:
        res = self.segfunc(res, self.tree[l])
        l += 1
      if r & 1:
        res = self.segfunc(res, self.tree[r - 1])
      l >>= 1
      r >>= 1
    return res
  

def segfunc(x,y):
  return x+y 

ide_ele=0 


seg=SegTree([0]*(N+1), segfunc, ide_ele)
seg.update(1,1)

for i in range(2,N+1):
  for l,r in lrlist:
    left=i-r
    right=i-l    
    if right<1:
      continue
    elif left<1:
      left=1
    
    current=seg.query(i,i+1)
    sum_intv=seg.query(left,right+1)
    seg.update(i,(current+sum_intv)%MOD)
    
    
print(seg.query(N,N+1))

Solution (Python):
n, k = map(int, input().split())
lr = [list(map(int, input().split())) for _ in range(k)]

mod = 998244353
dp = [0]*n
dp[0] = 1
s = 0
for i in range(1, n):
    for j in range(k):
        if i-lr[j][0] < 0:
            continue
        elif i-lr[j][1] <= 0:
            s = (s + dp[i-lr[j][0]]) % mod
        elif 0 < i-lr[j][1]:
            s = (s + dp[i-lr[j][0]] - dp[i-lr[j][1]-1]) % mod
    dp[i] = s
print(dp[-1])

Solution (Python):
N, K = map(int, input().split())
mod = 998244353
lr = [list(map(int, input().split())) for _ in range(K)]

dp = [0]*(N+1)
tmp = 1
imos = [0]*(N+1)
imos[0] = 0

for i in range(N):
    imos[i] += dp[i]
    if i != 0:
        tmp = imos[i]+tmp
    for k in range(K):
        l, r = lr[k]
        if l+i > N: continue
        dp[l+i] = (dp[l+i]+tmp)%mod
        dp[min(N, r+i+1)] = (dp[min(N, r+i+1)]-tmp)%mod
print(imos[N-1]%mod)

Solution (Python):
N,K_o=map(int,input().split())
S=[]
K=[]
mod=998244353


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

for i in range(K_o):
  L,R=map(int,input().split())
  for i in range(L,R+1):
    S.append(i)
  K.append([L,R])

bit=Bit(N+1)
bit.add(1,1)
bit.add(2,-1)
for i in range(N):
  for L,R in K:
    value_i=bit.sum(i)
    value_i%=mod
    bit.add(i+L,value_i)
    bit.add(i+R+1,value_i*-1)

print(bit.sum(N)%mod)

Solution (Python):

"""
Created on Sat Sep 19 20:18:10 2020

@author: liang
"""

N, K = map(int, input().split())
areas = list()
for i in range(K):
    l, r = map(int,input().split())
    areas.append((l,r))

tmp = 0
d = [0] * N


d[0] = 1
for i in range(N):
    for j in range(K):
        l, r = areas[j]
        if i-l >= 0:
            
            tmp += d[i-l]
        if i-r-1 >= 0:
            
            tmp -= d[i-r-1]
    d[i] += tmp
    
    d[i] %= 998244353 
    tmp  %= 998244353 
    



ans = d[N-1]
print(ans)

Solution (Python):
n, k = list(map(int, input().split()))
m = 998244353

s = []
for i in range(k):
    l, r = list(map(int, input().split()))
    s.append((l, r))

dp = [0] * n
dp[0] = 1
totals = [0] * n
totals[0] = 1

for i in range(1, n):
    thisTotal = 0
    for l, r in s:
        indL = i-l
        if indL >= 0:
            indR = max(0, i-r)

            thisTotal += totals[indL] - totals[indR-1]

    dp[i] = (thisTotal%m)
    totals[i] = (totals[i-1] + thisTotal)%m

print(dp[n-1])

Solution (Python):
N, K = map(int, input().split())
dp = [[0 for j in range(10)] for i in range(2 * 10 ** 5 + 10)]
sumdp = [0 for i in range(2 * 10 ** 5 + 10)]
sumdp[1] = 1
que = []
mod = 998244353

for i in range(K):
    l, r = map(int, input().split())
    que.append((l, r))

for i in range(2, N + 1):
    sumdp[i] += sumdp[i - 1]
    sumdp[i] %= mod
    for j in range(K):
        l, r = que[j]
        if i - r >= 1:
            dp[i][j] = sumdp[i - l] - sumdp[i - r - 1]
            sumdp[i] += dp[i][j]
        elif i - l >= 1:
            dp[i][j] = sumdp[i - l]
            sumdp[i] += dp[i][j]

ans = sum(dp[N][i] for i in range(10))

print(ans % mod)

Solution (Python):
import sys

MOD = 998244353


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


def main():
    input = sys.stdin.buffer.readline
    n, k = map(int, input().split())
    lr = [tuple(map(int, input().split())) for _ in range(k)]
    dp = Bit(n)
    dp.add(1, 1)
    for i in range(2, n + 1):
        for l, r in lr:
            if i - l < 1:
                continue
            if i - r < 2:
                dp.add(i, dp.sum(i - l) % MOD)
            else:
                dp.add(i, (dp.sum(i - l) - dp.sum(i - r - 1)) % MOD)
    print((dp.sum(n) - dp.sum(n - 1)) % MOD)


if __name__ == "__main__":
    main()

Solution (Python):
N,K = map(int,input().split())
LR = [list(map(int,input().split())) for _ in range(K)]
LR = sorted(LR)

MOD = 998244353
dp = [0] * (N+1)
dp[1] = 1
for i in range(1,N):
  dp[i]%=MOD
  for l,r in LR:
    if i+l<=N:
      dp[i+l] += dp[i]
    if i+r+1<=N:
      dp[i+r+1] -= dp[i]
      
  if i!=1:
    dp[i+1] += dp[i]
    

print(dp[-1]%MOD)