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):
n, k = map(int, input().split())
s = []
for i in range(k):
    l, r = map(int, input().split())
    s.append([l, r])

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

dp[1] = 1
s = sorted(s)
counter = 0
for i in range(1, n+1):
    counter += cumsum[i]
    dp[i] += counter
    dp[i] %= mod
    for l, r in s:
        if i+l <= n:
            cumsum[i+l] += dp[i]
        if i+r+1 <= n:
            cumsum[i+r+1] -= dp[i]
print(dp[n] % mod)

Solution (Python):


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

MOD=998244353
D=[0]*(N+1)
D[1]=1

S=dict()
B=dict()
for i in range(K):
    L,R=map(int,input().split())
    S[i]=(L,R)
    B[i]=0


for i in range(2,N+1):
    for j in range(K):
        L,R=S[j][0],S[j][1]
        if i-L>0: B[j]+=D[i-L]
        if i-R-1>0: B[j]-=D[i-R-1]

        D[i]+=B[j]
        
    D[i]%=998244353

print(D[N])

Solution (Python):
MOD = 998244353
N, K = map(int, input().split())
rl = [list(map(int, input().split())) for _ in range(K)]
dp = [0] * (N + 1)
dp[1] = 1
dp[2] = -1

for i in range(1, N + 1):
    dp[i] += dp[i - 1]
    for j in range(K):
        l, r = rl[j][0], rl[j][1]
        if i + l <= N:
            dp[i + l] += dp[i]
            dp[i + l] %= MOD
        if i + r + 1 <= N:
            dp[i + r + 1] -= dp[i]
            dp[i + r + 1] %= MOD
print(dp[N] % MOD)

Solution (Python):




import sys
input = sys.stdin.readline


 
 

def give_dp(N,K,mod,LR,dp,l,r):
    for i in range(N):
        if i > 0:
            dp[i] += dp[i-1]
            dp[i] %= mod
        for k in range(K):
            l = LR[k][0]
            r = LR[k][1]
            if i + l < N:
                dp[i+l] += dp[i]
                dp[i+1] %= mod
            if i + r + 1 < N:
                dp[i+r+1] -= dp[i]
                dp[i+1] %= mod
    return dp[-1]
 
 
def main():
    N,K = map(int,input().split())
    LR = [list(map(int,input().split())) for i in range(K)]
    
 
    mod = 998244353
 
    dp = [0 for i in range(N)]
    dp[0] = 1
    dp[1] = -1
    
 
    res = give_dp(N,K,mod,LR,dp,0,0)
    res %= mod
 
    print(res)
 
 
 
main()

Solution (Python):
import numpy as np



import sys
input = sys.stdin.readline

from numba import njit,i8


@njit(i8(i8,i8,i8,i8[:,:],i8[:],i8,i8))
def give_dp(N,K,mod,LR,dp,l,r):
    for i in range(N):
        if i > 0:
            dp[i] += dp[i-1]
            dp[i] %= mod
        for k in range(K):
            l = LR[k][0]
            r = LR[k][1]
            if i + l < N:
                dp[i+l] += dp[i]
                dp[i+1] %= mod
            if i + r < N:
                dp[i+r+1] -= dp[i]
                dp[i+1] %= mod
    return dp[-1]


def main():
    N,K = map(int,input().split())
    LR = [list(map(int,input().split())) for i in range(K)]
    LR = np.array(LR)

    mod = 998244353

    dp = [0 for i in range(N)]
    dp[0] = 1
    dp[1] = -1
    dp = np.array(dp)

    res = give_dp(N,K,mod,LR,dp,0,0)
    res %= mod

    print(res)



main()

Solution (Python):
import sys
import itertools

import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
from itertools import permutations
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


MOD = 998244353
N, K = map(int, input().split())
S = [0] * K
for i in range(K):
    l, r = map(int, input().split())
    S[i] = (l, r)

dp = [0] * (N + 2)
acc = [0] * (N + 2)
dp[1] = 1
acc[1] = 1
for i in range(1, N + 1):
    for j in range(K):
        li = i - S[j][1]
        ri = i - S[j][0]
        if ri < 0:
            continue
        li = max(li, 0)
        dp[i] += (acc[ri] - acc[li - 1]) % MOD
    acc[i] = (acc[i - 1] + dp[i]) % MOD
