CodeEff/ECCO huggingface dataset:
# Original solution
root=[]
n,k = list(map(int,input().split()))
for i in range(k):
    x,y = list(map(int,input().split()))
    root.append([x,y])

toori=[0]*(2*10**5)+[0]*n+[0]*(2*10**5)
toori[2*10**5]=1
cum=[0]*k
for a,i in enumerate (root):
    s=0
    for j in range (i[0],i[1]+1):
        s+=toori[2*10**5+1-j]
    cum[a]=s
aaa=sum(cum)
toori[2*10**5+1]+=aaa


for now in range(2,n):#nowが今の場所
    hueru=0
    for a,i in enumerate (root):
        hueru+=(toori[2*10**5+now-i[0]] - toori[2*10**5+now-1-i[1]])
    aaa+=hueru
    toori[2*10**5+now]+=aaa
    toori[2*10**5+n-1]%=998244353
    


print((toori[2*10**5+n-1]%998244353))


# Optimized solution
root=[]
n,k = list(map(int,input().split()))
for i in range(k):
    x,y = list(map(int,input().split()))
    root.append([x,y])

toori=[0]*(2*10**5)+[0]*n+[0]*(2*10**5)
toori[2*10**5]=1
cum=[0]*k
for a,i in enumerate (root):
    s=0
    for j in range (i[0],i[1]+1):
        s+=toori[2*10**5+1-j]
    cum[a]=s
aaa=sum(cum)%998244353
toori[2*10**5+1]+=aaa


for now in range(2,n):#nowが今の場所
    hueru=0
    for a,i in enumerate (root):
        hueru+=(toori[2*10**5+now-i[0]] - toori[2*10**5+now-1-i[1]])
    aaa+=hueru
    aaa%=998244353
    toori[2*10**5+now]+=aaa
    toori[2*10**5+now]%=998244353
    


print((toori[2*10**5+n-1]%998244353))
# Original solution
def resolve():
    n, k = list(map(int, input().split()))
    S = []
    L, R = [], []
    for _ in range(k):
        l1, r1 = list(map(int, input().split()))
        L.append(l1)
        R.append(r1)

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

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

    print((dp[n] % 998244353))

resolve()

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

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

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

    print((dp[n]))

resolve()
# Original solution
N, K = list(map(int, input().split()))
C = 998244353
S = set()
for _ in range(K):
    l, r = list(map(int, input().split()))
    S |= set(range(l, r+1))
# print(S)

dp = [0]*N
dp[0] = 1
for i in range(N-1):
    if dp[i] == 0:
        continue
    for j in S:
        if i+j < N:
            dp[i+j] = (dp[i+j]+dp[i]) % C
# print(dp)
print((dp[-1] % C))


# Optimized solution
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]
    # print(i,dp)
    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
        # print(i, imos)
dp[N-1] = (imsm[N-2]+imos[N-1]) % C
print((dp[N-1]))
# Original solution
N,K = list(map(int,input().split()))
S = [tuple(map(int,input().split())) for _ in range(K)]
MOD=998244353
dp=[0]*N
dp[0]=1
for i in range(N-1):
    x = dp[i]
    dp[0]=0
    for k in range(K):
        l,r = S[k]
        if i+l < N:
            dp[i+l]+=x
            dp[i+l]%MOD
        if i+r+1 < N:
            dp[i+r+1]-=x
            dp[i+r+1]%MOD
    dp[i+1]+=dp[i]
    dp[i+1]%MOD
print((dp[-1]%MOD))

# Optimized solution
N,K = list(map(int,input().split()))
S = [tuple(map(int,input().split())) for _ in range(K)]
MOD=998244353
dp=[0]*N
dp[0]=1
for i in range(N-1):
    x = dp[i]
    dp[0]=0
    for k in range(K):
        l,r = S[k]
        if i+l < N:
            dp[i+l]+=x
            dp[i+l]%=MOD
        if i+r+1 < N:
            dp[i+r+1]-=x
            dp[i+r+1]%=MOD
    dp[i+1]+=dp[i]
    dp[i+1]%=MOD
print((dp[-1]%MOD))
# Original solution
#!/usr/bin/env Python3

#import
#import math
#import numpy as np
#= int(input())
#= input()
modnum = 998244353

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

def mod(num):
    return num % modnum

S = []

for l, r in LR:
    for i in range(l, r + 1):
        if not i in S:
            S.append(i)

dp = [0] * N

dp[0] = 1

for i in range(1, N):
    for s in S:
        if not s > i:
            dp[i] = mod(dp[i] + dp[i - s])

