Harryxun/stf_run huggingface dataset:
import sys
G = list(map(int, input().split()))
total = G[0] + G[1]
if total % 3 != 0:
  print(0)
  sys.exit(0)

total //= 3
dis = G[0] - total

mod = 10 ** 9 + 7
fact = [1]
fact_inv = [1]
for i in range(10**6+4):
    new_fact = fact[-1]*(i+1)%mod
    fact.append(new_fact)
    fact_inv.append(pow(new_fact,mod-2,mod))

def mod_comb_k(n,k,mod):
    return fact[n] * fact_inv[k] % mod * fact_inv[n-k] %mod

print(comb_mod(total, min(G)-total, mod))


### FIXED CODE ###

import sys
G = list(map(int, input().split()))
total = G[0] + G[1]
if total % 3 != 0:
  print(0)
  sys.exit(0)

total //= 3
dis = G[0] - total

MOD = 10 ** 9 + 7
def inv_mod(a, p=MOD):
    def inv_mod_sub(a, p):
        if a == 1:
            return 1, 0
        else:
            d, r = p//a, p%a
            x, y = inv_mod_sub(r, a)
            return y-d*x, x
    if p < 0: p = -p
    a %= p
    return inv_mod_sub(a,p)[0] % p

def comb_mod(n, k):
    if k < 0 or k > n:
        return 0
    else:
        return f_mod[n]*f_mod_inverse[k]*f_mod_inverse[n-k] % MOD
f_mod=[1]*(10**6)
f_mod_inverse=[1]*(10**6)
for i in range(1,10**6):
  f_mod[i]=f_mod[i-1]*i%MOD
  f_mod_inverse[i]=f_mod_inverse[i-1]*inv_mod(i)%MOD

print(comb_mod(total, dis))
import sys, math

def calcSum(AList, B, C, Sum):
    Len = AList[B]
    if(Len == 0):
        return Sum
    Sum += (C-B) * Len

    AList[B] = 0
    AList[C] += Len
    return Sum

if(__name__ == "__main__"):



    N= int( input().strip() )

    Max = 10**5
    AList = [0] * Max
    A_str = input().strip().split()
    N_Queries = int( input().strip() )

    sum = 0
    for i in range(N):
        value = int(A_str[i])
        AList[value] += 1
        sum += value
    BCs = []
    Sums = [sum]
    for i in range(N_Queries):
        BC_str =  input().strip().split()
        B = int(BC_str[0])
        C = int(BC_str[1])
        Sums.append( calcSum(AList, B, C, Sums[-1]) )
        """
        BC = [ int(BC_str[0]), int(BC_str[1]) ]
        BCs.append(BC)
        """

    for i in range(1, 1+N_Queries):
        print(Sums[i])


### FIXED CODE ###

import sys, math

def calcSum(AList, B, C, Sum):
    Len = AList[B]
    if(Len == 0):
        return Sum
    Sum += (C-B) * Len

    AList[B] = 0
    AList[C] += Len
    return Sum

if(__name__ == "__main__"):
    N= int( input().strip() )

    Max = int(10**5)+1
    AList = [0] * Max
    A_str = input().strip().split()
    N_Queries = int( input().strip() )

    sum = 0
    for i in range(N):
        value = int(A_str[i])
        AList[value] += 1
        sum += value
    BCs = []
    Sums = [sum]
    for i in range(N_Queries):
        BC_str =  input().strip().split()
        B = int(BC_str[0])
        C = int(BC_str[1])
        Sums.append( calcSum(AList, B, C, Sums[-1]) )
        """
        BC = [ int(BC_str[0]), int(BC_str[1]) ]
        BCs.append(BC)
        """

    for i in range(1, 1+N_Queries):
        print(Sums[i])
n = int(input())
L = [0 for _ in range(86)]
L[0]=2
L[1]=1
if n > 2:
    for i in range(2,n+1):
        L[i] = L[i-1]+L[i-2]
print(L[n])

### FIXED CODE ###

n = int(input())
L = [0 for _ in range(n+2)]
L[0]=2
L[1]=1
if n >= 2:
    for i in range(2,n+1):
        L[i] = L[i-1]+L[i-2]
print(L[n])
N,M = map(int,input().split())
S = []
for _ in range(M):
  S.append(int(input()))
