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):
class segtree:
  
  def __init__(s, v, op, e):
    s._n = len(v)
    s.log = s.ceil_pow2(s._n)
    s.size = 1 << s.log
    s.d = [e()] * (2 * s.size)
    s.e = e
    s.op = op
    for i in range(s._n): s.d[s.size + i] = v[i]
    for i in range(s.size - 1, 0, -1): s.update(i)
  
  
  def set(s, p, x):
    p += s.size
    s.d[p] = x
    for i in range(1, s.log + 1): s.update(p >> i)
 
  
  def get(s, p):
    return s.d[p + s.size]
 
  
  def prod(s, l, r):
    sml, smr = s.e(), s.e()
    l += s.size
    r += s.size
    while (l < r):
      if l & 1: 
        sml = s.op(sml, s.d[l])
        l += 1
      if r & 1:
        r -= 1
        smr = s.op(s.d[r], smr)
      l >>= 1
      r >>= 1
    return s.op(sml, smr)
 
  
  def all_prod(s): return s.d[1]
 
  def update(s, k): s.d[k] = s.op(s.d[2 * k], s.d[2 * k + 1])
  def ceil_pow2(s, n):
    x = 0
    while (1 << x) < n: x += 1
    return x


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

def e():
  return 0
def op(a, b):
  return (a + b) % MOD

seg = segtree([0] * N, op, e)
seg.set(0, 1)

for i in range(1, N):
  ans = 0
  for l, r in LR:
    r, l = max(0, i - l + 1), max(0, i - r)
    ans = (ans + seg.prod(l, r)) % MOD
  seg.set(i, ans)

print(seg.get(N - 1))

Solution (Python):
M=998244353
class BIT:
    def __init__(self,n):
        self.size=n
        self.tree=[0]*-~n
    def sum(self,i):
        s=0
        while i:
            s=(s+self.tree[i])%M
            i-=i&-i
        return s
    def add(self,i,x):
        while i<=self.size:
            self.tree[i]=(self.tree[i]+x)%M
            i+=i&-i
(n,k),*s=[[*map(int,t.split())]for t in open(0)]
bit=BIT(n+5)
bit.add(1,1)
bit.add(2,-1)
for i in range(1,n):
    p=bit.sum(i)
    for l,r in s:
        l+=i
        r+=i
        if l>n:l=n+1
        if r>n:r=n+1
        bit.add(l,p)
        bit.add(r+1,-p)
print(bit.sum(n))

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

Solution (Python):
n, k = map(int, input().split())
mod = 998244353
x = [list(map(int, input().split())) for _ in range(k)]
x.sort()
dp = [0] * (n + 1)
dpsum = [0] * (n + 1)
dp[1], dpsum[1] = 1, 1
for i in range(2, n + 1):
    cnt = 0
    for j in range(k):
        cnt += (dpsum[max(0, i - x[j][0])] - dpsum[max(0, i - x[j][1] - 1)])
        cnt %= mod
        if i - x[j][1] < 0:
            break
    dp[i] = cnt
    dpsum[i] = dp[i] + dpsum[i - 1]
ans = dp[n]
print(ans)

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

mod = 998244353

S = [0, 1]

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

print(a)

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
for i in range(n):
  if i>1:
    dp[i]+=dp[i-1]
    dp[i]%=mod
  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[-1]%mod)

Solution (Python):
mod = 998244353
n,k = map(int,input().split())
c = [0 for _ in range(n+1)]
cs = [0 for _ in range(n+1)]
c[1] = 1
cs[1] = 1
csi = 1
lr = [(0,0) for _ in range(k)]
for i in range(k):
  li,ri = map(int,input().split())
  lr[i] = (li,ri)
for i in range(2,n+1):
  for lri in lr:
    l,r = lri
    if i-l > 0:
      c[i] = (c[i]+cs[i-l]-cs[max(0,i-r-1)])%mod
  csi = (c[i]+csi)%mod
  cs[i] = csi
print(c[n])

Solution (Python):
import sys
sys.setrecursionlimit(10**7) 
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque, defaultdict


