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 = []
for _ in range(k):
    lr.append(tuple(map(int, input().split())))
mod = 998244353

dp = [0]*n
dp[0] = 1

acc = [0]*n
acc[0] = 1

for i in range(1, n):
    for l, r in lr:
        if 0 <= i-r and i-l < i:
            dp[i] += acc[i-l]-acc[i-r-1]
        elif i-r < 0 and i-l < i:
            dp[i] += acc[i-l]
        elif i-r < 0 and i <= i-l:
            dp[i] += acc[i-1]
        elif 0 < i-r and i <= i-l:
            dp[i] += acc[i-1]-acc[i-r-1]
    acc[i] = acc[i-1]+dp[i]%mod

print(dp[-1]%mod)

Solution (Python):
N, K = map(int, input().split())
mod = 998244353
lr = [0] * K
for i in range(K):
    lr[i] = list(map(int, input().split()))
    lr[i][1] += 1

dp = [0] * (N+1)
dp[1] = 1
s = 0
for i in range(1, N):
    s += dp[i]
    for j in range(K):
        if (i + lr[j][0]) <= N:
            dp[i + lr[j][0]] = (dp[i + lr[j][0]] + s) % mod
        if (i + lr[j][1]) <= N:
            dp[i + lr[j][1]] = (dp[i + lr[j][1]] - s) % mod
        

print(dp[N])

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

Solution (Python):
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
s=0
for i in range(n):
  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-1])

Solution (Python):
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
s=0
for i in range(n):
  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-1])

Solution (Python):
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 l, r in lr:
        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])

Solution (Python):
n,k = map(int,input().split())
mod = 998244353

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

dp = [0 for i in range(n)]
dp[0] = 1
ruiseki = [0 for i in range(n+1)]
ruiseki[1] = 1

for i in range(1,n):
    for l,r in kukan:
        l = i - l
        r = i - r
        l,r = r,l
        if r < 0:
            continue
        elif l >= 0:
            dp[i] += (ruiseki[r] - ruiseki[l])%mod
        else:
            dp[i] += (ruiseki[r])%mod
    ruiseki[i+1] = (ruiseki[i] + dp[i])

print(dp[-1]%mod)

Solution (Python):
def readinput():
    n,k=map(int,input().split())
    lr=[]
    for _ in range(k):
        l,r=map(int,input().split())
        lr.append((l,r))
    return n,k,lr

def main(n,k,lr):
    lrs=sorted(lr,key=lambda x:x[0])
    MOD=998244353
    dp=[0]*(n+1)
    dp[1]=1
    for i in range(1,n):
        
        if dp[i]==0:
            continue
        skip=False
        for l,r in lrs:
            for j in range(l,r+1):
                
                if i+j>n:
                    skip=True
                    break
                dp[i+j]=(dp[i+j]+dp[i])%MOD
                
            if skip:
                break
    return dp[n]

def main2(n,k,lr):
    lrs=sorted(lr,key=lambda x:x[0])
    MOD=998244353
    dp=[0]*(n+1)
    ruiseki=[0]*(n+1)
    dp[1]=1
    ruiseki[1]=1
    for i in range(2,n+1):
        for l,r in lrs:
            if i-l<1:
                break
            dp[i]+=ruiseki[i-l]-ruiseki[max(1,i-r)-1]
        dp[i]=dp[i]%MOD
        ruiseki[i]=(ruiseki[i-1]+dp[i])%MOD
    return dp[n]

if __name__=='__main__':
    n,k,lr=readinput()
    ans=main2(n,k,lr)
    print(ans)

Solution (Python):
import sys

input = sys.stdin.readline

mod = 998244353

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

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

a = [0] * n
a[0] = 1
a[1] = -1
f = [1]

for i in range(n - 1):
    for l, r in lr:
        if i + l < n:
            a[i + l] += f[i]
            a[i + l] %= mod
        else:
            break
        if i + r + 1 < n:
            a[i + r + 1] -= f[i]
            a[i + r + 1] %= mod
        else:
            break
    f.append((f[i] + a[i + 1]) % mod)