S.sort()  

def Fib(n):    
    if n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        return Fib(n-1)+Fib(n-2)
      
for i in range(M):
  if i == 0:
    P = Fib(S[i]+1)
  else:
    P *= Fib(S[i] - S[i-1])
  if i == M-1:
    P *= Fib(N - S[i] + 1)

print(P%1000000007)

### FIXED CODE ###

def Fib(n):
    a, b = 0, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b

N,M = map(int,input().split())
if M == 0:
  P = Fib(N+2)
  print(P%1000000007)
else:
  S = []
  for _ in range(M):
    S.append(int(input()))
  S.append(-1)
  S.append(N+1)
  S.sort()  
  P = 1

  for i in range(M+1):
    P *= Fib(S[i+1]-S[i]) 

  print(P%1000000007)
a = map(int, input().split())
a.sort()
print(a[0]+a[1])

### FIXED CODE ###

a = list(map(int, input().split()))
a.sort()
print(a[0]+a[1])
people_num, first_point, correct = map(int,input().split())
people = [input() for i in range(people_num)]
points = [correct for i in range(people_num)]

for i in range(correct):
  for j in range(people_num):
    if j != i:
      points[j] -= 1
      if points[j] == 0:
        prints[j] = - 100000000

for i in range(people_num):
  if points[i] < 0:
  	print("No")
  else:
    print("Yes")

### FIXED CODE ###

people_num, first_point, correct = map(int,input().split())
who_correct = [input() for i in range(correct)]
points = [first_point-correct for i in range(people_num)]

 
for i in range(correct):
    points[int(who_correct[i])-1] += 1
    
for i in range(people_num):
  if points[i] <= 0:
  	print("No")
  else:
    print("Yes")
import itertools
N,A,B,C = map(int,input().split())
L = [int(input()) for _ in range(N)]
 
INF = 10 ** 18
answer = INF
for pattern in itertools.product(range(4), repeat = N):
  x = [0] * 4
  MP = 0
  for take, length in zip(pattern, L):
    if take == 3:
      continue
    if x[take] != 0:
      MP += 10
    x[take] += length
  if x[0] == 0 or x[1] == 0 or x[2] == 0:
    continue
  MP += abs(A-x[0])
  MP += abs(B-x[1])
  MP += abs(C-x[2])
  if answer > MP:
    answer = MP
print(answer

### FIXED CODE ###

import itertools
N,A,B,C = map(int,input().split())
L = [int(input()) for _ in range(N)]
 
INF = 10 ** 18
answer = INF
for pattern in itertools.product(range(4), repeat = N):
  x = [0] * 4
  MP = 0
  for take, length in zip(pattern, L):
    if take == 3:
      continue
    if x[take] != 0:
      MP += 10
    x[take] += length
  if x[0] == 0 or x[1] == 0 or x[2] == 0:
    continue
  MP += abs(A-x[0])
  MP += abs(B-x[1])
  MP += abs(C-x[2])
  if answer > MP:
    answer = MP
print(answer)
n, h = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(n)]

max_a = max(l, key=lambda x: x[0])[0]

l = [[a, b] for a, b in l if b > max_a]
l.sort(key=lambda x: x[1], reverse=True)
n = len(l)

c = 0
for i in range(n - 1):
  a, b = l[i]
  if a == max_a and l[i + 1][0] < max_a:
    l = l[i:]
    break
  h -= b
  c += 1
  if h <= 0:
    print(c)
    exit()
else:
  l = l[-1:]

last_a = l[0][0]
if l[0][1] >= h:
  print(c + 1)
else:
  for a, b in l[1:]:
    if b < last_a:
      break
    else:
      h -= b
      c += 1
      if h <= 0:
        print(c)
        exit()
  h -= l[0][1]
  c += 1
  print(c + h // last_a + (h % last_a != 0))

### FIXED CODE ###

n, h = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(n)]

max_a = max(l, key=lambda x: x[0])[0]
l = [[a, b] for a, b in l if b > max_a]
l.sort(key=lambda x: x[1], reverse=True)

c = 0
for a, b in l:
  h -= b
  c += 1
  if h <= 0:
    print(c)
    exit()

