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):
N, K = map(int, input().split())
LR = [tuple(map(int, input().split())) for _ in range(K)]

MOD = 998244353
class Mint:
    __slots__ = ('value')

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

import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 998244353

class BIT2:
    def __init__(self, N):
        self.N = (N+1)
        self.data0 = [0] * (N+1)
        self.data1 = [0] * (N+1)
        
    def _add(self, data, k, x):
        while k < self.N: 
            data[k] += x
            k += k & -k

    def _sum(self, data, k):
        s = 0
        while k:
            s += data[k]
            k -= k & -k
        return s

    def add(self, l, r, x):
        self._add(self.data0, l, -x*(l-1))
        self._add(self.data0, r, x*(r-1))
        self._add(self.data1, l, x)
        self._add(self.data1, r, -x)

    def sum(self, l, r):
        return self._sum(self.data1, r-1) * (r-1) + self._sum(self.data0, r-1) - self._sum(self.data1, l-1) * (l-1) - self._sum(self.data0, l-1)
    
N, K = map(int, readline().split())
bit = BIT2(N)
d = []
for _ in range(K):
    L,R = map(int, readline().split())
    d.append((L,R))

bit.add(1,2,1)

for i in range(2,N+1):
    for k in range(K):
        L,R = d[k]
        tmp = bit.sum(max(1,i-R),max(1,i-L+1))%MOD
        bit.add(i,i+1,tmp)
print(bit.sum(N,N+1)%MOD)

Solution (Python):

import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 998244353
N, K = map(int, readline().split())
data = []
for _ in range(K):
    L,R = map(int, readline().split())
    data.append((L,R))
    
A = [0]*(N+1)
A[1] = 1
S = [0]*(N+1)
S[1] = 1

for i in range(2,N+1):
    for k in range(K):
        L,R = data[k]
        A[i] += (S[max(0,i-L)]- S[max(0,i-R-1)]) % MOD
        A[i] %= MOD
    S[i] = (S[i-1] + A[i]) % MOD

print(A[N])

Solution (Python):

import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 998244353
N, K = map(int, readline().split())
data = []
for _ in range(K):
    L,R = map(int, readline().split())
    data.append((L,R))
    
data = sorted(data)
A = [0]*(N+1)
A[1] = 1
S = [0]*(N+1)
S[1] = 1

for i in range(2,N+1):
    for k in range(K):
        L,R = data[k]
        A[i] += (S[max(0,i-L)]- S[max(0,i-R-1)]) % MOD
        A[i] %= MOD
    S[i] = (S[i-1] + A[i]) % MOD

print(A[N])

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

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 998244353


def main():
    N, K, *LR = map(int, read().split())
    interval = [(l, r) for l, r in zip(*[iter(LR)] * 2)]

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

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

    for i in range(1, N):
        for l, r in interval:
            left = max(i - r, 0)
            right = max(i - l + 1, 0)
            dp[i] = (dp[i] + sdp[right] - sdp[left]) % MOD
        sdp[i + 1] = (sdp[i] + dp[i]) % MOD

    print(dp[N - 1])
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 998244353


def main():
    N, K, *LR = map(int, read().split())
    interval = [(l, r) for l, r in zip(*[iter(LR)] * 2)]

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

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

    print(dp[N])
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 998244353


def main():
    N, K, *LR = map(int, read().split())
    interval = [(l, r) for l, r in zip(*[iter(LR)] * 2)]

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

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

    print(dp[N])
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
N, K = map(int, input().split())

MOD = 998244353

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

E = [0] * N

def update(i, v):
	while i < N:
		E[i] = (E[i] + v) % MOD
		i |= i+1

def query(i):
	r = 0
	while i > 0:
		r += E[i-1]
		i &= i-1

	return r % MOD

update(0, 1)
update(1, -1)

for i in range(N-1):
	v = query(i+1)
	for L, R in P:
		if i + L < N:
			update(i+L, v)

			if i + R + 1 < N:
				update(i+R+1, -v)


print(query(N))

Solution (Python):
def N():
    return int(input())
def L():
    return list(map(int,input().split()))
def NL(n):
    return [list(map(int,input().split())) for i in range(n)]
mod = pow(10,9)+7
import numpy as np

import math
md = 998244353

n,k = L()
lr = NL(k)
s = set()

for l,r in lr:
    s |= set(range(l,r+1))


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