print(f[n - 1])

Solution (Python):

import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys
sys.setrecursionlimit(10**6)

readline = sys.stdin.readline

INF = 1 << 60


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap

MOD = 998244353

class ModInt:
    def __init__(self, x=0):
        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)) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2))
        )

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

    __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)) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2))
        )

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

@mt
def slv(N, K, LR):

    memo = [ModInt(0)] * (N+2)
    memo[1] = 1
    memo[1+1] = -1
    for i in range(1, N+1):
        memo[i] += memo[i-1]
        for l, r in LR:
            ll = min(N+1, i+l)
            rr = min(N+1, i+r+1)
            memo[ll] += memo[i]
            memo[rr] -= memo[i]

    return memo[N]


def main():
    N, K = read_int_n()
    LR = [read_int_n() for _ in range(K)]
    print(slv(N, K, LR))


if __name__ == '__main__':
    main()

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

Solution (Python):

import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys
sys.setrecursionlimit(10**6)

readline = sys.stdin.readline

INF = 1 << 60


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


class ModInt:
    def __init__(self, x=0, M=10**9+7):
        self.m = M
        self.x = x % self.m

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

    __repr__ = __str__

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

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

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

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

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

    __radd__ = __add__

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

    __rmul__ = __mul__

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

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


@mt
def slv(N, K, LR):
    M = 998244353
    memo = [ModInt(0, M)] * (N+2)
    memo[1] = 1
    memo[1+1] = -1
    for i in range(1, N+1):
        memo[i] += memo[i-1]
        for l, r in LR:
            ll = min(N+1, i+l)
            rr = min(N+1, i+r+1)
            memo[ll] += memo[i]
            memo[rr] -= memo[i]

    return memo[N]


def main():
    N, K = read_int_n()
    LR = [read_int_n() for _ in range(K)]
    print(slv(N, K, LR))


if __name__ == '__main__':
    main()

Solution (Python):
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():

    mod = 998244353
    n, k = LI()
    l = [0 for _ in range(k)]
    r = [0 for _ in range(k)]

    for i in range(k):
        l[i], r[i] = LI()

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

    for i in range(2,n+1):
        for el, er in zip(l, r):
            dp[i] += dpsum[max(i-el, 0)] - dpsum[max(i-er-1, 0)]
        dp[i] %= mod
        dpsum[i] = (dpsum[i-1] + dp[i])%mod

    print(dp[n])

main()

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

Solution (Python):

import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys
sys.setrecursionlimit(10**6)

readline = sys.stdin.readline

INF = 1 << 60


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


