Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import groupby, accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()
A = [k for k, g in groupby(A)]
i = 1
ans = 0

while i < N-1:
	if A[i-1] < A[i] > A[i+1] or A[i-1] > A[i] < A[i+1]:
		ans += 1
		i += 1
	i += 1

print(ans+1)


Fixed submission:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import groupby, accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()
A = [k for k, g in groupby(A)]
N = len(A)
i = 1
ans = 0

while i < N-1:
	if A[i-1] < A[i] > A[i+1] or A[i-1] > A[i] < A[i+1]:
		ans += 1
		i += 1
	i += 1

print(ans+1)
Buggy python submission (verdict: Runtime Error):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

print(max(A*B, C*D))


Fixed submission:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

A, B, C, D = MAP()

print(max(A*B, C*D))
Buggy python submission (verdict: Time Limit Exceeded):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, T = MAP()
A = LIST()
B = [sorted(A[i+1:N])[-1]-A[i] for i in range(N-1)]
# print(B)
print(B.count(max(B)))

Fixed submission:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, T = MAP()
A = LIST()
# B = [max(A[i+1:N])-A[i] for i in range(N-1)] # O(N^2)時間かかる
# print(B)
min_ = INF
B = []
for i in A:
	B.append(i-min_)
	# print(min_)
	if min_ > i:
		min_ = i
# print(B)
print(B.count(max(B)))

Buggy python submission (verdict: Time Limit Exceeded):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, T = MAP()
A = LIST()
B = [max(A[i+1:N])-A[i] for i in range(N-1)]
# print(B)
print(B.count(max(B)))

Fixed submission:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, T = MAP()
A = LIST()
# B = [max(A[i+1:N])-A[i] for i in range(N-1)] # O(N^2)時間かかる
# print(B)
min_ = INF
B = []
for i in A:
	B.append(i-min_)
	# print(min_)
	if min_ > i:
		min_ = i
# print(B)
print(B.count(max(B)))
Buggy python submission (verdict: Time Limit Exceeded):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
TA = [LIST() for _ in range(N)]
vote_T = TA[0][0]
vote_A = TA[0][1]
if len(TA)>1:
	for Ti, Ai in TA[1:]:
		n = 1
		tmp_Ti = Ti * n
		tmp_Ai = Ai * n
		while tmp_Ti < vote_T or tmp_Ai < vote_A:
			n += 1
			tmp_Ti = Ti * n
			tmp_Ai = Ai * n
		vote_T = tmp_Ti
		vote_A = tmp_Ai
print(vote_A + vote_T)

