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 sys
from operator import add
def input(): return sys.stdin.readline().rstrip()




class SegmentTree:

    __slots__ = ["func", "e", "original_size", "n", "data"]

    def __init__(self, length_or_list, func=max, e=-10**18):
        self.func = func
        self.e = e
        if isinstance(length_or_list, int):
            self.original_size = length_or_list
            self.n = 1 << ((length_or_list - 1).bit_length())
            self.data = [self.e] * (self.n*2)
        else:
            self.original_size = len(length_or_list)
            self.n = 1 << ((self.original_size - 1).bit_length())
            self.data = [self.e] * self.n + length_or_list + \
                [self.e] * (self.n - self.original_size)
            for i in range(self.n-1, 0, -1):
                self.data[i] = self.func(self.data[2*i], self.data[2*i+1])

    def replace(self, index, value):
        index += self.n
        self.data[index] = value
        index //= 2
        while index > 0:
            self.data[index] = self.func(
                self.data[2*index], self.data[2*index+1])
            index //= 2

    def folded(self, l, r):
        left_folded = self.e
        right_folded = self.e
        l += self.n
        r += self.n
        while l < r:
            if l % 2:
                left_folded = self.func(left_folded, self.data[l])
                l += 1
            if r % 2:
                r -= 1
                right_folded = self.func(self.data[r], right_folded)
            l //= 2
            r //= 2
        return self.func(left_folded, right_folded)

    def all_folded(self):
        return self.data[1]

    def __getitem__(self, index):
        return self.data[self.n + index]

    def max_right(self, l, f):
        
        if l >= self.original_size:
            return self.original_size
        l += self.n
        left_folded = self.e
        while True:
            
            while l % 2 == 0:
                l //= 2
            if not f(self.func(left_folded, self.data[l])):
                while l < self.n:
                    l *= 2
                    if f(self.func(left_folded, self.data[l])):
                        left_folded = self.func(left_folded, self.data[l])
                        l += 1
                return l - self.n
            left_folded = self.func(left_folded, self.data[l])
            l += 1
            if l == l & -l:
                break
        return self.original_size

    
    def min_left(self, r, f):
        
        if r == 0:
            return 0
        r += self.n
        right_folded = self.e
        while True:
            r //= r & -r
            if not f(self.func(self.data[r], right_folded)):
                while r < self.n:
                    r = 2 * r + 1
                    if f(self.func(self.data[r], right_folded)):
                        right_folded = self.func(self.data[r], right_folded)
                        r -= 1
                return r + 1 - self.n
            if r == r & -r:
                break
        return 0


def main():
    mod=998244353
    n, k = map(int, input().split())
    lr = []
    for i in range(k):
        l, r = map(int, input().split())
        lr.append((l, r))
    seg = SegmentTree(n, func=add, e=0)
    seg.replace(0, 1)
    for i in range(1, n):
        wa = 0
        for l, r in lr:
            if i-r >= 0:
                wa+=seg.folded(i-r,i-l+1)
            elif i-l>=0:
                wa+=seg.folded(0,i-l+1)
        wa%=mod
        seg.replace(i,wa)
    print(seg.folded(n-1,n))


if __name__ == '__main__':
    main()

Solution (Python):
def getsum(bit, i):

    s = 0
    i = i + 1

    while i > 0:

        s += bit[i]

        i -= i & (-i)
    return s

def interval_sum(bit, a, b):
    if a == 0:
        return getsum(bit, b)
    else:
        return getsum(bit, b) - getsum(bit, a - 1)

def updatebit(bit , n , i ,v):

    i += 1

    while i <= n:

        bit[i] += v

        i += i & (-i)


def construct(arr, n):

    bit = [0]*(n+1)

    for i in range(n):
        updatebit(bit, n, i, arr[i])

    return bit


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

intervals = []
for _ in range(k):
    a, b = map(int, input().split())
    intervals.append((a, b))
intervals.sort()


data = [0] * n
data[0] = 1
bit = construct(data, n)

mod = 998244353