print(dp[N] % MOD)

Solution (Python):

"""
N = 10, LR = [2, 4] を例とする.
fi:=マスiまで移動する方法の個数とおく.
便宜上0マスから始めると、
    N:  0 1 2 3 4 5 6 7 8 9 10
    fi: 0 1 0 1 1 2 2 4 5 8 11
となる.(1マス目には最初からいるのでf1 = 1とする.)
ここで、N=5,6の時で考えると、LR=[2,4]から
    f5 = f1 + f2 + f3  (∵2～4マス前からしか遷移がないので)
    f6 =      f2 + f3 + f4
よってf5とf6の差はf1とf4によって求めることができる.
    f6 = f5 - f1 + f4
一般化すると、
    fi = fi-1 - fi-1-R + fi-L
LRが複数ある場合でも区間が重複しないので、各区間に対して - fi-1-R + fi-L 部分を計算して fi を求めることができる.
計算量はO(KN) (K:=重複しない区間LRの個数)
"""










def solve(N, K, LR):
    mod = 998244353
    dp = [0] * (N + 1)
    dp[1] = 1
    
    
    
    
    dp[2] = 1 if 1 in [lr[0] for lr in LR] else 0
    for i in range(3, N + 1):
        x = 0
        for l, r in LR:
            x += dp[max(i - l, 0)] - dp[max(i - 1 - r, 0)]
        dp[i] = (dp[i - 1] + x) % mod
    print(dp[N])


if __name__ == '__main__':
    N, K = map(int, input().split())
    LR = [[int(i) for i in input().split()] for _ in range(K)]
    solve(N, K, LR)

Solution (Python):
n, k = list(map(int, input().split()))
s = []
for i in range(k):
    a, b = list(map(int, input().split()))
    s.append((a, b))
dp = [0]*(n+1)
v = 0
mod = 998244353
for i in range(1, n+1):
    if i == 1:
        for l, r in s:
            if i+l <= n:
                dp[i+l] += 1
            if i+r+1 <= n:
                dp[i+r+1] -= 1
    else:
        v += dp[i]
        v %= mod
        for l, r in s:
            if i+l <= n:
                dp[i+l] += v
            if i+r+1 <= n:
                dp[i+r+1] -= v


print(v % mod)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)











def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
def _debug(obj):
    print(obj, file=sys.stderr)



mod = 998244353

N, K = inpl()
left, right = [0] * K, [0] * K
for i in range(K):
    left[i], right[i] = inpl();

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

for i in range(2, N + 1):
    for k in range(K):
        dp[i] += wa[max(0, i - left[k])] - wa[max(0, i - right[k] - 1)]
        dp[i] %= mod
    wa[i] = (wa[i-1] +  dp[i]) % mod
print(dp[N])

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


mod = 998244353
dp = [0] * (N + 1)
dpsum = [0] * (N + 1)
dp[1] = 1
dpsum[1] = 1
for i in range(2, N + 1):
    for j in range(K):
        li = max(i - LR[j][1], 1)
        ri = i - LR[j][0]
        if ri < 0:
            continue
        dp[i] += dpsum[ri] - dpsum[li - 1]
        dp[i] %= mod
    dpsum[i] = dpsum[i - 1] + dp[i]

print(dp[N])

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)











def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
def _debug(obj):
    print(obj, file=sys.stderr)



mod = 998244353

N, K = inpl()
left, right = [0] * K, [0] * K
for i in range(K):
    left[i], right[i] = inpl();

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

for i in range(2, N + 1):
    for k in range(K):
        if i - left[k] >= 0:
            dp[i] += wa[i - left[k]] - wa[max(0, i - right[k] - 1)]
        dp[i] %= mod
        wa[i] = (wa[i-1] +  dp[i]) % mod
print(dp[N])

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

MOD = 998244353

interval = []
for i in range(K):
    intv = [int(x) for x in input().split()]
    interval.append(intv)

dp = [0]*N
diff = [0]*(N-1)
dp[0] = 1
diff[0] = -1

for i in range(N-1):
    for L,R in interval:
        if L <= N-1 - i:
            diff[i+L-1] += dp[i]
        if R+1 <= N-1 - i:
            diff[i+R] -= dp[i]
    dp[i+1] = dp[i] + diff[i]
    dp[i+1] %= MOD

