Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

n = int(input())
ans = 1 
a = list(map(int,input().split()))
for i in range(n):
  ans *= a[i]
if ans > 1000000000000000000:
  print("-1")
else:
  print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))

ans = 1

if 0 in a:
    ans = 0
else:
    for i in a:
        ans *= i
        if(ans > 10**18):
            ans = -1
            break
print(ans)
### BUGGY CODE ###

import bisect

n = int(input())
s = input()

RGB = [[], [], []]
for i in range(n):
    if s[i] == 'R':
        RGB[0].append(i)
    elif s[i] == 'G':
        RGB[1].append(i)
    else:
        RGB[2].append(i)
total = len(RGB[0]) * len(RGB[1]) * len(RGB[2])
len_B=len(RGB[2])
for r in RGB[0]:
    for g in RGB[1]:
        dif = abs(r - g)
        up = max(r,g)+dif
        down = min(r,g)-dif
        up_posi=bisect.bisect_left(RGB[2],up)

        if up_posi < len_B:
            if RGB[2][up_posi]==up:
                total-=1
        down_posi=bisect.bisect_left(RGB[2],down)
        if down_posi < len_B:
            if RGB[2][down_posi]==down:
                total-=1
        if dif % 2 == 0:
            center = (r+g)/2
            center_posi=bisect.bisect_left(RGB[2], center)
            if center_posi < len_B:
                if RGB[2][center_posi]==center:
                    total-=1
print(total)

### FIXED CODE ###

import bisect
import itertools

n = int(input())
s = input()

RGB = [[], [], []]
for i in range(n):
    if s[i] == 'R':
        RGB[0].append(i)
    elif s[i] == 'G':
        RGB[1].append(i)
    else:
        RGB[2].append(i)
total = len(RGB[0]) * len(RGB[1]) * len(RGB[2])
RGB.sort(key=lambda x:len(x))
len_B=len(RGB[2])
max_B=max(RGB[2])
min_B=min(RGB[2])
#for r in RGB[0]:
#    for g in RGB[1]:
bool_B=[False for i in range(n)]
for i in RGB[2]:
    bool_B[i]=True

for rg in itertools.product(RGB[0],RGB[1]):
    r=rg[0]
    g=rg[1]
    dif = abs(r - g)

    up = max(r,g)+dif
    down = min(r,g)-dif

    if max_B >=up:
        if bool_B[up]:
            total-=1
    if min_B <= down and max_B >= down:
        if bool_B[down]:
            total-=1
    if dif % 2 == 0:
        center = (r+g)//2
        if min_B<=center and max_B >= center:
            if bool_B[center]:
                total-=1
print(total)
### BUGGY CODE ###

N, M = list(map(int, input().split()))
p = list(map(int, input().split()))

set_list = []
edge = [[] for _ in range(N)]
for i in range(M):
    x, y = list(map(int, input().split()))
    x, y = x-1, y-1

    s1 = None
    s2 = None
    for i, se in enumerate(set_list):
        if x in se:
            s1 = se
        if y in se:
            s2 = se

    if s1 == None:
        if s2 == None:
            set_list.append({x, y})
        else:
            s2.add(x)
    else:
        if s2 == None:
            s1.add(y)
        elif s1 == s2:
            continue
        else:
            s = s1 | s2
            set_list.append(s)
            set_list.remove(s1)
            set_list.remove(s2)
count = 0
for i in range(N):
    if p[i] == i+1:
        count += 1
    else:
        for se in set_list:
            if {i, p[i]-1} <= se:
                count += 1
                continue

print(count)


### FIXED CODE ###

def root(R, a):
    if R[a] != a:
        R[a] = root(R, R[a])
    return R[a]

def union(R, x, y):
    a = root(R, x)
    b = root(R, y)
    if a != b:
        R[a] = b


N, M = list(map(int, input().split()))
p = list(map(int, input().split()))

R = [i for i in range(N)]
for i in range(M):
    x, y = list(map(int, input().split()))
    x, y = x-1, y-1
    union(R, x, y)

count = 0
for i in range(N):
    if root(R, i) == root(R, p[i] - 1):
        count += 1