for i in range(1, n):
    cnt = 0
    for a, b in intervals:
        if i - a < 0:
            break
        cnt += interval_sum(bit, max(i - b, 0), max(i - a, 0))
    cnt %= mod
    updatebit(bit, n, i, cnt)

print(interval_sum(bit, n - 1, n - 1) % mod)

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

dp = [0]*(n+5)
dp[1] = 1
dp2 = [0]*(n+5)
for i in range(1,n+1):
    dp[i] = (dp[i]+dp2[i]+dp2[i-1])%mod
    dp2[i] = (dp2[i]+dp2[i-1])%mod
    for l,r in K:
        dp2[min(i+l,n+2)] += dp[i]
        dp2[min(i+l,n+2)] %= mod
        dp2[min(i+r+1,n+2)] -= dp[i]
        dp2[min(i+r+1,n+2)] %= mod
print(dp[n]%mod)

Solution (Python):
import sys, math, re
from functools import lru_cache
from collections import deque
sys.setrecursionlimit(10**9)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

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

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

def main():
    N, K = mi()
    L, R = i2(K)

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

    for i in range(2, N+1):
        dp[i] = dp[i-1]
        for j in range(K):
            if i-L[j] >= 0:
                dp[i] += dp[i-L[j]]
            if i-R[j]-1 >= 0:
                dp[i] -= dp[i-R[j]-1]

        dp[i] %= 998244353

    print((dp[N]-dp[N-1])%998244353)




if __name__ == "__main__":
    main()

Solution (Python):
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c for j in range(b)] for i in range(a)]
def list3d(a, b, c, d): return [[[d for k in range(c)] for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e for l in range(d)] for k in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10**9)
INF = 10**19
MOD = 998244353
EPS = 10**-10

class BIT:
    """ Binary Indexed Tree """

    def __init__(self, n):
        self.n = n
        
        n += 1
        nv = 1
        while nv < n:
            nv *= 2
        self.size = nv
        self.tree = [0] * nv

    def sum(self, i):
        """ [0, i]を合計する """
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i-1]
            s %= MOD
            i -= i & -i
        return s

    def add(self, i, x):
        """ 値の追加：添字i, 値x """
        i += 1
        while i <= self.size:
            self.tree[i-1] += x
            self.tree[i-1] %= MOD
            i += i & -i

    def query(self, l, r):
        """ 区間和の取得 [l, r) """
        return (self.sum(r-1) - self.sum(l-1)) % MOD
    
    def get(self, i):
        """ 一点取得 """
        return self.query(i, i+1)

    def update(self, i, x):
        """ 値の更新：添字i, 値x """
        self.add(i, x - self.get(i))

    def print(self):
        for i in range(self.n):
            print(self.get(i), end=' ')
        print()

N, K = MAP()
LR = []
for i in range(K):
    l, r = MAP()
    LR.append((l, r))

dp = BIT(N+1)
dp.add(1, 1)
for i in range(2, N+1):
    for l, r in LR:
        cnt = dp.query(max(i-r, 0), max(i-l+1, 0))
        dp.add(i, cnt)
ans = dp.get(N)
print(ans)

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 998244353
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, k = LI()
lr = []
for _ in range(k):
    l, r = LI()
    lr.append([l, r+1])
dp = [0] * (n+1)
dp[1] = 1
for i in range(1, n):
    dp[i+1] += dp[i]
    dp[i+1] %= mod
    for l, r in lr:
        dp[i+1] += dp[i+1-l] - dp[max(0, i+1-r)]
        dp[i+1] %= mod
print((dp[-1] - dp[-2]) % mod)

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

dp = [0]*N
dp[0] = 1
if N > 2:
    dp[1] = -1
for i in range(N):
    if N > 2:
        dp[i] += dp[i-1]
    dp[i] %= mod
    for s in S:
        if s[0]+i < N:
            dp[s[0]+i] += dp[i]
            dp[s[0]+i] %= mod
        if s[1]+i+1 < N:
            dp[s[1]+i+1] -= dp[i]
            dp[s[1]+i+1] %= mod
print(dp[-1])