print(dp[N-1])

Solution (Python):
n,k=map(int,input().split())
dp=[0 for i in range(n+1)]
dp[1]=1
accum=[0 for i in range(n+1)]
accum[1]=1
s=[]
for i in range(k):
    x,y=map(int,input().split())
    s.append([x,y])
for i in range(2,n+1):
    for j in s:
        l,r=j
        tmpl=i-r
        tmpr=i-l
        if(tmpl<1):
            tmpl=1
        if(tmpr>=i):
            tmpr=i-1
        if(tmpr<0):
            continue
        dp[i]+=accum[tmpr]-accum[tmpl-1]
        dp[i]%=998244353
    accum[i]=dp[i]+accum[i-1]
    accum[i]%=998244353
print(dp[n]%998244353)

Solution (Python):
N,K = [int(i) for i in input().split()]
mod = 998244353
LR = []
S = []
dp = [0]*(N+1)
dps = [0]*(N+1)
dps[1] = 1
dp[1] = 1
for i in range(K):
  LR.append([int(i) for i in input().split()])

for i in range(1,N+1):
  for l,r in LR:
    l,r = i - r,i - l
    
    if r < 1:
      continue
    l = max(1,l)
    dp[i] += dps[r] - dps[l-1]
    dp[i] %= mod
    
    
  dps[i] = dps[i-1] + dp[i]
  
print(dp[-1])

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



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

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

for i in range(2, N+1):
    for l, r in lr:
        li = max(0, i-r)
        ri = i-l
        if ri < 0:
            continue
        dp[i] += dpsum[ri]-dpsum[li-1]
        dp[i] %= MOD
    dpsum[i] += dp[i]+dpsum[i-1]
    dpsum[i] %= MOD

print(dp[N])

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

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

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

for i in range(2, N+1):
    for l, r in lr:
        li = max(0, i-r)
        ri = i-l
        if ri < 0:
            continue
        dp[i] += dpsum[ri]-dpsum[li-1]
        dp[i] %= MOD
    dpsum[i] += dp[i]+dpsum[i-1]
    dpsum[i] %= MOD

print(dp[N])

Solution (Python):








if __name__ == "__main__":
    from sys import stdin as inp, stdout as out,setrecursionlimit as srl
    from collections import Counter,defaultdict,deque
    from heapq import *
    def upd(idx,v):
      while idx<len(b):
        b[idx]=(b[idx]+v)%mod
        idx+=(idx&-idx)
    def acc(idx):
        s=0
        while idx>0:
            s=(s+b[idx])%mod
            idx-=(idx&-idx)
        return s
    for _ in xrange(1):
        n,k=map(int,inp.readline().split())
        a=[map(int,inp.readline().split()) for i in xrange(k)]
        b=[0]*(n+1)
        mod=998244353
        upd(1,1)
        for i in xrange(2,n+1):
          for l,r in a:
            upd(i,acc(max(0,i-l))-acc(max(0,i-r-1))%mod)
        print (acc(n)-acc(n-1))%mod

Solution (Python):
MOD = 998244353

n, k = map(int, input().split())
l = [0] * k
r = [0] * k
for i in range(k):
    l[i], r[i] = map(int, input().split())

s = [0] * (n + 2)
for i in range(k):
    for j in range(l[i], r[i] + 1):
        s[j] = 1

ans = [0] * (n + 1)
ans[0] = 1
for i in range(n - 1):
    ans[i + 1] = ans[i]
    for j in range(k):
        ans[i + 1] += ans[max(-1, i + 1 - l[j])]
        ans[i + 1] -= ans[max(-1, i + 1 - r[j] - 1)]
        ans[i + 1] = ans[i + 1] % MOD
print((ans[n - 1] - ans[n - 2]) % MOD)

Solution (Python):








