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):
import bisect
import sys
input = sys.stdin.readline
M = 998244353
def solve():
  N, K = map(int, input().split())
  LR = []
  for _ in range(K):
    l, r = map(int, input().split())
    LR.append((l, r))
  Ss = [0] * K
  steps = [0] * (N+1)
  steps[1] = 1
  for n in range(2, N+1):
    for k in range(K):
      l, r = LR[k]
      
      
      if n-l >= 0:
        Ss[k] += steps[n-l]
      if n-r-1 >= 0:
        Ss[k] -= steps[n-r-1]
      Ss[k] %= M
    steps[n] = sum(Ss) % M
    
  print(steps[-1])
      
solve()

Solution (Python):
"Binary Indexed Tree"
"""
- iが与えられたときa1~aiまでの和を計算する O(log n)
- iとxが与えられたときai += x とする O(log n)
"""




def BIT_query(idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)  
    return res_sum



def BIT_updata(idx, x):
    while idx <= N:
        BIT[idx] += x
        idx += (idx&(-idx))  
    return
















N, K = map(int, input().split())
move = []
for _ in range(K):
    l, r = map(int, input().split())
    move.append([l, r])
MOD = 998244353
BIT = [0]*(N+1)  
BIT_updata(1, 1)
for i in range(2, N+1):
    for l, r in move:
        
        BIT_updata(i, (BIT_query(i-l)-BIT_query(i-r-1))%MOD)
ans = BIT_query(N) - BIT_query(N-1)
print(ans%MOD)

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

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

Solution (Python):
N, K = map(int, input().split())
MOD = 998244353
ans = [0, 1, -1] + [0]*(N-2)
L, R = [], []
for _ in range(K):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r+1)

temp = 0
for i in range(1, N):
    temp = (temp + (ans[i] % MOD)) % MOD
    for l in L:
        if i + l <= N:
            ans[i+l] = (ans[i+l] + temp) % MOD
    for r in R:
        if i + r <= N:
            ans[i + r] = (ans[i+r] - temp) % MOD
print((temp + ans[N]) % MOD)

Solution (Python):

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)

Solution (Python):









class BinaryIndexedTree:
    
    def __init__(self, size):
        self.size = size
        self.dat = [0]*(size+1)
        self.depth = size.bit_length()

    def init(self, a):
        for i, x in enumerate(a):
            self.add(i, x)

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

    def sum(self, r):
        r += 1
        ret = 0
        while r>0:
            ret += self.dat[r]
            r -= r & -r 
        return ret


    def lower_bound(self, x):
        """ 累積和がx以上になる最小のindexと、その直前までの累積和 """
        sum_ = 0
        pos = 0
        for i in range(self.depth, -1, -1):
            k = pos + (1 << i)
            if k <= self.size and sum_ + self.dat[k] < x:
                sum_ += self.dat[k]
                pos += 1 << i
        return pos  


    def get_original_sequence(self):
        ret = self.get_aggrigate_sequence()
        for i in range(self.size-1, 0, -1):
            ret[i] -= ret[i-1]
        return ret

    def get_aggrigate_sequence(self):
        return [bit.sum(i) for i in range(self.size)]

    def __str__(self):
        seq = self.get_original_sequence()
        ret = 'original :' + ' '.join(map(str, seq))
        ret += '\n'
        seq = self.get_aggrigate_sequence()
        ret += 'aggrigate:' + ' '.join(map(str, seq))
        return ret

class BitRAQ:
    def __init__(self, size):
        self.size = size
        self.bit0 = BinaryIndexedTree(size)
        self.bit1 = BinaryIndexedTree(size)

    def init(self, a):
        self.bit0.init(a)

    def add(self, l, r, x):
        self.bit0.add(l, -x * (l - 1))
        self.bit0.add(r, x * (r - 1))
        self.bit1.add(l, x)
        self.bit1.add(r, -x)

    def sum(self, r):
        return self.bit0.sum(r) + self.bit1.sum(r) * r

