Problem:
 Score : 400 points    Problem Statement 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 1 5 2
1 1
3 4      Sample Output 1 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 .        Sample Input 2 5 2
3 3
5 5      Sample Output 2 0  Because S = \{ 3, 5 \} holds, you cannot reach to Cell 5 .
Print 0 .       Sample Input 3 5 1
1 2      Sample Output 3 5       Sample Input 4 60 3
5 8
1 3
10 15      Sample Output 4 221823067  Note that you have to print the answer modulo 998244353 .

Solution (Python):


from sys import stdin, stdout
from math import *

testing = True

def tp(s="\n"):
	if testing:
		stdout.write(str(s))

def main():
	prime = 998244353
	n, k = [int(i) for i in stdin.readline().split()]
	llist = []
	rlist = []
	for i in range(k):
		l, r = [int(i) for i in stdin.readline().split()]
		llist.append(l)
		rlist.append(r)
	dp = [0]*(n+1)
	dp[1] = 1
	cumul = [0]*(n+1)
	cumul[1] = 1

	for i in range(2, n+1):
		for j in range(k):
			lower = max(1, i-rlist[j])
			upper = i-llist[j]
			
			
			if upper < 0:
				
				continue
			out = (cumul[upper] - cumul[lower - 1] + prime) % prime
			dp[i] += out
			dp[i] %= prime

		cumul[i] = (cumul[i - 1] + dp[i])%prime

	
	
	stdout.write("{0}\n".format(dp[n]))



main()

Solution (Python):
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])

Solution (Python):
import bisect
from collections import deque
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

mod = 998244353

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class BIT:
    def __init__(self, N):
        self.N = N
        self.T = [0] * (N + 1)
 
    def add(self, i, x):
        i += 1
        while i <= self.N:
            self.T[i] += x
            self.T[i] %= mod
            i += i & -i
 
    def _sum(self, i):
        s = 0
        i += 1
        while i > 0:
            s += self.T[i]
            s %= mod
            i -= i & -i
        return s % mod
 
    def sum(self, i, j):
        si = self._sum(i - 1)
        sj = self._sum(j)
        return (sj - si) % mod


def main():
    N, K = read_values()
    F = read_lists(K)

    bit = BIT(N)
    bit.add(0, 1)
    for i in range(1, N):
        s = 0
        for l, r in F:
            if i - l < 0:
                continue
            c = bit.sum(max(0, i - r), i - l)
            
            s += c
        
        bit.add(i, s)
        
    print(bit.sum(N - 1, N - 1) % mod)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

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

Ks = [list(mapint()) for _ in range(K)]
Ks.sort()

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sums(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

bit = Bit(N)
bit.add(1, 1)

for i in range(2, N+1):
    for l, r in Ks:
        if i-l<0:
            break
        dp[i] += bit.sums(i-l) - bit.sums(max(0, i-r-1))
        dp[i] %= mod
    bit.add(i, dp[i])

print(dp[-1])

Solution (Python):
mod = 998244353

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

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

for i in range(1, N):
    for k in range(K):
        l = max(0, i-R[k])
        r = i-L[k]
        if r < 0:
            continue
        dp[i] += ruisekiwa[r+1] - ruisekiwa[l]
        
        dp[i] %= mod
    ruisekiwa[i+1] = ruisekiwa[i] + dp[i]


print(dp[-1])

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

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

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


print(dp[N-1])

Solution (Python):
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])

Solution (Python):
N, K = map(int, input().split())
LR = []
for _ in range(K):
    L, R = map(int, input().split())
    LR.append((L, R))

MOD = 998244353

def f_dp(i):
    if 0 <= i < N:
        return dp[i]
    else:
        return 0

dp = [0] * N
dp[0] = 1
for i in range(1, N):
    temp = 0
    for k in range(K):

        temp += f_dp(i - LR[k][0]) - f_dp(i - LR[k][1]-1)
    dp[i] = (temp + dp[i-1]) % MOD

print((dp[-1] - dp[-2]) % MOD)

Solution (Python):
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

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


def get_nums_l():
    return [ int(s) for s in input().split(" ")]


