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())
l=[0]*k
r=[0]*k
mod=998244353
for i in range(k):
    l[i],r[i]=map(int,input().split())
dp=[0]*n
sum_dp=[0]*n
dp[0]=1
sum_dp[0]=1
for i in range(1,n):
    for j in range(k):
        if (i-l[j]>=0):
            dp[i]+=sum_dp[i-l[j]]
            dp[i]%=mod
        if (i-r[j]-1>=0):
            dp[i]-=sum_dp[i-r[j]-1]
            dp[i]+=mod
            dp[i]%=mod
    sum_dp[i]=sum_dp[i-1]+dp[i]
    sum_dp[i]%=mod
print(dp[n-1])

Solution (Python):
n,k= list(map(int, input().strip().split()))
l=[0]*n
r=[0]*n
mod=998244353
for i in range(k):
    l[i],r[i] = list(map(int, input().strip().split()))

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 = i - r[j] 
        ri = i - l[j] 
        if ri < 0: 
            continue
        li = max(li,1) 
        dp[i] += dpsum[ri] - dpsum[li-1] 
    dpsum[i] = (dpsum[i-1]+dp[i])%mod
    
print(dp[n]%mod)

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

dp = [1]
cumdp = [0,1]
for i in range(1,N):
    tmp = 0
    for l,r in LR:
        if i-l+1 <= 0: continue
        tmp += cumdp[i-l+1] - cumdp[max(0,i-r)]
    tmp %= MOD
    dp.append(tmp)
    cumdp.append((cumdp[-1] + tmp) % MOD)
print(dp[-1])

Solution (Python):
inf=998244353


N,K=map(int,input().split())
SS=[list(map(int,input().split())) for i in range(K)]

SS.sort()

table = [0 for k in range(N)] 
diff = [0 for k in range(N-1)]

table[0]=1
diff[0]=-1

for i in range(N-1):
    if table[i]!=0:
        for s in SS:
            lef=s[0]
            rig=s[1]
            if i+lef-1<N-1:
                diff[i+lef-1]+=table[i]
            if i+rig<N-1:
                diff[i+rig]-=table[i]
    table[i+1]=table[i]+diff[i]
    table[i+1]%=inf

print(table[N-1])

Solution (Python):

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

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

for i in range(1, N):
    for l, r in X:
        dp[i] += sdp[max(0, i - l + 1)] - sdp[max(0, i - r)]
        dp[i] %= MOD
    sdp[i + 1] = sdp[i] + dp[i]
    sdp[i + 1] %= MOD

print(dp[-1])

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

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

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

for i in range(2, N+1):
    for l, r in kukan:
        li = max(i - l, 0)
        ri = max(i - r - 1, 0)

        dp[i] += sumdp[li] - sumdp[ri]
        dp[i] %= MOD

    sumdp[i] = sumdp[i-1] + dp[i]

print(dp[N])

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
MOD = 998244353
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N, K = LI()
    LR = [LI() for _ in range(K)]

    dp = [0] * (N + 1)
    dp[0] = 1
    a = [0] * (N + 1)
    a[0] = 1
    a[1] = -1
    for i in range(N):
        for l, r in LR:
            left = min(i + l, N)
            right = min(i + r + 1, N)
            a[left] += dp[i]
            a[right] -= dp[i]
        dp[i+1] += dp[i] + a[i+1]
        dp[i+1] %= MOD
        
        

    print(dp[-2])

if __name__ == '__main__':
    resolve()

Solution (Python):
n,k = map(int,input().split())
mod = 998244353
dp = [0]*(n+10)
dpsum = [0]*(n+10)
dp[1] = dpsum[1] = 1
L = [0]*k
R = [0]*k
for i in range(k):
    l,r = map(int,input().split())
    L[i],R[i] = l,r
for i in range(2,n+1):
    for j in range(k):
        li = i-R[j]
        ri = i-L[j]
        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
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)
csum=[0]*(n+2)
dp[0]=1

