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

N = int(input())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7

ans = 0
for i in range(N):
  for j in range(i+1, N):
    ans += A[i]^A[j]
    
print(ans%MOD)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
MOD = 10**9+ 7

ans = 0
two = 1
for i in range(61):
  n = len([ a for a in A if (a >> i) & 1 ])
  ans += (n * (N - n) * two % MOD)
  two *= 2 
print(ans%MOD)
### BUGGY CODE ###

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

for i in range(d):
    t = a.index(max(a))
    a[t] = a[t]//2
    if max(a) == 0:
        break
print(sum(a))

### FIXED CODE ###

import heapq
n, d = map(int, input().split())
a = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(a)

for _ in range(d):
    t = heapq.heappop(a)
    heapq.heappush(a, (-1)*(-t//2))

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

#abc045_b
import sys

a=raw_input()
b=raw_input()
c=raw_input()

ch=a[0]

while True:
 if ch=='a':
  a=a[1:]
  if len(a)==0:
   print 'A'
   sys.exit()
  ch=a[0]
 elif ch=='b':
  b=b[1:]
  if len(b)==0:
   print 'B'
   sys.exit()
  ch=b[0]
 elif ch=='c':
  c=c[1:]
  if len(c)==0:
   print 'C'
   sys.exit()
  ch=c[0]
 

### FIXED CODE ###

#ABC045A

a=int(raw_input())
b=int(raw_input())
h=int(raw_input())
print (a+b)*h/2
### BUGGY CODE ###

n,k,q=map(int,input().split())
a=[int(input()) for _ in range(q)]
p=[k]*n

for i in range(q):
  seikai=a[i]-1
  for j in range(n):
    p[j]-=1
  p[seikai]+=1

for j in range(n):
  if p[j]>0:
    print('Yes')
  else:
    print('No')

### FIXED CODE ###

n,k,q=map(int,input().split())
a=[int(input()) for _ in range(q)]
p=[k-q]*n

for i in range(q):
  p[a[i]-1]+=1

for j in range(n):
  if p[j]>0:
    print('Yes')
  else:
    print('No')
### BUGGY CODE ###

import numpy as np
n = int(input())
an = np.array(list(map(int, input().split())))
q = int(input())
bici=[[] for i in range(q)]
for i in range(q):
    bici[i] = list(map(int, input().split()))
    an = np.where(an == bici[i][0],bici[i][1],an)
    Ans = np.sum(an)
    print(Ans)

### FIXED CODE ###

n = int(input())
Ans = 0
num = [0] * 100000
an = list(map(int, input().split()))
for i in range(n):
    num[an[i]-1] += 1
    Ans += an[i]
q = int(input())
for i in range(q):
    bici = list(map(int, input().split()))
    Ans += num[bici[0]-1]*(bici[1]-bici[0])
    num[bici[1]-1] += num[bici[0]-1]
    num[bici[0]-1] = 0
    print(Ans)
### BUGGY CODE ###

import bisect

N = int(input())
L = sorted(map(int, input().split(' ')))

ans = 0
for i in range(len(L)):
    for j in range(i + 1, len(L)):
        a = L[i]
        b = L[j]
        ans += bisect.bisect_right(L[j + 1:], a + b - 1)

print(ans)


### FIXED CODE ###

import bisect

N = int(input())
L = sorted(map(int, input().split(' ')))

ans = 0
for i in range(len(L)):
    for j in range(i + 1, len(L)):
        a = L[i]
        b = L[j]
        ans += max(0, bisect.bisect_right(L, a + b - 1) - (j + 1))

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

N, M, Q = map(int, input().split())
L, R = [], []
X = [[0]*N for _ in range(N)]
for i in range(M):
    l, r = map(int, input().split())
    L.append(l-1)
    R.append(r-1)
    X[l-1][r-1] += 1
C =[[0]*(N+1) for _ in range(N)]
for i in range(N):
    for j in range(N):
        C[i][j+1] = C[i][j] + X[i][j]

for i in range(Q):
    p, q = map(int, input().split())
    ans = 0
    for j in range(p-1, q):
        ans += C[j][q] - C[j][p-1]
    print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

N, M, Q = map(int, input().split())
L, R = [], []
X = [[0]*N for _ in range(N)]
for i in range(M):
    l, r = map(int, input().split())
    L.append(l-1)
    R.append(r-1)
    X[l-1][r-1] += 1
C =[[0]*(N+1) for _ in range(N)]
for i in range(N):
    for j in range(N):
        C[i][j+1] = C[i][j] + X[i][j]

for i in range(Q):
    p, q = map(int, input().split())
    ans = 0
    for j in range(p-1, q):
        ans += C[j][q] - C[j][p-1]
    print(ans)
### BUGGY CODE ###

from collections import defaultdict
import numpy as np


def trial_division(n):
    factor = defaultdict(int)
    tmp = int(np.sqrt(n)) + 1
    for num in range(2, tmp):
        while n % num == 0:
            n //= num
            factor[num] += 1
    factor[n] += 1
    return factor


def powmod(x, y, mod):
    if y == 0:
        return 1
    return (((powmod(x, y >> 1, mod) ** 2) % mod) * x ** (y & 1)) % mod


n = int(input())
a = np.array(list(map(int, input().split())))
mod = 10**9 + 7
numbers = defaultdict(int)
for a_i in a:
    for i, v in trial_division(a_i).items():
        numbers[i] = max(v, numbers[i])

l = 1
for i, v in numbers.items():
    l *= i ** v
    l %= mod

r = powmod(a, mod-2, mod)
ans = 0
for i in r:
    ans += l * i
    ans %= mod
print(int(ans))




### FIXED CODE ###

from collections import defaultdict
from functools import lru_cache
import math


def trial_division(n):
    factor = defaultdict(int)
    tmp = int(math.sqrt(n)) + 1
    for num in range(2, tmp):
        while n % num == 0:
            n //= num
            factor[num] += 1
    factor[n] += 1
    return factor


@lru_cache(maxsize=None)
def powmod(x, y, mod):
    if y == 0:
        return 1
    return (((powmod(x, y >> 1, mod) ** 2) % mod) * x ** (y & 1)) % mod


n = int(input())
a = list(map(int, input().split()))
mod = 10**9 + 7
numbers = defaultdict(int)
for a_i in a:
    for i, v in trial_division(a_i).items():
        numbers[i] = max(v, numbers[i])

l = 1
for i, v in numbers.items():
    l *= powmod(i, v, mod)
    l %= mod


ans = 0
for i in a:
    r = powmod(i, mod-2, mod)
    ans += l * r
    ans %= mod
print(int(ans))
### BUGGY CODE ###

input_num=input().split(" ")
input_str=list(input())
anslen=[]
for i in range(int(input_num[1])):
  divpoint=input().split(" ")
  k=''.join(input_str[int(divpoint[0])-1:int(divpoint[1])])
  anslen.append(k.count("AC"))
for i in range(int(input_num[1])):
  print(anslen[i])


### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
t=[0]*(N+1)
for i in range(N):
  t[i+1]=t[i]+(1 if S[i:i+2]=="AC" else 0)
for i in range(Q):
  start,end=map(int,input().split())
  print(t[end-1]-t[start-1])
### BUGGY CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))

INF = 10**9
dp = [INF] * N
dp[0] = 0
dp[1] = abs(h[1] - h[0])

for i in range(2, N):
  for j in range(1, K + 1):
    if i - j >= 0:
      dp[i] = min(dp[i], dp[i - j] + abs(h[i] - h[i - j]))
print(dp[N - 1])


### FIXED CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))

dp = [0] * N
for i, hi in enumerate(h):
  if i > 0:
    x = max(0, i - K)
    dp[i] = min([dpj + abs(hi - hj) for hj, dpj in zip(h[x:i], dp[x:i])])
print(dp[N - 1])
### BUGGY CODE ###

N=int(input())
A = list(map(int,input().split()))
Q=int(input())
B = [0]*Q
C = [0]*Q
for i in range(Q):
    B[i],C[i]=map(int,input().split())
ls = []
lsans=[]
D = A
for j in range(Q):
    ans = 0
    #print(ls)
    ls.append([a for a,x in enumerate(A) if x == B[j]])
    #print(B[j])
    #print(B)
    #print([a for a,x in enumerate(A) if x == B[j]])
    for i in range(len(ls[j])):
        D[ls[j][i]] = C[j]
    for z in range(N):
        ans += D[z]
        D = A
    lsans.append(ans)
for i in range(len(lsans)):
    print (lsans[i])


### FIXED CODE ###

N=int(input())
A = list(map(int,input().split()))
Q=int(input())
B = [0]*Q
C = [0]*Q
for i in range(Q):
    B[i],C[i]=map(int,input().split())
#print(B,C)
#print(A)
#a = 0
#for i in range(N):
    #a += A[i]
#print(a)
ls = [0]*100000
for i in A:
    ls[i-1] += 1
#print(ls)
sumA = sum(A)
#print("sumA",sumA)
for j in range(Q):
    #print(B[j]-1)
    #print(ls)
    sumA += (C[j]-B[j])*ls[B[j]-1]
    #print("j","C[j]","B[j]","ls[B[j]]",j,C[j],B[j],ls[B[j]-1])
    ls[C[j]-1] += ls[B[j]-1]
    ls[B[j]-1] = 0
    print(sumA)
### BUGGY CODE ###

import sys
n,m = map(int,input().split())
a = [int(input()) for i in range(m)]
dp = [1]*2 + [0]*(n-1)
mod = 1000000007
 
for i in range(1,m):
  if a[i]==a[i-1]+1:
    print(0)
    sys.exit()
  
for i in range(n-1):
  if i+1 in a:
    dp[i+2] = dp[i]
    dp[i+1] = 0
  else:
    dp[i+2] = dp[i]+dp[i+1]
  if dp[i+2] >= mod:
    dp[i+2] -= mod

print(dp[-1]%mod)  


### FIXED CODE ###

import sys
input = sys.stdin.readline
n,m = map(int,input().split())
hole = [0]*(n+1)
for i in range(m):
  hole[int(input())] = 1

dp = [0]*(n+1)
dp[0] = 1
MOD = 10**9+7
   
for i in range(1,n+1):
  if hole[i]==1:
    dp[i] = 0
  else:
    dp[i] = dp[i-1]+dp[i-2]
    dp[i] %= MOD

print(dp[-1])
### BUGGY CODE ###

import numpy as np
N = int(input())
a_s = input().split()
for i in range(N):
    a_s[i] = int(a_s[i])
a_s = np.array(a_s)

a_unique = np.unique(a_s)
# a_counts = []
# for i,a in enumerate(a_unique):
#     a_counts.append(np.sum(a_s==a))
# a_counts = np.array(a_counts)

ans = 0
for i in range(len(a_unique)):
    val = np.sum(a_s==a_unique[i]) #a_counts[i]
    if (i>0):
        if (a_unique[i-1]+1==a_unique[i]):
            val += np.sum(a_s==a_unique[i-1]) #a_counts[i-1]
            
    if (i<len(a_unique)-1):
        if (a_unique[i+1]-1==a_unique[i]):
            val += np.sum(a_s==a_unique[i+1]) #a_counts[i+1]
    
    if val > ans:
        ans = val
        
#     if ans >= sum(a_counts[i:]):
#         break
        
print(ans)

### FIXED CODE ###

from collections import Counter

N = int(input())
a_s = input().split()
a_s = [int(a_s[i]) for i in range(N)]

c = Counter(a_s)
c = sorted(c.items(), key=lambda x:x[0])
a_unique, a_counts = zip(*c)

ans = 0
for i,a in enumerate(a_unique):
    val = a_counts[i]
    if (i>0):
        if (a_unique[i-1]+1==a):
            val += a_counts[i-1]
            
    if (i<len(a_unique)-1):
        if (a_unique[i+1]-1==a):
            val += a_counts[i+1]
    
    if val > ans:
        ans = val
        
print(ans)
### BUGGY CODE ###

s=input()
q=int(input())
r=1
for i in range(q):
  q2=input().split()
  if int(q2[0])==1:
    r*=-1
  else:
    if (r==1 and int(q2[1])==1) or (r==-1 and int(q2[1])==2):
        s=q2[2]+s
    else:
        s=s+q2[2]
print(s if r==1 else s[::-1])

 
        

### FIXED CODE ###

from collections import deque
d=deque()
d.append(input())
q=int(input())
r=1
for i in range(q):
  q2=input().split()
  if int(q2[0])==1:
    r*=-1
  else:
    if (r==1 and int(q2[1])==1) or (r==-1 and int(q2[1])==2):
        d.appendleft(q2[2])
    else:
        d.append(q2[2])

print("".join(d) if r==1 else "".join(d)[::-1])
### BUGGY CODE ###

import itertools as it
import numpy as np

def rain_volume(A, N):
    A_citer = it.cycle(A)
    X = np.array([0]*N)
    for i in range(N):
        if i%2 == 0:
            A_p = [next(A_citer) for i in range(N)]
            X += A_p
            next(A_citer)
        elif i%2 != 0:
            A_m = [-next(A_citer) for i in range(N)]
            X += A_m
            next(A_citer)
    return X

if __name__ == '__main__':
    N = int(input())
    A = np.array(list(map(int, input().split(' '))))

    #N = 10**4 - 1
    #A = [10**9]*N
    print(' '.join(map(str, rain_volume(A, N))))

### FIXED CODE ###

def rain_volume(A, N):
    X = [0]*N
    X[0] = sum(A)
    for i, a in enumerate(A):
        if i%2 != 0:
            X[0] -= 2*a
    for i in range(1, N):
        if i != 0:
            X[i] = 2*A[i-1] - X[i-1]
    return X

if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split(' ')))

    print(' '.join(map(str, rain_volume(A, N))))
