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 collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() 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)]
mod = 998244353
inf = float("INF")
class BinaryIndexedTree:
    
    def __init__(self, size):
        """
        :param int size:
        """
        self.bit = [0 for _ in range(size)]
        self.size = size

    def add(self, i, w):
        """
        i番目にwを加える
        :param int i:
        :param int w:
        :return:
        """
        if i < 0:
            return
        x = i + 1
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        return

    def sum(self, i):
        """
        [0,i]の合計
        :param int i:
        :return:
        """
        res = 0
        x = i + 1
        while x > 0:
            res += self.bit[x - 1]
            x -= x & -x
        return res

    def search(self, x):
        """
        二分探索。和がx以上となる最小のインデックス(>= 1)を返す
        :param int x:
        :return :
        """
        i = 0
        s = 0
        step = 1 << self.size.bit_length()
        while step:
            if i + step <= self.size and s + self.bit[i + step - 1] < x:
                print(self.bit[i + step - 1], i, step)
                i += step
                s += self.bit[i - 1]
            step >>= 1
        return i

    def __len__(self):
        return self.size
    
    def __str__(self):
        res = [None] * self.size
        for i in range(self.size):
            res[i] = str(self.sum(i) -self.sum(i - 1))
        return ", ".join(res)

def solve():
    n, k = LI()
    lr = LIR(k)
    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = -1
    for i in range(1, n):
        for l, r in lr:
            if i + l <= n:
                dp[i + l] += dp[i]
                if i + r + 1 <= n:
                    dp[i + r + 1] -= dp[i]
        dp[i + 1] = (dp[i+1]+dp[i])%mod
    print(dp[-1])


    return



if __name__ == '__main__':
    solve()

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

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

dp[0] = 1
dp[1] = -1

for i in range(0, n):
    if i>0: dp[i] += dp[i-1]
    dp[i] %= 998244353
    for l,r in lr:
        if i+l > n: continue
        dp[i+l] += dp[i]
        dp[min(n, i+r+1)] -= dp[i]

print(dp[-2] % 998244353)

Solution (Python):
def mod(val, mod_base):
  if val >= mod_base:
    return val%mod_base
  return val


def resolve():
  base = 998244353
  N, K = map(int, input().split(" "))

  LRs = []
  for _ in range(K):
    (L, R) = map(int, input().split(" "))
    LRs.append((L, R))

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

  for i in range(1, N):
    dp[i] += dp[i-1]

    for lr in LRs:
      left = i + lr[0]
      right = i + lr[1] + 1
      if left <= N:
        dp[left] += dp[i]
        dp[left] = mod(dp[left], base)
      if right <= N:
        dp[right] -= dp[i]
        dp[right] = mod(dp[right], base)
  print(mod(dp[-1], base))

if __name__ == "__main__":
  resolve()

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

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


print(dp[n-1])

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


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


print(dp[n-1])

Solution (Python):
import sys









MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

def Main():
    n, k = read_ints()
    mod = 998244353
    dp = [0] * (n + 1)
    dp[0] = 1
    s = 1
    query = [read_int_list() for _ in range(k)]
    
    for i in range(1, n + 1):
        s += dp[i]
        for l, r in query:
            if l + i <= n:
                dp[i + l] = (dp[i + l] + s) % mod
            if r + i + 1 <= n:
                dp[i + r + 1] = (dp[i + r + 1] - s) % mod
    print(dp[n])

if __name__ == '__main__':
    Main()

Solution (Python):
def mod(val, mod_base):
  if val >= mod_base:
    return val%mod_base
  return val


def resolve():
  base = 998244353
  N, K = map(int, input().split(" "))

  LRs = []
  for _ in range(K):
    (L, R) = map(int, input().split(" "))
    LRs.append((L, R))

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

  for i in range(1, N):
    dp_sum[i] = dp[i] + dp_sum[i-1]

    for lr in LRs:
      left = i + lr[0]
      right = i + lr[1] + 1
      if left <= N:
        dp[left] += dp_sum[i]
        dp[left] = mod(dp[left], base)
      if right <= N:
        dp[right] -= dp_sum[i]
        dp[right] = mod(dp[right], base)
  print(mod(dp[-1], base))

