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

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]
print((dp[n]%998244353))

# Optimized solution
n,k = list(map(int,input().split()))
sec = []
for i in range(k):
  l,r = list(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))
# Original solution
from collections import deque
MOD = 998244353
N, K = list(map(int, input().split()))
LR = [list(map(int, input().split())) for _ in range(K)]

S = list()
for lr in LR:
    for i in range(lr[0], lr[1]+1):
        S.append(i)

dp = [0]*(N+1) # dp[i] : iに行く方法
dp[1] = 1

memo1 = deque()
memo2 = deque()

for i in range(1, N+1):
    # for s in S:
    #     if i + s <= N:
    #         dp[i + s] += dp[i]
    #         dp[i + s] %= MOD
    while(len(memo1)):
        # l = m[1]
        # r = m[2]
        m = memo1.popleft()
        if m[1] <= i and i <= m[2]:
            dp[i] += m[0]
            dp[i] %= MOD
        
        if not(m[2] < i):
            memo2.append(m)
    
    while(len(memo2)):
        tmp = memo2.popleft()
        memo1.append(tmp)
    
    for lr in LR:
        memo1.append([dp[i], lr[0] + i, lr[1] + i])
    
print((dp[N]))

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

dp = [0]*(N+1)
acc = [0]*(N+1) # acc[i] = dp[1] + ... dp[i]

dp[1] = 1
acc[1] = 1
for i in range(2, N+1):
    for lr in LR:
        l = lr[0]
        r = lr[1]

        dp[i] += (acc[max(0, i - l)] - acc[max(0, i - r - 1)] + MOD)
        dp[i] %= MOD
    acc[i] = (acc[i-1] + dp[i]) % MOD
    
    

print((dp[N]))
# print(acc)
# print(dp[N])
# Original solution
n, k = list(map(int, input().split()))
s = []
for i in range(k):
    a, b = list(map(int, input().split()))
    for j in range(a, b+1):
        s.append(j)
s = set(s)
dp = [0]*(n+1)
dp[1] = 1
mod = 998244353
for i in range(1, n+1):
    for ss in s:
        if i+ss <= n:
            dp[i+ss] += dp[i]
            dp[i+ss] %= mod
print((dp[-1]))


# Optimized solution
n, k = list(map(int, input().split()))
s = []
for i in range(k):
    a, b = list(map(int, input().split()))
    s.append((a, b))
dp = [0]*(n+1)
v = 0
mod = 998244353
for i in range(1, n+1):
    if i == 1:
        for l, r in s:
            if i+l <= n:
                dp[i+l] += 1
            if i+r+1 <= n:
                dp[i+r+1] -= 1
    else:
        v += dp[i]
        v %= mod
        for l, r in s:
            if i+l <= n:
                dp[i+l] += v
            if i+r+1 <= n:
                dp[i+r+1] -= v


print((v % mod))
# Original solution
n, k = list(map(int, input().split()))

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

mod = 998244353

dp = [0] * (n + 1)
#１マス目の行き方は１通り
dp[1] = 1
dpsum = [0] * (n + 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]
  
  dpsum[i] = dpsum[i - 1] + dp[i]

print((dp[n] % mod))



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

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

mod = 998244353

dp = [0] * (n + 1)
#１マス目の行き方は１通り
dp[1] = 1
dpsum = [0] * (n + 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]) % mod
  
  dpsum[i] = dpsum[i - 1] + dp[i]

print((dp[n] % mod))
# Original solution
n, k = list(map(int, input().split()))
s = [] 
mod = 998244353

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

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

for i in range(2,n+1):
    for l, r in s:
        li = max(i-r,1)
        ri = max(i-l,0)
        dp[i] += dpsum[ri] - dpsum[li-1]
    dpsum[i] = dpsum[i-1] + dp[i]

print((dp[n]%mod))

# Optimized solution
n, k = list(map(int, input().split()))
s = [] 
mod = 998244353

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

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

for i in range(2,n+1):
    for l, r in s:
        li = max(i-r,1)
        ri = max(i-l,0)
        dp[i] += (dpsum[ri] - dpsum[li-1])%mod
    dpsum[i] = (dpsum[i-1] + dp[i])%mod

print((dp[n]%mod))
# Original solution
n,k=list(map(int,input().split()))
mod=998244353
r=[0]*k
l=[0]*k
for _ in range(k):
  l_,r_=list(map(int,input().split()))
  l[_]=l_
  r[_]=r_
