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

n=int(input())
da=list(map(int,input().split()))
ans=0
da=sorted(da)
for i in range(1,n-1):
    for j in range(i):
        ok,ng=0,0
        ok+=i
        ng+=n
        while ng-ok!=1:
            mi=(ok+ng)//2
            if da[mi]<da[i]+da[j]:
                ok=0
                ok+=mi
            else:
                ng=0
                ng+=mi
        ans+=ok-i
print(ans)

### FIXED CODE ###

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

def bina(x,ok,ng):
    global da
    while ng-ok!=1:
        mi=(ok+ng)//2
        if da[mi]<x:
            ok=0
            ok+=mi
        else:
            ng=0
            ng+=mi
    return ok


ans=0
da=sorted(da)
for i in range(1,n-1):
    for j in range(i):
        ans+=bina(da[i]+da[j],i,n)-i
print(ans)
### BUGGY CODE ###

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

bc = []
for i in range(m):
    temp = list(map(int, input().split()))
    bc.append(temp)

bc_sorted = sorted(bc, key = lambda x:x[1], reverse = True)
temp = 0
d=[]
for i in range(m):
    for j in range(bc_sorted[i][0]):
        d.append(bc_sorted[i][1])
        if len(d) ==n:
            break

for i in range(min(n,len(d))):
    a_sort[i] = max(a_sort[i],d[i])

print(int(sum(a_sort)))

### FIXED CODE ###

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

bc = []
for i in range(m):
    temp = list(map(int, input().split()))
    bc.append(temp)

bc_sorted = sorted(bc, key = lambda x:x[1], reverse = True)
temp = 0

for i in range(m):
    for j in range(temp,min(n,temp+bc_sorted[i][0])):
        if a_sort[j] < bc_sorted[i][1]:
            a_sort[j] = bc_sorted[i][1]
            temp += 1
        else:
            break

print(int(sum(a_sort)))
### BUGGY CODE ###

N = int(input())
s = [int(input()) for _ in range(N)]
ans = 0
for i in range(2**N):
    correct = []
    su = 0
    for j in range(N):
        if ((i >> j) & 1):
            correct.append(j)
    for k in correct:
      su += s[k]
    if su % 10 == 0:
      su = 0
    ans = max(ans,su)
print(ans)
            

### FIXED CODE ###

N = int(input())
s = [int(input()) for _ in range(N)]
s.sort()
ans = sum(s)

if ans % 10 != 0:
  print(ans)
else:
  for i in range(N):
    if s[i] % 10 != 0:
      print(ans - s[i])
      exit()
  print(0)
### BUGGY CODE ###

n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
b = [0,0,0]
def judge(n):
    if  n!= 1 and all(n%i != 0 for i in range(2,round(n**(1/2) +1))):
        return True
    else:
        return False
for i in range(3,10**5):
    if judge(i) and judge((i+1)/2):
        b.append(1)
    else:
        b.append(0)
for i in range(n):
    print(sum(b[a[i][0]:a[i][1]+1]))

### FIXED CODE ###

n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
b = [0,0,0]
def judge(n):
    if  n!= 1 and all(n%i != 0 for i in range(2,round(n**(1/2) +1))):
        return True
    else:
        return False
for i in range(3,10**5):
    if judge(i) and judge((i+1)/2):
        b.append(1)
    else:
        b.append(0)
cnt = [0]*(10**5)
for i in range(1,10**5):
    cnt[i] = cnt[i-1] + b[i]
for i in range(n):
    ans = cnt[a[i][1]] - cnt[a[i][0]-1]
    print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

dict = {}
for i in range(1, 10**5+1):
    dict[i] = 0
for i in a:
    dict[i] += 1

for i in range(q):
    b, c = map(int, input().split())
    dict[c] += dict[b]
    dict[b] = 0
    ans = 0
    for i, j in dict.items():
        ans += i*j
    print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

dict = {}

for i in range(1, 10**5+1):
    dict[i] = 0
for i in a:
    dict[i] += 1

s = sum(a)

for i in range(q):
    b, c = map(int, input().split())
    s += (c-b)*dict[b]
    dict[c] += dict[b]
    dict[b] = 0
    print(s)
### BUGGY CODE ###

