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)]
    MOD = 998244353

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

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

if __name__ == '__main__':
    main()

Solution (Python):

import base64
import subprocess
import zlib


exe_bin = "c%1E9e{@q-p1&_iX@NEgTA-*55euhXAQC9p3e|+B@ZzS>fiQyzKGGy@Gqy=hUZ6PaSWl?(wi9Gr*X4}Pk>l>!(b;occh2tmW1O|6NR>HzmNI8XX4DnkQBzUD6|w%H+3)whd(-z`6ZAOyr<X&%_xpL@@ArQ1_ulut@7;HMce8)JNe~DxW^xljZtx0~cQZWe%!>e4Po~4~cgTD)4S0)2&Pc}vJuS<(qw3Y0RNhFhA$lrkXbCA^gepBH

open("./kyomu", 'wb').write(zlib.decompress(base64.b85decode(exe_bin)))
subprocess.run(["chmod +x ./kyomu"], shell=True)
subprocess.run(["./kyomu"], shell=True)

Solution (Python):
def main():
    n, k = map(int, input().split())
    mod = 998244353
    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = -1
    left = [0] * k
    right = [0] * k
    for i in range(k):
        left[i], right[i] = map(int, input().split())
        right[i] += 1
    for i in range(1, n + 1):
        dp[i] += dp[i - 1]
        for j in range(k):
            if i + left[j] <= n:
                dp[i + left[j]] += dp[i]
            if i + right[j] <= n:
                dp[i + right[j]] -= dp[i]
        dp[i] %= mod
    print(dp[n])


if __name__ == '__main__':
    main()

Solution (Python):
MOD = 998244353


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

    dp = [0] * (N+2)
    dpsum = [0] * (N+1)
    dp[1] = 1
    dpsum[1] = 1
    for i in range(2, N+1):
        for le, ri in LR:
            L = max(0, i - ri - 1)
            R = i - le
            if R < 1:
                continue
            dp[i] += dpsum[R] - dpsum[L]
            dp[i] %= MOD
        dpsum[i] += dpsum[i-1] + dp[i]
        dpsum[i] %= MOD
    print(dp[N])
    


if __name__ == '__main__':
    main()

Solution (Python):
MOD = 998244353


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

    dp = [0] * (N+2)
    dp[1] = 1
    dp[2] = -1
    for i in range(1, N+1):
        for le, ri in LR:
            if i+le <= N:
                dp[i+le] += dp[i]
                dp[i+le] %= MOD
            if i+ri+1 <= N:
                dp[i+ri+1] -= dp[i]
                dp[i+ri+1] %= MOD
        dp[i+1] += dp[i]
        dp[i+1] %= MOD
    print(dp[N])


if __name__ == '__main__':
    main()

Solution (Python):


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

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

dp = [0] * (n + 1)
dp[1] = 1
sdp = [0] * (n + 1)
sdp[1] = 1
for i in range(2, n + 1):
    for j in range(k):
        right = max(0, i - lr_list[j][0])
        left = max(0, i - lr_list[j][1] - 1)
        dp[i] = (dp[i] + sdp[right] - sdp[left]) % mod
    sdp[i] = sdp[i - 1] + dp[i]

print(dp[n])

Solution (Python):

def resolve():
    MOD = 998244353
    N, K = map(int, input().split())
    S = [tuple(map(int, input().split())) for _ in range(K)]
    L = [0] * K
    R = [0] * K
    L, R = zip(*S)
    
    

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

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

        dp_acum[i] = dp_acum[i - 1] + dp[i]
        dp_acum[i] %= MOD

    print(dp[N])


if __name__ == "__main__":
    resolve()

Solution (Python):
p=998244353
n,k=map(int,input().split())
kukan=[]
for i in range(k):
    l,r=map(int,input().split())
    kukan.append((l,r))
dp=[0]*n
sdp=[0]*(n+1)
dp[0]=1
sdp[1]=1
for i in range(1,n):
    for l,r in kukan:
        left=max(0,i-r)
        right=max(0,i-l+1)
        dp[i]=(dp[i]+sdp[right]-sdp[left])%p
    sdp[i+1]=(sdp[i]+dp[i])%p
print(dp[-1])

Solution (Python):

import sys
import collections as cl


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


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


MOD = 998244353


def main():
    N, K = MI()

    kukan = []
    for _ in range(K):
        tmp = LI()
        kukan.append(tmp)

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

    for i in range(N+1):
        for k in range(K):
            l, r = kukan[k]
            pre_l = i - r
            pre_r = i - l
            if pre_r < 0:
                continue
            pre_l = max(pre_l, 0)
            dp[i] += dp_sum[pre_r] - dp_sum[pre_l - 1]

        dp_sum[i] = dp[i] + dp_sum[i-1]
        dp_sum[i] %= MOD
        dp[i] %= MOD

    print(dp[-1])


