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

D = [1]
M = 5000
memo = []
for i in range(1, N):
  count = 0
  for l, r in LR:
    if l <= i:
      ll = i - min(i, r)
      rr = i - l + 1
      LL = (ll + M - 1) // M
      RR = rr // M
      if RR > LL:
        count += sum(D[ll:LL*M]) + sum(memo[LL:RR]) + sum(D[RR*M:rr])
      else:
        count += sum(D[ll:rr])
  D.append(count % 998244353)
  if len(D) % M == 0:
    memo.append(sum(D[-M:]))
print(D[-1])

Fixed submission:
N, K = map(int, input().split())
LR = [tuple(map(int, input().split())) for _ in range(K)]

D = [1]
M = 100
memo = []
memo2 = []
for i in range(1, N):
  count = 0
  for l, r in LR:
    if l <= i:
      l1 = i - min(i, r)
      r1 = i - l + 1
      l2 = (l1 + M - 1) // M
      r2 = r1 // M
      l3 = (l2 + M - 1) // M
      r3 = r2 // M
      if r3 > l3:
        count += sum(D[l1:l2*M]) + sum(memo[l2:l3*M]) + sum(memo2[l3:r3]) + sum(memo[r3*M:r2]) + sum(D[r2*M:r1])
      elif r2 > l2:
        count += sum(D[l1:l2*M]) + sum(memo[l2:r2]) + sum(D[r2*M:r1])
      else:
        count += sum(D[l1:r1])
  D.append(count % 998244353)
  if len(D) % M == 0:
    memo.append(sum(D[-M:]))
    if len(memo) % M == 0:
      memo2.append(sum(memo[-M:]))
print(D[-1])

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

D = [1]
M = 1000
memo = []
for i in range(1, N):
  count = 0
  for l, r in LR:
    if l <= i:
      ll = i - min(i, r)
      rr = i - l + 1
      LL = (ll + M - 1) // M
      RR = rr // M
      if RR > LL:
        count += sum(D[ll:LL*M]) + sum(memo[LL:RR]) + sum(D[RR*M:rr])
      else:
        count += sum(D[ll:rr])
  D.append(count % 998244353)
  if len(D) % M == 0:
    memo.append(sum(D[-M:]))
print(D[-1])

Fixed submission:
N, K = map(int, input().split())
LR = [tuple(map(int, input().split())) for _ in range(K)]

D = [1]
M = 100
memo = []
memo2 = []
for i in range(1, N):
  count = 0
  for l, r in LR:
    if l <= i:
      l1 = i - min(i, r)
      r1 = i - l + 1
      l2 = (l1 + M - 1) // M
      r2 = r1 // M
      l3 = (l2 + M - 1) // M
      r3 = r2 // M
      if r3 > l3:
        count += sum(D[l1:l2*M]) + sum(memo[l2:l3*M]) + sum(memo2[l3:r3]) + sum(memo[r3*M:r2]) + sum(D[r2*M:r1])
      elif r2 > l2:
        count += sum(D[l1:l2*M]) + sum(memo[l2:r2]) + sum(D[r2*M:r1])
      else:
        count += sum(D[l1:r1])
  D.append(count % 998244353)
  if len(D) % M == 0:
    memo.append(sum(D[-M:]))
    if len(memo) % M == 0:
      memo2.append(sum(memo[-M:]))
print(D[-1])

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

D = [1]
M = 10
memo = []
for i in range(1, N):
  count = 0
  for l, r in LR:
    if l <= i:
      ll = i - min(i, r)
      rr = i - l + 1
      LL = (ll + M - 1) // M
      RR = rr // M
      if RR > LL:
        count += sum(D[ll:LL*M]) + sum(memo[LL:RR]) + sum(D[RR*M:rr])
      else:
        count += sum(D[ll:rr])
  D.append(count % 998244353)
  if len(D) % M == 0:
    memo.append(sum(D[-M:]))
print(D[-1])

Fixed submission:
N, K = map(int, input().split())
LR = [tuple(map(int, input().split())) for _ in range(K)]

D = [1]
M = 100
memo = []
memo2 = []
for i in range(1, N):
  count = 0
  for l, r in LR:
    if l <= i:
      l1 = i - min(i, r)
      r1 = i - l + 1
      l2 = (l1 + M - 1) // M
      r2 = r1 // M
      l3 = (l2 + M - 1) // M
      r3 = r2 // M
      if r3 > l3:
        count += sum(D[l1:l2*M]) + sum(memo[l2:l3*M]) + sum(memo2[l3:r3]) + sum(memo[r3*M:r2]) + sum(D[r2*M:r1])
      elif r2 > l2:
        count += sum(D[l1:l2*M]) + sum(memo[l2:r2]) + sum(D[r2*M:r1])
      else:
        count += sum(D[l1:r1])
  D.append(count % 998244353)
  if len(D) % M == 0:
    memo.append(sum(D[-M:]))
    if len(memo) % M == 0:
      memo2.append(sum(memo[-M:]))
