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

mod = 998244353

class BIT():

    __slots__ = ["n", "data"]

    def __init__(self, li):
        self.n = len(li) + 1
        self.data = [1] + li
        for i in range(1, self.n):
            if i + (i & -i) < self.n:
                self.data[i + (i & -i)] += self.data[i]

    def add(self, i, a):
        i += 1
        while i < self.n:
            self.data[i] += a
            self.data[i] %= mod
            i += i & -i
        
    def acc(self, i):
        res = 0
        while i > 0:
            res += self.data[i]
            res %= mod
            i -= i & -i
        return res
    
    def fold(self, l, r):
        res = 0
        while l < r:
            res += self.data[r]
            r -= r & -r
            res %= mod
        while r < l:
            res -= self.data[l]
            l -= l & -l
            res %= mod
        return res
        
        
n, k = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(k)]
dp = BIT([0]*n)
dp.add(0, 1)
for i in range(1, n):
    for l, r in LR:
        dp.add(i, dp.fold(max(i-r, 0), max(i-l+1, 0)))
ans = dp.fold(n-1, n)
print(ans)

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

M = 998244353
T = [0]*N
T[0] = 1
s = 0
for i in range(N):
  s += T[i]
  for j in range(K):
    if i+L[j]<N:
      T[i+L[j]] += s
      T[i+L[j]] %= M
    if i+R[j]<N:
      T[i+R[j]] -= s
      T[i+R[j]] %= M

print(T[-1])

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


class BinaryIndexedTree:
    """一点加算、区間総和クエリをそれぞれO(logN)で答えるデータ構造。"""
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n + 1)

    def build(self, array):
        """arrayを初期値とするBinaryIndexedTreeを構築する。O(N)"""
        for i, val in enumerate(array):
            self.bit[i + 1] = val
        for i in range(1, self.size):
            if i + (i & -i) > self.size:
                continue
            self.bit[i + (i & -i)] += self.bit[i]

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

    def add(self, i, val):
        """i番目の要素にvalを加算する。O(logN)"""
        i += 1
        while i <= self.size:
            self.bit[i] += val
            self.bit[i] %= MOD
            i += i & -i

    def sum(self, l, r):
        """区間[l, r)の和を求める。O(logN)"""
        return (self._sum(r) - self._sum(l)) % MOD


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


bit = BinaryIndexedTree(n + 1)
bit.add(1, 1)

for i in range(2, n + 1):
    ptn = 0
    for l0, r0 in dist:
        l = i - r0
        r = i - l0 + 1
        l, r = max(l, 0), max(r, 0)
        ptn += bit.sum(l, r)
    bit.add(i, ptn)
    
print(bit.sum(n, n + 1) % MOD)

Solution (Python):
MOD = 998244353

def main():
    n, k = map(int, input().split())
    rng = [list(map(int, input().split())) for _ in range(k)]
    dp = [0]*(n+5)
    dp[1] = 1
    for i in range(1, n):
        dp[i] += dp[i-1]
        dp[i] %= MOD
        for l, r in rng:
            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)

if __name__ == "__main__":
    main()

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

N,K=map(int,input().split())
K=[tuple(map(int,input().split())) for i in range(K)]
mod=998244353

DP=[0]*(4*10**5+100)
DP[1]=1
DP[2]=-1

for i in range(1,N+1):
    DP[i]+=DP[i-1]
    DP[i]%=mod
    
    for l,r in 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):
p = 998244353
n, k = [int(i) for i in input().split(" ")]
n -= 1
a = [[0, 0] for i in range(k)]
for i in range(k):
  a[i] = [int(j) for j in input().split(" ")]
dp = [0] * (n+10)
cum = [0] * (n+10)
dp[0] = 1
cum[0] = 1

for i in range(1, n+1):
  for j in range(k):
    fi = i - a[j][1]
    se = i - a[j][0]
    if se < 0:
      continue
    if fi < 0:
      fi = 0
    if fi == 0:
      dp[i] = (dp[i] + cum[se]) % p
    else:
      dp[i] = (dp[i] + cum[se] - cum[fi-1]) % p
  cum[i] = (cum[i-1] + dp[i]) % p




print(dp[n] % p)

Solution (Python):
import sys


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

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

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

    def lower_bound(self, x):
        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_