dp=[0]*n
dp[0]=1
dpsum=[0]*n
dpsum[0]=1
for i in range(1,n):
  for j in range(k):
    li=i-r[j]
    ri=i-l[j]
    if ri>=0:
      li=max(li,0)
      dp[i]+=dpsum[ri]-dpsum[li-1]
  dpsum[i]=dpsum[i-1]+dp[i]
print((dp[n-1]%mod))

# Optimized solution
n,k=list(map(int,input().split()))
mod=998244353
s=set()
for _ in range(k):
  l,r=list(map(int,input().split()))
  for j in range(l,r+1):
    s.add(j)
m=len(s)
dp=[0]*n
dp[0]=1
for i in range(1,n):
  for j in s:
    if i-j>=0:
      dp[i]+=dp[i-j]
print((dp[n-1]%mod))
# Original solution
n,k=list(map(int,input().split()))
mod=998244353
s=set()
for _ in range(k):
  l,r=list(map(int,input().split()))
  for j in range(l,r+1):
    s.add(j)
m=len(s)
dp=[0]*n
dp[0]=1
for i in range(1,n):
  for j in s:
    if i-j>=0:
      dp[i]+=dp[i-j]
print((dp[n-1]%mod))


# Optimized solution
n,k=list(map(int,input().split()))
mod=998244353
l=[0]*n
r=[0]*n
for i in range(k):
  l[i],r[i]=list(map(int,input().split()))
dp=[0]*(n+10)
dp[0]=1
sumdp=[0]*(n+10)
sumdp[1]=1
for i in range(1,n):
  for j in range(k):
    li=max(0,i-r[j])
    ri=max(0,i-l[j]+1)
    dp[i]+=sumdp[ri]-sumdp[li]
  sumdp[i+1]=(sumdp[i]+dp[i])%mod
print((dp[n-1]%mod))
# Original solution
N,K = list(map(int,input().split()))

MOD = 998244353

interval = []
for i in range(K):
    L,R = list(map(int,input().split()))
    for j in range(L,R+1):
        interval.append(j)

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

for i in range(N-1):
    for j in interval:
        if j <= N-1 - i:
            dp[i+j] += dp[i]
            dp[i+j] %= MOD

print((dp[N-1]))

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

MOD = 998244353

interval = []
for i in range(K):
    intv = [int(x) for x in input().split()]
    interval.append(intv)

dp = [0]*N
diff = [0]*(N-1)
dp[0] = 1
diff[0] = -1

for i in range(N-1):
    for L,R in interval:
        if L <= N-1 - i:
            diff[i+L-1] += dp[i]
        if R+1 <= N-1 - i:
            diff[i+R] -= dp[i]
    dp[i+1] = dp[i] + diff[i]
    dp[i+1] %= MOD

print((dp[N-1]))
# Original solution
import sys
def input(): return sys.stdin.readline().rstrip()

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()

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

for i in range(2,N+1):
    count = 0
    for l,r in L:
        if l >= i:
            break
        elif l < i and i - r > 1:
            count += dp[i-l] - dp[i-r-1]
        else:
            count += dp[i-l]
    dp[i] = dp[i-1] + count

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

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

mod = 998244353
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()

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

for i in range(2,N+1):
    count = 0
    for l,r in L:
        if l >= i:
            break
        elif l < i and i - r > 1:
            count += dp[i-l] - dp[i-r-1]
        else:
            count += dp[i-l]
    dp[i] = (dp[i-1] + count) % mod

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

mod = 998244353

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

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

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



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

mod = 998244353

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

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

ans = 0
s = 0
flags = [1] * K
for i in range(1, N+1):
	s += dp[i]
	s %= mod
	for k in range(K):
		if flags[k] == 0:
			break
		l, r = lr[k]
		if i+l <= N:
			dp[i+l] += s
			if i+r+1 <= N:
				dp[i+r+1] -= s
			else:
				ans += s
				ans %= mod
				break
		else:
			flags[k] = 0
			break
print(ans)
# Original solution
n,k = list(map(int,input().split()))
mod = 998244353

s = []
for i in range(k):
    l,r = list(map(int,input().split()))
    for i in range(l,r+1):
        s.append(i)
s.sort()
# print(s)
dp = [0 for i in range(n+1)]
dp[1] = 1
for i in range(2,n+1):
    for j in s:
        if i-j >= 1:
            dp[i] += dp[i-j]
    # print(dp)
print((dp[n] % mod))

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

l,r = [0]*k,[0]*k
for i in range(k):
    ll,rr = list(map(int,input().split()))
    l[i],r[i] = ll,rr