if __name__ == "__main__":
  resolve()

Solution (Python):
n, k = [int(_) for _ in input().split()]
s = []
for i in range(k):
    s.append([int(_) for _ in input().split()])
dp = [0 for i in range(n)]
dp[0] = 1
dp_s = [0 for i in range(n+1)]
dp_s[1] = 1
for i in range(1, n):
    for j in range(len(s)):
        r, l = s[j]
        if i-r >= 0:
            if i-l >= 0:
                dp[i] += dp_s[i-r+1] - dp_s[i-l]
            else:
                dp[i] += dp_s[i-r+1] - dp_s[0]
    dp[i] = dp[i] % 998244353
    dp_s[i+1] += dp_s[i] + dp[i]
    dp_s[i+1] = dp_s[i+1] % 998244353
print(dp[-1])

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

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



for i in range(1, n):
    for j in range(len(s)):
        r, l = s[j]
        if i-r >= 0:
            if i-l >= 0:
                dp[i] += dp_s[i-r+1] - dp_s[i-l]
            else:
                dp[i] += dp_s[i-r+1] - dp_s[0]
    dp[i] = dp[i] % 998244353
    
    dp_s[i+1] += dp_s[i] + dp[i]
    dp_s[i+1] = dp_s[i+1] % 998244353
    
    
print(dp[-1])

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


def solve(N, region):
    dp = [ModInt(0)]*(N+1)
    dp[1] += 1
    dpsum = [ModInt(0)]*(N+1)
    dpsum[1] += 1

    for i in range(2, N+1):
        for r in region:
            left = i - r[1]
            right = i - r[0]
            if right < 0:
                continue
            left = max(left, 0)
            dp[i] += (dpsum[right] - dpsum[left-1])
        dpsum[i] = dpsum[i-1] + dp[i]

    return dp[N]


if __name__ == "__main__":
    N, K = map(int, input().split())
    region = [list(map(int, input().split())) for _ in range(K)]
    print(solve(N, region))

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

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








mod = 998244353
 
for i in range(1, N):
  
  
  for j in range(K):
    r = i - X[j][0]
    l = i - X[j][1]
    if r < 0: continue
    l = max(l, 0)
      
    dp[i] += acc[r+1] - acc[l] 
    dp[i] %= mod
  acc[i+1] = acc[i] + dp[i] 

print(dp[N-1])

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

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

Solution (Python):
n,k=map(int,input().split())
l=[]
mod=998244353
for i in range(k):
  l.append(tuple(map(int,input().split())))

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

Solution (Python):
def li():
    return [int(x) for x in input().split()]


MOD = 998244353
N, K = li()
L, R = [], []
for _ in range(K):
    l, r = li()
    L.append(l)
    R.append(r)



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

for i in range(1, N):
    dp[i+1] += dp[i]
    dp[i+1] %= MOD
    for k in range(K):
        l, r = L[k], R[k]
        dp[i+l] += dp[i]
        dp[i+l] %= MOD
        dp[i+r+1] -= dp[i]
        dp[i+r+1] %= MOD

print(dp[N])

Solution (Python):

n, k = list(map(int, input().split()))
s = list()
for i in range(k):
     l, r = list(map(int, input().split()))
     s.append((l, r))

mod = 998244353
i = 1
dp = [0] * (n+1)
dp[1] = 1
dpsum = [0] * (n+1)
dpsum[1] = 1
for i in range(2, n+1):
    for l, r in s:
        li = i-r
        ri = i-l
        if ri < 1: continue
        li = max(li, 1)
        dp[i] = (dp[i] + dpsum[ri] - dpsum[li-1]) % mod
    dpsum[i] = (dpsum[i-1] + dp[i]) % mod
    
