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):
def main():
    n, k = map(int, input().split())
    lr = [list(map(int, input().split())) for _ in range(k)]
    dp = [0] * (n + 1)
    dp[1] = 1
    dpsum = [0] * (n + 1)
    dpsum[1] = 1
    mod = 998244353

    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] = (dp[i] + dpsum[ri] - dpsum[li - 1]) % mod
        dpsum[i] = dpsum[i - 1] + dp[i]

    print(dp[-1] % mod)


if __name__ == "__main__":
    main()

Solution (Python):
def main():
    n, k = map(int, input().split())
    lr = [list(map(int, input().split())) for _ in range(k)]
    dp = [0] * (n + 1)
    dp[1] = 1
    dpsum = [0] * (n + 1)
    dpsum[1] = 1
    mod = 998244353

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

    print(dp[-1] % mod)


if __name__ == "__main__":
    main()

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

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

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

for i in range(2, N+1):
    for l, r in LR:
        if i - l >= 1:
            dp[i] += dp_sum[i-l] - dp_sum[max(0, i-r-1)]
            dp[i] %= MOD
    dp[i] %= MOD
    dp_sum[i] = dp_sum[i-1] + dp[i]
        
print(dp[N]%MOD)

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

Solution (Python):
n,k=map(int,input().split())
mod=998244353
lr=[]
for i in range(k):
    lr.append(list(map(int,input().split())))
d=[0]*(n+1)
d[0]=1
for i in range(n): 
    for l,r in lr:
        r+=1
        d[min(n,i+l)]+=d[i]
        d[min(n,i+r)]-=d[i]
    if i!=0:
        d[i+1]+=d[i]
    d[i+1]%=mod

print(d[n-1]%mod)

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

L, R = [], []

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

dp = [0] * 300000
dpsum = [0] * 300000
dp[1] = 1
dpsum[1] = 1

for i in range(2, N+1):
    for j in range(K):
        li = min(L[j], i)
        ri = min(R[j], i + 1)
        dp[i] += dpsum[i - li] - dpsum[i - ri - 1]

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

print(dp[N])

Solution (Python):

from math import floor, ceil, sqrt, factorial, log, gcd
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from heapq import heappop, heappush, heappushpop, heapify
import copy
import sys
INF = float('inf')
mod = 10**9+7
sys.setrecursionlimit(10 ** 6)


def lcm(a, b): return a * b / gcd(a, b)





def LI(): return list(map(int, sys.stdin.buffer.readline().split()))




def I(): return int(sys.stdin.buffer.readline())





def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()




def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')







def IR(n): return [I() for i in range(n)]







def LIR(n): return [LI() for i in range(n)]







def SR(n): return [S() for i in range(n)]







def LSR(n): return [LS() for i in range(n)]







def SRL(n): return [list(S()) for i in range(n)]




















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

Solution (Python):
n,k=map(int,input().split())
mod=998244353
lr=[]
for i in range(k):
    lr.append(list(map(int,input().split())))
d=[0]*(n+1)
d[0]=1
for i in range(n): 
    for l,r in lr:
        r+=1
        d[min(n,i+l)]+=d[i]
        d[min(n,i+r)]-=d[i]
    if i!=0:
        d[i+1]+=d[i]
    d[i+1]%=mod

print(d[n-1]%mod)

Solution (Python):
p = 998244353
n, k = map(int, input().split())
LRs = []
for j in range(k):
    lj, rj = map(int, input().split())
    LRs.append((lj, rj))
A = [0] * (n + 1)
i0 = min(lj for lj, rj in LRs)
A[0] = 1
A[i0] = 1
for i in range(i0 + 1, n):
    A[i] = A[i - 1]
    for j in range(k):
        lj, rj = LRs[j]
        if i - lj >= 0:
            A[i] += A[i - lj]
        if i - 1 - rj >= 0:
            A[i] -= A[i - 1 - rj]
        A[i] %= p
print(A[n - 1])

Solution (Python):
N,K = map(int,input().split())
L = []
for _ in range(K):
  l,r = map(int,input().split())
  L.append((l,r))