mod = 998244353
n, k = map(int, input().split())
lr = [list(map(int,input().split())) for _ in range(k)]
bit = BitRAQ(2*10**5+100)
bit.bit0.add(1,1)
for i in range(1,n):
    cnt = bit.sum(i) - bit.sum(i-1)
    cnt %= mod
    for l, r in lr:
        bit.add(i+l, i+r+1, cnt)
ret = bit.sum(n) - bit.sum(n-1)
ret %= mod
print(ret)

Solution (Python):

import sys
input = sys.stdin.readline
MOD = 998244353

n, k = map(int, input().split())
dp = [0] * n
dp[0] = 1
dp[1] = -1
delta = []
for _ in range(k):
    l, r = map(int, input().split())
    delta.append((l, 1))
    delta.append((r+1, -1))

total = 0
for i in range(n):
    total += dp[i]
    total %= MOD
    for p, d in delta:
        if i + p >= n:
            continue
        dp[i + p] += total * d
        dp[i + p] %= MOD
print(total % MOD)

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
dp = [0]*(2*n+1)
dp[0] = 1
dp[1] = -1
now = 1
for i in range(n):
    for l, r in lr:
        dp[i+l] += now
        dp[i+r+1] -= now
    now += dp[i+1]
    now %= mod
ans = 0
for i in range(n):
    ans += dp[i]
    ans %= mod
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

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

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

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

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

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

mod = 998244353

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

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

for i in range(n):
    p = i + 1
    temp = 0
    for j in range(k):
        s, t = move[j]
        r = max(0, p - s)
        l = max(0, p - t - 1)
        temp += ruiseki[r] - ruiseki[l]
    dp[p] += temp % mod
    ruiseki[p] = ruiseki[p - 1] + dp[p]

print(dp[n])

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

nums = []

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




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

for i in range(2, N + 1):
    for l, r in nums:
        
        if i - l > 0:
            
            
            dp[i] += (cumsum[i - l] - cumsum[max(i - r - 1, 0)]) % MOD
    cumsum.append(cumsum[-1] + dp[i])

print(dp[-1] % MOD)

Solution (Python):
import math
import collections
import bisect
from collections import deque
from copy import copy, deepcopy
import time

import numpy as np
import numba
from numba import njit, b1, i4, i8, f8
from numba import jit

mod = 998244353


def main():
    N,K = map(int,input().split())
    R = []
    L = []
    ans = [0 for i in range(N+1)]
    cumsum = [0 for i in range(N+1)]
    ans[1]=1
    ans[2]=-1
    cumsum[1]=1
    for i in range(K):
        r,l = map(int,input().split())
        R.append(r)
        L.append(l)
    for i in range(1,N+1):
        
        
        
        for j in range(K):
            if i+R[j]<=N:
                ans[i+R[j]]+=cumsum[i]
                ans[i+R[j]]%=mod
            if i+L[j]+1<=N:
                ans[i+L[j]+1]-=cumsum[i]
                ans[i+L[j]+1]%=mod
        if i<N:
            cumsum[i+1]=cumsum[i]+ans[i+1]
            cumsum[i+1]%=mod
        
    print(cumsum[N]%mod)
if __name__ == '__main__':
    main()

Solution (Python):
MOD = 998244353
N, K = map(int, input().split())
kukan = [None] * K
sums = [0] * (N+2)
path = [0] * (N+1)

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


path[1] = 1
sums[0] = 0
sums[1] = 1
for i in range(2, N+1):
  total = 0
  for j in range(K):
    l, r = kukan[j]
    if l >= i:
      continue
    if r >= i:
      r = i-1
    total = (total + sums[i - l] - sums[i - r - 1] + MOD) % MOD
  path[i] = total
  sums[i] = (sums[i-1] + total) % MOD

print(path[N])

Solution (Python):
N,K = map(int, input().split())

MOD = 998244353