print(D[-1])

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

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

D = deque([1], N)
for i in range(1, N):
  count = 0
  for l, r in LR:
    if l <= i:
      count += sum(D[i-k] for k in range(l, min(i, r) + 1))
  D.append(count % 998244353)
print(D[-1])

Fixed submission:
N, K = map(int, input().split())
LR = [tuple(map(int, input().split())) for _ in range(K)]

D = [1]
M = 100
memo = []
memo2 = []
for i in range(1, N):
  count = 0
  for l, r in LR:
    if l <= i:
      l1 = i - min(i, r)
      r1 = i - l + 1
      l2 = (l1 + M - 1) // M
      r2 = r1 // M
      l3 = (l2 + M - 1) // M
      r3 = r2 // M
      if r3 > l3:
        count += sum(D[l1:l2*M]) + sum(memo[l2:l3*M]) + sum(memo2[l3:r3]) + sum(memo[r3*M:r2]) + sum(D[r2*M:r1])
      elif r2 > l2:
        count += sum(D[l1:l2*M]) + sum(memo[l2:r2]) + sum(D[r2*M:r1])
      else:
        count += sum(D[l1:r1])
  D.append(count % 998244353)
  if len(D) % M == 0:
    memo.append(sum(D[-M:]))
    if len(memo) % M == 0:
      memo2.append(sum(memo[-M:]))
print(D[-1])

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

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

MOD = 998244353

D = deque([1], N)
for i in range(1, N):
  count = 0
  for l, r in LR:
    if l <= i:
      count += sum(D[i-k] for k in range(l, min(i, r) + 1))
  D.append(count % MOD)
print(D[-1])

Fixed submission:
N, K = map(int, input().split())
LR = [tuple(map(int, input().split())) for _ in range(K)]

D = [1]
M = 100
memo = []
memo2 = []
for i in range(1, N):
  count = 0
  for l, r in LR:
    if l <= i:
      l1 = i - min(i, r)
      r1 = i - l + 1
      l2 = (l1 + M - 1) // M
      r2 = r1 // M
      l3 = (l2 + M - 1) // M
      r3 = r2 // M
      if r3 > l3:
        count += sum(D[l1:l2*M]) + sum(memo[l2:l3*M]) + sum(memo2[l3:r3]) + sum(memo[r3*M:r2]) + sum(D[r2*M:r1])
      elif r2 > l2:
        count += sum(D[l1:l2*M]) + sum(memo[l2:r2]) + sum(D[r2*M:r1])
      else:
        count += sum(D[l1:r1])
  D.append(count % 998244353)
  if len(D) % M == 0:
    memo.append(sum(D[-M:]))
    if len(memo) % M == 0:
      memo2.append(sum(memo[-M:]))
print(D[-1])

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

D = [1]
for i in range(1, N):
  count = 0
  for l, r in LR:
    if l <= i:
      count += sum(D[i-k] for k in range(l, min(i, r) + 1))
  D.append(count % 998244353)
print(D[-1])

Fixed submission:
N, K = map(int, input().split())
LR = [tuple(map(int, input().split())) for _ in range(K)]

D = [1]
M = 100
memo = []
memo2 = []
for i in range(1, N):
  count = 0
  for l, r in LR:
    if l <= i:
      l1 = i - min(i, r)
      r1 = i - l + 1
      l2 = (l1 + M - 1) // M
      r2 = r1 // M
      l3 = (l2 + M - 1) // M
      r3 = r2 // M
      if r3 > l3:
        count += sum(D[l1:l2*M]) + sum(memo[l2:l3*M]) + sum(memo2[l3:r3]) + sum(memo[r3*M:r2]) + sum(D[r2*M:r1])
      elif r2 > l2:
        count += sum(D[l1:l2*M]) + sum(memo[l2:r2]) + sum(D[r2*M:r1])
      else:
        count += sum(D[l1:r1])
  D.append(count % 998244353)
  if len(D) % M == 0:
    memo.append(sum(D[-M:]))
    if len(memo) % M == 0:
      memo2.append(sum(memo[-M:]))
print(D[-1])