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):
MOD = 998244353
class SegmentTree:
    def __init__(self, a):
        self.padding = 0
        self.n = len(a)
        self.N = 2 ** (self.n-1).bit_length()
        self.seg_data = [self.padding]*(self.N-1) + a + [self.padding]*(self.N-self.n)
        for i in range(2*self.N-2, 0, -2):
            self.seg_data[(i-1)//2] = self.seg_data[i] + self.seg_data[i-1]
    
    def __len__(self):
        return self.n
    
    def update(self, i, x):
        idx = self.N - 1 + i
        self.seg_data[idx] += x
        self.seg_data[idx] %= MOD
        while idx:
            idx = (idx-1) // 2
            self.seg_data[idx] = (self.seg_data[2*idx+1] + self.seg_data[2*idx+2]) % MOD
    
    def query(self, i, j):
        
        if i == j:
            return self.seg_data[self.N - 1 + i] % MOD
        else:
            idx1 = self.N - 1 + i
            idx2 = self.N - 2 + j 
            result = self.padding
            while idx1 < idx2 + 1:
                if idx1&1 == 0: 
                    result = (result + self.seg_data[idx1]) % MOD
                if idx2&1 == 1: 
                    result = (result + self.seg_data[idx2]) % MOD
                    idx2 -= 1
                idx1 //= 2
                idx2 = (idx2 - 1)//2
            return result


N, K = map(int, input().split())
LR = [tuple(map(int, input().split())) for i in range(K)]
a = [0] * (N+1)
a[1] = 1
dp = SegmentTree(a)
for i in range(2, N+1):
    for l, r in LR:
        ll = max(0, i - l)
        rr = max(0, i - r)
        dp.update(i, dp.query(rr, ll+1))

print(dp.query(N, N+1))

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

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

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys

Z = 998244353


def input():
    return sys.stdin.readline().rstrip('\n')


def calc(N, K, LR):
    f = [0] * N
    a = [0] * N
    f[0] = 1
    a[0] = -1
    for i in range(N - 1):
        for (l, r) in LR:
            if i + l - 1 < N:
                a[i + l - 1] = a[i + l - 1] + f[i]
            if i + r < N:
                a[i + r] = a[i + r] - f[i]
        f[i + 1] = (a[i] + f[i]) % Z
    return f[N - 1]


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

Solution (Python):
n, k = map(int, input().split())
cum = [0, 1]
dp = [0, 1]

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

def check(i):
    res = 0
    for l, r in lr:
        if i - l < 1:
            continue
        res += cum[i-l] - cum[max(i-r-1,0)]
        res %= mod
    return res


for i in range(2,n+1):
    dp.append(check(i))
    cum.append((cum[-1]+dp[-1])%mod)

print(dp[-1])

Solution (Python):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 998244353

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))



N,K = LI()
L,R = LIR(K,2)

LR = [(L[i],R[i]) for i in range(K)]
LR.sort(key=lambda x:x[0])

L = [LR[i][0] for i in range(K)]
R = [LR[i][1] for i in range(K)]

S = [0]*K

dp = [0]*N
dp[0] = 1
for i in range(N):
    for k in range(K):
        if i > R[k]:
            S[k] += dp[i-L[k]] - dp[i-R[k]-1]
            S[k] %= mod
        elif i < L[k]:
            S[k] += 0
        else:
            S[k] += dp[i-L[k]]
            S[k] %= mod
        dp[i] += S[k]
        dp[i] %= mod


print(dp[-1])

Solution (Python):
def main():
    Q = 998244353
    N, K = map( int, input().split())
    LR = [ tuple( map( int, input().split())) for _ in range(K)]
    LR.sort()
    dp = [0]*(N+1)
    dp[1] = 1
    S = [0]*K
    for i in range(2,N+1):
        for j, (l, r) in enumerate(LR):
            if l <= i:
                S[j] += dp[i-l]
            if r < i:
                S[j] -= dp[i-r-1]
            S[j] %= Q
        dp[i] += sum(S)
        dp[i] %= Q
    
    print(dp[N])
        