### BUGGY CODE ###

def main():
    N,M=map( int, input().split())
    A=list( map( int, input().split()))
    for i in range(M):
        A[A.index(max(A))] = int(A[A.index(max(A))]/2)
    print(sum(A))

if __name__ == '__main__':
    main()

### FIXED CODE ###

import heapq
def main():
    N,M=map( int, input().split())
    A=list( map( int, input().split()))
    A = list(map(lambda x: x*(-1), A))
    heapq.heapify(A)
    for _ in range(M):
        u = heapq.heappop(A)
        heapq.heappush(A,int(u/2))
    print(-sum(A))


    

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

n=int(input())
p=list(map(int,input().split()))
cnt=0
list=[]

for i in range(n):
  list.append(p[i])
  if min(list)==p[i]:
    cnt+=1
    
print(cnt)

### FIXED CODE ###

n=int(input())
p=list(map(int,input().split()))
cnt=0
tiny=float('inf')

for i in range(n):
  if tiny>=p[i]:
    cnt+=1
    tiny=p[i]
  else:
    pass
    
print(cnt)
### BUGGY CODE ###

from statistics import mean, median,variance,stdev
import numpy as np
import sys
import math
import fractions
import itertools
import copy

def j(q):
    if q==1: print("Heisei")
    else:print("TBD")
    exit(0)