Fixed submission:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
TA = [LIST() for _ in range(N)]
vote_T = 1
vote_A = 1
for x, y in TA:
	# n = max(ceil(vote_T/x),ceil(vote_A/y))
	# n = max(-(-vote_T // x), -(-vote_A // y))
	n = max((vote_T//x + (vote_T%x!=0)),vote_A//y + (vote_A%y!=0))
	vote_T = x * n
	vote_A = y * n
print(vote_A + vote_T)
Buggy python submission (verdict: Runtime Error):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

a = INT()
b = INT()
h = INT()
print(int((a+b)*h/2))import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

a = INT()
b = INT()
h = INT()
print(int((a+b)*h/2))

Fixed submission:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

a = INT()
b = INT()
h = INT()
print(int((a+b)*h/2))
Buggy python submission (verdict: Runtime Error):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


n, m = map(int, input().split())
uf = UnionFind(n)

for i in range(m):
    a, b = map(int, input().split())
    uf.union(a-1, b-1)

print(uf.group_count() - 1)

Fixed submission:
k = int(input())

res = ''
while(k >= 1):
    res += 'ACL'
    k -= 1
print(res)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())

a = 0
while n > 0:
    mod = n % 10
    a += mod
    n = n // 10
if a % 9 == 0:
    print('Yes')
else:
    print('No')

Fixed submission:
n_list = list(input())

a = 0
for num_s in n_list:
    a += int(num_s)

if a % 9 == 0:
    print('Yes')
else:
    print('No')
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
a_list = list(map(int, input().split()))

res = 1
for a in a_list:
    res *= a
if res > (10 ** 18):
    res = -1
print(res)

Fixed submission:
N = int(input())
a_list = list(map(int, input().split()))

res = 1
if 0 in a_list:
    print(0)
    exit()

for a in a_list:
    res *= a
    if res > (10 ** 18):
        res = -1
        break
print(res)
Buggy python submission (verdict: Runtime Error):
L, R = map(int , input().split())

ans = 10 ** 9
for i range(L, R+1):
    for j range(i, R):
        mod = i * j % 2019
        if ans > mod:
            ans = mod
        elif mod == 0:
            ans = 0
            break
    else:
        continue
    break
print(ans)

Fixed submission:
L, R = map(int, input().split())

ans = 10 ** 9
for i in range(L, R):
    for j in range(i+1, R+1):
        tmp = (i*j)%2019
        if ans > tmp:
            ans = tmp
        if ans == 0:
            break
    else:
        continue
    break
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
L, R = map(int, input().split())

ans = 10 ** 9
for i in range(L, R):
  for j in range(i+1, R+1):
    tmp = (i*j)%2019
    if ans > tmp:
      ans = tmp
    if ans == 0:
      break
print(ans)

Fixed submission:
L, R = map(int, input().split())

ans = 10 ** 9
for i in range(L, R):
    for j in range(i+1, R+1):
        tmp = (i*j)%2019
        if ans > tmp:
            ans = tmp
        if ans == 0:
            break
    else:
        continue
    break
print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
readline=sys.stdin.readline

import numpy as np
from numba import njit,i8

N,K=map(int,readline().split())
DIV = 998244353
steps = []
for i in range(K):
  l,r = map(int,readline().split())
  for j in range(l, r + 1):
    steps.append(j)
    
steps = sorted(steps)
steps = np.array(steps, dtype = int)

@njit(i8(i8[:]),cache = True)
def solve(steps):
  dp = np.zeros(N, dtype = int)
  dp[0] = 1
  for i in range(len(dp)):
    for s in steps:
      if i + s >= len(dp):
        break
      dp[i + s] += dp[i]
      dp[i + s] %= DIV
      
  return dp[-1]

print(solve())


Fixed submission:
import sys
readline = sys.stdin.readline

N,K = map(int,readline().split())
DIV = 998244353

L = [None] * K
R = [None] * K
for i in range(K):
  L[i],R[i] = map(int,readline().split())

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

Buggy python submission (verdict: Time Limit Exceeded):
import sys
readline=sys.stdin.readline

N,K=map(int,readline().split())
DIV = 998244353
steps = []
for i in range(K):
  l,r = map(int,readline().split())
  for j in range(l, r + 1):
    steps.append(j)
    
steps = sorted(steps)

dp = [0] * (N)
dp[0] = 1
for i in range(len(dp)):
  for s in steps:
    if i + s >= len(dp):
      break
    dp[i + s] += dp[i]
    dp[i + s] %= DIV
    
print(dp[-1])


Fixed submission:
import sys
readline = sys.stdin.readline

N,K = map(int,readline().split())
DIV = 998244353

L = [None] * K
R = [None] * K
for i in range(K):
  L[i],R[i] = map(int,readline().split())

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

Buggy python submission (verdict: Time Limit Exceeded):
import sys
readline=sys.stdin.readline

N,K=map(int,readline().split())
DIV = 998244353
steps = []
for i in range(K):
  l,r = map(int,readline().split())
  for j in range(l, r + 1):
    steps.append(j)
    
steps = sorted(steps)

dp = [0] * (N)
dp[0] = 1
for i in range(len(dp)):
  for s in steps:
    if i + s >= len(dp):
      break
    dp[i + s] += dp[i]
    dp[i + s] %= DIV
    
print(dp[-1])


Fixed submission:
import sys
readline = sys.stdin.readline

N,K = map(int,readline().split())
DIV = 998244353

L = [None] * K
R = [None] * K
for i in range(K):
  L[i],R[i] = map(int,readline().split())

dp = [0] * (N + 1)
sdp = [0] * (N + 1)
dp[1] = 1
sdp[1] = 1
  
for i in range(2, len(dp)):
  for j in range(K):
    li = max(i - R[j], 0)
    ri = i - L[j]
    if ri < 0:
      continue
    dp[i] += (sdp[ri] - sdp[li - 1])
    dp[i] %= DIV
  sdp[i] = sdp[i - 1] + dp[i]
  sdp[i] %= DIV
  
print(dp[N])
Buggy python submission (verdict: Runtime Error):
import sys
readline=sys.stdin.readline

N,X,M = map(int,readline().split())
route = [X]
dic = {}
first = []
loop = []
for i in range(1, N):
  X = (X ** 2) % M
  if X in dic:
    first = route[:dic[X]]
    loop = route[dic[X]:]
    break
  route.append(X)
  dic[X] = i

if N == len(first):
  print(sum(first))
elif N < len(first):
  print(sum(first[:N]))
else:
  ans = sum(first)
  one_loop = sum(loop)
  N -= len(first)
  loop_cnt = N // len(loop)
  rest = N % len(loop)
  ans += loop_cnt * (sum(loop))
  ans += sum(loop[:rest])

  print(ans)


Fixed submission:
import sys
readline=sys.stdin.readline

N,X,M = map(int,readline().split())
route = [X]
dic = {}
first = []
loop = []
for i in range(1, N):
  X = (X ** 2) % M
  if X in dic:
    first = route[:dic[X]]
    loop = route[dic[X]:]
    break
  route.append(X)
  dic[X] = i
  
if len(first) == 0:
  print(sum(route[:N]))
  exit(0)

if N == len(first):
  print(sum(first))
elif N < len(first):
  print(sum(first[:N]))
else:
  ans = sum(first)
  one_loop = sum(loop)
  N -= len(first)
  loop_cnt = N // len(loop)
  rest = N % len(loop)
  ans += loop_cnt * (sum(loop))
  ans += sum(loop[:rest])

  print(ans)

Buggy python submission (verdict: Runtime Error):
import sys
readline=sys.stdin.readline

N,X,M = map(int,readline().split())
route = [X]
dic = {}
first = []
loop = []
for i in range(1, 10000):
  X = (X ** 2) % M
  if X in dic:
    first = route[:dic[X]]
    loop = route[dic[X]:]
    break
  route.append(X)
  dic[X] = i

#print(first)
#print(loop)

if N == len(first):
  print(sum(first))
elif N < len(first):
  print(sum(first[:N]))
else:
  ans = sum(first)
  one_loop = sum(loop)
  N -= len(first)
  loop_cnt = N // len(loop)
  rest = N % len(loop)
  ans += loop_cnt * (sum(loop))
  ans += sum(loop[:rest])

  print(ans)


Fixed submission:
import sys
readline=sys.stdin.readline

N,X,M = map(int,readline().split())
route = [X]
dic = {}
first = []
loop = []
for i in range(1, N):
  X = (X ** 2) % M
  if X in dic:
    first = route[:dic[X]]
    loop = route[dic[X]:]
    break
  route.append(X)
  dic[X] = i
  
if len(first) == 0:
  print(sum(route[:N]))
  exit(0)

if N == len(first):
  print(sum(first))
elif N < len(first):
  print(sum(first[:N]))
else:
  ans = sum(first)
  one_loop = sum(loop)
  N -= len(first)
  loop_cnt = N // len(loop)
  rest = N % len(loop)
  ans += loop_cnt * (sum(loop))
  ans += sum(loop[:rest])

  print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
readline=sys.stdin.readline

N = int(readline())

DIV = 10 ** 9 + 7

dp = [[0] * 4 for i in range(N + 1)]

dp[0][0] = 1

for i in range(1, N + 1):
  dp[i][0] += (dp[i - 1][0] * 8) % DIV
  dp[i][0] %= DIV
  
  dp[i][1] += dp[i - 1][0] + (dp[i - 1][1] * 9) % DIV
  dp[i][1] %= DIV
  
  dp[i][2] += dp[i - 1][0] + (dp[i - 1][2] * 9) % DIV
  dp[i][2] %= DIV
  
  dp[i][3] += dp[i - 1][1] + dp[i - 1][2] + (dp[i - 1][3] * 10) % DIV
  dp[i][3] %= DIV
  
print(dp[-1][3])


Fixed submission:
import sys
readline=sys.stdin.readline

N = int(readline())

DIV = 10 ** 9 + 7

# dp[i][j][k] = i - 1桁目で、すでに0が出た(j), すでに9が出た(k)

dp = [[[0] * 2 for j in range(2)] for i in range(N + 1)]

dp[0][0][0] = 1

for i in range(1, N + 1):
  dp[i][0][0] += dp[i - 1][0][0] * 8 # まだ0も9も出ない
  dp[i][0][0] %= DIV
  
  dp[i][1][0] += dp[i - 1][0][0] # 0が出た
  dp[i][1][0] += dp[i - 1][1][0] * 9 # 9以外何が出てもよい
  dp[i][1][0] %= DIV
  
  dp[i][0][1] += dp[i - 1][0][0] # 9が出た
  dp[i][0][1] += dp[i - 1][0][1] * 9 # 0以外何が出てもよい
  dp[i][0][1] %= DIV
  
  dp[i][1][1] += dp[i - 1][1][0] # 9が出た
  dp[i][1][1] += dp[i - 1][0][1] # 0が出た
  dp[i][1][1] += dp[i - 1][1][1] * 10 # 何が出てもよい
  dp[i][1][1] %= DIV
  
print(dp[-1][1][1])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
readline=sys.stdin.readline

N = int(readline())

DIV = 10 ** 9 + 7

dp = [[0] * 4 for i in range(N + 1)]

dp[0][0] = 1

for i in range(1, N + 1):
  dp[i][0] += dp[i - 1][0] * 8
  dp[i][0] %= DIV
  
  dp[i][1] += dp[i - 1][0] + dp[i - 1][1] * 9
  dp[i][1] %= DIV
  
  dp[i][2] += dp[i - 1][0] + dp[i - 1][2] * 9
  dp[i][2] %= DIV
  
  dp[i][3] += dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3] * 10
  dp[i][3] %= DIV
  