if __name__ == '__main__':
    main()

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

dp = [0]*(N+1)
dp_sum = [0]*(N+1)
dp[1] = dp_sum[1] = 1
for i in range(2,N+1):
    for l,r in move:
        if 0<i-l:
            dp[i] += dp_sum[i-l]
            if 0<i-r-1:
                dp[i] -= dp_sum[i-r-1]
        dp[i] %= mod
    dp_sum[i] = dp_sum[i-1] + dp[i]
            
print(dp[-1]%mod)

Solution (Python):

def solve():
    MOD = 998244353
    N, K = map(int, input().split())
    LR_L = [[int(x) for x in input().split()] for y 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]
        dp[i] %= MOD
        
        
        
        for li, ri in LR_L:
            if i + li < N+1:
                dp[i+li] += dp[i]
                dp[i+li] %= MOD
            if i + ri + 1 < N+1:
                dp[i+ri+1] -= dp[i]
                dp[i+ri+1] %= MOD
    print(dp[N])


solve()

Solution (Python):
from itertools import accumulate
n,k = map(int,input().split())
mod = 998244353

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

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

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

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

D = [1]
M = 100
memo = []
memo2 = []
for i in range(1, N):
  count = 0
  for l, r in LR:
    if l <= i:
      l1 = i - min(i, r)
      r1 = i - l + 1
      l2 = (l1 + M - 1) // M
      r2 = r1 // M
      l3 = (l2 + M - 1) // M
      r3 = r2 // M
      if r3 > l3:
        count += sum(D[l1:l2*M]) + sum(memo[l2:l3*M]) + sum(memo2[l3:r3]) + sum(memo[r3*M:r2]) + sum(D[r2*M:r1])
      elif r2 > l2:
        count += sum(D[l1:l2*M]) + sum(memo[l2:r2]) + sum(D[r2*M:r1])
      else:
        count += sum(D[l1:r1])
  D.append(count % 998244353)
  if len(D) % M == 0:
    memo.append(sum(D[-M:]))
    if len(memo) % M == 0:
      memo2.append(sum(memo[-M:]))
print(D[-1])

Solution (Python):


import sys
input=sys.stdin.readline

mod=998244353

n,k=map(int,input().split())
arr=[list(map(int,input().split()))+[i] for i in range(k)]
dp=[0]*(n+1)
dp[1]=1
sums=[0]*k
for i in range(2,n+1):
  for l,r,j in arr:
    if l>i:
      continue
    elif l<=i<=r:
      sums[j]+=dp[i-l]
    else:
      sums[j]-=dp[i-r-1]
      sums[j]+=dp[i-l]
    sums[j]%=mod
  for j in range(k):
    dp[i]+=sums[j]
print(dp[n]%mod)

Solution (Python):




import sys
from io import StringIO
import unittest





def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline
    mod=998244353
    dp=[0]*(2*(10**5)+10)
    dp[0]=1
    n,k=map(int, readline().rstrip().split())
    
    
    ll=[0]*(2*(10**5)+10)
    rr=[0]*(2*(10**5)+10)
    for i in range(k):
        ll[i],rr[i]=map(int, readline().rstrip().split())
    for i in range(n-1):
        if i > 0:
            dp[i]+=dp[i-1]

        if dp[i] == 0:
            continue

        for j in range(k):
            if i+ll[j] <= n:
                dp[i+ll[j]] += dp[i]
                dp[i+ll[j]]%=mod
            if i+rr[j]+1 <= n:
                dp[i+rr[j]+1] -= dp[i]
                dp[i+rr[j]+1]%=mod
    print(dp[n-1])
    
    
    
    
    

    
    
    
    

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