def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def main():
    INF = 999999999999999999999999
    MOD = 998244353

    n,k = get_nums_l()

    steps = []
    for _ in range(k):
        l,r = get_nums_l()
        steps.append((l,r))
    
    

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

    dp[0] = 1
    ruiseki[1] = 1

    for i in range(1, n):
        for a,b in steps:
            l = max(0, i-b)
            r = i-a
            
            if r < 0:
                continue

            add = (ruiseki[r+1] - ruiseki[l])
            dp[i] = (dp[i] + add) % MOD
            
        ruiseki[i+1] = (ruiseki[i] + dp[i]) % MOD
        

    print(dp[n-1] % MOD)

main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()

def main():
    mod = 998244353
    N, K = map(int, input().split())
    jump = []
    for _ in range(K):
        l, r = map(int, input().split())
        jump.append((l, r))

    dp = [0] * (N + 2)
    dp[0] = 1
    for i in range(N - 1):
        for l, r in jump:
            if i + l <= N:
                dp[i + l] = (dp[i + l] + dp[i]) % mod
            if i + r + 1 <= N:
                dp[i + r + 1] = (dp[i + r + 1] - dp[i]) % mod
        if i != 0:
            dp[i + 1] = (dp[i + 1] + dp[i]) % mod
        
    print(dp[N - 1] % mod)


if __name__ == "__main__":
    main()

Solution (Python):
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])

Solution (Python):
N, K = [int(s) for s in input().split()]
rans = []
for _ in range(K):
    l, r= [int(s) for s in input().split()]
    rans.append((l, r))
rans.sort()

prev = -1
newrans = []
for ran in rans:
    l, r = ran
    if l <= prev:
        newrans[-1] = max(r, newrans[-1])
    else:
        newrans.append([l,r])
    prev = max(prev, r)

MOD = 998244353

rans = newrans
sums = [0, 1]
s = 1

for i in range(2, N+1):
    
    for ran in rans:
        l = i - ran[0]
        r = max(i - ran[1] - 1, 0)
        
        if l >= 0:
            s = (s + sums[l] - sums[r]) % 998244353
    sums.append(s)

if N == 1:
    print(1)
else:
    print((sums[-1] - sums[-2]) % 998244353)

Solution (Python):


mod = 998244353

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

for k in range(K):
    L, R = map(int, input().split())
    kukans.append([L,R])

kukans = list(sorted(kukans, key=lambda x:x[0]))

ruiseki_dp = [0]
for i in range(1,N+1):
    if i == 1:
        ruiseki_dp.append(1)
    else:
        
        able_kukans = []
        for L,R in kukans:
            if R <= i-1:
                able_kukans.append([L,R])
            elif L <= i-1 < R:
                able_kukans.append([L,i-1])
                break
            else: 
                break
        
        next_dp = 0
        for L, R in able_kukans:
            next_dp = (next_dp+ruiseki_dp[i-L]-ruiseki_dp[i-R-1])%mod

        ruiseki_dp.append((ruiseki_dp[-1]+next_dp)%mod)
    
print((ruiseki_dp[-1]-ruiseki_dp[-2])%mod)

Solution (Python):
N, K = map(int, input().split())
LR = [tuple(map(int, input().split())) for _ in range(K)]

MOD = 998244353
class Mint:
    def __init__(self, value=0):
        self.value = value % MOD
        if self.value < 0: self.value += MOD

    @staticmethod
    def get_value(x): return x.value if isinstance(x, Mint) else x

    def inverse(self):
        a, b = self.value, MOD
        u, v = 1, 0
        while b:
            t = a // b
            b, a = a - t * b, b
            v, u = u - t * v, v
        if u < 0: u += MOD
        return u

    def __repr__(self): return str(self.value)
    def __eq__(self, other): return self.value == other.value
    def __neg__(self): return Mint(-self.value)
    def __hash__(self): return hash(self.value)
    def __bool__(self): return self.value != 0

    def __iadd__(self, other):
        self.value = (self.value + Mint.get_value(other)) % MOD
        return self

    def __add__(self, other):
        new_obj = Mint(self.value)
        new_obj += other
        return new_obj
    __radd__ = __add__

    def __isub__(self, other):
        self.value = (self.value - Mint.get_value(other)) % MOD
        if self.value < 0: self.value += MOD
        return self

    def __sub__(self, other):
        new_obj = Mint(self.value)
        new_obj -= other
        return new_obj

    def __rsub__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj -= self
        return new_obj

    def __imul__(self, other):
        self.value = self.value * Mint.get_value(other) % MOD
        return self

    def __mul__(self, other):
        new_obj = Mint(self.value)
        new_obj *= other
        return new_obj
    __rmul__ = __mul__

    def __ifloordiv__(self, other):
        other = other if isinstance(other, Mint) else Mint(other)
        self *= other.inverse()
        return self

    def __floordiv__(self, other):
        new_obj = Mint(self.value)
        new_obj //= other
        return new_obj

    def __rfloordiv__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj //= self
        return new_obj

