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-----
5 2
1 1
3 4

-----Sample Output-----
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.

Difficulty: interview

Starter code:

Solutions:
n, k = map(int, input().split())
l = [(0, 0) for i in range(k)]
for i in range(k):
    start, end = map(int, input().split())
    l[i] = start, end

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

dp[1] = 1
prefixSum[1] = 1

for i in range(2, n + 1):
    for j in range(k):
        start, end = l[j]
        i_s = max(i - start, 0)
        i_e = max(i - end -1, 0)    
        dp[i] += prefixSum[i_s] - prefixSum[i_e]
        dp[i] %= 998244353
    prefixSum[i] = prefixSum[i-1] + dp[i]
    prefixSum[i] %= 998244353

print(dp[n])

#!/usr/bin/env python3
import sys

MOD = 998244353  # type: int


def solve(N: int, K: int, L: "List[int]", R: "List[int]"):
    cum = [0]*(N+1)
    dp = [0]*(N+1)

    cum[1] = 1
    dp[1] = 1

    cnt = 0


    for i in range(2, N+1):
        for j in range(K):
            li = i - L[j]
            ri = i - R[j]
            if li < 0:
                continue

            ri = max(ri, 1)

            dp[i] += cum[li] - cum[ri-1]
        cum[i]=(cum[i-1]+dp[i])%MOD

    return print(dp[N]%MOD)


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    L = [int()] * (K)  # type: "List[int]"
    R = [int()] * (K)  # type: "List[int]"
    for i in range(K):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
    solve(N, K, L, R)

def __starting_point():
    main()

__starting_point()

n, k = [int(i) for i in input().split()]
rng = [[int(i) for i in input().split()] for i in range(k)]
mod = 998244353
dp = [0] * n

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

for i in range(1, n):
    for l, r in rng:
        dp[i] += dp_acc[max(0, i-l+1)] - dp_acc[max(0, i-r)]
        dp[i] %= mod
    dp_acc.append(dp_acc[i] + dp[i])

print((dp[n-1]))


import sys
#import time
from collections import deque, Counter, defaultdict
#from fractions import gcd
import bisect
import heapq
#import math
import itertools
import numpy as np
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
inf = 10**18
MOD = 1000000007
ri = lambda : int(input())
rs = lambda : input().strip()
rl = lambda : list(map(int, input().split()))
mod = 998244353

n,k = rl()
ch = []
for i in range(k):
    ch.append(tuple(rl()))
dp=[0]*(n+1)
dp[0]=0
dp[1]=1
for i in range(1,n):
    for e in ch:
        left = max(0, i-e[1])
        right = max(0,i-e[0]+1)
        dp[i+1]+= dp[right]-dp[left]
    dp[i+1] += dp[i]
    dp[i+1]%=mod
print((dp[n] - dp[n-1])%mod)

N,K = map(int, input().split())
mod = 998244353
L = list()
R = list()
for i in range(K):
  l,r = 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,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] % mod - dpSum[li-1] % mod
  dpSum[i] = dpSum[i-1] % mod + dp[i] % mod
ans = dp[N]
print(ans % mod)

n, k = map(int, input().split())
q = [tuple(map(int, input().split())) for _ in range(k)]
dp = [0] * (n + 5)
MOD = 998244353
cnt = 1
for i in range(1, n+5):
    cnt += dp[i]
    cnt %= MOD
    for p in q:
        if i + p[0] < n + 5:
            dp[i+p[0]] += cnt
            dp[i+p[0]] %= MOD
        if i + p[1] + 1 < n + 5:
            dp[i+p[1]+1] -= cnt
            dp[i+p[1]+1] %= MOD
print(dp[n])

mod = 998244353
n, k, *LR = map(int, open(0).read().split())
dp = [0] * (3*n)
dp[1] = 1
dp[2] = -1
for i in range(1, n+1):
    dp[i+1] += dp[i]
    dp[i+1] %= mod
    for l in LR[::2]:
        dp[i+l] += dp[i]
        dp[i+l] %= mod
    for r in LR[1::2]:
        dp[i+r+1] -= dp[i]
        dp[i+r+1] %= mod
print(dp[n])

N, K = map(int, input().split())
move = set()
MOD = 998244353
move = []
for i in range(K):
    move.append(tuple(map(int, input().split())))


dp = [0] * (2 * N + 3)
add = [0] * (2 * N + 3)
height = 0
dp[0] = dp[1] = 1
for i in range(1, N+1):
    height += add[i] % MOD
    if i != 1:
        dp[i] = height
    for L, R in move:
        add[i + L] += dp[i] % MOD
        add[i + R + 1] -= dp[i] % MOD
print(dp[N] % MOD)

def main():
    CONST = 998244353
    N,K = list(map(int,input().split()))
    lis = [0]*N*3
    MoveLis = []
    SumLis = [0]*N*3
    for i in range(K):
        L,R = list(map(int,input().split()))
        MoveLis.append((L,R))
    lis[1] = 1
    SumLis[1] = 1
    for i_n in range(2,N+1):
        for i_k in range(K):
            lis[i_n] += SumLis[max(i_n-MoveLis[i_k][0],0)] - SumLis[max(i_n-MoveLis[i_k][1]-1,0)]
            lis[i_n] %= CONST
        SumLis[i_n] += SumLis[i_n -1] + lis[i_n]
        SumLis[i_n] %= CONST
    print((lis[N]))
             




def __starting_point():
    main()


__starting_point()

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

for i in range(k):
    si = list(map(int, input().split()))
    s.append(si)
    
dp = [0] * (n+1)
dpsum = [0] * (n+1)
dp[1] = 1
dpsum[1] = 1

for j in range(2, n+1):
    for m in range(k):
        l = j - s[m][0]
        r = j - s[m][1]
        if l < 0:
            continue
        r = max(r, 1)
        dp[j] += dpsum[l] - dpsum[r-1]
    dpsum[j] = (dpsum[j-1] + dp[j])%mod 

ans = dp[n]%mod
print(ans)

import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
MOD = 998244353
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N, K = LI()
    LR = [LI() for _ in range(K)]

    dp = [0] * N
    dp[0] = 1
    dp_acm = list(itertools.accumulate(dp, initial=0))
    for i in range(1, N):
        for l, r in LR:
            dp[i] += dp_acm[max(i-l+1, 0)] - dp_acm[max(i-r, 0)]
            dp[i] %= MOD
        dp_acm[i+1] = dp_acm[i] + dp[i]
        dp_acm[i+1] %= MOD
    # print(dp)
    # print(dp_acm)

    print((dp[-1]))