print(count)
### BUGGY CODE ###

n=int(input())
s=list(input())
info=[]
for i in range(10):
    for j in range(10):
        for k in range(10):
            info.append(str(i)+str(j)+str(k))
ans=0
kind=0
while kind<=999:
    point=0
    for i in range(n):
        if point==0:  
            if info[kind][0]==s[i]:
                point+=1
                continue
        if point==1:
            if info[kind][1]==s[i]:
                point+=1
                continue
        if point==2:
            if info[kind][2]==s[i]:
                point+=1
                break
    if point==3:
        ans+=1
        #print(info[kind])
    kind+=1
print(ans)

### FIXED CODE ###

#import time

#t1=time.time()
n=int(input())
s=list(input())
info=[]
for i in range(10):
    for j in range(10):
        for k in range(10):
            info.append(str(i)+str(j)+str(k))
ans=0
kind=0
while kind<=999:
    point=0
    check=info[kind]
    for i in range(n):
        if point==0:  
            if check[0]==s[i]:
                point+=1
                continue
        if point==1:
            if check[1]==s[i]:
                point+=1
                continue
        if point==2:
            if check[2]==s[i]:
                point+=1
                break
    if point==3:
        ans+=1
        #print(info[kind])
    kind+=1
print(ans)
#t2=time.time()
#print(t2-t1)
### BUGGY CODE ###

def merge(a, left, mid, right):
    global x
    n1 = mid - left
    n2 = right - mid
    l = []
    r = [] 
    for i in range(n1):
        l.append(a[left + i])
    for i in range(n2):
        r.append(a[mid + i])
    l.append(float("inf"))
    r.append(float("inf"))
    i = 0
    j = 0
    for k in range(left,right):
        if l[i] <= r[j]:
            a[k] = l[i]
            i += 1
            x += 1
        else :
            a[k] = r[j]
            j += 1
            x += 1

def mergeSort(a, left, right):
    if left+1 < right:
        mid = int((left + right)/2)
        mergeSort(a, left, mid)
        mergeSort(a, mid, right)
        merge(a, left, mid, right)

n = int(input())
s = list(map(int,input().split()))
global x
x = 0
mergeSort(s,0,n)
print(*s)
print(x)



### FIXED CODE ###


def merge(a, left, mid, right):
    x = 0
    l = a[left:mid] + [float("inf")]
    r = a[mid:right] + [float("inf")]
    i = 0
    j = 0
    for k in range(left,right):
        if l[i] <= r[j]:
            a[k] = l[i]
            i += 1
        else :
            a[k] = r[j]
            j += 1
        x += 1
    return x

def mergeSort(a, left, right,x):
    if left+1 < right:
        mid = int((left + right)/2)
        mergeSort(a, left, mid,x)
        mergeSort(a, mid, right,x)
        x[0] += merge(a, left, mid, right)

n = int(input())
s = list(map(int,input().split()))
x = [0]
mergeSort(s,0,n,x)
print(*s)
print(x[0])
### BUGGY CODE ###

n = int(input())
s = list(input())

dp = [[0]*(n+1) for i in range(n+1)]
for i in range(n-1,-1,-1):
    for j in range(n-1,-1,-1):
        if s[i] == s[j]:
            dp[i][j] = dp[i+1][j+1] +1
        
ans = 0
for i in range(n-1):
    for j in range(i+1,n):
        ans = max(ans,min(dp[i][j],j-i))

print(ans)

### FIXED CODE ###

n = int(input())
s = list(input())

def z_algo(s):
    l = len(s)
    count = [0]*l
    i = 1
    j = 0
    count[0] = l
    while i < l:
        while i+j < l and s[i+j] == s[j]:
            j += 1
        count[i] = j
        if j == 0:
            i += 1
            continue
        
        k = 1
        while l - i > k and k < j-count[k]:
            count[i+k] = count[k]
            k += 1
        i += k
        j -= k
    return count
count = 0
for i in range(n):
    ans = z_algo(s[i:])
    for j in range(n-i):
        count = max(count,min(ans[j],j))

