CodeEff/ECCO huggingface dataset:
# Original solution
def main():
    n, k = list(map(int, input().split()))
    lr = [list(map(int, input().split())) for _ in range(k)]

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

    dp[0] = 1
    dp[1] = -1

    for i in range(0, n):
        if i>0: dp[i] += dp[i-1]
        for l,r in lr:
            if i+l > n: continue
            dp[i+l] += dp[i]
            dp[min(n, i+r+1)] -= dp[i]

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

main()


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

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

dp[0] = 1
dp[1] = -1

for i in range(0, n):
    if i>0: dp[i] += dp[i-1]
    dp[i] %= 998244353
    for l,r in lr:
        if i+l > n: continue
        dp[i+l] += dp[i]
        dp[min(n, i+r+1)] -= dp[i]

print((dp[-2] % 998244353))
# Original solution
MOD = 998244353
N, K = list(map(int, input().split()))
L = []
R = []
for k in range(K):
    l, r = list(map(int, input().split()))
    L += [l]
    R += [r]
# memo = [[0 for i in range(N+2)] for k in range(K)]
memo = [0 for i in range(N+2)]
memo[1] = 1
memo[2] = -1
cusum = 0
for i in range(1, N+1):
    cusum += memo[i]
    # print(cusum)
    for k in range(K):
        l, r = L[k], R[k]
        # for j in range(i+l, min(i+r+1, N+1)):
        #     memo[j] += memo[i]
        memo[min(i+l, N+1)] += cusum
        memo[min(i+r+1, N+1)] -= cusum
    # print(memo)
# for i in range(1, N+1):
#     for k in range(K):
#         memo[k][i+1] += memo[k][i]
print((cusum % MOD))

# Optimized solution
MOD = 998244353
N, K = list(map(int, input().split()))
L = []
R = []
for k in range(K):
    l, r = list(map(int, input().split()))
    L += [l]
    R += [r]
# memo = [[0 for i in range(N+2)] for k in range(K)]
memo = [0 for i in range(N+2)]
memo[1] = 1
memo[2] = -1
cusum = 0
for i in range(1, N+1):
    cusum = (cusum + memo[i]) % MOD
    # print(cusum)
    for k in range(K):
        l, r = L[k], R[k]
        # for j in range(i+l, min(i+r+1, N+1)):
        #     memo[j] += memo[i]
        memo[min(i+l, N+1)] += cusum
        memo[min(i+r+1, N+1)] -= cusum
    # print(memo)
# for i in range(1, N+1):
#     for k in range(K):
#         memo[k][i+1] += memo[k][i]
print((cusum % MOD))
# Original solution
#dpで素直にやるとO(N^2)だから、累積和で高速化しO(KN)にする

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

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

cnt = [0]*n
cnt[0] = 1
sum = [0]*n
sum[0] = 1
for i in range(1,n):
  for j in range(k):
    if i > s[j][1]:
      cnt[i] += sum[i-s[j][0]] - sum[i-s[j][1]-1]
    elif i >= s[j][0]:
      cnt[i] += sum[i-s[j][0]]
    sum[i] = sum[i-1] + cnt[i]

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

# Optimized solution
#dpで素直にやるとO(N^2)だから、累積和で高速化しO(KN)にする

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

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

cnt = [0]*n
cnt[0] = 1
sum = [0]*n
sum[0] = 1
for i in range(1,n):
  for j in range(k):
    if i > s[j][1]:
      cnt[i] += sum[i-s[j][0]] - sum[i-s[j][1]-1]
    elif i >= s[j][0]:
      cnt[i] += sum[i-s[j][0]]
    cnt[i] %= mod
    sum[i] = (sum[i-1] + cnt[i]) % mod

print((cnt[-1]))
# Original solution
N,K=list(map(int,input().split()))
S=[]
NUM=998244353
for _ in range(K):
    l,r=list(map(int,input().split()))
    for i in range(l,r+1):
        S.append(i)
S.sort()
dp=[0]*(N+1)
dp[1]=1
for i in range(2,N+1):
    for s in S:
        if i-s<=0: break
        dp[i]+=dp[i-s]
        dp[i]%=NUM

print((dp[N]))


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