print((dp[N-1]))



# Optimized solution
#!/usr/bin/env Python3

#import
#import math
#import numpy as np
#= int(input())
#= input()
modnum = 998244353

N, K = list(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]))
# Original solution
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
N,K = list(map(int,input().split()))
LR = [tuple(map(int,input().split())) for i in range(K)]
LR.sort()
MOD = 998244353

arr = []
for l,r in LR:
    for i in range(l,r+1):
        arr.append(i)

from functools import lru_cache
@lru_cache(maxsize=10**8)
def rec(n):
    if n==0: return 1
    ret = 0
    for a in arr:
        if n-a < 0: break
        ret += rec(n-a)
        ret %= MOD
    return ret

print((rec(N-1)))

# Optimized solution
import sys
input = sys.stdin.readline
N,K = list(map(int,input().split()))
LR = [tuple(map(int,input().split())) for i in range(K)]
MOD = 998244353

dp = [1]
cumdp = [0,1]
for i in range(1,N):
    tmp = 0
    for l,r in LR:
        if i-l+1 <= 0: continue
        tmp += cumdp[i-l+1] - cumdp[max(0,i-r)]
    tmp %= MOD
    dp.append(tmp)
    cumdp.append((cumdp[-1] + tmp) % MOD)
print((dp[-1]))
# Original solution
def main():
    N, K = list(map(int, input().split()))
    MOD = 998244353
    cand = set()
    for _ in range(K):
        L, R = list(map(int, input().split()))
        A = set(range(L,R+1))
        cand |= A

    dp = [0] * (N + 5)
    dp[0] = 1
    for i in range(N):
        for j in cand:
            if i + j <= N:
                dp[i+j] += dp[i]
                dp[i+j] %= MOD

    print((dp[N-1]))
    




if __name__ == "__main__":
    main()

# Optimized solution

def main():
    N, K = list(map(int, input().split()))
    MOD = 998244353
    L = [0] * K
    R = [0] * K
    for i in range(K):
        L[i], R[i] = list(map(int, input().split()))

    
    dp = [0] * (N + 1)
    dpsum = [0] * (N + 1)
    dp[1] = 1
    dpsum[1] = 1
    for i in range(2,N+1):
        for j in range(K):
            l = i - R[j]
            r = i - L[j]
            if r <= 0:
                continue
            l = max(1,l)
            dp[i] += dpsum[r] - dpsum[l-1]
            dp[i] %= MOD
        dpsum[i] = dpsum[i-1] + dp[i]
        dpsum[i] %= MOD

    print((dp[N]))


if __name__ == "__main__":
    main()
# Original solution
N, K = list(map(int, input().split()))
S = []

for _ in range(K):
  L, R = list(map(int, input().split()))
  S.extend(list(range(L,R+1)))
  
S.sort()

DP =[[0]*N for _ in range(N)]
DP[0][0] = 1

for i in range(N-1):
  DP[i+1] = DP[i]
  for j in S:
    
    if i+j<N:
      DP[i+1][i+j] += DP[i][i]
    else:
      break

#for i in range(N):
  #print(DP[i])
print((DP[N-1][-1]%998244353))

# Optimized solution
N, K = list(map(int, input().split()))
S = []

for _ in range(K):
  L, R = list(map(int, input().split()))
  S.extend(list(range(L,R+1)))
  
S.sort()

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

for i in range(N-1):
  for j in S:
    
    if i+j<N:
      DP[i+j] += DP[i]
    else:
      break

print((DP[-1]%998244353))
# Original solution
N, K = list(map(int, input().split()))
S = []

for i in range(K):
  s = list(map(int, input().split()))
  S.append(s)
  
DP = [0]*N
DP[0] = 1

#print(DP)

for i in range(1,N):
  T = 0
  for s in S:
    l = max(0,i-s[1])
    r = max(0,i-s[0]+1)
    T += sum(DP[l:r])
  DP[i] = T
  #print(DP)
  
print((DP[-1]%998244353))

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

L = []
R = []

for _ in range(K):
  l, r = list(map(int, input().split()))
  L.append(l)
  R.append(r)
  
dp = [0]*(N+5)
dp[1] = 1

for i in range(2, N+1):
  dp[i] = dp[i-1]
  for j in range(K):
    if i-L[j] >= 0:
      dp[i] += dp[i-L[j]]
    if i-R[j]-1 >= 0:
      dp[i] -= dp[i-R[j]-1]
    dp[i] %= 998244353
    
print(((dp[N]-dp[N-1])%998244353))
# Original solution
# 配るDP、もらうDP

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