def ct(x,y):
    if (x>y):print("")
    elif (x<y): print("")
    else: print("")

def ip():
    return int(input())

def swap(s,pos):
    s[pos]-=1
    s[pos+1]+=1
    print(s)
    if pos == n-2: return s
    if s[pos+2] == 0: swap(s,pos+1)
    return s


n = ip()                              #入力整数1つ
#h,w= (int(i) for i in input().split())      #入力整数横2つ
#n,x,y = (int(i) for i in input().split())    #入力整数横3つ
#n,a,b,c= (int(i) for i in input().split())  #入力整数横4つ
a = [int(i) for i in input().split()]        #入力整数配列
#a = input()                                  #入力文字列
#a = input().split()                          #入力文字配列
#n = ip()                      #入力セット(整数改行あり)(1/2)
#a=[ip() for i in range(n)]    #入力セット(整数改行あり)(2/2)

#jの変数はしようできないので注意
#全足しにsum変数使用はsum関数使用できないので注意

for i in range(n):
    b = copy.copy(a)
    b.pop(i)
    d = 0
    for k in range(1,len(b)):
        d+=abs(b[k-1]-b[k])
    print(d+abs(b[0])+abs(b[len(b)-1]))

### FIXED CODE ###

import copy
import heapq
import math
import fractions