c = [0]*(n+1)
for i in range(1,n+1):
    dp[i] = (dp[i]+dp[i-1])%md
    for l,r in lr:
        if i+l < n+1:
            dp[i+l] += dp[i]
            dp[i+l] %= md
            if i+r+1 < n+1:
                dp[i+r+1] -= dp[i]
                dp[i+r+1] %= md

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

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

Solution (Python):

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

kukan = list()
for i in range(K):
  l, r =  map(int, input().split())
  kukan.append((l, r))
dp = [0] * (N+1)
dp[1] = 1
dp_sum = [0] * (N+1)
dp_sum[1] = 1
for i in range(0, N+1):
  for j in range(K):
    from_l = i - kukan[j][1]
    from_r = i - kukan[j][0]
    if from_r < 0:
      continue
    else:
      from_l = max(1, from_l)
      dp[i] += dp_sum[from_r] - dp_sum[from_l - 1]
      dp[i] %= 998244353
  dp_sum[i] = dp[i] + dp_sum[i-1]
print(dp[N] % 998244353)

Solution (Python):
root=[]
n,k = map(int,input().split())
for i in range(k):
    x,y = map(int,input().split())
    root.append([x,y])

toori=[0]*(2*10**5)+[0]*n+[0]*(2*10**5)
toori[2*10**5]=1
cum=[0]*k
for a,i in enumerate (root):
    s=0
    for j in range (i[0],i[1]+1):
        s+=toori[2*10**5+1-j]
    cum[a]=s
aaa=sum(cum)%998244353
toori[2*10**5+1]+=aaa


for now in range(2,n):
    hueru=0
    for a,i in enumerate (root):
        hueru+=(toori[2*10**5+now-i[0]] - toori[2*10**5+now-1-i[1]])
    aaa+=hueru
    aaa%=998244353
    toori[2*10**5+now]+=aaa
    toori[2*10**5+now]%=998244353
    


print(toori[2*10**5+n-1]%998244353)

Solution (Python):
import sys
import os
import math
import bisect
import itertools
import collections
import heapq
import queue
import array







sys.setrecursionlimit(10000000)


def ii(): return int(sys.stdin.buffer.readline().rstrip())
def il(): return list(map(int, sys.stdin.buffer.readline().split()))
def fl(): return list(map(float, sys.stdin.buffer.readline().split()))
def iln(n): return [int(sys.stdin.buffer.readline().rstrip())
                    for _ in range(n)]


def iss(): return sys.stdin.buffer.readline().decode().rstrip()
def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split()))
def isn(n): return [sys.stdin.buffer.readline().decode().rstrip()
                    for _ in range(n)]


def lcm(x, y): return (x * y) // math.gcd(x, y)



MOD = 998244353
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, K = il()
    D = [il() for _ in range(K)]

    dp = [0] * (N)
    dp[0] = 1
    acc = 0
    for i in range(1, N):
        for l, r in D:
            if i - l >= 0:
                acc += dp[i-l]
                acc %= MOD
            if i - r - 1 >= 0:
                acc -= dp[i-r-1]
                acc %= MOD
        dp[i] = acc
    print(dp[-1])


if __name__ == '__main__':
    main()

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

Solution (Python):

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

for i in range(N):
  for l, r in move:
    dp[i+l] += dp[i]
    dp[i+l] %= mod
    dp[i+r+1] -= dp[i]
    dp[i+r+1] %= mod
  if i:
    dp[i+1] += dp[i]
  dp[i] %= mod

print(dp[N-1])

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

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

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

DP = [0 for _ in range(N)] 
DP[0] = 1
DP_sum = [0 for _ in range(N)] 
DP_sum[0] = 1

for n in range(1,N):
  
  
  
  for l,r in moves:
    
    if n-l >= 0:
      DP[n] += DP_sum[n-l]
      if n-r-1 >= 0: 
        DP[n] -= DP_sum[n-r-1]
    DP[n] %= MOD
    
  DP_sum[n] = (DP_sum[n-1] + DP[n]) % MOD 
  
print(DP[N-1] % MOD)

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

print(dp[n])

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

Solution (Python):

import sys
import math
import decimal
import itertools
from itertools import product
from functools import reduce
def input():
    return sys.stdin.readline()[:-1]
def gcd(*numbers):
    return reduce(math.gcd, numbers)
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)
def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
def sort_zip(a:list, b:list):
    z = zip(a, b)
    z = sorted(z)
    a, b = zip(*z)
    a = list(a)
    b = list(b)
    return a, b
def ceil(x):
    return math.ceil(x)
def floor(x):
    return math.floor(x)


def main():
    MOD = 998244353
    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())

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