DP = [0] * N
DP[0] = 1
con = [0] * (N + 1)
con[1] = 1
for i in range(1 , N):
  s = 0
  for l,r in L:
    s += con[max(0 , i - l + 1)] - con[max(0 , i - r)]
  DP[i] = s
  con[i + 1] = (con[i] + DP[i]) % 998244353
  
print(DP[N - 1] % 998244353)

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

INF = 998244353

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

dp = [0] * N
dp[0] = 1
a_sum = [0] * N
a_sum[0] = 1
for i in range(1, N):
    for lr in LR:
        if i - lr[0] >= 0:
            if i - lr[1]-1 >= 0:
                
                dp[i] = dp[i] + a_sum[i-lr[0]] - a_sum[i-lr[1]-1]
            else:
                dp[i] = dp[i] + a_sum[i-lr[0]]
    dp[i] %= INF
    a_sum[i] = a_sum[i-1] + dp[i]
    a_sum[i] %= INF
    
print(dp[-1])

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

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
dp_sum = [0] * (N + 1)
dp_sum[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 < 1:
            continue
        dp[i] += (dp_sum[ri] - dp_sum[li - 1]) % MOD
    dp_sum[i] = (dp_sum[i - 1] + dp[i]) % MOD

print(dp[-1] % MOD)

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

LR = []

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

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

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

print(dp[-1] % 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
dp[0]=1
dpc=[0]*(N+1)
dpc[1]=1

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

print(dp[N-1])

Solution (Python):
import numpy as np  
import numba
from numba import njit, b1, i4, i8, f8

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

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


jumps = np.array(jumps)


@njit((i8, i8, i8[:]), cache=True)
def main(N, m, jumps):
    L, R = jumps[::2], jumps[1::2]
    dpsum = np.zeros(N + 1)
    dp = np.zeros(N + 1)
    dp[1] = dpsum[1] = 1

    for i in range(2, N + 1):
        for j in range(len(L)):
            mn = max(0, i - R[j])
            mx = max(mn, i - L[j])
            dp[i] = (dp[i] + dpsum[mx] - dpsum[mn - 1]) % m
        dpsum[i] = (dp[i] + dpsum[i - 1]) % m
    return dp[N]


print(int(main(N, m, jumps)))

Solution (Python):

def main():
    import numpy as np

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

    dp = np.zeros(N + 1, dtype=np.int64)
    dp[1] = 1
    cumsum = np.zeros(N + 1, dtype=np.int64)
    cumsum[1] = 1
    for i in range(2, N + 1):
        for left_section, right_section in section:
            left = max(i - right_section - 1, 0)
            right = i - left_section
            if right < 0:
                continue
            dp[i] += cumsum[right] - cumsum[left]
        cumsum[i] = cumsum[i - 1] + dp[i]
        dp[i] %= MOD
        cumsum[i] %= MOD
    print(dp[N] % MOD)
    
    


if __name__ == '__main__':
    main()

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

count = 0
for _ in range(K):
    a,b = map(int, input().split())
    for _1 in range(_):
        x,y = L[_1],R[_1]
        if x <= a <= y or x <= b <= y :
            L[_1] = min(a,x)
            R[_1] = max(b,y)
            break
    else:
        L[_],R[_] =a,b
        count += 1
L,R = L[0:count+1],R[0:count+1]

MOD = 998244353
dp = [0]*(4*10**5+100)
for l, r in zip(L, R):
    dp[min(N + 1, 1 + l)] += 1
    dp[min(N + 1, 1 + r + 1)] -= 1

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

print(dp[N]%MOD)

Solution (Python):
n,k=map(int,input().split())
lr=[list(map(int,input().split())) for _ in range(k)]
accum=[0]*k
dp=[0]*(n+1)
dp[1]=1
mod=998244353
for num in range(2,n+1):
    for i in range(k):
        l,r=lr[i]
        if l<num<=r:
            accum[i]+=dp[num-l]
            accum[i]%=mod
            dp[num]+=accum[i]
        elif r<num:
            accum[i]+=dp[num-l]-dp[num-r-1]
            accum[i]%=mod
            dp[num]+=accum[i]
        dp[num]%=mod
print(dp[n])

Solution (Python):




import bisect



    







mod = 998244353
INF = 1<<50

def readInt():
    return list(map(int,input().split()))

def main():
    n,k = readInt()
    l = []
    r = []
    for i in range(k):
        a,b = readInt()
        l.append(a)
        r.append(b)
    dp = [0 for i in range(n+1)]
    dp[1] = 1
    dpsum = [0 for i in range(n+1)]
    dpsum[1] = 1
    for i in range(2,n+1):
        for j in range(k):
            lj = max(1,i - r[j])
            rj = i - l[j]
            if rj<1:
                continue
            dp[i] += dpsum[rj] - dpsum[lj-1]
            dp[i] %= mod
        dpsum[i] = dpsum[i-1] + dp[i]
    print(dp[n])
    return

if __name__=='__main__':
    main()

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

mod = 998244353

m_list = []

for _ in range(k):
    m_list.append(list(map(int, input().split())))

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

dp_sum = [0]*n
dp_sum[0] = 1

for i in range(1, n):
    for j in range(k):
        l, r = m_list[j]
        il = i-l
        ir = i-r-1
        if il < 0:
            continue
        else:
            if ir < 0 :
                dp[i] += dp_sum[il]
            else:
                dp[i] += dp_sum[il] - dp_sum[ir]
            dp[i] %= mod
    dp_sum[i] = dp_sum[i-1] + dp[i]
    dp_sum[i] %= mod

print(dp[n-1] % mod)

Solution (Python):


import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union































def main():
    Num = Union[int, float]
    
    mod = 998244353
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    def input():  return sys.stdin.readline().rstrip()
    def ii():     return int(input())
    def isp():    return input().split()
    def mi():     return map(int, input().split())
    def mi_0():   return map(lambda x: int(x)-1, input().split())
    def lmi():    return list(map(int, input().split()))
    def lmi_0():  return list(map(lambda x: int(x)-1, input().split()))
    def li():     return list(input())
    def debug(x): print(x, file=sys.stderr)
    
    
    
    n, k = mi()
    L = [lmi() for _ in range(k)]
    dp = [0] * n
    dp[0] = 1
    acc = [0] * (n + 1)    
    acc[1] = 1
    for i in range(1, n):
        s = 0
        for l, r in L:
            
            s = (s + acc[max(0, i - l + 1)] - acc[max(0, i - r)]) % mod
        dp[i] = s
        acc[i+1] = (acc[i] + dp[i]) % mod
        
        
    print(dp[n-1])


if __name__ == "__main__":
    main()

Solution (Python):
N, K = list(map(int, input().split()))
C = 998244353
L = [None]*K
for j in range(K):
    l, r = list(map(int, input().split()))
    L[j] = [l, r+1]

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

for i in range(N-1):
    if i > 0:
        imsm[i] = imsm[i-1]+imos[i]
        dp[i] = imsm[i] % C
    a = dp[i]
    
    for j in range(K):
        l, r = L[j]
        nl = min(i+l, N)
        nr = min(i+r, N)
        imos[nl] += a
        imos[nr] -= a
        
dp[N-1] = (imsm[N-2]+imos[N-1]) % C
print(dp[N-1])

Solution (Python):


import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union































def main():
    Num = Union[int, float]
    
    mod = 998244353
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    def input():  return sys.stdin.readline().rstrip()
    def ii():     return int(input())
    def isp():    return input().split()
    def mi():     return map(int, input().split())
    def mi_0():   return map(lambda x: int(x)-1, input().split())
    def lmi():    return list(map(int, input().split()))
    def lmi_0():  return list(map(lambda x: int(x)-1, input().split()))
    def li():     return list(input())
    def debug(x): print(x, file=sys.stderr)
    
    
    
    n, k = mi()
    L = [lmi() for _ in range(k)]
    dp = [0] * n
    dp[0] = 1
    acc = [0] * (n + 1)    
    acc[1] = 1
    for i in range(1, n):
        s = 0
        for l, r in L:
            
            s = (s + acc[max(0, i - l + 1)] - acc[max(0, i - r)]) % mod
        dp[i] = s
        acc[i+1] = (acc[i] + dp[i]) % mod
        
        
    print(dp[n-1])


if __name__ == "__main__":
    main()

Solution (Python):

import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    mod=998244353
    n, k = map(int, input().split())
    lr = []
    for i in range(k):
        l, r = map(int, input().split())
        lr.append((l, r))
    ans=[1]
    acc_ans=[1]
    for i in range(1, n):
        wa = 0
        for l, r in lr:
            if i-r > 0:
                wa+=-acc_ans[i-r-1]+acc_ans[i-l]
            elif i-l>=0:
                wa+=acc_ans[i-l]
        wa%=mod
        ans.append(wa)
        acc_ans.append(wa+acc_ans[-1])
    print(ans[-1])


if __name__ == '__main__':
    main()

Solution (Python):
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mat = lambda x, y, v: [[v]*y for _ in range(x)]
ten = lambda x, y, z, v: [mat(y, z, v) for _ in range(x)]
mod = 1000000007
sys.setrecursionlimit(1000000)

mod = 998244353

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

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

bit = BIT(N+1)
bit.add(1, 1)
bit.add(2, -1)

ans = 0
for i in range(1, N+1):
	s = bit.sum(i)
	s %= mod
	
	for k in range(K):
		l, r = lr[k]
		if i+l <= N:
			
			bit.add(i+l, s)
			if i+r+1 <= N:
				
				bit.add(i+r+1, -s)
			else:
				ans += s
				ans %= mod
print(ans)

Solution (Python):


import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union































def main():
    Num = Union[int, float]
    
    mod = 998244353
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    def input():  return sys.stdin.readline().rstrip()
    def ii():     return int(input())
    def isp():    return input().split()
    def mi():     return map(int, input().split())
    def mi_0():   return map(lambda x: int(x)-1, input().split())
    def lmi():    return list(map(int, input().split()))
    def lmi_0():  return list(map(lambda x: int(x)-1, input().split()))
    def li():     return list(input())
    def debug(x): print(x, file=sys.stderr)
    
    
    
    n, k = mi()
    L = [lmi() for _ in range(k)]
    dp = [0] * n
    dp[0] = 1
    acc = [0] * (n + 1)    
    acc[1] = 1
    for i in range(1, n):
        s = 0
        for l, r in L:
            
            s = (s + acc[max(0, i - l + 1)] - acc[max(0, i - r)]) % mod
        dp[i] = s
        acc[i+1] = (acc[i] + dp[i]) % mod
        
        
    print(dp[n-1])


if __name__ == "__main__":
    main()

Solution (Python):
'''
dp[i] = number of way to go from cell 0 to cell i
dp[0] = 1
for i in range(1, N):
    dp[i] = sum(dp[i - d] for d in seg for seg in segs)
Store dp in BIT
'''

mod = 998244353


class BIT:
    '''
    All methods use 0-based index while the internal use 1-based index
    '''

    def __init__(self, N, val=0):
        self.data = [val] * (N + 1)
        self.N = N

    def add_at(self, idx, val):
        i = idx + 1
        while i <= self.N:
            self.data[i] += val
            self.data[i] %= mod
            i += i & (-i)

    def sum_to(self, idx):
        res = 0
        i = idx + 1
        while i > 0:
            res += self.data[i]
            res %= mod
            i -= i & (-i)
        return res

    def range_sum(self, l, r):  
        return ((self.sum_to(r) - self.sum_to(l - 1)) + mod) % mod

    def __str__(self):
        data = [self.range_sum(i, i) for i in range(self.N)]
        return '[ ' + ' '.join(map(str, data)) + ' ]'


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

bit = BIT(N, 0)
bit.add_at(0, 1)
for i in range(N):
    for (l, r) in segs:
        lb = max(i - r, 0)
        ub = i - l
        if ub >= 0:
            val = bit.range_sum(lb, ub)
            bit.add_at(i, val)
print(bit.range_sum(N - 1, N - 1))

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

sys.setrecursionlimit(1000000)
MOD = 998244353
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 = [NLI() for _ in range(K)]
    dp = [0] * (N*2+10)
    dp[1] = 1
    now = 0

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

    print(dp[N])


if __name__ == "__main__":
    main()

Solution (Python):
def resolve():
    
    
    
    
    n,k=map(int,input().split())
    MOD=998244353
    lr=[list(map(int,input().split())) for _ in range(k)]
    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:
        li=i-r
        ri=i-l
        if r<0:continue
        li=max(1,li)
        dp[i]+=dpsum[ri]-dpsum[li-1]
      dpsum[i]=(dpsum[i-1]+dp[i])%MOD
    print(dp[n]%MOD)
    
if __name__ == '__main__':
    resolve()

Solution (Python):

import sys
import math
import itertools


n,k = (int(i) for i in input().split())


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

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

for i in range(2,n+1):
    for a in lr:
        if a[0] < i:
            dp[i] += ans[i-a[0]]
            if a[1] < i-1:
                dp[i] -= ans[i-a[1]-1]
    dp[i] = dp[i] % 998244353
    ans[i]=ans[i-1]+dp[i]

print(dp[n]%998244353)

Solution (Python):
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mat = lambda x, y, v: [[v]*y for _ in range(x)]
ten = lambda x, y, z, v: [mat(y, z, v) for _ in range(x)]
mod = 1000000007
sys.setrecursionlimit(1000000)

mod = 998244353

N, K = rl()
lr = []
for i in range(K):
	l, r = rl()
	lr.append((l,r))
lr.sort()

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

ans = 0
s = 0
flags = [1] * K
for i in range(1, N+1):
	s += dp[i]
	s %= mod
	for k in range(K):
		if flags[k] == 0:
			break
		l, r = lr[k]
		if i+l <= N:
			dp[i+l] += s
			if i+r+1 <= N:
				dp[i+r+1] -= s
			else:
				ans += s
				ans %= mod
				break
		else:
			flags[k] = 0
			break
print(ans)

Solution (Python):

n,k=map(int,input().split())
l=[0]*k
r=[0]*k
for j in range(k):
  l[j],r[j] = map(int,input().split())
p=998244353
dp=[0]*(n+max(r)+100)
dp[1]=1
dp[2]=-1
for i in range(1,n+1):
  dp[i] += dp[i-1]
  dp[i] %= p
  
  for lj,rj in zip(l,r):
    dp[i+lj] += dp[i]
    dp[i+lj] %= p
    dp[i+rj+1] -= dp[i]
    dp[i+rj+1] %= p
print(dp[n])

Solution (Python):

n,k=map(int,input().split())
l=[0]*k
r=[0]*k
for j in range(k):
  l[j],r[j] = map(int,input().split())
p=998244353
dp=[0]*(n+max(r)+100)
dp[1]=1
dp[2]=-1
for i in range(1,n+1):
  dp[i] += dp[i-1]
  dp[i] %= p
  
  for lj,rj in zip(l,r):
    dp[i+lj] += dp[i]
    dp[i+lj] %= p
    dp[i+rj+1] -= dp[i]
    dp[i+rj+1] %= p
print(dp[n])

Solution (Python):
def main():
    mod=998244353
    n,k=map(int,input().split())
    region=[]
    for _ in range(k):
        a,b=map(int,input().split())
        region.append((a,b))

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

    
    for j in region:
        if 1+j[0]<=n:
            work[1+j[0]]+=1
        if 1+j[1]+1<=n:
            work[1+j[1]+1]-=1    

    for i in range(2,n+1):
        dp[i]=dp[i-1]+work[i]
        dp[i]%=mod
        for j in region:
            if i+j[0]<=n:
                work[i+j[0]]+=dp[i]
                work[i+j[0]]%=mod
            if i+j[1]+1<=n:
                work[i+j[1]+1]-=dp[i]
                work[i+j[1]+1]%=mod
    print(dp[n])


main()

Solution (Python):
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

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

MOD = 998_244_353


@njit((i8, i8[:]), cache=True)
def main(N, LR):
    L, R = LR[::2], LR[1::2]
    K = len(L)
    F = np.zeros(N + 10, np.int64)
    F[0] = 1
    for n in range(1, N + 10):
        F[n] += F[n - 1]
        for k in range(K):
            l, r = L[k], R[k] + 1
            if n - l >= 0:
                F[n] += F[n - l]
            if n - r >= 0:
                F[n] -= F[n - r]
        F[n] %= MOD
    ans = F[N - 1] - F[N - 2]
    return ans % MOD


N, K = map(int, readline().split())
LR = np.array(read().split(), np.int64)

print(main(N, LR))

Solution (Python):
N, K = map(int, input().split())
mod = 998244353
L = [list(map(int, input().split())) for _ in range(K)]
D = {1: -1}
dp = [0 for _ in range(N)]
dp[0] = 1
for i in range(K):
    if L[i][0] in D:
        D[L[i][0]] -= 1
    else:
        D[L[i][0]] = -1
    if L[i][1]+1 in D:
        D[L[i][1]+1] += 1
    else:
        D[L[i][1]+1] = 1
dp[1] = -D[1] - 1
for i in range(2, N):
    for j in D:
        if i >= j:
            dp[i] += (-D[j]) * dp[i-j]
            dp[i] %= mod
print(dp[N-1])

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

dp = [0 for _ in range(2 * N + 1)]
dp[1] = 1

cum = [0 for _ in range(2 * N + 1)]
cum[1] = 1

for i in range(N):
    for l, r in S:
        dp[i + 1] += cum[i - l + 1] - cum[i - r]
        dp[i + 1] %= mod
    cum[i + 1] = cum[i] + dp[i + 1]
    cum[i + 1] %= mod
print(dp[N])

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

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

area.sort()
d = [0] * N
a = [0] * N


def func(pos):
    for l, r in area:
        if pos + l - 1 < N:
            a[pos + l-1] += d[pos]
        if pos + r < N:
            a[pos + r] -= d[pos]
    d[pos+1] = (d[pos] + a[pos]) % 998244353


d[0] = 1
a[0] = -1
for i in range(0, N-1):
    func(i)

print(d[N-1] % 998244353)

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

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

area.sort()
d = [0] * N
a = [0] * N


def func(pos):
    for l, r in area:
        if pos + l - 1 < N:
            a[pos + l-1] += d[pos]
        if pos + r < N:
            a[pos + r] -= d[pos]
    d[pos+1] = (d[pos] + a[pos]) % 998244353


d[0] = 1
a[0] = -1
for i in range(0, N-1):
    func(i)

print(d[N-1] % 998244353)

Solution (Python):
n, k = map(int, input().split())
lr = []
for _ in range(k):
    l, r = map(int, input().split())
    lr.append((l, r))
mod = 998244353
dp = [0]*(2*n+1)
dp[0] = 1
dp[1] = -1
now = 1
for i in range(n-1):
    for l, r in lr:
        dp[i+l] += now
        dp[i+r+1] -= now
    now += dp[i+1]
    now %= mod
print(now)

Solution (Python):
n,k = (int(x) for x in input().split())
lr = []
for _ in range(k):
    l,r = (int(x) for x in input().split())
    lr.append((l,r))
lr.sort()

mod = 998244353

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

for i in range(2,n+1):
    cnt = 0
    for l,r in lr:
        if l >= i:
            break
        else:
            cnt += dp[i-l] - dp[max(0,i-r-1)]
    dp[i] = (dp[i-1] + cnt) % mod

print(cnt%mod)

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

mod = 998244353

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

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

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

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

Solution (Python):
N,K = map(int, input().split())
d = [0]*2*K
for i in range(K):
    d[2*i], d[2*i+1] = map(int, input().split())
a=[0]*(N+1)
b=[0]*(N+1)
a[1]=1
b[1]=1
for i in range(2,N+1):
    t=0
    for j in range(K):
        if i-d[2*j]>0:
            t+=b[i-d[2*j]]
        if i-d[2*j+1]-1>0:
            t-=b[i-d[2*j+1]-1]
    a[i]=t%998244353
    b[i]=(b[i-1]+a[i])
print(a[N])

Solution (Python):
N,K = map(int, input().split())
LRs = []
P = 998244353
for _ in range(K):
  l,r = map(int, input().split())
  LRs.append((l,r))
  
memo = [0]*(N+2)
memo[1] = 1
memo[2] = -1
rlt = [0]*(N+2)
rlt[1] = 1


for i in range(1,N+1):
  for t in LRs:
    l = min(t[0]+i,N+1)
    r = min(t[1]+i+1,N+1)
    memo[l] = memo[l]+rlt[i]
    memo[r] = memo[r]-rlt[i]
  rlt[i+1] = (rlt[i]+memo[i+1])%P
  
print(rlt[N])

Solution (Python):

import sys


sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
printout = sys.stdout.write
sprint = sys.stdout.flush


sys.setrecursionlimit(10 ** 7)









INF = 1 << 50
EPS = 1e-8
mod = 998244353


def intread():
    return int(sysread())
def mapline(t=int):
    return map(t, sysread().split())
def mapread(t=int):
    return map(t, read().split())


def run():
    N, K = mapline()
    G = []
    for i in range(K):
        l, r = mapline()
        G.append((l, r))

    dp = [0]* N
    dp[0] = 1
    a = [0] * N
    a[1] = -1
    for k in range(0, N):
        if k >= 1:
            dp[k] = (dp[k-1] + a[k]) % mod
        for l, r in G:
            if k+l <= N-1:
                a[k+l] = (a[k+l] + dp[k]) % mod
            if k+r+1 <= N-1:
                a[k+r+1] = (a[k+r+1] - dp[k]) % mod

    print(dp[N-1])




if __name__ == "__main__":
    run()

Solution (Python):
N,K = map(int,input().split())
LR = [list(map(int,input().split())) for i in range(K)]
LR.sort()
mod = 998244353
ma = [0] * N
ma[0] = 1
for i in range(N):
    if i >1:
        ma[i] += ma[i-1]
    p = ma[i]%mod
    if p != 0:
        for l,r in LR:
            if i+l <N:
                ma[i+l] += p
            else:
                break
            if i+r+1<N:
                ma[i+r+1] -= p
print(ma[N-1]%mod)

Solution (Python):
N,K = list(map(int,input().split()))
p = 998244353
LR = []
for i in range(K):
    LR.append(list(map(int,input().split())))
T = [0]*(2*N+10)
T[1] = 1
S = [0]*(2*N+10)
S[1] = 1
S[2] = -1
for i in range(1,N):
    for j in range(K):
        L,R = LR[j]
        S[i+L]=S[i+L]+T[i]
        S[i+R+1]=S[i+R+1]-T[i]
    T[i+1] = (T[i]+S[i+1])%p
print(T[N])

Solution (Python):
import math

CON = 998244353

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

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

def solve():
    dp[1] = 1
    cs[1] = 1

    for i in range(2, N + 1):
        for pts in LR:
            if i - pts[0] > 0: dp[i] += cs[i-pts[0]] 
            if i - pts[1] > 0: dp[i] -= cs[i-(pts[1] + 1)] 
        dp[i] = dp[i] % CON
        cs[i] = (cs[i-1] + dp[i]) % CON

    print(dp[N])

solve()

Solution (Python):
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
ips = lambda:input().split()
import collections
import math
import itertools
import heapq as hq

n,k = ma()
mod =998244353
lr=[]
for i in range(k):
    lr.append(lma())
lr.sort()
dp = [0]*(n+1) 
dp[0]=1
tot=[0]*(n+1) 
tot[0]=1
for i in range(1,n):
    for l,r in lr:
        if i-l<0:
            continue
        elif i-r<0:
            r=i
        dp[i]+=tot[i-l]-tot[i-r-1]
        dp[i]%=mod
    tot[i]=(tot[i-1] + dp[i])%mod
    
print(dp[n-1])