import sys
from itertools import groupby
from copy import deepcopy

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def do_drop(H, W, G):
    for j in range(W):
        for i in range(H - 1):
            for k in range(H - 1, i, -1):
                if G[k][j] == 0 and G[k - 1][j] != 0:
                    G[k][j], G[k - 1][j] = G[k - 1][j], G[k][j]


def main():
    H, W, K = map(int, readline().split())
    G_base = [list(map(int, readline().strip())) for _ in range(H)]

    ans = 0
    for i in range(H):
        for j in range(W):
            G = deepcopy(G_base)
            G[i][j] = 0
            do_drop(H, W, G)

            power = 1
            score = 0
            while True:
                finished = True
                total = 0
                for row in G:
                    idx = 0
                    for k, g in groupby(row):
                        l = len(list(g))
                        if k > 0 and l >= K:
                            row[idx : idx + l] = [0] * l
                            total += k * l
                            finished = False
                        idx += l

                if finished:
                    break

                score += power * total
                power *= 2
                do_drop(H, W, G)

            if ans < score:
                ans = score

    print(ans)
    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from copy import deepcopy

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def drop(H, G):
    G = [[n for n in col if n != -1] for col in zip(*G)]
    G = [[-1] * (H - len(col)) + col for col in G]
    G = [list(row) for row in zip(*G)]
    return G


def main():
    H, W, K = map(int, readline().split())
    G_init = [list(map(int, list(readline().strip()))) for _ in range(H)]

    ans = 0
    for i in range(H):
        for j in range(W):
            G = deepcopy(G_init)
            G[i][j] = -1
            G = drop(H, G)

            current_ans = 0
            step = 0
            while True:
                score = 0
                for row in G:
                    seq = [[row[0], 1]]
                    for n in row[1:]:
                        if n == seq[-1][0]:
                            seq[-1][1] += 1
                        else:
                            seq.append([n, 1])
                    idx = 0
                    for n, c in seq:
                        if n != -1 and c >= K:
                            score += n * c
                            row[idx : idx + c] = [-1] * c
                        idx += c

                if score == 0:
                    break

                current_ans += score * pow(2, step)
                step += 1
                G = drop(H, G)

            if current_ans > ans:
                ans = current_ans

    print(ans)
    return


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

N = int(input())
SS = []
G1,G2,G3,G4 = [],[],[],[]
for _ in range(N):
    S = input()
    MIN = 0
    cnt = 0
    for s in list(S):
        if s == '(':
            cnt += 1
        else:
            cnt -= 1
        MIN = min(MIN,cnt)
    if MIN == 0 and cnt >= 0:
        G1.append([MIN,cnt])
    if MIN < 0 and cnt >= 0:
        G2.append([MIN,cnt])
    if MIN == cnt and cnt < 0:
        G3.append([MIN,cnt])
    if MIN < cnt and cnt < 0:
        G4.append([MIN,cnt])

cnt = 0
cnt += sum(L[0] for L in G1)
for L in G1:
    cnt += L[1]
G2.sort(reverse=True)
for L in G2:
    if cnt + L[0] < 0:
        print('No')
        exit()
    else:
        cnt += L[1]
G4.sort()
for L in G4:
    if cnt + L[0] < 0:
        print('No')
        exit()
    else:
        cnt += L[1]

cnt += sum(L[1] for L in G3)

if cnt == 0:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

N = int(input())
G2,G4 = [],[]
cnt2 = 0
cnt3 = 0
for _ in range(N):
    S = input()
    MIN = 0
    cnt = 0
    for s in list(S):
        if s == '(':
            cnt += 1
        else:
            cnt -= 1
        MIN = min(MIN,cnt)
    if MIN == 0 and cnt >= 0:
        cnt2 += cnt
    if MIN < 0 and cnt >= 0:
        G2.append([MIN,cnt])
    if MIN == cnt and cnt < 0:
        cnt3 += cnt
    if MIN < cnt and cnt < 0:
        G4.append([MIN,cnt])


G2.sort(reverse=True)
for L in G2:
    if cnt2 + L[0] < 0:
        print('No')
        exit()
    else:
        cnt2 += L[1]
for L in G4:
    if cnt2 + L[0] < 0:
        print('No')
        exit()
    else:
        cnt2 += L[1]

cnt2 += cnt3