LR.sort(key=lambda x: x[1])
pl = pr = -1
LR2 = []
for l, r in LR:
    if LR2:
        pl, pr = LR2.pop()
        if l <= pl:
            LR2.append((l, r))
        elif l <= pr:
            LR2.append((pl, r))
        else:
            LR2.append((pl, pr))
            LR2.append((l, r))
    else:
        LR2.append((l, r))

dp = [Mint() for _ in range(N + 5)]
dp[1] += 1
dp[2] -= 1
for i in range(1, N):
    dp[i] += dp[i - 1]
    for l, r in LR2:
        nl = min(i + l, N + 1)
        nr = min(i + r, N + 1)
        dp[nl] += dp[i]
        dp[nr + 1] -= dp[i]
dp[N] += dp[N - 1]
print(dp[N])

Solution (Python):
N, K = [int(_) for _ in input().split()]

S = [[int(_) for _ in input().split()] for _ in range(K)]
p = 998244353

dp = [0 for _ in range(N + 1)]
dsum = [0 for _ in range(N + 1)]

dp[0] = 1
dsum[0] = 1

for i in range(1, N):
    for l, r in S:
        s = i - r
        e = i - l
        
        if e >= 0:
            dp[i] += dsum[e]
        if s > 0:
            dp[i] -= dsum[s-1]
        dp[i] %= p
    dsum[i] = dsum[i-1] + dp[i]
    dsum[i] %= p

print(dp[N-1])

Solution (Python):
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
mod = 998244353

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

dist = [0] * (N + 1)
dist[1] = 1
for i in range(1, N + 1):
    dist[i] += dist[i - 1]
    dist[i] %= mod
    for l, r in LR:
        if i + l <= N:
            dist[i + l] += dist[i]
        if i + r + 1 <= N:
            dist[i + r + 1] -= dist[i]
    if i == 1:
        dist[i] = 0

print(dist[N])

Solution (Python):
MOD = 998244353

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


dp = [0] * 200010
dp[0] = 1

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

print(dp[N-1])

Solution (Python):
P = 998244353

def val(x):
	return (x+P)%P

n, k = map(int,input().split())
plages = []
for _ in range(k):
	x,y=map(int,input().split())
	plages+=[[x,y]]


pref = [0]*(n+1)
ans = [0]*(n+1)
ans[1] = pref[1] = 1

for i in range(2,n+1):
	for p in plages:
		l = max(0,i-p[1])
		r = max(0,i-p[0])
		add= 0
		if l==0 and r==0:add=0
		elif l==0: add = pref[r]
		else:
			add = val(pref[r]-pref[l-1])
		
		ans[i] += add
		ans[i]%=P
	pref[i] = pref[i-1]+ans[i]
	pref[i]%=P
	



print(ans[n])

Solution (Python):
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)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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

    MOD = 998244353

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

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

    dp[N] += c


    print(dp[N] % MOD)


if __name__ == '__main__':
    main()

Solution (Python):
MOD = 998244353

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

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

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


for i in range(1,N+1):
    ruiseki[i]= (ruiseki[i] + ruiseki[i-1])%MOD
    dp[i]=ruiseki[i]
    if i == 1:
        dp[1]=1
    for k in range(K):
        l,r = LR[k]
        ruiseki[min(N+1,i+l)]= (ruiseki[min(N+1,i+l)] + dp[i])%MOD
        ruiseki[min(N+1,i+r+1)]=(ruiseki[min(N+1,i+r+1)] - dp[i])%MOD

print(dp[N])

Solution (Python):




mod = 998244353

N, K = map(int, input().split())
LR = []
for k in range(K):
	L, R = map(int, input().split())
	LR.append((L,R))
counter = [0 for _ in range(N)]
for i in LR:
	l = i[0]
	r = i[1]
	if l < N:
		counter[l] += 1
	if r + 1 < N:
		counter[r+1] -= 1