kukan = []
for _ in range(k):
    # 区間の問題は扱いやすいように[ )　の形に直せるなら直す
    l, r = list(map(int, input().split()))
    l -= 1
    kukan.append([l, r])

dp = [0 for i in range(n)]
dp[0] = 1

# 区間のL, Rは数字が大きいため、その差一つ一つを考えると時間がない！
# それゆえにL, Rの端を考えればいいようにするためにそこまでの累和を考える
ruiseki = [0 for i in range(n + 1)]
ruiseki[1] = 1
for i in range(1, n):
    for l, r in kukan:
        l = i - l
        r = i - r
        l, r = r, l
        # print(l, r)
        if r < 0:
            continue
        elif l >= 0:
            dp[i] += (ruiseki[r] - ruiseki[l]) % mod
        else:
            dp[i] += (ruiseki[r]) % mod
    ruiseki[i + 1] = (ruiseki[i] + dp[i])
    # print(ruiseki, dp)

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


# Optimized solution
N, K = list(map(int, input().split()))
mod = 998244353

L = []
for _ in range(K):
    a, b = list(map(int, input().split()))
    b += 1
    L.append([a, b])

ruiwa = [0] * (N + 1)
dp = [0] * (N + 1)
dp[1] = 1
ruiwa[1] = 1
for i in range(2, N + 1):
    for l, r in L:
        l = i - l
        r = i - r
        l, r = r, l
        if r < 0:
            continue
        elif l >= 0:
            # print(ruiwa, r, l)
            dp[i] += (ruiwa[r] - ruiwa[l]) % mod
        else:
            dp[i] += ruiwa[r] % mod
    ruiwa[i] = (ruiwa[i - 1] + dp[i]) % mod

print((dp[-1] % mod))
# Original solution
N, K = list(map(int, input().split()))
LRs = [tuple(map(int, input().split())) for _ in range(K)]
mod = 998244353
    
mem = [0] * (N)
mem[N-1] = 1

for _i in range(N-1):
    i = N-2 - _i
    for l, r in LRs:
        if i+l < N:
            mem[i] += sum(mem[i+l:min(i+r+1, N)])

    mem[i] %= mod

print((mem[0]))

# Optimized solution
N, K = list(map(int, input().split()))
LRs = [tuple(map(int, input().split())) for _ in range(K)]
mod = 998244353

def diff(l):
    tmp = None
    res = []
    for elm in l:
        if tmp is None:
            res.append(elm)
            tmp = elm
        else:
            res.append(elm-tmp)
            tmp = elm

    return res

res_diff = [0] * N
res_diff[1] = -1
res = [1]

for i in range(N-1):
    for l, r in LRs:
        if i+l < N:
            res_diff[i+l] += res[i]
        if i+r+1 < N:
            res_diff[i+r+1] -= res[i]
    
    res_next = (res[-1]+res_diff[i+1])%mod
    res.append(res_next)

print((res[N-1]))
# Original solution
n,k = tuple(map(int,input().split()))
boolean = [False for _ in range(n+1)]
for _ in range(k):
  l,r = tuple(map(int,input().split()))
  for num in range(l,r+1):
    boolean[num] = True;
dp = [0 for _ in range(n+1)]
dp[1] = 1
for i in range(2,n+1):
  for lower in range(1,i):
    if boolean[lower]:  #start + lower
      start = i - lower
      dp[i]+= dp[start]
print((dp[n]%998244353))

# Optimized solution
MOD = 998244353
N, K = list(map(int, input().split()))
LR = [tuple(map(int, input().split())) for i in range(K)]
 
dp = [0] * (N+1)
dp[1] = 1    #ok
for i in range(1, N):
  dp[i] += dp[i-1]   #as min k = 1, so carry this on to the next
  dp[i] %= MOD
  for l, r in LR:
    ll = i + l
    rr = i + r
    if ll <= N:
      dp[ll] += dp[i]    #yes ll is accesible
      dp[ll] %= MOD
    if rr < N:
      dp[rr+1] -= dp[i]    #not accessible and will get cancelled out when we take prefix sum
      dp[rr+1] %= MOD
 
print((dp[-1]))
# Original solution
n, k = list(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):
  for l, r in LR:
    for j in range(l, r + 1):
      if i - j >= 0:
        dp[i] += dp[i - j]
        dp[i] %= MOD

print((dp[-1]))

# Optimized solution
n, k = list(map(int, input().split()))
LR = [list(map(int, input().split())) for _ in range(k)]

MOD = 998244353

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

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


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

