Harryxun/stf_run huggingface dataset:
import copy
def dfs(x,y,z,grid,H,W):
    if(x-1>=0):
        if(grid[y][x-1]>z or grid[y][x-1]==0):
            grid[y][x-1]=z+1
            dfs(x-1,y,z+1,grid,H,W)
    if(x+1<W):
        if(grid[y][x+1]>z or grid[y][x+1]==0):
            grid[y][x+1]=z+1
            dfs(x+1,y,z+1,grid,H,W)
    if(y-1>=0):
        if(grid[y-1][x]>z or grid[y-1][x]==0):
            grid[y-1][x]=z+1
            dfs(x,y-1,z+1,grid,H,W)
    if(y+1<H):
        if(grid[y+1][x]>z or grid[y+1][x]==0):
            grid[y+1][x]=z+1
            dfs(x,y+1,z+1,grid,H,W)
    return 0


H,W=map(int,input().split())
grid=[]
tmp=[]
for i in range(H):
    S=str(input())
    tmp=[]
    for j in range(W):
        if(S[j]=="."):
            tmp.append(0)
        else:
            tmp.append(-1)
    grid.append(tmp)
ans=0
result=0
for i in range(W):
    for j in range(H):
        if(grid[j][i]==0):
            if(j-1>=0 and j+1<H and i-1>=0 and i+1<W):
                if(grid[j-1][i]+grid[j+1][i]+grid[j][i-1]+grod[i+1]<(-1)):
                        dataset=copy.deepcopy(grid)
                        dfs(i,j,1,dataset,H,W)
                        ans=max(dataset)
                        ans=max(ans)
                        result=max(result,ans)
            else:
                dataset=copy.deepcopy(grid)
                dfs(i,j,1,dataset,H,W)
                ans=max(dataset)
                ans=max(ans)
                result=max(result,ans)
print(result-1)

### FIXED CODE ###

import copy
from collections import deque

#反省bfsだと計算量が多くなってしまうパターンだった。bfsが正解。
def dfs(x,y,z,grid,H,W):
    if(x-1>=0):
        if(grid[y][x-1]>z or grid[y][x-1]==0):
            grid[y][x-1]=z+1
            dfs(x-1,y,z+1,grid,H,W)
    if(x+1<W):
        if(grid[y][x+1]>z or grid[y][x+1]==0):
            grid[y][x+1]=z+1
            dfs(x+1,y,z+1,grid,H,W)
    if(y-1>=0):
        if(grid[y-1][x]>z or grid[y-1][x]==0):
            grid[y-1][x]=z+1
            dfs(x,y-1,z+1,grid,H,W)
    if(y+1<H):
        if(grid[y+1][x]>z or grid[y+1][x]==0):
            grid[y+1][x]=z+1
            dfs(x,y+1,z+1,grid,H,W)
    return 0
    
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

def bfs(x,y,grid,H,W):
    dist=[[0 for _ in range(W)] for _ in range(H)]
    que=deque()
    que.append((y,x))
    dist[y][x]=1
    while(len(que)>0):
        y,x=que.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if(0 <= nx < W) and (0 <= ny < H) and grid[ny][nx]==0 and dist[ny][nx] == 0:
                que.append((ny,nx))
                dist[ny][nx]=dist[y][x]+1
    return( max([max(dist[i]) for i in range(H)]))
    
H,W=map(int,input().split())
grid=[]
tmp=[]
for i in range(H):
    S=str(input())
    tmp=[]
    for j in range(W):
        if(S[j]=="."):
            tmp.append(0)
        else:
            tmp.append(-1)
    grid.append(tmp)
ans=0
result=0
for i in range(W):
    for j in range(H):
        if(grid[j][i]==0):
                ans=bfs(i,j,grid,H,W)
                result=max(result,ans)
print(result-1)
import sys
sys.setrecursionlimit=10**7

def cur(n):
    for x in neighbor[n]:
        if x!=par[n]:
            par[x]=n
            descend[n]+=cur(x)
    return descend[n]


def cur2(i):
    for x in neighbor[i]:
        if x!=par[i]:
            ans[x]=ans[i]*(descend[x])*modinv(n-descend[x])%mod
            cur2(x)