if __name__ == "__main__":
    from sys import stdin as inp, stdout as out,setrecursionlimit as srl
    from collections import Counter,defaultdict,deque
    from heapq import *
    for _ in xrange(1):
        n,k=map(int,inp.readline().split())
        a=[map(int,inp.readline().split()) for i in xrange(k)]
        b=[0]*(n+1)
        b[1]=1
        mod=998244353
        for i in xrange(2,n+1):
          b[i]=b[i-1]
          for l,r in a:
            b[i]=(b[i]+b[max(0,i-l)]-b[max(0,i-r-1)])%mod
        print (b[-1]-b[-2])%mod

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

    S = []
    LR = []
    for i in range(K):
        l, r = map(int, input().split())
        LR.append((l, r))
    
    LR.sort()
    
    
    

    a = [0] * N
    f = [0] * N
    f[0] = 1
    a[1] = -1

    for i in range(N):
        if i > 0:
            f[i] = (f[i-1] + a[i]) % MOD
        for (l, r) in LR:
            if i+l < N:
                a[i+l] = (a[i+l] + f[i]) % MOD
            if i+r+1 < N:
                a[i+r+1] = (a[i+r+1] - f[i]) % MOD
    
    print(f[N-1])

if __name__ == '__main__':
    main()

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

for _ in range(K):
  L, R = map(int, input().split())
  move.append((L, R))

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

for i in range(1, N):
  for l, r in move:
    dp[i] += accumdp[max(i-l+1, 0)] - accumdp[max(i-r, 0)]
  dp[i] %= MOD
  accumdp.append((accumdp[-1] + dp[i])%MOD)

print(dp[-1])

Solution (Python):
MOD = 998244353
N, K = map(int, input().split())
LR = [tuple(map(int, input().split())) for i in range(K)]
 
dp = [0] * (N+1)
dp[1] = 1    
for i in range(1, N):
  dp[i] += dp[i-1]   
  dp[i] %= MOD
  for l, r in LR:
    ll = i + l
    rr = i + r
    if ll <= N:
      dp[ll] += dp[i]    
      dp[ll] %= MOD
    if rr < N:
      dp[rr+1] -= dp[i]    
      dp[rr+1] %= MOD
 
print(dp[-1])

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

move = []
for _ in range(K):
  L, R = map(int, input().split())
  move.append((L, R))

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

for i in range(1, N+1):
  dp[i] += dp[i-1]
  for l, r in move:
    if i - l >= 0:
      dp[i] += dp[i-l]
    if i - r - 1 >= 0:
      dp[i] -= dp[i-r-1]
  dp[i] %= MOD

print(dp[N-1])

Solution (Python):
import sys
N,K=map(int, sys.stdin.readline().split())
LR=[ map(int, sys.stdin.readline().split()) for _ in range(K) ]

dp=[0]*(N+1)
sum_dp=[0]
mod=998244353

i=1
dp[i]=1
sum_dp.append(sum_dp[-1]+dp[i])

for i in range(2,N+1):
    for l,r in LR:
        dp[i]+=sum_dp[max(0,i-l)]-sum_dp[max(0,i-r-1)]
        dp[i]%=mod
    sum_dp.append( (sum_dp[-1]+dp[i])%mod )

print dp[-1]

Solution (Python):
def solve(N, LR):
    mod = 998244353

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

    for i in range(2, N+1):
        for lr in LR:
            left = i - lr[1]
            right = i - lr[0]
            if right < 0:
                continue
            left = max(left, 0)
            dp[i] += (dpsum[right] - dpsum[left-1])
            dp[i] %= mod
        dpsum[i] = dpsum[i-1] + dp[i]
        dpsum[i] %= mod

    return dp[N]


if __name__ == "__main__":
    N, K = map(int, input().split())
    LR = [list(map(int, input().split())) for _ in range(K)]
    print(solve(N, LR))

Solution (Python):

n, k = map(int, input().split())
mod = 998244353
li = []
for _ in range(k):
    l, r = map(int, input().split())
    li.append((l, r))
li.sort()
dp = [0]*(2*n+1)
s = [0] * (2*n+1)
dp[1] = 1
s[1] = 1
for i in range(2, n+1):
    for t in li:
        l, r = t
        dp[i] += s[max(i-l, 0)]
        dp[i] -= s[max(i-r-1, 0)]
        dp[i] %= mod
    s[i] = s[i-1] + dp[i]
    s[i] %= mod
print(dp[i]%mod)

Solution (Python):
import sys

input = sys.stdin.readline

N, K = map(int, input().split())
LR = [list(map(int, input().split())) for i in range(K)]
MOD = 998244353
 