print(dp[-1][3])


Fixed submission:
import sys
readline=sys.stdin.readline

N = int(readline())

DIV = 10 ** 9 + 7

# dp[i][j][k] = i - 1桁目で、すでに0が出た(j), すでに9が出た(k)

dp = [[[0] * 2 for j in range(2)] for i in range(N + 1)]

dp[0][0][0] = 1

for i in range(1, N + 1):
  dp[i][0][0] += dp[i - 1][0][0] * 8 # まだ0も9も出ない
  dp[i][0][0] %= DIV
  
  dp[i][1][0] += dp[i - 1][0][0] # 0が出た
  dp[i][1][0] += dp[i - 1][1][0] * 9 # 9以外何が出てもよい
  dp[i][1][0] %= DIV
  
  dp[i][0][1] += dp[i - 1][0][0] # 9が出た
  dp[i][0][1] += dp[i - 1][0][1] * 9 # 0以外何が出てもよい
  dp[i][0][1] %= DIV
  
  dp[i][1][1] += dp[i - 1][1][0] # 9が出た
  dp[i][1][1] += dp[i - 1][0][1] # 0が出た
  dp[i][1][1] += dp[i - 1][1][1] * 10 # 何が出てもよい
  dp[i][1][1] %= DIV
  
print(dp[-1][1][1])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
readline=sys.stdin.readline