def __starting_point():
    resolve()

__starting_point()

#!/usr/bin/env python3
import sys

MOD = 998244353  # type: int


def solve(N: int, K: int, L: "List[int]", R: "List[int]"):
    cum = [0]*(N+1)
    dp = [0]*(N+1)

    cum[1] = 1
    dp[1] = 1

    cnt = 0


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

    return print(dp[N]%MOD)


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    L = [int()] * (K)  # type: "List[int]"
    R = [int()] * (K)  # type: "List[int]"
    for i in range(K):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
    solve(N, K, L, R)

def __starting_point():
    main()

__starting_point()

n, k = map(int, input().split())
mod = 998244353
lr = []
s = set()
for i in range(k):
  l,r = map(int, input().split())
  for j in range(l,r+1):
    s.add(j)
  lr.append([l,r])

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

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

MOD = 998244353
N, K = list(map(int, input().split())) #Nはマス目の数、Kは区間の数(Kは10以下)
kukan = [tuple(map(int, input().split())) for _ in range(K)]

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

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

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

        dp[i] += sumdp[li] - sumdp[ri]
        dp[i] %= MOD

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

print((dp[N]))


n,k=list(map(int,input().split()))
mod=998244353
lr=[]
a=[0]*(n+1)
a[1]=1
for _ in range(k):
  l,r=list(map(int,input().split()))
  lr.append([l,r])
for i in range(2,n+1):
  for l,r in lr:
    if i-l<0: #iに到達可能なやり方がないとき
      continue
    a[i]+=a[i-l]-a[max(0,i-r-1)] #1手で到達可能なのは正味で何通りかを計算
  a[i]+=a[i-1] #同一区間の分を集約
  a[i]%=mod
print(((a[n]-a[n-1])%mod))


N , K = map(int,input().split())
mod = 998244353
L = [0]*K
R = [0]*K
for i in range(K):
  L[i] , R[i] = map(int,input().split())
L.sort()
R.sort()
dp = [0]*(N+1)
sdp = [0]*(N+1)
dp[1] = 1
sdp[1] = 1
for i in range(1,N):
  tdp = 0
  for j in range(K):
    if i - L[j] + 1 >= 0 :
      s1 = sdp[i - L[j] + 1]
    else:
      s1 = 0
    if i - R[j] >= 0:
      s2 = sdp[i - R[j]]
    else:
      s2 = 0
    tdp += s1 - s2
  dp[i+1] = tdp%mod
  sdp[i+1] = (sdp[i] + dp[i+1])%mod
print(dp[N]%mod)  

mod=998244353
n,k=map(int,input().split())
L=[]
R=[]
for _ in range(k):
    l,r=map(int,input().split())
    L.append(l)
    R.append(r)

sdp = [1]

def f(x):
    if x<0:
        return 0
    else:
        return sdp[x]

for i in range(1,n):
    x=0
    for j in range(k):
        x+=f(i-L[j])+mod-f(i-R[j]-1)
        x%=mod
    sdp.append((x+sdp[i-1])%mod)

print((sdp[n-1]+mod-sdp[n-2])%mod)

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

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

d = {}
acc = {}


def get_acc_num(i, l, r):
    if i - l <= 0:
        return 0
    if i - r <= 0:
        return acc[i-l]
    else:
        return acc[i-l] - acc[i-r-1]

MOD = 998244353
for i in range(1, N+1):
    # print(f"{i}-------------------")
    if i == 1:
        d[i] = 1
        acc[0] = 0
        acc[i] = 1
    else:
        d[i] = 0
        for l, r in S:
            # print(f"{l, r}")
            # print(get_acc_num(i, l, r))
            # print(get_acc_num(i, l, r))
            d[i] += get_acc_num(i, l, r) % MOD
            acc[i] = (acc[i-1] + d[i]) % MOD

print((d[N] % 998244353))



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

mod = 998244353
dp = [0] * n
sdp = [0] * (n+1)
dp[0] = 1
sdp[1] = 1
for i in range(1, n):
    for l, r in sec:
        dp[i] += sdp[max(i-l+1, 0)] - sdp[max(i-r, 0)]
        dp[i] %= mod
    sdp[i+1] = sdp[i] + dp[i]
    sdp[i+1] %= mod

print((dp[n-1]))


n, k = map(int, input().split())
mod = 998244353
l, r = [0] * n, [0] * n
dp = [0] * (n + 1)
ans = [0] * n
ans[0] = 1
dp[1] = 1
for i in range(k):
    l[i], r[i] = map(int, input().split())
    
    
for i in range(1, n):
    total = 0
    for j in range(k):
        total += dp[i - l[j] + 1] - dp[i - r[j]]
    ans[i] = total % mod
    dp[i + 1] = dp[i] + ans[i]
print(ans[-1])

def main():
    n, k = list(map(int, input().split()))
    ruiseki = [0] * (n + 1)
    mod = 998244353

    move_list = [list(map(int, input().split())) for i in range(k)]
    sorted_list = sorted(move_list)
    dp = [0] * (n + 1)
    dp[1] = 1
    ruiseki[1] = 1
    for i in range(2, n+1):
        for rng in sorted_list:
            left = max(0, i - rng[1]-1)
            right = min(i - rng[0], i - 1)
            if left < right:
                dp[i] += ruiseki[right] - ruiseki[left]
            else:
                break
        ruiseki[i] = ruiseki[i - 1] % mod + dp[i] % mod
    print((dp[-1] % mod))


def __starting_point():
    main()

__starting_point()

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

def main():
    n, k = list(map(int, input().split()))
    lr = [list(map(int, input().split())) for _ in [0]*k]
    bit = [0]*(n+1)
    bit[1] = 1
    mod = 998244353
    for i in range(1, n+1):
        if i+1 < n:
            bit[i+1] = (bit[i+1]+bit[i]) % mod
        k = bit[i]
        for l, r in lr:
            l += i
            if l > n:
                continue
            bit[l] = (bit[l]+k) % mod
            r += i+1
            if r <= n:
                bit[r] = (bit[r]-k) % mod
    print((bit[n] % mod))


main()


MOD = 998244353

def solve(n, k, l, r):
    dp = [0] * n
    dp[0] = 1
    memo = [1] * n
    for i in range(1, n):
        v = 0
        for x, y in zip(l, r):
            a = i - x
            if a < 0:
                continue
            v += memo[a]
            b = i - y - 1
            if b < 0:
                continue
            v -= memo[b]
        dp[i] = v % MOD
        memo[i] = (memo[i-1] + dp[i]) % MOD
    return dp[n-1]