print(c + h // max_a + (h % max_a != 0))
S=input().split()
if S[3]==S[4] and S[5]==S[6]:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

S=input()
if S[2]==S[3] and S[4]==S[5]:
    print('Yes')
else:
    print('No')
n=int(input())
a=sorted(list(map(int,input().split())))

l=[0]*(100005)
for i in range(n):
    if l[a[i]]==1:
        l[a[i]]+=1

    if l[a[i]]==0:
        for j in range(100000//a[i]+1):
            l[a[i]*j]+=1
    
cnt=0
for i in range(n):
    if l[a[i]]==1:
        cnt+=1
print(cnt)
            
        

### FIXED CODE ###

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

l=[0]*(1000005)
for i in range(n):
    if l[a[i]]==1:
        l[a[i]]+=1

    if l[a[i]]==0:
        for j in range(1000000//a[i]+1):
            l[a[i]*j]+=1
    
cnt=0
for i in range(n):
    if l[a[i]]==1:
        cnt+=1
print(cnt)
a,b,c = int(input().split(" "))
if a + b + c == 22:
  print("bust")

### FIXED CODE ###

A1, A2, A3 = map(int, input().split())

if sum([A1, A2, A3]) >= 22:
  print('bust')
else:
  print('win')
import sys
N=int(input())
a=[int(i) for i in input().split()]
a.sort()

if a[N-1]-a[0]>1:
  print("No")
  sys.exit()
if a[0]==N-1:
  print("Yes")
  sys.exit()
print(a[N])

### FIXED CODE ###

import sys
N=int(input())
a=[int(i) for i in input().split()]
a.sort()

if a[N-1]-a[0]>1:
  print("No")
  sys.exit()
if a[0]==N-1:
  print("Yes")
  sys.exit()
if a[N-1]==1:
  print("Yes")
  sys.exit()
if a[0]==a[N-1]:
  if 2*a[0]<=N:
    print("Yes")
  else:
    print("No")
  sys.exit()

count=a.index(a[N-1])
if count+1<=a[N-1] and a[N-1]<=count+int((N-count)/2):
  print("Yes")
else:
  print("No")
K = int(input())
A, B = map(int, input().split())


ps = int(A / K)
pa = A % K
qs = int(B / K)
qa = B % K

if A==B:
	if p==0:
		print("OK")
	else:
		print("NG")
else:
	if qs-ps>0:
		print("OK")
	else:
		if pa+qa >K:
			print("OK")
		else:
			print("NG")


### FIXED CODE ###

K = int(input())
A, B = map(int, input().split())


ps = int(A / K)
pa = A % K
qs = int(B / K)
qa = B % K

if A==B:
	if pa==0:
		print("OK")
	else:
		print("NG")
else:
	if qs-ps>0:
		print("OK")
	else:
		if pa==0 or qa ==0:
			print("OK")
		else:
			print("NG")
def calc():
    summ  = sum(A)
    low = summ / (4*M)
    high = 1000

    num = len([i for i in A if low <= i])
    #print(num)

    if M > num:
        print ("No")
    else:
        print ("Yes")

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


#N, M = 5, 2
#A = list(range(1, 6))
calc()

### FIXED CODE ###

#def calc():
    #summ  = sum(A)
    #print(summ)
    
    #low = summ / (4*M)
    #print(low)

    #newlist = [i for i in A if i >= low]
    #print(newlist)

    #num = len(newlist)
    #print(num)

    #if M <= num:
        #print ("Yes")
    #else:
        #print ("No")

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

#N, M = 5, 2
#A = [110, 2, 20, 10, 0]
#calc()

S = sum(A)
cnt = 0

for i in A:
    if i >= S / (4*M):
        cnt += 1
if cnt >= M:
    print("Yes")
else:
    print("No")
import collections
n=int(input())
ans=0
s=["".join(sorted(input())) for _ in range(n)]
c=collections.Counter(s)
for i in set(s):
  a=c[s]
  ans+=a*(a-1)//2
print(ans)



### FIXED CODE ###

N=int(input())
dictionary={}
count=0
for i in range(N):
    s=tuple(sorted(input()))
    if s in dictionary:
        dictionary[s]+=1
        count+=dictionary[s]
    else:
        dictionary[s]=0
print(count)
N, K =map(int, input().split())
import math
lcm=math.lcm(N,K)
ans=min(lcm, K-lcm) 


### FIXED CODE ###

N, K =map(int, input().split())
ans=N%K
print(min(ans, K-ans))
import sys

def insertionSort(A, N):
    for n in range(N-1):
        print (A[n], end=" ")
    print(A[N-1])
    for i in range(1, N):
        v = A[i]
        j = i - 1
        while j >= 0 and A[j] > v:
            A[j + 1] = A[j]
            j = j - 1
        A[j + 1] = v
        
        for n in range(N-1):
            print (A[n], end=" ")
        print(A[N-1])
    return A

N = int(input())
A = input()
A = A.split(" ")
for i in range(N):
    A[i] = int(A[i])
val = insertionSort(stdin_A, stdin_N)

### FIXED CODE ###

import sys

def insertionSort(A, N):
    for n in range(N-1):
        print (A[n], end=" ")
    print(A[N-1])
    for i in range(1, N):
        v = A[i]
        j = i - 1
        while j >= 0 and A[j] > v:
            A[j + 1] = A[j]
            j = j - 1
        A[j + 1] = v
        
        for n in range(N-1):
            print (A[n], end=" ")
        print(A[N-1])
    return A

N = int(input())
A = input()
A = A.split(" ")
for i in range(N):
    A[i] = int(A[i])
val = insertionSort(A, N)
input = '5 4 2 2 1'#W,H,x,y,r
w, h, x, y, r = input1.split()

top = y + r
bottom = y - r
left = x - r
right = x + r

if h >= top and bottom >= and right >= top and left >= 0:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

w, h, x, y, r = [int(i) for i in input().split(' ')]

top = y + r
bottom = y - r
left = x - r
right = x + r

if h >= top and bottom >= 0 and w >= right and left >= 0:
    print('Yes')
else:
    print('No')
def exists(value,n,ms,cs):
    if (len(value) != n):
        return False
    if all([value[i-1] == c for i,c in zip(ms,cs)]):
        return True
    return True
def unzip(li):
    return list(map(list, zip(*li)))
n,m = [int(e) for e in input().split()]
m = [input().split() for e in range(m)]
ms,cs = unzip(m)
ms = [int(e) for e in ms]
result = -1
for i in range(1000):
    if exists(str(i),n,ms,cs):
        result = i
        break
print(result)

### FIXED CODE ###

n,m = map(int,input().split())
sc = [[i for i in map(int,input().split())] for j in range(m)]
start = 0
goal = 0
if n==1:
  start = 0
  goal = 9
elif n==2:
  start = 10
  goal = 99
elif n==3:
  start = 100
  goal = 999

flag = 1
ans = -1
for num in range(start,goal+1):
  flag = 1
  for i in range(m):
    if str(num)[sc[i][0]-1] != str(sc[i][1]): #両辺ともちゃんとstrで変換
      flag = 0
  if flag == 1:
    ans = num
    break

print(ans)
n,m=map(int,input().split())
a=list(map(int,input().split()))
c=sum(a)/(4*m)
ans=0
for i in range(n):
    if a[n]>=c:
        ans+=1
if ans>=m:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
c=sum(a)/(4*m)
ans=0
for i in range(n):
    if a[i]>=c:
        ans+=1
if ans>=m:
    print('Yes')
else:
    print('No')
x, y = map(int, input().stlip(' '))

if y % 2 != 0:
  print('No')
elif y - 2 * x < 0:
  print('No')
else:
  print('Yes')
  


### FIXED CODE ###

X, Y = map(int, input().split(' '))

ans = 'No'
for x in range(X+1):
  if 2*x + 4*(X-x) == Y:
    ans = 'Yes'
    break
    
print(ans)
#!/usr/bin/env python
# -*- coding: utf-8 -*-

from itertools import product
coins = [10,50,100,500]

def coin_count(num):
    count = 0
    for coin in sorted(coins,reverse = True):
        count += num // coin
        num -= (num // coin)*coin
    return count

while True:
    price = int(input())
    if price == 0:
        break
    dp = [-1 for i in range(20*660)]
    dp[0] = 0
    has = map(lambda x:list(range(int(x)+1)),input().split(" "))
    ans = (10**8,())
    for t in product(*has):
        tmp = price - sum([coins[i] * t[i] for i in range(4)])
        if tmp <= 0:
            ans = min(ans,(coin_count(-1 * tmp),t))
    for i in range(4):
        if ans[1][i] != 0:
            print(coins[i],ans[1][i])
    print()

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

from itertools import product
coins = [10,50,100,500]

def coin_count(num):
    count = 0
    for coin in sorted(coins,reverse = True):
        count += num // coin
        num -= (num // coin)*coin
    return count

flag = True
while True:
    price = int(input())
    if price == 0:
        break

    if flag:
        flag = False
    else:
        print()

    has = list(map(int,input().split()))
    sum_coins = list(map(lambda x: x[0]*x[1], zip(has,coins)))


    change = (sum(sum_coins) - price)
    surplus = [change % 50 // 10, change % 100 // 50, change % 500 // 100, change // 500]

    for i in range(4):
        if has[i] > surplus[i]:
            print(coins[i],has[i] - surplus[i])
N, M = [int(i) for i in input().split()]
A = sorted([s for s in input().split()], reverse=True)
numDict = {"1":2, "2":5, "3":5, "4":4, "5":5, "6":6, "7":3, "8":7, "9":6}
dp = ["" for _ in range(N + 1)]

for i in range(N + 1):
    for strNum in A:
        if i - numDict[strNum] == 0 and dp[i] == "":
            dp[i] = strNum

        preStrNum = dp[i - numDict[strNum]]
        if preStrNum != "":
            if len(preStrNum) + 1 > len(dp[i]):
                dp[i] = preStrNum + strNum

print("".join(sorted(dp[N], reverse=True)))


### FIXED CODE ###

N, M = [int(i) for i in input().split()]
A = sorted([s for s in input().split()], reverse=True)
numDict = {"1":2, "2":5, "3":5, "4":4, "5":5, "6":6, "7":3, "8":7, "9":6}
dp = ["" for _ in range(N + 1)]

for i in range(N + 1):
    for strNum in A:
        if i - numDict[strNum] < 0:
            continue
        if i - numDict[strNum] == 0 and dp[i] == "":
            dp[i] = strNum
        preStrNum = dp[i - numDict[strNum]]
        if preStrNum != "":
            if len(preStrNum) + 1 > len(dp[i]):
                dp[i] = preStrNum + strNum

print("".join(sorted(dp[N], reverse=True)))
def main(A, dq, n):
    if n == -1:
        return dq[0]

    if (n in A) == False: 
        dp[n] = (dp[n + 1] + dp[n + 2]) % mod
    return main(A, dq, n-1)
 
N, M = map(int, input().split())
mod = 1000000007
dp = [0] * 10**5
A = [int(input()) for _ in range(M)] 
dp[N], dp[N-1] = 1, 1
ans = main(A, dp, N-2)
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
mod = 1000000007
dp = [0] * (N+2)
A = set([int(input()) for _ in range(M)]) 
dp[-2] = 1

for i in range(N-1, -1, -1):
    if (i in A) == False:
        dp[i] = (dp[i + 1] + dp[i + 2]) % mod 

print(dp[0])
a, b = (int(i) for i in input().split())  
print("{}{}".format(b, a))

### FIXED CODE ###

a, b = (i for i in input().split())
print("{}{}".format(b, a))
#入力,準備
N,W=map(int,input().split())
w=[0]*n
v=[0]*n
for i in range(n):
    w[i],v[i]=map(int,input().split())
dp=[0]*(W+1)

#メイン
#dp[j] : 重さの総和がjを超えないように選んだ時の価値の総和の最大値
for i in range(n):
    j=W
    while j>=w[i]:
        dp[j]=max(dp[j],dp[j-w[i]]+v[i])
        j-=1

print(dp[W])

### FIXED CODE ###

N,W=map(int,input().split())
w=[0]*N
v=[0]*N
for i in range(N):
    w[i],v[i]=map(int,input().split())
dp=[0]*(W+1)
for i in range(N):
    j=W
    while j>=w[i]:
        dp[j]=max(dp[j],dp[j-w[i]]+v[i])
        j-=1
print(dp[W])
from collections import Counter
N=int(input())
NN=N//2
l=list(map(int,input().split()))
l1=[l[2*i] for i in range(NN)]
l2=[l[2*i+1] for i in range(NN)]
l1c=Counter(l1)
l2c=Counter(l2)
r1=l1c.most_common()
r2=l2c.most_common()
if r1[0][0]==r2[0][0]:
  if r1[0][0]==NN and r2[0][0]==NN:
    ans=NN
  elif r1[0][1]>r2[0][1]:
    ans=N-r1[0][1]-r2[1][1]
  else:
    ans=N-r1[1][1]-r2[0][1]
else:
  ans=N-r1[0][1]-r2[0][1]
print(ans)

### FIXED CODE ###

from collections import Counter
N=int(input())
NN=N//2
l=list(map(int,input().split()))
l1=[l[2*i] for i in range(NN)]
l2=[l[2*i+1] for i in range(NN)]
l1c=Counter(l1)
l2c=Counter(l2)
r1=l1c.most_common()
r2=l2c.most_common()
if r1[0][0]==r2[0][0]:
  if r1[0][1]==NN and r2[0][1]==NN:
    ans=NN
  elif r1[0][1]>r2[0][1]:
    ans=N-r1[0][1]-r2[1][1]
  elif r1[0][1]<r2[0][1]:
    ans=N-r1[1][1]-r2[0][1]
  else:
    if r1[1][1]>r2[1][1]:
      ans=N-r1[1][1]-r2[0][1]
    else:
      ans=N-r1[0][1]-r2[1][1]
else:
  ans=N-r1[0][1]-r2[0][1]
print(ans)
import numpy as np
n = int(input())
an = np.array(input().split(" ")).astype("int64")


if an[0] == 0:
    if n % 2 == 0:
        print("0")
    elif n % 2 == 1:
        print("1")
        print("1")
elif an[0] == 1:
    if n % 2 == 0:
        print("1")
        print("1")
    elif n % 2 == 1:
        print("0")

### FIXED CODE ###

r = int(input())
print(3 * (r ** 2))
n = int(input().strip())
s = [input().strip() for _ in range(n)]
num_m = len([True for _s in s if _s[0] == "M"])
num_a = len([True for _s in s if _s[0] == "A"])
num_r = len([True for _s in s if _s[0] == "R"])
num_c = len([True for _s in s if _s[0] == "C"])
num_h = len([True for _s in s if _s[0] == "H"])
print(num_m * num_a * num_r + num_m * num_a * num_c + num_m * num_a * num_h + num_m * num_r * num_c
      + num_m * num_r * num_h + num_m * num_c * num_h + num_a * num_r * num_c +
      num_a * num_r * num_h + num_a * num_c * num_h + num_r * num_c * num_h

### FIXED CODE ###

n = int(input().strip())
s = [input().strip() for _ in range(n)]
num_m = len([True for _s in s if _s[0] == "M"])
num_a = len([True for _s in s if _s[0] == "A"])
num_r = len([True for _s in s if _s[0] == "R"])
num_c = len([True for _s in s if _s[0] == "C"])
num_h = len([True for _s in s if _s[0] == "H"])
print(num_m * num_a * num_r + num_m * num_a * num_c + num_m * num_a * num_h + num_m * num_r * num_c
      + num_m * num_r * num_h + num_m * num_c * num_h + num_a * num_r * num_c +
      num_a * num_r * num_h + num_a * num_c * num_h + num_r * num_c * num_h)
n, k = map(int, input().split())
s = input()
print(s[:k]+s.[k]lower()+s[k+1:])


### FIXED CODE ###

n, k = map(int, input().split())
s = input()
print(s[:k-1]+s[k-1].lower()+s[k:])
N = int(input())
K = int(input())
L = len(str(N))

def solve(num_str, k, smaller):

    keta = len(num_str)
    if k == 0:
        return 1
    elif smaller:
        if k == 1:
            return keta * 9
        elif k == 2:
            return keta * (keta-1)//2 * 9 * 9
        else:
            return keta * (keta-1) * (keta -2)//6 * 9 * 9 * 9
    else:   
        num = int(num_str)
        num_str = str(num_str)
        top = int(num_str[0])
        if top:
            zero = solve(num_str[1:], k, True)
            non_zero = solve(num_str[1:], k-1, True) * (top - 1)
            just = solve(num_str[1:], k-1, False)
            return zero + non_zero + just
        else:
            return solve(num_str[1:], k, False)
print(solve(str(N), K, False))

### FIXED CODE ###

N = int(input())
K = int(input())
L = len(str(N))

suu = []
for i in range(L):
    suu.append(int(str(N)[i]))

DP_1 =[[0 for k in range(L+2)] for i in range(L+1)]
DP_2 =[[0 for k in range(L+2)] for i in range(L+1)]
DP_2[0][0] = 1
for i in range(L):
    for k in range(L+1):
        DP_1[i+1][k] = DP_1[i][k] + DP_1[i][k-1] * 9 
        if suu[i]:
            DP_1[i+1][k] += DP_2[i][k] + DP_2[i][k-1] * max(suu[i] - 1, 0)
            DP_2[i+1][k] = DP_2[i][k-1]
        else:
            DP_2[i+1][k] = DP_2[i][k]
print(DP_1[L][K]+ DP_2[L][K])
k,s = int(input().split())
ret = 0
for i in range(k+1):
    bmax = min(k,bpc)+1
    bmin = max(0,s-i-k)
    if bmin < bmax : ret += bmax - bmin
print(ret)

### FIXED CODE ###

k,s = map(int,input().split())
ret = 0
for i in range(k+1):
    bmax = min(k,s-i)+1
    bmin = max(0,s-i-k)
    if bmin < bmax : ret += bmax - bmin
print(ret)
n = int(input())
a = n // 100
b = n % 100 // 10
c = n % 10
if a = 7:
  print('Yes')
elif b = 7:
  print('Yes')
elif c = 7:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

n = str(input())
a = '7'
if a in n:
  print('Yes')
else:
  print('No')
N = int(input())
S = input()
if S[N/2] == S[N/2:]:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

N = int(input())
S = input()
if S[:int(N / 2)] == S[int(N / 2):]:
    print("Yes")
else:
    print("No")
from math import gcd
from numpy import sign
mod = 1000000007
N = int(input())

if N == 1:
    print(1)
    
d = {}
counter = 0

f = 0
l = 0

for _ in range(N):
    a, b = list(map(int, input().split()))
    if a == b == 0:
        counter += 1
    elif a==0:
        f += 1
    elif b==0:
        l += 1
    else:
        g = gcd(a, b)
        a, b =  a // g, b //g
        if b < 0:
            a, b = -a, -b
        if (a, b) not in d:
            d[(a, b)] =1
        else:
            d[(a, b)] +=1

answer = 1


group = set()
for (p, q), v in d.items():
    invp,invq=-q,p
    if invq<0:
        invp,invq=-invp,-invq
    if not (invp,invq) in group:
        group.add((p,q))

for (p, q), v in group:
    invp, invq = (sign(p) * (-1) * q, abs(p))
    if (invp, invq) not in d:
        answer *= (2 ** d[(p, q)]) % mod
        answer = answer % mod
    else:
        answer *= ((2 ** d[(p, q)]) + (2 ** d[(invp, invq)]) - 1) % mod
        answer = answer % mod
        
answer *= 2**f + 2**l - 1
    
print((answer + counter - 1) % mod)

### FIXED CODE ###

from math import gcd
from numpy import sign
mod = 1000000007
N = int(input())

d = {}
counter = 0

f = 0
l = 0

for _ in range(N):
    a, b = list(map(int, input().split()))
    if a == b == 0:
        counter += 1
    elif a==0:
        f += 1
    elif b==0:
        l += 1
    else:
        g = gcd(a, b)
        a, b =  a // g, b //g
        if b < 0:
            a, b = -a, -b
        if (a, b) not in d:
            d[(a, b)] =1
        else:
            d[(a, b)] +=1

answer = 1

group = set()
for (p, q), v in d.items():
    invp,invq=-q,p
    if invq<0:
        invp,invq=-invp,-invq
    if not (invp,invq) in group:
        group.add((p,q))

for (p, q) in group:
    invp,invq=-q,p
    if invq<0:
        invp,invq=-invp,-invq
    if (invp, invq) not in d:
        answer *= (2 ** d[(p, q)])
    else:
        answer *= ((2 ** d[(p, q)]) + (2 ** d[(invp, invq)]) - 1)
        
answer *= 2**f + 2**l - 1
    
print((answer + counter - 1) % mod)