print(dp[n])

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

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

dp = [0]*n
dp[0] = 1
a = [0]*(n+1)
a[1] = dp[0]
for i in range(1, n):
    for j in range(k):
        r = i - d[0][j]
        l = i - d[1][j]
        if l < 1:
            l = 1
        if r < 0:
            continue
        dp[i] += a[r] - a[l-1]
        dp[i] %= 998244353
    a[i+1] = (a[i] + dp[i]) % 998244353
print(dp[-1])

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

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

MOD = 998244353

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

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


for i in range(2, N+1):
    for j in range(len(L_list)):
        if i - R_list[j]-1 < 0:
            R_pos = 0
        else:
            R_pos = i - R_list[j] - 1
        dp[i] += (sdp[i - L_list[j]] - sdp[R_pos])%MOD
        dp[i] %= MOD
    sdp[i] = sdp[i-1] + dp[i]
    sdp[i] %= MOD
    
    
print(dp[N])

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

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

mod = 998244353

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

for i in range(N-1):
    tmp = (tmp + dp[i]) % mod
    
    for l, r in LR:
        dp[min(i+l, N)] = (dp[min(i+l, N)] + tmp) % mod
        dp[min(i+r+1, N)] = (dp[min(i+r+1, N)] - tmp) % mod
print(dp[N-1])

Solution (Python):
MOD = 998244353
n, k = map(int, input().split())
l, r = [0]*k, [0]*k
for i in range(k):
    _l, _r = map(int, input().split())
    l[i], r[i] = _l, _r
