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.



Sample input:
5 2
1 1
3 4


Sample output:
4

Submission status: Runtime Error

Solution code:
import numpy as np

mod = 998244353

N, K = map(int, input().split())
LR = []

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

dp = np.array([0] * (N+1))
dp[1] += 1

for i in range(1, N+1):
    now = dp[i] % mod
    
    for l, r in LR:
        try:
            dp[i+l:i+r+1] += now
        except:
            break

print(dp[-1] % mod)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(250000)

dp = []
syugo = set()


def rec(i):
    global syugo
    global dp

    if i < 0 :
        return 0

    if i == 0 :
        return 1

    for j in syugo:
        dp[i] = dp[i] + rec(i-j)

    return dp[i]
def main():
    global syugo
    global dp
    n, k = map(int, input().split())

    for i in range(k):
        s, e = map(int, input().split())
        for j in range(s, e+1):
            syugo.add(j)

    dp = [0]*n

    for i in range(n):
        for j in syugo:
            if i - j ==0 :
                dp[i] = dp[i] + 1
            elif i - j  > 0:
                dp[i] = dp[i] + dp[i-j]
    ##    rec(n-1)

    print(dp[n-1]%998244353)
main()



#
# while True:
#     pair_str = input().split()
#     pair_int = [int(s) for s in pair_str]
#     if pair_int[0] == 0 and pair_int[1] == 0 :
#         break
#     else:
#         input_list.append(pair_int)


# if b > c * 2 :
    #     b_price = c
    #
    # input_array_list = []
    #
    # while True:
    #     input_array = input().split()
    #     if input_array[0] == "0" and input_array[1] == "0":
    #         break
    #     else:
    #         input_array_list.append(input_array)
    #
    # for item in input_array_list:
    #     n = int(item[0])
    #     k_sum = int(item[1])
    #
    #     count = 0
    #     for i in range(1,n + 1- 2):
    #         for j in range(i+1, n + 1 - 1):
    #             for k in range (j+1, n+ 1):
    #                 if i + j + k == k_sum :
    #                     count = count + 1
    #     print(count)

    #
    # for item in input_array_list:
    #     if item[1] == "+":
    #         print(str(int(item[0])+int(item[2])))
    #     elif item[1] =="-":
    #         print(str(int(item[0])-int(item[2])))
    #     elif item[1] == "/":
    #         print(str(int(item[0])//int(item[2])))
    #     elif item[1] == "*":
    #         print(str(int(item[0])*int(item[2])))
    #

# import sympy as sp

# input_list = []
# a,b,c = map(int, input().split())
# divisors = sp.divisors(c)
#
# count = 0
#
# for divisor in divisors:
#     if a <= divisor and divisor <= b:
#         count = count + 1
# print(count)
#
# while True:
#     pair_str = input().split()
#     pair_int = [int(s) for s in pair_str]
#     if pair_int[0] == 0 and pair_int[1] == 0 :
#         break
#     else:
#         input_list.append(pair_int)
#
# for pair_int in input_list:
#     if pair_int[0] <= pair_int[1]:
#         print("{} {}".format(pair_int[0], pair_int[1]))
#     else:
#         print("{} {}".format(pair_int[1], pair_int[0]))

#for i in range(10000):
#    print("Hello World")
#a = input().split()
#a_int = [int(s) for s in a]
#a_sorted = sorted(a_int)
#print(' '.join(map(str, a_sorted)))
import sys
sys.setrecursionlimit(250000)

dp = []
syugo = set()


def rec(i):
    global syugo
    global dp

    if i < 0 :
        return 0

    if i == 0 :
        return 1

    for j in syugo:
        dp[i] = dp[i] + rec(i-j)

    return dp[i]
def main():
    global syugo
    global dp
    n, k = map(int, input().split())

    for i in range(k):
        s, e = map(int, input().split())
        for j in range(s, e+1):
            syugo.add(j)

    dp = [0]*n

    for i in range(n):
        for j in syugo:
            if i - j ==0 :
                dp[i] = dp[i] + 1
            elif i - j  > 0:
                dp[i] = dp[i] + dp[i-j]
    ##    rec(n-1)

    print(dp[n-1]%998244353)
main()



#
# while True:
#     pair_str = input().split()
#     pair_int = [int(s) for s in pair_str]
#     if pair_int[0] == 0 and pair_int[1] == 0 :
#         break
#     else:
#         input_list.append(pair_int)


