AtCoder Beginner Contest 179 - Leaping Tak

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: MEDIUM

Starter code:

Solutions:
(n, k) = map(int, input().split())
ps = []
MOD = 998244353
s = set()
for _ in range(k):
	(l, r) = map(int, input().split())
	ps.append([l, r])
dp = [0] * (n + 1)
dp[0] = 1
acc = [0, 1]
for i in range(1, n):
	for (l, r) in ps:
		dp[i] += acc[max(0, i - l + 1)] - acc[max(0, i - r)]
	acc.append((acc[i] + dp[i]) % MOD)
print(dp[n - 1] % MOD)


(n, k) = map(int, input().split())
sec = []
for i in range(k):
	(l, r) = 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)


(n, k) = map(int, input().split())
mod = 998244353
list_s = []
for _ in range(k):
	(l, r) = map(int, input().split())
	list_s.append((l, r))
dp = [0] * (n + 1)
sdp = [0] * (n + 1)
dp[1] = 1
sdp[0] = 0
sdp[1] = 1
for i in range(2, n + 1):
	for (l, r) in list_s:
		dl = max(0, i - r - 1)
		dr = max(0, i - l)
		dp[i] += sdp[dr] - sdp[dl]
		sdp[i] = (sdp[i - 1] + dp[i]) % mod
print(dp[n] % mod)


(N, K) = map(int, input().split())
I = [0] * K
for m in range(K):
	(l, r) = map(int, input().split())
	I[m] = (l, r)
Mod = 998244353
DP = [0] * (N + 1)
DP[1] = 1
for x in range(2, N + 1):
	DP[x] = DP[x - 1]
	for (l, r) in I:
		a = max(0, x - r - 1)
		b = max(0, x - l)
		DP[x] += DP[b] - DP[a]
		DP[x] %= Mod
print((DP[N] - DP[N - 1]) % Mod)


MOD = 998244353
(N, K) = map(int, input().split())
segments = [tuple(map(int, input().split())) for _ in range(K)]
dp = [0] * (2 * N + 1)
for i in range(N):
	for (s, t) in segments:
		t += 1
		dp[i + s] += dp[i] if i != 0 else 1
		dp[i + t] -= dp[i] if i != 0 else 1
	dp[i + 1] += dp[i]
	dp[i + 1] %= MOD
print(dp[N - 1])


(n, k) = 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])


(N, k) = map(int, input().split())
dp = [0] * (N + 1)
dp[1] = 1
S = []
for i in range(k):
	S.append(list(map(int, input().split())))
for i in range(2, N + 1):
	for (l, r) in S:
		dp[i] += dp[max(i - l, 0)] - dp[max(i - r - 1, 0)]
	dp[i] += dp[i - 1]
	dp[i] %= 998244353
print((dp[N] - dp[N - 1]) % 998244353)


import sys
MOD = 998244353

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))
	K = int(next(tokens))
	L = [int()] * K
	R = [int()] * K
	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()


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
(n, k, *data) = list(map(int, read().split()))
mod = 998244353
dp = [0] * n
dp[0] = 1
route = 0
for j in range(1, n):
	for i in range(k):
		(l, r) = data[i * 2:i * 2 + 2]
		if j >= l:
			route += dp[j - l]
		if j > r:
			route -= dp[j - r - 1]
		route %= mod
	dp[j] += route
print(dp[-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)


def main():
	MOD = 998244353
	(n, k) = map(int, input().split())
	LR = []
	for _ in range(k):
		LR.append(tuple(map(int, input().split())))
	dp = [0] * (n + 1)
	dp[1] = 1
	for i in range(1, n):
		temp = 0
		for (l, r) in LR:
			ll = max(i + 1 - r - 1, 0)
			rr = max(i + 1 - l, 0)
			temp += dp[rr] - dp[ll]
		dp[i + 1] = (dp[i] + temp) % MOD
	print((dp[n] - dp[n - 1]) % MOD)
main()


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


(N, K) = map(int, input().split())
MOD = 998244353
lr = []
for _ in range(K):
	(l, r) = map(int, input().split())
	lr.append((l, r))
lr.sort()
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:
		lj = max(1, i - r)
		rj = i - l
		if rj < 1:
			continue
		dp[i] += dpsum[rj] - dpsum[lj - 1]
		dp[i] %= MOD
	dpsum[i] = dp[i] + dpsum[i - 1]
print(dp[N])


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


p = 998244353
(n, k) = map(int, input().split())
LR = []
for i in range(k):
	(Li, Ri) = map(int, input().split())
	LR.append([Li, Ri])
U = [0, 1]
cnt = [1]
for i in range(1, n):
	cnti = 0
	for (Li, Ri) in LR:
		scopeL = i - Ri
		scopeR = i - Li
		if scopeR >= 0:
			cnti += U[scopeR + 1] - U[max(0, scopeL)]
	cnt.append(cnti % p)
	U.append((U[i] + cnti) % p)
print(cnt[n - 1])


(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) = [int(x) for x in input().split()]
ranges = [tuple((int(x) for x in input().split())) for _ in range(K)]
ranges.sort()
p = 998244353
dpsum = [0] * (N + 1)
dpsum[1] = 1
for i in range(2, N + 1):
	dp = 0
	for (l, r) in ranges:
		rj = max(0, i - l)
		lj = max(1, i - r)
		dp += dpsum[rj] - dpsum[lj - 1]
		dp %= p
	dpsum[i] = dpsum[i - 1] + dp
	dpsum[i] %= p
print(dp)


(N, K) = map(int, input().split())
MOD = 998244353
LR = []
for _ in range(K):
	(L, R) = map(int, input().split())
	LR.append((L, R))
DP = [0] * (N + 1)
DP[1] = 1
S = [0] * (N + 1)
for i in range(1, len(DP)):
	for (L, R) in LR:
		v = S[max(i - L, 0)] - S[max(i - R - 1, 0)]
		DP[i] += v
	DP[i] %= MOD
	S[i] = (S[i - 1] + DP[i]) % MOD
print(DP[-1])


(n, k) = map(int, input().split())
arr = []
for _ in range(k):
	arr.append(list(map(int, input().split())))
pref = [0] * (n + 1)
dp = [0] * (n + 1)
dp[0] = 1
pref[0] = 1
for i in range(1, n):
	for j in range(k):
		if arr[j][1] <= i:
			dp[i] = (dp[i] + pref[i - arr[j][0]] - pref[i - arr[j][1] - 1]) % 998244353
		elif arr[j][0] <= i:
			dp[i] = (dp[i] + pref[i - arr[j][0]]) % 998244353
	pref[i] = (pref[i - 1] + dp[i]) % 998244353
print(dp[n - 1])


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


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) = map(int, input().split())
mod = 998244353
lr = []
for i in range(k):
	lr.append(list(map(int, input().split())))
d = [0] * (n + 1)
d[0] = 1
for i in range(n):
	for (l, r) in lr:
		r += 1
		d[min(n, i + l)] += d[i]
		d[min(n, i + r)] -= d[i]
	if i != 0:
		d[i + 1] += d[i]
	d[i + 1] %= mod
print(d[n - 1] % mod)


(N, K) = map(int, input().split())
LR = [list(map(int, input().split())) for k in range(K)]
dp = 3 * N * [0]
dp[0] = 1
dp[1] = -1
for n in range(N):
	for (L, R) in LR:
		dp[L + n] += dp[n]
		dp[n + R + 1] -= dp[n]
	dp[n + 1] = (dp[n] + dp[n + 1]) % 998244353
print(dp[N - 1])


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


p = 998244353
(n, k) = map(int, input().split())
kukan = []
for i in range(k):
	(l, r) = map(int, input().split())
	kukan.append((l, r))
dp = [0] * n
sdp = [0] * (n + 1)
dp[0] = 1
sdp[1] = 1
for i in range(1, n):
	for (l, r) in kukan:
		left = max(0, i - r)
		right = max(0, i - l + 1)
		dp[i] = (dp[i] + sdp[right] - sdp[left]) % p
	sdp[i + 1] = (sdp[i] + dp[i]) % p
print(dp[-1])


(N, K) = map(int, input().split())
S = [tuple(map(int, input().split())) for i in range(K)]
MOD = 998244353
dp = [1]
acc = [0, 1]
for i in range(1, N):
	c = 0
	for (lk, rk) in S:
		if i - lk < 0:
			continue
		c += acc[i - lk + 1] - acc[max(i - rk, 0)]
	c %= MOD
	dp.append(c)
	acc.append((acc[-1] + dp[-1]) % MOD)
print(dp[N - 1])


(N, K) = map(int, input().split())
X = [list(map(int, input().split())) for i in range(K)]
C = [0] * (N * 3)
DP = [0] * N
mod = 998244353
DP[0] = 1
Y = 0
for i in range(N):
	Y += C[i]
	DP[i] += Y
	Y %= mod
	DP[i] %= mod
	for j in range(K):
		C[i + X[j][0]] += DP[i]
		C[i + X[j][1] + 1] -= DP[i]
print(DP[N - 1])


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


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


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


(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())
LR = []
for _ in range(K):
	LR.append(list(map(int, input().split())))
