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: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
mod = 998244353
lr = []
s = set()
for i in range(k):
  l,r = map(int, input().split())
  for j in range(l,r+1):
    s.add(j)

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

for i in range(K):
    l, r = map(int, input().split())
    D = D | set(range(l, r+1))
dp = {}
dp[1] = 1

for i in range(2, N+1):
    dpi = 0
    for d in D:
        if i - d < 1:
            continue
        dpi += dp[i-d]
    dp[i] = dpi % MOD

print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin,stdout
n,k=list(map(int,stdin.readline().split()));l=[];s=[];M=998244353
for _ in range(k):
    x,y=list(map(int,stdin.readline().split()))
    l+=[[x,y]]
for stp in range(n+1):
    for x,y in l:
        if x<=stp<=y:s+=[stp]
dp=[0]*(n+1);dp[1]=1
for i in range(2,n+1):
     for steps in s:
         if steps>=i:break
         dp[i]=(dp[i]+dp[i-steps])%M
print(dp[n])

Submission status: Time Limit Exceeded

Solution code:
#import math
#import itertools
import numpy as np
#from collections import deque
# sys.setrecursionlimit(10 ** 6)
MOD = 998244353
#INF = 10 ** 9
#PI = 3.14159265358979323846

INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

def do():
    n,k=INTM()
    lrs=[]
    for i in range(k):
        lrs.append(LIST())
    pt=np.array([0]*((2*n)+1))
    pt[0]=1
    for i in range(n):
        for l,r in lrs:
            pt[i+l:i+r+1]=([pt[i]]*(r-l+1)+pt[i+l:i+r+1])%MOD
    
    print(pt[n-1]%MOD)


if __name__=='__main__':
    do()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys

def main():
    input = sys.stdin.readline
    n, k = map(int, input().split())
    tmp = []
    for _ in range(k):
        l, r = map(int, input().split())
        for i in range(l, r + 1):
            tmp.append(i)
    tmp.sort()
    dp = [0] * n
    dp[0] = 1

    for i in range(n):
        for j in range(len(tmp)):
            if i + tmp[j] <= n - 1:
                dp[i + tmp[j]] += dp[i]
                dp[i + tmp[j]] %= 998244353
            else:
                del tmp[j:]
    print(dp[-1])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)

MOD = 998244353


def main(input, print):
    n, k = map(int, input().split())
    s = []
    for i in range(k):
        l, r = map(int, input().split())
        for j in range(l, r+1):
            s.append(j)
    s = list(set(s))
    s.sort()
    dp = [0]*(n+1)
    dp[1] = 1
    for i in range(1, n+1):
        for m in s:
            ni = i+m
            if ni > n:
                continue
            dp[ni] += dp[i]
            dp[ni] %= MOD
    print(dp[n])


if __name__ == '__main__':
    main(sys.stdin.readline, print)

Submission status: Time Limit Exceeded

Solution code:
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
# from decorator import stop_watch
#
#
# @stop_watch
def solve(N, K, LR):
    mod = 998244353
    S = []
    for lr in LR:
        S += [i for i in range(lr[0], lr[1] + 1)]
    S.sort()
    dp = [0] * (N + 1)
    dp[1] = 1
    for i in range(1, N + 1):
        for s in S:
            if i + s > N:
                break
            dp[i + s] = (dp[i + s] + dp[i]) % mod
    print(dp[N])


if __name__ == '__main__':
    N, K = map(int, input().split())
    LR = [[int(i) for i in input().split()] for _ in range(K)]
    solve(N,K,LR)

    # # test
    # from random import randint
    # from func import random_str
    # N, K = 2 * 10 ** 5, 1
    # LR = [[1, N]]
    # solve(N, K, LR)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

V = []

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

V.sort()

v = len(V)

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

dp[1] = 1

for i in range(2,N+1):
    for j in range(v):
        if i - V[j] >= 1:
            dp[i] += (dp[i - V[j]])%MOD
        else:
            break