def modinv(a,m=10**9+7):
    if a==0: return 1
    b=m
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return lastx % m

mod=10**9+7
n=int(input())
neighbor=[[]  for _ in range(n+1)]
descend=[1]*(n+1)
par=[0]*(n+1)

for _ in range(n-1):
    a,b=map(int,input().split())
    neighbor[a].append(b)
    neighbor[b].append(a)

cur(1)
ans=[1]*(n+1)
ans1=1
for i in range(1,n+1):
    ans1=ans1*i%mod
for x in range(1,n+1):
    ans1=ans1*modinv(descend[x])%mod
ans[1]=ans1
cur2(1)
for i in range(1,n+1):
    print(ans[i])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

def modinv(a,m=10**9+7):
    if a==0: return 1
    else:
        b=m
        (x, lastx) = (0, 1)
        (y, lasty) = (1, 0)
        while b != 0:
            q = a // b
            (a, b) = (b, a % b)
            (x, lastx) = (lastx - q * x, x)
            (y, lasty) = (lasty - q * y, y)
        return lastx % m

def cur(p):
    if neighbor[p]==[]: return
    for x in neighbor[p]:
        par[x]=p
        neighbor[x].remove(p)
        cur(x)
    descend[par[p]]+=descend[p]

def cur2(p):
    for x in neighbor[p]:
        ans[x]=ans[p]*descend[x]*modinv(n-descend[x])
        ans[x]%=mod
        cur2(x)

mod=10**9+7
n=int(input())
neighbor=[set()  for _ in range(n+2)]
descend=[1 for i in range(n+1)]
par=[0]+[0]*(n+1)

for _ in range(n-1):
    a,b=map(int,input().split())
    neighbor[a].add(b)
    neighbor[b].add(a)

cur(1)


ans=[1]*(n+1)
ans1=1
for i in range(1,n+1):
    ans1=ans1*i*modinv(descend[i])
    ans1%=mod
ans[1]=ans1

cur2(1)

for i in range(1,n+1):
    print(ans[i])
X,N = map(int,input().split())
A = list(map(int,input().split()))
for d in range(X+1):
  for i in [-1, +1]:
    B = X + d*i
    if A.count(B) == 0:
      print(B)
      exit(0)

### FIXED CODE ###

llist = list(map(int,input().split()))
print(llist.index(0)+1)
#ModSum
N = int(input())