dp = [0] * (N + 1)
dp[1] = 1
dp_sum = [0] * (N + 1)
dp_sum[1] = 1
 
 
def get(l, r, i):
    return dp_sum[max((i - l), 0)] - dp_sum[max((i - r-1), 0)]
 
 
for i in range(1, N+1):
    for l, r in LR:
        dp[i] += get(l, r, i) % MOD
    dp_sum[i] = (dp_sum[i - 1] + dp[i])%MOD

print(dp[N] % MOD)

Solution (Python):
N, K = map(int, input().split())
L=[]
R=[]
for i in range(K):
  l,r= map(int, input().split())
  L.append(l)
  R.append(r)

dp=[0]*(N+1)
dp[1]=1
dpd=[0]*(N+2)
dpd[2]=-1

for i in range(1, N):
  for j in range(K):
    dpd[min(i+L[j],N+1)]+=dp[i]
    dpd[min(i+R[j]+1,N+1)]-=dp[i]
  dp[i+1]=(dp[i]+dpd[i+1])%998244353

print(dp[N])

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

MOD = 998244353
n, k = map(int, input().split())
s = list()
for i in range(k):
    s.append(tuple(map(int, input().split())))

dp = [0] + [0] * n
diff = [0] + [0] * n
dp[1] = 1
diff[2] = -1
for i in range(1, n):
    for j, k in s:
        if i + j > n:
            continue
        diff[i + j] += dp[i]
        if i + k + 1 > n:
            continue
        diff[i + k + 1] -= dp[i]
    
    dp[i + 1] = (dp[i] + diff[i + 1]) % MOD
print(dp[n])

Solution (Python):
N, K = map(int, input().split())
L, R = [], []
for _ in range(K):
    tmpl, tmpr = map(int, input().split())
    L.append(tmpl)
    R.append(tmpr)
MOD = 998244353

dp = [0] * (N + 1)
dp[1] = 1
dp[2] = -1
for i in range(1, N + 1):
    dp[i] = dp[i - 1] + dp[i]
    for l, r in zip(L, R):
        if i + l < N + 1:
            dp[i + l] += dp[i]
            dp[i + l] %= MOD
        if i + r + 1 < N + 1:
            dp[i + r + 1] -= dp[i]
            dp[i + r + 1] %= MOD
print(dp[N] % MOD)

Solution (Python):
N, K = map(int, input().split())
L, R = [], []
for _ in range(K):
    tmpl, tmpr = map(int, input().split())
    L.append(tmpl)
    R.append(tmpr)
MOD = 998244353

dp = [0] * (N + 1)
dp[1] = 1
dp[2] = -1
for i in range(1, N + 1):
    dp[i] = dp[i - 1] + dp[i]
    for l, r in zip(L, R):
        if i + l < N + 1:
            dp[i + l] += dp[i]
            dp[i + l] %= MOD
        if i + r + 1 < N + 1:
            dp[i + r + 1] -= dp[i]
            dp[i + r + 1] %= MOD
print(dp[N] % MOD)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

MOD = 998244353
n, k = map(int, input().split())
s = list()
for i in range(k):
    s.append(tuple(map(int, input().split())))

dp = [0] + [0] * n
diff = [0] + [0] * n
dp[1] = 1
for i in range(1, n):
    for j, k in s:
        if i + j > n:
            continue
        diff[i + j] += dp[i]
        if i + k + 1 > n:
            continue
        diff[i + k + 1] -= dp[i]
    dp[i] = (dp[i - 1] + diff[i]) % MOD
    dp[i + 1] = (dp[i] + diff[i + 1]) % MOD
print(dp[n])

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

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

dp = [0]*(N+1)
dpsum = [0]*(N+1)
dp[1] = 1
dpsum[1] = 1
for i in range(2, N+1):
    for l, r in lr:
        lj = max(1, i-r)
        rj = i-l

        if rj < 1:
            continue

        dp[i] += dpsum[rj]-dpsum[lj-1]
        dp[i] %= MOD
    dpsum[i] = dp[i]+dpsum[i-1]

print(dp[N])

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