# if b > c * 2 :
    #     b_price = c
    #
    # input_array_list = []
    #
    # while True:
    #     input_array = input().split()
    #     if input_array[0] == "0" and input_array[1] == "0":
    #         break
    #     else:
    #         input_array_list.append(input_array)
    #
    # for item in input_array_list:
    #     n = int(item[0])
    #     k_sum = int(item[1])
    #
    #     count = 0
    #     for i in range(1,n + 1- 2):
    #         for j in range(i+1, n + 1 - 1):
    #             for k in range (j+1, n+ 1):
    #                 if i + j + k == k_sum :
    #                     count = count + 1
    #     print(count)

    #
    # for item in input_array_list:
    #     if item[1] == "+":
    #         print(str(int(item[0])+int(item[2])))
    #     elif item[1] =="-":
    #         print(str(int(item[0])-int(item[2])))
    #     elif item[1] == "/":
    #         print(str(int(item[0])//int(item[2])))
    #     elif item[1] == "*":
    #         print(str(int(item[0])*int(item[2])))
    #

# import sympy as sp

# input_list = []
# a,b,c = map(int, input().split())
# divisors = sp.divisors(c)
#
# count = 0
#
# for divisor in divisors:
#     if a <= divisor and divisor <= b:
#         count = count + 1
# print(count)
#
# while True:
#     pair_str = input().split()
#     pair_int = [int(s) for s in pair_str]
#     if pair_int[0] == 0 and pair_int[1] == 0 :
#         break
#     else:
#         input_list.append(pair_int)
#
# for pair_int in input_list:
#     if pair_int[0] <= pair_int[1]:
#         print("{} {}".format(pair_int[0], pair_int[1]))
#     else:
#         print("{} {}".format(pair_int[1], pair_int[0]))

#for i in range(10000):
#    print("Hello World")
#a = input().split()
#a_int = [int(s) for s in a]
#a_sorted = sorted(a_int)
#print(' '.join(map(str, a_sorted)))

Submission status: Runtime Error

Solution code:
from sys import stdin


class DFS():
    def __init__(self,N,S):
        self.N = N
        self.S = S
        self.seen = [False] * self.N
        self.cnt = [0] * self.N

    def dfs(self, i):
        if i == self.N-1:
            return 1
        elif i > self.N-1:
            return 0
        elif self.seen[i]:
            return self.cnt[i]
        else:
            cnt = 0
            for s in self.S:
                cnt += self.dfs(i+s)
            else:
                self.cnt[i] = cnt
                self.seen[i] = True
            return self.cnt[i]


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, K = list(map(int, _in[0].split(' ')))  # type:list(int)
    L_R_arr = []
    for i in range(K):
        _ = list(map(int, _in[i+1].split(' ')))  # type:list(int)
        L_R_arr.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    ans = 0
    S = []
    for L, R in L_R_arr:
        S.extend([i for i in range(L, R+1)])
    S = sorted(set(S))
    dfs = DFS(N, S)
    dfs.dfs(0)
    ans = dfs.cnt[0] % 998244353
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
mod = 998244353
 
div = set()
for _ in range(K):
  l,r = map(int,input().split())
  for i in range(l,r+1):
    div.add(i)
min_step = min(div)
dp = [-1]*N
dp[0] = 1
def calc(i):
  if dp[i] >= 0: return dp[i]
  #if i < min_step: dp[i]=0; return dp[i]
  if i < min_step: return 0
  tmp = 0
  for j in div:
    if j > i: continue
    dp[i-j] = calc(i-j)
    tmp = (tmp + dp[i-j])%mod
  dp[i] = tmp
  return tmp
 
print(calc(N-1)%mod)

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
LR = [list(map(int,input().split())) for i in range(K)]
LR.sort()
mod = 998244353
ma = [0] * N
ma[0] = 1
for i in range(N):
    if ma[i] != 0:
        for l,r in LR:
            for j in range(l,r+1):
                if i+j < N:
                    ma[i+j] += ma[i]
                else:
                    f = 1
                    break
            if f:
                break
print(ma[N-1]%mod)

Submission status: Runtime Error

Solution code:
from sys import stdin


