Harryxun/stf_run huggingface dataset:
#!venv/bin/python

N,K = [int(x) for x in input().split()]
A = [format(int(x), 'b') for x in input().split()]

count_1 = [0 for i in range(40)]
count_0 = [0 for i in range(40)]

print(A)

for a in A:
    for i in range(40):
        if i >= len(a):
            count_0[i] += 1
            continue
        if a[-(i+1)] == "1":
            count_1[i] += 1
        else:
            count_0[i] += 1
        
k = 0
for i in range(39,0,-1):
    if 2 ** i + k > K:
        continue
    if count_0[i] > count_1[i]:
        k += 2 ** i

ans = 0
for a in A:
    ans += k ^ int(a,2)
print(ans)


### FIXED CODE ###

#!venv/bin/python

T, X = [int(x) for x in input().split()]

print(T / X)
m, n = [int (input().split(" ")]

a =[ [int(i) for i in input().split(" ")] for _ in range(n) ]
b =[]
for i in range(m):
    b.append( int(input()) )


for x in range(n):
    result = 0
    for y in range(m):
        result += a[x][y] * b[y]
    print(result)
    

### FIXED CODE ###

n, m = [int(i) for i in input().split(" ")]

a =[ [int(i) for i in input().split(" ")] for _ in range(n) ]
b =[]
for i in range(m):
    b.append( int(input()) )


for x in range(n):
    result = 0
    for y in range(m):
        result += a[x][y] * b[y]
    print(result)
N, M = map(int,input().split(' '))
a = [int(input()) for i in range(M)]
for i in range(M-1):
  if a[i]+1 == a[i+1]:
    print(0)
    exit()
def step(n):
  if n == 0 :
    return 1
  elif n == 1 :
    return 2
  tmp = [0]*n
  tmp[0] = 1
  tmp[1] = 2
  for i in range(2,n):
    tmp[i] = tmp[i-2] + tmp[i-1]
  return tmp[n-1]
ans = step(a[0]-1)
for i in range(1,M):
  n = a[i] - a[i-1] - 2
  ans = ans*step(n)
n = N - a[M-1] -1
ans = ans*step(n)

print(ans%(10**9+7))

### FIXED CODE ###

N, M = map(int,input().split(' '))
a = set([int(input()) for i in range(M)])
ans = [0]*(N+1)
ans[0] = 1
for i in range(1,N+1):
  if i in a:
    ans[i] = 0
  else:
    ans[i] = (ans[i-1]+ans[i-2])%(10**9+7)
print(ans[N])
def comb(n, r):
    return f(n) / (f(n - r) * f(r)) 
 
def f(n):
    if n == 1:
        return 1
    else:
        return n * f(n - 1)

n = input()
a = map(int, raw_input().split())
 
a.sort()
a.reverse()
max = 0
ai = 0
aj = 0
for i in range(0, len(a)):
    for j in range(i + 1, len(a)):
        c = comb(a[i], a[j])
        if c > max:
            max = c
            ai = a[i]
            aj = a[j]
print(str(ai) + " " + str(aj))

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split(" ")]
m = max(a)
abs_min = m
abs_i = 0