Solution (Python):
n,k=map(int,input().split())
arr=[]
for _ in range(k):
	arr.append(list(map(int,input().split())))
pref=[0]*(n+1)
dp=[0]*(n+1)
dp[0]=1
pref[0]=1
for i in range(1,n):
	for j in range(k):
		if(arr[j][1]<=i):
			dp[i]=(dp[i]+pref[i-arr[j][0]]-pref[i-arr[j][1]-1])%998244353
		elif(arr[j][0]<=i):
			dp[i]=(dp[i]+pref[i-arr[j][0]])%998244353
	pref[i]=(pref[i-1]+dp[i])%998244353
print(dp[n-1])

Solution (Python):
"""
imos方を使えばよさそう
imos[i][0] => iマス目に到達する場合の数
imos[i][1] => imosの累積
imos[i+l][1] += imos[i]
imos[i+r+1][1] -= imos[i]
"""
mod = 998244353
N,K = map(int,input().split())
LR = [list(map(int,input().split())) for _ in range(K)]

imos = [[0]*2 for _ in range(N)]
imos[0][0] = 1

for i in range(N):
    if i > 0:
        imos[i][1] += imos[i-1][1]
        imos[i][1] %= mod
    imos[i][0] += imos[i][1]
    for l,r in LR:
        if i+l < N:
            imos[i+l][1] += imos[i][0]
            imos[i+l][1] %= mod
        if i+r+1 < N:
            imos[i+r+1][1] -= imos[i][0]
            imos[i+r+1][1] %= mod