dp = [0]*(n+1)
dpsum = [0]*(n+1)
dp[1], dpsum[1] = 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
        dp[i] += dpsum[ri] - dpsum[li-1]
        dp[i] %= mod
    dpsum[i] = dpsum[i-1] + dp[i]
print((dp[n]))
# Original solution
import sys
input = sys.stdin.readline
m = 998244353
def main():
    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+1)
    dp[1] = 1
    dpsum = [0]*(n+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(li,1)
            dp[i] += dpsum[ri] - dpsum[li-1]
        dpsum[i] = dpsum[i-1]+dp[i]

    print((dp[n]%m))
main()

# Optimized solution
m = 998244353
def main():
    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+1)
    dp[1] = 1
    dpsum = [0]*(n+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(li,1)
            dp[i] += dpsum[ri] - dpsum[li-1]
        dpsum[i] = (dpsum[i-1]+dp[i])%m

    print((dp[n]%m))
main()
# Original solution
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

mod = 998244353

n, k = list(map(int, input().split()))
s = set()
for _ in range(k):
    l, r = list(map(int, input().split()))
    for i in range(l, r + 1):
        s.add(i)

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

for i in range(1, n + 1):
    for j in range(i):
        if i - j in s:
            dp[i] += dp[j]
            dp[i] %= mod

print((dp[-2]))
    

# Optimized solution
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

mod = 998244353

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 + 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]))
# Original solution
P=998244353
N,K=list(map(int,input().split()))
LR=[]
for _ in range(K):
  l,r=list(map(int,input().split()))
  LR+=list(range(l,r+1))
LR=list(set(LR))
c=[0]*N
c[0]=1
for k in range(N):
  S=[x for x in LR if x<=k]
  while len(S):
    c[k]+=c[k-S[-1]]%P
    S.pop()
print((c[-1]%P))

# Optimized solution
P=998244353
N,K=list(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))
# 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+1])
L.sort()
mod=998244353
A=[0 for i in range(N+1)]
A[1]=1
for i in range(N+1):
    if A[i]>0:
        A[i]%=mod
        for l,r in L:
            for n in range(l+i,r+i):
                if n<=N:
                    A[n]+=A[i]
                else:
                    break
print((A[N]%mod))

# Optimized solution
N,k=list(map(int,input().split()))
L=[0 for i in range(2)]

K=[]
for i in range(k):
    l,r=list(map(int,input().split()))
    K.append([l,r])
mod=998244353
L[1]=1
R=[0,1]
for i in range(2,N+1):
    cnt=0
    for l,r in K:
        cnt+=R[max(0,i-l)]
        cnt-=R[max(0,i-(r+1))]
    cnt%=mod
    L.append(cnt)
    R.append(R[-1]+cnt)
print((L[-1]%mod))
#print(R)
# Original solution
# -*- coding: utf-8 -*-
"""
Created on Sat Sep 19 20:18:10 2020

@author: liang
"""
#D
N, K = list(map(int, input().split()))
areas = list()
for i in range(K):
    l, r = list(map(int,input().split()))
    areas.append((l,r))
areas_sum = [0] * N 

d = [0] * N
d[0] = 1
for i in range(N):
    for j in range(K):
        l, r = areas[j]
        if i-l >= 0:
            areas_sum[j] += d[i-l]
        if i-r-1 >= 0:
            areas_sum[j] -= d[i-r-1]
    d[i] += sum(areas_sum)
    d[i] %= 998244353 

#print(d)
ans = d[N-1]
print(ans)

# Optimized solution
# -*- coding: utf-8 -*-
"""
Created on Sat Sep 19 20:18:10 2020

@author: liang
"""
#D
N, K = list(map(int, input().split()))
areas = list()
for i in range(K):
    l, r = list(map(int,input().split()))
    areas.append((l,r))
#areas_sum = [0] * N 
tmp = 0
d = [0] * N
#check = [0] * N
#check[0] = 1
d[0] = 1
for i in range(N):
    for j in range(K):
        l, r = areas[j]
        if i-l >= 0:
            #areas_sum[j] += d[i-l]
            tmp += d[i-l]
        if i-r-1 >= 0:
            #areas_sum[j] -= d[i-r-1]
            tmp -= d[i-r-1]
    d[i] += tmp
    #check[i] += tmp
    d[i] %= 998244353 
    tmp  %= 998244353 
    #t.append(tmp)

#print(d)
#print(check)
ans = d[N-1]
print(ans)
#print(tmp)
# Original solution
N, K = list(map(int, input().split()))
S = []
for j in range(K):
    LRj = list(map(int, input().split()))
    for s in range(LRj[0], LRj[1] + 1):
        S.append(s)