MOD = 998244353
dp = [0] * (N + 1)
dp[0] = 1
for i in range(N):
	for (L, R) in LR:
		if i + L < N:
			dp[i + L] += dp[i]
		if i + R + 1 < N:
			dp[i + R + 1] -= dp[i]
	if i > 0:
		dp[i + 1] = (dp[i + 1] + dp[i]) % MOD
print(dp[-1])


(N, K) = map(int, input().split())
L_R = [list(map(int, input().split())) for _ in range(K)]
MOD = 998244353
L_R.sort()
f = [0] * N
f[0] = 1
a = [0] * (N + 1)
a[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])


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


import sys

def input():
	return sys.stdin.readline().strip()

def mapint():
	return map(int, input().split())
sys.setrecursionlimit(10 ** 9)
(N, K) = mapint()
dp = [0] * (N * 3 + 1)
dp[1] = 1
dp[2] = -1
mod = 998244353
LR = [list(mapint()) for _ in range(K)]
for i in range(1, N + 1):
	dp[i] = (dp[i] + dp[i - 1]) % mod
	for (l, r) in LR:
		dp[i + l] = (dp[i + l] + dp[i]) % mod
		dp[i + r + 1] = (dp[i + r + 1] - dp[i]) % mod
print(dp[N])


(N, K) = map(int, input().split())
L = []
R = []
for i in range(K):
	(l, r) = map(int, input().split())
	L.append(l)
	R.append(r)
dp = [0] * (N + 1)
dp[1] = 1
dpd = [0] * (N + 2)
dpd[2] = -1
for i in range(1, N):
	for j in range(K):
		dpd[min(i + L[j], N + 1)] += dp[i]
		dpd[min(i + R[j] + 1, N + 1)] -= dp[i]
	dp[i + 1] = (dp[i] + dpd[i + 1]) % 998244353
print(dp[N])


(N, K) = map(int, input().split())
LR = list((tuple(map(int, input().split())) for _ in range(K)))
S = [0] * (N + 1)
S[1] = 1
for k in range(2, N + 1):
	s = 0
	for (l, r) in LR:
		(p0, p1) = (max(k - r - 1, 0), max(k - l, 0))
		s += S[p1] - S[p0]
	S[k] = (S[k - 1] + s) % 998244353
print((S[-1] - S[-2]) % 998244353)


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


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


(N, K) = map(int, input().split())
dp = [0 for _ in range(3 * N)]
dp[0] = 1
S_left = []
S_right = []
for i in range(K):
	(l, r) = map(int, input().split())
	S_left.append(l)
	S_right.append(r)
plus = 0
for j in range(N):
	plus += dp[j]
	for k in range(K):
		dp[S_left[k] + j] += plus
		dp[S_left[k] + j] %= 998244353
		dp[S_right[k] + j + 1] -= plus
		dp[S_right[k] + j + 1] %= 998244353
dp_cum = [1]
print(dp[N - 1] % 998244353)


MOD = 998244353
(N, K) = map(int, input().split())
LR = [tuple(map(int, input().split())) for i in range(K)]
dp = [0] * (N + 1)
dp[1] = 1
for i in range(1, N):
	dp[i] += dp[i - 1]
	dp[i] %= MOD
	for (l, r) in LR:
		ll = i + l
		rr = i + r
		if ll <= N:
			dp[ll] += dp[i]
			dp[ll] %= MOD
		if rr < N:
			dp[rr + 1] -= dp[i]
			dp[rr + 1] %= MOD
print(dp[-1])


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


import sys
input = sys.stdin.readline
mod = 998244353
(n, k) = map(int, input().split())
arr = [list(map(int, input().split())) + [i] for i in range(k)]
dp = [0] * (n + 1)
dp[1] = 1
sums = [0] * k
for i in range(2, n + 1):
	for (l, r, j) in arr:
		if l > i:
			continue
		elif l <= i <= r:
			sums[j] += dp[i - l]
		else:
			sums[j] -= dp[i - r - 1]
			sums[j] += dp[i - l]
		sums[j] %= mod
	for j in range(k):
		dp[i] += sums[j]
print(dp[n] % mod)


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


MOD = 998244353
(N, K) = map(int, input().split())
seg = [tuple(map(int, input().split())) for _ in range(K)]
dp = [0] * (N + 1)
dp[0] = 1
for i in range(N):
	for (s, t) in seg:
		if i + s <= N:
			dp[i + s] += dp[i]
		if i + t + 1 <= N:
			dp[i + t + 1] -= dp[i]
	dp[0] = 0
	dp[i + 1] += dp[i]
	dp[i + 1] %= MOD
print(dp[N - 1])


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


(N, K) = map(int, input().split())
l = []
mod = 998244353
for i in range(K):
	(L, R) = map(int, input().split())
	l.append([L, R])
l.sort()
a = [0 for i in range(N + 1)]
a[1] = 1
b = [0 for i in range(N + 1)]
b[1] = 1
for i in range(2, N + 1):
	for j in range(K):
		if l[j][0] < i:
			a[i] += (b[i - l[j][0]] - b[max(0, i - l[j][1] - 1)]) % mod
		else:
			break
	b[i] = (b[i - 1] + a[i]) % mod
mod = 998244353
print(a[N] % mod)


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


MOD = 998244353
(N, K) = list(map(int, input().split()))
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, *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])


MOD = 998244353
(n, k) = map(int, input().split())
left = []
right = []
for _ in range(k):
	(l, r) = map(int, input().split())
	left += [l]
	right += [r]
pref = [0, 1]
for i in range(n - 1):
	new = 0
	for j in range(k):
		new += pref[max(0, i + 2 - left[j])] - pref[max(0, i + 1 - right[j])]
	pref.append((pref[-1] + new) % MOD)
print(new % MOD)


mod = 998244353
(n, k) = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(k)]
DP = [0 for _ in range(n + 1)]
SDP = [0 for _ in range(n + 1)]
DP[1] = 1
SDP[1] = 1
for i in range(2, n + 1):
	for (l, r) in LR:
		DP[i] += (SDP[max(i - l, 0)] - SDP[max(i - r, 1) - 1]) % mod
		DP[i] %= mod
	SDP[i] = (SDP[i - 1] + DP[i]) % mod
print(DP[n])


(n, k) = 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)


MOD = 998244353
(n, k) = map(int, input().split())
seg = [list(map(int, input().split())) for _ in range(k)]
dp = [0 for _ in range(n + 1)]
dp[1] = 1
cum = [0 for _ in range(n + 1)]
cum[1] = 1
for i in range(2, n + 1):
	for (l, r) in seg:
		(r, l) = (max(i - l, 0), max(i - r - 1, 0))
		dp[i] += cum[r] - cum[l]
		dp[i] %= MOD
	cum[i] = cum[i - 1] + dp[i]
	cum[i] %= MOD
print(dp[n])


P = 998244353
(N, K) = [int(x) for x in input().split()]
intervals = []
for _ in range(K):
	(L, R) = [int(x) for x in input().split()]
	intervals.append([L, R])
dp = [0] * (N + 1)
csum = [0] * (N + 1)
dp[1] = 1
csum[1] = 1
for i in range(2, N + 1):
	for j in range(K):
		(L, R) = intervals[j]
		dp[i] = (dp[i] + csum[max(0, i - L)] - csum[max(0, i - R - 1)]) % P
	csum[i] = (csum[i - 1] + dp[i]) % P
ans = dp[N]
print(ans)


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


(N, K) = map(int, input().split())
LRs = []
P = 998244353
for _ in range(K):
	(l, r) = map(int, input().split())
	LRs.append((l, r))
memo = [0] * (N + 2)
memo[1] = 1
memo[2] = -1
rlt = [0] * (N + 2)
rlt[1] = 1
for i in range(1, N + 1):
	for t in LRs:
		l = min(t[0] + i, N + 1)
		r = min(t[1] + i + 1, N + 1)
		memo[l] = memo[l] + rlt[i]
		memo[r] = memo[r] - rlt[i]
	rlt[i + 1] = (rlt[i] + memo[i + 1]) % P
print(rlt[N])


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())
mod = 998244353
(l, r) = ([0] * k, [0] * k)
for i in range(k):
	(ll, rr) = 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])


(N, K) = map(int, input().split())
L = [0] * K
R = [0] * K
for i in range(K):
	(L[i], R[i]) = map(int, input().split())
	R[i] += 1
M = 998244353
T = [0] * N
T[0] = 1
s = 0
for i in range(N):
	s += T[i]
	for j in range(K):
		if i + L[j] < N:
			T[i + L[j]] += s
			T[i + L[j]] %= M
		if i + R[j] < N:
			T[i + R[j]] -= s
			T[i + R[j]] %= M
print(T[-1])


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())
dp = [0 for i in range(n + 1)]
acc = [0 for i in range(n + 1)]
dp[1] = 1
mod = 998244353
acc[1] = 1
(l, r) = ([], [])
for i in range(k):
	(a, b) = map(int, input().split())
	l.append(a)
	r.append(b)
for i in range(2, n + 1):
	for j in range(k):
		if i - l[j] < 0:
			continue
		dp[i] += acc[i - l[j]] - acc[max(0, i - r[j] - 1)]
		dp[i] %= mod
	acc[i] = (acc[i - 1] + dp[i]) % mod
print(dp[-1])


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