Solution (Python):
mod = 998244353
n,k = map(int,input().split())
s = [list(map(int,input().split())) for i in range(k)]
c = [0]*(n+1)
c[0] = 1
for i in range(n):
    for j,k in s:
        if i+j<n+1:
            c[i+j] += c[i]
        if i+k<n:
            c[i+k+1] -= c[i]
    if i>0:
        c[i+1] += c[i] 
        c[i+1] %= mod

print(c[n-1])

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

s=[0 for _ in range(N+1)]
s[1]=1
for i in range(1,N):
  s[i+1] = s[i]
  for l,r in LR:
    s[i+1]+=(s[max(0,i-l+1)]-s[max(0,i-r)])%P
    s[i+1]%=P
print((s[N]-s[N-1])%P)

Solution (Python):
class BIT:
    def __init__(self,len_A, mod):
        self.N = len_A + 10
        self.bit = [0]*(len_A+10)
        self.mod = mod
        
    def query(self,i):
        res = 0
        idx = i+1
        while idx:
            res += self.bit[idx]
            idx -= idx&(-idx)
        return res

    def update(self,i,x):
        idx = i+1
        while idx < self.N:
            self.bit[idx] += x
            self.bit[idx] %= self.mod
            idx += idx&(-idx)

n, k = map(int, input().split())
mod = 998244353
bit = BIT(n,mod)
dp = [0]*(n+3)
lr = []
for i in range(k):
    l, r = map(int, input().split())
    lr.append((l, r))
    if l != r:
        for g in range(l, r+1):
            dp[g] = 1
            bit.update(g, 1)
    else:
        dp[l] = 1
        bit.update(l, 1)
lr.sort()

for i in range(1, n+1):
    ssum = 0
    for g in range(k):
        if i > lr[g][1]:
            ssum += bit.query(i-lr[g][0]) - bit.query(i-lr[g][1]-1)
        else:
            if lr[g][0] < i:
                ssum += bit.query(i-lr[g][0]) 
            break
    dp[i] += ssum
    dp[i] %= mod
    bit.update(i, ssum)
print(dp[n-1])

Solution (Python):


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



ide_ele = 0




class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

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

mod=998244353
n,k=map(int,input().split())
Q=[]
for _ in range(k):
    a,b=map(int,input().split())
    Q.append((a,b))

dp=[0 for i in range(n+1)]
dp[1]=1
dp=SegTree(dp,segfunc,ide_ele)
for i in range(2,n+1):
    cnt=0
    for que in Q:
        cnt+=dp.query(max(0,i-que[1]),max(0,i-que[0]+1))%mod
        
        cnt%=mod
    dp.update(i,cnt)
print(dp.query(n,n+1))

Solution (Python):
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())


N,K = MI()
LR = [tuple(MI()) for i in range(K)]
mod = 998244353

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

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

N, K = map(int, input().split())
seg = [tuple(map(int, input().split())) for _ in range(K)]
dp = [0] * (N+1)
dp[0] = 1
for i in range(N):
    for s, t in seg:
        if (i+s) <= N:dp[i+s] += dp[i]
        if (i+t+1) <= N:dp[i+t+1] -= dp[i]
    dp[0] = 0
    dp[i+1] += dp[i]
    dp[i+1] %= MOD
    
print(dp[N-1])

Solution (Python):
import sys
import math


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


def main():
    N, K = map(int, input().split())
    L = [[] for _ in range(K)]
    for t in range(K):
        l, r = map(int, input().split())
        for j in range(l, r + 1):
            L[t].append(j)

    lc = [0] * K
    mod = 998244353

    dp = [0] * (N + 1)
    dp[0] = 1
    for i in range(1, N + 1):

        for k in range(K):
            CL = L[k]
            if len(CL) == 1:
                lc[k] = dp[i - CL[0]] % mod
            else:
                if CL[-1] > i:
                    lc[k] = lc[k] % mod + dp[i - L[k][0]] % mod
                else:
                    lc[k] = (lc[k] + dp[i - L[k][0]] - dp[i - L[k][-1] - 1]) % mod
            dp[i] = lc[k] + dp[i] % mod

    print(dp[N - 1] % mod)