print(imos[-1][0])

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def solve():
    MOD = 998244353

    def makeBIT(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        data = [0] * (numPow2+1)
        return data, numPow2
    def setInit(As):
        for iB, A in enumerate(As, 1):
            data[iB] = A
        for iB in range(1, numPow2):
            i = iB + (iB & -iB)
            data[i] += data[iB]
    def addValue(iA, A):
        iB = iA + 1
        while iB <= numPow2:
            data[iB] += A
            iB += iB & -iB
    def getSum(iA):
        iB = iA + 1
        ans = 0
        while iB > 0:
            ans += data[iB]
            iB -= iB & -iB
        return ans
    def getRangeSum(iFr, iTo):
        return getSum(iTo) - getSum(iFr-1)


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

    data, numPow2 = makeBIT(N)

    addValue(0, 1)

    for i in range(1, N):
        v = 0
        for L, R in LRs:
            x, y = i-R, i-L
            if y < 0:
                continue
            if x < 0:
                x = 0
            v += getRangeSum(x, y) % MOD
            v %= MOD
        addValue(i, v)

    ans = getRangeSum(N-1, N-1) % MOD
    print(ans)


solve()

Solution (Python):
n , k = map(int,input().split())
mod = 998244353
s = []
for i in range(k):
    l , r = map(int,input().split())
    s.append((l,r))
dp = [0 for i in range(n)]
dp[0] = 1
dp[1] = -1

for i in range(n):
    if i != 0:
        dp[i] += dp[i-1]
        dp[i] %= mod
    if dp[i] == 0:
        continue
    for L , R in s:
        if i + L < n:
            dp[i+L] += dp[i]
            dp[i+L] %= mod
            if i + R + 1 < n:
                dp[i+R+1] -= dp[i]
print(dp[-1]%mod)

Solution (Python):
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
mod = 998244353; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

def inverse(N, mod):
	return (pow(N, mod - 2, mod))

def main():
	N, K = getlist()
	DP = [0] * (2 * N + 1)
	DP2 = [0] * (2 * N + 1)
	DP[0] = 1
	LR = []
	for i in range(K):
		L, R = getlist()
		LR.append([L, R])

	for i in range(N):
		DP[i] += DP2[i]
		DP[i] %= mod
		for l, r in LR:
			DP2[i + l] += DP[i]
			DP2[i + l] %= mod
			DP2[i + r + 1] -= DP[i]
			DP2[i + r + 1] %= mod
		DP2[i + 1] += DP2[i]
		DP2[i + 1] %= mod

	ans = DP[N - 1]
	print(ans % mod)

if __name__ == '__main__':
	main()

Solution (Python):
n,k=[int(c) for c in input().split()]
MOD = 998244353
segs = []
for _ in range(k):
    a,b=[int(c) for c in input().split()]
    segs.append((a,b))


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

for i in range(n):
    
    if dp[i] < 0:
        dp[i]+=MOD
    for a,b in segs:
        if i+a <=n:
            dp[i+a]+=dp[i]
        if i+b+1 <= n:
            dp[i+b+1]-=dp[i]
    dp[i]%=MOD
    if i !=0:
        dp[i+1] = dp[i+1]+dp[i]

print(dp[n-1]%MOD)

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

n,k,*data = list(map(int,read().split()))
mod = 998244353

dp = [0] * n
dp[0] = 1
route = 0
for j in range(1,n):
    for i in range(k):
        l,r = data[i*2:i*2+2]
        if(j >= l):
            route += dp[j-l]
        if(j > r):
            route -= dp[j-r-1]
        route %= mod
    dp[j] += route


print(dp[-1])

Solution (Python):
N, K = map(int, input().split())
T = []
mod = 998244353
for i in range(K):
    L, R = map(int, input().split())
    T.append([L, R])
dp = [0]*(N+1)
dp[1] = 1
Total = [0]*(N+1)
Total[1] = 1
for i in range(2, N+1):
    for j in range(K):
        L, R = T[j]
        dp[i] += Total[max(0, i-L)] - Total[max(0, i-R-1)]
    dp[i] %= mod
    Total[i] = Total[i-1] + dp[i]
    Total[i] %= mod
print(dp[N])

Solution (Python):
mod=998244353
import sys
input=sys.stdin.readline
n,k=map(int,input().split())
lr=[]
for i in range(k):
	l,r=map(int,input().split())
	lr.append((l,r))
lr.sort()

cnt=[0]*n
cnt[0]=1
dp=[0]*n
for i in range(n-1):
	cnt[i]+=dp[i]
	for x,y in lr:
		if i+x<n:
			dp[i+x]+=cnt[i]
			dp[i+x]%=mod
		if i+y<n-1:
			dp[i+y+1]-=cnt[i]
			dp[i+y+1]%=mod
	dp[i]%=mod
	cnt[i]%=mod
	dp[i+1]+=dp[i]
print((cnt[-1]+dp[-1])%mod)

Solution (Python):
def pointUpdate(BIT,index,val):
    mod = 998244353
    while index < len(BIT):
        BIT[index] += val
        BIT[index] %= mod
        index += index&-index

def pointQuery(BIT,index):
    mod = 998244353
    total = 0
    while index > 0:
        total += BIT[index]
        index -= index&-index
        total %= mod

    return total

def rangeUpdate(BIT,l,r,val):
    pointUpdate(BIT,l,val)
    pointUpdate(BIT,r+1,-val)

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

    segs.sort()

    mod = 998244353
    BIT = [0]*(n+1)
    BIT[1] = 1
    for cell in range(1,n+1):
        curr = pointQuery(BIT,cell)
        if cell == n:
            print(curr)
        for l,r in segs:
            left = min(cell+l,n+1)
            right = min(cell+r,n+1)
            rangeUpdate(BIT,left,right,curr)

main()

Solution (Python):
MOD = 998244353
inpl = lambda: tuple(map(int,input().split()))
N, K = inpl()
LR = [inpl() for _ in range(K)]
dp = [0]*N

c = 1
for i in range(N):
    c = (c + dp[i]) % MOD
    for L, R in LR:
        if i + L < N:
            dp[i+L] = (dp[i+L] + c) % MOD
            if i + R + 1 < N:
                dp[i+R+1] = (dp[i+R+1] - c) % MOD
print(dp[-1])

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

class Binary_Indexed_Tree():
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)

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

    def get(self, i):
        return self.sum_range(i, i)

    def sum(self, i):
        i += 1
        ret = 0
        while i:
            ret += self.data[i]
            i &= i-1
        return ret

    def sum_range(self, l, r):
        return self.sum(r)-self.sum(l-1)