m =  998244353

# print(S)

dp = [0] * N
dp[0] = 1
for i in range(1, N):
    for s in S:
        if s <= i:
            # print(i, i-s)
            dp[i] += dp[i - s] % m
            dp[i] %= m

ans = dp[N - 1]

print(ans)

# Optimized solution
N, K = list(map(int, input().split()))
S = []
for j in range(K):
    S.append(list(map(int, input().split())))

m =  998244353

# print(S)

dp = [0] * N
dp[0] = 1
sum_of_region = [0] * K
for i in range(1, N):
    for j in range(K):
        if i - S[j][0] >= 0:
            sum_of_region[j] += dp[i - S[j][0]]
        if i - S[j][1] - 1 >= 0:
            sum_of_region[j] -= dp[i - S[j][1] - 1]
        dp[i] += sum_of_region[j] % m
        dp[i] %= m
    # print(i, dp, sum_of_region)

ans = dp[N - 1]
print(ans)
# Original solution
N, K = list(map(int, input().split()))
dp = [0] * N
dp[0] = 1
dp_sum = [0] * N
L = [0] * K
R = [0] * K
mod = 998244353

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

for i in range(1, N):
    # マスiにたどり着くためのパターン数を数える
    cnt = 0
    for j in range(K):
        start = max(0, i - R[j])
        end = i - L[j]
        if end < 0:
            continue
        cnt += sum(dp[start:end+1]) % mod
        cnt %= mod
    dp[i] = cnt

print((dp[N - 1]))


# Optimized solution
N, K = list(map(int, input().split()))
dp = [0] * N
dp[0] = 1
dp_sum = [0] * N
dp_sum[0] = 1
L = [0] * K
R = [0] * K
mod = 998244353

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

for i in range(1, N):
    # マスiにたどり着くためのパターン数を数える
    cnt = 0
    for j in range(K):
        start = max(0, i - R[j])
        end = i - L[j]
        cnt += (dp_sum[end] - dp_sum[start - 1]) % mod
        cnt %= mod
    dp[i] = cnt
    dp_sum[i] = dp_sum[i - 1] + cnt

print((dp[N - 1]))
# Original solution
n,k=[int(c) for c in input().split()]
MOD = 998244353
segs = set()
for _ in range(k):
    a,b=[int(c) for c in input().split()]
    for i in range(a,b+1):
        segs.add(i)

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

for i in range(n-1):
    if dp[i] != 0:
        for j in segs:
            if i + j < n:
                dp[i+j] = dp[i+j] + dp[i]
                dp[i+j]%=MOD

# print(dp)
print((dp[-1]))



# Optimized solution
n,k=[int(c) for c in input().split()]
MOD = 998244353
segs = []
for _ in range(k):
    a,b=[int(c) for c in input().split()]
    segs.append((a,b))


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

for i in range(n):
    # dp[i] = dp[i] + dp[i-1]
    if dp[i] < 0:
        dp[i]+=MOD
    for a,b in segs:
        if i+a <=n:
            dp[i+a]+=dp[i]
        if i+b+1 <= n:
            dp[i+b+1]-=dp[i]
    dp[i]%=MOD
    if i !=0:
        dp[i+1] = dp[i+1]+dp[i]

print((dp[n-1]%MOD))
# Original solution
N, K = list(map(int, input().split()))
dp = [0] *  (2 * 10 ** 5 + 1)
S = set()
for i in range(K):
    l, r = list(map(int, input().split()))
    for v in range(l, r + 1):
        S.add(v)

dp[1] = 1
MOD = 998244353
for i in range(1, N):
    for v in S:
        if i + v <= N:
            dp[i + v] += dp[i]
            dp[i + v] %= MOD

print((dp[N]))



# Optimized solution
N, K = list(map(int, input().split()))
W = [0] * (N + 1)
W[1] = 1

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

MOD = 998244353
for i in range(1, N):
    for l, r in R:
        a = max(i - r, 0)
        b = i - l
        if b < 0:
            continue
        W[i + 1] += (W[b + 1] - W[a])
        W[i + 1] %= MOD
    W[i + 1] += W[i]
    
print((W[N] - W[N - 1]))
# Original solution
N, K = list(map(int, input().split()))
LR = [list(map(int, input().split())) for _ in range(K)]