def j(n):
    if n:print("Yes")
    else:print("No")
    exit(0)
rem = 10 ** 9 + 7

"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def iprow():
    return [int(i) for i in input().split()]
def ips():
    return (int(i) for i in input().split())
def ipmultiplerow(n):
    a = []
    for i in range(n):
        a.append(ip())
    return a
def printmultiplerow(a):
    for i in a:
        print(i)
def printrow(a):
    for i in range(len(a)-1):
        print(a[i],end = " ")
    print(a[-1])

n = ip()
a = [0]
a.extend(iprow())
a.append(0)
sub = []
jsub = []
n+=2
for i in range(n-1):
    sub.append(abs(a[i+1]-a[i]))
for i in range(n-2):
    jsub.append(abs(a[i+2]-a[i]))
s = sum(sub)
s-=sub[0]
for i in range(n-2):
    s-=sub[i+1]
    print(s+jsub[i])
    s+=sub[i]
### BUGGY CODE ###

import sys,math,collections,itertools
input = sys.stdin.readline

N,M,K = list(map(int,input().split()))
fr = [[] for i in range(N+1)]
bl = [[] for i in range(N+1)] 
      
for _ in range(M):
    a,b = map(int,input().split())
    fr[a].append(b)
    fr[b].append(a)
for _ in range(K):
    c,d = map(int,input().split())
    bl[c].append(d)
    bl[d].append(c)