PAT = []
for _ in range(K):
  l,r = map(int, input().split())
  PAT.append((l,r))
  
IMOS = [0] * (N+10)
IMOS[1] = 1
for i in range(0,N):
  if IMOS[i] == 0:
    continue
  for l,r in PAT:
    if i+l > N+1:
      continue
    IMOS[i+l] += IMOS[i]
    if i+r-1 > N+1:
      continue
    IMOS[i+r+1] -= IMOS[i]
  
  IMOS[i+1] += IMOS[i]
  IMOS[i+1] %= MOD
  
print((IMOS[N] - IMOS[N-1]) % MOD)

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

Solution (Python):
import sys
MAX_INT = int(10e12)
MIN_INT = -MAX_INT
mod = 998244353
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N,K = IL()
lr = [IL() for i in range(K)]
lr.sort()

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

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

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

Solution (Python):

printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**18

R = 998244353

def ddprint(x):
  if DBG:
    print(x)

n,k = inm()
l = []
r = []
for i in range(k):
    ll,rr = inm()
    l.append(ll)
    r.append(rr)
a = [0]*n
c = [0]*(n+1)
a[0] = c[0] = 1
for i in range(1,n):
    for j in range(k):
        if i-l[j]>=0:
            a[i] = (a[i]+c[i-l[j]]-c[max(0,i-r[j])-1])%R
    c[i] = (c[i-1]+a[i])%R
print(a[n-1])

Solution (Python):
N, K = map(int, input().split())

Q = 998244353
L, R = [], []

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

P = [0] * N
P[0] = 1

C = [0] * N
C[0] = 1
S = 1

for i in range(1, N):
    for l, r in zip(L, R):
        if l > i:
            break
        
        if r >= i:
            P[i] += C[i-l]
        else:
            s = C[i-l] - C[i-r-1]
            if s < 0:
                s += Q
            P[i] += s

        P[i] = P[i] % Q
    S += P[i]
    S %= Q
    C[i] = S


print(P[-1])

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

N = 2 * n


data0 = [0]*(N+1)
data1 = [0]*(N+1)

mod = 998244353

def _add(data, k, x):
    while k <= N:
        x %= mod
        data[k] += x
        data[k] %= mod
        k += k & -k
def add(l, r, x):
    _add(data0, l, -x*(l-1)%mod)
    _add(data0, r, x*(r-1)%mod)
    _add(data1, l, x)
    _add(data1, r, -x)


def _get(data, k):
    s = 0
    while k:
        s += data[k]
        s %= mod
        k -= k & -k
    return s
def query(l, r):
    return _get(data1, r-1) * (r-1) + _get(data0, r-1) - _get(data1, l-1) * (l-1) - _get(data0, l-1)

add(1, 2, 1)
for i in range(n):
    now = query(i+1, i+2) 
    for l, r in lrl:
        add(l+i+1, r+i+2, now % mod)

print(query(n, n+1) % mod)

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

    dp = [0]*(n*2 + 100)
    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 LR:
            if i + l > n:
                continue
            dp[l + i] = (dp[l+i] + dp[i])%mod
            dp[r + i + 1] = dp[r+i+1] - dp[i]  if dp[r+i+1] - dp[i] > 0 else dp[r+i+1] - dp[i] + 998244353
    print(dp[n]%998244353) 
    return

if __name__ == "__main__":
    main()

Solution (Python):
def resolve():
    import sys
    input = sys.stdin.readline
    mod = 998244353
    n, k = map(int, input().split())
    dp = [0] * n
    dp[0] = 1
    s = [tuple(map(int, input().split())) for _ in range(k)]
    total = 0
    for i in range(n - 1):
        total = (total + dp[i]) % mod
        for l, r in s:
            if i + l < n:
                dp[i + l] += total
                if i + r + 1 < n:
                    dp[i + r + 1] -= total
    print(dp[-1] % mod)


if __name__ == '__main__':
    resolve()

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

mod = 998244353