print((dp[-1]))
# Original solution
N,K=list(map(int,input().split()))

arr={0}
for i in range(K):
    a,b=list(map(int,input().split()))
    arr|=set([j for j in range(a,b+1)])

arr.discard(0)


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

ans=0
for i in range(N):
    for j in range(i,N):
        if dp[i][j]!=0:
            for k in arr:
                if j+k<=N-1:
                    dp[i+1][j+k]+=dp[i][j]
    ans+=dp[i][-1]
            
print((ans%998244353))

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

arr={0}
for i in range(K):
    a,b=list(map(int,input().split()))
    arr|=set([j for j in range(a,b+1)])

arr.discard(0)


dp=[0]*N 
dp[0]=1

ans=0
for i in range(N):
    for j in arr:
        if i+j<=N-1:
            dp[i+j]+=dp[i]
    
    
print((dp[-1]%998244353))
# Original solution
import sys

input = sys.stdin.readline

mod = 998244353

n, k = list(map(int, input().split()))

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

leaplist = []
for l, r in lr:
    leaplist += list(range(l, r + 1))
pass

dp = [0] * n
dp[0] = 1
for i in range(1, n):
    for l in leaplist:
        if i < l:
            break
        dp[i] += dp[i - l]
        dp[i] %= mod
print((dp[-1]))


# Optimized solution
import sys

input = sys.stdin.readline

mod = 998244353

n, k = list(map(int, input().split()))

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

a = [0] * n
a[0] = 1
a[1] = -1
f = [1]

for i in range(n - 1):
    for l, r in lr:
        if i + l < n:
            a[i + l] += f[i]
            a[i + l] %= mod
        else:
            break
        if i + r + 1 < n:
            a[i + r + 1] -= f[i]
            a[i + r + 1] %= mod
        else:
            break
    f.append((f[i] + a[i + 1]) % mod)
print((f[n - 1]))
# Original solution
import sys

input = sys.stdin.readline

mod = 998244353

n, k = list(map(int, input().split()))

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

a = [0] * n
a[0] = 1
a[1] = -1
f = [1]

for i in range(n - 1):
    for l, r in lr:
        if i + l < n:
            a[i + l] += f[i]
            a[i + l] %= mod
        else:
            break
        if i + r + 1 < n:
            a[i + r + 1] -= f[i]
            a[i + r + 1] %= mod
        else:
            break
    f.append((f[i] + a[i + 1]) % mod)
print((f[n - 1]))


# Optimized solution
import sys

input = sys.stdin.readline

mod = 998244353

n, k = list(map(int, input().split()))

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

if lr[0][0] == 1:
    f = [1, 1]
else:
    f = [1, 0]

for i in range(2, n):
    next_f = f[i - 1]
    for l, r in lr:
        if i - l >= 0:
            next_f += f[i - l]
        else:
            break
        if i - r - 1 >= 0:
            next_f -= f[i - r - 1]
        else:
            break
    f.append(next_f % mod)


print((f[n - 1]))
# Original solution
N, K = list(map(int, input().split()))
mod = 998244353
D = []
dp = [0] * (N+10)
for i in range(K):
    L, R = list(map(int, input().split()))
    for i in range(L, R+1):
        D.append(i)

D = sorted(D)
dp[0] = 1
for i in range(N):
    for d in D:
        if i + d > N:
            continue
        dp[i + d] += dp[i]
        dp[i + d] %= mod

print((dp[N-1]))



# Optimized solution
N, K = list(map(int, input().split()))
mod = 998244353
D = []
dp = [0] * (N+1)
for i in range(K):
    L, R = list(map(int, input().split()))
    D.append([L, R])

dp[0] = 1
a = 0
for i in range(N):
    a += dp[i]
    a %= mod
    for d in D:
        if i + d[0] > N:
            continue
        dp[i + d[0]] += a
        dp[i + d[0]] %= mod
        if i + d[1] + 1 > N:
            continue

        dp[i + d[1] + 1] -= a
        dp[i + d[1] + 1] %= mod


print((dp[N-1]))
# Original solution
N,K = list(map(int,input().split()))
l = []
for i in range(K):
    L,R = list(map(int,input().split()))
    l.append([L,R])


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)]
    b[i] = b[i-1]+a[i]
mod = 998244353
print((a[N]%mod))

# Optimized solution
N,K = list(map(int,input().split()))
l = []
for i in range(K):
    L,R = list(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)]
        else:
            break
    b[i] = b[i-1]+a[i]