if __name__ == '__main__':
    main()

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

Solution (Python):

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 = i - l
        lj = max(1, i - r)  
        if rj <= 0: continue
        dp += dpsum[rj] - dpsum[lj - 1]
        dp %= p
    dpsum[i] = dpsum[i - 1] + dp
    dpsum[i] %= p

print(dp)

Solution (Python):

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)

Solution (Python):

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

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 ranges:
        rj = i - l
        lj = max(1, i - r)  
        if rj <= 0: continue

        dp[i] += dpsum[rj] - dpsum[lj - 1]
        dp[i] %= p
    dpsum[i] = dpsum[i - 1] + dp[i]
    dpsum[i] %= p

print(dp[N])

Solution (Python):
import math
import sys
import os

sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")
INF = float("inf")
MOD = 998244353    


N,K = LI()
LRs = [LI() for _ in range(K)]

dp = [0]*(N+1)
cum = [0]*(N+1)
dp[1] = 1
cum[1] = 1
for i in range(2, N+1):
    for j in range(K):
        l, r = LRs[j]
        start = max(0,i-r-1)
        end = max(0,i-l)
        dp[i] += cum[end] - cum[start]
        dp[i] %= MOD
    
    cum[i] = (cum[i-1] + dp[i]) % MOD
ans = dp[N]
print(ans)

Solution (Python):
def main():
    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 + 1)
    s = [0] * (n + 1)
    dp[1] = 1
    s[1] = 1
    for i in range(2, n + 1):
        for j in range(k):
            l = max(1, i - R[j])
            r = i - L[j]
            if r < 1: continue
            dp[i] += s[r] - s[l - 1]
            dp[i] %= MOD
        s[i] = s[i - 1] + dp[i]
        s[i] %= MOD
    print(dp[n])


if __name__ == "__main__":
    main()

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

Solution (Python):
import math
import sys
import os


sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")
INF = float("inf")
MOD = 998244353    


N,K = LI()
LRs = [LI() for _ in range(K)]















dp = [0]*(N+1)

cum = [0]*(N+1)
dp[1] = 1
cum[1] = 1
for i in range(2, N+1):
    for j in range(K):
        l, r = LRs[j]
        start = max(0,i-r-1)
        end = max(0,i-l)
        
        
        dp[i] += cum[end] - cum[start]
        
        
        
        
        
    
    dp[i] %= MOD
    
    cum[i] = (cum[i-1] + dp[i]) % MOD
print(dp[N])

Solution (Python):


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

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


for i in range(2, n+1):
    for j in range(k):
        li = i-R[j]
        ri = i-L[j]
        if ri<0: continue
        li = max(li, 1)
        dp[i] += (cumsum[ri]-cumsum[li-1])%mod
    cumsum[i] = cumsum[i-1]+dp[i]

print(dp[n]%mod)

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

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

Solution (Python):
import sys

import math

import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd


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

Solution (Python):
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext

def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')

MOD = 998244353
num_list = []
str_list = []

def main():
    n, k = i_map()
    num_list = i_row_list(k)

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

    for i in range(2, n+1):
        for j in range(k):
            li = i - num_list[j][1]
            ri = i - num_list[j][0]
            if ri < 0:
                continue
            li = max(li, 0)
            dp[i] += dp_sum[ri] - dp_sum[li-1]
            dp[i] %= MOD
        dp_sum[i] = dp_sum[i-1] + dp[i]
    
    print(dp[n]%MOD)

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    ikimasu = sys.stdin.buffer.readline
    ini = lambda: int(ins())
    ina = lambda: list(map(int, ikimasu().split()))
    ins = lambda: ikimasu().strip()
    MOD = 998244353
    class ModInt:
        def __init__(self, x):
            self.x = x % MOD

        def __str__(self):
            return str(self.x)

        __repr__ = __str__

        def __add__(self, other):
            return (
                ModInt(self.x + other.x) if isinstance(other, ModInt) else
                ModInt(self.x + other)
            )

        def __sub__(self, other):
            return (
                ModInt(self.x - other.x) if isinstance(other, ModInt) else
                ModInt(self.x - other)
            )

        def __mul__(self, other):
            return (
                ModInt(self.x * other.x) if isinstance(other, ModInt) else
                ModInt(self.x * other)
            )

        def __truediv__(self, other):
            return (
                ModInt(
                    self.x * pow(other.x, MOD - 2, MOD)
                ) if isinstance(other, ModInt) else
                ModInt(self.x * pow(other, MOD - 2, MOD))
            )

        def __pow__(self, other):
            return (
                ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
                ModInt(pow(self.x, other, MOD))
            )

        __radd__ = __add__

        def __rsub__(self, other):
            return (
                ModInt(other.x - self.x) if isinstance(other, ModInt) else
                ModInt(other - self.x)
            )

        __rmul__ = __mul__

        def __rtruediv__(self, other):
            return (
                ModInt(
                    other.x * pow(self.x, MOD - 2, MOD)
                ) if isinstance(other, ModInt) else
                ModInt(other * pow(self.x, MOD - 2, MOD))
            )

        def __rpow__(self, other):
            return (
                ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
                ModInt(pow(other, self.x, MOD))
            )

    n,k = ina()
    dp = [ModInt(0)]*(n+1)
    dp[1] = 1
    pair = [(0,0)]*k
    for i in range(k):
        l,r = ina()
        pair[i] = (l,r)
    for i in range(1,n):
        tmp = i
        dp[tmp]+=dp[tmp-1]
        for j in range(k):
            if(tmp+pair[j][0])<=n:
                
                dp[tmp+pair[j][0]]+=dp[tmp]
                
            if(tmp+pair[j][1])<=n-1:
                
                dp[tmp+pair[j][1]+1]-=dp[tmp]
                
    
    print(dp[n])
        
        
    

    
    
        


    
        


        


    




