dp = [0]*(n+1)
dp[1] = 1
dpac = [0]*(n+1)
dpac[1] = 1
for i in range(2, n+1):
    for kl, kr in kkn:
        l = i-kr
        r = i-kl
        if r < 0: continue
        l = max(l, 0)
        dp[i] += dpac[r] - dpac[l-1]
        dp[i] %= MOD
    dpac[i] = dpac[i-1] + dp[i]
    dpac[i] %= MOD
print(dp[n])

Solution (Python):
n, k = map(int, input().split()); m = 998244353; a = []
for i in range(k): a.append(list(map(int, input().split())))
b = [0]*n; b.append(1); c = [0]*n; c.append(1)
for i in range(1, n):
    d = 0
    for j in range(k): d = (d+c[n+i-a[j][0]]-c[n+i-a[j][1]-1])%m
    b.append(d); c.append(c[-1]+d)
print(b[-1]%m)

Solution (Python):
N,K=map(int,input().split())
MOD = 998244353
dp = [0]*(N*3)

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

LR.sort()

imos = [0]*(N*3)
dp[1] = 1
imos[1] = 1
for i in range(1, N):
    if i >= 2:
        dp[i+1] += dp[i]

    for l, r in LR:
        dp[i+l] += dp[i]
        dp[i+l] %= MOD
        dp[i+r+1] -= dp[i]
        dp[i+r+1] %= MOD
    
    

print(dp[N]%MOD)

Solution (Python):
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10000000)
input = sys.stdin.readline
INF = float("inf")
MOD = 998244353




def main():
    N, K = map(int, input().split())
    
    L = [0]*K
    R = [0]*K
    for i in range(K):
        L[i], R[i] = map(int, input().split())

    dp = [0]*(N*2 + 1)
    a = [0]*(N*2 + 1)
    dp[0] = 1
    a[1] = -1
    for i in range(N):
        for j in range(K):
            a[i+L[j]] += dp[i]
            a[i+R[j]+1] -= dp[i]
        dp[i+1] = (dp[i] + a[i+1]) % MOD
    
    print(dp[N-1])



if __name__ == '__main__':
    main()

Solution (Python):
mod = 998244353

n, k = map(int, input().split())

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

dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n+1):
    for l, r in s:
        jl = max(i - l, 0)
        jr = max(i - r - 1, 0)
        dp[i] = (dp[i] + dp[jl] - dp[jr]) % mod
    dp[i] += dp[i-1]
print((dp[n] - dp[n-1]) % mod)

Solution (Python):
N,K = map(int,input().split())
LR = []
for _ in range(K): LR.append(list(map(int,input().split())))
MOD = 998244353
dp = [0]*(N+1)
dp[0] = 1
for i in range(N):
  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>0: dp[i+1] = (dp[i+1]+dp[i])%MOD
print(dp[-1])

Solution (Python):
def solve(l, r, i):
    if i - l < 1:
        return 0
    return dp[i - l] - dp[max(i - r - 1, 0)]


n, k = map(int, input().split())
lr = [list(map(int, input().split())) for _ in range(k)]
MOD = 998244353

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

for i in range(2, n + 1):
    tmp = 0
    for l, r in lr:
        tmp += solve(l, r, i)
    tmp = tmp % MOD
    dp[i] = (dp[i - 1] + tmp) % MOD

print(tmp)

Solution (Python):

import sys
import numpy as np
import numba
from numba import i8

input = sys.stdin.buffer.readline
mod = 998244353


def I():
    return int(input())


def MI():
    return map(int, input().split())


@numba.njit((i8, i8[:]), cache=True)
def main(N, LR):
    L, R = LR[::2], LR[1::2]
    K = len(L)

    dp = np.zeros(N + 1, np.int64)
    dpsum = np.zeros(N + 1, np.int64)
    dp[1] = 1
    dpsum[1] = 1

    for i in range(2, N + 1):
        for k in range(K):
            li = i - R[k]
            ri = i - L[k]
            if ri < 0:
                continue
            li = max(li, 1)
            dp[i] += dpsum[ri] - dpsum[li - 1]
            dp[i] %= mod
        dpsum[i] = dpsum[i - 1] + dp[i]
        dpsum[i] %= mod

    return dp[N]


N, K = MI()
LR = np.array(sys.stdin.buffer.read().split(), np.int64)

print(main(N, LR))

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

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

print(dp[-1])