BIT = Binary_Indexed_Tree(n)
BIT.add(0, 1)
for i in range(1,n):
    tmp = 0
    for l,r in lr:
        l = i-l
        r = max(i-r, 0)
        if l < 0:
            continue
        tmp += BIT.sum_range(r, l)
    tmp %= mod
    BIT.add(i, tmp)

ans = BIT.get(n-1)
print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
n,k=map(int,input().split())
l=[list(map(int,input().split())) for i in range(k)]
mod=998244353
dp=[0]*n
dp[0]=1
dp2=[0,1]

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

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 998244353
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

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

    m = [0] * (N+1)
    s = 1

    for i in range(1,N):
        s = (s + m[i]) % MOD
        if s:
            for l,r in a:
                if i + l <= N:
                    m[i+l] = (m[i+l] + s) % MOD
                if i + r + 1 <= N:
                    m[i+r+1] = (m[i+r+1] - s) % MOD
    print(m[-1])


if __name__ == '__main__':
    main()

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

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

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

INF=998244353
dp=[0]*n
dp[0]=1
sum=[0]*(n+1)
sum[0]=0
sum[1]=1

for i in range(1,n):
    temp=0
    for j in range(k):
        l=i-segment[j][1]
        r=i-segment[j][0]
        if r<0:
            continue
        if l<0:
            l=0
        temp=(temp+(sum[r+1]-sum[l]))%INF
    dp[i]=temp
    sum[i+1]=(sum[i]+temp)%INF

print(dp[n-1])

Solution (Python):
MOD = 998244353

n,k = map(int,input().split())
lr = [list(map(int,input().split())) for _ in range(k)]
dp = [0]*n
dp[0] = 1

newdp = 0

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

print(dp[-1])

Solution (Python):
import sys
import heapq, functools, collections
import math, random
from collections import Counter, defaultdict





MOD = 998244353

def solve(k, grid):  
    console("----- solving ------")
    console(grid)
    ways = [1]
    psum = [0,1]
    ps = 1

    for i in range(1,k):
        cur = 0
        for a,b in grid:
            if a > i:
                continue
            if b > i:
                b = i
            console(i-a+1,i-b,i)
            cur += psum[i-a+1] - psum[i-b]

        console()
        console(i, cur, ways, psum)
        console()
         
        ways.append(cur%MOD)
        ps += cur
        psum.append(ps%MOD)


    
    return ways[-1]%MOD


def console(*args):  
    
    return




for case_num in [1]:
    
    

    
    
    
    
    

    
    k, nrows = list(map(int,input().split()))

    
    
    
    grid = []
    for _ in range(nrows):
        grid.append(list(map(int,input().split())))

    res = solve(k, grid)  
    
    
    

    
    print(res)

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 998244353
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    N, K = map(int, readline().split())

    mat = []
    for _ in range(K):
        l, r = map(int, readline().split())
        mat.append((l, r))

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

    for i in range(1, N + 1):
        cur += acc[i]
        cur %= MOD
        dp[i] = cur
        dp[i] %= MOD
        for l, r in mat:
            acc[i + l] += dp[i]
            acc[i + l] %= MOD
            acc[i + r + 1] -= dp[i]
            acc[i + r + 1] %= MOD

    print(dp[N] % MOD)


if __name__ == '__main__':
    main()

Solution (Python):
mod = 998244353
N = int(1e6)
n, k = map(int, input().split())
seg = []
for i in range(k):
    seg.append(tuple(map(int, input().split())))
pref = [1] + [0] * N
for i in range(1, n):
    pref[i] += pref[i - 1]
    for x, y in seg:
        pref[i] += pref[i - x] - pref[i - y - 1] + mod
    pref[i] %= mod
print((pref[n - 1] - pref[n - 2] + mod) % mod)

Solution (Python):
MOD = 998244353

n, k = map(int, input().split())
left=[]
right=[]
for _ in range(k):
    l,r=map(int, input().split())
    left+=[l]
    right+=[r]
pref = [0,1]