if __name__ == "__main__":
    main()

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

    LL.append(L)
    RR.append(R + 1)


keep = 0
dp = [0] * 2 * N
dp[N] = 1
for i in range(1, N):
    for j in range(K):

        keep = (keep + dp[N + i - LL[j]] - dp[N + i - RR[j]]) % mod 

    dp[N + i] = (dp[N + i] + keep) % mod
print(dp[2 * N - 1] % mod)

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

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

mod = 998244353

for i in range(2, n+1):
    for l, r in lr:
        left, right = i - r, i - l
        if left > 0:
            dp[i] += dp_cum[right] - dp_cum[left - 1]
        elif right > 0:
            dp[i] += dp_cum[right]
    
    dp[i] %= mod
    dp_cum[i] = dp[i] + dp_cum[i-1]
    dp_cum[i] %= mod

print(dp[n])

Solution (Python):
MOD = 998244353



def dp_range(l, r):
    left = 0 if l-1 < 0 else dp_acc[l-1]
    right = 0 if r < 0 else dp_acc[r]
    return right - left

N, K = map(int, input().split())
segments = [tuple(map(int, input().split())) for _ in range(K)]
dp = [0] * (2 * N + 1)
dp_acc = [0] * (2 * N + 1)

dp[0], dp_acc[0] = 1, 1


for i in range(N):
    for j in range(K):
        dp[i] += dp_range(i - segments[j][1], i - segments[j][0])
        dp[i] %= MOD
        dp_acc[i] = (dp_acc[i - 1] + dp[i]) % MOD
print(dp[N-1])

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from sys import exit

import sys
sys.setrecursionlimit(1000000000)
mod = 998244353





N, K = getNM()
que = [getList() for i 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]
    dp[i] %= mod
    for l, r in que:
        if i + l <= N:
            dp[i + l] += dp[i]
        if i + r + 1 <= N:
            dp[i + r + 1] -= dp[i]
print(dp[N] % mod)

Solution (Python):
import sys
import math


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


def main():
    N, K = map(int, input().split())
    L = [[] for _ in range(K)]
    for t in range(K):
        l, r = map(int, input().split())
        for j in range(l, r + 1):
            L[t].append(j)

    lc = [0] * K
    mod = 998244353

    dp = [0] * (N + 1)
    dp[0] = 1
    for i in range(1,N+1):

        for k in range(K):
            CL =L[k]
            if len(CL)==1:
                lc[k]=dp[i-CL[0]] %mod
            else:
                if CL[-1] > i:
                    lc[k] = lc[k] %mod +dp[i-L[k][0]] %mod
                else:
                    lc[k] =( lc[k] + dp[i - L[k][0]] - dp[i - L[k][-1]-1] )%mod
            dp[i] += lc[k]



    print(dp[N - 1]%mod)


if __name__ == "__main__":
    main()

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

dp = [0]*(n+1)
dp[0] = 1
dp2 = [0]*(n+1)
for i in range(n):
    dp2[i] = (dp2[i]+dp2[i-1])%mod
    dp[i] = (dp[i]+dp2[i])%mod
    for l,r in K:
        dp2[min(i+l,n)] = (dp2[min(i+l,n)]+dp[i])%mod
        dp2[min(i+r+1,n)] = (dp2[min(i+r+1,n)]-dp[i])%mod
print(dp[n-1]%mod)

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

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


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

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

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

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

ide_ele=0 


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

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

Solution (Python):

import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys
sys.setrecursionlimit(10**6)

readline = sys.stdin.readline

INF = 1 << 60


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