n, k = list(map(int, input().split()))
l, r = list(zip(*[list(map(int, input().split())) for i in range(k)]))
print((solve(n, k, l, r)))


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

mod = 998244353

lr = []
ans = [0] * (N+1)
ans[1] = 1 
lr = []
for _ in range(K):
    l,r = map(int, input().split())
    lr.append([l,r])

for i in range(2,N+1):
    for l, r in lr:
        if i-l < 0:
            continue
        ans[i] += ans[i-l] - ans[max(0, i-r-1)]
    ans[i] += ans[i-1]
    ans[i] %= mod

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

n,k = map(int, input().split())
mod = 998244353
S = []
for _ in range(min(n, k)):
    l, r = map(int, input().split())
    S.append((l, r+1))
dp = [0] * (n+1)
cum = [0] * (n+1)
dp[1] = 1
cum[1] = 1
for i in range(2, n+1):
    # もらうdp
    for l, r in S:
        ll = max(0, i - r)
        rr = max(0, i - l)
        dp[i] += cum[rr] - cum[ll]
        dp[i] %= mod
    cum[i] = (cum[i-1] + dp[i]) % mod

print(dp[n])

N,K = map(int, input().split())
mod = 998244353
L = list()
R = list()
for i in range(K):
  l,r = 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,1):
  for j in range(K):
    li = i-R[j]
    ri = i-L[j]
    if ri < 0:
      continue
    li = max(li,0)
    dp[i] += dpSum[ri] % mod - dpSum[li-1] % mod
  dpSum[i] = dpSum[i-1] % mod + dp[i] % mod
ans = dp[N]
print(ans % mod)

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return list(map(int, input().split()))
def LIST(): return list(map(int, input().split()))
def ZIP(n): return list(zip(*(MAP() for _ in range(n))))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 998244353

N, K = MAP()
LR = [LIST() for _ in range(K)]
dp = [0]*(N+1)
dp_acc = [0]*(N+1)
dp[1] = 1
dp_acc[1] = 1

for i in range(2, N+1):
    for L, R in LR:
        l = max(0, i-R-1)
        r = max(0, i-L)
        dp[i] += dp_acc[r]-dp_acc[l]
        dp[i] %= mod
    dp_acc[i] = dp_acc[i-1] + dp[i]
    dp_acc[i] %= mod
    
print((dp[-1]))


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

MOD = 998244353

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

imos = [0] * n

for i in range(0, n):
	imos[i] += imos[i - 1]
	imos[i] %= MOD
	dp[i] += imos[i]
	dp[i] %= MOD
	for l, r in lr:
		if i + l < n:
			imos[i + l] += dp[i]
		if i + r + 1 < n:
			imos[i + r + 1] -= dp[i]
print(dp[n - 1])

def main():
    import sys
    input = sys.stdin.readline

    mod = 998244353

    n, k = list(map(int, input().split()))
    bk = []
    for _ in range(k):
        dl, dr = list(map(int, input().split()))
        bk.append((dl, dr))

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

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

    for i in range(2, n + 1):
        for dl, dr in bk:
            r = i - dl
            if r < 1:
                continue
            l = max(1, i - dr)
            dp[i] = (dp[i] + acc[r] - acc[l - 1]) % mod
        acc[i] = (acc[i - 1] + dp[i]) % mod
    print((dp[-1]))


def __starting_point():
    main()

__starting_point()

n,k = map(int,input().split())
mod = 998244353
s = []
for _ in range(k):
    l,r = map(int,input().split())
    s += [(l,r)]

s.sort()
a = [0]*(n+1)
a[1] = 1
for i in range(2, n+1):
    a[i] = a[i-1]
    for l,r in s:
        a[i] += a[max(0, i-l)] - a[max(0, i-r-1)]
    a[i] %= mod
print((a[n] - a[n-1]) % mod)

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

dp = [0] * (N + 1)##dpを累積和のリストにする
dp[1] = 1

for i in range(1,N):
    for e in range(K):##K=iの時の累積和の範囲
        left = max(0, i-R[e])##左側：とりうる一番小さいIdx
        right = max(0,i-L[e]+1)##右側：とりうる一番大きいIdx
        dp[i+1] += dp[right]-dp[left]##i+1番目のdpはdpの右ー左
        ##print(dp)
    dp[i+1] += dp[i]##累積和（＝現在の数字＋一つ前の累積和）にするために一つ前のdpを足す
    ##print(dp)
    dp[i+1]%=MOD
print((dp[N] - dp[N-1])%MOD)

q = 998244353

n, k = 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 l, r in lr:
        li = i - r
        ri = i - l
        if ri < 1: continue
        li = max(li, 1)
        dp[i] += (dpsum[ri] - dpsum[li - 1])
        dp[i] %= q
    dpsum[i] = dp[i] + dpsum[i - 1]
    dpsum[i] %= q

print(dp[n])

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

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

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

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

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

        dp[i] += prefix_sum[r1] - prefix_sum[l1]
        dp[i] %= MOD

    prefix_sum[i] = (prefix_sum[i - 1] + dp[i]) % MOD

print(dp[-1])

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

dp = [0] * (n+1)    # dp[i+1]: Num of ways to reach cell i (0-based).
dif = [0] * (n+1)   # dif[i] = dp[i] - dp[i-1] for  i > 0.

dif[1] = 1
dif[2] = -1
for i in range(1,n+1):
    dp[i] = (dp[i-1] + dif[i]) % 998244353
    for l,r in s:
        if i+l <= n:
            dif[i+l] += dp[i]
        if i+r <= n:
            dif[i+r] -= dp[i]

print(dp[-1])

# import itertools
# import math
# from functools import reduce
# import sys
# sys.setrecursionlimit(500*500)
# import numpy as np
# from collections import deque
# import heapq

# 入力
# N = int(input())
# S = input()
# n, *a = map(int, open(0))
N, K = map(int, input().split())
# L_R = list(map(int, input().split()))
# A = list(map(lambda x: int(x)*(-1), input().split()))
L_R = [list(map(int,input().split())) for _ in range(K)]
# S = input()

# B_C = sorted(B_C, reverse=True, key=lambda x:x[1])
# all_cases = list(itertools.permutations(P))
# a = list(itertools.combinations_with_replacement(range(1, M + 1), N))
# itertools.product((0,1), repeat=n)

# A = np.array(A)
# cum_A = np.cumsum(A)
# cum_A = np.insert(cum_A, 0, 0)

# edges = [list(map(int,input().split())) for _ in range(N - 1)]
# tree = [[] for _ in range(N + 1)]