dp = [0] * (N + 1)
dpsum = [0] * (N + 1)
dp[1] = 1
dpsum[1] = 1
for i in range(2, N + 1):
    for j in range(K):
        li = max(i - LR[j][1], 1)
        ri = i - LR[j][0]
        if ri < 0:
            continue
        dp[i] += dpsum[ri] - dpsum[li - 1]
    dpsum[i] = dpsum[i - 1] + dp[i]

print((dp[N] % 998244353))


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


mod = 998244353
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):
        li = max(i - LR[j][1], 1)
        ri = i - LR[j][0]
        if ri < 0:
            continue
        dp[i] += dpsum[ri] - dpsum[li - 1]
        dp[i] %= mod
    dpsum[i] = dpsum[i - 1] + dp[i]

print((dp[N]))
# Original solution
mod = 998244353

class FenwickTree:
    def __init__(self, n, init_list=None):
        self.n = n
        self.data = [0] * n
        if init_list:
            assert n == len(init_list)
            for i in range(n):
                self.add(i, init_list[i])
        
    def add(self, i, val):
        assert 0 <= i < self.n
        i += 1
        while i <= self.n:
            self.data[i - 1] = (val + self.data[i - 1]) % mod
            i += i & -i #LSBを加算して上の層へ
            
    def update(self, i, val):
        self.add(i, val - self.sum(i, i+1))

    def sum(self, l, r): #[l, r)
        assert  0 <= l <= r <= self.n
        if l != 0:
            return (self.sum(0, r) - self.sum(0, l)) % mod
        ret = 0
        while r > 0:
            ret = (ret + self.data[r - 1]) % mod
            r -= r & -r #LSB減算して上の層へ
        return ret

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

s = []
for _ in range(k):
    l, r = list(map(int, input().split()))
    s.append((l, r))

ft = FenwickTree(n)
ft.add(0, 1)
for i in range(1, n):
    for l, r in s:
        jl = i - l
        jr = max(i - r, 0)
        if jl < 0:
            continue
        ft.add(i, ft.sum(jr, jl+1) % mod)
print((ft.sum(n-1, n) % mod))

# Optimized solution
mod = 998244353

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

s = []
for _ in range(k):
    l, r = list(map(int, input().split()))
    s.append((l, r))

dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n+1):
    for l, r in s:
        jl = max(i - l, 0)
        jr = max(i - r - 1, 0)
        dp[i] = (dp[i] + dp[jl] - dp[jr]) % mod
    dp[i] += dp[i-1]
print(((dp[n] - dp[n-1]) % mod))
# Original solution
mod = 998244353
N, K = list(map(int,input().split()))

v = []
for _ in range(K):
    L, R = list(map(int,input().split()))
    # for d in range(L, R+1):
    #     moves.append(d)
    v.append((L, R))
v.sort()

dp = [0] * N        # マスi-1に到達するまでの操作列の個数
sdp = [0] * (N + 1) # dp[i]までの累積和 
dp[0] = 1
sdp[1] = 1

for n in range(1, N):
    for p in v:
        left = max(0, n - p[1])
        right = max(0, n - p[0]+1)
        dp[n] += sdp[right] - sdp[left]
    sdp[n+1] = sdp[n] + dp[n]

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

# Optimized solution
n, k = list(map(int, input().split()))
sec = [list(map(int, input().split())) for _ in range(k)]
sec.sort()
    
mod = 998244353
    
dp = [0] * n
dp[0] = 1
sum_dp = [0, 1]
for i in range(1, n):
    for l, r in sec:
        if i - l < 0:
            break
        elif i - r > 0:
            dp[i] = ((dp[i] + sum_dp[i-l+1]) % mod - sum_dp[i-r]) % mod
        else:
            dp[i] = (dp[i] + sum_dp[i-l+1]) % mod
    
    sum_dp.append((sum_dp[-1] + dp[i]) % mod)
    
print((dp[n-1]))
# Original solution
n, k = list(map(int, input().split()))
m = 998244353

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

    for j in range(l, r+1):
        s.append(j)

dp = [0] * n
dp[0] = 1
for i in range(n):
    for j in s:
        ind = i-j
        if ind >= 0:
            dp[i] += dp[ind]
            dp[i] %= 998244353

print((dp[n-1]))

# Optimized solution
n, k = list(map(int, input().split()))
m = 998244353

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

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

for i in range(1, n):
    thisTotal = 0
    for l, r in s:
        indL = i-l
        if indL >= 0:
            indR = max(0, i-r)

            thisTotal += totals[indL] - totals[indR-1]

    dp[i] = (thisTotal%m)
    totals[i] = (totals[i-1] + thisTotal)%m

print((dp[n-1]))