mod = 998244353
(N, K) = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(K)]
D.sort()
dp = [0] * N
dp[0] = 1
if D[0][0] < N:
	dp[D[0][0]] = 1
	for n in range(D[0][0], N - 1):
		dp[n + 1] = dp[n]
		for i in range(K):
			(L, R) = D[i]
			if n - L + 1 >= 0:
				dp[n + 1] += dp[n - L + 1]
			if n - R + 1 > 0:
				dp[n + 1] -= dp[n - R]
			dp[n + 1] %= mod
print(dp[N - 1])


M = 998244353
f = lambda : [*map(int, input().split())]
(n, k) = f()
lr = [f() for _ in range(k)]
dp = [0] * n
dp[0] = 1
S = [0]
for i in range(1, n):
	S += [S[-1] + dp[i - 1]]
	for (l, r) in lr:
		dp[i] += S[max(i - l + 1, 0)] - S[max(i - r, 0)]
	dp[i] %= M
print(dp[-1])


(N, K) = map(int, input().split())
X = [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):
	for (l, r) in X:
		dp[i] += sdp[max(0, i - l + 1)] - sdp[max(0, i - r)]
		dp[i] %= MOD
	sdp[i + 1] = sdp[i] + dp[i]
	sdp[i + 1] %= MOD
print(dp[-1])


(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:
		if i - s[0] > 0:
			end = max([i - s[1], 0])
			rui += (dp[i - s[0]] - dp[end - 1]) % 998244353
	dp[i] = (dp[i - 1] + rui) % 998244353
print((dp[N] - dp[N - 1]) % 998244353)


(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):
	if i == 1:
		d[i] = 1
		acc[0] = 0
		acc[i] = 1
	else:
		d[i] = 0
		for (l, r) in S:
			d[i] += get_acc_num(i, l, r) % MOD
			acc[i] = (acc[i - 1] + d[i]) % MOD
print(d[N] % 998244353)


(n, K) = [int(a) for a in input().split()]
s = [[int(a) for a in input().split()] for _ in range(K)]
MOD = 998244353
dp = [0] * (n + 1)
dp_sum = [0] * (n + 1)
dp[1] = 1
for i in range(1, n + 1):
	for (l, r) in s:
		dp[i] += dp_sum[i - l if i - l > 0 else 0] - dp_sum[i - r - 1 if i - r - 1 > 0 else 0]
		dp_sum[i] = (dp[i] + dp_sum[i - 1]) % MOD
print(dp[n] % MOD)


(n, k) = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(k)]
MOD = 998244353
dp = [0] * n
dp[0] = 1
ruidp = [0] * (n + 1)
ruidp[1] = 1
for i in range(n):
	for (l, r) in LR:
		dp[i] += ruidp[max(i - l + 1, 0)] - ruidp[max(i - r, 0)]
		dp[i] %= MOD
	ruidp[i + 1] = ruidp[i] + dp[i]
	ruidp[i + 1] %= MOD
print(dp[-1])


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


(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())
T = []
mod = 998244353
for i in range(K):
	(L, R) = map(int, input().split())
	T.append([L, R])
dp = [0] * (N + 1)
dp[1] = 1
Total = [0] * (N + 1)
Total[1] = 1
for i in range(2, N + 1):
	for j in range(K):
		(L, R) = T[j]
		dp[i] += Total[max(0, i - L)] - Total[max(0, i - R - 1)]
	dp[i] %= mod
	Total[i] = Total[i - 1] + dp[i]
	Total[i] %= mod
print(dp[N])


p = 998244353
(n, k) = map(int, input().split())
LRs = [tuple(map(int, input().split())) for _ in range(k)]
A = [0] * (2 * n + 1)
for (lj, rj) in LRs:
	A[lj] += 1
	A[rj + 1] -= 1
s = 0
for i in range(1, n):
	s = (s + A[i]) % p
	for (lj, rj) in LRs:
		A[i + lj] += s
		A[i + rj + 1] -= s
print(s)


P = 998244353
(N, K) = 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)


(N, K) = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(K)]
LR = sorted(LR)
MOD = 998244353
dp = [0] * (N + 1)
dp[1] = 1
for i in range(1, N):
	dp[i] %= MOD
	for (l, r) in LR:
		if i + l <= N:
			dp[i + l] += dp[i]
		if i + r + 1 <= N:
			dp[i + r + 1] -= dp[i]
	if i != 1:
		dp[i + 1] += dp[i]
print(dp[-1] % MOD)


mod = 998244353
(n, k) = map(int, input().split())
K = [list(map(int, input().split())) for i in range(k)]
dp = [0] * (n + 5)
dp[1] = 1
dp2 = [0] * (n + 5)
for i in range(1, n + 1):
	dp[i] = (dp[i] + dp2[i] + dp2[i - 1]) % mod
	dp2[i] = (dp2[i] + dp2[i - 1]) % mod
	for (l, r) in K:
		dp2[min(i + l, n + 2)] += dp[i]
		dp2[min(i + l, n + 2)] %= mod
		dp2[min(i + r + 1, n + 2)] -= dp[i]
		dp2[min(i + r + 1, n + 2)] %= mod
print(dp[n] % 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])


(n, k) = map(int, input().split())
dp = [0] * (n + 1)
dp[1] = 1
rui = [0] * (n + 1)
rui[1] = 1
p = 998244353
lr = []
for i in range(k):
	lr.append(list(map(int, input().split())))
for i in range(2, n + 1):
	for (l, r) in lr:
		dp[i] += rui[max(i - l, 0)] - rui[max(i - r - 1, 0)]
		dp[i] %= p
	rui[i] = rui[i - 1] + dp[i]
	rui[i] %= p
print(dp[n])


MOD = 998244353
(N, K) = map(int, input().split())
l = []
dp = [0] * N
sdp = [0] * (N + 1)
for i in range(K):
	(L, R) = map(int, input().split())
	l.append([L, R])
dp[0] = 1
sdp[1] = 1
for i in range(1, N):
	for (L, R) in l:
		dp[i] += sdp[max(0, i - L + 1)] - sdp[max(0, i - R)]
		dp[i] %= MOD
	sdp[i + 1] = sdp[i] + dp[i]
	sdp[i + 1] %= MOD
print(dp[N - 1])


(N, K) = map(int, input().split())
LRs = [tuple(map(int, input().split())) for _ in range(K)]
MOD = 998244353
dp = [0] * (N + 1)
dp_csum = [0] * (N + 2)
dp[1] = 1
dp_csum[2] = 1
for i in range(2, N + 1):
	for (L, R) in LRs:
		dp[i] += dp_csum[max(0, i - L + 1)] - dp_csum[max(0, i - R)]
		dp[i] %= MOD
	dp_csum[i + 1] = dp_csum[i] + dp[i]
	dp_csum[i + 1] %= MOD
print(dp[N])


(n, k) = map(int, input().split())
lst = [list(map(int, input().split())) for i in range(k)]
mod = 998244353
dp = [1]
imos = [0] * (2 * n + 10)
imos[0] = 1
imos[1] = -1
for i in range(n):
	for (l, r) in lst:
		imos[i + l] += dp[-1]
		imos[i + r + 1] -= dp[-1]
	dp.append((dp[-1] + imos[i + 1]) % mod)
print(dp[n - 1])


(N, K) = map(int, input().split())
P = 998244353
S = [tuple(map(int, input().split())) for _ in range(K)]
f = [0] * 10 ** 6
f[0] = 1
for i in range(N):
	for (l, r) in S:
		f[i + l] += f[i]
		f[i + l] %= P
		f[i + r + 1] -= f[i]
		f[i + r + 1] %= P
	if i:
		f[i + 1] += f[i]
	f[i] %= P
print(f[N - 1])


(n, k) = map(int, input().split())
MOD = 998244353
a = [list(map(int, input().split())) for _ in range(k)]
dp = [0] * (n + 1)
dp[0] = 0
dp[1] = 1
for i in range(2, n + 1):
	dp[i] = dp[i - 1]
	for (x, y) in a:
		l = i - y
		r = i - x
		l = max(l, 0)
		r = min(r, i - 1)
		dp[i] = (dp[i] + (dp[r] - (dp[l - 1] if l > 0 else 0))) % MOD
print((dp[-1] - dp[-2] + MOD) % MOD)


(n, k) = map(int, input().split())
kkn = [list(map(int, input().split())) for _ in range(k)]
MOD = 998244353
dp = [0] * (n + 1)
dp[1] = 1
dpac = [0] * (n + 1)
dpac[1] = 1
for i in range(2, n + 1):
	for (kl, kr) in kkn:
		l = i - kr
		r = i - kl
		if r < 0:
			continue
		l = max(l, 0)
		dp[i] += dpac[r] - dpac[l - 1]
		dp[i] %= MOD
	dpac[i] = dpac[i - 1] + dp[i]
	dpac[i] %= MOD
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])


from collections import defaultdict
dp = defaultdict(int)
(mod1, mod2) = (10 ** 9 + 7, 998244353)
mod = mod2
(n, k) = map(int, input().split())
f = 0
dp[1] = 1
ls = [tuple(map(int, input().split())) for i in range(k)]
for i in range(1, 1 + n):
	for (r, l) in ls:
		f = (f + -dp[i - 1 - l] + dp[i - r]) % mod
	dp[i] = (dp[i] + f) % mod