n, k, *lr = map(int, sys.stdin.buffer.read().split())
lr = list(zip(lr[0::2], lr[1::2]))
MOD = 998244353

bit = BinaryIndexedTree(n + 2, MOD)
bit.add(1, 1)
for i in range(1, n):
    v = bit.sum(i)
    for l, r in lr:
        bit.add(i + l, v)
        bit.add(min(i + r + 1, n + 1), -v)

print((bit.sum(n) - bit.sum(n - 1)) % MOD)

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

N,K=map(int,input().split())
K=[tuple(map(int,input().split())) for i in range(K)]
mod=998244353

DP=[0]*(4*10**5+100)
DP[1]=1
DP[2]=-1

for i in range(1,N+1):
    DP[i]+=DP[i-1]
    DP[i]%=mod
    
    for l,r in 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 = map(int, input().split())
LRs = [tuple(map(int, input().split())) for _ in range(K)]

MOD = 998244353

dp = [0] * (N + 1)
dp_csum = [0] * (N + 2)
dp[1] = 1
dp_csum[2] = 1
for i in range(2, N + 1):
    for L, R in LRs:
        dp[i] += dp_csum[max(0, i - L + 1)] - dp_csum[max(0, i - R)]
        dp[i] %= MOD
    dp_csum[i + 1] = dp_csum[i] + dp[i]
    dp_csum[i + 1] %= MOD




print(dp[N])

Solution (Python):


import sys
readline = sys.stdin.readline
read = sys.stdin.read




def get(i,l,r):
    a = i-r
    b = i-l
    if b < 0: return 0
    return acc[b] - (acc[a-1] if a-1 >= 0 else 0)



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

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


MOD = 998244353
for i in range(1,n):
    v = 0
    for l,r in lr:
        v += get(i,l,r)
    dp[i] = v%MOD
    acc[i] = (acc[i-1] + dp[i])%MOD
    

print(dp[n-1]%MOD)

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

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






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


def print_bit(B):
    n = B.size
    ANS = []
    for i in range(n):
        ANS.append(B.sum(i, i+1))
    print(*ANS)

B = Bit(n)
mod = 998244353
B.add(0, 1)
for i in range(1, n):
    for j in range(k):
        B.add(i, (B.sum(max(0,i-C[j][1]), max(0,i-C[j][0]+1)))%mod)

print(B.sum(n-1,n)%mod)

Solution (Python):
from math import inf, log2


class SegmentTree:
    def __init__(self, array, func=max):
        self.n = len(array)
        self.size = 2**(int(log2(self.n-1))+1) if self.n != 1 else 1
        self.func = func
        self.default = 0 if self.func != min else inf
        self.data = [self.default] * (2 * self.size)
        self.process(array)

    def process(self, array):
        self.data[self.size : self.size+self.n] = array
        for i in range(self.size-1, -1, -1):
            self.data[i] = self.func(self.data[2*i], self.data[2*i+1])

    def query(self, alpha, omega):
        """Returns the result of function over the range (inclusive)!"""
        if alpha == omega:
            return self.data[alpha + self.size]
        res = self.default
        alpha += self.size
        omega += self.size + 1
        while alpha < omega:
            if alpha & 1:
                res = self.func(res, self.data[alpha])
                alpha += 1
            if omega & 1:
                omega -= 1
                res = self.func(res, self.data[omega])
            alpha >>= 1
            omega >>= 1
        return res

    def update(self, index, value):
        """Updates the element at index to given value!"""
        index += self.size
        self.data[index] = value
        index >>= 1
        while index:
            self.data[index] = self.func(self.data[2*index], self.data[2*index+1])
            index >>= 1



import os
import sys
from io import BytesIO, IOBase

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")


from math import gcd, ceil