Solution (Python):
n, k = map(int, input().split())
mod = 998244353
d = [0] * (n + 1)
d[1] = 1
LR =[list(map(int, input().split())) for _ in range(k)]

for i in range(2, n+1):
  d[i] = d[i - 1]
  for l, r in LR:
    if i - l <= 0:
      continue
    d[i] = (d[i] + (d[i-l] - d[max(0,i-r-1)])) % mod
print((d[-1] - d[-2])%mod)

Solution (Python):
def solve(l, r, i):
    if i - l < 1:
        return 0
    return dp[i - l] - dp[max(i - r - 1, 0)]


n, k = map(int, input().split())
MOD = 998244353
lr = [list(map(int, input().split())) for _ in range(k)]

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

for i in range(2, n + 1):
    tmp = 0
    for l, r in lr:
        tmp += solve(l, r, i)
    tmp = tmp % MOD
    dp[i] = (dp[i - 1] + tmp) % MOD

print(tmp)

Solution (Python):

import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

input = sys.stdin.buffer.readline
mod = 998244353


def I():
    return int(input())


def MI():
    return map(int, input().split())


@njit((i8, i8[:]), cache=True)
def main(N, LR):
    L, R = LR[::2], LR[1::2]
    K = len(L)

    dp = np.zeros(N + 1, np.int64)
    dpsum = np.zeros(N + 1, np.int64)
    dp[1] = 1
    dpsum[1] = 1

    for i in range(2, N + 1):
        for k in range(K):
            li = i - R[k]
            ri = i - L[k]
            if ri < 0:
                continue
            li = max(li, 1)
            dp[i] += dpsum[ri] - dpsum[li - 1]
            dp[i] %= mod
        dpsum[i] = dpsum[i - 1] + dp[i]
        dpsum[i] %= mod

    return dp[N]


N, K = MI()
LR = np.array(sys.stdin.buffer.read().split(), np.int64)

print(main(N, LR))

Solution (Python):
import sys
input = sys.stdin.readline
INF = 10**18
sys.setrecursionlimit(10**6)
import itertools as it
import collections as cl
from collections import deque
import math
from functools import reduce
from collections import defaultdict
MOD = 998244353


def li():
    return [int(x) for x in input().split()]

N, K = li()

L, R = [], []
for _ in range(K):
    l, r = li()
    L.append(l)
    R.append(r)


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



dpsum = [0] * (N+1)
dpsum[1] = 1
for i in range(2, N+1):
    for j in range(K):
        li = max(i - R[j], 1)
        ri = i - L[j]
        if ri >= 0:
            dp[i] += dpsum[ri] - dpsum[li-1]
            dp[i] %= MOD
    dpsum[i] = dpsum[i-1] + dp[i]
    dpsum[i] %= MOD

print(dp[N])

Solution (Python):
'''
自宅用PCでの解答
'''
import math

import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

mod = 998244353
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"
INF = 1<<32-1


def main():
    n,k = map(int,ipt().split())
    dp = [0]*(n+1)
    dp[1] = 1
    rng = [tuple(map(int,ipt().split())) for i in range(k)]
    for i in range(2,n+1):
        for l,r in rng:
            dp[i] += dp[max(0,i-l)]-dp[max(0,i-r-1)]
        dp[i] += dp[i-1]
        dp[i] %= mod

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

    return None

if __name__ == '__main__':
    main()

Solution (Python):

import sys
import numpy as np




input = sys.stdin.readline
mod = 998244353


def I():
    return int(input())


def MI():
    return map(int, input().split())



def main(N, steps):
    dp = np.zeros(N + 1, np.int64)
    dpsum = np.zeros(N + 1, np.int64)
    dp[1] = 1
    dpsum[1] = 1
    for i in range(2, N + 1):
        for l, r in steps:
            li = i - r
            ri = i - l
            if ri < 0:
                continue
            li = max(li, 1)
            dp[i] += dpsum[ri] - dpsum[li - 1]
            dp[i] %= mod
        dpsum[i] = dpsum[i - 1] + dp[i]
        dpsum[i] %= mod

    return dp[N]


N, K = MI()

steps = []
for _ in range(K):
    l, r = MI()
    steps.append((l, r))


print(main(N, steps))

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

for _ in range(K):
  L, R = map(int, input().split())
  move.append((L, R))