if cnt2 == 0:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

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

cnt = 0
for i,v in enumerate(p):
    if i == 0:
        cnt += 1
        continue
    if min(p[:i]) > v:
        cnt += 1
print(cnt)

### FIXED CODE ###

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

cnt = 0
for i,v in enumerate(p):
    if i == 0:
        cnt += 1
        min_ = v
        continue
    if min_ > v:
        min_ = v
        cnt += 1
print(cnt)
### BUGGY CODE ###

import sys

res=10**9+7
def permutation(n):
  x=1
  for i in range(n):x=(x*(i+1))
  return(x)
n,m=map(int,input().split())
n%=res
m%=res
if(n>m+1 or m>n+1):
  print(0)
elif(n==m):
  p=permutation(n)
  print((2*p*p)%res)
else:
  ma=max(n,m)
  p=permutation(ma)
  p2=p//ma
  print((p*p2)%res)


### FIXED CODE ###

import sys

res=10**9+7
def permutation(n):
  x=1
  for i in range(n):x=(x*(i+1))%res
  return(x%res)
n,m=map(int,input().split())
n%=res
m%=res
if(n>m+1 or m>n+1):
  print(0)
elif(n==m):
  p=permutation(n)
  print((2*p*p)%res)
else:
  mi=min(n,m)
  p=permutation(mi)
  p2=p*max(n,m)
  print((p*p2)%res)
### BUGGY CODE ###

MOD = 10**9 + 7
n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))

dp = [[0] * (m+1) for _ in range(n+1)]
cs = [[0] * (m+1) for _ in range(n+1)]

for i in range(1, n+1):
    for j in range(1, m+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = 1 + cs[i-1][j-1]
            dp[i][j] %= MOD

        cs[i][j] = cs[i-1][j] + cs[i][j-1] - cs[i-1][j-1] + dp[i][j]
        cs[i][j] %= MOD

print((cs[n][m] + 1) % MOD)


### FIXED CODE ###

MOD = 10**9 + 7
n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))

dp = [[0] * (m+1) for _ in range(n+1)]
cs = [[0] * (m+1) for _ in range(n+1)]