# for edge in edges:
#     tree[edge[0]].append(edge[1])
#     tree[edge[1]].append(edge[0])

# depth = [-1] * (N + 1)
# depth[1] = 0
# count = [0] * (N + 1)

# for i in range(Q):
#     p, x = map(int, input().split())
#     count[p] += x

# def dfs(tree, s):
#     for l in tree[s]:
#         if depth[l[0]] == -1:
#             depth[l[0]] = depth[s] + 1
#             dfs(tree, l[0])
# dfs(tree, 1)

# 素因数分解
# 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):
#     lower_divisors , upper_divisors = [], []
#     i = 1
#     while i*i <= n:
#         if n % i == 0:
#             lower_divisors.append(i)
#             if i != n // i:
#                 upper_divisors.append(n//i)
#         i += 1
#     return lower_divisors + upper_divisors[::-1]

# bfs
# tree = [[] for _ in range(N + 1)]
# edges = [list(map(int,input().split())) for _ in range(M)]

# for edge in edges:
#     tree[edge[0]].append(edge[1])
#     tree[edge[1]].append(edge[0])

# depth = [-1] * (N + 1)
# depth[1] = 0

# d = deque()
# d.append(1)

# ans = [0] * (N + 1)
# while d:
#  v = d.popleft()
#  for i in tree[v]:
#    if depth[i] != -1:
#      continue
#    depth[i] = depth[v] + 1
#    ans[i] = v
#    d.append(i)

# # ans = depth[2:]
# print('Yes')
# print(*ans[2:], sep="\n")

# def gcd_list(numbers):
#     return reduce(math.gcd, numbers)

# # 高速素因数分解準備
# MAXN = 10**6+10
# sieve = [i for i in range(MAXN+1)]
# p = 2
# while p*p <= MAXN:
#     if sieve[p] == p:
#         for q in range(2*p, MAXN+1, p):
#             if sieve[q] == q:
#                 sieve[q] = p
#     p += 1

MOD = 998244353
L_R.sort()

f = [0] * N  # f: マスiまで移動する方法の個数(0-index)
f[0] = 1
a = [0] * (N + 1) # ai := fi - f_i-1
a[1] = -1  # この初期条件の-1を忘れないように注意!

for i in range(N - 1):
    for l, r in L_R:
        if i + l < N:
            a[i + l] += f[i]
            a[i + l] %= MOD
        if i + r + 1 < N:
            a[i + r + 1] -= f[i]
            a[i + r + 1] %= MOD
    f[i + 1] = (f[i] + a[i + 1]) % MOD

print(f[-1])

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

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

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

for i in range(1,n):
    tmp=0
    for l,r in s:
        tmp+=sdp[i-l+1]-sdp[i-r]
    dp[i]=tmp%mod
    sdp[i+1]=sdp[i]+dp[i]
print(dp[-1])

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

dp = [0] * (N+1)
dpSum = [0] * (N+1)
R = list()
L = list()

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

dp[1] = 1
dpSum[1] = 1

for i in range(2,N+1,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] % mod - dpSum[li-1] % mod
  dpSum[i] = (dpSum[i-1] + dp[i]) % mod

ans = dp[N] % mod
print(ans)


n,k=list(map(int,input().split()))
lr=[]
for i in range(k):
  l_,r_=list(map(int,input().split()))
  lr.append([l_,r_])

dp=[0]*(n+1)
sdp=[0]*(n+1)
dp[1]=1
sdp[1]=1
p=998244353
for i in range(2,n+1):
  for l,r in lr:
    if i-l>=1:
      if i-r>=1:
        dp[i]=(dp[i]+sdp[i-l]-sdp[i-r-1])%p
      else:
        dp[i]=(dp[i]+sdp[i-l])%p
  sdp[i]=(sdp[i-1]+dp[i])%p

print((dp[n]%p))



N,K=map(int,input().split())
mod=998244353
L=[0]*K;R=[0]*K
m=[0]*3*N
m[0]=1;m[1]=-1
for i in range(K):
  L[i],R[i]=map(int,input().split())
#print(m)

for j in range(N):
  m[j+1]+=m[j]%mod
  for i in range(K):
#    if j+L[i]>N-1:break
    m[j+L[i]] +=m[j]%mod
    m[j+R[i]+1] -=m[j]%mod
#a    print(j,i,m)
print(m[N-1]%mod)

n,k=list(map(int,input().split()))
mod=998244353
hee=[tuple(map(int,input().split())) for _ in range(k)]
dp=[0]*(n+1)
dp[1]=1
summdp=[0]*(n+1)
summdp[1]=1
for i in range(2,n+1):
    for l,r in hee:
        li=max(i-l,0)
        ri=max(i-r-1,0)
        dp[i]+=summdp[li]-summdp[ri]
        dp[i]%=mod
    summdp[i]=summdp[i-1]+dp[i]
print((dp[n]))



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

N,K=map(int,input().split())
mod=998244353
L=[0]*K;R=[0]*K
m=[0]*3*N
m[0]=1;m[1]=-1
for i in range(K):
  L[i],R[i]=map(int,input().split())
#print(m)

for j in range(N):
  m[j+1]+=m[j]%mod
  for i in range(K):
    if j+L[i]>N-1:continue
    m[j+L[i]] +=m[j]%mod
    m[j+R[i]+1] -=m[j]%mod
#a    print(j,i,m)
print(m[N-1]%mod)

N, K =map(int, input().split())
mod = 998244353
L = list()
R = list()

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

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

for i in range(2,N+1,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] % mod - dpSum[li-1] % mod
  dpSum[i] = dpSum[i-1] % mod + dp[i] % mod

ans = dp[N] % mod
print(ans)

"""
累積和によるDP高速化
"""

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

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

dp = [0] * N # dpテーブル
sdp = [0] * (N+1) # dpテーブルの累積和

# DPの初期値を設定
dp[0] = 1
sdp[1] = 1

for n in range(1, N):
    for lr in LR:
        left = max(0, n - lr[1])
        right = max(0, n - lr[0] + 1)
        dp[n] += sdp[right] - sdp[left]
        dp[n] %= mod
    sdp[n+1] = (sdp[n] + dp[n]) % mod

res = dp[N-1]
print(res)

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


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

for i in range(2, n+1):
    for l, r in lr:
        li = max(i-r, 1)
        ri = i-l
        if ri < 0: continue
        dp[i] += cum[ri] - cum[li-1]
        dp[i] %= mod
    cum[i] = dp[i] + cum[i-1]
    cum[i] %= mod
print(dp[n]%mod)