class LazySegmentTree():
    def __init__(self, op, e, mapping, composition, im, init_array):
        self.op = op
        self.e = e
        self.mapping = mapping
        self.composition = composition
        self.im = im

        l = len(init_array)

        def ceil_pow2(n):
            x = 0
            while (1 << x) < n:
                x += 1
            return x
        self.log = ceil_pow2(l)
        self.size = 1 << self.log
        self.d = [e() for _ in range(2*self.size)]
        self.lz = [im() for _ in range(self.size)]

        for i, a in enumerate(init_array):
            self.d[i+self.size] = a

        for i in range(self.size-1, 0, -1):
            self.__update(i)

    def set(self, p, x):
        p += self.size

        for i in range(self.log, 0, -1):
            self.__push(p >> i)

        self.d[p] = x

        for i in range(1, self.log+1):
            self.__update(p >> i)

    def __getitem__(self, p):
        p += self.size
        for i in range(self.log, 0, -1):
            self.__push(p >> i)
        return self.d[p]

    def prod(self, l, r):
        if l == r:
            return self.e()

        l += self.size
        r += self.size

        for i in range(self.log, 0, -1):
            if ((l >> i) << i) != l:
                self.__push(l >> i)
            if ((r >> i) << i) != r:
                self.__push(r >> i)

        sml = self.e()
        smr = self.e()

        while l < r:
            if l & 1:
                sml = self.op(sml, self.d[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.op(self.d[r], smr)
            l >>= 1
            r >>= 1

        return self.op(sml, smr)

    def apply(self, l, r, f):
        if l == r:
            return

        l += self.size
        r += self.size

        for i in range(self.log, 0, -1):
            if ((l >> i) << i) != l:
                self.__push(l >> i)
            if ((r >> i) << i) != r:
                self.__push((r-1) >> i)

        l2, r2 = l, r
        while l < r:
            if l & 1:
                self.__all_apply(l, f)
                l += 1
            if r & 1:
                r -= 1
                self.__all_apply(r, f)
            l >>= 1
            r >>= 1
        l, r = l2, r2

        for i in range(1, self.log+1):
            if ((l >> i) << i) != l:
                self.__update(l >> i)
            if ((r >> i) << i) != r:
                self.__update((r-1) >> i)

    def __update(self, k):
        self.d[k] = self.op(self.d[2*k], self.d[2*k+1])

    def __all_apply(self, k, f):
        self.d[k] = self.mapping(f, self.d[k])
        if k < self.size:
            self.lz[k] = self.composition(f, self.lz[k])

    def __push(self, k):
        self.__all_apply(2*k, self.lz[k])
        self.__all_apply(2*k+1, self.lz[k])
        self.lz[k] = self.im()


M = 998244353

def e():
    return 0

def op(sl, sr):
    return (sl + sr) % M

def mapping(fl, sr):
    return (fl + sr) % M

def composition(fl, fr):
    return (fl + fr) % M

def im():
    return 0

@mt
def slv(N, K, LR):
    memo = LazySegmentTree(op, e, mapping, composition, im, [0]*(N+1))
    memo.apply(1, 1+1, 1)
    for i in range(1, N+1):
        n = memo[i]
        for l, r in LR:
            ll = min(N+1, i+l)
            rr = min(N+1, i+r+1)
            memo.apply(ll, rr, n)

    return memo[N]


def main():
    N, K = read_int_n()
    LR = [read_int_n() for _ in range(K)]
    print(slv(N, K, LR))


if __name__ == '__main__':
    main()

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

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

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=998244353
    N,K=MI()
    
    dp=[0]*N
    dp[0]=1
    
    L=[0]*K
    R=[0]*K
    for i in range(K):
        L[i],R[i]=MI()
    
    
    for i in range(N-1):
        for k in range(K):
            l= i + L[k]
            r= i + R[k] +1
            if l<N:
                dp[l]+=dp[i]
                dp[l]%=mod
            if r<N:
                dp[r]-=dp[i]
                dp[r]%=mod
        if i!=0:
            dp[i+1]+=dp[i]
        dp[i+1]%=mod
        
                
    print(dp[-1])
            
            

main()

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

Solution (Python):
def resolve():
    mod=998244353
    n,k=map(int,input().split())
    d=[[],[]]
    for _ in range(k):
        l,r=map(int,input().split())
        d[0].append(l)
        d[1].append(r)
    dp=[0]*(n+1)
    a=[0]*(n+2)
    a[1]=dp[1]=1
    for i in range(2,n+1):
        for j in range(k):
            if i-d[0][j]>0:
                dp[i]=(dp[i]+a[i-d[0][j]]-a[max(i-d[1][j]-1,0)]+mod)%mod
        
        a[i]=(a[i-1]+dp[i])%mod
    print(dp[n])
resolve()

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

Solution (Python):
def resolve():
    MOD = 998244353
    N, K = map(int, input().split())
    S = [tuple(map(int, input().split())) for _ in range(K)]
    L = [0] * K
    R = [0] * K
    L, R = zip(*S)

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

    dp_acum = [0] * (N + 1)
    dp_acum[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] += dp_acum[ri] - dp_acum[li - 1]
            dp[i] %= MOD

        dp_acum[i] = dp_acum[i - 1] + dp[i]
        dp_acum[i] %= MOD

    print(dp[N])


if __name__ == "__main__":
    resolve()

Solution (Python):
mod = 998244353
n,k =map(int,input().split())
step =[0]*(n+1)

step[1]=1
stepsum=[0]*(n+1)
stepsum[1]=1
l=[0]*k
r=[0]*k
for i in range(k):
    l[i],r[i]=map(int,input().split())

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


print(step[n]%mod)

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

Solution (Python):

import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys
sys.setrecursionlimit(10**6)

readline = sys.stdin.readline

INF = 1 << 60


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K, LR):
    M = 998244353
    memo = [0] *(N+2)
    memo[1] = 1
    memo[1+1] = -1
    for i in range(1, N+1):
        memo[i] += memo[i-1]
        memo[i] %= M
        for l, r in LR:
            ll = min(N+1, i+l)
            rr = min(N+1, i+r+1)
            memo[ll] += memo[i]
            memo[ll] %= M
            memo[rr] -= memo[i]
            memo[rr] %= M

    return memo[N]


def main():
    N, K = read_int_n()
    LR = [read_int_n() for _ in range(K)]
    print(slv(N, K, LR))


if __name__ == '__main__':
    main()

Solution (Python):


def input_int_array():
    return map(int, input().split())


MOD = 998244353


def answer():
    n, k = input_int_array()
    spans = [tuple(input_int_array()) for x in range(k)]

    count = [0] * (n)
    count[0] = 1
    accum = [0] * (n + 1)
    accum[1] = 1

    for i in range(1, n):
        j = i + 1
        for l, r in spans:
            start = max(0, j - r - 1)
            end = max(0, j - l)
            count[i] += accum[end] - accum[start]
        accum[j] = accum[j-1] + count[i] % MOD
    print(count[n-1] % MOD)


answer()

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from collections import deque
from collections import Counter
import bisect
from collections import defaultdict
import itertools
def main():
    mod = 998244353
    N, K = MI()
    sec = []
    for i in range(K):
        l, r = MI()
        sec.append((l, r))
    dp = [0 for _ in range(N + 1)]
    dpsum = [0 for _ in range(N + 1)]
    dp[0] = 1
    dpsum[0] = 1
    for i in range(1, N):
        for j in range(K):
            li = i - sec[j][1]
            ri = i - sec[j][0]
            if ri < 0:
                continue
            li = max(li, 0)
            dp[i] += (dpsum[ri] - dpsum[li - 1]) % mod
            dp[i] %= mod
        dpsum[i] = (dpsum[i - 1] + dp[i]) % mod
    print(dp[N - 1])
if __name__ == "__main__":
    main()

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

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

Solution (Python):

n,k=map(int,input().split())
*lr,=[tuple(map(int, input().split())) for _ in range(k)]
res =[0]*(2*n+3)

diff=[0]*(2*n+3)



diff[0]=1
diff[1]=-1
mod=998244353

for i in range(n+1):
    res[i]=res[i-1]+diff[i]
    res[i]%=mod
    diff[i]%=mod
    for li,ri in lr:
        diff[i+li]+=res[i]
        diff[i+ri+1]-=res[i]
    
    
print(res[n-1]%mod)

Solution (Python):

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

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

Solution (Python):
n,k=map(int,input().split())
k_list=[]

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

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

for i in range(1,n):
    dpsum[i]=dp[i]+dpsum[i-1]
    for j in range(k):
        l,r=k_list[j]
        li=i+l
        ri=i+r+1
        if li<=n:
            dp[li]+=dpsum[i]
            dp[li]=dp[li]%998244353
        if ri<=n:
            dp[ri]-=dpsum[i]
            dp[ri]=dp[ri]%998244353

print(dp[n])