for i in range(0, n):
    ab = abs((m + 1)//2 - a[i])
    if a[i] != m and abs_min > ab:
        abs_min = ab
        abs_i = i
        
print(m, a[abs_i])
str = input()

list = str.split()

odd=["R","U","D"]
even=["L","U","D"]

i = 1
flag = False
for l in list:
    if i % 2 == 0:
        if l in even:
            pass
        else:
            flag = True
            break
    else:
        if l in odd:
            pass
        else:
            flag = True
            break
if(flag):
    print(No)
else:
    print(Yes)

### FIXED CODE ###

str = input()

list = list(str)

i = 0
f = True
for l in list:
    i+=1
    if i%2 != 0:
        if l == "L":
            f=False
            break
    else:
        if l == "R":
            f=False
            break

if(f):
    print("Yes",end="\n")
else:
    print("No",end="\n")
from itertools import *
n = int(input())
d = list(map(int,input().split()))
ans = 0
for i,j in comninations(d,2):
  ans += i*j
print(ans)


### FIXED CODE ###

from itertools import *
n = int(input())
d = list(map(int,input().split()))
ans = 0
for i,j in combinations(d,2):
  ans += i*j
print(ans)
=10**9+7
n,m=map(int,input().split())
A=[1 for i in range(n)]
if n!=1:
  A[1]=2
  for i in range(m):
    A[int(input())-1]=0
  
  if A[0]==0 and A[1]!=0:
    A[1]=1



  for i in range(2,n):
    if A[i]!=0:
      A[i]=(A[i-1]+A[i-2])
      A[i]%=MOD

    
  print(A[n-1])

### FIXED CODE ###

MOD=10**9+7
n,m=map(int,input().split())
A=[1 for i in range(n)]
if n!=1:
  A[1]=2
  for i in range(m):
    A[int(input())-1]=0
  
  if A[0]==0 and A[1]!=0:
    A[1]=1



  for i in range(2,n):
    if A[i]!=0:
      A[i]=(A[i-1]+A[i-2])
      A[i]%=MOD

    
  print(A[n-1])
  
else:print(1)
N, M = map(int, input().split())

result = [-2] * N
edge_from = [[] for _ in range(N + 1)]
edge_to = [[] for _ in range(N + 1)]

for _ in range(N - 1 + M):
    A, B = map(int, input().split())
    edge_from[B].append(A)
    edge_to[A].append(B)

parent = []
for i in range(1, N + 1):
    if any(edge_to[i]) and not any(edge_from[i]):
        parent.append(i)
        result[i] = -1
        break

while True:
    next_ = []
    for p in parent:
        for child in edge_to[p]:
            edge_from[child].remove(p)
            if not any(edge_from[child]):
                result[child] = p
                next_.append(child)
    if not any(next_):
        break
    parent = next_

for x in result:
    print(x)

### FIXED CODE ###

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

result = [-2] * N
edge_from = [[] for _ in range(N)]
edge_to = [[] for _ in range(N)]

for _ in range(N - 1 + M):
    A, B = map(int, input().split())
    edge_from[B-1].append(A-1)
    edge_to[A-1].append(B-1)

parent = []
for i in range(N):
    if len(edge_to[i]) > 0 and len(edge_from[i]) == 0:
        parent.append(i)
        result[i] = -1

while True:
    next_ = []
    for p in parent:
        for child in edge_to[p]:
            edge_from[child].remove(p)
            if len(edge_from[child]) == 0:
                result[child] = p
                next_.append(child)
    if len(next_) == 0:
        break
    parent = next_.copy()

for x in result:
    print(x + 1)
R = int(input())
if R < 1200:
    print('ABC')
elif:
    R < 2800:
    print('ARC')
else:
    print('AGC')


### FIXED CODE ###

R = int(input())
if R < 1200:
    print('ABC')
elif R < 2800:
    print('ARC')
else:
    print('AGC')
import sys

lines = []
for line in sys.stdin:
    lines.append(line.strip().split(','))

field = [[0 for i in range(10)] for j in range(10)]

def drop(x, y, z):
    if z==1:
        for i in range(-1,2):
            for j in range(-1,2):
                if abs(i)+abs(j)<2 and 0<=y+j<=10 and 0<=x+i<=10:
                    field[y+j][x+i] += 1
    elif z==2:
        for i in range(-1,2):
            for j in range(-1,2):
                if 0<=y+j<=10 and 0<=x+i<=10:
                    field[y+j][x+i] += 1
    else:
        for i in range(-2,3):
            for j in range(-2,3):
                if abs(i)+abs(j)<3 and 0<=y+j<=10 and 0<=x+i<=10:
                    field[y+j][x+i] += 1



for line in lines:
    x,y,z = map(int, line)
    drop(x,y,z)



### FIXED CODE ###

import sys

lines = []
for line in sys.stdin:
    lines.append(line.strip().split(','))

field = [[0 for i in range(10)] for j in range(10)]

def drop(x, y, z):
    if z==1:
        for i in range(-1,2):
            for j in range(-1,2):
                if abs(i)+abs(j)<2 and 0<=y+j<=9 and 0<=x+i<=9:
                    field[y+j][x+i] += 1
    elif z==2:
        for i in range(-1,2):
            for j in range(-1,2):
                if 0<=y+j<=9 and 0<=x+i<=9:
                    field[y+j][x+i] += 1
    else:
        for i in range(-2,3):
            for j in range(-2,3):
                if abs(i)+abs(j)<3 and 0<=y+j<=9 and 0<=x+i<=9:
                    field[y+j][x+i] += 1



for line in lines:
    x,y,z = map(int, line)
    drop(x,y,z)

n = 0
m = 0
for f in field:
    for e in f:
        if e > m:
            m = e
        if e==0:
            n+=1

print(n)
print(m)
n,m=map(int,input().split())

ab = [map(int, input().split()) for _ in range(m)]
a,b = [list(i) for i in zip(*ab)]

indexlist=[-1]*n

def findroot(x):
    while 1:
        if indexlist[x-1] < 0:
            return x
        else:
            x=indexlist[x-1]
            


def merge(a,b):
    art=findroot(a)
    brt=findroot(b)
    if not art == brt:
        indexlist[art-1]+=indexlist[brt-1]
        indexlist[brt-1]=a
        return
    else:
        return
        

for j in range(m):
    a1=a[j]
    b1=b[j]
    merge(a1,b1)

ans=min(indexlist)*(-1)
print(ans)

### FIXED CODE ###

import sys

#UnionFindTreeクラスの定義
class UnionFind():
    #クラスコンストラクタ
    #selfはインスタンス自身
    def __init__(self, n):
        #親ノードを-1に初期化する
        self.parents = [-1] * n

    #根を探す（再帰関数）
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    #xとyの木を併合する
    def union(self, x, y):
        #x,yの根をX,Yとする
        X = self.find(x)
        Y = self.find(y)

        #根が同じなら結合済み
        if X == Y:
            return

        #ノード数が多い方をXとする
        if self.parents[X] > self.parents[Y]:
            X, Y = Y, X

        #XにYのノード数を足す
        self.parents[X] += self.parents[Y]
        #Yの根をXとする
        self.parents[Y] = X


N, M = map(int, input().split())
info = [tuple(map(int, s.split())) for s in sys.stdin.readlines()]

#UnionFindインスタンスの生成
uf = UnionFind(N)
for a, b in info:
    #インデックスを調整し、a,bの木を結合
    a -= 1; b -= 1
    uf.union(a, b)

ans = min(uf.parents)

print(-ans)
import sys
import math
from functools import reduce

readline = sys.stdin.buffer.readline


def main():
    gcd = math.gcd

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

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

    B = A[::]
    while not any(b % 2 for b in B):
        B = [b // 2 for b in B]

    if not all(b % 2 for b in B):
        print(0)
        return

    semi_lcm = reduce(lcm, (a // 2 for a in A))
    print((M // semi_lcm + 1) // 2)
    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

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

from math import floor
from fractions import gcd
from functools import reduce


def lcm(x, y):
    return x * y // gcd(x, y)


b = [n // 2 for n in a]

lcm_b = reduce(lcm, b)

for n in b:
    if (lcm_b // n) % 2 == 0:
        print(0)
        exit()

n = floor((M / lcm_b - 1) / 2) + 1

print(n)
X, A = map(int(input().split()))
if(X < A): print(0)
else: print(10)

### FIXED CODE ###

X, A = map(int, input().split())
if(X < A): print(0)
else: print(10)
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from EmurateInput import input

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


def rot_encode(n):
    from string import ascii_lowercase as lc, ascii_uppercase as uc
    lookup = str.maketrans(lc + uc, lc[n:] + lc[:n] + uc[n:] + uc[:n])
    return lambda s: s.translate(lookup)


print(rot_encode(N)(S))


### FIXED CODE ###

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


def rot_encode(n):
    from string import ascii_lowercase as lc, ascii_uppercase as uc
    lookup = str.maketrans(lc + uc, lc[n:] + lc[:n] + uc[n:] + uc[:n])
    return lambda s: s.translate(lookup)


print(rot_encode(N)(S))
A = [map(int, input().split())]

print(max(A) - min(A))


### FIXED CODE ###

A = [int(x) for x in input().split()]

print(max(A) - min(A))
s = input()
s = s[::-1]
mod = 10 ** 9 + 7
table = [[0] * 13 for _ in range(len(s) + 2)]
table[0][0] = 1
dd = 1
for c in range(len(s)):
    if s[c] == "?":
        for n in range(10):
            for i in range(13):
                table[c + 1][(i + n * dd) % 13] += table[c][i]
                table[c + 1][(i + n * dd) % 13] %= mod
    else:
        num = int(s[c])
        for i in range(13):
            table[c + 1][(i + num * dd) % 13] += table[c][i]
            table[c + 1][(i + num * dd) % 13] %= mod
    dd = (dd * 10) % 13
print(table[c + 1][5])

### FIXED CODE ###

import sys
input = sys.stdin.readline

A, B = map(int, input().split())
if (A + B) % 2 == 0:
    print( (A + B) // 2)
else:
    print('IMPOSSIBLE')
# -*- coding: utf-8 -*-
a1, a2, a3 = map(int, input().sprit())
print("win" if a1 + a2 + a3 <=21 else "bust")

### FIXED CODE ###

# -*- coding: utf-8 -*-
a1, a2, a3 = map(int, input().split())
print("win" if a1 + a2 + a3 <= 21 else "bust")
from functools import lru_cache

import numpy as np


@lru_cache(maxsize=None)
def xor(bit, digit):
    """
    A の各要素について右から digit 桁目を bit で XOR した合計
    :param int bit:
    :param int digit:
    :return:
    """
    assert bit in [0, 1]
    bit <<= digit
    mask = 1 << digit
    return sum([(a ^ bit) & mask for a in A])


_, K = map(int, input().split())
A = list(map(int, input().split()))

DIGIT = 50

# [桁][k 未満の桁をえらんだことがあるか]
dp = np.empty([DIGIT + 1, 2], dtype=int)
dp.fill(-np.inf)

dp[-1][0] = 0
for d in reversed(range(DIGIT)):
    k = (K >> d) & 1
    # bit=k
    dp[d][0] = max(dp[d][0], dp[d + 1][0] + xor(bit=k, digit=d))
    # k==1 なら bit=0 も OK
    if k == 1:
        dp[d][1] = max(dp[d][1], dp[d + 1][0] + xor(bit=0, digit=d))
    # k 未満の桁をえらんだことがあるなら bit にどっちを選んでも OK
    dp[d][1] = max(dp[d][1], dp[d + 1][1] + xor(bit=0, digit=d))
    dp[d][1] = max(dp[d][1], dp[d + 1][1] + xor(bit=1, digit=d))

print(dp[0].max())


### FIXED CODE ###

from functools import lru_cache


def get_bit(n, d):
    return (n >> d) & 1


@lru_cache(maxsize=None)
def xor(bit, digit):
    """
    A の各要素について右から digit 桁目を bit で XOR した合計
    :param int bit:
    :param int digit:
    :return:
    """
    assert bit in [0, 1]
    # bit <<= digit
    # mask = 1 << digit
    # return sum([(a ^ bit) & mask for a in A])
    if bit == 0:
        return bit_counts[digit] << digit
    else:
        return (N - bit_counts[digit]) << digit


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

DIGIT = 50
bit_counts = [sum([get_bit(a, d=d) for a in A]) for d in range(DIGIT)]

# [桁][k 未満の桁をえらんだことがあるか]
dp = [[-float('inf') for _ in range(2)] for _ in range(DIGIT + 1)]
# dp = np.empty([DIGIT + 1, 2], dtype=int)
# dp.fill(-np.inf)

dp[-1][0] = 0
for d in reversed(range(DIGIT)):
    k = get_bit(K, d=d)
    # bit=k
    dp[d][0] = max(dp[d][0], dp[d + 1][0] + xor(bit=k, digit=d))
    # k==1 なら bit=0 も OK
    if k == 1:
        dp[d][1] = max(dp[d][1], dp[d + 1][0] + xor(bit=0, digit=d))
    # k 未満の桁をえらんだことがあるなら bit にどっちを選んでも OK
    dp[d][1] = max(dp[d][1], dp[d + 1][1] + xor(bit=0, digit=d))
    dp[d][1] = max(dp[d][1], dp[d + 1][1] + xor(bit=1, digit=d))

print(max(dp[0]))
# B
import math
N = int(input())

def make_prime_list(num):
    if num < 2:
        return []

    prime_list = [i for i in range(num + 1)]
    prime_list[1] = 0 # 1は素数ではない
    num_sqrt = math.sqrt(num)

    for prime in prime_list:
        if prime == 0:
            continue
        if prime > num_sqrt:
            break

        for non_prime in range(2 * prime, num, prime):
            prime_list[non_prime] = 0

    return [prime for prime in prime_list if prime != 0]

def search_divisor_num(num):
    if num < 0:
        return None
    elif num == 1:
        return 1
    else:
        num_sqrt = math.floor(math.sqrt(num))
        prime_list = make_prime_list_2(num_sqrt)

        divisor_num = 1
        for prime in prime_list:
            count = 1
            while num % prime == 0:
                num //= prime
                count += 1
            divisor_num *= count

        if num != 1:
            divisor_num *= 2

        return divisor_num

re = 0
for i in range(1, N+1, 2):
    num = search_divisor_num(i)
    if num == 8:
        re += 1
        
print(re)

### FIXED CODE ###

import math
N = int(input())

def make_prime_list(num):
    if num < 2:
        return []

    prime_list = [i for i in range(num + 1)]
    prime_list[1] = 0 # 1は素数ではない
    num_sqrt = math.sqrt(num)

    for prime in prime_list:
        if prime == 0:
            continue
        if prime > num_sqrt:
            break

        for non_prime in range(2 * prime, num, prime):
            prime_list[non_prime] = 0

    return [prime for prime in prime_list if prime != 0]

def search_divisor_num(num):
    if num < 0:
        return None
    elif num == 1:
        return 1
    else:
        num_sqrt = math.floor(math.sqrt(num))
        prime_list = make_prime_list(num_sqrt)

        divisor_num = 1
        for prime in prime_list:
            count = 1
            while num % prime == 0:
                num //= prime
                count += 1
            divisor_num *= count

        if num != 1:
            divisor_num *= 2

        return divisor_num

re = 0
for i in range(1, N+1, 2):
    num = search_divisor_num(i)
    if num == 8:
        re += 1
        
print(re)
a=int(input())
b=int(input())
x=(a*b)%2
if x==0:
	print("Even")
else:
  	print("Odd")

### FIXED CODE ###

a,b=map(int,input().split())
x=(a*b)%2
if x==0:
	print("Even")
else:
  	print("Odd")
N = int(input())
l = list(map(int, input().split()))
l.sort()
 
from bisect import bisect_left
ans = 0
for i in range(n):
  for j in range(i+1, n):
    t = l[i]+l[j]
    idx = bisect_left(l, t)
    ans += max(0, idx-j-1)
print(ans)

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
l.sort()
 
from bisect import bisect_left
ans = 0
for i in range(n):
  for j in range(i+1, n):
    t = l[i]+l[j]
    idx = bisect_left(l, t)
    ans += max(0, idx-j-1)
print(ans)
N = int(input())
L = input().split()
L = [int(s) for s in L]
i = 0
L_max = 0
for i in range(len(L)):
    if L[i] < L[i+1]:
        L_max = L[i+1]
if L_max > sum(L):
    print("Yes")
else:
    print("No")        

### FIXED CODE ###

N = int(input())
L = input().split()
L = [int(s) for s in L]
i = 0
L_max = L[0]
for i in range(len(L)):
    if L_max < L[i]:
        L_max = L[i]
if L_max < sum(L) - L_max:
    print("Yes")
else:
    print("No")
N = int(input())
A = list(map(int,input().split()))
for i in range(N):
  A[i]-= i+1
A.sort()
total = sum(A)
mean1 = total//N
mean2 = total//N + 1
med1 = A[N//2]
med2 = A[N//2+1]
ans1 = 0
ans2 = 0
ans3 = 0
ans4 = 0 
for a in A:
  ans1+=abs(a-mean1)
  ans2+=abs(a-mean2)
  ans3+=abs(a-med1)
  ans4+=abs(a-med2)
print(min([ans1,ans2,ans3,ans4]))

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
for i in range(N):
  A[i]-= i+1
A.sort()
total = sum(A)
mean1 = total//N
mean2 = total//N + 1
med1 = A[N//2]
#med2 = A[N//2+1]
ans1 = 0
ans2 = 0
ans3 = 0
ans4 = 0 
for a in A:
  ans1+=abs(a-mean1)
  ans2+=abs(a-mean2)
  ans3+=abs(a-med1)
  #ans4+=abs(a-med2)
print(min([ans1,ans2,ans3]))
N, M = map(int,input().split())
S = []
for i in range(M):
    s = tuple(map(int,input().split()))
    S.append(s)
ans = [-1 for _ in range(M)]

for x in S:
    if ans[x[0]-1] == -1 or ans[x[0]-1] == x[1]:
        ans[x[0]-1] = x[1]
    else:
        print(-1)
        exit()
if N > 1 and ans[0] == 0:
    print(-1)
    exit()

for i in range(len(ans)):
    if ans[i] == -1 :    
        if i == 0:
            print('1',end='')
        else:
            print('0',end='')
    else:
        print(ans[i],end='')
print()




### FIXED CODE ###

N , M = map(int,input().split())
L = []
for _ in range(M):
    m = tuple(map(int,input().split()))
    L.append(m)
if N == 1:
    for ans in range(0,10):
        ans = str(ans)
        for x in L:
            if ans[x[0] - 1] != str(x[1]):
                break
        else:
            print(ans)
            exit()
    print(-1)
    exit()
else:
    for ans in range(10 ** (N - 1),10 ** N ):
        ans = str(ans)
        for x in L:
            if ans[x[0] - 1] != str(x[1]):
                break
        else:
            print(ans)
            exit()
    print(-1)
    exit()
# -*- coding: utf-8 -*-
A,B=map(int,input().split)
if A <= 8 and B <= 8:
  print("Yay!")
else:
  print(":(")

### FIXED CODE ###

# -*- coding: utf-8 -*-
A,B =map(int,input().split())
if A <= 8 and B <= 8:
  print("Yay!")
else:
  print(":(")
x,k,d = list(map(int,input().split()))
x = abs(x)
mst = x//d
if mst&1 != k&1:
    mst+=1
print(abs(x-(min(mst,k))*d))

### FIXED CODE ###

t = input()
if "RRR" in t:
    print(3)
elif "RR" in t:
    print(2)
elif "R" in t:
    print(1)
else:
    print(0)
s = [input() for _ in range(int(input))]
t = [input() for _ in range(int(input))]

l = list(set(s))

print(max(0, max(s.count(l[i]) - t.count(l[i]) for i in range(len(l)))))

### FIXED CODE ###

s = [input() for _ in range(int(input()))]
t = [input() for _ in range(int(input()))]

l = list(set(s))

print(max(0, max(s.count(l[i]) - t.count(l[i]) for i in range(len(l)))))
H, W = map(int, input().split())

for i in range(W):
    c = input()
    print(c + '\n' + c)

### FIXED CODE ###

H, W = map(int, input().split())

for i in range(H):
    c = input()
    print(c + '\n' + c)
import sys
lines = sys.stsin.readlines()
K, N = map(int, lines[0].srtip().split())
As = map(int, lines[1].strip().split())

diffs =[]
for base, switch in zip(arr[:-1], arr[1:]+[0]):
  diffs append(switch-base)

diffs append(arr[0]+K-arr[-1])

print(K-max(diffs))

### FIXED CODE ###

K, N = list(map(int, input().split()))
As = list(map(int, input().split()))
diffs =[]
for base, switch in zip(As[:-1], As[1:]):
  diffs.append(switch-base)
diffs.append(As[0]+K-As[-1])
print(K-max(diffs))
n = input()
k = int(input())

dl = [[None] * (len(n) + 1) for _ in range(len(n) + 1)]
de = [[None] * (len(n) + 1) for _ in range(len(n) + 1)]


def n_num_e(d, i):
    # d: n of digits
    # i: n of nonzero digits
    if d == 0:
        if i == 0:
            return 1
        else:
            return 0
    elif de[d][i] is not None:
        return de[d][i]
    else:
        if int(n[d - 1]) == 0:
            result = n_num_e(d - 1, i)
        else:
            result = n_num_e(d - 1, i - 1)
        de[d][i] = result
        return result


def n_num_l(d, i):
    # d: n of digits
    # i: n of nonzero digits
    if d == 0:
        return 0
    elif dl[d][i] is not None:
        return dl[d][i]
    else:
        if int(n[d - 1]) == 0:
            ne = 0
            nl = 9 * n_num_l(d - 1, i - 1) + n_num_l(d - 1, i)
            result = ne + nl
        else:
            ne = (int(n[d - 1]) - 1) * n_num_e(d - 1, i - 1) + n_num_e(d - 1, i)
            nl = 9 * n_num_l(d - 1, i - 1) + n_num_l(d - 1, i)
            result = ne + nl

        dl[d][i] = result
        return result


answer = n_num_e(len(n), k) + n_num_l(len(n), k)
print(answer)



### FIXED CODE ###

from sys import setrecursionlimit
setrecursionlimit(10 ** 6)
MAXN = 100

n = input()
k = int(input())

dl = [[None] * (MAXN + 1) for _ in range(MAXN + 1)]
de = [[None] * (MAXN + 1) for _ in range(MAXN + 1)]


def n_num_e(d, i):
    # d: n of digits
    # i: n of nonzero digits
    if d == 0:
        if i == 0:
            return 1
        else:
            return 0
    elif de[d][i] is not None:
        return de[d][i]
    else:
        if int(n[d - 1]) == 0:
            result = n_num_e(d - 1, i)
        else:
            result = n_num_e(d - 1, i - 1)
        de[d][i] = result
        return result


def n_num_l(d, i):
    # d: n of digits
    # i: n of nonzero digits
    if d == 0:
        return 0
    elif dl[d][i] is not None:
        return dl[d][i]
    else:
        if int(n[d - 1]) == 0:
            ne = 0
            nl = 9 * n_num_l(d - 1, i - 1) + n_num_l(d - 1, i)
            result = ne + nl
        else:
            ne = (int(n[d - 1]) - 1) * n_num_e(d - 1, i - 1) + n_num_e(d - 1, i)
            nl = 9 * n_num_l(d - 1, i - 1) + n_num_l(d - 1, i)
            result = ne + nl

        dl[d][i] = result
        return result


answer = n_num_e(len(n), k) + n_num_l(len(n), k)
print(answer)
N, M = map(int, input().split())

nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]

id N == 0:
  a = cmb(M,2)
elif M == 0:
  a = cmb(N,2)
else:
  a = cmb(N,2) + cmb(M,2)

print(int(a))

### FIXED CODE ###

N, M = map(int, input().split())
 
nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]

if N < 2 and M < 2:
  a = 0
elif N < 2:
  a = cmb(M,2)
elif M < 2:
  a = cmb(N,2)
elif N > 1 and M > 1:
  a = cmb(N,2) + cmb(M,2)

print(int(a))
import math

a,b=map(int,input().split())
print(int(a*b/math.gcd(a,b)))


### FIXED CODE ###

import fractions

A,B=map(int,input().split())
f=A*B//fractions.gcd(A,B)
print(f)
a,b,x=map(int,input().split())

for in range(a,b+1):
  if i%x==0:
    Base=i
    break
count=1
num=2
while Base<=b:
  Base*=num
  count+=1
    
print(count)


### FIXED CODE ###

#-*- coding:utf-8 -*-
a,b,x=map(int,input().split())

print(b//x-(a-1)//x)