N, K = map(int, input().split())
rng = [list(map(int, input().split())) for i in range(K)]
dp = [0]*(N+1)
dp[1] = 1
s = [0]*(N+1)
s[1] = 1
MOD = 998244353
for i in range(2, N+1):
    for j, k in rng:
        if i - j < 1:
            pass
        elif i - k < 1:
            k = i - 1
        dp[i] += s[i-j] - s[i-k-1]
        dp[i] %= MOD
    s[i] += (s[i-1] + dp[i])%MOD
print(dp[-1])

N, K, *LR = list(map(int, open(0).read().split()))
MOD = 998244353
dp = [0] * N
acc = [0] * (N + 1)
dp[0] = 1
acc[1] = 1
for i in range(N):
    for l, r in zip(*[iter(LR)] * 2):
        left = max(0, i - r)
        right = max(0, i - l + 1)
        dp[i] += acc[right] - acc[left]
        dp[i] %= MOD
    acc[i + 1] = acc[i] + dp[i]
    acc[i + 1] %= MOD
print((dp[-1]))


N,K = map(int,input().split())
S=[]
for _ in range(K):
  L,R = map(int,input().split())
  S.append([L,R])
a=[0]*(N+1)
d=[0]*(3*N)
d[0] = 1     #d[i] = a[i+1]-a[i]
d[1] = -1
for i in range(1,N+1):
    a[i] = (a[i-1]+d[i-1])%998244353
    for l,r in S:
        d[i+l-1] += a[i]
        d[i+r] -= a[i]
print(a[N])

import sys
mod = 998244353

N, K = list(map(int, sys.stdin.readline().strip().split()))

step = []
for _ in range(K):
    L, R = list(map(int, sys.stdin.readline().strip().split()))

    step.append((L, R))
step.sort()

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

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

for i in range(2, N + 1):
    for L, R in step:
        iter_L = i - R
        iter_R = i - L

        if iter_R <= 0:
            continue
        
        iter_L = max(1, iter_L)

        dp[i] += (cusum[iter_R] - cusum[iter_L - 1]) % mod
    
    cusum[i] = (cusum[i - 1] + dp[i]) % mod

print((dp[N] % mod))


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

dp=[0]*(3*n)
dp[0]=1
dp[1]=-1
#imos
for i in range(n):
    for l,r in M:
        dp[l+i]+=dp[i]
        dp[i+r+1]-=dp[i]
    dp[i+1]=(dp[i]+dp[i+1])%mod
print(dp[n-1])

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)  # dpを到達方法の累積和のリストにする
dp[1] = 1

for i in range(1, N):
    for e in range(K):  # K=iの時の累積和の範囲
        left = max(0, i - R[e])  # 左側：とりうる一番小さいIdx
        right = max(0, i - L[e] + 1)  # 右側：とりうる一番大きいIdx
        dp[i + 1] += dp[right] - dp[left]  # i+1番目のdpはdpの右ー左
    dp[i + 1] += dp[i]  # 累積和（＝現在の数字＋一つ前の累積和）にするために一つ前のdpを足す
    dp[i + 1] %= MOD
print(((dp[N] - dp[N - 1]) % MOD))





def __starting_point():
  
  N,K = [int(x) for x in input().split()]
  S = []
  l = [0] * K
  r = [0] * K
  for i in range(K):
    l[i],r[i] = [int(x) for x in input().split()]
  
  dp = [0] * N
  dp[0] = 1
  sdp = [0] * (N+1)
  sdp[0] = 0
  sdp[1] = 1
  for i in range(1,N):

    dp[i] = sum([sdp[max([i-l[k]+1, 0])] - sdp[max([i-r[k], 0])]
                 for k in range(K)]) % 998244353
    sdp[i+1] = (dp[i] + sdp[i]) % 998244353
    

  
    
  print((dp[-1]))

  
  
  




  

  
      


  
    
  
  


__starting_point()

q = 998244353

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

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

result = [0]*N
result[0] = 1
result[1] = -1

for i in range(N - 1):
    for l, r in S:
        if i + l < N:
            result[i + l] = (result[i + l] + result[i]) % q
            if i + r + 1 < N:
                result[i + r + 1] = (result[i + r + 1] - result[i]) % q
    result[i + 1] = (result[i] + result[i + 1]) % q

print(result[-1])

N,K = map(int, input().split())
mod = 998244353
L = list()
R = list()
for i in range(K):
  l,r = map(int, input().split())
  L.append(l)
  R.append(r)
dp = [0] * (N+1)
dpSum = [0] * (N+1)
dp[1] = 1
dpSum[1] = 1
for i in range(2,N+1,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] % mod - dpSum[li-1] % mod
  dpSum[i] = dpSum[i-1] % mod + dp[i] % mod
ans = dp[N] % mod
print(ans)

n,k=map(int,input().split())
S=[]
for i in range(k):
    s=list(map(int,input().split()))
    S.append(s)
mod=998244353
DP=[0 for i in range(n+1)]
DP[1]=1
R=[0 for i in range(n+1)]
R[1]=1
for i in range(2,n+1):
    for l,r in S:
        li=i-r
        ri=i-l
        if ri<0:
            continue
        DP[i]+=R[ri]-R[max(li-1,0)]
        DP[i]%=mod
    R[i]=R[i-1]+DP[i]
    R[i]%=mod
print(DP[n])

mod = 998244353
n, k, *LR = map(int, open(0).read().split())
dp = [0] * (3*n)
dp[1] = 1
dp[2] = -1
for i in range(1, n+1):
    dp[i+1] += dp[i]
    dp[i+1] %= mod
    for l, r in zip(LR[::2], LR[1::2]):
        dp[i+l] += dp[i]
        dp[i+l] %= mod
        dp[i+r+1] -= dp[i]
        dp[i+r+1] %= mod
print(dp[n])

#参考
#https://atcoder.jp/contests/abc179/submissions/16904040

MOD = 998244353
 
def solve(lr, dp, n):
    acc_dp = [1] * n    # 累積和
    for i in range(1, n):
        val = 0
        for d in lr: # 各区間について区間和を求め足していく
            a = i - d[0]
            if a < 0:
                continue
            b = i - d[1] - 1 
            val += acc_dp[a] - (acc_dp[b] if b >= 0 else 0) # 区間和を素早く求める
        dp[i] = val % MOD
        acc_dp[i] = (acc_dp[i - 1] + dp[i]) % MOD
    return dp[n - 1]
 
 
def main():
    f = open(0)
    n, k = [int(x) for x in f.readline().split()]
    lr = [[int(x) for x in f.readline().split()] for _ in range(k)]
    dp = [0] * n
    dp[0] = 1
    ans = solve(lr, dp, n)
    print(ans)
 