main()

Solution (Python):
MOD = 998244353

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

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

LR = []

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

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

print((dp[N]-dp[N-1]) % MOD)

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

MOD = 998244353
dp = [0]*n  
dp[0] = 1 
dp[1] = -1  

for i in range(n): 
    if i > 0: dp[i] += dp[i-1] 
    for l, r in LR:
        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-1] + MOD) % MOD)

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

mod = 998244353
dp = [0]*(n+1)
dp[0],dp[1] = 0,1
cumsum = [0]*(n+1)
cumsum[1] = 1
for i in range(2,n+1):
  for l,r in sec:
    if i>l:
      dp[i] += cumsum[i-l]-cumsum[max(0,i-r-1)]
  cumsum[i] = (dp[i]+cumsum[i-1])%mod
print(dp[n]%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):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 998244353


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

    dp = [0] * (n + 1)
    dp_sum = [0] * (n + 1)
    dp[1] = 1
    dp_sum[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] += dp_sum[ri] - dp_sum[li - 1]
            dp[i] %= mod
        dp_sum[i] = dp_sum[i - 1] + dp[i]
        dp_sum[i] %= mod
    print(dp[n])


if __name__ == '__main__':
    resolve()

Solution (Python):
n, K = [int(a) for a in input().split()]
s = [[int(a) for a in input().split()] for _ in range(K)]

MOD = 998244353

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

for i in range(1, n+1):
    for l, r in s:
        dp[i] += dp_sum[i-l if (i-l) > 0 else 0] - dp_sum[(i-r-1) if (i-r-1) > 0 else 0]
        dp_sum[i] = (dp[i] + dp_sum[i-1]) % MOD

print(dp[n] % MOD)

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

MOD = 998244353
dp = [0]*(n+1)  
dp[0] = 1
dp[1] = -1

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

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

Solution (Python):
n, k = map(int, input().split())
mod = 998244353
list_s = []
for _ in range(k):
    l, r = map(int, input().split())
    list_s.append((l, r))
dp = [0] * (n + 1)
sdp = [0] * (n + 1)
dp[1] = 1
sdp[0] = 0
sdp[1] = 1

for i in range(2, n + 1):
    for l, r in list_s:
        dl = max(0, i - r - 1)
        dr = max(0, i - l)
        dp[i] += sdp[dr] - sdp[dl]
        sdp[i] = (sdp[i - 1] + dp[i]) % mod
print(dp[n] % mod)

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