print(count)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
li = []
f = 0
for i in a:
    if i not in li:
        li.append(i)
    else:
        f += 1
if f % 2:
	print(len(li) - 1)
else:
	print(len(li))


### FIXED CODE ###

n = int(input())
a = map(int,input().split())
a = set(a)
f = n - len(a)

if f % 2:
	f += 1

print(n - f)
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
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()
H = LIST()
I = []
 
if N == 1:
  print(0)
  exit()
 
for i in range(N):
  c = 0
  j = 0
  while j < N-i-1 and H[i+j] >= H[i+j+1] :
    c += 1
    j += 1
    
  I.append(c)
  
    
print(int(max(I)))

### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
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()
H = LIST()
I = []

if N == 1:
  print(0)
  exit()
  
i = 0
 
while i < N :
  c = 0
  j = 0
  while j < N-i-1 and H[i+j] >= H[i+j+1] :
    c += 1
    j += 1
    
  I.append(c)
  i += c+1
  
print(int(max(I)))
### BUGGY CODE ###

N = int(input())
v = ((map(int, input().split())))
answer = 1
for i in v:
    answer = answer * i
answer = answer if answer <= 1000000000000000000 else -1
print(answer)

### FIXED CODE ###

N = int(input())
v = list(map(int, input().split()))
limit = 10 ** 18

answer = 1
if 0 in v:
  answer = 0
else:
  for i in v:
    answer = answer * i
    if answer <= limit:
      continue
    else:
      answer = -1
      break
print(answer)
### BUGGY CODE ###

a, b, x = map(int, input().split())
count = 0
for n in range(a, b+1):
    if n % x == 0:
        count += 1
        n += 1

print(count)


### FIXED CODE ###