def pre(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        j = pi[i - 1]
        while j and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi


def prod(a):
    ans = 1
    for each in a:
        ans = (ans * each)
    return ans

def lcm(a, b): return a * b // gcd(a, b)


def binary(x, length=16):
    y = bin(x)[2:]
    return y if len(y) >= length else "0" * (length - len(y)) + y


for _ in range(int(input()) if not True else 1):
    
    n, k = map(int, input().split())
    
    
    
    
    a = [0]*(n+1)
    a[1] = 1
    st = SegmentTree(a, func=lambda a,b:a+b)
    segs = []
    for i in range(k):
        l, r = map(int, input().split())
        segs += [[l, r]]
    mod = 998244353
    for i in range(2, n+1):
        val = 0
        for l, r in segs:
            if i - l >= 1:
                val += st.query(max(1, i-r), i-l)
                val = val % mod
        st.update(i, val)
    print(st.query(n, n))

Solution (Python):
import sys
from sys import exit
from collections import deque
from copy import deepcopy
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 998244353

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod=MOD):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        if k<0 or n<k:
            return 0
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x,mode='counter'):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    if mode=='counter':
        return C
    S = set([1])
    for k in C:
        T = deepcopy(S)
        for x in T:
            for i in range(1,C[k]+1):
                S.add(x*(k**i))
    if mode=='set':
        return S
    if mode=='list':
        return sorted(list(S))



N,K=mint()
lr=[lint() for _ in range(K)]
dp=[0]*(N+1)
dp[1]=1
dp[2]=-1
tmp=0
for i in range(1,N):
    tmp+=dp[i]
    tmp%=MOD
    for l,r in lr:
        if i+l<=N:
            dp[i+l]+=tmp
            dp[i+l]%=MOD
        if i+r+1<=N:
            dp[i+r+1]-=tmp
            dp[i+r+1]%=MOD
print(sum(dp)%MOD)

Solution (Python):
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
mod = 998244353
a = [tuple(map(int, input().split())) for _ in range(K)]
dp = [0] * (N + 1)
dp[1] = 1
imos = [0] * (N + 1)
for i in range(1, N):
  dp[i] += imos[i]
  dp[i] %= mod
  for l, r in a:
    if i + l > N: continue
    imos[i + l] += dp[i]
    imos[i + l] %= mod
    if i + r + 1 > N: continue
    imos[i + r + 1] -= dp[i]
    imos[i + r + 1] %= mod
  imos[i + 1] += imos[i]
  imos[i + 1] %= mod
dp[-1] += imos[-1]
dp[-1] %= mod
print(dp[-1])

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






class BinaryIndexedTree:
  def __init__(self, n):
    self.bit = [0] * n

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

  def sum_sub(self, i):
    a = 0
    i += 1
    while i:
      a += self.bit[i-1]
      i -= i & -i
    return a

  def sum(self, i, j):
    a = 0
    if j != 0:
      a += self.sum_sub(j-1)
    if i != 0:
      a -= self.sum_sub(i-1)
    return a
mod=998244353
n,k=map(int,input().split())
lr=[]
for i in range(k):
  l,r=map(int,input().split())
  lr.append((l,r))
bit=BinaryIndexedTree(2*n+7)
bit.add(0,1)
bit.add(1,-1)
for i in range(n-1):
  x=bit.sum_sub(i)%mod
  for l,r in lr:
    bit.add(i+l,x)
    bit.add(i+r+1,-x)
print(bit.sum_sub(n-1)%mod)

Solution (Python):
mod = 998244353
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline
    N, K = map(int, input().split())
    L = []
    R = []
    for _ in range(K):
        l, r = map(int, input().split())
        L.append(l)
        R.append(r)

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys

sys.setrecursionlimit(500005)
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().strip()

n, K = na()
lr = []
for i in range(K):
    lr.append(na())

mod = 998244353
dp = [0] * (n+1)
cum = [0] * (n+1)

dp[1] = cum[1] = 1
for i in range(2, n+1):
    v = 0
    for u in lr:
        l = max(1, i-u[1])
        r = i-u[0]
        if l <= r:
            v += cum[r] - cum[l-1] + mod
    dp[i] = v % mod
    cum[i] = cum[i-1] + dp[i]
    if cum[i] >= mod:
        cum[i] -= mod
print(dp[n])

Solution (Python):
N,K=map(int,input().split())
X=[list(map(int,input().split())) for i in range(K)]
C=[0]*(N*3)
DP=[0]*N
mod=998244353
DP[0]=1
Y=0
for i in range(N):
  Y+=C[i]
  DP[i]+=Y
  Y%=mod
  DP[i]%=mod
  for j in range(K):
    C[i+X[j][0]]+=DP[i]
    C[i+X[j][1]+1]-=DP[i]
print(DP[N-1])