Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(K)]
 
# dpの高速化 => O(N)で解く
dp = [0] * N
dp[0] = 1
mod = 998244353
 
for i in range(N):
  for j in range(K):
    L = X[j][0]
    R = X[j][1]
    for k in range(L, R+1):
      if 0 <= i - k < N-1:
        dp[i] += dp[i-k]
        dp[i] %= mod
      else: continue

print(dp[N-1])

Fixed submission:
N, K = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(K)]
 
# dpの高速化 => 累積和によって、O(N)で解く
dp = [0] * N
acc = [0]* (N+1)
dp[0], acc[1] = 1, 1
# acc[0] = 0
# acc[1] = dp[0]
# acc[2] = dp[0] + dp[1]
# acc[n] = dp[0] + dp[1] + dp[n-1]

# dp[0] = acc[1] - acc[0]
# dp[1] = acc[2] - acc[1]
# dp[n-1] = acc[n] - acc[n-1]
mod = 998244353
 
for i in range(1, N):
  # acc[i] = dp[0] + ... + dp[i-1] が既知
  # 貰うdp
  for j in range(K):
    r = i - X[j][0]
    l = i - X[j][1]
    if r < 0: continue
    l = max(l, 0)
      
    dp[i] += acc[r+1] - acc[l] # s = dp[L] + ... + dp[R]
    dp[i] %= mod
  acc[i+1] = acc[i] + dp[i] # acc[i+1] = dp[0] + ... + dp[i]

print(dp[N-1])

Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(K)]

# dpの高速化 => O(N)で解く
dp = [0] * N
dp[0] = 1
mod = 998244353
 
for i in range(N):
  for j in range(K):
    L = X[j][0]
    R = X[j][1]
    for k in range(L, R+1):
      if 0 <= i - k <= N-1:
        dp[i] += dp[i-k]
        dp[i] %= mod
      else: continue

print(dp[N-1])

Fixed submission:
N, K = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(K)]
 
# dpの高速化 => 累積和によって、O(N)で解く
dp = [0] * N
acc = [0]* (N+1)
dp[0], acc[1] = 1, 1
# acc[0] = 0
# acc[1] = dp[0]
# acc[2] = dp[0] + dp[1]
# acc[n] = dp[0] + dp[1] + dp[n-1]

# dp[0] = acc[1] - acc[0]
# dp[1] = acc[2] - acc[1]
# dp[n-1] = acc[n] - acc[n-1]
mod = 998244353
 
for i in range(1, N):
  # acc[i] = dp[0] + ... + dp[i-1] が既知
  # 貰うdp
  for j in range(K):
    r = i - X[j][0]
    l = i - X[j][1]
    if r < 0: continue
    l = max(l, 0)
      
    dp[i] += acc[r+1] - acc[l] # s = dp[L] + ... + dp[R]
    dp[i] %= mod
  acc[i+1] = acc[i] + dp[i] # acc[i+1] = dp[0] + ... + dp[i]

print(dp[N-1])

Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(K)]

mod = 998244353
dp = [0] * N
dp[0] = 1

# O(N)で解く！
# N-1個目のマスまでdp
for i in range(N-1):
  for j in range(K):
    for k in range(X[j][0], X[j][1]+1):
      if 0 <= i + k <= N-1:
        dp[i+k] += dp[i]
        dp[i+k] %= mod
      else: continue

print(dp[N-1])

Fixed submission:
N, K = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(K)]
 
# dpの高速化 => 累積和によって、O(N)で解く
dp = [0] * N
acc = [0]* (N+1)
dp[0], acc[1] = 1, 1
# acc[0] = 0
# acc[1] = dp[0]
# acc[2] = dp[0] + dp[1]
# acc[n] = dp[0] + dp[1] + dp[n-1]

# dp[0] = acc[1] - acc[0]
# dp[1] = acc[2] - acc[1]
# dp[n-1] = acc[n] - acc[n-1]
mod = 998244353
 
for i in range(1, N):
  # acc[i] = dp[0] + ... + dp[i-1] が既知
  # 貰うdp
  for j in range(K):
    r = i - X[j][0]
    l = i - X[j][1]
    if r < 0: continue
    l = max(l, 0)
      
    dp[i] += acc[r+1] - acc[l] # s = dp[L] + ... + dp[R]
    dp[i] %= mod
  acc[i+1] = acc[i] + dp[i] # acc[i+1] = dp[0] + ... + dp[i]

print(dp[N-1])

Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(K)]

S = []
for i in range(K):
  for j in range(X[i][0], X[i][1]+1): S.append(j)

mod = 998244353
dp = [0] * N
dp[0] = 1

# N-1個目のマスまでdp
for i in range(N-1):
  for j in S:
    if 0 <= i + j <= N-1:
      dp[i+j] += dp[i]
      dp[i+j] %= mod
    else: continue

print(dp[N-1])

Fixed submission:
N, K = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(K)]
 
# dpの高速化 => 累積和によって、O(N)で解く
dp = [0] * N
acc = [0]* (N+1)
dp[0], acc[1] = 1, 1
# acc[0] = 0
# acc[1] = dp[0]
# acc[2] = dp[0] + dp[1]
# acc[n] = dp[0] + dp[1] + dp[n-1]

# dp[0] = acc[1] - acc[0]
# dp[1] = acc[2] - acc[1]
# dp[n-1] = acc[n] - acc[n-1]
mod = 998244353
 
for i in range(1, N):
  # acc[i] = dp[0] + ... + dp[i-1] が既知
  # 貰うdp
  for j in range(K):
    r = i - X[j][0]
    l = i - X[j][1]
    if r < 0: continue
    l = max(l, 0)
      
    dp[i] += acc[r+1] - acc[l] # s = dp[L] + ... + dp[R]
    dp[i] %= mod
  acc[i+1] = acc[i] + dp[i] # acc[i+1] = dp[0] + ... + dp[i]

print(dp[N-1])