print(dp[n])


(n, k) = map(int, input().split())
l = []
mod = 998244353
for i in range(k):
	l.append(tuple(map(int, input().split())))
s = [0, 1]
for i in range(1, n):
	t = 0
	for j in range(k):
		t += s[max(0, i - l[j][0] + 1)] - s[max(0, i - l[j][1])]
	s.append((s[-1] + t) % mod)
print(t % mod)


mod = 998244353
N = int(1000000.0)
(n, k) = map(int, input().split())
seg = []
for i in range(k):
	seg.append(tuple(map(int, input().split())))
pref = [1] + [0] * N
for i in range(1, n):
	pref[i] += pref[i - 1]
	for (x, y) in seg:
		pref[i] += pref[i - x] - pref[i - y - 1] + mod
	pref[i] %= mod
print((pref[n - 1] - pref[n - 2] + mod) % mod)


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


(n, k) = map(int, input().split())
lr = []
for _ in range(k):
	(l, r) = 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 - 1):
	for (l, r) in lr:
		dp[i + l] += now
		dp[i + r + 1] -= now
	now += dp[i + 1]
	now %= mod
print(now)


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


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


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)


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


P = 998244353
(N, K) = map(int, input().split())
X = []
for _ in range(K):
	(l, r) = map(int, input().split())
	X.append((l - 1, r))
A = [1] + [0] * N
S = [0, 1] + [0] * N
for i in range(1, N):
	for (l, r) in X:
		A[i] += S[max(i - l, 0)] - S[max(i - r, 0)]
		A[i] %= P
	S[i + 1] = (S[i] + A[i]) % P
print(A[N - 1])


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


import sys
input = sys.stdin.readline
(inp, ip) = (lambda : int(input()), lambda : [int(w) for w in input().split()])
M = 998244353
(n, k) = ip()
seg = [ip() for i in range(k)]
dp = [0] * (n + 1)
pre = [0] * (n + 1)
dp[1] = 1
pre[1] = 1
for i in range(2, n + 1):
	for (l, r) in seg:
		(a, b) = (max(i - r, 1), i - l)
		dp[i] += (pre[b] - pre[a - 1]) % M
	pre[i] += (pre[i - 1] + dp[i]) % M
print(dp[n] % M)


(n, k) = map(int, input().split())
l = [list(map(int, input().split())) for i in range(k)]
x = [0] * (n + 1)
x[0] = 1
l.sort()
t = 0
for i in range(1, n + 1):
	for j in range(k):
		if i - l[j][1] > 0:
			t += x[i - l[j][0]] - x[i - l[j][1] - 1]
		elif i - l[j][0] >= 0:
			t += x[i - l[j][0]]
		t = t % 998244353
		x[i] = t
print(x[n - 1])


(n, k) = map(int, input().split())
m = 998244353
a = []
for i in range(k):
	a.append(list(map(int, input().split())))
b = [0] * n
b.append(1)
c = [0] * n
c.append(1)
for i in range(1, n):
	d = 0
	for j in range(k):
		d = (d + c[n + i - a[j][0]] - c[n + i - a[j][1] - 1]) % m
	b.append(d)
	c.append(c[-1] + d)
print(b[-1] % m)


(N, K) = map(int, input().split())
MOD = 998244353
dp = [0] * (N + 1)
LR = []
for _ in range(K):
	(l, r) = map(int, input().split())
	LR.append((l, r))
LR.sort()
dp[1] = 1
dp_sum = [0] * (N + 1)
dp_sum[1] = 1
for i in range(2, N + 1):
	for (l, r) in LR:
		if i - l >= 1:
			dp[i] += dp_sum[i - l] - dp_sum[max(0, i - r - 1)]
			dp[i] %= MOD
	dp[i] %= MOD
	dp_sum[i] = dp_sum[i - 1] + dp[i]
print(dp[N] % MOD)


(N, K) = map(int, input().split())
mod = 998244353
LR = []
for _ in range(K):
	LR.append(list(map(int, input().split())))
step = [0 for _ in range(N)]
step[0] = 1
step[1] = -1
answer = 0
for i in range(N):
	answer = (answer + step[i]) % mod
	for (L, R) in LR:
		if i + L < N:
			step[i + L] += answer
		if i + R + 1 < N:
			step[i + R + 1] -= answer
print(answer % mod)


(n, k) = map(int, input().split())
lr = [list(map(int, input().split())) for _i in range(k)]
mod = 998244353
dp = [0] * (n + 1)
dp[1] = 1
for p in range(2, n + 1):
	for (i, j) in lr:
		dp[p] += dp[max(p - i, 0)] - dp[max(p - j - 1, 0)]
		dp[p] %= mod
	dp[p] += dp[p - 1]
print((dp[n] - dp[n - 1]) % mod)


from itertools import accumulate
(N, K) = map(int, input().split())
mod = 998244353
Move = [list(map(int, input().split())) for _ in range(K)]
DP = [0] * N
DP[0] = 1
DP[1] = -1
cnt = 0
for i in range(N):
	DP[i] += cnt
	DP[i] %= mod
	cnt = DP[i]
	for (l, r) in Move:
		if i + l < N:
			DP[i + l] += DP[i]
		if i + r + 1 < N:
			DP[i + r + 1] -= DP[i]
print(DP[-1])


(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)]
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
	S[i] = (S[i - 1] + DP[i]) % mod
print(DP[n])


import sys

def MI():
	return map(int, sys.stdin.readline().rstrip().split())
(N, K) = MI()
LR = [tuple(MI()) for i in range(K)]
mod = 998244353
dp = [0] * (N + 1)
dp[1] = 1
for i in range(2, N + 1):
	dp[i] = dp[i - 1]
	for j in range(K):
		(l, r) = LR[j]
		dp[i] += dp[max(i - l, 0)] - dp[max(i - r - 1, 0)]
		dp[i] %= mod
print((dp[N] - dp[N - 1]) % mod)


(n, k) = map(int, input().split())
L = []
R = []
h = [0, 1, -1] + [0] * 400010
M = 998244353
for i in range(k):
	(l, r) = map(int, input().split())
	L.append(l)
	R.append(r)
N = 0
for i in range(1, n):
	N = (N + h[i] + 100 * M) % M
	for j in range(k):
		h[L[j] + i] += N
		h[R[j] + i + 1] -= N
print((N + h[n] + 100 * M) % M)


mod = 998244353
(n, k) = map(int, input().split())
s = []
for _ in range(k):
	(l, r) = 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)


(N, K) = map(int, input().split())
d = [0] * 2 * K
for i in range(K):
	(d[2 * i], d[2 * i + 1]) = map(int, input().split())
a = [0] * (N + 1)
b = [0] * (N + 1)
a[1] = 1
b[1] = 1
for i in range(2, N + 1):
	t = 0
	for j in range(K):
		if i - d[2 * j] > 0:
			t += b[i - d[2 * j]]
		if i - d[2 * j + 1] - 1 > 0:
			t -= b[i - d[2 * j + 1] - 1]
	a[i] = t
	b[i] = (b[i - 1] + a[i]) % 998244353
print(a[N] % 998244353)


MOD = 998244353
(N, K) = map(int, input().split())
lr = []
for i in range(K):
	lr.append(list(map(int, input().split())))
dp = [0] * 10 ** 6
dp[0] = 1
dpcum = [0] * 10 ** 6
dpcum[0] = 1
for i in range(1, N + 1):
	for j in range(K):
		dp[i] += dpcum[max(-1, i - lr[j][0])] - dpcum[max(-1, i - lr[j][1] - 1)]
		dp[i] %= MOD
	dpcum[i] = (dpcum[i - 1] + dp[i]) % MOD
print(dp[N - 1])


(n, k) = map(int, input().split())
mod = 998244353
l = [0] * n
r = [0] * n
for i in range(k):
	(l[i], r[i]) = 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)


(n, k) = map(int, input().split())
div = 998244353
S = []
for i in range(k):
	S.append(tuple(map(int, input().split())))
dp = [0] * (2 * n)
wa = [0] * k
dp[n] = 1
for i in range(n + 1, 2 * n):
	for j in range(k):
		wa[j] += dp[i - S[j][0]] - dp[i - S[j][1] - 1]
		dp[i] += wa[j]
	dp[i] %= div
print(dp[-1])


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


p = 998244353
(n, k) = map(int, input().split())
num = [tuple(map(int, input().split())) for _ in range(k)]
dp = [0] * (2 * n + 1)
dp[0] = 1
dp[1] = -1
for i in range(n):
	for (l, r) in num:
		dp[i + l] += dp[i]
		dp[i + r + 1] -= dp[i]
	dp[i + 1] += dp[i]
	dp[i + 1] %= p
print(dp[n - 1])


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


(N, K) = map(int, input().split())
L = [0] * K
R = [0] * K
for i in range(K):
	(L[i], R[i]) = map(int, input().split())
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 = i - R[j]
		Ri = i - L[j]
		if Ri < 0:
			continue
		else:
			Li = max(Li, 1)
			dp[i] = (dp[i] + dpsum[Ri] - dpsum[Li - 1]) % MOD
	dpsum[i] = dpsum[i - 1] + dp[i]