fl = [-1 for i in range(N+1)]
fl[0] = 0
fl[1] = 1
nxt = 1
dic = {}
while nxt != 0:
    q = collections.deque([nxt])
    
    fl[nxt]=nxt
    cnt = 0
    while q:
        now = q.popleft()
        for f in fr[now]:
            if fl[f] == -1:
                fl[f] = nxt
                cnt +=1
                q.append(f)
    dic[nxt] = cnt
    if -1 in set(fl):
        nxt = fl.index(-1)
    else:
        nxt = 0

mbf = collections.deque()
for i in range(1,N+1):
    ff = 0
    for j in bl[i]:
        if fl[j] == fl[i]:
            ff -= 1
    
    ff += dic[fl[i]]-len(fr[i])
    mbf.append(ff)
print(*mbf)


### FIXED CODE ###

import sys,collections
input = sys.stdin.readline

def main():
    N,M,K = list(map(int,input().split()))
    fr = [[] for i in range(N+1)]
    bl = [[] for i in range(N+1)]

          
    for _ in range(M):
        a,b = map(int,input().split())
        fr[a].append(b)
        fr[b].append(a)
    for _ in range(K):
        c,d = map(int,input().split())
        bl[c].append(d)
        bl[d].append(c)

    fl = [-1 for i in range(N+1)]
    fl[0] = 0
    fl[1] = 1
    nxt = 1
    dic = {}
    s = set(range(1,N+1))
    while nxt != 0:
        q = collections.deque([nxt])
        
        fl[nxt]=nxt
        cnt = 0
        while q:
            now = q.popleft()
            s.discard(now)
            for f in fr[now]:
                if fl[f] == -1:
                    fl[f] = nxt
                    cnt +=1
                    q.append(f)
        dic[nxt] = cnt
        #try:
            #nxt = fl.index(-1)
        #except:
            #nxt = 0
        if len(s) == 0:
            nxt = 0
        else:
            nxt = s.pop()


    mbf = collections.deque()
    for i in range(1,N+1):
        ff = 0
        for j in bl[i]:
            if fl[j] == fl[i]:
                ff -= 1
        
        ff += dic[fl[i]]-len(fr[i])
        mbf.append(ff)
    print(*mbf)

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