class DFS():
    def __init__(self,N,S):
        self.N = N
        self.S = S
        self.seen = [False] * self.N
        self.cnt = [0] * self.N

    def dfs(self, i):
        if i == self.N-1:
            return 1
        elif i > self.N-1:
            return 0
        elif self.seen[i]:
            return self.cnt[i]
        else:
            cnt = 0
            for s in self.S:
                cnt += self.dfs(i+s)
            else:
                self.cnt[i] = cnt
                self.seen[i] = True
            return self.cnt[i]


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, K = list(map(int, _in[0].split(' ')))  # type:list(int)
    L_R_arr = []
    for i in range(K):
        _ = list(map(int, _in[i+1].split(' ')))  # type:list(int)
        L_R_arr.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    ans = 0
    S = []
    for L, R in L_R_arr:
        S.extend([i for i in range(L, R+1)])
    S = sorted(set(S))
    print(S)
    dfs = DFS(N, S)
    dfs.dfs(0)
    ans = dfs.cnt[0] % 998244353
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

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

memo = [None] * (N + 1)

def f(x):
    if x < 0:
        return 0
    if memo[x] is None:
        memo[x] = _f(x)
    # print(x, memo[x])
    return memo[x]


def _f(x):
    if x < 1:
        return 0
    if x == 1:
        return 1
    ans = 0
    for k in range(K):
        for i in range(L[k], R[k] + 1):
            ans += f(x - i)
            ans %= MOD
    return ans % MOD


print(f(N) % MOD)

Submission status: Runtime Error

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

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



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

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

print(dp[n])

Submission status: Runtime Error

Solution code:
import sys

mod = 998244353

N, K = map(int, sys.stdin.readline().strip().split())

step = []
for _ in range(K):
    L, R = map(int, sys.stdin.readline().strip().split())
    step.append((L, R))
step.sort()

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


def solve(u):
    if u <= 0:
        return 0

    if dp[u] is not False:
        return dp[u]
    
    dp[u] = 0
    for L, R in step:
        for i in range(L, R + 1):
            dp[u] += solve(u - i)
    return dp[u]


solve(N)

print(dp[-1] % mod)

Submission status: Runtime Error

Solution code:
MOD = 998244353 
N, K = [int(i) for i in input().split()]
k = []
vals = []
for i in range(K):
  v = [int(i) for i in input().split()]
  vals.extend([*range(v[0], v[1] + 1)])
  
vals.sort()

d  = {}

def helper(n):
  if n == 0:
    return 1
  if n in d:
    return d[n]
  if n < vals[0]:
    return -1
  count = 0
  for v in vals:
    r = helper(n - v)
    if r != -1:
      count += r
      count %= MOD
  d[n] = count
  return int(count)
 
print(helper(N - 1))

Submission status: Runtime Error

Solution code:
# Binary Indexed Tree (Fenwick Tree)
class BIT:
  def __init__(self, n):
    self.n = n
    self.bit = [0]*(n+1)
    self.el = [0]*(n+1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.bit[i]
      i -= i & -i
    return s
  def add(self, i, x):
    # assert i > 0
    self.el[i] += x
    while i <= self.n:
      self.bit[i] += x
      i += i & -i
  def get(self, i, j=None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i-1)

mod = 998244353
N, K = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(K)]
A.sort()
dp = BIT(N)
dp.add(1,1)
for i in range(2,N+1):
  for l,r in A:
    if i-l<=0:# Binary Indexed Tree (Fenwick Tree)
class BIT:
  def __init__(self, n):
    self.n = n
    self.bit = [0]*(n+1)
    self.el = [0]*(n+1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.bit[i]
      i -= i & -i
    return s
  def add(self, i, x):
    # assert i > 0
    self.el[i] += x
    while i <= self.n:
      self.bit[i] += x
      i += i & -i
  def get(self, i, j=None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i-1)

mod = 998244353
N, K = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(K)]
A.sort()
dp = BIT(N)
dp.add(1,1)
for i in range(2,N+1):
  for l,r in A:
    if i-l<=0:
      continue
    if i-r>0:
      dp.add(i,dp.get(i-r,i-l)%mod)
    else:
      dp.add(i,dp.sum(i-l)%mod)
print(dp.el[-1]%mod)


      continue
    if i-r>0:
      dp.add(i,dp.get(i-r,i-l)%mod)
    else:
      dp.add(i,dp.sum(i-l)%mod)
print(dp.el[-1]%mod)

Submission status: Runtime Error

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

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

memo = [None] * (N + 1)