NUM=998244353
dp=[0]*(N+1)
dp[1]=1
sums=[0]*(N+1)
sums[1]=1
for i in range(2,N+1):
    for s in S:
        _l,_r=i-s[0],i-s[1]-1
        if _l<0:
            continue
        elif _r<0:
            _r=0
        dp[i]+=sums[_l]-sums[_r]
        dp[i]%=NUM
    sums[i]=dp[i]+sums[i-1]
    sums[i]%=NUM

print((dp[N]))
# Original solution
import sys
input = sys.stdin.readline

class FenwickTree:
    def __init__(self, size):
        self.bit = [0] * (size + 1)
        self.size = size

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

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

mod = 998244353
N, K = list(map(int, input().split()))
L, R = list(zip(*[list(map(int, input().split())) for _ in range(K)]))
dp = FenwickTree(N + 1)
dp.add(1, 1)
dp.add(2, -1)
for i in range(1, N):
    x = dp.sum(i)
    for j in range(K):
        dp.add(i + L[j], x)
        if i + R[j] + 1 <= N:
            dp.add(i + R[j] + 1, -x)
print((dp.sum(N)))

# Optimized solution
import sys
input = sys.stdin.readline

mod = 998244353
N, K = list(map(int, input().split()))
L, R = list(zip(*[list(map(int, input().split())) for _ in range(K)]))
dp = [0] * (N + 1)
dp[1] = 1
dp[2] = -1
x = 0
for i in range(1, N):
    x = (x + dp[i]) % mod
    for j in range(K):
        if i + L[j] > N:
            continue
        dp[i + L[j]] = (dp[i + L[j]] + x) % mod
        if i + R[j] + 1 <= N:
            dp[i + R[j] + 1] = (dp[i + R[j] + 1] - x) % mod
x = (x + dp[N]) % mod
print(x)
# Original solution
n,k=list(map(int,input().split()))
S = {}
for i in range(k):
  tmp = list(map(int,input().split()))
  lr = list(range(tmp[0],tmp[1]+1))
  S = set(lr).union(S)

MOD = 998244353

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

# 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)
sdp = [0] * (n+1)
dp[1] = 1
sdp[1] = 1

for i in range(n+1):
  for j in range(k):
    left = max(0, i-lr[j][1])
    right = max(0, i-lr[j][0]+1)
    
    dp[i] += sdp[right] - sdp[left]
  if i+1 <= n:
    sdp[i+1] = sdp[i]%mod + dp[i]%mod

print((dp[n]%mod))
# Original solution
n,k = list(map(int,input().split()))
st = set([])
for i in range(k):
  x,y = list(map(int,input().split()))
  for z in range(x,y+1):
    st.add(z)
ans = [1]
for i in range(1,n):
  s = 0
  for x in st:
    if i >= x:
      s = s + ans[i-x]
  ans.append(s % 998244353)   
  
print((ans[-1]))  
  
  
    
  

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

for i in range(1,n):
  s = 0
  for (x,y) in st:
    if i > y:
      s = (s + total[i-x] - total[i-y-1]) % 998244353
    elif i >= x:
      s = (s + total[i-x]) % 998244353
  total.append((s+total[-1]) % 998244353)   
  
print(((total[-1]-total[-2]) % 998244353))
# Original solution
n , k = list(map(int, input().split()))

li = [0]*(n+2)
lis = []
lis2 =[0]*(3*n)
lis2[1]=1

for i in range(k):
    l,r = list(map(int, input().split()))
    for j in range(l,r+1):
        lis.append(j)

for i in range(1,n+1):
    for j in lis:
        lis2[i]%=998244353
        lis2[i+j]+=lis2[i]

print((lis2[n]))


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

li = [0]*(n+2)
lis = []
lr=[]
lis2 =[0]*(3*n)
lis2[1]=1
lis2[2]=-1

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

for i in range(1,n+1):
    lis2[i]+=lis2[i-1]
    lis2[i]%=998244353

    for j,k in lr:
        lis2[i+j]+=lis2[i]
        lis2[i+k+1]-=lis2[i]

print((lis2[n]%998244353))
# Original solution
n,k = (int(x) for x in input().split())
s = []
for _ in range(k):
    a,b = (int(x) for x in input().split())
    s+=list(range(a,b+1))
mod = 998244353
    