print( int(N*(N-1)//2 )

#sum = ( int(N*(N-1)/2) )
#print(sum)


### FIXED CODE ###

#ModSum
N = int(input())

print( (N*(N-1))//2 )

#sum = ( int(N*(N-1)/2) )
#print(sum)
N,M,C = map(int,input().split())
B = list(map(int,input().split()))
ans = 0
for i in range(N):
  A = list(map(int,input().split()))
  tmp = 0
  for j in range(M):
    tmp += A[i]*B[i]
  if tmp + C > 0:
    ans += 1
print(ans)


### FIXED CODE ###

N,M,C = map(int,input().split())
B = list(map(int,input().split()))
ans = 0
for i in range(N):
  A = list(map(int,input().split()))
  tmp = 0
  for j in range(M):
    tmp += A[j]*B[j]
  if tmp + C > 0:
    ans += 1
print(ans)
N = int(input())
S = input()
cut = 0
for n in range(N+1):
    if S[n] == 'A' and S[n + 1] == 'B' and S[n + 2] == 'C':
        cut += 1

print(cut)

### FIXED CODE ###

N = int(input())
S = input()
cut = S.count('ABC')
print(cut)
n = int( raw_input() )
A = map( int , raw_input().split() )
q = int( raw_input() )
mi = map( int , raw_input().split() )

for i in range( len(A) + 1 ):
  def solve(i, m)
    if m == 0:
      return True
    if i >= n:
      return False
  res = solve( i+1 , m ) or solve( i+1 , m-A[i] )
  return res

for m in mi
  if solve( 0 , m ):
    print 'yes'
  else:
    print 'no'
   

### FIXED CODE ###

n = input()
A = map( int , raw_input().split() )
q = input()
mi = map( int , raw_input().split() )

def solve(i, m):
  if m == 0:
    return True
  elif i >= n or m > sum(A):
    return False

  res = solve( i+1 , m ) or solve( i+1 , m-A[i] )
  return res

for m in mi:
  if solve( 0 , m ): print "yes"
  else: print "no"
import sys
input = sys.stdin.readline

def inv(x):
    return pow(x, MOD-2, MOD)
    
def C(n, r):
    return fact[n]*inv(fact[r])*inv(fact[n-r])

N = int(input())

if N>3000:
    1/0
    
x = list(map(int, input().split()))
ans = 0
MOD = 10**9+7
fact = [1]

for i in range(1, N):
    fact.append(fact[-1]*i%MOD)
    
for i in range(N-1):
    for j in range(i+1, N):
        #print(i, j)
        
        #r = j-i+1
        add = 1
        
        if j==N-1:
            r = N-2-i+1
            add *= (x[j]-x[i])
            add %= MOD
            add *= C(N-1, r)
            add %= MOD
            add *= fact[r-1]
            add %= MOD
            add *= fact[N-1-r]
            add %= MOD
            #ans += (x[j]-x[i])*C(N-1, r)*fact[r-1]*fact[N-1-r]
            ans += add
            #print(C(N-1, r-1)*fact[N-1-r+1]*fact[r-2])
        else:
            r = j-i+1
            add *= (x[j]-x[i])
            add %= MOD
            add *= C(N-1, r)
            add %= MOD
            add *= fact[j-i-1]
            add %= MOD
            add *= fact[N-1-r]
            add %= MOD
            ans += add
            #ans += (x[j]-x[i])*C(N-1, r)*fact[j-i-1]*fact[N-1-r]
        #print(x[j]-x[i])
            #print(C(N-1, r)*fact[N-1-r]*fact[r-2])
        #ans += (x[j]-x[i])*C(N-1, r)*fact[N-1-r]
        #print('ans:', ans)
        ans %= MOD

#ans *= fact[N-1]
ans %= MOD

print(ans)

### FIXED CODE ###

N = int(input())
x = list(map(int, input().split()))
MOD = 10**9+7
D = x[-1]-x[0]
ans = 0
fact = [1]

for i in range(1, N):
    fact.append(fact[-1]*i%MOD)

inv_table = [-1]*N

for i in range(N):
    inv_table[i] = pow(i, MOD-2, MOD)
    
for i in range(N-1):
    d = D-(x[i]-x[0])
    ans += d*fact[N-1]*inv_table[i+1]
    ans %= MOD

print(ans)
a = sorted(list(map(int, input().split())))
if a[2]-a[1]>=1:
  print(a[2]*2-1)
elif a[2]-a[1]=0:
  print(a[2]*2)

### FIXED CODE ###

a = sorted(list(map(int, input().split())))
if a[1]-a[0] >= 1:
  print(a[1]*2-1)
else:
  print(a[1]*2)
from math import gcd
from math import sqrt
A, B = map(int, input().split())
if (A == 1 or B == 1):
    print(1)
    exit(0)
C = gcd(A, B)
ans = 0
for i in range(1, C + 1):
    if (C % i == 0):
        C //= i
        ans += 1
    if (i >= C): break
print(ans)


### FIXED CODE ###

from fractions import gcd
from math import sqrt


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


def main():
    A, B = map(int, input().split())
    C = gcd(A, B)
    if (C == 1):
        print(1)
        exit(0)
    arr = factorization(C)
    # print(arr)
    print(len(arr) + 1)


if __name__ == "__main__":
    main()
from bisect import *
from itertools import accumulate
n, m, k = map(int, input().split())
a = [0]+list(map(int, input().split()))
b = [0]+list(map(int, input().split()))
a = accumulate(a)
b = accumulate(b)
ans = 0
for i in range(n+1):
    ind = bisect_right(b, k-a[i])
    ans = max(ans, ind+i-1)

print(ans)


### FIXED CODE ###

from bisect import *
from itertools import accumulate
n, m, k = map(int, input().split())
a = [0]+list(map(int, input().split()))
b = [0]+list(map(int, input().split()))
a = list(accumulate(a))
b = list(accumulate(b))
ans = 0
for i in range(n+1):
    if a[i] > k:
        continue
    ind = bisect_right(b, k-a[i])
    ans = max(ans, ind+i-1)

print(ans)
import math
a,b,c = map(int,input().split())
if math.gcd(a,b) == 1:
    print('YES')
else:
    print('NO')

### FIXED CODE ###

import fractions
a,b,c = map(int,input().split())
if c%fractions.gcd(a,b) == 0:
    print('YES')
else:
    print('NO')
import sys
input = sys.stdin.readline
N = int(input())
XL = []
import numpy as np
for _ in range(N):
    XL.append([int(x) for x in input().split()])
XL = np.array(sorted(XL))
XL_max = []
XL_min = []
for i in XL:
    XL_max.append(i[0] + i[1])
    XL_min.append(i[0] - i[1])
A = [0] * N
for i in range(N):
    cnt = 0
    left = sorted(XL_max[:i])
    right = sorted(XL_min[i+1:])
    cnt += i - np.searchsorted(left, XL_min[i], side = "right") 
    cnt += np.searchsorted(right, XL_max[i], side = "left")
    A[i] = cnt
cnt = np.array(sorted(A, reverse=True), np.int64)
cnt = np.cumsum(cnt)
if cnt[-1] == 0:
    print(n)
else:
    print(N - (np.searchsorted(cnt, cnt[-1] // 2) + 1))



### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
XL = []
for _ in range(N):
    tmp = [int(x) for x in input().split()]
    XL.append(tmp)
LR = []
for i in XL:
    LR.append([i[0] - i[1], i[0] + i[1]])
LR.sort()
ans = N
last = LR[0][1]
for i in range(1, N):
    if last > LR[i][0]:
        if last > LR[i][1]:
            last = LR[i][1]
        ans -= 1
    else:
        last = LR[i][1]
print(ans)
impor sys
ans = 1
count = 1
while ans:
  ans = int(sys.stdin.readline())
  if ans:
    print "Case %d: %d"(count, ans)
    count += 1

### FIXED CODE ###

import sys
ans = 1
count = 1
while ans:
  ans = int(sys.stdin.readline())
  if ans:
    print "Case %d: %d"%(count, ans)
    count += 1
from math import gcd
from functools import reduce

def gcd_list(numbers):
    return reduce(gcd, numbers)

n = int(input())
a = [int(_) for _ in input().split()]
a.sort()
ir = [a[0]]
for i in range(1,n):
    ir.append(gcd(a[0], a[i]))
mi = ir.index(min(ir))
mr = []
for i in range(n):
    mr.append(gcd(a[mi], a[i]))
if ir.count(min(ir)) > mr.count(min(mr)):
    print(gcd_list(a[1::]))
elif ir.count(min(ir)) == mr.count(min(mr)):
    print(a[0])
elif ir.count(min(ir)) < mr.count(min(mr)):
    a.pop(mi)
    print(gcd_list(a))


### FIXED CODE ###

import math
def get_div_list(num):
    if num == 1:
        return [1]
    else:
        div_list = []
        div_list.append(1)
        div_list.append(num)
        for i in range(2, math.floor(math.sqrt(num))+ 1):
            if num % i == 0:
                div_list.append(i)
                div_list.append(num // i)
        list(set(div_list))
        div_list.sort(reverse = True)
        return div_list
n = int(input())
a = [int(_) for _ in input().split()]
d = sorted(list(set(get_div_list(a[0])+get_div_list(a[1]))))[::-1]
for i in range(len(d)):
    cnt = 0
    for j in range(n):
        if a[j]%d[i]==0:cnt+=1
    if cnt >= n-1:
        print(d[i])
        break
def gcd(a,b):
    if b > 0:
        c = a % b
        print(gcd(b,c))
    elif b == 0:
        print(a)

N, X = map(int,input().split())
x = list(input().split())
x = [abs(X-int(i)) for i in x]
for i in x:
    if i == x[0]:
        a = i
    else:
        a = gcd(a,i)
print(a)

### FIXED CODE ###

def gcd(a,b):
    if b > 0:
        c = a % b
        return(gcd(b,c))
    elif b == 0:
        return(a)

N, X = map(int,input().split())
x = list(input().split())
x = [abs(X-int(i)) for i in x]
for i in x:
    if i == x[0]:
        a = i
    else:
        a = gcd(a,i)
print(a)
lis = ["SUN","MON","TUE","WEN","THU","FRI","SAT"]
s = str(input())
print((7-lis.index(s))%7)

### FIXED CODE ###

lis = ["SUN","MON","TUE","WED","THU","FRI","SAT"]
s = str(input())
print((7-lis.index(s)))
a = int(1)
while True:
	b = int(raw_input())
	print('Case ' + str(a) + ': ' + str(b))
		a += 1
	if b != 0:
		continue
	else:
		break

### FIXED CODE ###

a = int(1)
b = int(1)
while True:
	b = int(raw_input())
	if b != 0:
		print('Case ' + str(a) + ': ' + str(b))
		a += 1
		continue
	else:
		break
N=int(input())
li=map(string,input().split())
dic={}
for k in li:
  dic[k]+=1
max_dic= max(dic)
print(max_dic)

### FIXED CODE ###

N = int(input())
D = {}
for _ in range(N):
    S = input()
    if S not in D: D[S]=0
    D[S]+=1

M = max(D.values())
for S in sorted(list(D)):
    if D[S]==M:
      print(S)
import fractions

n,X=map(int,input().split())
x=list(map(int,input().split()))
x.append(X)
x2=sorted(x)
a=x2[1]-x2[0]
if len(x2)<=2:
    print(a)
else:
    for i in range(1,n-1):
        b=x2[i+1]-x2[i]
        ans=fractions.gcd(a,b)
        a=ans
    print(ans)

### FIXED CODE ###

import fractions

n,X=map(int,input().split())
x=list(map(int,input().split()))
ans=abs(x[0]-X)
for i in range(1,n):
    b=abs(x[i]-X)
    ans=fractions.gcd(ans,b)
print(ans)
N = int(input())
array=[int(n) for n in input().split()]

lst=0
for i in range(N+1):
    left_array=array[:N+i]
    print(left_array)
    l = sorted(left_array)[-N:]
    print('l:',l)
    right_array=array[N+i:]
    print(right_array)
    r = sorted(right_array)[:N]
    print('r:',r)
    ans = sum(l)-sum(r)
    print(ans)
    if ans > lst:
        lst= ans
print(lst)

### FIXED CODE ###

N = int(input())
array = [int(n) for n in input().split()]
import copy
import heapq
lst = [None for i in range(N + 1)]
left_lst = copy.deepcopy(lst)
right_lst = copy.deepcopy(lst)
left_array = array[:N]
right_array= [-n for n in array[-N:]]
l_sum = sum(left_array)
r_sum = sum(right_array)
heapq.heapify(left_array)
heapq.heapify(right_array)
left_lst[0] = l_sum
right_lst[0] = r_sum

for k in range(N, 2 * N):
    new_a, new_b = array[k], array[-k - 1]*-1
    heapq.heappush(left_array,new_a)
    heapq.heappush(right_array,new_b)
    old_a = heapq.heappop(left_array)
    l_sum += (new_a - old_a)
    left_lst[k - N + 1] = l_sum
    old_b = heapq.heappop(right_array)
    r_sum += (new_b - old_b)
    right_lst[k - N + 1] = r_sum
lst = [ a + b for a, b in zip(left_lst, list(reversed(right_lst)))]
print(max(lst))
def gcd(a, b):
    if a == 0:
        return b
    return gcd(b%a, a)

def lcm(a,b):
    return a*b/gcd(a,b)

if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))
    l = int(1)
    for e in a:
        l = lcm(l,e)
    s = int(0)
    for e in a:
        s += l//e
    mod = int(1000000007)
    print(int(s % mod))


### FIXED CODE ###

def gcd(a, b):
    if a == 0:
        return b
    return gcd(b%a, a)

def lcm(a,b):
    return a*b//gcd(a,b)

if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))
    l = int(1)
    for e in a:
        l = lcm(l,e)
    s = int(0)
    for e in a:
        s += l//e
    mod = int(1000000007)
    print(int(s % mod))
n = input()
l = []
for i in range(int(n)):
	command = input()
	if command[0] == 'i':
		l.insert([(command[6:])])
	else:
		if command[7] == " ":
			if  command[6:] in l:
				l.remove(command[6:])
		else:
			if command[7] == 'L':
				l.pop()
			else:
				l.pop(0)
for i in l[:-1]:
	print(i, end=' ')
print(l[-1])

### FIXED CODE ###

from collections import deque
n = input()
d = deque()
for i in range(int(n)):
	command = input()
	if command[0] == 'i':
		d.appendleft(command[7:])
	else:
		if command[6] == " ":
			if  command[7:] in d:
				d.remove(command[7:])
		else:
			if command[6] == 'L':
				d.pop()
			else:
				d.popleft()
for _ in range(len(d)-1):
	print(d.popleft(), end=" ")
print(d.pop())
ny = input().split()
n = int(ny[0])
y = int(ny[1])

def solve(n,y):
    Y = y/1000
    p = int((Y - n) // 9)
    for v in range(p+1):
        if (Y - n - 9*v)%4 == 0:
            b = int((Y - n - 9*v)/4)
            c = int((Y - 10*v - 5*b))
            if c*b < 0:
                continue
            else:
                return str(v), str(b), str(c)


ans = solve(n,y)
if ans != None:
    print(' '.join(ans))
else:
    print(-1, -1, -1) 

### FIXED CODE ###

year = input()
year = year.replace('2017','2018')
print(year)
S,T=map(int,input().split())
	print(T+S)

### FIXED CODE ###

s,t=input().split()
print(t+s)
def resolve():
    #n=int(input())
    #a,b=map(int,input().split())
    #x=list(map(int,input().split()))
    #a=[list(map(lambda x:int(x)%2,input().split())) for _ in range(h)]

    def calc(x):#xは数字
        xn=x
        x=bin(x)[2:]
        cnt=sum(list(map(int,list(x))))
        if xn%cnt==0:
            return 1
        else:
            return calc(xn%cnt)+1
    
    n=int(input())    
    x=input()
    cnt=sum(list(map(int,list(x))))
    x=int(x,2)
    ans=[]
    for i in range(n):
        if x>>i&1:
            ans.append(calc(x-2**i))
        else:
            ans.append(calc(x+2**i))
    print(*ans[::-1],sep='\n')

if __name__ == '__main__':
    resolve()

### FIXED CODE ###

def resolve():
    #n=int(input())
    #a,b=map(int,input().split())
    #x=list(map(int,input().split()))
    #a=[list(map(lambda x:int(x)%2,input().split())) for _ in range(h)]

    def popcount(n):
        c=format(n,'b').count('1')
        if c!=0:
            return n%c
        else:
            return 0
    def f(n):
        count=0
        while n>0:
            n=popcount(n)
            count+=1
        return count
        
    n=int(input())    
    x=input()
    cnt=x.count('1')
    x10=int(x,2)
    ans=[]
    a=x10%(cnt+1)
    if cnt==1:
        b=0
    else:
        b=x10%(cnt-1)
    for i in range(n):
        if x[i]=='1' and cnt==1:
            print(0)
            continue
        elif x[i]=='1':
            cal=(b-pow(2,n-1-i,cnt-1))%(cnt-1)
        else:
            cal=(a+pow(2,n-1-i,cnt+1))%(cnt+1)
        print(f(cal)+1)

if __name__ == '__main__':
    resolve()
s,d=int(input()),input()
n=[int(i) for i in s]
l=len(s)
mod=10**9+7
dp=[[[0]*d,[0]*d] for i in range(l+1)]
dp[0][0][0]=1
for i in range(l):
    for smaller in range(2):
        for j in range(d):
            for x in range(10 if smaller else n[i]+1):
                dp[i+1][smaller or x<n[i]][(j+x)%d] += dp[i][smaller][j]
                dp[i+1][smaller or x<n[i]][(j+x)%d]%=mod
print((dp[l][0][0]+dp[l][1][0]-1)%mod)

### FIXED CODE ###

s,d=input(),int(input())
n=[int(i) for i in s]
l=len(s)
mod=10**9+7
dp=[[[0]*d,[0]*d] for i in range(l+1)]
dp[0][0][0]=1
for i in range(l):
    for smaller in range(2):
        for j in range(d):
            for x in range(10 if smaller else n[i]+1):
                dp[i+1][smaller or x<n[i]][(j+x)%d] += dp[i][smaller][j]
                dp[i+1][smaller or x<n[i]][(j+x)%d]%=mod
print((dp[l][0][0]+dp[l][1][0]-1)%mod)
dat0 = input()
if dat0 == 1:
    print("Hello World")
else:
    dat1 = input()
    dat2 = input()
    ans = int(dat1) + int(dat2)
    print(ans)


### FIXED CODE ###

dat0 = input()
if dat0 == "1":
    print("Hello World")
else:
    dat1 = input()
    dat2 = input()
    ans = int(dat1) + int(dat2)
    print(ans)
N,P=map(int,input().split())
ans=1
for i in range(1,P+1):
    a=pow(i,N)
    if P//a==0:
        break
    else:
        if P%a==0:
            ans=i
print(ans)

### FIXED CODE ###

N,P=map(int,input().split())
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
p=factorization(P)
#print(p)
k=[]
ans=1
for i in range(len(p)):
    d=p[i][1]//N
    k.append(d)
for i in range(len(p)):
    ans*=pow(p[i][0],k[i])
print(ans)
import itertools

[a,b,c] = [int(x) for x in input().split()]
[d,e,f] = [int(x) for x in input().split()]
[g,h,i] = [int(x) for x in input().split()]
N = int(input())
num_list = []
for i in N:
  n = int(input())
  num_list.append(n)
set_list = [{a,b,c},{d,e,f},{g,h,i},{a,d,g},{b,e,h},{c,f,i},{a,e,i}]
the_set = set(num_list) & set([a,b,c,d,e,f,g,h,i])
v = itertools.permutations(the_set,3)
for i in f:
  if i in set_list:
    print('Yes')
    break


### FIXED CODE ###

import itertools
import sys

[a,b,c] = [int(x) for x in input().split()]
[d,e,f] = [int(x) for x in input().split()]
[g,h,i] = [int(x) for x in input().split()]
N = int(input())
num_list = []
for j in range(N):
  n = int(input())
  num_list.append(n)

set_list = [{a,b,c},{d,e,f},{g,h,i},{a,d,g},{b,e,h},{c,f,i},{a,e,i},{c,e,g}]
the_set = set(num_list) & set([a,b,c,d,e,f,g,h,i])

v = itertools.permutations(the_set,3)
for k in v:
  if set(k) in set_list:
    print('Yes')
    sys.exit()
print('No')
from collections import Counter
input = sys.stdin.readline

def main():
    N = int(input())
    A = list(map(int, input().split()))
    Q = int(input())

    d = Counter(A)
    # print(d)

    for i in range(Q):
        ans = 0
        b, c = map(int, input().split())
        if b in d.keys():
            d[c] += d[b]
            d[b] = 0
        for k, v in d.items():
            ans += k * v
        # print(d)
        print(ans)


if __name__ == "__main__":
    main()



### FIXED CODE ###

from collections import Counter
import sys

input = sys.stdin.readline


def main():
    N = int(input())
    A = list(map(int, input().split()))
    Q = int(input())

    d = Counter(A)
    # print(d)
    ans = sum(A)

    for i in range(Q):
        b, c = map(int, input().split())
        if d[b] != 0:
            ans -= d[b] * b
            ans -= d[c] * c
            d[c] += d[b]
            d[b] = 0
            ans += d[c] * c

        print(ans)


if __name__ == "__main__":
    main()
N, Q = map(int, input().split())
S = input()
dp = [0] * N
for i in range(N-2, -1, -1):
    dp[i] = dp[i+1]
    if S[i:i+2] == 'AC':
        dp[i] += 1
for _ in range(Q):
    l, r = map(int, input().split())    print(dp[l-1] - dp[r-1])

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
dp = [0] * N
for i in range(N-2, -1, -1):
    dp[i] = dp[i+1]
    if S[i:i+2] == 'AC':
        dp[i] += 1
for _ in range(Q):
    l, r = map(int, input().split())
    print(dp[l-1] - dp[r-1])