class BinaryIndexedTree() :
  def __init__(self, n, mod) :
    self.n = n
    self.mod = mod
    self.tree = [0] * (n + 1)
      
  def sum(self, i) :
    s = 0
    while i > 0 :
      s += self.tree[i]
      i -= i & -i
    return s
      
  def add(self, i, x) :
    while i <= self.n :
      self.tree[i] += x
      self.tree[i] %= mod
      i += i & -i
      
BIT = BinaryIndexedTree(N * 2, mod)
BIT.add(1, 1)
BIT.add(2, -1)
for i in range(1, N) :
  for l, r in LR :
    x = BIT.sum(i)
    BIT.add(i + l, x)
    BIT.add(i + r + 1, -x)

print(BIT.sum(N) % mod)

Solution (Python):
n,k= list(map(int, input().split()))
INF=998244353
s=[]
for i in range(k):
    j,jj=map(int,input().split())
    s.append([l for l in range(j,jj+1)])
pattern=[0 for i in range(n)]
pattern[0]=1
ls=len(s)
memo=[0 for i in range(k)]
s.sort()
for i in range(1,n):
    tmp=0
    for index,j in enumerate(s):
        if i-j[0]<0:
            break
        elif i-j[-1]>0:
            memo[index]+=pattern[i-j[0]]
            memo[index]-=pattern[i-j[-1]-1]
            if memo[index]<0:
                memo[index]+=INF
        else:
            memo[index]+=pattern[i-j[0]]

        
        memo[index]%=INF
    pattern[i]=(sum(memo)%INF)
print(pattern[-1])

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil,pi,factorial
    from operator import itemgetter
    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    def LI2(): return [int(input()) for i in range(n)]
    def MXI(): return [[LI()]for i in range(n)]
    def SI(): return input().rstrip()
    def printns(x): print('\n'.join(x))
    def printni(x): print('\n'.join(list(map(str,x))))
    inf = 10**17
    mod = 998244353

    n,k=MI()
    area=[LI() for i in range(k)]
    
    
    m=2*n
    BIT = [0]*(2*n+1)
    
    
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]%mod
            idx -= idx&(-idx)
        return res_sum%mod
    
    
    def BIT_update(idx,x):
        while idx <= m:
            BIT[idx] += x%mod
            idx += idx&(-idx)
        return
    BIT_update(n+1,1)
    
    for i in range(n+2,2*n+1):
        ans=0
        for j in range(k):
            l,r=area[j]
            
            
            ans=(ans+BIT_query(i-l)-BIT_query(i-r-1))%mod
        
        BIT_update(i,ans%mod)
        
    
    print((BIT_query(2*n)-BIT_query(2*n-1))%mod)
            

    
        
        
        
        
    
        
                    
            
        



        
        
        
        
        
    
if __name__=="__main__":
    main()

Solution (Python):
import sys

input = sys.stdin.readline

N, K = map(int, input().split())
S = set()
for _ in range(K):
    l, r = map(int, input().split())
    S.add((l, r))

mod = 998244353
dp = [0 for _ in range(N+1)]
dp[1] = 1
acc = [0 for _ in range(N+1)]
acc[1] = 1
for i in range(1, N+1):
    for (l, r) in S:
        left = max(i - r - 1, 0)
        right = max(i - l, 0)
        
        dp[i] += acc[right] - acc[left]
        dp[i] %= mod
    acc[i] = acc[i-1] + dp[i]
    acc[i] %= mod


print(dp[N])

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