S = [0]*K
dp = [0]*(2*N)
dp[N] = 1

for i in range(N+1, 2*N):
  for k, (l, r) in enumerate(move):
    S[k] -= dp[i-r-1]
    S[k] += dp[i-l]
    dp[i] += S[k]
  dp[i] %= mod

print(dp[-1])

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


dp, acc = [0] * (n + 1), [0] * (n + 1)
dp[1], acc[1] = 1, 1
for i in range(2, n + 1):
    for l, r in lr:
        accl, accr = max(i - (r + 1), 0), max(i - l, 0)
        dp[i] += acc[accr] - acc[accl]
    dp[i] %= mod
    acc[i] = (dp[i] + acc[i - 1]) % mod
print(dp[n])

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

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


def get(l, r, i):
    return dp_sum[max((i - l), 0)] - dp_sum[max((i - r-1), 0)]


for i in range(1, N+1):
    for l, r in LR:
        dp[i] += get(l, r, i) % MOD
    dp_sum[i] = (dp_sum[i - 1] + dp[i])%MOD
print(dp[N] % MOD)

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

dp = [0] * (n + 1)
acc = [0] * (n + 1)
dp[1], acc[1] = 1, 1
for i in range(2, n + 1):
    for l, r in lr:
        dp[i] += acc[max(i - l, 0)]
        dp[i] -= acc[max(i - (r + 1), 0)]
    dp[i] %= mod
    acc[i] = (dp[i] + acc[i - 1]) % mod
print(dp[n])

Solution (Python):
N, K = [int(v) for v in input().split()]

links = []
for k in range(K):
    L, R = [int(v) for v in input().split()]
    links.append((L, R))

links = sorted(links, key=lambda x: x[1])

count = [1]
sub = [0, 1]
subtotal = 1

for i in range(1, N):
    v = 0
    for l, r in links:
        r2 = i - l + 1
        l2 = i - r
        if l2 < 0:
            l2 = 0
        if r2 >= 0:
            v += sub[r2] - sub[l2]

    count.append(v % 998244353)
    subtotal = (subtotal + v) % 998244353
    sub.append(subtotal )

print(count[-1])

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

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

dp[1] = 1
acc[1] = 1
for i in range(2, N+1):
    for lr in LR:
        l = lr[0]
        r = lr[1]

        dp[i] += (acc[max(0, i - l)] - acc[max(0, i - r - 1)] + MOD)
        dp[i] %= MOD
    acc[i] = (acc[i-1] + dp[i]) % MOD
    
    

print(dp[N])

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

L = [0] * K
R = [0] * K
for i in range(0, K):
    L[i], R[i] = map(int, input().split())

moves = [0] * N
moves[0] = 1

rui_wa = [0] * N
rui_wa[0] = 1

for i in range(1, N):
    for j in range(0, K):
        l = max(i - L[j], 0)
        r = max(i - R[j], 0)
        if i - L[j] < 0:
            continue

        moves[i] += (rui_wa[l] - rui_wa[r - 1]) % 998244353

    rui_wa[i] = (moves[i] + rui_wa[i - 1])  % 998244353



print(moves[N - 1] % 998244353)

Solution (Python):
(n,_),*s=[[*map(int,t.split())]for t in open(0)]
d=[1,-1]+[c:=0]*2*n
for i in range(n):
 c=(c+d[i])%998244353
 for l,r in s:d[i+l]+=c;d[i-~r]-=c
print(c)

Solution (Python):
import sys
import math
import itertools
import collections
from collections import deque
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
MOD2 = 998244353
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def main():
    N, K = NMI()
    LR = list(sorted([NLI() for _ in range(K)]))
    
    dp = [0 for _ in range(N)]
    dp[0] = 1
    
    cumsum = [0 for _ in range(N+1)]
    cumsum[0] = 0
    cumsum[1] = 1
    
    for n in range(1,N):
        for k in range(K):
            r = n-LR[k][0]
            l = n-LR[k][1]
            if r < 0:
                continue
            else:
                l = max(0,l)
            dp[n] += cumsum[r+1]-cumsum[l]
        dp[n] = dp[n]%MOD2
        cumsum[n+1] = (dp[n] + cumsum[n])%MOD2
    print(dp[-1])
if __name__ == '__main__':
    main()