Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
MOD = 998244353

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

dp = [0] * (N + 1)
dp[1] = 1
dp_sum = [0] * (N + 1)
dp_sum[1] = 1
for i in range(2, N + 1):
    for j in range(K):
        li = i - R[j]
        ri = i - L[j]
        if ri < 1:
            continue
        li = max(1, li)
        dp[i] += dp_sum[ri] - dp_sum[li - 1]
    dp_sum[i] = dp_sum[i - 1] + dp[i]

print(dp[-1] % MOD)


Fixed submission:
N, K = map(int, input().split())
MOD = 998244353

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

dp = [0] * (N + 1)
dp[1] = 1
dp_sum = [0] * (N + 1)
dp_sum[1] = 1
for i in range(2, N + 1):
    for j in range(K):
        li = max(i - R[j], 1)
        ri = i - L[j]
        if ri < 1:
            continue
        dp[i] += (dp_sum[ri] - dp_sum[li - 1]) % MOD
    dp_sum[i] = (dp_sum[i - 1] + dp[i]) % MOD

print(dp[-1] % MOD)

Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
MOD = 998244353

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

dp = [0] * (N + 1)
dp[1] = 1
dp_sum = [0] * (N + 1)
dp_sum[1] = 1
for i in range(2, N + 1):
    for j in range(K):
        li = i - R[j]
        ri = i - L[j]
        if ri < 1:
            continue
        li = max(1, li)
        dp[i] += dp_sum[ri] - dp_sum[li - 1]
    dp_sum[i] = dp_sum[i - 1] + dp[i]

print(dp[-1] % MOD)


Fixed submission:
N, K = map(int, input().split())
MOD = 998244353

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

dp = [0] * (N + 1)
dp[1] = 1
dp_sum = [0] * (N + 1)
dp_sum[1] = 1
for i in range(2, N + 1):
    for j in range(K):
        li = max(i - R[j], 1)
        ri = i - L[j]
        if ri < 1:
            continue
        dp[i] += (dp_sum[ri] - dp_sum[li - 1]) % MOD
    dp_sum[i] = (dp_sum[i - 1] + dp[i]) % MOD

print(dp[-1] % MOD)

Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
MOD = 998244353
S = [0] * (N + 1)
for i in range(K):
    l, r = map(int, input().split())
    for j in range(l, r + 1):
        S[j] = 1

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


Fixed submission:
N, K = map(int, input().split())
MOD = 998244353

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

dp = [0] * (N + 1)
dp[1] = 1
dp_sum = [0] * (N + 1)
dp_sum[1] = 1
for i in range(2, N + 1):
    for j in range(K):
        li = max(i - R[j], 1)
        ri = i - L[j]
        if ri < 1:
            continue
        dp[i] += (dp_sum[ri] - dp_sum[li - 1]) % MOD
    dp_sum[i] = (dp_sum[i - 1] + dp[i]) % MOD

print(dp[-1] % MOD)

Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
MOD = 998244353
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] * 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)


Fixed submission:
N, K = map(int, input().split())
MOD = 998244353

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

dp = [0] * (N + 1)
dp[1] = 1
dp_sum = [0] * (N + 1)
dp_sum[1] = 1
for i in range(2, N + 1):
    for j in range(K):
        li = max(i - R[j], 1)
        ri = i - L[j]
        if ri < 1:
            continue
        dp[i] += (dp_sum[ri] - dp_sum[li - 1]) % MOD
    dp_sum[i] = (dp_sum[i - 1] + dp[i]) % MOD

print(dp[-1] % MOD)

Buggy python submission (verdict: Time Limit Exceeded):
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)


Fixed submission:
N, K = map(int, input().split())
MOD = 998244353

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

dp = [0] * (N + 1)
dp[1] = 1
dp_sum = [0] * (N + 1)
dp_sum[1] = 1
for i in range(2, N + 1):
    for j in range(K):
        li = max(i - R[j], 1)
        ri = i - L[j]
        if ri < 1:
            continue
        dp[i] += (dp_sum[ri] - dp_sum[li - 1]) % MOD
    dp_sum[i] = (dp_sum[i - 1] + dp[i]) % MOD

print(dp[-1] % MOD)