for i in range(n-1):
    new = 0
    for j in range(k):
        new += pref[max(0,i+2-left[j])] - pref[max(0,i+1-right[j])]
        
    pref.append((pref[-1] + new) % MOD)
print(new % MOD)

Solution (Python):
FAST_IO = 1
if FAST_IO:
    import io, sys, atexit
    rr = iter(sys.stdin.read().splitlines()).next
    sys.stdout = _OUTPUT_BUFFER = io.BytesIO()

    @atexit.register
    def write():
        sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
else:
    rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())
rrmm = lambda n: [rrm() for _ in xrange(n)]


MOD = 998244353
YES, NO, IMP = "YES", "NO", "IMPOSSIBLE"
from collections import defaultdict as ddic

def solve(N, K, A):
    dp = [0] * N
    dp[0] = 1
    windows = [0] * K
    for i in xrange(1, N):
        for k, (L, R) in enumerate(A):
            if 0 <= i - L < N:
                windows[k] += dp[i - L]
            if 0 <= i - R - 1 < N:
                windows[k] -= dp[i - R - 1]
            windows[k] %= MOD
        dp[i] += sum(windows)
        dp[i] %= MOD

    return dp[-1] % MOD
    
N, K = rrm()
A = rrmm(K)
print solve(N, K, A) % MOD

Solution (Python):
mod = 998244353

N,K = map(int,input().split())
O = []
for i in range(K):
    O.append(tuple(map(int,input().split())))

A = [0] * (N+1)
A[0] = 1
B = [0] * (N+1)
aaa = 0
for i in range(N):
    for L,R in O:
        if i + L < N:
            B[i + L] += A[i]
            if i + R < N:
                B[i + R + 1] -= A[i]
    aaa += B[i + 1]
    A[i+1] = aaa % mod

print(A[N-1])

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

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



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

Solution (Python):
MOD = 998244353
N,K = map(int,input().split())
lr = []
for i in range(K):
    lr.append(list(map(int,input().split())))
dp = [0] * (10**6)
dp[0] = 1
dpcum = [0] * (10**6)
dpcum[0] = 1
for i in range(1,N+1):
    for j in range(K):
        dp[i] += dpcum[max(-1,i-lr[j][0])] - dpcum[max(-1,i-lr[j][1]-1)]
        dp[i] %= MOD
    dpcum[i] = (dpcum[i-1] + dp[i]) % MOD

print(dp[N-1])

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

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

    def init(self, init_val):
        for i, v in enumerate(init_val):
            self.add(i, v)

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

    def sum(self, i, j):
        
        
        return self._sum(j) - self._sum(i)

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

class RangeAddBIT:
    def __init__(self, n):
        self.n = n
        self.bit1 = BIT(n)
        self.bit2 = BIT(n)

    def init(self, init_val):
        self.bit2.init(init_val)

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

    def sum(self, l, r):
        
        
        return self._sum(r) - self._sum(l)

    def _sum(self, i):
        
        
        return self.bit1._sum(i)*i + self.bit2._sum(i)

bit = RangeAddBIT(n+10)
bit.add(1, 2, 1)
for i in range(1, n):
    t = bit.sum(i, i+1)
    t %= mod
    
    for j in range(k):
        l, r = LR[j]
        bit.add(i+l, i+r+1, t)
print(bit.sum(n, n+1)%mod)

Solution (Python):



