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

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

for i in range(2, N+1):
    sum_list = [0 for L, R in S]

    j = 0
    for L, R in S:
        RR = i - L
        if RR <= 0:
            continue
        LL = max(1, i-R)
        if sum_list[j] == 0:
            t = sum(dp[LL:RR+1]) % MOD
            sum_list[j] = t
            dp[i] += t
        else:
            if LL >= 2:
                sum_list[j] -= dp[1]
            sum_list[j] += dp[RR]
            sum_list[j] %= MOD
            dp[i] += sum_list[j]
        j += 1

    dp[i] %= MOD

print(dp[N])


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

dp = [0] * (N + 1)
dp[1] = 1
sum_list = [0] * (N + 1)
sum_list[1] = 1

for i in range(2, N+1):
    for L, R in S:
        RR = i - L
        if RR <= 0:
            continue
        LL = max(1, i-R)
        if LL <= RR:
            t = sum_list[RR] - sum_list[LL-1]
            dp[i] += t
    sum_list[i] = (sum_list[i-1] + dp[i]) % MOD
    dp[i] %= MOD

print(dp[N])

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

dp = [0] * (N + 1)
dp[1] = 1
sum_list = [0] * (N + 1)
sum_list[1] = 1

for i in range(2, N+1):
    for L, R in S:
        RR = i - L
        if RR <= 0:
            continue
        LL = max(1, i-R)
        if LL <= RR:
            t = sum_list[RR] - sum_list[LL-1]
            dp[i] += t
    sum_list[i] = sum_list[i-1] + dp[i]
    dp[i] %= MOD

print(dp[N])


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

dp = [0] * (N + 1)
dp[1] = 1
sum_list = [0] * (N + 1)
sum_list[1] = 1

for i in range(2, N+1):
    for L, R in S:
        RR = i - L
        if RR <= 0:
            continue
        LL = max(1, i-R)
        if LL <= RR:
            t = sum_list[RR] - sum_list[LL-1]
            dp[i] += t
    sum_list[i] = (sum_list[i-1] + dp[i]) % MOD
    dp[i] %= MOD

print(dp[N])

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

dp = [0] * (N + 1)
dp[1] = 1
sum_list = [0] * (N + 1)
sum_list[1] = 1

for i in range(2, N+1):
    for L, R in S:
        RR = i - L
        if RR <= 0:
            continue
        LL = max(1, i-R)
        if LL <= RR:
            t = sum_list[RR] - sum_list[LL-1]
            dp[i] += t
    sum_list[i] = sum_list[i-1] + dp[i]
    dp[i] %= MOD

print(dp[N])


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

dp = [0] * (N + 1)
dp[1] = 1
sum_list = [0] * (N + 1)
sum_list[1] = 1

for i in range(2, N+1):
    for L, R in S:
        RR = i - L
        if RR <= 0:
            continue
        LL = max(1, i-R)
        if LL <= RR:
            t = sum_list[RR] - sum_list[LL-1]
            dp[i] += t
    sum_list[i] = (sum_list[i-1] + dp[i]) % MOD
    dp[i] %= MOD

print(dp[N])

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

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

for i in range(2, N+1):
    sum_list = [0 for L, R in S]

    j = 0
    for L, R in S:
        RR = i - L
        if RR <= 0:
            continue
        LL = max(1, i-R)
        if sum_list[j] == 0:
            t = sum(dp[LL:RR+1])
            sum_list[j] = t
            dp[i] += t
        else:
            if LL >= 2:
                sum_list[j] -= dp[1]
            sum_list[j] += dp[RR]
            dp[i] += sum_list[j]
        j += 1

    dp[i] %= MOD

print(dp[N])


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

dp = [0] * (N + 1)
dp[1] = 1
sum_list = [0] * (N + 1)
sum_list[1] = 1

for i in range(2, N+1):
    for L, R in S:
        RR = i - L
        if RR <= 0:
            continue
        LL = max(1, i-R)
        if LL <= RR:
            t = sum_list[RR] - sum_list[LL-1]
            dp[i] += t
    sum_list[i] = (sum_list[i-1] + dp[i]) % MOD
    dp[i] %= MOD

print(dp[N])

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

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

for i in range(2, N+1):
    sum_list = [0 for L, R in S]

    j = 0
    for L, R in S:
        RR = i - L
        if RR <= 0:
            continue
        LL = max(1, i-R)
        if sum_list[j] == 0:
            t = sum(dp[LL:RR+1])
            sum_list[j] = t
            dp[i] += t
        else:
            if LL >= 2:
                sum_list[j] -= dp[1]
            sum_list[j] += dp[RR]
            dp[i] += sum_list[j]
        j += 1

    dp[i] %= MOD

print(dp[N])


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

dp = [0] * (N + 1)
dp[1] = 1
sum_list = [0] * (N + 1)
sum_list[1] = 1

for i in range(2, N+1):
    for L, R in S:
        RR = i - L
        if RR <= 0:
            continue
        LL = max(1, i-R)
        if LL <= RR:
            t = sum_list[RR] - sum_list[LL-1]
            dp[i] += t
    sum_list[i] = (sum_list[i-1] + dp[i]) % MOD
    dp[i] %= MOD

print(dp[N])

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

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

for i in range(2, N+1):
    for L, R in S:
        RR = i - L
        if RR <= 0:
            continue
        LL = max(1, i-R)
        dp[i] += sum(dp[LL:RR+1])
    dp[i]

print(dp[N] % MOD)


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

dp = [0] * (N + 1)
dp[1] = 1
sum_list = [0] * (N + 1)
sum_list[1] = 1

for i in range(2, N+1):
    for L, R in S:
        RR = i - L
        if RR <= 0:
            continue
        LL = max(1, i-R)
        if LL <= RR:
            t = sum_list[RR] - sum_list[LL-1]
            dp[i] += t
    sum_list[i] = (sum_list[i-1] + dp[i]) % MOD
    dp[i] %= MOD

print(dp[N])

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

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

for i in range(2, N+1):
    for L, R in S:
        RR = i - L
        if RR <= 0:
            continue
        LL = max(1, i-R)
        dp[i] += sum(dp[LL:RR+1])
    dp[i] %= MOD

print(dp[N])


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

dp = [0] * (N + 1)
dp[1] = 1
sum_list = [0] * (N + 1)
sum_list[1] = 1

for i in range(2, N+1):
    for L, R in S:
        RR = i - L
        if RR <= 0:
            continue
        LL = max(1, i-R)
        if LL <= RR:
            t = sum_list[RR] - sum_list[LL-1]
            dp[i] += t
    sum_list[i] = (sum_list[i-1] + dp[i]) % MOD
    dp[i] %= MOD

print(dp[N])

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

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

for i in range(2, N+1):
    for L, R in S:
        RR = i - L
        if RR <= 0:
            continue
        LL = max(1, i-R)
        dp[i] += sum(dp[LL:RR+1])
    dp[i] %= MOD

print(dp[N])


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

dp = [0] * (N + 1)
dp[1] = 1
sum_list = [0] * (N + 1)
sum_list[1] = 1

for i in range(2, N+1):
    for L, R in S:
        RR = i - L
        if RR <= 0:
            continue
        LL = max(1, i-R)
        if LL <= RR:
            t = sum_list[RR] - sum_list[LL-1]
            dp[i] += t
    sum_list[i] = (sum_list[i-1] + dp[i]) % MOD
    dp[i] %= MOD

print(dp[N])