Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

MOD = 998244353
n, k = map(int, input().split())
s = set()
for i in range(k):
    a, b = map(int, input().split())
    s.update(range(a, b + 1))
s = sorted(list(s))

dp = [0] + [0] * n
dp[1] = 1
for i in range(1, n + 1):
    for j in s:
        if i + j > n:
            break
        else:
            dp[i + j] = (dp[i + j] + dp[i]) % MOD
print(dp[n])


Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

MOD = 998244353
n, k = map(int, input().split())
s = list()
for i in range(k):
    s.append(tuple(map(int, input().split())))

dp = [0] + [0] * n
diff = [0] + [0] * n
dp[1] = 1
for i in range(1, n):
    for j, k in s:
        if i + j > n:
            continue
        diff[i + j] += dp[i]
        if i + k + 1 > n:
            continue
        diff[i + k + 1] -= dp[i]
    dp[i] = (dp[i - 1] + diff[i]) % MOD
    dp[i + 1] = (dp[i] + diff[i + 1]) % MOD
print(dp[n])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

MOD = 998244353
n, k = map(int, input().split())
s = set()
for i in range(k):
    a, b = map(int, input().split())
    s.update(range(a, b + 1))
s = sorted(list(s))

dp = [0] + [-1] * n
def dfs(goal, route):
    if dp[goal] != -1:
        return dp[goal]
    else:
        ans = 0
        for r in route:
            if goal - r < 1:
                break
            else:
                ans = (ans + dfs(goal - r, route)) % MOD
        dp[goal] = ans
        return dp[goal]
dp[1] = 1
print(dfs(n, s))


Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

MOD = 998244353
n, k = map(int, input().split())
s = list()
for i in range(k):
    s.append(tuple(map(int, input().split())))

dp = [0] + [0] * n
diff = [0] + [0] * n
dp[1] = 1
for i in range(1, n):
    for j, k in s:
        if i + j > n:
            continue
        diff[i + j] += dp[i]
        if i + k + 1 > n:
            continue
        diff[i + k + 1] -= dp[i]
    dp[i] = (dp[i - 1] + diff[i]) % MOD
    dp[i + 1] = (dp[i] + diff[i + 1]) % MOD
print(dp[n])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

MOD = 998244353
n, k = map(int, input().split())
s = set()
for i in range(k):
    a, b = map(int, input().split())
    s.update(range(a, b + 1))
s = sorted(list(s))

dp = [0] + [-1] * n
def dfs(goal, route):
    if dp[goal] != -1:
        return dp[goal]
    else:
        ans = 0
        for r in route:
            if goal - r < 1:
                break
            else:
                ans = (ans + dfs(goal - r, route)) % MOD
        dp[goal] = ans
        return dp[goal]
dp[1] = 1
print(dfs(n, s))


Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

MOD = 998244353
n, k = map(int, input().split())
s = list()
for i in range(k):
    s.append(tuple(map(int, input().split())))

dp = [0] + [0] * n
diff = [0] + [0] * n
dp[1] = 1
for i in range(1, n):
    for j, k in s:
        if i + j > n:
            continue
        diff[i + j] += dp[i]
        if i + k + 1 > n:
            continue
        diff[i + k + 1] -= dp[i]
    dp[i] = (dp[i - 1] + diff[i]) % MOD
    dp[i + 1] = (dp[i] + diff[i + 1]) % MOD
print(dp[n])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

MOD = 998244353
n, k = map(int, input().split())
s = set()
for i in range(k):
    a, b = map(int, input().split())
    s.update(range(a, b + 1))

dp = [0] + [-1] * n
def dfs(goal, route):
    if dp[goal] != -1:
        return dp[goal]
    else:
        ans = 0
        for r in route:
            if goal - r < 1:
                continue
            else:
                ans = (ans + dfs(goal - r, route)) % MOD
        dp[goal] = ans
        return dp[goal]
dp[1] = 1
print(dfs(n, s))


Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

MOD = 998244353
n, k = map(int, input().split())
s = list()
for i in range(k):
    s.append(tuple(map(int, input().split())))

dp = [0] + [0] * n
diff = [0] + [0] * n
dp[1] = 1
for i in range(1, n):
    for j, k in s:
        if i + j > n:
            continue
        diff[i + j] += dp[i]
        if i + k + 1 > n:
            continue
        diff[i + k + 1] -= dp[i]
    dp[i] = (dp[i - 1] + diff[i]) % MOD
    dp[i + 1] = (dp[i] + diff[i + 1]) % MOD
print(dp[n])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

MOD = 998244353
n, k = map(int, input().split())
s = set()
for i in range(k):
    a, b = map(int, input().split())
    s.update(range(a, b + 1))

dp = [0] + [-1] * n
def dfs(goal, route):
    if dp[goal] != -1:
        return dp[goal]
    else:
        ans = 0
        for r in route:
            if goal - r < 1:
                continue
            else:
                ans = (ans + dfs(goal - r, route)) % MOD
        dp[goal] = ans
        return dp[goal]
dp[1] = 1
print(dfs(n, s))


Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

MOD = 998244353
n, k = map(int, input().split())
s = list()
for i in range(k):
    s.append(tuple(map(int, input().split())))

dp = [0] + [0] * n
diff = [0] + [0] * n
dp[1] = 1
for i in range(1, n):
    for j, k in s:
        if i + j > n:
            continue
        diff[i + j] += dp[i]
        if i + k + 1 > n:
            continue
        diff[i + k + 1] -= dp[i]
    dp[i] = (dp[i - 1] + diff[i]) % MOD
    dp[i + 1] = (dp[i] + diff[i + 1]) % MOD
print(dp[n])