from collections import Counter

from itertools import accumulate,combinations,permutations,product

from heapq import heapify,heappop,heappush

from functools import reduce,lru_cache

from decimal import Decimal
from argparse import ArgumentParser

args=ArgumentParser()
args.add_argument('-loc', '--local', type=bool,default=False)
LOCAL=args.parse_args().local

def input(): 
    x=sys.stdin.readline(); 
    if x[-1]=="\n": 
        return x.rstrip() 
    return x
    
def printe(*x):_=print("
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): 
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

def main():
    mod = 998244353
 
    

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

    dp=[0]*N
    dp[0]=1
    acc=[0]*N
    tacc=0
    for i in range(N):
        if i!=0:
            tacc=(tacc+acc[i])%mod
            dp[i]=tacc
        for l,r in S:
            if i+l<N:
                acc[i+l]+=dp[i]
                acc[i+l]%=mod
            if i+r+1<N:
                acc[i+r+1]-=dp[i]
                acc[i+r+1]%=mod
        
    print(dp[-1])

if __name__ == "__main__":
    main()

Solution (Python):
N,K=map(int,input().split())
I=[0]*K
for m in range(K):
    l,r=map(int,input().split())
    I[m]=(l,r)

Mod=998244353

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

for x in range(2,N+1):
    DP[x]=DP[x-1]
    for (l,r) in I:
        a=max(0,x-r-1)
        b=max(0,x-l)
        DP[x]+=DP[b]-DP[a]
        DP[x]%=Mod
print((DP[N]-DP[N-1])%Mod)

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

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

    dp = [0]*(n)

    zone = [tuple(map(int, input().split())) for i in range(k)]
    zone.sort()

    dp[0] = 1
    count = 0
    bit = [0]*k

    for i in range(1, n):
        for j in range(k):
            l, r = zone[j]
            if i-l >= 0:
                bit[j] += dp[i-l]
            if i-r-1 >= 0:
                bit[j] -= dp[i-r-1]
        dp[i] += sum(bit)%mod
        dp[i] %= mod
    ans = dp[n-1]
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
N,K = map(int,input().split())
LR = []
mod = 998244353
for i in range(K):
    L,R = map(int,input().split())
    LR.append((L,R))
dp = [0]*(3*N)
for L,R in LR:
    dp[L] += 1
    dp[L] %= mod
    dp[R+1] -= 1
    dp[R+1] %= mod
for i in range(1,N-1):
    for L,R in LR:
        dp[i+L] += dp[i]
        dp[i+L] %= mod
        dp[i+R+1] -= dp[i]
        dp[i+R+1] %= mod
    dp[i+1] += dp[i]
    dp[i+1] %= mod
print(dp[N-1])

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=998244353
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

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

class RangeBIT:
    def __init__(self,n):
        self.p=self.BIT(n+1)
        self.q=self.BIT(n+1)
    
    def add(self,s,t,x):
        self.p.add(s,-x*s)
        self.p.add(t,x*t)
        self.q.add(s,x)
        self.q.add(t,-x)
    
    def sum(self,s,t):
        return self.p.sum(t)+self.q.sum(t)*t-self.p.sum(s)-self.q.sum(s)*s
    
    class BIT:
        def __init__(self,n):
            self.num=n
            self.dat=[0]*(self.num+1)
        
        def add(self,i,x):
            i+=1
            while i<=self.num:
                self.dat[i]+=x
                i+=i&-i
        
        def sum(self,i):
            i+=1
            s=0
            while i>0:
                s+=self.dat[i]
                i-=i&-i
            return s

b=RangeBIT(N)
b.add(0,1,1)
for i in range(N):
    res=b.sum(i,i+1)%MOD
    for l,r in zip(L,R):
        if i+l<N:
            b.add(i+l,min(i+r,N),res)
print(b.sum(N-1,N)%MOD)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from math import gcd
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().rstrip().split()
def S(): return sys.stdin.readline().rstrip()
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)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]