def f(x):
    if x < 0:
        return 0
    if memo[x] is None:
        memo[x] = _f(x)
    # print(x, memo[x])
    return memo[x]


def _f(x):
    if x < 1:
        return 0
    if x == 1:
        return 1
    ans = 0
    for k in range(K):
        for i in range(L[k], R[k] + 1):
            ans += f(x - i)
    return ans % MOD


print(f(N) % MOD)

Submission status: Runtime Error

Solution code:
def kai(N, X, M):
    A_n = [X]
    for i in range(1, N):
        A_i = (A_n[i-1] **2) % M
        A_n.append(A_i)
    return A_n, sum(A_n)

N, X, M = map(int, input().split())
print(kai(N, X, M))

Submission status: Runtime Error

Solution code:
from sys import stdin

input = stdin.readline
from functools import lru_cache

MOD = 998244353


def solve():
    N,K = map(int,input().split())
    step = [tuple(map(int,inp.split())) for inp in stdin.read().splitlines()]\


    @lru_cache(None)
    def dp(n):
        if n == 1:
            return 1
        res = 0
        for a,b in step:
            if n <= a:
                continue
            for i in range(a,b+1):
                if n > i:
                    res += dp(n-i)
        return res % MOD

    print(dp(N))


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest
#import itertools
#import heapq
#from collections import deque
#d = deque()

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline
    mod=998244353
    dp=[0]*(2*(10**5)+10)
    dp[0]=1
    n,k=map(int, readline().rstrip().split())
    #s=set()
    #lr=[0]*(2*(10**5)+10)
    ll=[0]*(2*(10**5)+10)
    rr=[0]*(2*(10**5)+10)
    for i in range(k):
        ll[i],rr[i]=map(int, readline().rstrip().split())
    for i in range(n-1):
        if dp[i] == 0:
            continue
        for j in range(k):
            for x in range(ll[j],rr[j]+1):
                if x > n:
                    break
                dp[i+x] += dp[i]
                dp[i+x]%=mod
    print(dp[n-1])
    #for i in range(n):
    #    if i > 0:
    #        lr[i]+=lr[i-1]
    #    if lr[i] > 0:
    #        s.add(i)

    #arr=list(map(int, readline().rstrip().split()))
    #n=int(readline())
    #ss=readline().rstrip()
    #yn(1)

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Submission status: Runtime Error

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

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

memo = [None] * (N + 1)

def f(x):
    if x < 0:
        return 0
    if memo[x] is None:
        memo[x] = _f(x)
    # print(x, memo[x])
    return memo[x]


def _f(x):
    if x < 1:
        return 0
    if x == 1:
        return 1
    ans = 0
    for k in range(K):
        for i in range(L[k], R[k] + 1):
            ans += f(x - i)
    return ans


print(f(N) % MOD)

Submission status: Runtime Error

Solution code:
#: Author - Soumya Saurav
import sys,io,os,time
from collections import defaultdict
from collections import Counter
from collections import deque
from itertools import combinations
from itertools import permutations
import bisect,math,heapq
alphabet = "abcdefghijklmnopqrstuvwxyz"

input = sys.stdin.readline

########################################
import collections,sys,threading
sys.setrecursionlimit(10**9)
threading.stack_size(10**8)




def solve():
	from functools import lru_cache
	n , k = map(int, input().split())
	moves = set()
	for i in range(k):
		l , r = map(int, input().split())
		for j in range(l,r+1):
			moves.add(j)
	#print(moves)
	mod = 998244353
	@lru_cache(None)
	def f(curr):
		if curr > n:
			return 0
		if curr == n:
			return 1
		ans = 0
		for ele in moves:
			ans += f(curr + ele)
			ans = ans%mod
		return ans
	print(f(1))


threading.Thread(target=solve).start()




'''
# Wrap solution for more recursion depth
#submit as python3

'''

Submission status: Runtime Error

Solution code:
import heapq
n,k=map(int,input().split())
can=[]
you=[0]*(n+1)
for i in range(k):
    l,r=map(int,input().split())
    you[l],you[r+1]=1,-1
for i in range(n):
    you[i+1]+=you[i]
for i in range(n):
    if you[i]:
        can.append(i)
table=[0]*n
table[0]=1
ka=[0]*(n+1)
ka[0]=1
que=[0]
heapq.heapify(que)
can.sort()
while que:
    now=heapq.heappop(que)
    ka[now]=0
    for j in can:
        if now+j>=n:
            break
        table[now+j]=(table[now+j]+table[now])%998244353
        if ka[now+j]==0:
            heapq.heappush(que,now+j)
            ka[now+j]=1