x, y, z, k = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
b = list(map(int, input().split(' ')))
c = list(map(int, input().split(' ')))
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
t = []
for i in range(x):
    for j in range(y):
        for l in range(z):
            if i * j * l < k:
                t.append(a[i]+b[j]+c[l])
            else:
                break
t.sort(reverse=True)
for i in range(k):
    print(t[i])

### FIXED CODE ###

x,y,z,K=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
ans=[]
for i in range(x):
  for j in range(y):
    for k in range(z):
      if (i+1)*(j+1)*(k+1)<=K:
        ans.append(a[i]+b[j]+c[k])
      else:
        break
ans.sort(reverse=True)
for i in range(K):
  print(ans[i])
### BUGGY CODE ###

N = int(input())
a_list = map(int, input().split())
b_list = [int(a % 2) for a in a_list]
i = 0
while not(1 in b_list):
    a_list = [int(a / 2) for a in a_list]
    b_list = [int(a % 2) for a in a_list]
    i += 1
print(i)


### FIXED CODE ###

N = int(input())
a_list = list(map(int, input().split()))
b_list = [int(a % 2) for a in a_list]
zero_list = [0 for a in a_list]
i = 0
while zero_list == b_list:
    a_list = [int(a / 2) for a in a_list]
    b_list = [int(a % 2) for a in a_list]
    i += 1
print(i)
### BUGGY CODE ###

import itertools
n=int(input())
ss=input()
l=["R","G","B"]
ans=0
for v in itertools.permutations(l, 3):
    for i in range(n-2):
        if ss[i]==v[0]:
            for k in range(i+1,n-1):
                if ss[k]==v[1]:
                    for p in range(k+1,n):
                        if (k-i!=p-k) and ss[p]==v[2]:
                            ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
s=input()
ans=s.count("R")*s.count("G")*s.count("B")  # 第１条件の全事象
for i in range(n-2):
    for j in range(i+1,n-1):
        k=j+j-i
        if k<n and s[k]!=s[i] and s[k]!=s[j] and s[i]!=s[j]: # 第1条件 かつ not第２条件
            ans-=1
print(ans)
### BUGGY CODE ###

n = int(input())
x = round(n**0.5)

while n%x!=0:
    x += 1
y = n//x
print(len(str(max(x,y))))

### FIXED CODE ###

n = int(input())
a = round(n**0.5)
while n % a != 0:
  a -= 1
b = n//a
print(len(str(max(a,b))))
### BUGGY CODE ###

# 入力
N,K = list(map(int, input().split()))
A_list = list(map(int, input().split()))

for i in range(N-K):
    score1, score2 = (1,1)
    for j in range(K):
        score1 *= A_list[i+j]
        score2 *= A_list[i+j+1]
    if((score2 - score1) > 0):
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

# 入力
N,K = list(map(int, input().split()))
A_list = list(map(int, input().split()))

for i in range(N-K):
    if((A_list[i+K] - A_list[i]) > 0):
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
INF =  float("inf")
import bisect
import statistics
mod = 10**9+7

K = input()
D = int(input())

n = len(K)

dp = [[[0 for k in range(D)] for j in range(2)] for i in range(n+1)]
dp[0][0][0] = 1

for i in range(1,n+1):
    for k in range(D):
        for j in range(10):
            dp[i][1][k] += dp[i-1][1][(k-j) % D]
        for j in range(int(K[i-1])):
            dp[i][1][k] += dp[i-1][0][(k-j) % D]
        dp[i][0][k] += dp[i-1][0][(k-int(K[i-1])) % D]