mod = 998244353

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)
        self.depth = n.bit_length()

    def __iter__(self):
        psum = 0
        for i in range(self.size):
            csum = self.sum(i+1)
            yield csum - psum
            psum = csum
        raise StopIteration()

    def __str__(self):  
        return str(list(self))

    def sum(self, i):
        
        if not (0 <= i <= self.size): raise ValueError("error!")
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        if not (0 <= i < self.size): raise ValueError("error!")
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def lower_bound(self, x):
        """ 累積和がx以上になる最小のindexと、その直前までの累積和 """
        sum_ = 0
        pos = 0
        for i in range(self.depth, -1, -1):
            k = pos + (1 << i)
            if k <= self.size and sum_ + self.tree[k] < x:
                sum_ += self.tree[k]
                pos += 1 << i
        return pos + 1, sum_

    def __getitem__(self, key):
        if not (0 <= key < self.size): raise IndexError("error!")
        return self.sum(key+1) - self.sum(key)

    def __setitem__(self, key, value):
        
        if not (0 <= key < self.size): raise IndexError("error!")
        self.add(key, value - self[key])

class BitImos:
    """
    ・範囲すべての要素に加算
    ・ひとつの値を取得
    の2種類のクエリをO(logn)で処理
    bit = BitImos(len(li))
    """
    def __init__(self, n):
        self.bit = Bit(n+1)

    def add(self, s, t, x):
        
        self.bit.add(s, x)
        self.bit.add(t, -x)

    def get(self, i):
        return self[i]

    def __getitem__(self, key):
        
        return self.bit.sum(key+1)

b = BitImos(n)
b.add(0,1,1)

for i in range(n):
    tmp = b.get(i)
    tmp %= mod
    for l1,r1 in lr:
        if i + l1 < n:
            b.add(i+l1, min(i+r1+1, n), tmp)

print(b.get(n-1) % mod)

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

mod = 998244353
        
table = [0]*N
table[0] = 1
TABLE = [0]*N
TABLE[0] = 1

for i in range(1, N):
    TABLE[i] = TABLE[i-1]
    for L, R in S:
        l = i-L
        r = i-R-1
        if r >= 0:
            table[i] += TABLE[l] - TABLE[r]
            table[i] %= mod
            TABLE[i] += TABLE[l] - TABLE[r]
            TABLE[i] %= mod
        elif l >= 0 and r < 0:
            table[i] += TABLE[l]
            table[i] %= mod
            TABLE[i] += TABLE[l]
            TABLE[i] %= mod
            
print(table[N-1]%mod)

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

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

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,k = list(map(int, input().split()))
lr = [tuple(map(int, input().split())) for _ in range(k)]
lr.sort()
dp = [0]*(n)
cum = [0]*(n)
dp[0] = 1
cum[0] = 1
vals = [0] * k
M = 998244353
for i in range(1,n):
    for j,(l,r) in enumerate(lr):

        if i-l>=0:
            tmp = cum[max(i-l,0)]
            if i-r-1>=0:
                tmp -= cum[max(0, i-r-1)]
            vals[j] = tmp
            vals[j] %= M
    dp[i] = sum(vals)
    dp[i] %= M    
    cum[i] = cum[i-1] + dp[i]
    cum[i] %= M
ans = dp[n-1]%M
print(ans%M)

Solution (Python):

import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**12
m = 998244353


def main():
    N, K = map(int, input().split())
    dp = [0] * (N + 1)
    LR = [list(map(int, input().split())) for _ in range(K)]
    dp[1] = 1
    for i in range(1, N):
        for j in range(K):
            if i + LR[j][0] <= N:
                dp[i + LR[j][0]] += dp[i]
                dp[i + LR[j][0]] %= m
            if i + LR[j][1] < N:
                dp[i + LR[j][1]+1] -= dp[i]
                dp[i + LR[j][1]+1] %= m
        
        if i < N-1:
            dp[i + 2] += dp[i+1]
            dp[i + 2] %= m
    print(dp[N])


if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.buffer.readline

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

MOD = 998244353

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

