Buggy python submission (verdict: Runtime Error):
N,X,M = map(int,input().split())

ans = X
A = X
TF = True
srt = 1000000
retu = dict()
retu[X] = 1
loop = X
for i in range(N-1):
    if TF:
        A = A**2 % M
        if retu.get(A) != None:
          srt = j
          goal = i
          TF = False
          break   
        if TF:
          retu[A] = 1
          loop += A
    else:
      break
      
if N-1 > srt:
    n = (N-srt)//(goal-srt+1)
    saisyo = sum(retu[:srt])
    loop -= saisyo
    print(saisyo + loop*n + sum(retu[srt:N-n*(goal-srt+1)]))
    
else:
    print(sum(retu[:N]))


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

dp = [0]*(N+1)
acc = [0]*(N+1) # acc[i] = dp[1] + ... dp[i]

dp[1] = 1
acc[1] = 1
for i in range(2, N+1):
    for lr in LR:
        l = lr[0]
        r = lr[1]

        dp[i] += (acc[max(0, i - l)] - acc[max(0, i - r - 1)] + MOD)
        dp[i] %= MOD
    acc[i] = (acc[i-1] + dp[i]) % MOD
    
    

print(dp[N])
# print(acc)
# print(dp[N])

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
MOD = 998244353
N, K = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(K)]

S = list()
for lr in LR:
    for i in range(lr[0], lr[1]+1):
        S.append(i)

dp = [0]*(N+1) # dp[i] : iに行く方法
dp[1] = 1

memo1 = deque()
memo2 = deque()

for i in range(1, N+1):
    # for s in S:
    #     if i + s <= N:
    #         dp[i + s] += dp[i]
    #         dp[i + s] %= MOD
    while(len(memo1)):
        # l = m[1]
        # r = m[2]
        m = memo1.popleft()
        if m[1] <= i and i <= m[2]:
            dp[i] += m[0]
            dp[i] %= MOD
        
        if not(m[2] < i):
            memo2.append(m)
    
    while(len(memo2)):
        tmp = memo2.popleft()
        memo1.append(tmp)
    
    for lr in LR:
        memo1.append([dp[i], lr[0] + i, lr[1] + i])
    
print(dp[N])

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

dp = [0]*(N+1)
acc = [0]*(N+1) # acc[i] = dp[1] + ... dp[i]

dp[1] = 1
acc[1] = 1
for i in range(2, N+1):
    for lr in LR:
        l = lr[0]
        r = lr[1]

        dp[i] += (acc[max(0, i - l)] - acc[max(0, i - r - 1)] + MOD)
        dp[i] %= MOD
    acc[i] = (acc[i-1] + dp[i]) % MOD
    
    

print(dp[N])
# print(acc)
# print(dp[N])

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

S = list()
for lr in LR:
    for i in range(lr[0], lr[1]+1):
        S.append(i)

dp = [0]*(N+1) # dp[i] : iに行く方法
dp[1] = 1

memo = list()

for i in range(1, N+1):
    # for s in S:
    #     if i + s <= N:
    #         dp[i + s] += dp[i]
    #         dp[i + s] %= MOD
    for m in memo:
        # l = m[1]
        # r = m[2]
        if m[1] <= i and i <= m[2]:
            dp[i] += m[0]
            dp[i] %= MOD
    
    for lr in LR:
        memo.append([dp[i], lr[0] + i, lr[1] + i])
    
print(dp[N])

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

dp = [0]*(N+1)
acc = [0]*(N+1) # acc[i] = dp[1] + ... dp[i]

dp[1] = 1
acc[1] = 1
for i in range(2, N+1):
    for lr in LR:
        l = lr[0]
        r = lr[1]

        dp[i] += (acc[max(0, i - l)] - acc[max(0, i - r - 1)] + MOD)
        dp[i] %= MOD
    acc[i] = (acc[i-1] + dp[i]) % MOD
    
    

print(dp[N])
# print(acc)
# print(dp[N])