dp, dpsum = [0]*(n+1), [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
        li = max(li, 1)
        dp[i] += dpsum[ri] - dpsum[li-1]
        dp[i] %= MOD
    dpsum[i] = dpsum[i-1] + dp[i]
print(dp[n])

Solution (Python):
MOD = 998244353
n, k = map(int, input().split())
l, r = [0]*k, [0]*k
for i in range(k):
    _l, _r = map(int, input().split())
    l[i], r[i] = _l, _r
dp, dpsum = [0]*(n+1), [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
        li = max(li, 1)
        dp[i] += dpsum[ri] - dpsum[li-1]
        dp[i] %= MOD
    dpsum[i] = dpsum[i-1] + dp[i]
print(dp[n])

Solution (Python):
MOD = 998244353


def solve(lr, dp, n):
    acc_dp = [1] * n
    for i in range(1, n):
        val = 0
        for d in lr:
            a = i - d[0]
            if a < 0:
                continue
            b = i - d[1] - 1
            val += acc_dp[a] - (acc_dp[b] if b >= 0 else 0)
        dp[i] = val % MOD
        acc_dp[i] = (acc_dp[i - 1] + dp[i]) % MOD
    return dp[n - 1]


def main():
    f = open(0)
    n, k = [int(x) for x in f.readline().split()]
    lr = [[int(x) for x in f.readline().split()] for _ in range(k)]
    dp = [0] * n
    dp[0] = 1
    ans = solve(lr, dp, n)
    print(ans)

main()

Solution (Python):
def resolve():
  base = 998244353
  N, K = map(int, input().split(" "))

  LRs = []
  for _ in range(K):
    (L, R) = map(int, input().split(" "))
    LRs.append((L, R))

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

  for i in range(2, N+1):
    for lr in LRs:
      left = max(i - lr[1] - 1, 0)
      right = max(i - lr[0], 0)
      dp[i] += dp_sum[right] - dp_sum[left]
      if dp[i] >= base:
        dp[i] %= base
      dp_sum[i] = dp_sum[i-1] + dp[i]
  print(dp[-1])

if __name__ == "__main__":
  resolve()

Solution (Python):
import numpy as np
from numba import njit
from numba.types import i8
ni8 = np.int64
MOD = 998244353


@njit((i8[:,::-1], i8[:], i8, i8), cache=True)
def solve(lr, dp, n, k):
    acc_dp = np.ones_like(dp)
    for i in range(1, n):
        val = 0
        for j in range(k):
            a = i - lr[j, 0]
            if a < 0:
                continue
            b = i - lr[j, 1] - 1
            val += acc_dp[a] - (acc_dp[b] if b >= 0 else 0)
        dp[i] = val % MOD
        acc_dp[i] = (acc_dp[i - 1] + dp[i]) % MOD
    return dp[n - 1]


def main():
    f = open(0)
    n, k = [int(x) for x in f.readline().split()]
    lr = np.fromstring(f.read(), ni8, sep=' ').reshape((-1, 2))
    dp = np.zeros(n, ni8)
    dp[0] = 1
    ans = solve(lr, dp, n, k)
    print(ans)

main()

Solution (Python):
from sys import stdin,stdout
def INPUT():return list(int(i) for i in stdin.readline().split())
def inp():return stdin.readline()
def out(x):return stdout.write(x)
import math
import random
J=998244353

n,k=INPUT()
A=[]
for i in range(k):
    x,y=INPUT()
    A.append([x,y])
A.sort()
s,e=-1,-1
S=[]
for i in range(len(A)):
    if i==0:
        S.append([A[i][0],A[i][1]])
    else:
        if A[i][0]>S[-1][1]:
            S.append([A[i][0],A[i][1]])
        else:
            S[-1][1]=A[i][1]
cum=[0]*(n+1)
dp=[0]*(n+1)
dp[1]=1
cum[1]=1
for i in range(2,n+1):
    for ele in S:
        x=ele[0]
        y=ele[1]
        dp[i]=(dp[i]+cum[max(i-x,0)]-cum[max(0,i-y-1)])%J
    cum[i]=(cum[i-1]+dp[i])%J
print(dp[n])

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

def diff(l):
    tmp = None
    res = []
    for elm in l:
        if tmp is None:
            res.append(elm)
            tmp = elm
        else:
            res.append(elm-tmp)
            tmp = elm

    return res

res_diff = [0] * N
res_diff[1] = -1
res = [1]

for i in range(N-1):
    for l, r in LRs:
        if i+l < N:
            res_diff[i+l] += res[i]
        if i+r+1 < N:
            res_diff[i+r+1] -= res[i]
    
    res_next = (res[-1]+res_diff[i+1])%mod
    res.append(res_next)

print(res[N-1])

Solution (Python):
N, K = map(int, input().split())
L = []
R = []

mod = 998244353

for i in range(K):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r + 1)

diff = [0] + [1] + [-1] + [0] * (10 ** 5 * 5)
ans = [0] * (10 ** 5 * 5)

for i in range(1, N + 1):
    ans[i] = ans[i-1] + diff[i]
    ans[i] %= mod
    for j in range(K):
        diff[i + L[j]] += ans[i]
        diff[i + R[j]] -= ans[i]
        diff[i + L[j]] %= mod
        diff[i + R[j]] %= mod

print(ans[N])

Solution (Python):


MOD = 998244353
ROOT = 3

sum_e = (911660635, 509520358, 369330050, 332049552, 983190778, 123842337, 238493703, 975955924, 603855026, 856644456, 131300601, 842657263, 730768835, 942482514, 806263778, 151565301, 510815449, 503497456, 743006876, 741047443, 56250497, 0, 0, 0, 0, 0, 0, 0, 0, 0)
sum_ie = (86583718, 372528824, 373294451, 645684063, 112220581, 692852209, 155456985, 797128860, 90816748, 860285882, 927414960, 354738543, 109331171, 293255632, 535113200, 308540755, 121186627, 608385704, 438932459, 359477183, 824071951, 0, 0, 0, 0, 0, 0, 0, 0, 0)

def butterfly(arr):
    n = len(arr)
    h = (n - 1).bit_length()
    for ph in range(1, h + 1):
        w = 1 << (ph - 1)
        p = 1 << (h - ph)
        now = 1
        for s in range(w):
            offset = s << (h - ph + 1)
            for i in range(p):
                l = arr[i + offset]
                r = arr[i + offset + p] * now
                arr[i + offset] = (l + r) % MOD
                arr[i + offset + p] = (l - r) % MOD
            now *= sum_e[(~s & -~s).bit_length() - 1]
            now %= MOD

def butterfly_inv(arr):
    n = len(arr)
    h = (n - 1).bit_length()
    for ph in range(1, h + 1)[::-1]:
        w = 1 << (ph - 1)
        p = 1 << (h - ph)
        inow = 1
        for s in range(w):
            offset = s << (h - ph + 1)
            for i in range(p):
                l = arr[i + offset]
                r = arr[i + offset + p]
                arr[i + offset] = (l + r) % MOD
                arr[i + offset + p] = (MOD + l - r) * inow % MOD
            inow *= sum_ie[(~s & -~s).bit_length() - 1]
            inow %= MOD

def convolution(a, b):
    n = len(a)
    m = len(b)
    if not n or not m: return []
    if min(n, m) <= 100:
        if n < m:
            n, m = m, n
            a, b = b, a
        res = [0] * (n + m - 1)
        for i in range(n):
            for j in range(m):
                res[i + j] += a[i] * b[j]
                res[i + j] %= MOD
        return res
    z = 1 << (n + m - 2).bit_length()
    a += [0] * (z - n)
    b += [0] * (z - m)
    butterfly(a)
    butterfly(b)
    for i in range(z):
        a[i] *= b[i]
        a[i] %= MOD
    butterfly_inv(a)
    a = a[:n + m - 1]
    iz = pow(z, MOD - 2, MOD)
    for i in range(n + m - 1):
        a[i] *= iz
        a[i] %= MOD
    return a

def autocorrelation(a):
    n = len(a)
    if not n: return []
    if n <= 100:
        res = [0] * (2 * n - 1)
        for i in range(n):
            for j in range(n):
                res[i + j] += a[i] * a[j]
                res[i + j] %= MOD
        return res
    z = 1 << (2 * n - 2).bit_length()
    a += [0] * (z - n)
    butterfly(a)
    for i in range(z):
        a[i] *= a[i]
        a[i] %= MOD
    butterfly_inv(a)
    a = a[:2 * n - 1]
    iz = pow(z, MOD - 2, MOD)
    for i in range(2 * n - 1):
        a[i] *= iz
        a[i] %= MOD
    return a

def resize(a, m):
    n = len(a)
    if n == m: return a
    if n > m: return a[:m]
    else: return a + [0] * (m - n)

def add(a, b):
    return [(va + vb) % MOD for va, vb in zip(a, b)]

def sub(a, b):
    return [(va - vb) % MOD for va, vb in zip(a, b)]

def times(a, k):
    return [v * k % MOD for v in a]

def multiply(a, b):
    return convolution(a.copy(), b.copy())

def square(a):
    return autocorrelation(a.copy())

def inverse(a):
    n = len(a)
    r = pow(a[0], MOD - 2, MOD)
    m = 1
    tmp = [r]
    while m < n:
        tmp += [0] * m
        m *= 2
        tmp = sub(times(tmp, 2), multiply(a[:m], square(tmp.copy())[:m]))
    res = tmp[:n]
    return res

def divide(a, b):
    return multiply(a, inverse(b))

def differentiate(a):
    n = len(a)
    res = [0] * n
    for i in range(1, n):
        res[i - 1] = a[i] * i % MOD
    return res

def integrate(a):
    n = len(a)
    res = [0] * n
    for i in range(n - 1):
        res[i + 1] = a[i] * pow(i + 1, MOD - 2, MOD) % MOD
    return res

def log(a):
    assert a[0] == 1
    n = len(a)
    return integrate(divide(differentiate(a), a)[:n])

def exp(a):
    assert a[0] == 0
    n = len(a)
    res = [1]
    g = [1]
    q = differentiate(a)
    m = 1
    while m < n:
        g = sub(times(g, 2), multiply(res, square(g)[:m]))
        g += [0] * m
        res += [0] * m
        m *= 2
        w = add(q[:m], multiply(g, sub(differentiate(res), multiply(res, q[:m])[:m]))[:m])
        res = add(res, multiply(res, sub(a[:m], integrate(w)))[:m])
    return res[:n]

def power(a, k):
    n = len(a)
    for d, p in enumerate(a):
        if p != 0: break
    else: return [0] * n
    res = [0] * n
    g = a[d:] + [0] * d
    g = exp(times(log(times(g, pow(p, MOD - 2, MOD))), k))
    for i in range(max(n - d * k, 0)):
        res[d * k + i] = g[i]
    res = times(res, pow(p, k, MOD))
    return res

def tonelli_shanks(n, p): 
    if n == 0: return 0
    if n == 1: return 1
    if pow(n, (p - 1) // 2, p) != 1: return -1
    q, s = p - 1, 0
    while q % 2 == 0:
        q //= 2
        s += 1
    z = 1
    while pow(z, (p - 1) // 2, p) != p - 1:
        z += 1
    m, c, t, r = s, pow(z, q, p), pow(n, q, p), pow(n, (q + 1) // 2, p)
    while t != 1:
        k = 1
        while pow(t, 2**k, p) != 1:
            k += 1
        x = pow(c, pow(2, m - k - 1, p - 1), p)
        m = k
        c = (x * x) % p
        t = (t * c) % p
        r = (r * x) % p
    if r * r % p != n: return -1
    return r

def sqrt_(a):
    assert a[0] != 0
    n = len(a)
    s = tonelli_shanks(a[0], MOD)
    if s == -1: return
    m = 1
    res = [s]
    minv2 = pow(2, MOD - 2, MOD)
    while m < n:
        res += [0] * m
        m *= 2
        res = times(add(res, divide(a[:m], res)), minv2)
    return res[:n]

def sqrt(a):
    n = len(a)
    for d, p in enumerate(a):
        if p != 0: break
    else: return [0] * n
    if d % 2 == 1: return
    s = tonelli_shanks(p, MOD)
    if s == -1: return
    res = [0] * n
    g = a[d:] + [0] * d
    g = sqrt_(times(g, pow(p, MOD - 2, MOD)))
    if g is None: return
    g = times(g, s)
    for i in range(n - d + 1):
        if d // 2 + i >= n: break
        res[d // 2 + i] = g[i]
    return res

def build_exp(n, b):
    res = [0] * (n + 1)
    res[0] = 1
    for i in range(n):
        res[i + 1] = res[i] * b % MOD
    return res

def build_factorial(n):
    fct = [0] * (n + 1)
    inv = [0] * (n + 1)
    fct[0] = inv[0] = 1
    for i in range(n):
        fct[i + 1] = fct[i] * (i + 1) % MOD
    inv[n] = pow(fct[n], MOD - 2, MOD)
    for i in range(n)[::-1]:
        inv[i] = inv[i + 1] * (i + 1) % MOD
    return fct, inv

def taylor_shift(a, c):
    n = len(a)
    fct, inv = build_factorial(n)
    d = build_exp(n, c)
    p = [0] * (2 * n - 1)
    for i in range(n):
        p[i + n - 1] = a[i] * fct[i] % MOD
    q = [0] * (2 * n - 1)
    for i in range(n):
        q[n - 1 - i] = d[i] * inv[i] % MOD
    r = multiply(p, q)
    res = [0] * n
    for i in range(n):
        res[i] = r[2 * n - 2 + i] * inv[i] % MOD
    return res

def bernoulli(n):
    fct, inv = build_factorial(n + 1)
    e = [0] * n
    e[0] = 1
    expx = [inv[i + 1] for i in range(n)]
    res = [v * fct[i] % MOD for i, v in enumerate(divide(e, expx)[:n])]
    return res

def partition(n):
    res = [0] * n
    for i in range(-n, n + 1):
        k = i * (3 * i - 1) // 2
        if k >= n: continue
        if i % 2 == 0: res[k] = 1
        else: res[k] = MOD - 1
    return inverse(res)

def stirling_first(n):
    res = [1]
    t = 0
    for i in range((n).bit_length())[::-1]:
        a = n >> i
        res = multiply(res, taylor_shift(res, -t))
        t *= 2
        if a & 1:
            res = multiply(res, [-t, 1])
            t += 1
    return res

def stirling_second(n):
    fct, inv = build_factorial(n + 1)
    a = [0] * (n + 1)
    b = [0] * (n + 1)
    for i in range(n + 1):
        a[i] = pow(i, N, MOD) * inv[i] % MOD
        b[i] = inv[i] * (1 - (i & 1) * 2)
    res = multiply(a, b)[:n + 1]
    return res

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
F = [0] * (N + 1)

for _ in range(K):
    l, r = map(int, input().split())
    for i in range(l, r + 1):
        F[i] = 1

I = [1] + [0] * N

print(inverse(sub(I, F))[N - 1])

Solution (Python):

import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  
MOD = 998244353


def debug(*x):
    print(*x, file=sys.stderr)


def solve(N, K, SS):
    count = [0] * (N + 10)
    count[0] = 1
    accum = [0] * (N + 10)
    accum[0] = 1

    for pos in range(1, N):
        ret = 0
        for left, right in SS:
            start = pos - right - 1
            end = pos - left
            ret += (accum[end] - accum[start])
            ret %= MOD
        count[pos] = ret
        accum[pos] = accum[pos - 1] + ret

    ret = count[N - 1]
    return ret % MOD


def main():
    
    N, K = map(int, input().split())
    SS = []
    for i in range(K):
        SS.append(tuple(map(int, input().split())))
    print(solve(N, K, SS))



T1 = """
5 2
1 1
3 4
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
4
"""

T2 = """
5 2
3 3
5 5
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
0
"""

T3 = """
5 1
1 2
"""
TEST_T3 = """
>>> as_input(T3)
>>> main()
5
"""

T4 = """
60 3
5 8
1 3
10 15
"""
TEST_T4 = """
>>> as_input(T4)
>>> main()
221823067
"""

T5 = """
10 1
1 2
"""
TEST_T5 = """
>>> as_input(T5)
>>> main()
55
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Solution (Python):
def segfunc(x,y):return x+y
ide_ele=0
class segtree():
  def __init__(self,init_val,segfunc=segfunc,ide_ele=ide_ele):
    n=len(init_val)
    self.segfunc=segfunc
    self.ide_ele=ide_ele
    self.num=1<<(n-1).bit_length()
    self.tree=[ide_ele]*2*self.num
    for i in range(n):
      self.tree[self.num+i]=init_val[i]
    for i in range(self.num-1,0,-1):
      self.tree[i]=self.segfunc(self.tree[2*i], self.tree[2*i+1])
  def update(self,k,x):
    k+=self.num
    self.tree[k]=x
    while k>1:
      self.tree[k>>1]=self.segfunc(self.tree[k],self.tree[k^1])
      k>>=1
  def query(self,l,r):
    l+=self.num
    res=self.ide_ele
    r+=self.num+1
    while l<r:
      if l&1:
        res=self.segfunc(res,self.tree[l])
        l+=1
      if r&1:
        res=self.segfunc(res,self.tree[r-1])
      l>>=1
      r>>=1
    return res
mod=998244353
n,k=map(int,input().split())
l,r=[0]*k,[0]*k
for i in range(k):
  l[i],r[i]=map(int,input().split())
dp=[0]*(n+1)
dp[1]=1
st=segtree(dp)
for i in range(2,n+1):
  s=0
  for j in range(k):
    lj=max(i-r[j],0)
    rj=max(i-l[j],0)
    s+=st.query(lj,rj)
    s%=mod
  st.update(i,s)
print(s)

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