l = [0]*(n)
s = sorted(s)
min_num = s[0]
for i in range(min_num,n):
    for j in s:
        if j < i:
	        l[i] += (l[i-j])
    if i in s:
        l[i] += 1
    l[i] %= mod
print((l[n-1]))

# Optimized solution
n,k = (int(x) for x in input().split())
lr = []
for _ in range(k):
    l,r = (int(x) for x in input().split())
    lr.append((l,r))
lr.sort()

mod = 998244353

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

for i in range(2,n+1):
    cnt = 0
    for l,r in lr:
        if l >= i:
            break
        else:
            cnt += dp[i-l] - dp[max(0,i-r-1)]
    dp[i] = (dp[i-1] + cnt) % mod

print((cnt%mod))
# Original solution
import sys
from functools import lru_cache
sys.setrecursionlimit(10 ** 8)


N, K = list(map(int, input().split()))
M = 998244353
S = set()
for _ in range(K):
    L, R = list(map(int, input().split()))
    for i in range(L, R + 1):
        S.add(i)


@lru_cache(None)
def dp(i):
    if i < 1:
        return 0
    elif i == 1:
        return 1
    else:
        res = 0
        for d in S:
            res += dp(i - d)
            res %= M
        return res
print((dp(N) % M))

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

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

for i in range(1, N):
    cur = 0
    for L, R in K:
        a = i - R
        b = i - L
        if b < 0:
            continue
        cur += prefix[b] - (prefix[a - 1] if a - 1 >= 0 else 0)
    dp[i] = cur % M
    prefix[i] = prefix[i - 1] + dp[i]
    prefix[i] %= M
print((dp[N - 1]))
# Original solution
class BIT:
    def __init__(self, n, MOD):
        self.n = n
        self.data = [0] * (n + 1)
        self.MOD = MOD

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

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


n, k = list(map(int, input().split()))
mod = 998244353
bit = BIT(n + 2, mod)
ranges = []
for _ in range(k):
    l, r = list(map(int, input().split()))
    ranges.append((l, r))

bit.add(1, 1)

for i in range(1, n):
    v = bit.sum(i)
    for l, r in ranges:
        bit.add(i + l, v)
        bit.add(min(n + 1, i + r + 1), -v)
print((bit.sum(n) - bit.sum(n - 1) % mod))


# Optimized solution
class BIT:
    def __init__(self, n, MOD):
        self.n = n
        self.data = [0] * (n + 1)
        self.MOD = MOD

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

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


n, k = list(map(int, input().split()))
mod = 998244353
bit = BIT(n + 2, mod)
ranges = []
for _ in range(k):
    l, r = list(map(int, input().split()))
    ranges.append((l, r))

bit.add(1, 1)

for i in range(1, n):
    v = bit.sum(i)
    for l, r in ranges:
        bit.add(i + l, v)
        bit.add(min(n + 1, i + r + 1), -v)
print(((bit.sum(n) - bit.sum(n - 1)) % mod))
# Original solution
class BIT:
    def __init__(self, n, MOD):
        self.n = n
        self.data = [0] * (n + 1)
        self.MOD = MOD

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

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


n, k = list(map(int, input().split()))
mod = 998244353
bit = BIT(n + 2, mod)
ranges = []
for _ in range(k):
    l, r = list(map(int, input().split()))
    ranges.append((l, r))

bit.add(1, 1)

for i in range(1, n):
    v = bit.sum(i)
    for l, r in ranges:
        bit.add(i + l, v)
        bit.add(min(n + 1, i + r + 1), -v)
print(((bit.sum(n) - bit.sum(n - 1)) % mod))


# Optimized solution
class BIT:
    def __init__(self, n, MOD):
        self.n = n
        self.data = [0] * (n + 1)
        self.MOD = MOD

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

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

    def diff(self, i, j):
        s = self.sum(j) - self.sum(i)
        s %= self.MOD
        return s


n, k = list(map(int, input().split()))
mod = 998244353
bit = BIT(n + 2, mod)
ranges = []
for _ in range(k):
    l, r = list(map(int, input().split()))
    ranges.append((l, r))

bit.add(1, 1)

for i in range(1, n):
    v = bit.sum(i)
    for l, r in ranges:
        bit.add(i + l, v)
        bit.add(min(n + 1, i + r + 1), -v)