for i in range(n):
    for j in range(k):
        l,r=lr[j]
        dp[i]+=csum[max(i+1-l,0)]-csum[max(i-r,0)]
        dp[i]%=mod
    csum[i+1]+=dp[i]+csum[i]
    csum[i+1]%=mod

print(dp[n-1])

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

l = [0] * k
r = [0] * k
dp = [0] * (n+1)
dpsum = [0] * (n+1)
dp[1] = 1
dpsum[1] = 1

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

for i in range(2, n+1):
    for j in range(k):
        li = max(1, i - r[j])
        ri = i - l[j]
        if ri >= 0:
            dp[i] += dpsum[ri] - dpsum[li-1]
    dp[i] = dp[i] % 998244353
    dpsum[i] = (dpsum[i-1] + dp[i]) % 998244353
    
print(dp[n])

Solution (Python):
N, K = map(int, input().split())
MOD = 998244353
t = []
for _ in range(K):
    l, r = map(int, input().split())
    t.append((l, r))
dp = [0]*(N+1)
dp[1] = 1
dps = [0]*(N+1)
dps[1] = 1
for i in range(2, N+1):
    for j in range(K):
        li = i-t[j][0]
        ri = i-t[j][1]
        if li < 0:
            continue
        ri = max(ri, 1)
        dp[i] += dps[li]-dps[ri-1]
        dp[i] %= MOD
    dps[i] = dps[i-1]+dp[i]
    dps[i] %= MOD
print(dp[N])

Solution (Python):
N, K = (int(i) for i in input().split())
l, r = [0]*K, [0]*K
for k in range(K):
    l[k], r[k] = (int(x) for x in input().split())



'''
import numpy as np
dp = [0]*N
dp[0] = 1
for i in range(N):
    for k in range(K):
        for j in range(l[k], r[k]+1):
            if (i+j < N):
                dp[i+j] = dp[i+j] + dp[i]
            if j == r[k]:
                print(i, (l[k], r[k]), dp, np.diff(dp))
print(dp[-1]%998244353)
'''



dp = [0]*N
dps = [0]*(N-1)
dp[0] = 1
dps[0] = -1
for i in range(N-1):
    for k in range(K):
        if i + l[k] - 1 < (N - 1):
            dps[i + l[k] - 1] += dp[i]
        if i + r[k] < (N - 1):
            dps[i + r[k]    ] -= dp[i]
        
    dp[i+1] = (dps[i] + dp[i])%998244353
print(dp[-1]%998244353)

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

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

dp[1] = 1
dp_rui[1] = 1

for i in range(2,n+1):
    for j in range(k):
        lft = i - lr[j][1]
        rht = i - lr[j][0]
        
        if rht <= 0:
            continue
        lft = max(1,lft)
        dp[i] += dp_rui[rht] - dp_rui[lft-1]
        
        dp[i] %= mod
        
        
    dp_rui[i] = dp_rui[i-1] + dp[i]
    dp_rui[i] %= mod

print(dp[n]%mod)

Solution (Python):
N, K = map(int, input().split())
Range = [None] * K

for i in range(K):
    Range[i] = list(map(int, input().split()))

sweep = {1: 1}
M = 998244353

value = 0
for cell in range(1, N+1):
    value += sweep.get(cell, 0)
    value = (value + M) % M
    for r in range(K):
        sweep[cell + Range[r][0]] = (sweep.get(cell + Range[r][0], 0) + value + M) % M
        sweep[cell + Range[r][1] + 1] = (sweep.get(cell + Range[r][1] + 1, 0) - value + M) % M

print(sweep.get(N, 0))

Solution (Python):

import sys
from math import factorial

MOD = 998244353
INF = 10000000000

def main():
    n, k = list(map(int, input().split()))  
    lrList = [list(map(int, input().split())) for _ in range(k)]  

    s = []
    for l, r in lrList:
        for i in range(l, r+1):
            s.append(i)
    s.sort()

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

    
    result = (sum[n] - sum[n-1]) % MOD
    
    print("{}".format(result))