class SegmentTree:
    def __init__(self, data, default=0, func=max):
        """initialize the segment tree with data"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()

        self.data = [default] * (2 * _size)
        self.data[_size : _size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __delitem__(self, idx):
        self[idx] = self._default

    def __getitem__(self, idx):
        return self.data[idx + self._size]

    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1

    def __len__(self):
        return self._len

    def query(self, start, stop):
        """func of data[start, stop)"""
        start += self._size
        stop += self._size

        res_left = res_right = self._default
        while start < stop:
            if start & 1:
                res_left = self._func(res_left, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res_right = self._func(self.data[stop], res_right)
            start >>= 1
            stop >>= 1

        return self._func(res_left, res_right)

    def __repr__(self):
        return "SegmentTree({0})".format(self.data)


N, K = [int(x) for x in input().split()]
LR = [[int(x) for x in input().split()] for i in range(K)]

MOD = 998244353
numWays = SegmentTree([0 for i in range(N + 1)], 0, lambda x, y: x + y)
numWays[1] = 1

for i in range(2, N + 1):
    total = 0
    for l, r in LR:
        if i - l >= 0:
            total += numWays.query(max(0, i - r), i - l + 1)
    numWays[i] = total % MOD


print(numWays[N])

Solution (Python):
n,k = list(map(int,input().split()))
arr = []
for i in range(k):
    l = list(map(int,input().split()))
    arr.append(l)
mex = 2*pow(10,5) + 5
mod = 998244353
dp = [0 for i in range(mex)]
suf = [0 for i in range(mex)]
dp[n] = 1
suf[n] = 1
for i in range(n-1,0,-1):
    for j in range(k):
        l = i+arr[j][0]
        r = i+arr[j][1]
        r = min(r,n)
        if l<=r:
            dp[i] = (dp[i]+suf[l]-suf[r+1])%mod
    suf[i] = (dp[i]+suf[i+1])%mod
print(dp[1])

Solution (Python):
import sys
import math
import collections
import bisect
import itertools
import decimal
import copy
import heapq




INF = 10 ** 20

MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))
flush = lambda: sys.stdout.flush()



def main():
    n, k = ns()
    pos = []
    for _ in range(k):
        l, r = ns()
        pos.append([l, r])

    imos = [0 for _ in range(n + 1)]
    imos[0] = 1
    imos[1] = -1
    total = 0

    for i in range(n):
        total += imos[i]
        total %= MOD
        if total > 0:
            for l, r in pos:
                if i + l <= n:
                    imos[i + l] += total
                    imos[i + l] %= MOD
                if i + r + 1 <= n:
                    imos[i + r + 1] -= total
                    imos[i + r + 1] %= MOD

    print(total % MOD)


if __name__ == '__main__':
    main()

Solution (Python):
MOD=998244353
N,K=map(int,input().split())
LR=[]
for i in range(K):
    l,r=map(int,input().split())
    LR.append((l,r))
LR.sort(key=lambda x:x[0])


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

for i in range(N):
    dp[i]=(dp[i]+imos[i])%MOD
    for l,r in LR:
        if i+l>=N:
            break
        imos[i+l]=(imos[i+l]+dp[i])%MOD
        R=min(i+r+1,N)
        imos[R]=(imos[R]-dp[i]+MOD)%MOD
    imos[i+1]=(imos[i]+imos[i+1])%MOD
print(dp[N-1])

Solution (Python):


import sys
input=sys.stdin.readline

mod=998244353

n,k=map(int,input().split())
arr=[list(map(int,input().split()))+[i] for i in range(k)]
dp=[0]*(n+1)
dp[1]=1
sums=[0]*k
for i in range(2,n+1):
  for l,r,j in arr:
    if l>i:
      continue
    elif l<=i<=r:
      sums[j]+=dp[i-l]
    else:
      sums[j]-=dp[i-r-1]
      sums[j]+=dp[i-l]
    sums[j]%=mod
  for j in range(k):
    dp[i]+=sums[j]
print(dp[n]%mod)

Solution (Python):
def main():
    MOD = 998244353
    N, K = list(map(int, input().split()))
    section_list = [list(map(int, input().split())) for _ in range(K)]
    dp = [0] * N
    dp[0] = 1
    dp[1] = -1
    for n in range(N):
        cnt = dp[n]
        for k in range(K):
            L, R = section_list[k]
            if n + L < N:
                dp[n + L] += cnt
                dp[n + L] %= MOD
            if n + R + 1 < N:
                dp[n + R + 1] -= cnt
                dp[n + R + 1] %= MOD
        if n < N - 1:
            dp[n + 1] += dp[n]
            dp[n + 1] %= MOD
    print(dp[N - 1])


if __name__ == '__main__':
    main()