print(dp[-1]%MOD)

Submission status: Time Limit Exceeded

Solution code:
# import numpy as np
import sys, math, heapq
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial, gcd
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10 ** 7)
MOD = 998244353
input = lambda: sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep="\n")

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

for i in range(1, N + 1):
    for lr in LR:
        l, r = lr
        if i in range(l, r + 1):
            S.add(i)

dp = [0] * (N + N + 10)
dp[1] = 1
for i in range(1, N):
    for s in S:
        dp[i + s] += dp[i]
        dp[i + s] %= MOD
dp[N] %= MOD
print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
S = set()

MOD = 998244353
for _ in range(K):
    L, R = map(int, input().split())
    S |= set(range(L, R + 1))
# print(f'{S=}')

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

for i in range(1, len(DP)):
    for s in S:
        if i - s > 0:
            DP[i] += DP[i - s]
    DP[i] %= MOD
# print(f'{DP=}')
print(DP[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

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

steps = tuple(steps)
mod = 998244353

ans = [1]
for i in range(1,N):
    c = 0
    for s in steps:
        if i - s < 0:
            continue
        c += ans[i-s]
        c %= mod
    ans.append(c)

print(ans[N-1])

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
dp = [0] *  (2 * 10 ** 5 + 1)
S = set()
for i in range(K):
    l, r = map(int, input().split())
    for v in range(l, r + 1):
        S.add(v)

dp[1] = 1
MOD = 998244353
for i in range(1, N):
    for v in S:
        if i + v <= N:
            dp[i + v] += dp[i]
            dp[i + v] %= MOD

print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
MOD = 998244353
S = set()
for i in range(K):
    l, r = map(int, input().split())
    for i in range(l, r + 1):
        S.add(i)

dp = [0] * N
dp[0] = 1
for i in range(1, N):
    for s in S:
        if s > i:
            continue
        dp[i] += dp[i - s]
print(dp[-1] % MOD)

Submission status: Time Limit Exceeded

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

for i in range(K):
    l, r = map(int, input().split())
    D = D | set(list(range(l, r+1)))

dp = {}
dp[1] = 1

for i in range(2, N+1):
    dpi = 0
    for d in D:
        if i - d < 1:
            continue
        dpi += dp[i-d]
    dp[i] = dpi % MOD

print(dp[N])

Submission status: Time Limit Exceeded

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

lst = np.zeros((N+1), int)
for _ in range(K):
  l, r = map(int, input().split())
  #for i in range(l, r+1):
  lst[l:r+1] = 1
    
#print(lst)

dp = np.zeros((N), int)
dp[0] = 1

for i in range(N):
  dp[i:] += lst[:N-i] * dp[i] % MOD
  #print(dp)
  #print(dp[i:], lst[:N-i])
   
print(dp[N-1] % MOD)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N, K = map(int, input().split())

div_num = 998244353
dp = [0 for _ in range(N + 1)]
dp[1] = 1
S_list = []
for i in range(K):
    L, R = map(int, input().split())
    for j in range(L, R + 1):
        S_list.append(j)

S_list.sort()
len_S = len(S_list)
for i in range(2, N + 1):
    for j in range(len_S):
        if i <= S_list[j]:
            break
        dp[i] += dp[i - S_list[j]]

print(dp[N] % div_num)

Submission status: Time Limit Exceeded

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,input().split())
s=set()
for i in range(k):
  l,r=map(int,input().split())
  s |= set(range(l,r+1))
  
memo=[0]*(n+1)
memo[1]=1
def move(x):
  y=0
  if memo[x]!=0:
    return memo[x]
  else:
    for j in s:
      if 1<=x-j<=n:
        memo[x]+=move(x-j)
    return memo[x]

print(move(n)%998244353)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from operator import add
def input(): return sys.stdin.readline().rstrip()

# ライブラリ参照https://atcoder.jp/contests/practice2/submissions/16580070


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):
        # assert f(self.e)
        if l >= self.original_size:
            return self.original_size
        l += self.n
        left_folded = self.e
        while True:
            # l //= l & -l
            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

    # 未verify
    def min_left(self, r, f):
        # assert f(self.e)
        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()

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7
M = 998244353