print((bit.diff(n - 1, n)))
# Original solution
N, K = list(map(int, input().split()))
MOD = 998244353

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

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

# 区間の合計を複数回求める＝累積和
# 累積和を作りながらDPをする
for i in range(2, N+1):
    # マスiに移動できる数を求める
    for l, r in lr:
        # iの左側からiへ移動できる区間を求めるので、
        # lとrは逆になる
        li = max(i-r, 1)
        ri = i-l

        # 右のマスが0以下なら移動できないので次へ
        if li < 1:
            continue

        dp[i] += dpsum[ri]-dpsum[li-1]
        dp[i] %= MOD
    dpsum[i] = dpsum[i-1]+dp[i]
print((dp[N]))


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

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

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

# 区間の合計を複数回求める＝累積和
# 累積和を作りながらDPをする
for i in range(2, N+1):
    # マスiに移動できる数を求める
    for l, r in lr:
        # iの左側からiへ移動できる区間を求めるので、
        # lとrは逆になる
        li = max(i-r, 1)
        ri = i-l

        # 右のマスが0以下なら移動できないので次へ
        if ri < 1:
            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
N,K=list(map(int,input().split()))

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

#A1～Aiまでの和 O(logN)
def BIT_query(idx):
  res_sum = 0
  while idx > 0:
    res_sum += BIT[idx]
    idx -= idx&(-idx)
  return res_sum
#Ai += x O(logN)
def BIT_update(idx,x):
  while idx <= N:
    BIT[idx] += x
    idx += idx&(-idx)
  return  

#初期化
BIT=[0]*(N+1)
BIT_update(1,1)

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

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

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

#A1～Aiまでの和 O(logN)
def BIT_query(idx):
  res_sum = 0
  while idx > 0:
    res_sum += BIT[idx]
    idx -= idx&(-idx)
  return res_sum
#Ai += x O(logN)
def BIT_update(idx,x):
  while idx <= N:
    BIT[idx] += x
    idx += idx&(-idx)
  return  

#初期化
BIT=[0]*(N+1)
BIT_update(1,1)

for i in range(2,N+1):
  for l,r in lrlist:
    left=i-r
    right=i-l    
    if right<1:
      continue
    elif left<1:
      left=1
    
    sum_intv=BIT_query(right)-BIT_query(left-1)
    BIT_update(i,sum_intv)
    
  nomod=BIT_query(i)-BIT_query(i-1)
  BIT_update(i,nomod%MOD-nomod)
    
print((BIT_query(N)-BIT_query(N-1)))
# Original solution
N, K = list(map(int,input().split()))
LR = [tuple(map(int,input().split())) for _ in range(K)]
d = [0]*N
ans = [0]*N
ans[0] = 1
MOD = 998244353
for i in range(N):
    x = ans[i]
    for k in range(K):
        L, R = LR[k]
        if i+L < len(d):
            d[i+L] += x
            d[i+L] %= MOD
        if i+R+1 < len(d):
            d[i+R+1] -= x
            d[i+R+1] %= MOD
    for j in range(i+2, len(d)):
        d[j] += d[j-1]
        d[j] %= MOD
    for j in range(len(d)):
        ans[j] = (ans[j]+d[j]) % MOD
        d[j] = 0
print((ans[-1] % MOD))

# Optimized solution
N, K = list(map(int,input().split()))
LR = [tuple(map(int,input().split())) for _ in range(K)]
d = [0]*N
d[0] = 1
MOD = 998244353
for i in range(N-1):
    x = d[i]
    d[0] = 0
    for k in range(K):
        L, R = LR[k]
        if i+L < len(d):
            d[i+L] += x
            d[i+L] %= MOD
        if i+R+1 < len(d):
            d[i+R+1] -= x
            d[i+R+1] %= MOD
    d[i+1] += d[i]
    d[i+1] %= MOD
print((d[-1] % MOD))
# Original solution
MOD = 998244353

N, K = list(map(int,input().split()))
S = []
for _ in range(K):
    L, R = list(map(int,input().split()))
    for i in range(L,R+1):
        if i not in S:
            S.append(i)

# dp[i]: マスiに移動する方法
dp = [0] * 200010
dp[0] = 1