sm = 0
counter[0] = 1
for k in range(1, N):
	counter[k] += sm
	sm = counter[k]%mod
	if sm == 0:
		continue
	for i in LR:
		l = i[0]
		r = i[1]
		if k + l < N:
			counter[k+l] += sm
			counter[k+l] %= mod
		if k + r + 1 < N:
			counter[k+r+1] -= sm
			counter[k+r+1] %= mod
print(counter[-1]%mod)

Solution (Python):
import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=998244353
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

lst=[0]*(n+1)
lst[0]=1
lst[1]=-1

now=0

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

Solution (Python):
from typing import List, Any


def read_int() -> int:
    return int(input().strip())


def read_ints() -> List[int]:
    return list(map(int, input().strip().split(' ')))


def solve() -> Any:
    N, K = read_ints()
    L, R = [], []
    for _ in range(K):
        l, r = read_ints()
        L.append(l)
        R.append(r)
    dp = [0]*N
    prefix = [0]*N
    dp[0] = 1
    prefix[0] = 1
    modulo = 998244353
    for i in range(1, N):
        for k in range(K):
            left = max(0, i-R[k])
            right = i-L[k]
            if right < 0:
                continue
            if left == 0:
                dp[i] = (dp[i]+prefix[right])%modulo
            else:
                dp[i] = (dp[i]+prefix[right]-prefix[left-1])%modulo
        prefix[i] = (prefix[i]+prefix[i-1]+dp[i])%modulo
    return dp[N-1]


if __name__ == '__main__':
    print(solve())

Solution (Python):
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)

Solution (Python):
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()

Solution (Python):
mod = 998244353

class FenwickTree:
    def __init__(self, n, init_list=None):
        self.n = n
        self.data = [0] * n
        if init_list:
            assert n == len(init_list)
            for i in range(n):
                self.add(i, init_list[i])
        
    def add(self, i, val):
        assert 0 <= i < self.n
        i += 1
        while i <= self.n:
            self.data[i - 1] = (val + self.data[i - 1]) % mod
            i += i & -i 
            
    def update(self, i, val):
        self.add(i, val - self.sum(i, i+1))

    def sum(self, l, r): 
        assert  0 <= l <= r <= self.n
        if l != 0:
            return (self.sum(0, r) - self.sum(0, l)) % mod
        ret = 0
        while r > 0:
            ret = (ret + self.data[r - 1]) % mod
            r -= r & -r 
        return ret

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

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

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

Solution (Python):

import sys

MOD = 998244353  

def debug(N, st):
    print(*[st.query(i, i+1) for i in range(N)], sep=" ")

def solve(N: int, K: int, L: "List[int]", R: "List[int]"):
    add = lambda a,b: (a+b)%MOD
    st = SegmentTreeLazy([0]*N, 0, 0, add, add, add)
    st.update(0, 1, 1)
    
    for i in range(N):
        
        v = st.query(i, i+1)
        for l, r in zip(L, R):
            ll, rr = l + i, min(r + i + 1, N)
            if ll >= N:
                continue
            st.update(ll, rr, v)
    return st.query(N-1, N)



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

class SegmentTreeLazy():
    def __init__(self, arr, ti, ei, func, op, merge):
        self.h = (len(arr) - 1).bit_length()
        self.n = 2**self.h
        self.func = func
        self.op = op
        self.merge = merge
        self.ti = ti
        self.ei = ei
        self.val = [ti for _ in range(2 * self.n)]
        for i in range(len(arr)):
            self.val[self.n + i] = arr[i]
        for i in range(1, self.n)[::-1]:
            self.val[i] = self.func(self.val[2 * i], self.val[2 * i + 1])
        self.laz = [ei for _ in range(2 * self.n)]

    def reflect(self, k):
        if self.laz[k] == self.ei:
            return self.val[k]
        return self.op(self.val[k], self.laz[k])

    def propagate(self, k):
        if self.laz[k] == self.ei: return
        self.laz[2 * k] = self.merge(self.laz[2 * k], self.laz[k])
        self.laz[2 * k + 1] = self.merge(self.laz[2 * k + 1], self.laz[k])
        self.val[k] = self.reflect(k)
        self.laz[k] = self.ei

    def thrust(self, k):
        for i in range(1, self.h + 1)[::-1]:
            self.propagate(k >> i)

    def recalc(self, k):
        while k:
            k >>= 1
            self.val[k] = self.func(self.reflect(2 * k), self.reflect(2 * k + 1))

    def update(self, lt, rt, x):
        lt += self.n
        rt += self.n
        vl = lt
        vr = rt
        self.thrust(lt)
        self.thrust(rt - 1)
        while rt - lt > 0:
            if lt & 1:
                self.laz[lt] = self.merge(self.laz[lt], x)
                lt += 1
            if rt & 1:
                rt -= 1
                self.laz[rt] = self.merge(self.laz[rt], x)
            lt >>= 1
            rt >>= 1
        self.recalc(vl)
        self.recalc(vr - 1)

    def query(self, lt, rt):
        lt += self.n
        rt += self.n
        self.thrust(lt)
        self.thrust(rt - 1)
        vl = vr = self.ti
        while rt - lt > 0:
            if lt & 1:
                vl = self.func(vl, self.reflect(lt))
                lt += 1
            if rt & 1:
                rt -= 1
                vr = self.func(self.reflect(rt), vr)
            lt >>= 1
            rt >>= 1
        return self.func(vl, vr)
    

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    
    main()