class BIT:
    def __init__(self, size):
        self.bit = [0] * size
        self.size = size
        self.total = 0

    def add(self, i, w):
        x = i + 1
        self.total += w
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        return

    def sum(self, i):
        res = 0
        x = i + 1
        while x:
            res += self.bit[x - 1]
            x -= x & -x
        return res

    def interval_sum(self, i, j): 
        return self.sum(j - 1) - self.sum(i - 1) if i else self.sum(j - 1)


mod=998244353
n,k=LI()
lr=LIR(k)
bit=BIT(n+1)
bit.add(0,1)
for i in range(n):
    ret=0
    for j in range(k):
        l,r=lr[j]
        if i-l+1>0:
            ret+=bit.interval_sum(max(i-r,0),i-l+1)
    bit.add(i,ret%mod)
    ans=ret%mod

print(ans)

Solution (Python):


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

D = []

for i in range(K):
    l,r = list(map(int,input().split()))
    D.append((l,"l"))
    D.append((r,"r"))

D.sort(key=lambda x:x[0])
mod = 998244353

DP = [0]*N

DP[0] = 1
DPP = [0]*(N+1)
DPP[1] = 1

def max(a,b):
    if a>b:
        return a
    else:
        return b

def S(x,y):
    return DPP[max(y,0)] - DPP[max(x-1,0)]


for i in range(N-1):
    a = 0
    for j in range(len(D)//2):
        a += S(i+2 - D[2*j+1][0], i+2 - D[2*j][0])
        a %= mod
    DP[i+1] = a
    DPP[i+2] = (a + DPP[i+1])%mod

print(DP[-1])

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

class BIT:
    
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
    
    
    def add(self, i, x):
        i += 1
        
        while i<=self.n:
            self.bit[i] = (x+self.bit[i])%MOD
            i += i&(-i)

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

N, K = map(int, input().split())
LR = [tuple(map(int, input().split())) for _ in range(K)]
MOD = 998244353
bit = BIT(N)
bit.add(0, 1)
bit.add(1, -1)

for i in range(N):
    now = bit.acc(i+1)
    
    
    for L, R in LR:
        if i+L<N:
            bit.add(i+L, now)
        
        if i+R<N:
            bit.add(i+R+1, -now)

print(bit.acc(N))

Solution (Python):

def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)


import sys
import numpy as np

mod = 998244353
def solve(N, K, LR):
    dp = np.zeros(N+1, dtype=np.int64)
    cum = np.zeros(N+1, dtype=np.int64)
    dp[1] = 1
    cum[1] = 1
    for i in range(2, N+1):
        d = 0
        for idx_LR in range(K):
            l, r = LR[idx_LR]
            ll = max(0, i - l)
            rr = max(0, i - r - 1)
            d += cum[ll] - cum[rr]
        d %= mod
        dp[i] = d
        cum[i] = (cum[i-1] + d) % mod
    return dp[N]

numba_compile([
    [solve, "i8(i8,i8,i8[:,:])"],
])

def main():
    N, K = map(int, sys.stdin.buffer.readline().split())
    LR = np.array(sys.stdin.buffer.read().split(), dtype=np.int64).reshape(K, 2)
    ans = solve(N, K, LR)
    print(ans)

main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 998244353


class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0] * (n + 1)
        self.step = pow(2, n.bit_length() - 1)

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

    def get_sum(self, i):
        i += 1
        x = 0
        while i > 0:
            x += self.data[i]
            i -= i & -i
        return x

    
    def get_sum_range(self, l, r):
        return self.get_sum(r - 1) - self.get_sum(l - 1)


def main():
    N, K, *LR = map(int, read().split())

    interval = [(l, r) for l, r in zip(*[iter(LR)] * 2)]

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

    for i in range(N):
        cur = bit.get_sum(i) % MOD
        for l, r in interval:
            bit.add(i + l, cur)
            bit.add(i + r + 1, -cur)

    print(bit.get_sum(N) % MOD)
    return


if __name__ == '__main__':
    main()

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

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

ruiseki=[0]*n
ruiseki[0]=1