print(table[-1]%998244353)

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.read
#readlines = sys.stdin.readlines
import numpy as np
from numba import njit
def main():
    large_num = 998244353
    n, k = map(int, input().split())
    n -= 1
    dd = [0] * (10**5 * 2)

    m = map(int, read().split())
    ab = zip(m, m)
    for a, b in ab:
        for i1 in range(a, b + 1):
            dd[i1] = 1
    s = [i for i, v in enumerate(dd) if v == 1]
    s = np.array(s)

    @njit()
    def sol(s, n):
        dp = np.zeros(n+1)
        dp[0] = 1
        for i1 in range(1, n+1):
            for se in s:
                if se > i1:
                    break
                else:
                    dp[i1] += dp[i1 - se]
            dp[i1] = dp[i1] % large_num
        return dp[-1]
    print(int(sol(s, n)))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
count=0
for i in range(1,1000):
    print(i)
    for j in range(1,1000):
        print(j)
        if (i*j)>=n:
            count+=j-1
            break
print(count)

Submission status: Runtime Error

Solution code:
def kai(N, X, M):
    A_n = [X]
    for i in range(1, N):
        A_i = (A_n[i-1] **2) % M
        A_n.append(A_i)
    return sum(A_n)

N, X, M = map(int, input().split())
print(kai(N, X, M))

Submission status: Runtime Error

Solution code:
from numba import jit

MOD = 998244353
N, K = list(map(int, input().split()))

dp = np.zeros(N+1, dtype=np.int64)
mv = np.zeros(N+1, dtype=np.int64)
for i in range(K):
    l, r = list(map(int, input().split()))
    for j in range(l, r+1):
        mv[j] = 1

@jit(nopython=True)
def shift_and_add(dp, mv, m, i):
    dp += np.concatenate((np.zeros(i+1, dtype=np.int64), mv[1:N-i+1]*m))
    dp %= MOD
        
dp[1] = 1
for i in range(1, N+1):
    m = dp[i]
    shift_and_add(dp, mv, m, i)

print(dp[N])

Submission status: Runtime Error

Solution code:
import numpy as np
N, K = map(int, input().split())
MOD = 998244353

mark = [0]*(N+1)
for i in range(K):
    l, r = map(int, input().split())
    for i in range(l, r+1):
        mark[i] = 1

count = [0]*(N+1)
count[1] = 1
for i in range(1, N+1):
    for k in range(N+1):
        if mark[k] > 0 and (i + k) <= N:
            count[i + k] = (count[i + k] + count[i]) % MOD

print(count[N])

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.read
#readlines = sys.stdin.readlines
import numpy as np
from numba import njit
def main():
    large_num = 998244353
    n, k = map(int, input().split())
    n -= 1
    dd = [0] * (n+1)

    m = map(int, read().split())
    ab = zip(m, m)
    for a, b in ab:
        for i1 in range(a, b + 1):
            dd[i1] = 1
    s = [i for i, v in enumerate(dd) if v == 1]
    s = np.array(s)

    @njit()
    def sol(s, n):
        dp = np.zeros(n+1)
        dp[0] = 1
        for i1 in range(1, n+1):
            for se in s:
                if se > i1:
                    break
                else:
                    dp[i1] += dp[i1 - se]
            dp[i1] = dp[i1] % large_num
        return dp[-1]
    print(int(sol(s, n)))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
'''go to every index and then run a index - 1 to 1 for it and check whether the proposed number lies somewhere or not'''
n,k = tuple(map(int,input().split()))
boolean = [False]*n
for _ in range(k):
  l,r = tuple(map(int,input().split()))
  for num in range(l,r+1):
    boolean[num] = True;
dp = [0 for _ in range(n+1)]
boolean = [False for _ in range(n+1)]
for i in range(2,n+1):
  for lower in range(1,i):
    if boolean[lower]:
    	start = i - lower
        dp[i] += dp[start]
print(dp[n])

Submission status: Runtime Error

Solution code:
mod = 998244353
N,K = map(int,input().split())

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

dp = [0]*N
dp[0] = 1
dp[D[0][0]] = 1