class SegmentTree:
    def __init__(self, array, operator, identity_element):
        _len = len(array)
        self.__len = _len
        self.__op = operator
        self.__size = 1 << (_len - 1).bit_length()
        self.__tree = [identity_element] * self.__size + \
            array + [identity_element] * (self.__size - _len)
        self.__ie = identity_element

        for i in range(self.__size - 1, 0, -1):
            self.__tree[i] = operator(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def update(self, i, v):
        i += self.__size
        self.__tree[i] = v
        while i:
            i //= 2
            self.__tree[i] = self.__op(
                self.__tree[i * 2], self.__tree[i * 2 + 1])
        

    def query(self, l, r):
        """[l, r)
        """
        l += self.__size
        r += self.__size
        ret = self.__ie
        while l < r:
            if l & 1:
                ret = self.__op(ret, self.__tree[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.__op(ret, self.__tree[r])
            l //= 2
            r //= 2
        return ret

    def max_right(self, l, f):
        
        assert 0 <= l <= self.__len
        if l == self.__len:
            return self.__len

        l += self.__size
        sm = self.__ie
        while True:
            while l % 2 == 0:
                l >>= 1
            if not f(self.__op(sm, self.__tree[l])):
                while l < self.__size:
                    l = 2*l
                    if f(self.__op(sm, self.__tree[l])):
                        sm = self.__op(sm, self.__tree[l])
                        l += 1
                return l - self.__size
            sm = self.__op(sm, self.__tree[l])
            l += 1

            if (l & -l) == l:
                break

        return self.__len

    def min_left(self, r, f):
        assert 0 <= r <= self.__len
        if r == 0:
            return 0

        r += self.__size
        sm = self.__ie
        while True:
            r -= 1
            while r > 1 and (r % 2):
                r >>= 1
            if not f(self.__op(sm, self.__tree[r])):
                while r < self.__size:
                    r = 2*r + 1
                    if f(self.__op(sm, self.__tree[r])):
                        sm = self.__op(sm, self.__tree[r])
                        r -= 1
                return r + 1 - self.__size
            sm = self.__op(sm, self.__tree[r])

            if (r & -r) == r:
                break

        return 0

    def __getitem__(self, key):
        return self.__tree[key + self.__size]



@mt
def slv(N, K, LR):
    M = 998244353
    memo = SegmentTree([0] * (N+1), add, 0)
    memo.update(1, 1)
    for i in range(2, N+1):
        v = 0
        for l, r in LR:
            v += memo.query(max(0, i-r), max(0, i-l+1))
            v %= M
        memo.update(i, v)

    return memo[N]


def main():
    N, K = read_int_n()
    LR = [read_int_n() for _ in range(K)]
    print(slv(N, K, LR))


if __name__ == '__main__':
    main()

Solution (Python):
import sys
INF = 1 << 60
MOD = 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()

class SegmentTree(object):
    def __init__(self, A, dot, unit):
        n = 1 << (len(A) - 1).bit_length()
        tree = [unit] * (2 * n)
        for i, v in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
        self._n = n
        self._tree = tree
        self._dot = dot
        self._unit = unit

    def __getitem__(self, i):
        return self._tree[i + self._n]

    def update(self, i, v):
        i += self._n
        self._tree[i] = v
        while i != 1:
            i >>= 1
            self._tree[i] = self._dot(self._tree[i << 1], self._tree[i << 1 | 1])

    def add(self, i, v):
        self.update(i, self[i] + v)

    def sum(self, l, r):
        l += self._n
        r += self._n
        l_val = r_val = self._unit
        while l < r:
            if l & 1:
                l_val = self._dot(l_val, self._tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_val = self._dot(self._tree[r], r_val)
            l >>= 1
            r >>= 1
        return self._dot(l_val, r_val)

def resolve():
    n, k = map(int, input().split())
    D = [tuple(map(int, input().split())) for _ in range(k)]
    tree = SegmentTree([0] * n, lambda x, y : (x + y) % MOD, 0)
    tree.update(0, 1)

    for i in range(1, n):
        for l, r in D: 
            if i - l >= 0:
                tree.add(i, tree.sum(max(0, i - r), i - l + 1))

    print(tree[n - 1] % MOD)
resolve()

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

resolve()

Solution (Python):
MOD = 998244353
n, k = map(int, input().split())
seg = [list(map(int, input().split())) for _ in range(k)]
dp = [0 for _ in range(n+1)]
dp[1] = 1
cum = [0 for _ in range(n+1)]
cum[1] = 1
for i in range(2, n+1):
	for l, r in seg:
		r, l = max(i-l, 0), max(i-r-1, 0)
		dp[i] += cum[r] - cum[l]
		dp[i] %= MOD
	cum[i] = cum[i-1] + dp[i]
	cum[i] %= MOD
print(dp[n])

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

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

n,k = readInts()
lr = [readInts() for i in range(k)]

dp = [-1]*(n+2)
dp[n]=1
dp[n+1]=0
i=n
ruiseki = [0]*(k)
for j in range(k):
	ruiseki[j] = dp[min(i+lr[j][0],n+1)]-dp[min(i+lr[j][1],n+1)]

ans = 0
for i in range(n-1,0,-1):
	t = 0
	for j in range(k):
		ll = dp[min(i+lr[j][0],n+1)]
		rr = dp[min(i+lr[j][1]+1,n+1)]
		
		ruiseki[j] += ll-rr
	t+=sum(ruiseki)
	dp[i]=t%998244353
	

print(dp[1])

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

S = [ tuple( map(int, input().split()) ) for i in range(K)]


Ans = [0 for i in range(N)]
Ans[0] = 1
a = [0 for i in range(N)]
a[1] = -1
for i in range(1, N):
  for s in S:
    if i-1 + s[0] <= N-1:
      a[i-1 + s[0]] += Ans[i-1]
      a[i-1 + s[0]] %= 998244353
    if i + s[1] <= N-1:
      a[i + s[1]] -= Ans[i-1]
      a[i + s[1]] %= 998244353
  Ans[i] = (Ans[i-1] + a[i]) % 998244353
  
  

print(Ans[N-1])

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

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



def BIT_query(idx):
  res_sum = 0
  while idx > 0:
    res_sum += BIT[idx]
    idx -= idx&(-idx)
  return res_sum

def BIT_update(idx,x):
  while idx <= N:
    BIT[idx] += x
    idx += idx&(-idx)
  return  


BIT=[0]*(N+1)
BIT_update(1,1)

for i in range(2,N+1):
  for l,r in lrlist:
    left=i-r
    right=i-l    
    if right<1:
      continue
    elif left<1:
      left=1
    
    sum_intv=BIT_query(right)-BIT_query(left-1)
    BIT_update(i,sum_intv)
    
  nomod=BIT_query(i)-BIT_query(i-1)
  BIT_update(i,nomod%MOD-nomod)
    
print(BIT_query(N)-BIT_query(N-1))

Solution (Python):
import sys;input=sys.stdin.readline
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

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

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

N, K = map(int, input().split())
mod=998244353
X = []
rs = []
for _ in range(K):
    l, r = map(int, input().split())
    rs.append((l, r))
st = Bit(N)
st.add(1, 1)
for i in range(2, N+1):
    t = 0
    for l, r in rs:
        if i-l<1:
            continue
        t += st.sum(i-l) - st.sum(max(i-r-1, 0))
        t%=mod
    st.add(i, t)
print((st.sum(N)-st.sum(N-1))%mod)

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

region = []
mod = 998244353

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

cnt = [0] * (n + 1)
cnt[0] = 0
imos = [0] * (n + 1)
imos[0] = 1

for i in range(n):

    if i - 1 >= 0:
        cnt[i] = cnt[i - 1] + imos[i]
        cnt[i] %= mod
    for l, r in region:
        if i + l < n:
            imos[i + l] += cnt[i] if i != 0 else 1
            imos[i + l] %= mod

        if i + r + 1 < n:
            imos[i + r + 1] -= cnt[i] if i != 0 else 1
            imos[i + l + 1] %= mod

print(cnt[n - 1] % mod)