for i in range(1,n):
    ruiseki[i]=ruiseki[i-1]
    for j in range(k):
        if(i<idou[j][0]):
            continue
        hiku=0
        if(i>idou[j][1]):
            hiku=ruiseki[i-idou[j][1]-1]
        
        ruiseki[i]+=(p+ruiseki[i-idou[j][0]]-hiku)%p
        ruiseki[i]%=p



print((p+ruiseki[-1]-ruiseki[-2])%p)

Solution (Python):
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  
def LS2(): return list(sys.stdin.readline().rstrip())  


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]
        if i-l > 0:
            dp[i] += dp[i-l]-dp[max(i-r-1,0)]
            dp[i] %= mod

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

Solution (Python):


import os,sys
from io import BytesIO, IOBase

def main():
    mod = 998244353
    n,k = map(int,input().split())
    su = [0,1]
    dp = [0]+[1]+[0]*(n-1)
    ra = []
    for _ in range(k):
        ra.append(tuple(map(int,input().split())))
    for i in range(2,n+1):
        for y in ra:
            if y[0]>i:
                continue
            aa,bb = i-y[0],max(i-y[1],1)
            dp[i] += (su[aa]-su[bb-1])%mod
            dp[i] %= mod
        su.append((su[-1]+dp[i])%mod)
    print(dp[-1])


    

BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

if __name__ == '__main__':
    main()

Solution (Python):
l=input().split()
n=int(l[0])
k=int(l[1])
tot=[]
for i in range(k):
    l=input().split()
    li=[int(i) for i in l]
    tot.append(li)
dp=[0 for i in range(n)]
pref=[1]
dp[0]=1
sumi=1
for i in range(1,n):
    for j in range(k):
        r=tot[j][1]
        l=tot[j][0]
        if(i-l>=0):
            dp[i]+=pref[i-l]
        if(i-r-1>=0):
            dp[i]-=pref[i-r-1]
    dp[i]%=998244353
    sumi+=dp[i]
    sumi%=998244353
    pref.append(sumi)


print(dp[-1])

Solution (Python):
mod = 998244353
n,k = map(int,input().split())
c = [0 for _ in range(n+1)]
cs = [0 for _ in range(n+1)]
c[1] = 1
cs[1] = 1
csi = 1
lr = [(0,0) for _ in range(k)]
for i in range(k):
  li,ri = map(int,input().split())
  lr[i] = (li,ri)
for i in range(2,n+1):
  for lri in lr:
    l,r = lri
    if i-l > 0:
      c[i] = (c[i]+cs[i-l]-cs[max(0,i-r-1)])%mod
  csi = (c[i]+csi)%mod
  cs[i] = csi
print(c[n])

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 998244353
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]



def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


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


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





N,K = IL()
data = ILL(K)
data.sort()

class SegmentTree:
  def __init__(self, n, e):
    self.n = n
    self.e = e
    self.size = 2 ** ((n - 1).bit_length())
    self.node = [self.e] * (2 * self.size)
 
  def build(self, array):
    for i in range(self.n):
      self.node[self.size + i] = array[i]
 
  def get(self, i):
    i += self.size
    ret = self.node[i]
    while i > 1:
      i >>= 1
      ret += self.node[i]
    return ret
 
  def add(self, l, r, val):
    l, r = l + self.size, r + self.size
    while l < r:
      if l & 1:
        self.node[l] += val
        self.node[l] %= MOD
        l += 1
      if r & 1:
        r -= 1
        self.node[r] += val
        self.node[r] %= MOD
      l, r = l >> 1, r >> 1
      
ST = SegmentTree(N+10,0)
ST.add(1,2,1)

for i in range(1,N):
  for k in range(K):
    l,r = data[k]
    if i+l <= N:
      ST.add(i+l,min(i+r+1,N+1),ST.get(i))

print(ST.get(N)%MOD)

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):
import sys
import re
import random
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter



input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)