def main():
    N, K = map(int, readline().split())
    S = set()
    for k in range(K):
        L, R = map(int, readline().split())
        S |= set(range(L, R + 1))

    dp = [0] * (N + 1)
    dp[1] = 1
    S = list(S)
    S.sort()

    for i in range(1, N + 1):
        for s in S:
            if i - s > 0:
                dp[i] += dp[i - s]
                dp[i] %= M
            else:
                break
    print(dp[N])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# D

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)
mod = 998244353

n, k = map(int, input().split())
s = []

for i in range(k):
    l,r = map(int, input().split())
    # print(list(range(l,r+1)))
    s = s + list(range(l,r+1))

s = list(set(s))
# print(s)

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

for i in range(1, n):
    for s_ in s:
        if i-s_>=0:
            dp[i] += dp[i-s_] % mod

print(dp[n-1] % mod)

Submission status: Time Limit Exceeded

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

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

for step in range(1, N + 1):
    for i in range(N):
        for l, r in LR:
            for d in range(l, r + 1):
                if N < i + d:
                    continue
                else:
                    dp[step][i + d] += dp[step - 1][i]

ans = 0
for i in range(N + 1):
    ans = (ans + dp[i][N]) % 998244353

print(ans)

Submission status: Time Limit Exceeded

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

Q = 998244353
S = [0] * (N + 1)

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

P = [0] * N
P[0] = 1

for i in range(1, N):
    for j in range(i):
        P[i] += S[i-j] * P[j]
        P[i] = P[i] % Q

print(P[-1])

Submission status: Time Limit Exceeded

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

if __name__ == '__main__':
    f()

Submission status: Time Limit Exceeded

Solution code:
mod=998244353
n,k=map(int,input().split())
step=[]
for i in range(k):
    l,r=map(int,input().split())
    for p in range(l,r+1):
        step.append(p)
step=sorted(step)
dp=[0 for i in range(n+1)]
dp[1]=1
for i in range(1,n+1):
    for s in step:
        if i+s<=n:
            dp[i+s]+=dp[i]
            dp[i+s]%=mod
        else:
            break
print(dp[n]%mod)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
def main():
    import numpy as np

    N, K = map(int, input().split())
    S = set()
    for _ in range(K):
        l, r = map(int, input().split())
        for n in range(l, r + 1):
            S.add(n)
    MOD = 998244353

    dp = [0] * N
    dp[0] = 1
    dp = np.zeros(N, dtype=np.int64)
    dp[0] = 1
    for i in range(N):
        for d in S:
            if i >= d:
                dp[i] += dp[i - d] % MOD
    print(dp[-1] % MOD)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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]
    
    for l, r in LR:
        try:
            dp[i+l:i+r+1] += now
            dp[i+l:i+r+1] %= mod
        except:
            pass

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int, input().split())
mod = 998244353
S = []
for _ in range(min(n, k)):
    l, r = map(int, input().split())
    S += list(range(l, r+1))

# 合計がn-1になるように組み合わせる
dp = [0] * (n+1)
dp[1] = 1
for i in range(2, n+1):
    # もらうdp
    for si in S:
        if i > si:
            dp[i] += dp[i-si]
            dp[i] %= mod

print(dp[n])

Submission status: Time Limit Exceeded

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

for i in range(K):
    l, r = map(int, input().split())
    D += list(range(l, r+1))

dp = {}
dp[1] = 1

for i in range(2, N+1):
    dpi = 0
    for d in D:
        if i - d < 1:
            continue
        dpi += dp[i-d]
    dp[i] = dpi % MOD

print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
import sys
si = sys.stdin.readline