for i in range(1, n+1):
    for j in range(1, m+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = 1 + cs[i-1][j-1]
            dp[i][j] %= MOD

        cs[i][j] = cs[i-1][j] + cs[i][j-1] - cs[i-1][j-1] + dp[i][j]
        cs[i][j] %= MOD

print((cs[n][m] + 1) % MOD)
### BUGGY CODE ###

from collections import Counter
def get_par(x, par_lst):
  if x == par_lst[x]:
    return x
  ret = get_par(par_lst[x], par_lst)
  #par_lst[x] = ret
  return ret

def main():
  while True:
    n, m = map(int, input().split())
    if n == 0:
      break
    par_lst = [i for i in range(n)]
    counter = Counter()
    flag = False
    if m == 0:
      print("yes")
      continue
    for _ in range(m):
      u, v = map(int, input().split())
      u -= 1
      v -= 1
      counter[u] += 1
      counter[v] += 1
      pu, pv = get_par(u, par_lst), get_par(v, par_lst)
      if pu == pv:
        flag = True
      else:
        par_lst[pu] = pv
    
    if counter.most_common()[0][1] > 2:
      flag = True
    if flag:
      print("no")
    else:
      print("yes")
main()


### FIXED CODE ###

from collections import Counter
def get_par(x, par_lst):
  if x == par_lst[x]:
    return x
  ret = get_par(par_lst[x], par_lst)
  par_lst[x] = ret
  return ret

def main():
  while True:
    n, m = map(int, input().split())
    if n == 0:
      break
    par_lst = [i for i in range(n)]
    counter = [0] * n
    flag = False
    for _ in range(m):
      u, v = map(int, input().split())
      u -= 1
      v -= 1
      counter[u] += 1
      counter[v] += 1
      pu, pv = get_par(u, par_lst), get_par(v, par_lst)
      if pu == pv:
        flag = True
      else:
        par_lst[pu] = pv
    
    if max(counter) > 2:
      flag = True
    if flag:
      print("no")
    else:
      print("yes")
main()
### BUGGY CODE ###

n, m = map(int, input().split())
max_i = m // n
for i in range(max_i, 0, -1):
    if m % i == 0:
        print(i)
        break


### FIXED CODE ###

import math

n, m = map(int, input().split())
max_i = 1
for i in range(1, int(math.sqrt(m)) + 1):
    if m % i != 0:
        continue
    j = m // i
    if i * n <= m and i > max_i:
        max_i = i
    if j * n <= m and j > max_i:
        max_i = j
print(max_i)
### BUGGY CODE ###

N = int(input())
A=list(map(int, input().split()))
ans=1
for i in range(N):
    ans=ans*A[i]
if ans>10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

N = int(input())
A=list(map(int, input().split()))
ans=1
if 0 in A:
    ans=0
    print(ans)
else:
    for i in range(N):
        if ans>10**18:
            break
        ans=ans*A[i]
    if ans>10**18:
        print(-1)
    else:
        print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
*P, = map(int, input().split())
expec = tuple((P[i] * (P[i] + 1) / 2) / P[i] for i in range(N))
ans = 0
for i in range(N-K+1):
    a = expec[i:i+K]
    s = sum(a)
    ans = max(ans, s)
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
*P, = map(int, input().split())
cum = [0] * (N + 1)
for i in range(N):
    cum[i+1] = cum[i] + (P[i] * (P[i] + 1) / 2) / P[i]
ans = 0
for i in range(N-K+1):
    ans = max(ans, cum[i+K] - cum[i])
print(ans)
### BUGGY CODE ###

I = list(map(int,input().split()))
N = I[0]
M = I[1]
A = list(map(int,input().split()))

for i in range(M):
    num = A.index(max(A))
    A[num] = A[num] / 2

B = list(map(int,A))
ans = sum(B)
print(ans)

### FIXED CODE ###

import heapq
import math
I = list(map(int,input().split()))
N = I[0]
M = I[1]
A = list(map(lambda x:-x,map(int,input().split())))
heapq.heapify(A)
for i in range(M):
    num = heapq.heappop(A)
    num = math.ceil(num / 2)
    heapq.heappush(A,num)

print(-sum(A))
### BUGGY CODE ###

# coding: utf-8

from itertools import accumulate as accum
import sys
input = sys.stdin.readline

def f(N, s):
    MOD = int(1e9 + 7)
    dp = [[0] * N for _ in range(N)]
    for j in range(N):
        dp[0][j] = 1
    for i in range(1, N):
        csum = list(accum(dp[i - 1], lambda x, y: (x + y) % MOD))
        dpi = dp[i]
        csum_ = csum[N - i]
        i_ = i - 1
        for j in range(N - i):  # N-(i+1)+1 = N-i
            dpi[j] = csum[j] if s[i_] == ">" else (csum_ - csum[j] + MOD) % MOD
    return(dp[-1][0])

N = int(input()) # 2 <= N <= 30000
s = input().rstrip() # len(s) = N - 1
print(f(N, s))


### FIXED CODE ###

# coding: utf-8

import sys
input = sys.stdin.readline

def f2(N, s):
    MOD = int(1e9 + 7)
    dp = [1] * N
    for i in range(1, N):
        csum = list(dp)
        for j in range(1, N - i + 1):
            csum[j] += csum[j - 1]
        csum_ = csum[N - i]
        i_ = i - 1
        for j in range(N - i):  # N-(i+1)+1 = N-i
            dp[j] = csum[j] if s[i_] == ">" else (csum_ - csum[j] + MOD) % MOD
    return(dp[0])

N = int(input()) # 2 <= N <= 30000
s = input().rstrip() # len(s) = N - 1
print(f2(N, s))
### BUGGY CODE ###

n, m = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
a.sort()
bc = []
for _ in range(m):
    bc.append([int(i) for i in input().split()])
bc = sorted(bc, key=lambda x: x[1], reverse=True)
for i in range(m):
    for j in range(bc[i][0]):
        if a[j] < bc[i][1]:
            a[j] = bc[i][1]
    a.sort()
print(sum(a))

### FIXED CODE ###

n, m = map(int, input().split())
a = [int(i) for i in input().split()]
bc = []
for _ in range(m): bc.append([int(i) for i in input().split()])
a.sort()
bc.sort(key=lambda x:x[1])
bc = bc[::-1]
idx = 0
for b, c in bc:
    for bi in range(b):
        if idx + bi == n or a[idx+bi] >= c:
            idx = "e"
            break
        else: a[idx+bi] = c
    if idx == "e": break
    else: idx += b
print(sum(a))
### BUGGY CODE ###

# AtCoder
import itertools
s = input()
K = int(input())

substrings = set()
for left in range(len(s)):
    for right in range(1, len(s)+1):
        if not s[left:right]:
            continue

        substrings.add(s[left:right])
print(sorted(list(substrings))[K-1])


### FIXED CODE ###

# AtCoder
s = input()
K = int(input())


substrings = set()
for i in range(len(s)):
    for j in range(1, K+1):
        substrings.add(s[i:i+j])

print(sorted(list(substrings))[K-1])
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()

ans=[0]*n
for i in range(n-1):
    if s[i:i+2]=='AC':
        ans[i:i+2]=[1,2]

for i in range(q):
    l,r=map(int,input().split())
    cnt=0
    for j in range(l-1,r-1):
        if ans[j:j+2]==[1,2]:
            cnt+=1
    print(cnt)

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
ans=[0]*n+[0]
for i in range(n):
    if s[i:i+2]=='AC':
        ans[i+1]=ans[i]+1
    else:
        ans[i+1]=ans[i]
for i in range(q):
    l,r=map(int,input().split())
    print(ans[r-1]-ans[l-1])
### BUGGY CODE ###

from functools import reduce

n = int(input())
A = list(map(int, input().split()))
s = 0

def xor(a, b):
    return a ^ b
for i in range(n-1):
    for j in range(i+1, n):
        s += xor(A[i],A[j])%(10**9+7)
s = s % (10**9+7)
print(s)

### FIXED CODE ###

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

zero_each_dig = [0 for _ in range(60)]
one_each_dig = [0 for _ in range(60)]

for i in range(n):
     for j in range(60):
        if (A[i] >> j) & 1 == 1:
            one_each_dig[j] += 1
        else:
            zero_each_dig[j] += 1

Multi = []
for k in range(60):
    Multi.append(zero_each_dig[k] * one_each_dig[k] * (2**k) % (10**9 +7))

ans = sum(Multi) % (10**9 +7)
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
INF = float("inf")
from itertools import accumulate
import operator


def solve(N: int, A: "List[int]"):
    acc_sum = [0]+list(accumulate(A))
    acc_xor = [0]+list(accumulate(A, func=operator.xor))

    ans = 0
    for i in range(1, N+1):       # left
        left, right = i, N+1
        while right-left > 1:
            # print("while, ({},{})".format(left, right))
            mid = (right+left)//2
            s = acc_sum[mid]-acc_sum[i-1]
            x = acc_xor[mid] ^ acc_xor[i-1]
            if s >= x:
                right = mid
            else:
                left = mid
        # print("{}, ({}, {})".format(i, left, right))
        s = acc_sum[left]-acc_sum[i-1]
        x = acc_xor[left] ^ acc_xor[i-1]
        while s <= x and left <= N:  # いくつか見ていく
            s = acc_sum[left]-acc_sum[i-1]
            x = acc_xor[left] ^ acc_xor[i-1]
            if s == x:
                ans += 1
            left += 1

    # print(acc_sum)
    # print(acc_xor)
    print(ans)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
INF = float("inf")
from itertools import accumulate
import operator


def solve(N: int, A: "List[int]"):
    acc_sum = [0]+list(accumulate(A))
    acc_xor = [0]+list(accumulate(A, func=operator.xor))

    ans = 0
    for i in range(1, N+1):       # left
        left, right = i, N+1
        while right-left > 1:
            # print("while, ({},{})".format(left, right))
            mid = (right+left)//2
            s = acc_sum[mid]-acc_sum[i-1]
            x = acc_xor[mid] ^ acc_xor[i-1]
            if s > x:
                right = mid
            else:
                left = mid
        ans += left-i+1
        # print("{}, ({}, {})".format(i, left, right))
        # while left < N+1 and\
        #         acc_sum[left]-acc_sum[i-1] == acc_xor[left] ^ acc_xor[i-1]:
        #     ans += 1
        #     left += 1

        # s =
        # x =
        # while s <= x and left <= N:  # いくつか見ていく
        #     s = acc_sum[left]-acc_sum[i-1]
        #     x = acc_xor[left] ^ acc_xor[i-1]
        #     if s == x:
        #         ans += 1
        #     left += 1

    # print(acc_sum)
    # print(acc_xor)
    print(ans)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


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

import copy

def dfs(i, operations, rest_bs):
    if i == 0 and len(rest_bs) == 0:
        return operations

    for k, b in enumerate(rest_bs):
        j = k + 1
        if j <= i and j == b:
            copied_operations = copy.deepcopy(operations)
            copied_operations.append(j)
            res = dfs(i-1, copied_operations, rest_bs[:k] + rest_bs[k+1:])
            if res != -1:
                return res
    return -1


if __name__ == "__main__":
    N = int(input())
    bs = list(map(int, input().split()))

    res = dfs(N, [], bs)
    if res == -1:
        print(-1)
    else:
        for n in reversed(res):
            print(n)


### FIXED CODE ###

if __name__ == "__main__":
    N = int(input())
    bs = list(map(int, input().split()))

    operations = []
    for i in range(N):
        j_remove = -1
        for j in range(N-i):
            if bs[j] == j+1:
                j_remove = j
        if j_remove == -1:
            print("-1")
            exit()
        operations.append(bs.pop(j_remove))
    for n in reversed(operations):
        print(n)
### BUGGY CODE ###

MOD = 10**9 + 7
K = input()
D = int(input())
N = len(K)
dp0 = [[0] * D for _ in range(N+1)]
dp1 = [[0] * D for _ in range(N+1)]
dp0[0][0] = 1
for i, digit in enumerate(K, 1):
    digit = int(digit)
    for d in range(D):
        for k in range(10):
            dp1[i][(d + k) % D] += dp1[i-1][d]
            dp1[i][(d + k) % D] %= MOD
            if k < digit:
                dp1[i][(d + k) % D] += dp0[i-1][d]
                dp1[i][(d + k) % D] %= MOD
            elif k == digit:
                dp0[i][(d + k) % D] += dp0[i-1][d]
                dp0[i][(d + k) % D] %= MOD
print((dp0[N][0] + dp1[N][0] - 1) % MOD)

### FIXED CODE ###

MOD = 10**9 + 7
K = input()
D = int(input())
N = len(K)
dp0 = [[0] * D for _ in range(N+1)]
dp1 = [[0] * D for _ in range(N+1)]
dp0[0][0] = 1
for i, digit in enumerate(K, 1):
    digit = int(digit)
    for d in range(D):
        for k in range(10):
            dp1[i][(d + k) % D] += dp1[i-1][d]
            dp1[i][(d + k) % D] %= MOD
            if k < digit:
                dp1[i][(d + k) % D] += dp0[i-1][d]
                dp1[i][(d + k) % D] %= MOD
            elif k == digit:
                dp0[i][(d + k) % D] += dp0[i-1][d]
                dp0[i][(d + k) % D] %= MOD
print((dp0[N][0] + dp1[N][0] - 1) % MOD)
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
 
opt = [0]
for i in range(1,n):
    opt += [min([opt[-j] + abs(h[i-j] - h[i]) for j in range(1,min(i,k)+1)])]
print(opt[-1])

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
cost=[0]
for i in range(1, n):
  cost+=[min([cost[-j] + abs(a[i-j] - a[i]) for j in range(1,min(i,k)+1)])]
print(cost[-1])
### BUGGY CODE ###

N, K, Q = map(int, input().split())
A = [int(input()) for _ in range(Q)]
ans = ["Yes"] * N
ok = Q - K
for i in range(1, N + 1):
  sumA = A.count(i)
  if sumA <= ok:
    ans[i - 1] = "No"

for ANS in ans:
  print(ANS)

### FIXED CODE ###

from collections import Counter
N, K, Q = map(int, input().split())
A = [int(input()) for _ in range(Q)]
C = Counter(A)
ans = ["No"] * N
ok = Q - K
if ok < 0:
  ans = ["Yes"] * N
  for ANS in ans:
    print(ANS)
  exit()

c = [key - 1 for key,val in C.items() if val > ok]
for i in c:
  ans[i] = "Yes"
for ANS in ans:
  print(ANS)