def solve():
    MOD = 998244353
    n, k = getList()
    imos = [0] * (n + 10)
    imos[2] = -1
    kukan = [getList() for i in range(k)]

    ans = 1
    for i in range(1, n+1):
        ans += imos[i]
        for l, r in kukan:
            l, r = min(i+l, n+2), min(i+r, n+2)
            imos[l] += ans
            imos[r+1] -= ans
        ans %= MOD
    
    print(ans % MOD)


def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    
    solve()

Solution (Python):
MOD = 998244353
N, K = map(int, input().split())
LRs = []
sums = []
for _ in range(K):
    l, r = map(int, input().split())
    LRs.append([l, r])
    sums.append(1 if l <= 1 <= r else 0)

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

for i in range(2, N+1):
    dp[i] = sum(sums) % MOD
    for k in range(K):
        l, r = LRs[k]
        sums[k] = (sums[k] + dp[i-l+1] - dp[i-r]) % MOD
print(dp[N])

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

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

imos = [0 for _ in range(n)]
imos[0] = 1
imos[1] = -1
now = 0
mod = 998244353
for i in range(n):
    now += imos[i]
    now %= mod
    
    for j in range(k):
        try:
            imos[i+lr[j][0]] += now
            imos[i+lr[j][0]] %= mod
        except:
            pass
        try:
            imos[i+lr[j][1]+1] -= now
            imos[i+lr[j][1]+1] %= mod
        except:
            pass
    
print(now)

Solution (Python):
n,k=[int(i) for i in raw_input().split()]
l=[[int(i) for i in raw_input().split()]for j in range(k)]
dp=[0 for i in range(n+1)]
dp[1]=1
dp1=[0 for i in range(n+1)]
dp1[1]=1
m=998244353
for i in range(2,n+1):
    dp1[i]=dp1[i-1]
    for j in l:
        if(i-j[1]>0):
            dp[i]+=dp1[i-j[0]]-dp1[i-j[1]-1]
        else:
            dp[i]+=dp1[i-j[0]]
    dp1[i]+=dp[i]
    dp1[i]%=m
    dp[i]%=m
print dp[n]%m

Solution (Python):
def main():
    examD()

def examA():
    S = SI()
    if S[-1]=="s":
        ans = S+"es"
    else:
        ans = S+"s"
    print(ans)
    return

def examB():
    N = I()
    D = [LI()for _ in range(N)]
    current = 0
    for d1,d2 in D:
        if d1==d2:
            current += 1
        else:
            current = 0
        if current==3:
            print("Yes")
            return
    print("No")
    return

def examC():
    N = I()
    cnt = 0
    for i in range(1,N):
        for j in range(1,1+N//i-(N%i==0)):
            cnt += 1
    ans = cnt
    print(ans)
    return

def examD():
    N, K = LI()
    LR = [LI()for _ in range(K)]
    dp = [0]*N
    S = [0]*N
    dp[0] = 1
    S[0] = 1
    for i in range(1,N):
        cur = 0
        for l,r in LR:
            if i<l:
                continue
            cur += S[i-l]
            if i<r+1:
                continue
            cur -= S[i-r-1]
            cur += mod2
            cur %= mod2

        dp[i] = cur
        S[i] = S[i-1] + cur
        S[i] %= mod2

    ans = dp[-1]
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,alphabet_convert,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 1<<31
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    main()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

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

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

step = [0 for _ in range(N)]
step[0] = 1
step[1] = -1
answer = 0

for i in range(N):
  answer = (answer+step[i])%mod
  for L,R in LR:
    if i+L < N:
      step[i+L] += answer
    if i+R+1 < N:
      step[i+R+1] -= answer

print((answer)%mod)

Solution (Python):
MOD = 998244353
max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y

N,K = map(int,input().split())
f = lambda x: (int(x[0]),int(x[1])+1)
lr = [f(input().split()) for _ in range(K)]

dp = [0]*(N+1)

dp[1] = 1

for i in range(2,N+1):
    t = 0
    for l,r in lr:
        if l > i:
            continue
        a = i - l
        b = max2(0, i - r)
        t += dp[a] - dp[b]
    dp[i] = (dp[i-1]+t)%MOD
print((dp[-1]-dp[-2])%MOD)