print(dp[N])


mod = 998244353

def main():
	(n, k) = map(int, input().split())
	query = []
	for i in range(k):
		query.append(list(map(int, input().split())))
	dp = [0] * (n + 1)
	dp[1] = 1
	for i in range(2, n + 1):
		dp[i] += dp[i - 1]
		for lr in query:
			if i - lr[0] <= 0:
				continue
			else:
				dp[i] += dp[i - lr[0]] - dp[max(0, i - lr[1] - 1)]
				dp[i] %= mod
	print((dp[n] - dp[n - 1]) % mod)
main()


MOD = 998244353
inpl = lambda : tuple(map(int, input().split()))
(N, K) = inpl()
LR = [inpl() for _ in range(K)]
dp = [0] * N
c = 1
for i in range(N):
	c = (c + dp[i]) % MOD
	for (L, R) in LR:
		if i + L < N:
			dp[i + L] = (dp[i + L] + c) % MOD
			if i + R + 1 < N:
				dp[i + R + 1] = (dp[i + R + 1] - c) % MOD
print(dp[-1])


(N, K) = 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])


import sys, collections as cl, bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10 ** 9 + 7
Max = sys.maxsize

def l():
	return list(map(int, input().split()))

def m():
	return list(map(int, input().split()))

def onem():
	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):
	return ' '.join(map(str, x))

def max2(x):
	return max(list(map(max, x)))

def In(x, a):
	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
(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])


import sys
input = sys.stdin.readline
(n, k) = map(int, input().split())
l = [list(map(int, input().split())) for i in range(k)]
mod = 998244353
dp = [0] * n
dp[0] = 1
dp2 = [0, 1]
for i in range(1, n):
	for j in range(k):
		dp[i] += (dp2[max(i - l[j][0] + 1, 0)] - dp2[max(i - l[j][1], 0)]) % mod
	dp2.append((dp2[-1] + dp[i]) % mod)
print(dp[-1] % mod)


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


MOD = 998244353
(N, K) = map(int, input().split())
rl = [list(map(int, input().split())) for _ in range(K)]
dp = [0] * (N + 1)
sdp = [0] * (N + 1)
dp[1] = 1
sdp[1] = 1
for i in range(2, N + 1):
	for j in range(K):
		(l, r) = (rl[j][0], rl[j][1])
		tl = max(1, i - r)
		tr = max(0, i - l)
		dp[i] += sdp[tr] - sdp[tl - 1]
		dp[i] %= MOD
	sdp[i] += dp[i] + sdp[i - 1]
	sdp[i] %= MOD
print(dp[N])


(N, K) = list(map(int, input().split()))
p = 998244353
LR = []
for i in range(K):
	LR.append(list(map(int, input().split())))
T = [0] * (2 * N + 10)
T[1] = 1
S = [0] * (2 * N + 10)
S[1] = 1
S[2] = -1
for i in range(1, N):
	for j in range(K):
		(L, R) = LR[j]
		S[i + L] = S[i + L] + T[i]
		S[i + R + 1] = S[i + R + 1] - T[i]
	T[i + 1] = (T[i] + S[i + 1]) % p
print(T[N])


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


(N, K) = map(int, input().split())
S = []
for _ in range(K):
	S.append(list(map(int, input().split())))
mod = 998244353
dp = [0 for _ in range(2 * N + 1)]
dp[1] = 1
cum = [0 for _ in range(2 * N + 1)]
cum[1] = 1
for i in range(N):
	for (l, r) in S:
		dp[i + 1] += cum[i - l + 1] - cum[i - r]
		dp[i + 1] %= mod
	cum[i + 1] = cum[i] + dp[i + 1]
	cum[i + 1] %= mod
print(dp[N])


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


MOD = 998244353
(N, K) = map(int, input().split())
lr = [list(map(int, input().split())) for _ in range(K)]
lr.sort()
dp = [0] * (N + 1)
dp[1] = 1
dpsum = [0] * (N + 1)
dpsum[1] = 1
for i in range(2, N + 1):
	for (l, r) in lr:
		li = max(0, i - r)
		ri = i - l
		if ri < 0:
			continue
		dp[i] += dpsum[ri] - dpsum[li - 1]
		dp[i] %= MOD
	dpsum[i] += dp[i] + dpsum[i - 1]
	dpsum[i] %= MOD
print(dp[N])


(N, K) = map(int, input().split())
L = []
for _ in range(K):
	(l, r) = map(int, input().split())
	L.append((l, r))
DP = [0] * N
DP[0] = 1
con = [0] * (N + 1)
con[1] = 1
for i in range(1, N):
	s = 0
	for (l, r) in L:
		s += con[max(0, i - l + 1)] - con[max(0, i - r)]
	DP[i] = s
	con[i + 1] = (con[i] + DP[i]) % 998244353
print(DP[N - 1] % 998244353)


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


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


MOD = 998244353
(n, k) = map(int, input().split())
seg = [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 seg:
		s[i + 1] += (s[max(0, i - l + 1)] - s[max(0, i - r)]) % MOD
		s[i + 1] %= MOD
print((s[n] - s[n - 1]) % MOD)


(N, K) = map(int, input().split())
W = [0] * (N + 1)
W[1] = 1
R = []
for i in range(K):
	(l, r) = 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])


(N, K) = map(int, input().split())
MOD = 998244353
move = []
for _ in range(K):
	(L, R) = map(int, input().split())
	move.append((L, R))
dp = [0] * (N + 1)
dp[0] = 1
dp[1] = -1
for i in range(1, N + 1):
	dp[i] += dp[i - 1]
	for (l, r) in move:
		if i - l >= 0:
			dp[i] += dp[i - l]
		if i - r - 1 >= 0:
			dp[i] -= dp[i - r - 1]
	dp[i] %= MOD
print(dp[N - 1])


(N, K) = 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])


MOD = 998244353
(N, K) = [int(s) for s in input().split()]
ls = [0 for _ in range(N)]
lssum = [0 for _ in range(N)]
ls[0] = 1
lssum[0] = 1
sections = [[int(s) for s in input().split()] for _ in range(K)]
for i in range(1, N):
	for sec in sections:
		if sec[0] > i:
			continue
		else:
			l = sec[0]
			r = min([i, sec[1]])
			ls[i] = (ls[i] + lssum[i - l] - lssum[i - r - 1]) % MOD
	lssum[i] = (lssum[i - 1] + ls[i]) % MOD
print(ls[N - 1])


(N, K) = map(int, input().split())
MOD = 998244353
D = []
for _ in range(K):
	(l, r) = map(int, input().split())
	D.append((l, r))
imos = [0] * (N + 2)
dp = [0] * (N + 1)
imos[0] = 1
imos[1] = -1
for i in range(N):
	dp[i] = dp[i - 1] + imos[i]
	dp[i] %= MOD
	for (a, b) in D:
		imos[min(i + a, N + 1)] += dp[i]
		imos[min(i + b + 1, N + 1)] -= dp[i]
print(dp[N - 1])


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
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())
for j in range(N):
	m[j + 1] += m[j] % mod
	for i in range(K):
		m[j + L[i]] += m[j] % mod
		m[j + R[i] + 1] -= m[j] % mod
print(m[N - 1] % mod)


import sys
input = sys.stdin.readline
(N, K) = map(int, input().split())
K = [tuple(map(int, input().split())) for i in range(K)]
mod = 998244353
DP = [0] * (4 * 10 ** 5 + 100)
DP[1] = 1
DP[2] = -1
for i in range(1, N + 1):
	DP[i] += DP[i - 1]
	DP[i] %= mod
	for (l, r) in K:
		DP[i + l] += DP[i]
		DP[i + l] %= mod
		DP[i + r + 1] -= DP[i]
		DP[i + r + 1] %= mod
print(DP[N])


(n, k) = map(int, input().split())
LR = [tuple(map(int, input().split())) for _ in range(k)]
dp = [0 for _ in range(n + 1)]
dp[1] = 1
s = 0
mod = 998244353
for i in range(1, n + 1):
	s += dp[i]
	for (l, r) in LR:
		if i + l <= n:
			dp[i + l] = (dp[i + l] + s) % mod
			if i + r + 1 <= n:
				dp[i + r + 1] = (dp[i + r + 1] - s) % mod
print(dp[n])


(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] * 300000
dpsum = [0] * 300000
dp[1] = 1
dpsum[1] = 1
for i in range(2, N + 1):
	for j in range(K):
		li = min(L[j], i)
		ri = min(R[j], i + 1)
		dp[i] += dpsum[i - li] - dpsum[i - ri - 1]
	dp[i] %= 998244353
	dpsum[i] = dpsum[i - 1] + dp[i]
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) = 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)


(N, K) = map(int, input().split())
dp = [0] * N
dp[0] = 1
mod = 998244353
L = list()
for i in range(K):
	(a, b) = map(int, input().split())
	L.append([a, b])
R = [0, 1]
for i in range(1, N):
	for j in range(K):
		(a, b) = L[j]
		if i >= b:
			dp[i] += R[i - a + 1] - R[i - b]
		elif i >= a:
			dp[i] += R[i - a + 1]
		dp[i] %= mod
	R.append(R[-1] + dp[i])