class SegmentTreeDual():
    def __init__(self, arr, op=lambda x, y: y if y != -1 else x, ie=-1):
        self.h = (len(arr) - 1).bit_length()
        self.n = 2**self.h
        self.ie = ie
        self.op = op
        self.val = [ie for _ in range(self.n)]
        self.laz = [ie for _ in range(2 * self.n)]
        for i in range(len(arr)):
            self.val[i] = arr[i]

    def propagate(self, k):
        if self.laz[k] == self.ie: return
        if self.n <= k:
            self.val[k - self.n] = self.op(self.val[k - self.n], self.laz[k])
        else:
            self.laz[2 * k] = self.op(self.laz[2 * k], self.laz[k])
            self.laz[2 * k + 1] = self.op(self.laz[2 * k + 1], self.laz[k])
        self.laz[k] = self.ie

    def update(self, lt, rt, x):
        lt += self.n
        rt += self.n
        while rt - lt > 0:
            if lt & 1:
                self.laz[lt] = self.op(self.laz[lt], x)
                self.laz[lt] %= MOD
                lt += 1
            if rt & 1:
                rt -= 1
                self.laz[rt] = self.op(self.laz[rt], x)
                self.laz[rt] %= MOD
            lt >>= 1
            rt >>= 1

    def get(self, idx):
        res = self.val[idx]
        idx += self.n
        while idx:
            res = self.op(res, self.laz[idx])
            res %= MOD
            idx >>= 1
        return res

from operator import add

arr = [0] * N
arr[0] = 1

S = SegmentTreeDual(arr, add, 0)

for i in range(N - 1):
    s = S.get(i)
    for l, r in I:
        S.update(min(i + l, N), min(i + r + 1, N), s)

print(S.get(N - 1) % MOD)

Solution (Python):
class BITRAQ:
    def __init__(self, n, mod):
        self.n = n + 1
        self.mod = mod
        self.bit = [[0]*(self.n) for _ in range(2)]
    
    def add_sub(self, p, i, x):
        while i < self.n:
            self.bit[p][i] += x
            self.bit[p][i] %= self.mod
            i += i & -i
    
    def add(self, l, r, x):
        self.add_sub(0, l, -x * (l - 1))
        self.add_sub(0, r, x * (r - 1))
        self.add_sub(1, l, x)
        self.add_sub(1, r, -x)

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

    def get(self, i):
        return self.sum(i) % self.mod - self.sum(i - 1) % self.mod

p = 998244353

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

hop = []

for i in range(K):
    hop.append(tuple(map(int, input().split())))

dp = BITRAQ(N, p)

dp.add(1, 2, 1)

for i in range(N - 1):
    for j in range(K):
        dp.add(i + hop[j][0] + 1, min(N + 1, i + hop[j][1] + 2), dp.get(i + 1) % p)

print(dp.get(N) % p)

Solution (Python):

from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 998244353
INF = float("inf")

sys.setrecursionlimit(1000000)

def main():
    N, K = LI()
    LR = LIR(K)
    cumsum = [0] * (N+2)

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

    for i in range(N-1, 0, -1):
        for l, r in LR:
            dp[i] = (dp[i] + cumsum[min(i + l, N+1)] - cumsum[min(i + r + 1, N+1)]) % MOD

        cumsum[i] = (cumsum[i] + dp[i] + cumsum[i+1]) % MOD

    print(dp[1])


if __name__ == '__main__':
    main()

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

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

Solution (Python):
MOD = 998244353
n, k = (int(x) for x in input().split())
LR = [tuple(int(x) for x in input().split()) for _ in range(k)]
LR.sort()
dp = [0] * (n + 1)
dp[1] = 1
dp[2] = -1
for i in range(1, n + 1):
    dp[i] += dp[i - 1] % MOD
    dp[i] %= MOD
    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

print(dp[n] % MOD)

Solution (Python):
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod = 998244353
INF = 10**18
eps = 10**-7

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



dp = [0]*(2*n+10)

imos = [0]*(2*n+10)
dp[1] = 1
for i in range(1,n+1):
    imos[i] = (imos[i-1]+imos[i])%mod
    dp[i] = (dp[i]+imos[i])%mod
    for (l,r) in LR:
        imos[i+l] += dp[i]
        imos[i+r+1] -= dp[i]

print(dp[n])