Solution (Python):
n,k = map(int,raw_input().split())
jis = [map(int, raw_input().split()) for _ in range(k)]
jis.sort()

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

print dp[n-1]

Solution (Python):
MOD = 998244353
n, k = map(int, input().split())
cumulative_sum = [0 for _ in range(n+1)]
table = [0 for i in range(n)]
pair_list = []
for i in range(k):
    l, r = map(int, input().split())
    pair_list.append((l,r))

table[0] = 1
cumulative_sum[1] = 1
for i in range(1,n):
    root = 0
    for l, r in pair_list:
        l = max(i-l+1, 0)
        r = max(i-r,0)
        root += cumulative_sum[l]- cumulative_sum[r]
        root %= MOD
    table[i]= root % MOD
    cumulative_sum[i+1] = (cumulative_sum[i]+root)%MOD
    

print(table[-1])

Solution (Python):
import sys

def solve():
      input = sys.stdin.readline
      N, K = map(int, input().split())
      L = [[int(i) for i in input().split()] for _ in range(K)]
      L.sort()
      mod = 998244353
      D = [0] * (N + 1)
      D[0] = 1
      D[1] = -1
      for i in range(N):
            if i > 0:
                  D[i] += D[i-1]
                  D[i] %= mod
            for l, r in L:
                  if i + l <= N:
                        D[i + l] += D[i]
                        D[i + l] %= mod
                  if i + r + 1 <= N:
                        D[i + r + 1] -= D[i]
                        D[i + r + 1] = (mod + D[i + r + 1]) % mod
      print(D[N-1])

      return 0

if __name__ == "__main__":
      solve()

Solution (Python):
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])

Solution (Python):
import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
from fractions import Fraction
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
INF = float("inf")
MOD = 998244353

N,K = map(int,input().split())
move = []
for i in range(K):
    L,R = map(int,input().split())
    move.append((L,R))

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

for i in range(1,N):
    """
    print(i)
    print(dp)
    print(Sum)
    """
    for j in move:
        l,r = j[0],j[1]
        left = max(0,i-r)
        right = i-l

        if right >= 0:
            
            dp[i] += Sum[right+1]-Sum[left]
            dp[i] %= MOD

        Sum[i+1] = Sum[i] + dp[i]
        Sum[i+1] %= MOD
"""
print(dp)
print(Sum)
"""
print(dp[-1])

Solution (Python):
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])

Solution (Python):

from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for _ in range(n)]
def LIR(n):
    return [LI() for _ in range(n)]
def SR(n):
    return [S() for _ in range(n)]
def LSR(n):
    return [LS() for _ in range(n)]

sys.setrecursionlimit(1000000)
mod = 998244353

def solve():
    def add(i,x):
        while i < len(dp):
            dp[i] += x
            dp[i] %= mod
            i += i&-i
    def sum(i):
        res = 0
        while i:
            res += dp[i]
            res %= mod
            i -= i&-i
        return res

    n,k = LI()
    p = LIR(k)
    p.sort()
    dp = [0]*(n+2)
    add(1,1)
    add(2,-1)
    for i in range(1,n):
        dpi = sum(i)%mod
        for l,r in p:
            li = i+l
            if li > n:
                break
            ri = min(n,i+r)+1
            add(li,dpi)
            add(ri,-dpi)
    print(sum(n)%mod)
    return


if __name__ == "__main__":
    solve()