print(dp[-1])


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


(n, k) = map(int, input().split())
s = [list(map(int, input().split())) for _ in range(k)]
dp = [0] * (n + 1)
dp[1] = 1
mod = 998244353
dpsum = [0] * (n + 1)
dpsum[1] = 1
for i in range(2, n + 1):
	for j in range(k):
		li = max(i - s[j][1], 1)
		ri = i - s[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])


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


import sys
MOD = 998244353

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)

def main():

	def iterate_tokens():
		for line in sys.stdin:
			for word in line.split():
				yield word
	tokens = iterate_tokens()
	N = int(next(tokens))
	K = int(next(tokens))
	L = [int()] * K
	R = [int()] * K
	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())
l = [0] * k
r = [0] * k
for j in range(k):
	(l[j], r[j]) = map(int, input().split())
p = 998244353
dp = [0] * (n + max(r) + 100)
dp[1] = 1
dp[2] = -1
for i in range(1, n + 1):
	dp[i] += dp[i - 1]
	dp[i] %= p
	for (lj, rj) in zip(l, r):
		dp[i + lj] += dp[i]
		dp[i + lj] %= p
		dp[i + rj + 1] -= dp[i]
		dp[i + rj + 1] %= p
print(dp[n])


(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
R = []
for _ in range(k):
	(l, r) = map(int, input().split())
	R.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 j in range(k):
		li = i - R[j][1]
		ri = i - R[j][0]
		if ri < 0:
			continue
		li = max(li, 1)
		dp[i] += (dpsum[ri] - dpsum[li - 1]) % mod
	dpsum[i] = dpsum[i - 1] + dp[i]
	dpsum[i] %= mod
print(dp[n] % mod)


(N, K) = map(int, input().split())
L = [0] * N
R = [0] * N
DP = [0] * (N + 10)
DP[0] = 1
SDP = [0] * (N + 10)
SDP[1] = 1
MOD = 998244353
for i in range(K):
	(L[i], R[i]) = map(int, input().split())
for i in range(1, N):
	for j in range(K):
		l = max(0, i - R[j])
		r = max(0, i - L[j] + 1)
		DP[i] += SDP[r] - SDP[l]
	SDP[i + 1] = (SDP[i] + DP[i]) % MOD
print(DP[N - 1] % MOD)


mod = 998244353
(N, K) = map(int, input().split())
O = []
for i in range(K):
	O.append(tuple(map(int, input().split())))
A = [0] * (N + 1)
A[0] = 1
B = [0] * (N + 1)
aaa = 0
for i in range(N):
	for (L, R) in O:
		if i + L < N:
			B[i + L] += A[i]
			if i + R < N:
				B[i + R + 1] -= A[i]
	aaa += B[i + 1]
	A[i + 1] = aaa % mod
print(A[N - 1])


import sys
from collections import deque, Counter, defaultdict
import bisect
import heapq
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)


mod = 998244353
(n, k) = map(int, input().split())
left = []
right = []
for _ in range(k):
	(l, r) = map(int, input().split())
	left.append(l)
	right.append(r)
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
	for j in range(k):
		dp[i] += dp[max(0, i - left[j])] - dp[max(0, i - right[j] - 1)]
		dp[i] %= mod
	dp[i] = (dp[i - 1] + dp[i]) % mod
print((dp[n] - dp[n - 1]) % mod)


(n, k) = map(int, input().split())
lis = [list(map(int, input().split())) for i in range(k)]
imos = [0] * (2 * n + 1)
imos[0] = 1
imos[1] = -1
ans = [1]
for i in range(n):
	for (x, y) in lis:
		imos[i + x] += ans[-1]
		imos[i + y + 1] -= ans[-1]
	ans.append((ans[-1] + imos[i + 1]) % 998244353)
print(ans[-2])


MOD = 998244353
(N, K) = map(int, input().split())
kukan = [list(map(int, input().split())) for _ in range(K)]
step = [0 for _ in range(K)]
ans = [0] * (2 * N)
ans[N] = 1
for i in range(N):
	for k in range(K):
		step[k] += ans[N + i - kukan[k][0]] - ans[N + i - kukan[k][1] - 1]
	ans[N + i] += sum(step) % MOD
print(ans[-1])


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


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


p = 998244353
(n, k) = map(int, input().split())
LR = [tuple(map(int, input().split())) for _ in range(k)]
DP = [0] * (2 * n + 1)
DP[0] = 1
DP[1] = -1
for i in range(n):
	for (l, r) in LR:
		DP[i + l] += DP[i]
		DP[i + r + 1] -= DP[i]
	DP[i + 1] += DP[i]
	DP[i + 1] %= p
print(DP[n - 1])


MOD = 998244353
(N, K) = map(int, input().split())
LRs = []
sums = []
for _ in range(K):
	(l, r) = map(int, input().split())
	LRs.append([l, r])
	sums.append(1 if l <= 1 <= r else 0)
dp = [0] * (N * 2)
dp[1] = 1
for i in range(2, N + 1):
	dp[i] = sum(sums) % MOD
	for k in range(K):
		(l, r) = LRs[k]
		sums[k] = (sums[k] + dp[i - l + 1] - dp[i - r]) % MOD
print(dp[N])


(N, K) = map(int, input().split())
DP = [0] * (N + 1)
DPsum = [0] * (N + 1)
DP[1] = 1
DPsum[1] = 1
lr = []
m = 998244353
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:
		lx = i - r - 1
		rx = i - l
		lx = max(0, lx)
		rx = max(0, rx)
		DP[i] += DPsum[rx] - DPsum[lx]
	DPsum[i] = (DPsum[i - 1] + DP[i]) % m
print(DP[N] % m)


(n, k) = map(int, input().split())
lr = [list(map(int, input().split())) for i in range(k)]
dp = [0 for i in range(n + 1)]
mod = 998244353
lr.sort()
a = [0] * (n + 1)
dp[0] = 1
a[0] = 1
for i in range(1, n + 1):
	for (l, r) in lr:
		if i - l < 0:
			continue
		elif i - l >= 0 and i - r - 1 < 0:
			dp[i] += a[i - l]
		else:
			dp[i] += a[i - l] - a[i - r - 1]
	dp[i] %= mod
	a[i] = a[i - 1] + dp[i]
	a[i] %= mod
print(dp[n - 1] % 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) = map(int, input().split())
LL = []
RR = []
mod = 998244353
for i in range(K):
	(L, R) = map(int, input().split())
	LL.append(L)
	RR.append(R + 1)
keep = 0
dp = [0] * 2 * N
dp[N] = 1
for i in range(1, N):
	for j in range(K):
		keep = (keep + dp[N + i - LL[j]] - dp[N + i - RR[j]]) % mod
	dp[N + i] = (dp[N + i] + keep) % mod
print(dp[2 * N - 1] % mod)


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


(N, K) = map(int, input().split())
S = [tuple(map(int, input().split())) for _ in range(K)]
MOD = 998244353
dp = [0] * N
dp[0] = 1
for i in range(N - 1):
	x = dp[i]
	dp[0] = 0
	for k in range(K):
		(l, r) = S[k]
		if i + l < N:
			dp[i + l] += x
			dp[i + l] %= MOD
		if i + r + 1 < N:
			dp[i + r + 1] -= x
			dp[i + r + 1] %= MOD
	dp[i + 1] += dp[i]
	dp[i + 1] %= MOD
print(dp[-1] % MOD)


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


((n, _), *s) = [[*map(int, t.split())] for t in open(0)]
d = [1, -1] + [0] * 2 * n
for i in range(n):
	d[i] = (d[i - 1] + d[i]) % 998244353
	for (l, r) in s:
		d[i + l] += d[i]
		d[i - ~r] -= d[i]
print(d[n - 1])


mod = 998244353
(N, K) = map(int, input().split())
S = []
for _ in range(K):
	S.append(list(map(int, input().split())))
L = [1]
SUM = [1]
for i in range(1, N):
	tmp = 0
	for j in range(K):
		if i - S[j][0] >= 0:
			tmp += SUM[i - S[j][0]]
		if i - S[j][1] - 1 >= 0:
			tmp -= SUM[i - S[j][1] - 1]
	L.append(tmp % mod)
	SUM.append((L[-1] + SUM[-1]) % mod)
print(L[-1])


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[-1])

def __starting_point():
	resolve()
__starting_point()


(n, k) = map(int, input().split())
st = []
for i in range(k):
	(x, y) = 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)


(n, k) = map(int, input().split())
B = [[0] * 2 for i in range(k)]
for i in range(k):
	B[i] = list(map(int, input().split()))
mod = 998244353
A = [0] * (n + 1)
A[0] = 1
a = 1
for i in range(n):
	for j in range(k):
		A[min(n, i + B[j][0])] = (A[min(n, i + B[j][0])] + a) % mod
		A[min(n, i + B[j][1] + 1)] = (A[min(n, i + B[j][1] + 1)] - a) % mod
	a = a + A[i + 1]
print(A[-2] % mod)