for n in range(D[0][0],N-1):
    dp[n+1] = dp[n]
    for i in range(K):
        L,R = D[i]
        if n-L+1>=0:
            dp[n+1] += dp[n-L+1]
        if n-R+1>0:
            dp[n+1] -= dp[n-R]
        dp[n+1] %= mod
print(dp[N-1])

Submission status: Runtime Error

Solution code:
def sum(i):
    if nums[i] != -1:
        return nums[i]

    else:
        nums[i] = 0
        for k in S:
            if i - k > 0:
                nums[i] += sum(i - k)
            else:
                break
        return nums[i]


S = set()
temp = []
temp = list(map(int, input().split()))
N = temp[0]
K = temp[1]
nums = [-1, 1]

for i in range(2, N + 1):
    nums.append(-1)

for i in range(0, K):
    temp = list(map(int, input().split()))
    L = temp[0]
    R = temp[1]

    for k in range(L, R + 1):
        S.add(k)

print(sum(N) % 998244353)

Submission status: Runtime Error

Solution code:
import sys

mod = 998244353

N, K = map(int, sys.stdin.readline().strip().split())

step = []
for _ in range(K):
    L, R = map(int, sys.stdin.readline().strip().split())
    step.append((L, R))
step.sort()

dp = [False] * N
dp[0] = 1


def solve(u):
    # print(f'u :{u}')
    if u < 0:
        return 0

    if dp[u] is not False:
        return dp[u]
    
    dp[u] = 0
    for L, R in step:
        for i in range(L, R + 1):
            # print(f'i: {i}')
            dp[u] += solve(u - i)
    return dp[u]


solve(N - 1)

print(dp[-1] % mod)

Submission status: Runtime Error

Solution code:
n,k = map(int, input().split())
hani = [0 for i in range(n)]
kumi = [-1 for i in range(n)]
for i in range(k):
    l,r = map(int,input().split())
    for j in range(l-1,r):
        hani[j] = 1


def countt(n,hani,kumi):
    if n == 1:
        if hani[0] == 1:
            kumi[0] = 1
        else:
            kumi[0] = 0
    else:
        an = 0
        for i in range(0,n-1):
            if hani[i] == 1:
                if kumi[n-i-2] == -1:
                    kumi = countt(n-i-1,hani,kumi)
                an += kumi[n-i-2]
        kumi[n-1] = an
    return kumi

kumi = countt(n,hani,kumi)
ans = kumi[-1]
print(ans % 998244353)

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
s = []
for i in range(k):
    l,r = map(int,input().split())
    s.append(l)
    s.append(r)
suji = 998244353

_s = set(s)
pos=[]
 
def dfs(x):
    if x > n:
        return
    if x == n:
        pos.append(True)
    for i in _s:
        dfs(x+i)
        
dfs(1)
 
num = pos.count(True)
 
print(num%suji)

Submission status: Runtime Error

Solution code:
n, k = map(int,input().split())
l_r = [ list(map(int, input().split())) for _ in range(k)  ]
s_l = [ list(range(l,r+1)) for l,r in l_r ]
d = [0] * n
d[0] = 1
for i in range(1, n):
    c = 0
    for s in s_l:
        if s <= i and d[i-s] > 0:
            c += d[i-s]
    d[i] = c%998244353
print(d[-1]%998244353)

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
s = []
for i in range(k):
    l,r = map(int,input().split())
    s.append(l)
    s.append(r)
suji = 998244353

_s = set(s)
pos=[]
 
def dfs(x):
    if x > n:
        return
    if x == n:
        pos.append(True)
    for i in _s:
        dfs(x+i)
        
dfs(1)
 
num = pos.count(True)
 
print(num%suji)

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
S = set()
for _ in range(K):
  a,b = map(int,input().split())
  for i in range(a,b+1):
    S.add(i)
    
def dfs(n):
  if n == N:
    return 1
  elif n > N:
    return 0
  else:
    cnt = 0
    for i in S:
      cnt += dfs(n+i)
      
    return cnt

ans = dfs(1) % 998244353
print(ans)

Submission status: Runtime Error

Solution code:
import heapq
n,k=map(int,input().split())
can=[]
for i in range(k):
    l,r=map(int,input().split())
    for j in range(l,r+1):
        can.append(j)
table=[0]*n
table[0]=1
que=[0]
heapq.heapify(que)
can.sort()
while que:
    now=heapq.heappop(que)
    for j in can:
        if now+j>n:
            break
        table[now+j]=(table[now+j]+table[now])%998244353
        if now+j in set(que):
            continue
        heapq.heappush(que,now+j)