if __name__ == "__main__":
    main()

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

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

Solution (Python):
import sys



from copy import *
from bisect import *	

from math import gcd,ceil,sqrt
from itertools import permutations as prm,product
 
def eprint(*args):
    print(*args, file=sys.stderr)
zz=1
 

if zz:
	input=sys.stdin.readline
else:	
	sys.stdin=open('input.txt', 'r')
	sys.stdout=open('all.txt','w')
di=[[-1,0],[1,0],[0,1],[0,-1]]
def inc(d,c,x=1):
	d[c]=d[c]+x if c in d else x
def bo(i):
	return ord(i)-ord('A')	
def li():
	return [int(xx) for xx in input().split()]
def fli():
	return [float(x) for x in input().split()]	
def comp(a,b):
	if(a>b):
		return 2
	return 2 if a==b else 0		
def gi():	
	return [xx for xx in input().split()]
def fi():
	return int(input())
def pro(a): 
	return reduce(lambda a,b:a*b,a)		
def swap(a,i,j): 
	a[i],a[j]=a[j],a[i]	
def si():
	return list(input().rstrip())	
def mi():
	return 	map(int,input().split())			
def gh():
	sys.stdout.flush()
def isvalid(i,j):
	return 0<=i<n and 0<=j<m and a[i][j]!="."
def bo(i):
	return ord(i)-ord('a')	
def graph(n,m):
	for i in range(m):
		x,y=mi()
		a[x].append(y)
		a[y].append(x)

t=1
mod=998244353



while t>0:
	t-=1
	n,k=mi()
	d=[0]*(2*n+5)
	a=[]
	for i in range(k):
		a.append(li())
	d[1]=1	
	d[2]=-1
	for i in range(1,n+1):
		d[i]+=d[i-1]
		d[i]%=mod
		for j in range(k):
			d[i+a[j][0]]+=d[i]
			d[i+a[j][1]+1]-=d[i]
	
		
		
	print(d[n])

Solution (Python):
import numpy as np

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

dp = np.zeros(N+2, dtype = int)
dp[1] = 1
dp[2] = -1

atai = 0
for i in range(1, N+2):
    atai += dp[i]
    for LR in LRs:
        if(i+LR[0] <= N):
            dp[i+LR[0]] = (dp[i+LR[0]] + atai) % 998244353
        if(i+LR[1] <= N):
            dp[i+LR[1]+1] = (dp[i+LR[1]+1] -atai) % 998244353




ruisekiwa = [0]

for hoge in dp:
    ruisekiwa.append(ruisekiwa[-1]+hoge)
print(ruisekiwa[N+1] % 998244353)

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

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

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

for i in range(2, n + 1):
    for l, r in lr:
        if l >= i:
            continue

        ll = max(1, i - r)
        rr = i - l
        if ll <= rr:
            dp[i] += cumsum[rr] - cumsum[ll - 1]
            dp[i] %= mod
    cumsum[i] = cumsum[i - 1] + dp[i]
    cumsum[i] %= mod

print(dp[n] % mod)

Solution (Python):
m = 998244353
def main():
    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+1)
    dp[1] = 1
    dpsum = [0]*(n+1)
    dpsum[1] = 1

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

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