mod = 998244353
print((a[N]%mod))
# Original solution
N,K = list(map(int,input().split()))
l = []
for i in range(K):
    L,R = list(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)]
        else:
            break
    b[i] = b[i-1]+a[i]
mod = 998244353
print((a[N]%mod))

# Optimized solution
N,K = list(map(int,input().split()))
l = []
mod = 998244353
for i in range(K):
    L,R = list(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))
# Original solution
N, K = list(map(int, input().split()))
LR = [tuple(map(int, input().split())) for _ in range(K)]

D = [1]
M = 10
memo = []
for i in range(1, N):
  count = 0
  for l, r in LR:
    if l <= i:
      ll = i - min(i, r)
      rr = i - l + 1
      LL = (ll + M - 1) // M
      RR = rr // M
      if RR > LL:
        count += sum(D[ll:LL*M]) + sum(memo[LL:RR]) + sum(D[RR*M:rr])
      else:
        count += sum(D[ll:rr])
  D.append(count % 998244353)
  if len(D) % M == 0:
    memo.append(sum(D[-M:]))
print((D[-1]))

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

D = [1]
M = 1000
memo = []
for i in range(1, N):
  count = 0
  for l, r in LR:
    if l <= i:
      ll = i - min(i, r)
      rr = i - l + 1
      LL = (ll + M - 1) // M
      RR = rr // M
      if RR > LL:
        count += sum(D[ll:LL*M]) + sum(memo[LL:RR]) + sum(D[RR*M:rr])
      else:
        count += sum(D[ll:rr])
  D.append(count % 998244353)
  if len(D) % M == 0:
    memo.append(sum(D[-M:]))
print((D[-1]))
# Original solution
N, K = list(map(int, input().split()))
LR = [tuple(map(int, input().split())) for _ in range(K)]

D = [1]
M = 5000
memo = []
for i in range(1, N):
  count = 0
  for l, r in LR:
    if l <= i:
      ll = i - min(i, r)
      rr = i - l + 1
      LL = (ll + M - 1) // M
      RR = rr // M
      if RR > LL:
        count += sum(D[ll:LL*M]) + sum(memo[LL:RR]) + sum(D[RR*M:rr])
      else:
        count += sum(D[ll:rr])
  D.append(count % 998244353)
  if len(D) % M == 0:
    memo.append(sum(D[-M:]))
print((D[-1]))

# Optimized solution
N, K = list(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]))
# Original solution
n,k = list(map(int,input().split()))
jis = [list(map(int, input().split())) for _ in range(k)]
jis.sort()
dp = [0 for _ in range(n)]
dp[0] = 1
mod = 998244353
for i in range(1,n):
	flag = True
	for u,v in jis:
		if flag is False: break
		for w in range(u,v+1):
			if i-w>=0:
				dp[i] += dp[i - w]
				dp[i] %= mod
			else:
				flag = False
				break
print(dp[n-1])

# Optimized solution
n,k = list(map(int,input().split()))
jis = [list(map(int, input().split())) for _ in range(k)]
jis.sort()

dp = [0 for _ in range(n)]
dp[0] = 1
pre = [0 for _ in range(n)]
pre[0] = 1
mod = 998244353
for i in range(1,n):
	flag = True
	for u,v in jis:
		uu,vv = i - v, i - u
		
		if vv >= 0:
			dp[i] += pre[vv] - (pre[uu - 1] if uu - 1 >= 0 else 0)
			dp[i] %= mod
	pre[i] += dp[i] + pre[i-1]
	pre[i] %= mod

print(dp[n-1])
# Original solution
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

MOD = 998244353
n, k = list(map(int, input().split()))
s = set()
for i in range(k):
    a, b = list(map(int, input().split()))
    s.update(list(range(a, b + 1)))
s = sorted(list(s))

dp = [0] + [0] * n
dp[1] = 1
for i in range(1, n + 1):
    for j in s:
        if i + j > n:
            break
        else:
            dp[i + j] = (dp[i + j] + dp[i]) % MOD
print((dp[n]))


# Optimized solution
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

MOD = 998244353
n, k = list(map(int, input().split()))
s = list()
for i in range(k):
    s.append(tuple(map(int, input().split())))

dp = [0] + [0] * n
diff = [0] + [0] * n
dp[1] = 1
for i in range(1, n):
    for j, k in s:
        if i + j > n:
            continue
        diff[i + j] += dp[i]
        if i + k + 1 > n:
            continue
        diff[i + k + 1] -= dp[i]
    dp[i] = (dp[i - 1] + diff[i]) % MOD
    dp[i + 1] = (dp[i] + diff[i + 1]) % MOD
print((dp[n]))