mod = 998244353

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] * (n + 1)
dp_csum = [0] * (n + 1)
dp[1] = 1
dp_csum[1] = 1
for i in range(2, n + 1):
    for j in range(k):
        left = i - r[j]
        right = i - l[j]
        if right >= 1:
            dp[i] += dp_csum[right] - dp_csum[max(left, 1) - 1]
            dp[i] %= mod
    dp_csum[i] = dp_csum[i - 1] + dp[i]
    dp_csum[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 = [0] * (n+1)
sdp = [0] * (n+1)
dp[1] = 1
sdp[1] = 1

for i in range(n+1):
  for j in range(k):
    left = max(0, i-lr[j][1])
    right = max(0, i-lr[j][0]+1)
    
    dp[i] += sdp[right] - sdp[left]
  if i+1 <= n:
    sdp[i+1] = sdp[i]%mod + dp[i]%mod

print(dp[n]%mod)

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

Solution (Python):
N, K = map(int, input().split())
L = []
for _ in range(K):
  a, b = map(int, input().split())
  L.append((a,b))
L.sort()
DP_1 = [0]*N
DP_2 = [0]*(N+1)
DP_1[0], DP_2[1] = 1, 1
mod = 998244353
for i in range(1, N):
  for l in L:
    if l[0]>i:
      break
    elif l[1]>i:
      DP_1[i] += DP_2[i-l[0]+1]
      DP_1[i] %= mod
    elif l[1]<=i:
      DP_1[i] += DP_2[i-l[0]+1]-DP_2[i-l[1]]
      DP_1[i] %= mod
  DP_2[i+1] = DP_2[i] + DP_1[i]
  DP_2[i+1] %= mod
print(DP_1[-1]%mod)

Solution (Python):
import numpy as np

m = 998244353
N, K = map(int, input().split())
span = []
for K in range(K):
    l , r = map(int, input().split())
    span.append([l, r])

add = [0,1]
ans = [1]

for i in range(2,N+1):
    tmp = 0
    for s in span:
        l, r = s[0], s[1]+1
        if l > len(ans):
            continue
        elif r >= len(ans)+1:
            r = len(ans)+1
        tmp += (add[i-l] - add[i-r])%m
    ans.append(tmp%m)
    add.append(add[-1]+tmp)

print(ans[-1]%m)

Solution (Python):


N, K = map(int, input().split())
mod = 998244353
s = []
for k in range(K):
  s.append(list(map(int,input().split())))

cnt = [0]*N
cnt[0] = 1
sum = [0]*N
sum[0] = 1
for i in range(1,N):
  for j in range(K):
    
    if i > s[j][1]: 
      cnt[i] += sum[i-s[j][0]] - sum[i-s[j][1]-1]
    elif i >= s[j][0]:
      cnt[i] += sum[i-s[j][0]]
    cnt[i] = cnt[i] % mod
    sum[i] = (sum[i-1] + cnt[i])% mod
print(cnt[-1] % mod)

Solution (Python):







modnum = 998244353

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

def mod(num):
    return num % modnum

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

dp[1] = 1
sdp[1] = 1

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

        dp[i] += sdp[ri] - sdp[li]
        dp[i] = mod(dp[i])

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

print(dp[N])

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

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

for i in range(2,N+1):
    for l, r in S: 
        if i >= r + 1:
            dp[i] += dp_sums[i - l] - dp_sums[i - r - 1] 
            dp_sums[i] = dp_sums[i-1] + dp[i]
        elif i > l and i < r + 1:
            dp[i] += dp_sums[i - l] 
            dp_sums[i] = dp_sums[i-1] + dp[i]
        elif i <= l:
            dp_sums[i] = dp_sums[i-1] + dp[i]
    dp[i] %= 998244353
    dp_sums[i] %= 998244353
print(dp[N])

Solution (Python):
MOD = 998244353


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

    dp = [0] * (N+2)
    dp[1] = 1
    dp[2] = -1
    for i in range(1, N+1):
        for le, ri in LR:
            if i+le <= N:
                dp[i+le] += dp[i]
                dp[i+le] %= MOD
            if i+ri+1 <= N:
                dp[i+ri+1] -= dp[i]
                dp[i+ri+1] %= MOD
        dp[i+1] += dp[i]
        dp[i+1] %= MOD
    print(dp[N])


if __name__ == '__main__':
    main()

Solution (Python):

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
        self.depth = n.bit_length()
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
 
    def lower_bound(self, x):
        """ 累積和がx以上になる最小のindexと、その直前までの累積和 """
        sum_ = 0
        pos = 0
        for i in range(self.depth, -1, -1):
            k = pos + (1 << i)
            if k <= self.size and sum_ + self.tree[k] < x:
                sum_ += self.tree[k]
                pos += 1 << i
        return pos + 1, sum_

m=998244353    
N,K=map(int,input().split())
bit = Bit(N)
bit.add(1,1)
period = []
for _ in range(K):
    l,r=map(int,input().split())
    period.append((l,r))
for i in range(2,N+1):
    for l,r in period:
        rx = max(0,i-l)
        lx = max(0,i-r-1)
        if rx==0:
            tmp_r = 0
        else:
            tmp_r = bit.sum(rx)
        if lx == 0:
            tmp_l = 0
        else:
            tmp_l = bit.sum(lx)
        bit.add(i,(tmp_r-tmp_l)%m)
ans = (bit.sum(N)-bit.sum(N-1))%m
print(ans)

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

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

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

for k in range(2, N+1):
    s = 0
    for l,r in LR:
        p0,p1 = max(k-r-1, 0), max(k-l, 0)
        s += S[p1] - S[p0]

    S[k] = (S[k-1] + s)%998244353

print((S[-1] - S[-2])%998244353)

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

a = [0] * (N+1)
f = [0] * (N+1)
mv = list()
for i in range(K):
    mv.append(list(map(int, input().split())))

def solve(N, a, f):
    for i in range(1, N+1):
        f[i] = (f[i-1] + a[i]) % MOD
        for j in range(len(mv)):
            l, r = mv[j]
            if i+l < N+1: a[i+l] = (a[i+l] + f[i]) % MOD
            if i+r+1 < N+1: a[i+r+1] = (a[i+r+1] - f[i]) % MOD

a[1] = 1
mv.sort()
solve(N, a, f)

print(a[N])

Solution (Python):
MOD=998244353
N,K=[int(s) for s in input().split()]
ls=[0 for _ in range(N)]
lssum=[0 for _ in range(N)]
ls[0]=1
lssum[0]=1

sections=[[int(s) for s in input().split()] for _ in range(K)]

for i in range(1,N):
  for sec in sections:
    if sec[0]>i:
      continue
    else:
      l=sec[0]
      r=min([i,sec[1]])
      ls[i]=(ls[i]+lssum[i-l]-lssum[i-r-1])%MOD
  lssum[i]=(lssum[i-1]+ls[i])%MOD
print(ls[N-1])

Solution (Python):
class BIT:
    def __init__(self, n, MOD):
        self.n = n
        self.data = [0] * (n + 1)
        self.MOD = MOD

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

    def add(self, i, x):
        while i <= self.n:
            self.data[i] += x
            self.data[i] %= self.MOD
            i += i & -i

    def diff(self, i, j):
        s = self.sum(j) - self.sum(i)
        s %= self.MOD
        return s


n, k = map(int, input().split())
mod = 998244353
bit = BIT(n + 2, mod)
ranges = []
for _ in range(k):
    l, r = map(int, input().split())
    ranges.append((l, r))

bit.add(1, 1)

for i in range(1, n):
    v = bit.sum(i)
    for l, r in ranges:
        bit.add(i + l, v)
        bit.add(min(n + 1, i + r + 1), -v)
print(bit.diff(n - 1, n))

Solution (Python):
N, K = map(int, input().split())
mod = 998244353
lr = []
for k in range(K):
    lr.append(list(map(int, input().split())))
dp = [0]*(2*N+1)
dp[0] = 1
dpsum = 0
for i in range(N):
    dpsum += dp[i]%mod
    for k in lr:
        l = k[0]
        r = k[1]

        dp[i+l] += dpsum%mod
        dp[i+r+1] -= dpsum%mod
        
print(dp[N-1]%mod)

Solution (Python):
MOD=998244353
N,K=[int(s) for s in input().split()]
ls=[0 for _ in range(N)]
lssum=[0 for _ in range(N)]
ls[0]=1
lssum[0]=1

sections=[[int(s) for s in input().split()] for _ in range(K)]
sections.sort()

for i in range(1,N):
  for sec in sections:
    if sec[0]>i:
      continue
    else:
      l=sec[0]
      r=min([i,sec[1]])
      ls[i]=(ls[i]+lssum[i-l]-lssum[i-r-1])%MOD
  lssum[i]=(lssum[i-1]+ls[i])%MOD
print(ls[N-1])

Solution (Python):
class BIT:
    def __init__(self, n, MOD):
        self.n = n
        self.data = [0] * (n + 1)
        self.MOD = MOD

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

    def add(self, i, x):
        while i <= self.n:
            self.data[i] += x
            self.data[i] %= self.MOD
            i += i & -i


n, k = map(int, input().split())
mod = 998244353
bit = BIT(n + 2, mod)
ranges = []
for _ in range(k):
    l, r = map(int, input().split())
    ranges.append((l, r))

bit.add(1, 1)

for i in range(1, n):
    v = bit.sum(i)
    for l, r in ranges:
        bit.add(i + l, v)
        bit.add(min(n + 1, i + r + 1), -v)
print((bit.sum(n) - bit.sum(n - 1)) % mod)

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

a = [0 for i in range(N+1)]
a[1] = 1
b = [0 for i in range(N+1)]
b[1] = 1
for i in range(2,N+1):
    for j in range(K):
        if l[j][0] < i:
            a[i] += (b[i-l[j][0]]-b[max(0,i-l[j][1]-1)])%mod
        else:
            break
    b[i] = (b[i-1]+a[i])%mod
mod = 998244353
print(a[N]%mod)

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

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

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

dp = [0] * (N + 1)
sdp = [0] * (N + 1)
dp[1] = 1
sdp[1] = 1
  
for i in range(2, len(dp)):
  for j in range(K):
    li = max(i - R[j], 0)
    ri = i - L[j]
    if ri < 0:
      continue
    dp[i] += (sdp[ri] - sdp[li - 1])
    dp[i] %= DIV
  sdp[i] = sdp[i - 1] + dp[i]
  sdp[i] %= DIV
  
print(dp[N])

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

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

for i in range(2, N+1):
    for s in S:
        fr = max(0, i-s[1]-1)
        to = max(0, i-s[0])
        dp[i] += (cumsum_dp[to]-cumsum_dp[fr]) % mod
    cumsum_dp[i] = (cumsum_dp[i-1] + dp[i]) % mod
    
print(dp[N]%mod)