main()

import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return list(map(int,input().split()))
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(list(map(max,x)))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

n,k = m()
mod = 998244353
ans = [0 for i in range(n+1)]

data = []
for i in range(k):
    data.append(l())

for i in range(0,n):
    if i == 0:
        ans[i] = 1
    else:
        ans[i] += ans[i-1]
        ans[i] %= mod
        for j in range(k):
            l,r = data[j]
            r += 1
            if l + i <= n:
                ans[i+l] += ans[i]
                ans[i+l] %= mod
            if r + i <= n:
                ans[i+r] -= ans[i]
                ans[i+r] %= mod

print((ans[-1]))









n, k = list(map(int, input().split()))
mod = 998244353
arr = []
for i in range(k):
    arr.append(list(map(int, input().split())))
arr.sort()
dp = [0] * (n+1)
dp[1] = 1
presum = [0] * 10
for i in range(2, n+1):
    for j in range(k):
        presumj = presum[j]
        if i - arr[j][0] >= 1:
            presumj += dp[i - arr[j][0]]
        if i - arr[j][1] -1 >= 1:
            presumj -= dp[i - arr[j][1] -1]
        presumj %= mod
        presum[j] = presumj
        dp[i] += presumj
        dp[i] %= mod
print(dp[n])

N, K = list(map(int, input().split()))
S = [list(map(int, input().split())) for _ in range(K)]
dp = [0 for _ in range(N + 1)]
S.sort()

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


for i in range(S[0][0]+1, N+1):
    rui = 0
    for s in S:
        # 区間の終わりが0より大きい場合
        if i - s[0] > 0:
            # 区間の始まりを計算し、実際のendを計算する
            end = max([i - s[1], 0])
            # 追跡わにより、場合の和を加える
            rui += (dp[i - s[0]] - dp[end - 1]) % 998244353
    # 累積和としてdpに記入する
    dp[i] = (dp[i-1] + rui) % 998244353
print(((dp[N]-dp[N-1]) % 998244353))


n, k = [int(x) for x in input().split()]
lr = [[int(x) for x in input().split()] for _ in range(k)]

accsum = [0, 1] + [0] * n


def sum_between(l: int, r: int) -> int:
    if r >= 1:
        return accsum[r] - accsum[max(l - 1, 0)]
    else:
        return 0


for i in range(2, n + 1):
    accsum[i] = (accsum[i - 1] + sum(sum_between(i - r, i - l) for l, r in lr)) \
        % 998244353


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


def main():
  mod=998244353
  N,K=map(int,input().split())
  S=[tuple(map(int,input().split())) for _ in range(K)]
  S.sort()
  
  f=[0]*N
  f[0]=1
  a=[0]*(N+1)
  a[1]=-1
  
  for i in range(0,N-1):
    for l,r in S:
      if i+l<N:
        a[i+l]+=f[i]
        a[i+l]%=mod
      if i+r+1<N:
        a[i+r+1]-=f[i]
        a[i+r+1]%=mod
    f[i+1]=(f[i]+a[i+1])%mod
  print(f[-1])
  
  
  
  
def __starting_point():
  main()
__starting_point()

N,K = list(map(int,input().split()))
mod = 998244353
dp = [0] * (N+1)
dpSum = [0] * (N+1)
R = []
L = []

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

dp[1] = 1
dpSum[1] = 1
for i in range(2,N+1,1):
  for j in range(K):
    li = i - R[j]
    ri = i - L[j]
    if ri < 1:
      continue
    li = max(li, 1)
    dp[i] += dpSum[ri] % mod - dpSum[li-1] % mod
  dpSum[i] = dpSum[i-1] % mod + dp[i] % mod
ans = dp[N] % mod
print(ans)


N,K = map(int,input().split())
mod = 998244353
dp = [0] * (N+1)
R = []
L = []
for i in range(K):
  l,r = map(int,input().split())
  L.append(l)
  R.append(r)
  
dp[1] = 1
s = [0] * (N+1)
s[1] = 1
for i in range(2,N+1,1):
  for j in range(K):
    li = i - R[j]
    ri = i - L[j]
    if ri < 1:
      continue
    li = max(li, 1)
    dp[i] += s[ri]%mod - s[li-1]%mod
  s[i] = s[i-1]%mod + dp[i]%mod
ans = dp[N] % mod
print(ans)

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

dp = [0] * N
dp[0] = 1
ds = [1] * N
for i in range(1, N):
    for s in S:
        if i - s[0] < 0:
            continue
        if i - s[1] - 1 < 0:
            dp[i] += ds[i - s[0]] % MOD
        else:
            dp[i] += (ds[i - s[0]] - ds[i - s[1] - 1]) % MOD
    ds[i] = ds[i - 1] + dp[i] % MOD

print(dp[-1] % MOD)

N, K = list(map(int, input().split()))
mod = 998244353
L = list()
R = list()
for i in range(K):
  l,r = list(map(int, input().split()))
  L.append(l)
  R.append(r)
dp = [0] * (N+1)
dpSum = [0] * (N+1)
dp[1] = 1
dpSum[1] = 1
for i in range(2,N+1,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] % mod - dpSum[li-1] % mod
  dpSum[i] = dpSum[i-1] % mod + dp[i] % mod
ans = dp[N] % mod
print(ans)


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


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

LR = [list(map(int, input().split())) for _ in range(K)]
# LR.sort(key=lambda x: x[0], reverse=True)

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

prefix_sum = [0]
prefix_sum.append(1)

for i in range(2, N + 1):
    for j in range(K):
        l, r = LR[j]

        l1 = max(i - r - 1, 0)
        r1 = max(i - l, 0)

        dp[i] += prefix_sum[r1] - prefix_sum[l1]
        dp[i] %= MOD

    prefix_sum.append(prefix_sum[-1] + dp[i])

print((dp[-1]))


def main():
    n,k = map(int,input().split())
    mod = 998244353
    s = [list(map(int,input().split()))]
    for _ in range(k-1):
        l,r = map(int,input().split())
        s.append([l,r])
    ans = [0] * (n+1)
    d = [0] * (n+1)
    d[1] = 1
    d[2] = -1
    for i in range(1,n+1):
        ans[i] += (ans[i-1] + d[i]) % mod
        for l,r in s:
            if i+l < n+1:
                d[i+l] += ans[i] % mod
            if i+r+1 < n+1:
                d[i+r+1] -= ans[i] % mod
    print(ans[-1]%mod)

def __starting_point():
    main()
__starting_point()

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

MOD = 998244353

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