print(table[-1]%998244353)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
s=[]
for _ in range(k):
    l,r=map(int,input().split())
    for i in range(l,r+1):
        s.append(i)
s=sorted(s)
ans=[0]*(2*(10**5)+100)
ans[0]=1
for i in range(n-1):
    ans[i]=ans[i]%998244353
    for j in s:
        ans[i+j]+=ans[i]
print(ans[n-1]%998244353)

Submission status: Runtime Error

Solution code:
def main():
    n, k = map(int, input().split())
    memo = [-1] * (n+1)
    s = []

    def calc(n):
        if memo[n]>=0:
            return memo[n]
        c = 0
        for v in s:
            if v>n:
                break
            if v==n:
                c += 1
            else:
                c += calc(n-v)
        # print(n, c)
        memo[n] = c % 998244353
        return c

    for _ in range(k):
        l, r = map(int, input().split())
        s.extend(range(l, r+1))
    s.sort()

    ans = calc(n-1) % 998244353
    print(ans)
    # print(memo)

main()

Submission status: Runtime Error

Solution code:
class Rec_memo:
    def __init__(self):
        self.memo = {}

    def solve(self,n,nums):
        nums_cleaned = [i for i in nums if i <= n]
        if n == 0 or nums_cleaned == []:
            return 0
        elif n == min(nums_cleaned):
            return 1
        else:
            max_num = max(nums_cleaned)
            if (n,max_num) in self.memo.keys():
                return self.memo[(n,max_num)]
            else:
                self.memo[(n,max_num)] = sum([self.solve(n-i,nums_cleaned) for i in nums_cleaned])
                return self.memo[(n,max_num)]


N,K = map(int,input().split())
nums = []
for _ in range(K):
    L,R = map(int,input().split())
    for i in range(L,R+1):
        nums.append(i)

rec_memo = Rec_memo()
out = rec_memo.solve(N,nums)
print(out % 998244353)

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
s=[]
dp=[0]*n
for i in range(k):
     l,r =map(int,input().split())
     s.append([l,r])
      
s.sort()
dp[0]=1
dp[s[0][0]]=1
for i in range(s[0][0]+1,n):
    for j in s:
        if j[0]>i:
            break
        for k in range(j[0],j[1]+1):
            if i< k:
                break
            else:
                dp[i]+= dp[i-k] % 998244353
        dp[i] %= 998244353
print(dp[n-1])

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
l,r = [list(map(int,input().split())) for i in range(k)]
suji = 998244353
s = []
for i in l:
    s.append(i)
for j in r:
    s.append(j)
_s = set(s)
pos=[]
 
def dfs(x):
    if x > n:
        return
    if x == n:
        pos.append(True)
    for i in _s:
        dfs(x+i)
        
dfs(1)
 
num = pos.count(True)
 
print(num%suji)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
s=[]
for _ in range(k):
    l,r=map(int,input().split())
    for i in range(l,r+1):
        s.append(i)
s=sorted(s)
ans=[0]*(2*(10**5)+10)
ans[0]=1
for i in range(n-1):
    for j in s:
        ans[i]=ans[i]%998244353
        ans[i+j]+=ans[i]
print(ans[n-1]%998244353)

Submission status: Runtime Error

Solution code:
n,k= list(map(int, input().split()))
INF=998244353
s=[]
for i in range(k):
    j,k=map(int,input().split())
    s.append([l for l in range(j,k+1)])
pattern=[0 for i in range(n)]
pattern[0]=1
ls=len(s)
s.sort()
for i in range(1,n):
    tmp=0
    for j in s:
        if i-j[0]<0:
            break
        else:
            tmp+=sum(pattern[max(i-j[1],0):i-j[0]])
        tmp%=INF
    pattern[i]=tmp
print(pattern[-1])

Submission status: Runtime Error

Solution code:
def dfs(i):
  global ans
  if i>n:
    return
  if i==n:
    ans += 1
    return
  for j in range(len(myList)):
    dfs(i+myList[j])

n,k = map(int,input().split())
myList = []
for i in range(k):
  l,r = map(int,input().split())
  for j in range(l,r+1):
    myList.append(j)
myList.sort()
#print(myList)
ans = 0
dfs(1)
print(ans%998244353)