if __name__ == '__main__':
    main()

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

import sys
readline = sys.stdin.readline

MOD = 998244353
def frac(limit):
    frac = [1]*limit
    for i in range(2,limit):
        frac[i] = i * frac[i-1]%MOD
    fraci = [None]*limit
    fraci[-1] = pow(frac[-1], MOD -2, MOD)
    for i in range(-2, -limit-1, -1):
        fraci[i] = fraci[i+1] * (limit + i + 1) % MOD
    return frac, fraci
frac, fraci = frac(1341398)
pr = 3
LS = 20
class NTT:
    def __init__(self):
        self.N0 = 1<<LS
        omega = pow(pr, (MOD-1)//self.N0, MOD)
        omegainv = pow(omega, MOD-2, MOD)
        self.w = [0]*(self.N0//2)
        self.winv = [0]*(self.N0//2)
        self.w[0] = 1
        self.winv[0] = 1
        for i in range(1, self.N0//2):
            self.w[i] = (self.w[i-1]*omega)%MOD
            self.winv[i] = (self.winv[i-1]*omegainv)%MOD
        used = set()
        for i in range(self.N0//2):
            if i in used:
                continue
            j = 0
            for k in range(LS-1):
                j |= (i>>k&1) << (LS-2-k)
            used.add(j)
            self.w[i], self.w[j] = self.w[j], self.w[i]
            self.winv[i], self.winv[j] = self.winv[j], self.winv[i]
        
    def _fft(self, A):
        M = len(A)
        bn = 1
        hbs = M>>1
        while hbs:
            for j in range(hbs):
                A[j], A[j+hbs] = A[j] + A[j+hbs], A[j] - A[j+hbs]
                if A[j] > MOD:
                    A[j] -= MOD
                if A[j+hbs] < 0:
                    A[j+hbs] += MOD
            for bi in range(1, bn):
                wi = self.w[bi]
                for j in range(bi*hbs*2, bi*hbs*2+hbs):
                    A[j], A[j+hbs] = (A[j] + wi*A[j+hbs])%MOD, (A[j] - wi*A[j+hbs])%MOD
            bn <<= 1
            hbs >>= 1

    def _ifft(self, A):
        M = len(A)
        bn = M>>1
        hbs = 1
        while bn:
            for j in range(hbs):
                A[j], A[j+hbs] = A[j] + A[j+hbs], A[j] - A[j+hbs]
                if A[j] > MOD:
                    A[j] -= MOD
                if A[j+hbs] < 0:
                    A[j+hbs] += MOD
            for bi in range(1, bn):
                winvi = self.winv[bi]
                for j in range(bi*hbs*2, bi*hbs*2+hbs):
                    A[j], A[j+hbs] = (A[j] + A[j+hbs])%MOD, winvi*(A[j] - A[j+hbs])%MOD
            bn >>= 1
            hbs <<= 1
    
    def convolve(self, A, B):
        LA = len(A)
        LB = len(B)
        LC = LA+LB-1
        M = 1<<(LC-1).bit_length()
        A += [0]*(M-LA)
        B += [0]*(M-LB)
        self._fft(A)
        self._fft(B)
        C = [0]*M
        for i in range(M):
            C[i] = A[i]*B[i]%MOD
        self._ifft(C)
        minv = pow(M, MOD-2, MOD)
        for i in range(LC):
            C[i] = C[i]*minv%MOD
        return C[:LC]
        
        return C
    
    def inverse(self, A):
        LA = len(A)
        dep = (LA-1).bit_length()
        M = 1<<dep
        A += [0]*(M-LA)
        
        g = [pow(A[0], MOD-2, MOD)]
        for n in range(dep):
            dl = 1<<(n+1)
            f = A[:dl]
            fg = self.convolve(f, g[:])[:dl]
            fgg = self.convolve(fg, g[:])[:dl]
            ng = [None]*dl
            for i in range(dl//2):
                ng[i] = (2*g[i]-fgg[i])%MOD
            for i in range(dl//2, dl):
                ng[i] = MOD-fgg[i]
            g = ng[:]
        return g[:LA]
    
    def integral(self, A):
        A = [1] + [A[i]*fraci[i+2]%MOD for i in range(len(A))]

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

A = [0]*(N+2)
for _ in range(K):
    l, r = map(int, readline().split())
    A[l] += 1
    A[r+1] -= 1

for i in range(1, N+1):
    A[i] += A[i-1]
A = A[:-1]
A[0] -= 1
A = [-a%MOD for a in A]

NN = NTT()
print(NN.inverse(A[:])[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):  
        assert i > 0
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


class BitImos:
    """
    ・範囲すべての要素に加算
    ・ひとつの値を取得
    の2種類のクエリをO(logn)で処理
    """
    def __init__(self, n):
        self.bit = Bit(n+1)

    def add(self, s, t, x):
        
        self.bit.add(s, x)
        self.bit.add(t, -x)

    def get(self, i):
        return self[i]

    def __getitem__(self, key):
        
        return self.bit.sum(key)


N, K = map(int, input().split())
LR = [tuple(map(int, input().split())) for _ in range(K)]

bit = BitImos(N+2)
bit.add(1, 2, 1)

mod = 998244353

for i in range(1, N+1):
    cur = bit.get(i) % mod
    for l, r in LR:
        if i + l > N:
            continue
        bit.add(i+l, min(i + r + 1, N + 2), cur)

print(bit.get(N) % mod)

Solution (Python):
n,k=map(int,input().split())
mod=998244353
R=[]
for _ in range(k):
  l,r=map(int,input().split())
  R.append([l,r])

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

Solution (Python):
n,k=map(int,input().split())
mod=998244353
R=[]
for _ in range(k):
  l,r=map(int,input().split())
  R.append([l,r])

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

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

    mod = 998244353

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

    S.sort()
    

    ans = [0]*N
    acc = [0]*N
    ans[0] = 1
    acc[0] = 1

    for i in range (1,N):
        for l,r in S:

            if i-l < 0:
                break
            else:
                ans[i] += acc[i-l]
            if i-r -1 < 0:
                break
            else:
                ans[i] -= acc[i-r-1]

        ans[i] %= mod
        acc[i] = (acc[i-1]+ans[i])%mod


    print(ans[N-1])


main()

Solution (Python):
def resolve():
    n, k = map(int, input().split())
    S = []
    L, R = [], []
    for _ in range(k):
        l1, r1 = map(int, input().split())
        L.append(l1)
        R.append(r1)

    dp = [0 for i in range(n + 1)]
    dpsum = [0 for i in range(n + 1)]
    dp[1] = 1
    dpsum[1] = 1
    for i in range(2, n + 1):
        for j in range(k):
            Li = i - R[j]
            Ri = i - L[j]
            if Ri < 0:
                continue
            Li = max(1, Li)
            dp[i] += dpsum[Ri] - dpsum[Li - 1]  
            dp[i] %=  998244353

        dpsum[i] = (dpsum[i - 1] + dp[i]) % 998244353

    print(dp[n])

resolve()

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

l = [0] * K
r = [0] * K

for i in range(K):
	l[i], r[i] = map(int, input().split())
	
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 = i - r[j]
		ri = i - l[j]
		if li <= 0:
			dp[i] = dp[i] + dpsum[ri]
			dp[i] %= MOD
		else:
			dp[i] = dpsum[ri] - dpsum[li-1] + dp[i]
			dp[i] %= MOD
			
			
	dpsum[i] = dp[i] + dpsum[i-1]
	dpsum[i] %= MOD
	
print(dp[N] % MOD)

Solution (Python):

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

l = []
r = []

MOD = 998244353

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

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 = i - r[j]
        ri = i - l[j]
        if ri < 0: continue
        
        li = max(1, li)
        dp[i] += (dpsum[ri] - dpsum[li-1])%MOD 
    dpsum[i] = (dpsum[i-1] + dp[i])%MOD

print(dp[N]%MOD)

Solution (Python):
from sys import stdin
import sys
sys.setrecursionlimit(10**7)


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, K = list(map(int, _in[0].split(' ')))  
    L_R_arr = []
    for i in range(K):
        _ = list(map(int, _in[i+1].split(' ')))  
        L_R_arr.append(_)
    
    dp = [0] * N
    sdp = [0] * (N+1)
    dp[0] = 1
    for i in range(N):
        for L, R in L_R_arr:
            right = max(0, i-L+1)
            left  = max(0, i-R)
            dp[i] += sdp[right] - sdp[left]
        else:
            sdp[i+1] = (sdp[i] + dp[i]) % 998244353
    ans = dp[-1] % 998244353
    
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

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



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

Solution (Python):
'''
    Auther: ghoshashis545 Ashis Ghosh
    College: jalpaiguri Govt Enggineering College

'''
from os import path
import sys
from heapq import heappush,heappop
from functools import cmp_to_key as ctk
from collections import deque,defaultdict as dd 
from bisect import bisect,bisect_left,bisect_right,insort,insort_left,insort_right
from itertools import permutations
from datetime import datetime
from math import ceil,sqrt,log,gcd
def ii():return int(input())
def si():return input().rstrip()
def mi():return map(int,input().split())
def li():return list(mi())
abc='abcdefghijklmnopqrstuvwxyz'

mod=998244353
inf = float("inf")
vow=['a','e','i','o','u']
dx,dy=[-1,1,0,0],[0,0,1,-1]

def bo(i):
    return ord(i)-ord('a')



    
def solve():

    
    

    n,k = mi()

    seg = []

    for i in range(k):
        seg.append(li())

    dp = [0]*(n+1)

    dp[1] = 1
    for i in range(2,n+1):
        dp[i] += dp[i-1]
        dp[i] %= mod
        for j in range(k):
            if seg[j][0] >= i:
                continue


            l = max(1,i - seg[j][1])

            r =  i - seg[j][0]

            dp[i] += dp[r] - dp[l-1]
            dp[i] += mod
            dp[i] %= mod


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


        









        
if __name__ =="__main__":

    
    if path.exists('input.txt'):
        sys.stdin=open('input.txt', 'r')
        sys.stdout=open('output.txt','w')
    else:
        input=sys.stdin.readline
    solve()

Solution (Python):
N,K=map(int, input().split())
P=998244353
S=[tuple(map(int,input().split())) for _ in range(K)]

f=[0]*(10**6)
f[0]=1
for i in range(N):
  for l, r in S:
    f[i+l] += f[i]
    f[i+l]%=P
    f[i+r+1]-=f[i]
    f[i+r+1]%=P
  if i:
    f[i+1]+=f[i]
  f[i]%=P
print(f[N-1])

Solution (Python):


n, k = map(int, input().split())
s_list = []
a_list = [0] * (n + 1)
b_list = [0] * (n + 1)
a_list[1] = 1
b_list[1] = 1
for i in range(k):
    l, r = map(int, input().split())
    s_list.append([l, r + 1])

for i in range(2, n + 1):
    for l, r in s_list:
        t2 = max(0, i - l)
        t1 = max(0, i - r)
        a_list[i] += b_list[t2] - b_list[t1]
    b_list[i] = (b_list[i - 1] + a_list[i]) % 998244353

print(a_list[n] % 998244353)

Solution (Python):
n,k=map(int,input().split())
lr=[]
for i in range(k):
  l_,r_=map(int,input().split())
  lr.append([l_,r_])
mod=998244353



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

dp[1]=1
sumdp[1]=1

for i in range(2,n+1):
  for l,r in lr:
    if i>l:
      if i<=r:
        dp[i]=(dp[i]+sumdp[i-l])%mod
      else:
        dp[i]=(dp[i]+sumdp[i-l]-sumdp[i-r-1])%mod
  sumdp[i]=(sumdp[i-1]+dp[i])%mod
  
  
print(dp[n]%mod)

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

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

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

for i in range(2, N+1):
    for s in S:
        l = i - s[1]
        r = i - s[0]
        if r < 1:continue
        l = max(1, l)

        dp[i] += dpsum[r] - dpsum[l-1]
        dp[i] %= mod

    dpsum[i] = (dpsum[i-1] + dp[i]) % mod

print(dp[-1])

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

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

mod = 998244353

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 = i - r[j]
    ri = i - l[j]
    if ri < 0:
      continue
    li = max(1, li)

    dp[i] += (dpsum[ri] - dpsum[li - 1]) % mod
  
  dpsum[i] = dpsum[i - 1] + dp[i]

print(dp[n] % mod)

Solution (Python):
mod = 998244353




def main(N, S):
    dp = [0 if n != 0 else 1 for n in range(N)]     
    A = [0 if n != 0 else 1 for n in range(N)]      

    for i in range(1, N):   
        for l, r in S:  
            if i - l < 0:   
                break
            else:           
                if i - r <= 0:  
                    dp[i] += A[i-l]
                else:
                    dp[i] += A[i-l] - A[i-r-1]
        dp[i] %= mod
        A[i] = (A[i-1] + dp[i]) % mod
    print(dp[-1])

if __name__ == '__main__':
    N, K = list(map(int, input().split()))
    S = {tuple(map(int, input().split())) for k in range(K)}
    S = sorted(list(S), key = lambda x:x[0])    
    main(N, S)

Solution (Python):
mod = 998244353



def main(N, S):
    dp = [0 if n != 0 else 1 for n in range(N)]     
    A = [0 if n != 0 else 1 for n in range(N)]      

    for i in range(1, N):   
        for l, r in S:  
            if i - l < 0:   
                break
            else:           
                if i - r <= 0:  
                    dp[i] += A[i-l]
                else:
                    dp[i] += A[i-l] - A[i-r-1]
        dp[i] %= mod
        A[i] = (A[i-1] + dp[i]) % mod
    print(dp[-1])

if __name__ == '__main__':
    N, K = list(map(int, input().split()))
    S = {tuple(map(int, input().split())) for k in range(K)}
    S = sorted(list(S), key = lambda x:x[0])    
    main(N, S)

Solution (Python):
mod = 998244353


def main(N, S):
    dp = [0 if n != 0 else 1 for n in range(N)]     
    A = [0 if n != 0 else 1 for n in range(N)]      

    for i in range(1, N):   
        for l, r in S:  
            if i - l < 0:   
                break
            else:           
                dp[i] += A[i-l] - A[max(i-r, 0)-1]  
        dp[i] %= mod
        A[i] = (A[i-1] + dp[i]) % mod
    print(dp[-1])

if __name__ == '__main__':
    N, K = list(map(int, input().split()))
    S = {tuple(map(int, input().split())) for k in range(K)}
    S = sorted(list(S), key = lambda x:x[0])    
    main(N, S)

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

DP=[0 for _ in range(n+1)]
SDP=[0 for _ in range(n+1)]
DP[1]=1
SDP[1]=1

for i in range(2,n+1):
    for l,r in LR:
        DP[i] +=(SDP[max(i-l,0)]-SDP[max(i-r,1)-1])%mod
        DP[i] %=mod
    SDP[i]=(SDP[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
dp[0] = 1
acc = 0

for i in range(1, n):
    
    for li, ri in lr:
        if i - li >= 0:
            acc += dp[i - li]
            acc %= mod
        if i - ri - 1 >= 0:
            acc -= dp[i - ri - 1]
            acc %= mod
    dp[i] = acc
print(dp[-1])

Solution (Python):
import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    

def main():
    N, K = MI()
    L = [LI() for i in range(K)]
    D = [0] * N
    D[0] = 1
    D[1] = -1
    num = 0
    mod = 998244353
    for index in range(N):
        num += D[index] % mod
        for l, r in L:
            if index + r + 1 <= N-1:
                D[index+l] += num
                D[index+r+1] -= num
            elif index+l <= N-1:
                D[index+l] += num
                
    print(num % mod)
    
if __name__ == "__main__":
    main()

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

NUM=998244353
dp=[0]*(N+1)
dp[1]=1
sums=[0]*(N+1)
sums[1]=1
for i in range(2,N+1):
    for s in S:
        _l,_r=i-s[0],i-s[1]-1
        if _l<0:
            continue
        elif _r<0:
            _r=0
        dp[i]+=sums[_l]-sums[_r]
        dp[i]%=NUM
    sums[i]=dp[i]+sums[i-1]
    sums[i]%=NUM

print(dp[N])

Solution (Python):
p = 998244353

n, k = map(int, input().split())
num = [tuple(map(int, input().split())) for _ in range(k)]

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

dp[0] = 1
dp[1] = -1

for i in range(n):
    for l, r in num:
        dp[i+l] += dp[i]
        dp[i+r+1] -= dp[i]
    dp[i+1] += dp[i]
    dp[i+1] %= p

print(dp[n-1])

Solution (Python):
n, k = map(int, input().split())
s = [] 
mod = 998244353

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

dp = [0 for _ in range(n+1)]
dp[1] = 1
dpsum = [0 for _ in range(n+1)]
dpsum[1] = 1

for i in range(2,n+1):
    for l, r in s:
        li = max(i-r,1)
        ri = max(i-l,0)
        dp[i] += (dpsum[ri] - dpsum[li-1])%mod
    dpsum[i] = (dpsum[i-1] + dp[i])%mod

print(dp[n]%mod)

Solution (Python):
N, K = map(int, input().split())
dp = [0] * N
dp[0] = 1
dp_sum = [0] * N
dp_sum[0] = 1
L = [0] * K
R = [0] * K
mod = 998244353

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

for i in range(1, N):
    
    cnt = 0
    for j in range(K):
        start = max(0, i - R[j])
        end = i - L[j]
        cnt += (dp_sum[end] - dp_sum[start - 1]) % mod
        cnt %= mod
    dp[i] = cnt
    dp_sum[i] = dp_sum[i - 1] + cnt

print(dp[N - 1])

Solution (Python):
n, k = map(int, input().split())
mod = 998244353
S = []
for _ in range(k):
    l, r = map(int, input().split())
    S.append([l, r])


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

Solution (Python):
n,k=map(int,input().split())
L=[]
R=[]
h=[0,1,-1]+[0]*400010
M=998244353
for i in range (k):
    l,r=map(int,input().split())
    L.append(l)
    R.append(r)
N=0
for i in range (1,n):
    N=(N+h[i]+100*M)%M
    for j in range (k):
        h[L[j]+i]+=N
        h[R[j]+i+1]-=N
print(((N+h[n])+100*M)%M)

Solution (Python):
from itertools import accumulate

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

DP = [0] * N
DP[0] = 1
DP[1] = -1
cnt = 0

for i in range(N):
    DP[i] += cnt
    DP[i] %= mod
    cnt = DP[i]
    for l, r in Move:
        if i + l < N:
            DP[i+l] += DP[i]
        if i + r + 1 < N:
            DP[i + r + 1] -= DP[i]

print(DP[-1])

Solution (Python):
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))


mod = 998244353
n,k = readints()
s = [readints() for i in range(k)]

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

b = [0] * k

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

print(a[-1])

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

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

for i in range(2, n + 1):
    for l, r in lr:
        if l >= i:
            continue

        ll = max(1, i - r)
        rr = i - l
        dp[i] += cumsum[rr] - cumsum[ll - 1]
        dp[i] %= mod
    cumsum[i] = cumsum[i - 1] + dp[i]
    cumsum[i] %= mod

print(dp[n] % mod)