imos = [0] * n

for i in range(0, n):
	imos[i] += imos[i - 1]
	dp[i] += imos[i]
	dp[i] %= MOD
	for l, r in lr:
		if i + l < n:
			imos[i + l] += dp[i]
			imos[i] %= MOD
		if i + r + 1 < n:
			imos[i + r + 1] -= dp[i]
print(dp[n - 1])

# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read
 
#n,q = map(int, readline().split())
#*a, = map(int, readline().split())
 
def get(i,l,r):
    a = i-r
    b = i-l
    if b < 0: return 0
    return acc[b] - (acc[a-1] if a-1 >= 0 else 0)
 
 
 
n,k = map(int, readline().split())
lr = [list(map(int, readline().split())) for _ in range(k)]
 
dp = [0]*(n)
dp[0] = 1
acc = [1]*(n)
 
 
MOD = 998244353
for i in range(1,n):
    v = 0
    for l,r in lr:
        v += get(i,l,r)
    dp[i] = v%MOD
    acc[i] = (acc[i-1] + dp[i])%MOD
    #print(dp,acc)
 
print(dp[n-1]%MOD)

N, K = list(map(int, input().split()))
A = []
for i in range(K):
  l, r = list(map(int, input().split()))
  A.append((l, r))
M = 998244353
dp = [0 for i in range(N+1)]
sumdp = [0 for i in range(N+1)]
dp[1] = 1
sumdp[1] = 1
for i in range(2, N+1):
  tmp = 0
  for l, r in A:
    l, r = i-r, i-l
    if r <= 0:
      continue
    l = max(1, l)
    tmp += (sumdp[r] - sumdp[l-1])
    tmp %= M
  dp[i] = tmp
  sumdp[i] = (sumdp[i-1] + dp[i])%M
print((dp[N]))


MOD = 998244353


def main():
    N, K = list(map(int, input().split()))
    ranges = [None] * K
    for i in range(K):
        L, R = list(map(int, input().split()))
        ranges[i] = (L, R)
    delta = [0] * (N+1)
    ans = [0] * (N+1)
    delta[1] = 1
    delta[2] = (-1) % MOD
    for i in range(1, N+1):
        ans[i] = (ans[i-1] + delta[i]) % MOD
        for L, R in ranges:
            if i + L <= N:
                delta[i+L] = (delta[i+L] + ans[i]) % MOD
            if i + R + 1 <= N:
                delta[i+R+1] = (delta[i+R+1] - ans[i]) % MOD
    print((ans[N]))


def __starting_point():
    main()

__starting_point()

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

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

for i in range(2, N+1):
    for l, r in lr:
        if i-l < 1:
            continue
        dp[i] += dp[i-l]-dp[max(i-r-1, 0)]
    dp[i] += dp[i-1]
    dp[i] %= mod

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

n, k = map(int, input().split())
lr = [list(map(int, input().split())) for _ in range(k)]
mod = 998244353
dp = [0]*(n+1)
imos = [0]*(n+1)

for i in range(n):
    if i == 0:
        tmp = 1
    else:
        imos[i] = (imos[i] + imos[i-1])%mod
        tmp = imos[i]
    for j in range(k):
        if lr[j][0]+i >n: continue
        imos[lr[j][0]+i] += tmp
        imos[min(lr[j][1]+1+i, n)] -= tmp
print(imos[-2]%mod)

n, k = map(int,input().split())
mod = 998244353
dp = [0]*(n*3)

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

lr.sort()

imos = [0]*(n*3)
imos[1] = 1
dp[1] = 1

for i in range(1, n):
    if i >= 2:
        dp[i+1] += dp[i]
    for l, r in lr: # i = 1の時点でdp[2]は確定している。そのためi>=2では同時に累積和を求める。
        dp[i+l] += dp[i]
        dp[i+l] %= mod
        dp[i+r+1] -= dp[i]
        dp[i+r+1] %= mod

        
print(dp[n]%mod)

N, K=map(int,input().split())
mod=998244353
M=[]
for i in range(K):
    l,r=map(int,input().split())
    M.append([l,r])
 
dp=[0]*(3*N)
dp[0]=1
dp[1]=-1
#imos
for i in range(N):
    for l,r in M:
        dp[l+i]+=dp[i]
        dp[i+r+1]-=dp[i]
    dp[i+1]=(dp[i]+dp[i+1])%mod
print(dp[N-1])

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

z = [1]+[0]*(N-1)
s = [0]*(N+2)
for j in range(N):
    for l, r in LR:
        z[j] += s[j-l] - s[j-r-1]
    s[j] = (s[j-1] + z[j])%mod

print(z[-1]%mod)

n, k = list(map(int, input().split()))
l = [None] * k
r = [None] * k
for i in range(k):
    l[i], r[i] = list(map(int, input().split()))
mod = 998244353
s = [0] * n
d = [0] * n
s[0] = 1
for i in range(n - 1):
    for j in range(k):
        if i + l[j] < n:
            d[i + l[j]] += s[i]
            d[i + l[j]] %= mod
        if i + r[j] + 1 < n:
            d[i + r[j] + 1] -= s[i]
            d[i + r[j] + 1] %= mod
    s[i + 1] = s[i] + d[i + 1]
    s[i + 1] %= mod
print((d[n - 1]))


N,K=list(map(int,input().split()))
mod=998244353
L=[0]*K;R=[0]*K
m=[0]*3*N
m[0]=1;m[1]=-1
for i in range(K):
  L[i],R[i]=list(map(int,input().split()))

for j in range(N):
  m[j+1]+=m[j]%mod
  for i in range(K):
    if j+L[i]>N-1:continue
    m[j+L[i]] +=m[j]%mod
    m[j+R[i]+1] -=m[j]%mod
print((m[N-1]%mod))


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

mod = 998244353
n,k=map(int,input().split())
s=[list(map(int,input().split())) for _ in range(k)]
dp=[0]*(n+1)
dp[1]=1
dpsum=[0]*(n+1)
dpsum[1]=1

for i in range(2,n+1):
  for s1,s2 in s:
    l=i-s2
    r=i-s1
    if r<1:
      continue
    l=max(l,1)
    dp[i]+=(dpsum[r]-dpsum[l-1])%mod
  dpsum[i]=(dpsum[i-1]+dp[i])%mod
print(dp[-1]%mod)

mod = 998244353
n, k = map(int, input().split())
list_N = [0] * (n + 1)
list_N[1] = 1
list_N[2] = -1
d = []
for _ in range(k):
    l, r = map(int, input().split())
    d.append([l, r])