a, b, x = map(int, input().split())
if a != 0:
    print( b // x - (a - 1)//x )
else:
    print(b // x + 1)
### BUGGY CODE ###


# class Point():
#   def __init__(self, x, y):
#     self.x = x
#     self.y = y
  
#   def __str__(self):
#     # return f"Point(x={self.x}, y={self.y})"
#     return "Point(x=" + str(self.x) + ", y=" + str(self.y) + ")"

#   def __repr__(self):
#     return self.__str__()

def parse():
  H, W = map(int, input().split(" "))
  grid = []
  for h in range(H):
    grid.append(list(input()))
  return H, W, grid

def print_grid(grid):
  H = len(grid)
  print("grid:")
  for y in range(H):
    print(grid[y])

def is_all_black(grid):
  H = len(grid)
  W = len(grid[0])
  for y in range(H):
    for x in range(W):
      if grid[y][x] == ".": return False
  return True

def main():
  H, W, grid = parse()
  # print(H, W, grid)

  # vecs = [Point(0, -1), Point(0, 1), Point(-1, 0), Point(1, 0)]
  vecs = [(0, -1), (0, 1), (-1, 0), (1, 0)]
  
  # 初期の黒色の場所を追加
  black_points = set()
  for y in range(H):
    for x in range(W):
      if grid[y][x] == "#":
        black_points.add((x, y))
        # black_points.append(Point(x, y))

  ans = 0
  while len(black_points) > 0:
  # while not is_all_black(grid):
    next_black_points = set()
    for black_point in black_points:
      # print("black_point:", black_point)
      for vec in vecs:
        x = black_point[0] + vec[0]
        y = black_point[1] + vec[1]
        # target_point = Point(black_point.x + vec.x, black_point.y + vec.y)
        if x < 0 or y < 0 or x >= W or y >= H or grid[y][x] == "#": continue
        grid[y][x] = "#"
        next_black_points.add((x, y))
    black_points = next_black_points
    ans += 1

    # print("next_black_points:", next_black_points)
    # print_grid(grid)
    # input()
  
  print(ans - 1)

if __name__ == "__main__":
  main()

### FIXED CODE ###


import numpy as np

def parse():
  H, W = map(int, input().split(" "))
  grid = [list(input()) for y in range(H)]
  return H, W, grid

def print_grid(grid):
  H = len(grid)
  print("grid:")
  for line in grid:
    for c in line:
      print(c, end="")
    print("")

def main():
  H, W, grid = parse()
  # print(H, W)
  # print_grid(grid)

  # visited = [[W * H if grid[y][x] == "." else 0 for x in range(W)] for y in range(H)]
  visited = np.zeros((H, W), int)
  for y in range(H):
    # visited.append([])
    for x in range(W):
      if grid[y][x] == ".":
        visited[y][x] = H * W

  for y in range(1, H):  # ↓
    # 要素ごとの処理
    # print(visited)
    visited[y][:] = np.minimum(visited[y][:], visited[y - 1][:] + 1)
    # print(visited)
    # input()
    # print(visited[y])
    # exit(0)

  for y in range(H - 2, -1, -1):
    visited[y, :] = np.minimum(visited[y, :], visited[y + 1][:] + 1)

  for x in range(1, W):
    visited[:, x] = np.minimum(visited[:, x], visited[:, x - 1] + 1)

  for x in range(W - 2, -1, -1):
    visited[:, x] = np.minimum(visited[:, x], visited[:, x + 1] + 1)

  # print(visited)
  # exit(0)

  # max_len = 0
  # for y in range(H):
  #   max_val = max(visited[y])
  #   max_len = max_len if max_len > max_val else max_val
  # print(max_len)
  print(np.max(visited))

if __name__ == "__main__":
  main()
### BUGGY CODE ###

N = int(input())
for i in range(1, N+1):
    ans = 0
    for x in range(1, int((10**2)//(6**(1/2)))):
        for y in range(1, int((10**2)//(6**(1/2)))):
            for z in range(1, int((10**2)//(6**(1/2)))):
                if x**2+y**2+z**2+x*y+y*z+z*x == i:
                    ans += 1
    print(ans)

### FIXED CODE ###

N = int(input())

def count(a, b, c):
    return (a+b+c)**2-a*b-b*c-c*a

table = [0] * (N+1)
for x in range(1, 101):
    for y in range(1, 101):
        for z in range(1, 101):
            tmp = count(x, y, z)
            if tmp <= N:
                table[tmp] += 1
print(*table[1:], sep="\n")
### BUGGY CODE ###

import sys, math
from collections import defaultdict, deque
from copy import deepcopy
import itertools
# 文字列の場合は普通のinput()を使うか下を使う
# input = sys.stdin.readline().rstrip()

N = int(input())
S = input()
q = deque([])
q_new = deque([])
d = {}
for i in range(10):
    for j in range(10):
        for k in range(10):
            q.append((i, j, k))
            d[(i, j, k)] = 0

ans = 0
for x in S:
    x = int(x)
    while q:
        (i, j, k) = q.popleft()
        n = d[(i, j, k)]
        if n == 2 and k == x:
            ans += 1
        else:
            if n == 0 and i == x:
                d[(i, j, k)] += 1
            elif n == 1 and j == x:
                d[(i, j, k)] += 1
            q_new.append((i, j, k))
        
    q = q_new
    q_new = deque([])
print(ans)

### FIXED CODE ###

import sys, math
from collections import defaultdict, deque
from copy import deepcopy
import itertools
# 文字列の場合は普通のinput()を使うか下を使う
# input = sys.stdin.readline().rstrip()

N = int(input())
S = input()
q = deque([])
q_new = deque([])
d = defaultdict(list)
for i in range(10):
    for j in range(10):
        for k in range(10):
            d[i].append([k, j, i])

ans = 0
for x in S:
    x = int(x)
    q = deepcopy(d[x])
    d[x] = []
    for key in q:
        l = len(key)
        if l == 3:
            d[key[1]].append(key[:2])
        elif l == 2:
            d[key[0]].append(key[:1])
        elif l == 1:
            ans += 1

print(ans)
### BUGGY CODE ###

import heapq
N,M = map(int,input().split())
A = list(map(int,input().split()))
heapq.heapify(A)
curmin = min(A)

for _ in range(M):
  b,c = map(int,input().split())
  if c <= curmin: continue

  cnt = 0
  while cnt < b and len(A)>0:
    a = heapq.heappop(A)
    if a >= c:
      heapq.heappush(A,a)
      break
    cnt += 1
    heapq.heappush(A,c)

  # for _ in range(cnt):
  #   heapq.heappush(A,c)

  curmin = min(A[0], c)

print(sum(A))

### FIXED CODE ###

N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()

cards = []
for _ in range(M):
  b,c = map(int,input().split())
  cards.append([c,b])
cards.sort(key=lambda x: -x[0])

res = 0
idx = 0
left = cards[idx][1]
for i,a in enumerate(A):
  if a > cards[idx][0]:
    res += sum(A[i:])
    break
  else:
    res += cards[idx][0]

    left -= 1
    if left <= 0:
      idx += 1
      if idx >= M:
        if i+1 < N:
          res += sum(A[i+1:])
        break
      else:
        left = cards[idx][1]

print(res)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

a = input() + "$"
n = len(a)

alph = "abcdefghijklmnopqrstuvwxyz"
dp = [-1] * (n + 1)

next_ = [[-1] * (n + 1) for i in range(26)]
for char in range(26):
    tmp = - 1
    for i in range(n)[::-1]:
        if a[i] == alph[char]:
            tmp = i + 1
        next_[char][i] = tmp


def solve(i):
    if dp[i] != -1:
        return dp[i]
    tmp = n + 1
    for char in range(26):
        if next_[char][i] == -1:
            dp[i] = 0
            return dp[i]
        tmp = min(solve(next_[char][i]) + 1 , tmp)
    dp[i] = tmp
    return dp[i]

solve(0)
ans = []
i = 0
while True:
    for char in range(26):
        if dp[i] == dp[next_[char][i]] + 1:
            ans.append(alph[char])
            i = next_[char][i]
            break
    else:
        break

print("".join(ans))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

a = input() + "$"
n = len(a)

alph = "abcdefghijklmnopqrstuvwxyz"
dp = [-1] * (n + 1)

next_ = [[-1] * (n + 1) for i in range(26)]
for char in range(26):
    tmp = - 1
    for i in range(n)[::-1]:
        if a[i] == alph[char]:
            tmp = i + 1
        next_[char][i] = tmp


def solve():
    for i in range(n + 1)[::-1]:
        tmp = n + 1
        for char in range(26):
            if next_[char][i] == -1:
                dp[i] = 1
                break
            tmp = min(dp[next_[char][i]] + 1 , tmp)
        else:
            dp[i] = tmp

solve()
ans = []
i = 0
while True:
    for char in range(26):
        if next_[char][i] == -1:
            ans.append(alph[char])
            print("".join(ans))
            exit()
        if dp[i] == dp[next_[char][i]] + 1:
            ans.append(alph[char])
            i = next_[char][i]
            break
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()
from collections import defaultdict

def main():
    N = int(input())
    S = input()

    R = []
    G = []
    B = []

    for i in range(N):
        if S[i] == 'R':
            R.append(i)
        if S[i] == 'G':
            G.append(i)
        if S[i] == 'B':
            B.append(i)

    base = len(R)*len(G)*len(B)

    cnt = 0
    for r in R:
        for g in G:
            for b in B:
                if abs(b-g) == abs(g-r) or abs(b-r) == abs(r-g) or abs(g-b) == abs(b-r) or abs(g-r) == abs(r-b) or abs(r-b) == abs(b-g) or abs(r-g) == abs(g-b):
                    cnt += 1



    print(base-cnt)  

if __name__ == "__main__":
    main() 

### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()

N = int(input())
S = input()

R = []
G = []
B = []

for i in range(N):
    if S[i] == 'R':
        R.append(i)
    if S[i] == 'G':
        G.append(i)
    if S[i] == 'B':
        B.append(i)

base = len(R)*len(G)*len(B)

cnt = 0
for i in range(N):
    for j in range(i+1, N):
        k = 2*j - i
        if k >= N or S[i] == S[j] or S[j] == S[k] or S[k] == S[i]:
            continue
        cnt += 1

print(base-cnt)
### BUGGY CODE ###

from scipy.sparse.csgraph import csgraph_from_dense, dijkstra
import sys
input = sys.stdin.readline
N = int(input())
abc = [map(int, input().split()) for i in range(N-1)]

Q, K = map(int, input().split())
xy = [map(int, input().split()) for i in range(Q)]

g = [[10**9+1]*N for i in range(N)]

for a, b, c in abc:
    g[a-1][b-1] = c
    g[b-1][a-1] = c

G = csgraph_from_dense(g, null_value=10**9+1)

g2 = dijkstra(G)
for x, y in xy:
    print(int(g2[x-1][K-1] + g2[K-1][y-1]))


### FIXED CODE ###

N=int(input())
abc=[tuple(map(int,input().split())) for i in range(N-1)]
g=[set() for i in range(N)]
for a,b,c in abc:
  g[a-1].add((b-1,c))
  g[b-1].add((a-1,c))
memo=[-1]*N

Q,K=map(int,input().split())
import collections
q=collections.deque([(K-1,0)])
memo[K-1]=0
while(q):
  
  x,w = q.popleft()
  for a,b in g[x]:
    if memo[a]==-1:
      memo[a]=w+b
      q.append((a,w+b))
  
for i in range(Q):
  x,y=map(int,input().split())
  print(memo[x-1]+memo[y-1])
### BUGGY CODE ###

import sys
n = int(sys.stdin.readline().rstrip("\n"))
l = [int(s) for s in sys.stdin.readline().rstrip("\n").split()]
s = 1
for i in l:
    s *= i
if s > 10**18:
    print(-1)
else:
    print(s)

### FIXED CODE ###

import sys
n = int(sys.stdin.readline().rstrip("\n"))
l = [int(s) for s in sys.stdin.readline().rstrip("\n").split()]
s = 1
if 0 in l:
    print(0)
else:
    for i in l:
        s *= i
        if s > 10**18:
            print(-1)
            break
    else:
        print(s)
### BUGGY CODE ###

a, b, k = map(int, input().split())

for i in range(a, b+1):
    if i < a+k or b-k < i:
        print(i)


### FIXED CODE ###

a, b, k = map(int, input().split())

for i in range(a, min(b+1, a+k)):
    print(i)
for i in range(max(b-k+1, a+k), b+1):
    print(i)
### BUGGY CODE ###

K = int(input())
D = int(input())
strK = str(K)
lenK = len(strK)
#dp[i][smaller][k]はi桁まで見たあまりkの物の数とする.ただしsmaller=0のときはまだK以下かわかってないとする. 
dp = [[[0]*D for i in range(2)] for _ in range(lenK + 1)]
dp[0][0][0] = 1
for i in range(lenK):
    for j in range(2):
        for k in range(D):
            if j == 0:
                for l in range(int(strK[i])+1):
                    if l != int(strK[i]):    
                        if k + l < D:
                            dp[i+1][1][k+l] += dp[i][0][k]
                        else:
                            dp[i+1][1][(k+l)%D] += dp[i][0][k]
                    else:
                        if k+l < D:
                            dp[i+1][0][k+l] += dp[i][0][k]
                        else:
                            dp[i+1][0][(k+l)%D] += dp[i][0][k]
            else:
                for l in range(10):
                    if k+l < D:
                        dp[i+1][1][k+l] += dp[i][1][k]
                    else:
                        dp[i+1][1][(k+l)%D] += dp[i][1][k]
print((dp[lenK][0][0] + dp[lenK][1][0] - 1)%1000000007)

### FIXED CODE ###

K = input()
D = int(input())
lenK = len(K)
mod = 10**9+7
#dp[i][smaller][k]はi桁まで見たあまりkの物の数とする.ただしsmaller=0のときはまだK以下かわかってないとする. 
dp = [[[0]*D for i in range(2)] for _ in range(lenK + 1)]
dp[0][0][0] = 1
for i,c in enumerate(K):
    for less in range(2):
        lim = 9 if less else int(c)
        for r in range(D):
            for d in range(lim+1):
                dp[i+1][less or d < lim][(r+d)%D] += dp[i][less][r]
                dp[i+1][less or d < lim][(r+d)%D] %= mod
print((dp[-1][0][0] + dp[-1][1][0] - 1)%mod)