mod = 998244353
n, k = [int(e) for e in si().split()]
dp, coins = [0 for _ in range(200000+10)], set()
while k:
    k -= 1
    a, b = [int(e) for e in si().split()]
    for i in range(a, b+1):
        coins.add(i)
        dp[1+i] = 1

coins = list(coins)
coins = sorted(coins)
for i in range(1, n+1):
    for coin in coins:
        if i >= coin:
            dp[i] = (dp[i]+dp[i-coin]) % mod
print(dp[n])

Submission status: Time Limit Exceeded

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

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

s = []
for i in range(k):
    ss = ab[i][0]
    se = ab[i][1]
    for j in range(ss,se+1):
        s.append(j)

s.sort()

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

for l in range(1,n):
    for m in s:
        if l-m <0:
            break
        dp[l] = (dp[l] +dp[l-m]) % 998244353 

print(dp[n-1]%998244353 )

Submission status: Time Limit Exceeded

Solution code:
n, k = list(map(int, input().split()))
s = set()
o = []
for i in range(k):
    n1 = list(map(int, input().split()))
    o.append(n1)
l=[0]*(n*2)
l[0] = 1
for i in range(n):
    for j in o:
        for k in range(j[0],j[1]+1):
            l[i+k] = (l[i+k]+l[i])%998244353
print(l[n-1]%998244353)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Sep 19 20:18:10 2020

@author: liang
"""
#D
N, K = map(int, input().split())
areas = list()
for i in range(K):
    l, r = map(int,input().split())
    areas.append((l,r))
areas_sum = [0] * N 

d = [0] * N
d[0] = 1
for i in range(N):
    for j in range(K):
        l, r = areas[j]
        if i-l >= 0:
            areas_sum[j] += d[i-l]
        if i-r-1 >= 0:
            areas_sum[j] -= d[i-r-1]
    d[i] += sum(areas_sum)
    d[i] %= 998244353 

#print(d)
ans = d[N-1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#D
N,K=map(int,input().split())
p=998244353
L=[0]*K
R=[0]*K
C=[0]*K
mov=set()
for i in range(K):
    L[i],R[i] = map(int,input().split())
    for i in range(L[i],R[i]+1):
        mov.add(i)
    #C[i] = [L[i],R[i]]
#C.sort()

dp = [0]*(N+1)
dp[1]=1
for i in range(2,N+1):
    for m in mov:
        if i-m>=1:
            dp[i] += dp[i-m]
            dp[i] %= p
    #print(dp[i])
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
value = []
for _ in range(k):
    l, r = map(int, input().split())
    value.append([l, r])
value.sort()
mod = 998244353
dp = [0 for _ in range(n)]
dp[0] = 1
for i in range(n - 1):
    for l, r in value:
        for dist in range(l, min(r + 1, n - 1 - i + 1)):
            if i + dist <= n - 1:
                dp[i + dist] = (dp[i] + dp[i + dist]) % mod
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
mod = 998244353
ans = [0]*(n*2)
ans[0] = 1
c = []


for i in range(k):
    l, r = map(int, input().split())
    for j in range(l, r + 1):
        c.append(j)

for i in range(n):
    for j in c:
        ans[i + j] += ans[i]%mod

print(ans[n - 1]%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)

class ABC(object):

    def __init__(self):
        pass


    def main(self):
        N, K = map(int, input().split())
        LR = [[int(_) for _ in input().split()] for i in range(K)]
        mod = 998244353

        enable_step = []
        for l, r in LR:
            for i in range(l, r+1):
                enable_step.append(i)
            
        # '0' index is not used.
        step_pattern = [0]*(N+1)
        step_pattern[1] = 1

        for i_n in range(1, N):
            for j_enable_step in enable_step:
                if (i_n + j_enable_step) > N:
                    continue
                step_pattern[i_n + j_enable_step] += step_pattern[i_n]
                step_pattern[i_n + j_enable_step] %= mod
        
        ans = step_pattern[N] % mod
        print(ans)
        return


if __name__ == "__main__":
    obj = ABC()
    obj.main()
    sys.exit(0)