cnt = 0
for i in range(1, n + 1):
    cnt += list_N[i]
    cnt %= mod
    if cnt != 0:
        for l, r in d:
            if i + l <= n:
                list_N[i + l] += 1 * cnt
            if i + r + 1 <= n:
                list_N[i + r + 1] -= 1 * cnt

print(cnt % mod)

n, k = map(int, input().split())
L = [0 for i in range(k)]
R = [0 for i in range(k)]
for i in range(k):
    L[i], R[i] = map(int, input().split())

DP = [0 for i in range(n+1)] # DP[0] is not used
S = [0 for i in range(n+1)]
mod = 998244353
DP[1] = 1
S[1] = 1
for i in range(2, n+1):
    for j in range(k):
        imin, imax = max(0, i - R[j]), max(0, i - L[j]) 
        DP[i] = (DP[i] + S[imax] - S[imin - 1]) % mod # sum DP[i-R[j]]~DP[i-L[j]]
    S[i] = (S[i-1] + DP[i]) % mod

print(DP[n])

mod=998244353
n,k=map(int,input().split())
L=[]
R=[]
for _ in range(k):
    l,r=map(int,input().split())
    L.append(l)
    R.append(r)
dp=[0]*n
dp[0]=1
dp_s=[0]*n
dp_s[0]=1
for i in range(1,n):
    for j in range(k):
        l=L[j]
        r=R[j]
        if i-l>=0:
            if i-r>=1:
                dp[i]=(dp[i]+dp_s[i-l]-dp_s[i-r-1])%mod
            else:
                dp[i]=(dp[i]+dp_s[i-l])%mod
    dp_s[i]=(dp_s[i-1]+dp[i])%mod
print(dp[n-1])

n, k = list(map(int,input().split()))
p = 998244353
l = []
r = []

for i in range(0, k):
  x, y = list(map(int,input().split()))
  l.append(x)
  r.append(y)

a = [0] * (n + 1)
s = [0] * (n + 1)
a[1] = 1
s[1] = 1

for i in range(2, n + 1):
  for j in range(0, k):
    L = max(i - r[j], 1)
    R = max(i - l[j], 0)
    a[i] += s[R] - s[L - 1]
    a[i] %= p
  s[i] = s[i - 1] + a[i]
  s[i] %= p

print((a[n]))


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

#print (L)                                                                                                                                                                 

dp = [0 for i in range(N + 10)]
sdp = [0 for i in range(N + 11)]
dp[0] = 1
sdp[1] = 1

for i in range(1, N):
    #print('i:',i)                                                                                                                                                         
    for array in L:
        #print('array loop:', array)                                                                                                                                       
        if i - array[-1] < 0:
            start = 0
        else:
            start = i - array[-1]
        if i - array[0] < 0:
            end = 0
        else:
            end = i - array[0] + 1
                                                                                                                                       
        dp[i] += sdp[end] - sdp[start]
    dp[i] = dp[i] % 998244353
    sdp[i+1] = sdp[i] + dp[i]                                                                                                                                                         

print(dp[N-1])

n,k=map(int,input().split());A=[1]+[0]*n;S=[[*map(int,input().split())]for _ in"_"*k];m=998244353
for i in range(1,n):
  A[i]+=A[i-1]
  for l,r in S:
    if i>r:A[i]-=A[i-r-1]
    if i>=l:A[i]+=A[i-l]
  A[i]%=m
print((A[n-1]-A[n-2])%m)

N,K=map(int,input().split())
LR=[list(map(int,input().split())) for i in range(K)]
d=[0]*(N+1)
da=[0]*(N+1)
d[1]=da[1]=1
m=998244353
for i in range(1,N):
    for l,r in LR:
        if l<=i+1:
            d[i+1]+=da[i+1-l]-da[max(0,i-r)]
    da[i+1]=(da[i]+d[i+1])%m
print(d[-1]%m)

n, k = map(int,input().split())
l = []
r = []
MOD = 998244353
for i in range(k):
    i1, i2 = map(int, input().split())
    l.append(i1)
    r.append(i2)

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

for i in range(1,n+1):
    for j in range(k):
        li = i-r[j]
        ri = i-l[j]
        if ri < 0:
            continue
        li = max(0,li)
        dp[i] += (dpsum[ri] - dpsum[li-1])%MOD
    dpsum[i] = (dpsum[i-1] + dp[i])%MOD

print(dp[n]%MOD)

n, k = list(map(int, input().split()))
mod = 998244353
dp = [0 for _ in range(n + 5)]
dpsum = [0 for _ in range(n + 5)]
dp[1] = 1
dpsum[1] = 1
l = []
r = []

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

for i in range(1, n + 1):
    for j in range(k):
        # 左端はi-区間右端
        lindex = i - r[j]
        rindex = i - l[j]
        dp[i] += dpsum[rindex] - dpsum[lindex - 1]
        dp[i] %= mod
    dpsum[i] = dpsum[i - 1] + dp[i]
    dpsum[i] %= mod
# print(dp)
# print(dpsum)

print((dp[n]))


#!/usr/bin/env python3
import sys

MOD = 998244353  # type: int

def solve(N: int, K: int, L: "List[int]", R: "List[int]"):
    n = N+1
    a = [0] * n
    s = [0] * n
    a[1] = 1
    s[1] = 1
    for i in range(2, n):
        for k in range(K):
            l = max(i - R[k], 0)
            r = max(i - L[k], 0)
            a[i] += s[r] - s[l-1]
            a[i] %= MOD
        s[i] = s[i-1] + a[i]
        s[i] %= MOD
    return a[N] % MOD


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    L = [int()] * (K)  # type: "List[int]"
    R = [int()] * (K)  # type: "List[int]"
    for i in range(K):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
    print((solve(N, K, L, R)))

def __starting_point():
    main()

__starting_point()

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

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

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

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

# -*- coding utf-8 -*-

MOD = 998244353

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

S = set()
for LR in LR_K:
    S |= set(range(LR[0], LR[1] + 1))

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

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

for i in range(2, N + 1):
    for LR in LR_K:
        li = max(i - LR[1], 1)
        ri = i - LR[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]))


n, k = list(map(int, input().split()))
dp = [0]*(n)
a = [list(map(int, input().split())) for i in range(k)]

dp[0] = 1
dp[1] = -1
for i in range(n-1):
    for l, r in a:
        if i+l < n:
            dp[i+l] += dp[i]
    for l, r in a:
        if i+r+1 < n:
            dp[i+r+1] -= dp[i]

    dp[i+1] += dp[i]
    dp[i+1] %= 998244353

print((dp[n-1]))