S = int(readline())

# 最も多い箱の数は、N = S // 3個
# Nから1個の箱i個に対して、残った数値（S - 3 * i）を分ける場合の数を足し合わせる

N = S // 3

DIV = 10 ** 9 + 7
n = (10 ** 6) * 2
g1 = [1] * 2 + [0] * (n - 2) # 元テーブル
g2 = [1] * 2 + [0] * (n - 2) #逆元テーブル
inverse = [0, 1] + [0] * (n - 2) #逆元テーブル計算用テーブル

for i in range(2, n):
  g1[i] = (g1[i - 1] * i) % DIV
  inverse[i] = (-inverse[DIV % i] * (DIV // i)) % DIV
  g2[i] = (g2[i - 1] * inverse[i]) % DIV

def nCr(n, r, DIV):
  if (r < 0 or r > n):
    return 0
  r = min(r, n-r)
  return g1[n] * g2[r] * g2[n-r] % DIV

ans = 0
for i in range(N, 0, -1):
  rest = S - 3 * i
  if rest <= 0:
    ans += 1
    continue
  # rest個をi個の箱に分ける
  # rest + i - 1 C min(rest, i - 1)
  ans += nCr(rest + i - 1, rest, DIV)
  ans %= DIV
  
print(ans)


Fixed submission:
import sys
readline=sys.stdin.readline

S = int(readline())

# 最も多い箱の数は、N = S // 3個
# Nから1個の箱i個に対して、残った数値（S - 3 * i）を分ける場合の数を足し合わせる

N = S // 3

DIV = 10 ** 9 + 7
n = (10 ** 6) * 2
g1 = [1] * 2 + [0] * (n - 2) # 元テーブル
g2 = [1] * 2 + [0] * (n - 2) #逆元テーブル
inverse = [0, 1] + [0] * (n - 2) #逆元テーブル計算用テーブル

for i in range(2, n):
  g1[i] = (g1[i - 1] * i) % DIV
  inverse[i] = (-inverse[DIV % i] * (DIV // i)) % DIV
  g2[i] = (g2[i - 1] * inverse[i]) % DIV

def nCr(n, r, DIV):
  if (r < 0 or r > n):
    return 0
  r = min(r, n-r)
  return g1[n] * g2[r] * g2[n-r] % DIV

ans = 0
for i in range(N, 0, -1):
  rest = S - 3 * i
  if rest <= 0:
    ans += 1
    continue
  # rest個をi個の箱に分ける
  # rest + i - 1 C min(rest, i - 1)
  ans += nCr(rest + i - 1, rest, DIV)
  ans %= DIV
  
print(ans)