print((dp[n][1][0] + dp[n][0][0] -1) % mod)


### FIXED CODE ###

from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
INF =  float("inf")
import bisect
import statistics
mod = 10**9+7

K = input()
D = int(input())

n = len(K)

dp = [[[0 for k in range(D)] for j in range(2)] for i in range(n+1)]
dp[0][0][0] = 1

for i in range(1,n+1):
    for k in range(D):
        for j in range(10):
            dp[i][1][k] = (dp[i][1][k] + dp[i-1][1][(k-j) % D]) % mod
        for j in range(int(K[i-1])):
            dp[i][1][k] = (dp[i][1][k] + dp[i-1][0][(k-j) % D]) % mod
        dp[i][0][k] = (dp[i][0][k] + dp[i-1][0][(k-int(K[i-1])) % D]) % mod

print((dp[n][1][0] + dp[n][0][0] -1) % mod)
### BUGGY CODE ###

n=int(input())
 
a=list(map(int,input().split()))
num=0
for i in range(n):
  for j in range(n-1,i,-1):
    num=num+a[i]*a[j]
else:
  print(num % 1000000007)

### FIXED CODE ###

n=int(input())

l = 1000000007
a=list(map(int,input().split()))
s = sum(a)
num = 0
for i in range(n):
  s = s- a[i]
  num =num+a[i]*s
else:
  print(num%l)
### BUGGY CODE ###

H,W = list(map(int,input().split()))
temp = [["#" for i in range(W+2)]]
A = temp + [["#"] + (list(str(input()))) + ["#"] for i in range(H)] + temp
 
black = []
 
cnt = 0
 
for i in range(1,H+1):
    for j in range(1,W+1):
        if A[i][j] == "#":
            black.append([i,j])
 
length = len(black)
            
while (length < H*W):
    gray = []
    for l in black:
            c1 = [l[0],l[1]-1]
            if A[c1[0]][c1[1]] == ".":
                gray.append(c1)
                A[c1[0]][c1[1]] = "#"
            c2 = [l[0],l[1]+1]
            if  A[c2[0]][c2[1]] == ".":
                gray.append(c2)
                A[c2[0]][c2[1]] = "#"
            c3 = [l[0]-1,l[1]]
            if  A[c3[0]][c3[1]] == ".":
                gray.append(c3)
                A[c3[0]][c3[1]] = "#"
            c4 = [l[0]+1,l[1]]
            if  A[c4[0]][c4[1]] == ".":
                gray.append(c4)
                A[c4[0]][c4[1]] = "#"
    
    black = [l for l in gray]
    
    cnt += 1
    length += len(black)
    
print(cnt)

### FIXED CODE ###

H,W = list(map(int,input().split()))
A = [list(str(input())) for i in range(H)]
 
black = []
 
cnt = 0
 
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            black.append([i,j])
 
length = len(black)
            
while (length < H*W):
    gray = []
    for l in black:
        if l[1] != 0:
            c1 = (l[0],l[1]-1)
            if A[c1[0]][c1[1]] == ".":
                gray.append(c1)
                A[c1[0]][c1[1]] = "#"
        if l[1] != W-1:
            c2 = (l[0],l[1]+1)
            if  A[c2[0]][c2[1]] == ".":
                gray.append(c2)
                A[c2[0]][c2[1]] = "#"
        if l[0] != 0:
            c3 = (l[0]-1,l[1])
            if  A[c3[0]][c3[1]] == ".":
                gray.append(c3)
                A[c3[0]][c3[1]] = "#"
        if l[0] != H-1:
            c4 = (l[0]+1,l[1])
            if  A[c4[0]][c4[1]] == ".":
                gray.append(c4)
                A[c4[0]][c4[1]] = "#"
    
    gray = list(set(gray))
    black = [l for l in gray]
    
    cnt += 1
    length += len(black)
    
print(cnt)