import sys
input = sys.stdin.readline
(N, K) = map(int, input().split())
LR = [tuple(map(int, input().split())) for i in range(K)]
MOD = 998244353
dp = [1]
cumdp = [0, 1]
for i in range(1, N):
	tmp = 0
	for (l, r) in LR:
		if i - l + 1 <= 0:
			continue
		tmp += cumdp[i - l + 1] - cumdp[max(0, i - r)]
	tmp %= MOD
	dp.append(tmp)
	cumdp.append((cumdp[-1] + tmp) % MOD)
print(dp[-1])


(N, K) = map(int, input().split())
S = [[int(s) for s in input().split()] for _ in range(K)]
mod = 998244353
dp = [0] * N
dp[0] = 1
if N > 2:
	dp[1] = -1
for i in range(N):
	if N > 2:
		dp[i] += dp[i - 1]
	dp[i] %= mod
	for s in S:
		if s[0] + i < N:
			dp[s[0] + i] += dp[i]
			dp[s[0] + i] %= mod
		if s[1] + i + 1 < N:
			dp[s[1] + i + 1] -= dp[i]
			dp[s[1] + i + 1] %= mod
print(dp[-1])


(N, K) = map(int, input().split())
L = [list(map(int, input().split())) for i in range(K)]
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):
	for array in L:
		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])


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)


(N, K) = map(int, input().split())
LR = [list(map(int, input().split())) for i in range(K)]
MOD = 998244353
dp = [0] * (N + 1)
dp[1] = 1
dp_sum = [0] * (N + 1)
dp_sum[1] = 1

def get(l, r, i):
	return dp_sum[max(i - l, 0)] - dp_sum[max(i - r - 1, 0)]
for i in range(1, N + 1):
	for (l, r) in LR:
		dp[i] += get(l, r, i) % MOD
	dp_sum[i] = (dp_sum[i - 1] + dp[i]) % MOD
print(dp[N] % MOD)


import sys
input = sys.stdin.readline
(N, K) = map(int, input().split())
MOD = 998244353
dp = [0 for _ in range(N + 1)]
dp[1] = 1
R = [tuple(map(int, input().split())) for _ in range(K)]
S = [0 for _ in range(K)]
for i in range(2, N + 1):
	s = 0
	for k in range(K):
		S[k] += dp[max(0, i - R[k][0])] - dp[max(0, i - R[k][1] - 1)]
		S[k] %= MOD
		s = (s + S[k]) % MOD
	dp[i] = s
print(dp[N])


import sys
input = sys.stdin.buffer.readline
(N, K) = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(K)]
mod = 998244353
dp = [0] * (N + 1)
tmp = 1
for i in range(N - 1):
	tmp = (tmp + dp[i]) % mod
	for (l, r) in LR:
		dp[min(i + l, N)] = (dp[min(i + l, N)] + tmp) % mod
		dp[min(i + r + 1, N)] = (dp[min(i + r + 1, N)] - tmp) % mod
print(dp[N - 1])


(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
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())
mod = 998244353
lr = [list(map(int, input().split())) for _ in range(K)]
dp = [0] * (N + 1)
tmp = 1
imos = [0] * (N + 1)
imos[0] = 0
for i in range(N):
	imos[i] += dp[i]
	if i != 0:
		tmp = imos[i] + tmp
	for k in range(K):
		(l, r) = lr[k]
		if l + i > N:
			continue
		dp[l + i] = (dp[l + i] + tmp) % mod
		dp[min(N, r + i + 1)] = (dp[min(N, r + i + 1)] - tmp) % mod
print(imos[N - 1] % mod)


(n, k) = map(int, input().split())
LR = [tuple(map(int, input().split())) for _ in range(k)]
mod = 998244353
dp = [1]
acc = [0, 1]
for i in range(1, n):
	new = 0
	for (l, r) in LR:
		if i < l:
			continue
		r = min(r, i)
		new += acc[i - l + 1] - acc[i - r]
		new %= mod
	dp.append(new)
	acc.append((acc[-1] + new) % mod)
print(dp[-1])


(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 + 5)
dp[1] = 1
for i in range(2, N + 1):
	dp[i] = dp[i - 1]
	for j in range(K):
		if i - L[j] >= 0:
			dp[i] += dp[i - L[j]]
		if i - R[j] - 1 >= 0:
			dp[i] -= dp[i - R[j] - 1]
		dp[i] %= 998244353
print((dp[N] - dp[N - 1]) % 998244353)


def solve(l, r, i):
	if i - l < 1:
		return 0
	return dp[i - l] - dp[max(i - r - 1, 0)]
(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
for i in range(2, n + 1):
	tmp = 0
	for (l, r) in lr:
		tmp += solve(l, r, i)
	tmp = tmp % MOD
	dp[i] = (dp[i - 1] + tmp) % MOD
print(tmp)


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


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


(N, K) = map(int, input().split())
LR = [list(map(int, input().split())) for i in range(K)]
LR.sort()
mod = 998244353
ma = [0] * N
ma[0] = 1
for i in range(N):
	if i > 1:
		ma[i] += ma[i - 1]
	p = ma[i] % mod
	if p != 0:
		for (l, r) in LR:
			if i + l < N:
				ma[i + l] += p
			else:
				break
			if i + r + 1 < N:
				ma[i + r + 1] -= p
print(ma[N - 1] % mod)


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


(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
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) = map(int, input().split())
s = []
mod = 998244353
for i in range(k):
	(l, r) = 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)


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


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())
ans = [0 for _ in range(n * 3)]
ans[1] = 1
idou = []
for _ in range(k):
	a = list(map(int, input().split()))
	idou.append(a)
mod = 998244353
rui = [0 for _ in range(n + 1)]
rui[1] = 1
for i in range(2, n + 1):
	for g in idou:
		(x, y) = g
		left = max(0, i - y - 1)
		right = max(0, i - x)
		ans[i] += (rui[right] - rui[left]) % mod
	rui[i] += (rui[i - 1] + ans[i]) % mod
print(ans[n] % mod)


(n, k) = 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) = 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)


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


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


(N, K) = map(int, input().split())
mod = 998244353
dp = [0] * N
dp[0] = 1
LR = [list(map(int, input().split())) for i in range(K)]
X = [0] * K
for i in range(1, N):
	for j in range(K):
		if i - LR[j][0] >= 0:
			X[j] += dp[i - LR[j][0]]
		if i - LR[j][1] > 0:
			X[j] -= dp[i - LR[j][1] - 1]
		X[j] %= mod
	dp[i] = sum(X) % mod
print(dp[-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])


mod = 998244353
(N, K) = map(int, input().split())
move = [list(map(int, input().split())) for _ in range(K)]
dp = [0] * (N + 1)
dp_sum = [0] * (N + 1)
dp[1] = dp_sum[1] = 1
for i in range(2, N + 1):
	for (l, r) in move:
		if 0 < i - l:
			dp[i] += dp_sum[i - l]
			if 0 < i - r - 1:
				dp[i] -= dp_sum[i - r - 1]
		dp[i] %= mod
	dp_sum[i] = dp_sum[i - 1] + dp[i]
print(dp[-1] % 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):
		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[n])


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


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

def check(i):
	res = 0
	for (l, r) in lr:
		if i - l < 1:
			continue
		res += cum[i - l] - cum[max(i - r - 1, 0)]
		res %= mod
	return res
for i in range(2, n + 1):
	dp.append(check(i))
	cum.append((cum[-1] + dp[-1]) % mod)
print(dp[-1])


mod = 998244353
(N, K) = map(int, input().split())
A = [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 A:
		S[i + 1] += S[max(0, i - l + 1)] - S[max(0, i - r)]
	S[i + 1] %= mod
print((S[N] - S[N - 1]) % mod)


(N, K) = map(int, input().split())
LR = [tuple(map(int, input().split())) for _ in range(K)]
mod = 998244353
S = [0, 1]
for i in range(2, N + 1):
	a = 0
	for (l, r) in LR:
		a = (a + S[max(i - l, 0)] - S[max(i - r - 1, 0)]) % mod
	S.append((S[-1] + a) % mod)
print(a)


(N, K) = map(int, input().split())
MOD = 998244353
S = []
for _ in range(K):
	(l, r) = map(int, input().split())
	S.append((l, r))
dp = [0] * (N + 1)
accDp = [0] * (N + 1)
dp[1] = 1
accDp[1] = 1
for i in range(2, N + 1):
	for (l, r) in S:
		(r, l) = (max(0, i - l), max(1, i - r))
		dp[i] += accDp[r] - accDp[l - 1]
	dp[i] %= MOD
	accDp[i] = (accDp[i - 1] + dp[i]) % MOD
print(dp[N])


(N, K) = map(int, input().split())
MOD = 998244353
D = [0] * (N + 1)
D[1] = 1
S = dict()
B = dict()
for i in range(K):
	(L, R) = map(int, input().split())
	S[i] = (L, R)
	B[i] = 0
for i in range(2, N + 1):
	for j in range(K):
		(L, R) = (S[j][0], S[j][1])
		if i - L > 0:
			B[j] += D[i - L]
		if i - R - 1 > 0:
			B[j] -= D[i - R - 1]
		D[i] += B[j]
	D[i] %= 998244353
print(D[N])


(n, k) = map(int, input().split())
l = [0, 1]
a = [1]
kl = []
mod = 998244353
for i in range(k):
	kl.append(list(map(int, input().split())))
for i in range(1, n):
	ans = 0
	for (li, re) in kl:
		ans -= l[max(i - re, 0)]
		ans += l[max(i - li + 1, 0)]
		ans %= mod
	a.append(ans)
	l.append((l[-1] + ans) % mod)
print(a[-1])


(N, k) = map(int, input().split())
L = [0 for i in range(2)]
K = []
for i in range(k):
	(l, r) = 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)