for i in range(N):
    for d in S:
        if i+d < N:
            dp[i+d] += dp[i]
            dp[i+d] %= MOD

print((dp[N-1]))


# Optimized solution
MOD = 998244353

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

# dp[i]: マスiに移動する方法
dp = [0] * 200010
dp[0] = 1

for i in range(N):
    for l, r in LR:
        if i+l < N:
            dp[i+l] += dp[i]
            dp[i+l] %= MOD
        if i+r < N:
            dp[i+r+1] -= dp[i]
            dp[i+r+1] %= MOD
    if i>=1:
        dp[i+1] += dp[i]
        dp[i+1] %= MOD

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

def solve():
    MOD = 998244353

    def makeBIT(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        data = [0] * (numPow2+1)
        return data, numPow2
    def setInit(As):
        for iB, A in enumerate(As, 1):
            data[iB] = A
        for iB in range(1, numPow2):
            i = iB + (iB & -iB)
            data[i] += data[iB]
    def addValue(iA, A):
        iB = iA + 1
        while iB <= numPow2:
            data[iB] += A
            iB += iB & -iB
    def getSum(iA):
        iB = iA + 1
        ans = 0
        while iB > 0:
            ans += data[iB]
            iB -= iB & -iB
        return ans
    def getRangeSum(iFr, iTo):
        return getSum(iTo) - getSum(iFr-1)


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

    data, numPow2 = makeBIT(N)

    addValue(0, 1)

    for i in range(1, N):
        for L, R in LRs:
            x, y = i-R, i-L
            if y < 0:
                continue
            if x < 0:
                x = 0
            v = getRangeSum(x, y)
            addValue(i, v)

    ans = getRangeSum(N-1, N-1) % MOD
    print(ans)


solve()


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

def solve():
    MOD = 998244353

    def makeBIT(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        data = [0] * (numPow2+1)
        return data, numPow2
    def setInit(As):
        for iB, A in enumerate(As, 1):
            data[iB] = A
        for iB in range(1, numPow2):
            i = iB + (iB & -iB)
            data[i] += data[iB]
    def addValue(iA, A):
        iB = iA + 1
        while iB <= numPow2:
            data[iB] += A
            iB += iB & -iB
    def getSum(iA):
        iB = iA + 1
        ans = 0
        while iB > 0:
            ans += data[iB]
            iB -= iB & -iB
        return ans
    def getRangeSum(iFr, iTo):
        return getSum(iTo) - getSum(iFr-1)


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

    data, numPow2 = makeBIT(N)

    addValue(0, 1)

    for i in range(1, N):
        v = 0
        for L, R in LRs:
            x, y = i-R, i-L
            if y < 0:
                continue
            if x < 0:
                x = 0
            v += getRangeSum(x, y) % MOD
            v %= MOD
        addValue(i, v)

    ans = getRangeSum(N-1, N-1) % MOD
    print(ans)


solve()
# Original solution
MOD = 998244353


def main():
    from bisect import bisect_left
    N, K = (int(i) for i in input().split())
    S = set()
    for _ in range(K):
        le, ri = (int(i) for i in input().split())
        for i in range(le, ri+1):
            S.add(i)

    A = sorted(S)
    memo = [0] * (N+1)
    memo[0] = 1

    def dfs(N):
        if N < 0:
            return 0
        if memo[N] != 0:
            return memo[N]
        ret = 0
        idx = bisect_left(A, N)
        for i in A[idx::-1]:
            ret += dfs(N - i)
            ret %= MOD
        memo[N] = ret
        return ret

    print((dfs(N-1)))
    # print(memo, A)


if __name__ == '__main__':
    main()


# Optimized solution
MOD = 998244353


def main():
    N, K = (int(i) for i in input().split())
    LR = [[int(i) for i in input().split()] for j in range(K)]

    dp = [0] * (N+2)
    dp[1] = 1
    dp[2] = -1
    for i in range(1, N+1):
        for le, ri in LR:
            if i+le <= N:
                dp[i+le] += dp[i]
                dp[i+le] %= MOD
            if i+ri+1 <= N:
                dp[i+ri+1] -= dp[i]
                dp[i+ri+1] %= MOD
        dp[i+1] += dp[i]
        dp[i+1] %= MOD
    print((dp[N]))


if __name__ == '__main__':
    main()
# Original solution
MOD = 998244353


def main():
    N, K = (int(i) for i in input().split())
    LR = [[int(i) for i in input().split()] for j in range(K)]

    dp = [0] * (N+2)
    dp[1] = 1
    dp[2] = -1
    for i in range(1, N+1):
        for le, ri in LR:
            if i+le <= N:
                dp[i+le] += dp[i]
                dp[i+le] %= MOD
            if i+ri+1 <= N:
                dp[i+ri+1] -= dp[i]
                dp[i+ri+1] %= MOD
        dp[i+1] += dp[i]
        dp[i+1] %= MOD
    print((dp[N]))


if __name__ == '__main__':
    main()


# Optimized solution
MOD = 998244353


def main():
    # 配るdp + imos法
    N, K = (int(i) for i in input().split())
    LR = [[int(i) for i in input().split()] for j in range(K)]

    dp = [0] * (N+2)
    dp[1] = 1
    dp[2] = -1
    for i in range(1, N+1):
        for le, ri in LR:
            if i+le <= N:
                dp[i+le] += dp[i]
                dp[i+le] %= MOD
            if i+ri+1 <= N:
                dp[i+ri+1] -= dp[i]
                dp[i+ri+1] %= MOD
        dp[i+1] += dp[i]
        dp[i+1] %= MOD
    print((dp[N]))


if __name__ == '__main__':
    main()
# Original solution
n, k = list(map(int, input().split()))
lr = []
for _ in range(k):
    l, r = list(map(int, input().split()))
    lr.append((l, r))
mod = 998244353
dp = [0]*(2*n+1)
dp[0] = 1
dp[1] = -1
now = 1
for i in range(n):
    for l, r in lr:
        dp[i+l] += now
        dp[i+r+1] -= now
    now += dp[i+1]
print((sum(dp[:n])%mod))

# Optimized solution
n, k = list(map(int, input().split()))
lr = []
for _ in range(k):
    l, r = list(map(int, input().split()))
    lr.append((l, r))
mod = 998244353
dp = [0]*(2*n+1)
dp[0] = 1
dp[1] = -1
now = 1
for i in range(n):
    for l, r in lr:
        dp[i+l] += now
        dp[i+r+1] -= now
    now += dp[i+1]
    now %= mod
ans = 0
for i in range(n):
    ans += dp[i]
    ans %= mod
print(ans)
# Original solution
n,k = list(map(int,input().split()))
ns = []
for i in range(k):
    l, r = list(map(int,input().split()))
    for k in range(l, r+1):
        ns.append(k)
arr = [0 for i in range(n)]
arr[0] = 1
for i in range(n):
    for j in ns:
        if i + j < n:
            arr[i + j] += arr[i]
print((arr[n-1] % 998244353))

# Optimized solution
MOD = 998244353
n,k = list(map(int,input().split()))
ns = [list(map(int,input().split())) for i in range(k)]
    
dp = [0 for j in range(n+1)]
cum = [0 for j in range(n+1)]
dp[1] = 1
cum[1] = 1
for i in range(2, n+1):
    for j in range(k):
        l, r = ns[j]
        if i - l >= 0:
            dp[i] += cum[i-l]
        if i - (r+1) >= 0:
            dp[i] -= cum[i-(r+1)]
    dp[i] = (dp[i] % MOD + MOD) % MOD
    cum[i] = (cum[i-1] + dp[i]) % MOD
print((dp[n]))
# Original solution
n, k = list(map(int, input().split()))
s = []
for i in range(k):
    l, r = list(map(int, input().split()))
    s += list(range(l, r+1))

mod = 998244353
dp = [0] * (n+1)
dp[1] = 1
s = sorted(s)
for i in range(1, n):
    dp[i] %= mod
    for add in s:
        if i+add <= n:
            dp[i+add] += dp[i]
print((dp[n] % mod))

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

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

dp[1] = 1
s = sorted(s)
counter = 0
for i in range(1, n+1):
    counter += cumsum[i]
    dp[i] += counter
    dp[i] %= mod
    for l, r in s:
        if i+l <= n:
            cumsum[i+l] += dp[i]
        if i+r+1 <= n:
            cumsum[i+r+1] -= dp[i]
print((dp[n] % mod))