(n, k) = map(int, input().split())
lr = [list(map(int, input().split())) for _ in range(k)]
mod = 998244353
dp = [0] * n
dp[0] = 1
s = 0
for i in range(1, n):
	for j in range(k):
		if i - lr[j][0] < 0:
			continue
		elif i - lr[j][1] <= 0:
			s = (s + dp[i - lr[j][0]]) % mod
		elif 0 < i - lr[j][1]:
			s = (s + dp[i - lr[j][0]] - dp[i - lr[j][1] - 1]) % mod
	dp[i] = s
print(dp[-1])


(N, K) = 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)


(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:
		dp[i + l] += dp[i]
		dp[i + l] %= mod
		dp[i + r + 1] -= dp[i]
		dp[i + r + 1] %= mod
print(dp[n] % mod)


mod = 998244353
(N, K) = list(map(int, input().split()))
S = [list(map(int, input().split())) for _ in range(K)]
dp = [0] * (2 * N + 10)
dp[0] = 1
tmp = 0
for i in range(N):
	tmp += dp[i]
	tmp %= mod
	for (L, R) in S:
		dp[i + L] += tmp
		dp[i + R + 1] -= tmp
print(dp[N - 1] % mod)


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


import sys
(n, k) = map(int, input().split())
mod = 998244353
dp = [0] * (n + 1)
dp[1] = 1
r = [tuple(map(int, input().split())) for _ in range(k)]
s = [0 for _ in range(k)]
for i in range(2, n + 1):
	sums = 0
	for j in range(k):
		s[j] += dp[max(0, i - r[j][0])] - dp[max(0, i - r[j][1] - 1)]
		s[j] %= mod
		sums = (sums + s[j]) % mod
	dp[i] = sums
print(dp[n])


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


def main():
	(n, k) = map(int, input().split())
	LRs = [list(map(int, input().split())) for _ in range(k)]
	dp = [0, 1] + [0] * n
	for i in range(2, n + 1):
		dp[i] = dp[i - 1]
		for (l, r) in LRs:
			dp[i] += dp[max(i - l, 0)] - dp[max(i - r - 1, 0)]
			dp[i] %= 998244353
	print((dp[n] - dp[n - 1]) % 998244353)
main()


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) = map(int, input().split())
S = []
for _ in range(K):
	(l, r) = map(int, input().split())
	S.append((l, r))
mod = 998244353
dp = [0] * (N + 1)
cumsum_dp = [0] * (N + 1)
dp[1] = 1
cumsum_dp[1] = 1
for i in range(2, N + 1):
	for s in S:
		fr = max(0, i - s[1] - 1)
		to = max(0, i - s[0])
		dp[i] += (cumsum_dp[to] - cumsum_dp[fr]) % mod
	cumsum_dp[i] = (cumsum_dp[i - 1] + dp[i]) % mod
print(dp[N] % mod)


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


MOD = 998244353
(N, K) = list(map(int, input().split()))
dp = [0] * (N + 1)
dp[1] = 1
LR = []
for i in range(K):
	(l, r) = list(map(int, input().split()))
	LR.append([l, r])
for i in range(2, N + 1):
	dp[i] = dp[i - 1]
	for j in range(K):
		(l, r) = LR[j]
		dp[i] += dp[max(i - l, 0)] - dp[max(i - r - 1, 0)]
		dp[i] %= MOD
print((dp[N] - dp[N - 1]) % MOD)


(N, K) = map(int, input().split())
x = 998244353
dp = [0 for i in range(N)]
sdp = [0 for i in range(N)]
L = []
R = []
dp[0] = 1
sdp[0] = 1
for i in range(K):
	(l, r) = map(int, input().split())
	L.append(l)
	R.append(r)
for i in range(1, N):
	for j in range(K):
		dp[i] += sdp[max(i - L[j], -1)] - sdp[max(i - R[j] - 1, -1)]
		dp[i] %= x
	sdp[i] = (sdp[i - 1] + dp[i]) % x
print(dp[-1] % x)


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


(N, K) = map(int, input().split())
P = 998244353
S = list((list(map(int, input().split())) for _ in range(K)))
dp = [0] * (N + 1)
tmp = 1
for i in range(1, N + 1):
	tmp += dp[i]
	for s in S:
		(l, r) = s
		if i + l <= N:
			dp[i + l] += tmp
			dp[i + l] %= P
		if i + r + 1 <= N:
			dp[i + r + 1] -= tmp
			dp[i + r + 1] %= P
print(dp[N])


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


import sys
input = sys.stdin.buffer.readline
(N, K) = map(int, input().split())
A = [tuple(map(int, line.split())) for line in sys.stdin.buffer.readlines()]
A.sort()
mod = 998244353
acc = [0] * (N + 5)
acc[0] = 1
for i in range(1, N + 1):
	cum = 0
	for (l, r) in A:
		if i - l < 0:
			break
		(p, q) = (max(0, i - r), max(0, i - l))
		cum += acc[q] - acc[p - 1]
	acc[i] = (cum + acc[i - 1]) % mod
print((acc[N - 1] - acc[N - 2]) % 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])


(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())
DP = [0] * (N + 1)
DP[1] = 1
S = []
for i in range(K):
	S.append(list(map(int, input().split())))
for i in range(2, N + 1):
	for (l, r) in S:
		DP[i] += DP[max(i - l, 0)] - DP[max(i - r - 1, 0)]
	DP[i] += DP[i - 1]
	DP[i] %= 998244353
print((DP[N] - DP[N - 1]) % 998244353)


(n, k) = 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)


(N, K) = map(int, input().split())
MOD = 998244353
S = []
for _ in range(K):
	(L, R) = map(int, input().split())
	S.append((L, R))
S.sort()
dp = [0] * (N + 1)
dp[1] = 1
ans = [0] * (K + 1)
for i in range(2, N + 1):
	for j in range(K):
		(L, R) = (S[j][0], S[j][1])
		if L >= i:
			break
		l = max(0, i - R)
		r = min(i - 1, i - L)
		ans[j] += dp[r] - dp[l - 1]
	dp[i] += sum(ans)
	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
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])


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


mod = 998244353
w = []
dp = [0] * 200005
ds = [0] * 200005
dp[1] = 1
ds[1] = 1
(n, k) = map(int, input().split())
for i in range(k):
	(a, b) = map(int, input().split())
	w.append((a, b))
for i in range(2, n + 1):
	for (j, k) in w:
		li = i - k
		ri = i - j
		if ri < 0:
			continue
		li = max(li, 1)
		dp[i] += ds[ri] - ds[li - 1]
		dp[i] %= mod
	ds[i] = ds[i - 1] + dp[i]
	ds[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)
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) = map(int, input().split())
mod = 998244353
d = [0] * (n + 1)
d[1] = 1
LR = [list(map(int, input().split())) for _ in range(k)]
for i in range(2, n + 1):
	d[i] = d[i - 1]
	for (l, r) in LR:
		if i - l <= 0:
			continue
		d[i] = (d[i] + (d[i - l] - d[max(0, i - r - 1)])) % mod
print((d[-1] - d[-2]) % mod)


mod = 998244353
import sys
input = sys.stdin.readline
(n, k) = map(int, input().split())
lr = []
for i in range(k):
	(l, r) = map(int, input().split())
	lr.append((l, r))
lr.sort()
cnt = [0] * n
cnt[0] = 1
dp = [0] * n
for i in range(n - 1):
	cnt[i] += dp[i]
	for (x, y) in lr:
		if i + x < n:
			dp[i + x] += cnt[i]
			dp[i + x] %= mod
		if i + y < n - 1:
			dp[i + y + 1] -= cnt[i]
			dp[i + y + 1] %= mod
	dp[i] %= mod
	cnt[i] %= mod
	dp[i + 1] += dp[i]
print((cnt[-1] + dp[-1]) % mod)


(n, k) = map(int, input().split())
s = []
p = 998244353
for i in range(k):
	(l, r) = map(int, input().split())
	s.append([l, r])
k = len(s)
dp = [0] * (3 * n)
dp[1] = 1
dp[2] = -1
for i in range(1, n):
	dp[i] = (dp[i - 1] + dp[i]) % p
	for j in range(k):
		(l, r) = (s[j][0], s[j][1])
		dp[i + l] = (dp[i + l] + dp[i]) % p
		dp[i + r + 1] = (dp[i + r + 1] - dp[i]) % p
dp[n] = dp[n - 1] + dp[n]
print(dp[n] % p)


import sys
readline = sys.stdin.readline
read = sys.stdin.read

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


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


(N, K) = 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])


import sys
input = sys.stdin.readline
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
for i in range(1, n):
	dp[i + 1] += dp[i]
	for (l, r) in lr:
		dp[i + 1] += dp[max(i - l + 1, 0)] - dp[max(i - r, 0)]
		dp[i + 1] %= mod
print((dp[n] - dp[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):
	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])