Harryxun/stf_run huggingface dataset:
n=int(input())
K=int(input())
if K==1:
    counter=0
    for i in range(100):
        for j in range(1,10):
            a="0"*(i)+str(j)+"0"*(99-i)
            if 1<=int(a)<=n:
                counter+=1
    print(counter)
elif K==2:
    counter=0
    for i in range(100):
        for j in range(i+1,100):
            for k in range(1,10):
                for l in range(1,10):
                    a="0"*(i)+str(k)+"0"*(j-i-1)+str(l)+"0"*(99-j)
                    if 1<=int(a)<=n:
                        counter+=1
    print(counter)
elif K==3:
    counter=0
    for i in range(100):
        if 100-i>len(str(n)):
            pass
        elif 100-i<len(str(n)):
            for j in range(i+1,100):
                for k in range(j+1,100):
                    counter+=9*9*9
        elif 100-i==len(str(n)):
            for j in range(i+1,100):
                for k in range(j+1,100):

                        for b in range(1,10):
                            for c in range(1,10):
                                P=str(int(str(n)[i]))+"0"*(j-i-1)+str(b)+"0"*(k-j-1)+str(c)+"0"*(99-k)
                                if 1<=int(P)<=n:
                                    counter+=1
            counter+=((98-i)*(99-i)//2)*9*9*(int(str(n)[i])-1)
    print(counter)
                    


                    


### FIXED CODE ###

n=int(input())
K=int(input())
if K==1:
    counter=0
    for i in range(100):
        for j in range(1,10):
            a="0"*(i)+str(j)+"0"*(99-i)
            if 1<=int(a)<=n:
                counter+=1
    print(counter)
elif K==2:
    counter=0
    for i in range(100):
        for j in range(i+1,100):
            for k in range(1,10):
                for l in range(1,10):
                    a="0"*(i)+str(k)+"0"*(j-i-1)+str(l)+"0"*(99-j)
                    if 1<=int(a)<=n:
                        counter+=1
    print(counter)
elif K==3:
    counter=0
    for i in range(100):
        if 100-i>len(str(n)):
            pass
        elif 100-i<len(str(n)):
            for j in range(i+1,100):
                for k in range(j+1,100):
                    counter+=9*9*9
        elif 100-i==len(str(n)):
            for j in range(i+1,100):
                for k in range(j+1,100):

                        for b in range(1,10):
                            for c in range(1,10):
                                P=(str(n)[0])+"0"*(j-i-1)+str(b)+"0"*(k-j-1)+str(c)+"0"*(99-k)
                                if 1<=int(P)<=n:
                                    counter+=1
            counter+=((98-i)*(99-i)//2)*9*9*(int(str(n)[0])-1)
    print(counter)
def gcd(t):
    try:
        b,a=sorted(t)
        while True:
            m=a%b
            if m==0:
                return b
            a=b;b=m
    except:
        return 1

try:
    a,b,k=(int(x) for x in input().split())
    g=gcd((a,b))
    cd=[]
    i=g
except:
    print(1)
while True:
    try:
        if g%i==0:
            cd.append(i)
            i=i//2
            if i==0:
                break
        else:
            i-=1
    except:
        break
print(cd[k-1])

### FIXED CODE ###

def gcd(t):
    b,a=sorted(t)
    while True:
        m=a%b
        if m==0:
            return b
        a=b;b=m
a,b,k=(int(x) for x in input().split())
g=gcd((a,b))
cd=[]
for i in range(g+1)[::-1]:
    if i==0:
        break
    if g%i==0:
        cd.append(i)
print(cd[k-1])
#!/usr/bin/env python

def addToChild(i,ci):
    global c, visit
    visit[i]= True
    #
    for v in edge[i]:
        if visit[v]: continue
        c[v]+= ci
        addToChild(v,c[v])

import sys

n,q = [ int(x) for x in sys.stdin.readline().strip().split() ]
edge= [ [] for _ in range(n) ]
for i in range(n-1):
    a,b = [ int(x)-1 for x in sys.stdin.readline().strip().split() ]
    edge[a].append( b )
    edge[b].append( a )
#
sys.setrecursionlimit(n)
c= [ 0 for _ in range(n) ]
for i in range(q):
    p,x= [ int(x) for x in sys.stdin.readline().strip().split() ]
    c[p-1]+= x
#
visit= [ False for _ in range(n) ]
addToChild(0,c[0])
for ci in c: print( ci,end=" " )


### FIXED CODE ###

import sys
from operator import itemgetter

n,q = [ int(x) for x in sys.stdin.readline().strip().split() ]
edge= [ [] for _ in range(n-1) ]
for i in range(n-1):
    edge[i] = [ int(x)-1 for x in sys.stdin.readline().strip().split() ]
edge.sort( key=itemgetter(0) )
c= [ 0 for _ in range(n) ]
for i in range(q):
    p,x= [ int(x) for x in sys.stdin.readline().strip().split() ]
    c[p-1]+= x
#
for a,b in edge: c[b]+= c[a]

print( *c )
nm_ent = list(map(int, input().split()))
n = nm_ent[0]
m = nm_ent[1]

x = list(map(int, input().split()))
x.sort()
if m == 1:
    print(0)
else:
    xl = []
    for i in range(0, m-1):
        xl.append(x[i+1] - x[i])
    k = 1
    while k < n:
        xl.remove(max(xl))
        k += 1
    print(sum(xl))

### FIXED CODE ###

nm_ent = list(map(int, input().split()))
n = nm_ent[0]
m = nm_ent[1]

x = list(map(int, input().split()))
x.sort()
if n >= m:
    print(0)
else:
    xl = []
    for i in range(0, m-1):
        xl.append(x[i+1] - x[i])
    xl.sort(reverse = True)
    del xl[:n-1]
    print(sum(xl))
def main():
  N, K = map(int, input().split())
	h = list(map(int, input().split()))
	INF = 10**9
	dp = [INF] * N
	dp[0] = 0
	for i in range(N):
    	for k in range(1, K+1):
        	if i + k < N:
            	dp[i+k] = min(dp[i+k], dp[i]+abs(h[i] - h[i+k]))
        	else:
            	break
	print(dp[N-1])

if __name__ == '__main__':
  main()

### FIXED CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
INF = 10**9
dp = [INF] * N
dp[0] = 0
for i in range(N):
    for k in range(1, K+1):
        if i + k < N:
            dp[i+k] = min(dp[i+k], dp[i]+abs(h[i] - h[i+k]))
print(dp[N-1])
s = input()
print(s.replace(',',' ')）

### FIXED CODE ###

s = input()
print(s.replace(',',' '))
n = int(input())
as = list(map(int,input().split()))

ans = 1

for i in as:
    ans *= i
    ans = min(ans, 10*18+1)
if ans == 10**18+1:
    print('-1')
    break

print(ans)


### FIXED CODE ###

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

ans = 1

for i in As:
    ans *= i
    ans = min(ans, 10**18 + 1)

if ans == 10**18 + 1:
    print(-1)

else:
    print(ans)
N, A, B = map(int, input().split())

BLUE = "b"
RED = "r"


balls = ""
while True:
    if len(balls) >= N:
        break
    balls += BLUE*A
    balls += RED*B

print(len([ball for ball in list(balls)[0:N] if ball == BLUE]))


### FIXED CODE ###

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

if A == 0:
    print(0)
    exit()

x = int(N / (A+B))
y = N % (A+B)
z = 0
if y < A:
    z = y
else:
    z = A

blue = 0
if x < 10**100:
    blue = (x * A) + z
else:
    blue = 10*100*A + z
print(blue)
#! /usr/bin/env python3
# -*- coding: utf-8 -*-
N, K = [int(x) for x in input().split()]
height = []
for _ in range(N):
    height.append(int(input()))

height.sort()
height.reverse()
sublist = []
for i in range(N-K+1):
    hmax-hmin = height[i]-height[i+K-1]
    sublist.append(hmax-hmin)

print(min(sublist))


### FIXED CODE ###

#! /usr/bin/env python3
# -*- coding: utf-8 -*-
N, K = [int(x) for x in input().split()]
height = []
for _ in range(N):
    height.append(int(input()))

height.sort()
height.reverse()
sublist = []
for i in range(N-K+1):
    hmaxhmin = height[i]-height[i+K-1]
    sublist.append(hmaxhmin)

print(min(sublist))
n=int(input())
import math
mod=10**9+7
ans = math.factorial(n)
x=0
k = ans
for i in range(1,int(k**0.5)+1):
    if k%i==0:
        x+=1
        if i!=n//i:
            x+=1
print(x%mod)




### FIXED CODE ###

n=int(input())
mod=10**9+7
arr = {}
def factorization(k):
    temp=k
    for i in range(2,int(-(-k**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp//=i
            if i in arr:
                arr[i]+=cnt
            else:
                arr[i]=cnt
    if temp!=1:
        if temp in arr:
                arr[temp]+=1
        else:
            arr[temp]=1
    if arr==[]:
        if k in arr:
                arr[k]+=1
        else:
            arr[k]=1
for i in range(1,n+1):
    factorization(i)
ans=1

for value in arr.values():
    ans*=(value+1)
    
# print(arr)
print(ans%mod)




# x=0
# k = ans
# for i in range(1,int(k**0.5)+1):
#     if k%i==0:
#         x+=1
#         if i!=n//i:
#             x+=1
# print(x%mod)
from functools import lru_cache

N = int(input())
X = input()
x = int(X, 2)
y = X.count('1')
if y == 0:
    print(*[0]*N, sep='\n')
    exit()
else:
    x2 = x % (y-1)
x1 = x % (y+1)

def f(n):
    if n == 0:
        return 0
    return 1 + f(n % bin(n).count('1'))

d = [0] * (2*10**5+5)
for i in range(2*10**5+5):
    d[i] = f(i)

for i in range(N):
    if x >>(N - i - 1) & 1:
        # print(f(x-pow(2, N-i-1)))
        print(d[(x2 - pow(2, N - i - 1, y-1)) % (y-1)] + 1)
    else:
        # print(f(x+pow(2, N-i-1)))
        print(d[(x1 + pow(2, N - i - 1, y+1)) % (y+1)] + 1)

### FIXED CODE ###

from functools import lru_cache

N = int(input())
X = input()
x = int(X, 2)
y = X.count('1')
if y == 1:
    x2 = 0
else:
    x2 = x % (y-1)
x1 = x % (y+1)

def f(n):
    if n == 0:
        return 0
    return 1 + f(n % bin(n).count('1'))

d = [0] * (2*10**5+5)
for i in range(2*10**5+5):
    d[i] = f(i)

for i in range(N):
    if x >>(N - i - 1) & 1:
        # print(f(x-pow(2, N-i-1)))
        if y - 1 == 0:
            print(0)
        else:
            print(d[(x2 - pow(2, N - i - 1, y-1)) % (y-1)] + 1)
    else:
        # print(f(x+pow(2, N-i-1)))
        print(d[(x1 + pow(2, N - i - 1, y+1)) % (y+1)] + 1)
w = input()
for i in set(w):
    if w.count(i)%2 == 1:
        print("No")
        exit(1)

print("Yes")


### FIXED CODE ###

w = [input() for i in range(4)]
N = int(w[0])
K = int(w[1])
X = int(w[2])
Y = int(w[3])

paid = 0
for i in range(1,N+1):
    if i < K+1:
        paid += X
    else:
        paid += Y

print(paid)
n,m=map(int,input().split())
import math
a = list(map(int, input().split()))
ans = a[0]
for i in range(1, n):
    ans = ans * a[i] // math.gcd(ans, a[i])


b = [int(i/2) for i in a]
ans2= b[0]
for i in range(1, n):
    ans2 = ans2 * b[i] // math.gcd(ans2, b[i])


if ans2>m:
    print(0)
else:
    print((m-ans2)//ans+1)

### FIXED CODE ###

import fractions,sys

n,m=map(int,input().split())
a = list(map(int, input().split()))
# ans = a[0]
# for i in range(1,n):
#     ans = ans * a[i] // fractions.gcd(ans, a[i])
ff=[]
for j in  a:
    count=0
    for i in range(1,36):
        if j%(2**i)==0:
            count+=1
    ff.append(count)
ff=[i==ff[0] for i in ff]

 
b = [int(i/2) for i in a]
# b_list=[i%4==0 for i in b]
# bb=sum(b_list)
# if bb!=0 and bb!=n:
if all(ff)==False:
    print(0)
    exit()

ans2= b[0]
for i in range(1,n):
    ans2 = ans2 * b[i] // fractions.gcd(ans2, b[i])

# tf=[(ans2/i)%2==0 for i in b]
# and any(tf)
if ans2>m:
    print(0)
else:
    print((m-ans2)//(ans2*2)+1)
N, *X = map(int, open(0).read().split())

MAX = 10 ** 5
MOD = 10 ** 9 + 7

# Factorial
fac = [0] * (MAX + 1)
fac[0] = 1
fac[1] = 1
for i in range(2, MAX + 1):
    fac[i] = fac[i - 1] * i % MOD
    
# Inverse factorial
finv = [0] * (MAX + 1)
finv[MAX] = pow(fac[MAX], MOD - 2, MOD)
for i in reversed(range(1, MAX + 1)):
    finv[i - 1] = finv[i] * i % MOD

def comb(n, k):
    if n < k:
        return 0
    return fac[n] * finv[n - k] * finv[k]

# Find indices of duplicated values
indices = [-1] * (N + 1)
for i in range(N + 1):
    if indices[X[i]] < 0:
        indices[X[i]] = i
    else:
        l = indices[X[i]]
        r = i
        break

for k in range(1, N + 2):
    print((comb(N + 1, k) - comb(l + N - r, k - 1)) % MOD)



### FIXED CODE ###

N, *X = map(int, open(0).read().split())

MAX = 10 ** 5 + 1
MOD = 10 ** 9 + 7

# Factorial
fac = [0] * (MAX + 1)
fac[0] = 1
fac[1] = 1
for i in range(2, MAX + 1):
    fac[i] = fac[i - 1] * i % MOD
    
# Inverse factorial
finv = [0] * (MAX + 1)
finv[MAX] = pow(fac[MAX], MOD - 2, MOD)
for i in reversed(range(1, MAX + 1)):
    finv[i - 1] = finv[i] * i % MOD

def comb(n, k):
    if n < k:
        return 0
    return fac[n] * finv[n - k] * finv[k]

# Find indices of duplicated values
indices = [-1] * (N + 1)
for i in range(N + 1):
    if indices[X[i]] < 0:
        indices[X[i]] = i
    else:
        l = indices[X[i]]
        r = i
        break

for k in range(1, N + 2):
    print((comb(N + 1, k) - comb(l + N - r, k - 1)) % MOD)
def main():
    import numpy as np
    A=[]
    for _ in range(3):
        A.append(list(map(int,input().split())))
    
    R=np.zeros((3,3))
    K=[]
    for a in A:
        K+=a

    N=int(input())
    for i in range(N):
        b=int(input())
        if b not in K:
            continue
        
        idx=K.index(b)
        R[idx//3,idx%3]=1

    if any( all(x) for x in R.tolist()) or any(all(x) for x in R.T.tolist()):
        print('Yes')
    elif R[0,0] and R[1,1] and R[2,2] or R[0,2] and R[1,1] and R[2,0]:
        print('Yes')
    else:
        print('No')
        
main()


### FIXED CODE ###

def main():
    import numpy as np
    A=[]
    for _ in range(3):
        A.append(list(map(int,input().split())))
    
    R=np.zeros((3,3))
    K=[]
    for a in A:
        K+=a

    N=int(input())
    for i in range(N):
        b=int(input())
        if b not in K:
            continue
        
        idx=K.index(b)
        R[idx//3,idx%3]=1

    if any( all(x) for x in R.tolist()) or any(all(x) for x in R.T.tolist()):
        print('Yes')
    elif R[0,0] and R[1,1] and R[2,2] or R[0,2] and R[1,1] and R[2,0]:
        print('Yes')
    else:
        print('No')
        
main()
N, M = map(int, input().split())
data = []
for m in range(M):
  data.append(map(int, input().split()))
  
corresp = {}
for n in range(1, N+1):
    data_n = []
    for i in range(M):
        if data[i][0] == n:
            data_n.append(data[i])
    sort_n = sorted(data_n, key=lambda data_n_i: data_n_i[1])
    for k in range(len(sort_n)):
        corresp.update({str(sort_n[k]):k+1})
    

for i in range(M):
    print('{0:012d}'.format(data[i][0]*100000+corresp[str(data[i])]))


### FIXED CODE ###

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

print(X+(Y//2))
N = input()
list=[]
flg = 0 
for i in range(N):
    list.append(map(int, raw_input().split()))
if N == 1:
	rem = abs(list[0][1]) + abs(list[0][2])
	if rem == 1:
		print("Yes")
	else:
		print("No")
else:
	for i in range(N-1):
		rem = abs(list[i][1]-list[i+1][1]) + abs(list[i][2]-list[i+1][2])
		time = list[i][0]-list[i+1][0]
		if (time-rem) <= 0:
			flg = 1
			break
		elif (time-rem) % 2 ==1:
			flg = 1
		            break
	if flg == 0:
		print("Yes")
	else:
		print("No")

### FIXED CODE ###

N = input()
list=[]
flg = 0 
for i in range(N):
    list.append(map(int, raw_input().split()))
if N == 1:
	rem = abs(list[0][1]) + abs(list[0][2])
	if rem == 1:
		print("Yes")
	else:
		print("No")
else:
	for i in range(N-1):
		rem = abs(list[i][1]-list[i+1][1]) + abs(list[i][2]-list[i+1][2])
		time = list[i+1][0]-list[i][0]
		if (time-rem) < 0:
			    flg = 1
		            break
		elif (time-rem) % 2 ==1:
			    flg = 1
		            break
		            
	if flg == 0:
		print("Yes")
	else:
		print("No")
n,k = map(int,input().split())
s = []
ans = 0
for i in range(K):
  d = int(input())
  A = list(map(int,input().split()))
  for i in range(d):
    s.append(A[i])
  
for i in range(K):
  if s.count(i) == 0:
    ans += 1
    
print(ans)
    

### FIXED CODE ###

n,k = map(int,input().split())
s = []
ans = 0
for i in range(k):
  d = int(input())
  A = list(map(int,input().split()))
  for i in range(d):
    s.append(A[i])

for i in range(n+1):
  if s.count(i) == 0:
    ans += 1
    
print(ans-1)
import sys

H, W, M = map(int, input().split())
hw = [list(map(int, input().split())) for _ in range(M)]

hw.sort()

hcnt = [0] * (H+1)
wcnt = [0] * (W+1)

target = []
for i, j in hw:
    hcnt[i] += 1
    wcnt[j] += 1
    target.append([str(i) + " " + str(j),1])

d = dict(target)

hlist = []
hmax = -1
for i in range(1,H+1):
    if hmax < hcnt[i]:
        hlist = [i]
        hmax = hcnt[i]
    elif hmax == hcnt[i]:
        hlist.append(i)

wlist = []
wmax = -1
for i in range(1,W+1):
    if wmax < wcnt[i]:
        wlist = [i]
        wmax = wcnt[i]
    elif wmax == wcnt[i]:
        wlist.append(i)

if len(hlist) * len(wlist) > M:
    print(hmax + wmax)
    sys.exit()

idx = 0
for h in hlist:
    for w in wlist:
        while h > hw[idx][0] or w > hw[idx][1]:
            idx += 1
            if h == hw[idx][0] and w == hw[idx][1]:
                break
        if h < hw[idx][0] or w < hw[idx][1]:
            print(hmax + wmax)
            sys.exit()
        
print(hmax + wmax - 1)


### FIXED CODE ###

import sys

H, W, M = map(int, input().split())
hw = [list(map(int, input().split())) for _ in range(M)]

hw.sort()

hcnt = [0] * (H+1)
wcnt = [0] * (W+1)

target = []
for i, j in hw:
    hcnt[i] += 1
    wcnt[j] += 1
    target.append([str(i) + " " + str(j),1])

d = dict(target)

hlist = []
hmax = -1
for i in range(1,H+1):
    if hmax < hcnt[i]:
        hlist = [i]
        hmax = hcnt[i]
    elif hmax == hcnt[i]:
        hlist.append(i)

wlist = []
wmax = -1
for i in range(1,W+1):
    if wmax < wcnt[i]:
        wlist = [i]
        wmax = wcnt[i]
    elif wmax == wcnt[i]:
        wlist.append(i)

if len(hlist) * len(wlist) > M:
    print(hmax + wmax)
    sys.exit()

idx = 0
for h in hlist:
    for w in wlist:
        while h > hw[idx][0] or w > hw[idx][1]:
            idx += 1
            if idx == M:
                print(hmax + wmax)
                sys.exit()                
            if h == hw[idx][0] and w == hw[idx][1]:
                break
        if h < hw[idx][0] or w < hw[idx][1]:
            print(hmax + wmax)
            sys.exit()
        
print(hmax + wmax - 1)
from math import inf
from itertools import chain

H, W = map(int, input().split())
M = [list(input()) for _ in range(H)]


def flatten(list_of_lists):
    "Flatten one level of nesting"
    return chain.from_iterable(list_of_lists)


def bfs(start, end):
    distance = [[inf for i in range(W)] for j in range(H)]
    queue = [(end, start)]
    distance[end][start] = 0

    while queue:
        y, x = queue.pop()
        for i in range(0, 4):
            nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
            if 0 <= nx < W and 0 <= ny < H and M[ny][nx] != '#' and distance[ny][nx] == inf:
                queue.insert(0, (ny, nx))
                distance[ny][nx] = distance[y][x] + 1
    return distance


m = 0
for i in range(W):
    for j in range(H):
        if M[j][i] != "#":

            for length in list(flatten(bfs(i, j))):
                if length != inf and m < length:
                    m = length

print(m)


### FIXED CODE ###


from itertools import chain

H, W = map(int, input().split())
M = [list(input()) for _ in range(H)]
inf = float('inf')

def flatten(list_of_lists):
    "Flatten one level of nesting"
    return chain.from_iterable(list_of_lists)


def bfs(start, end):
    distance = [[inf for i in range(W)] for j in range(H)]
    queue = [(end, start)]
    distance[end][start] = 0

    while queue:
        y, x = queue.pop()
        for i in range(0, 4):
            nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
            if 0 <= nx < W and 0 <= ny < H and M[ny][nx] != '#' and distance[ny][nx] == inf:
                queue.insert(0, (ny, nx))
                distance[ny][nx] = distance[y][x] + 1
    return distance


m = 0
for i in range(W):
    for j in range(H):
        if M[j][i] != "#":

            for length in list(flatten(bfs(i, j))):
                if length != inf and m < length:
                    m = length

print(m)
# 二項係数を"やるだけ"にしてくれるライブラリ
from collections import Counter
MAX = 1000005
MOD = 10**9+7
factrial = [0]*MAX
inverse = [0]*MAX
factrial_inverse = [0]*MAX


# テーブルを作る前処理
def COMinit():
    global factrial, inverse, factrial_inverse
    factrial[0] = 1
    factrial[1] = 1
    inverse[1] = 1
    factrial_inverse[0] = 1
    factrial_inverse[1] = 1
    for i in range(2, MAX):
        factrial[i] = factrial[i-1] * i % MOD
        inverse[i] = MOD - inverse[MOD % i] * (MOD//i) % MOD
        factrial_inverse[i] = factrial_inverse[i-1] * inverse[i] % MOD


# 二項係数計算
def COM(n, k):
    global factrial, inverse, factrial_inverse
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return factrial[n] * (factrial_inverse[k] * factrial_inverse[n-k] % MOD) % MOD


# 前処理完了
COMinit()


N, P = map(int, input().split())  # 袋がN個, mod2をPにしたい
A = list(map(lambda x: int(x)%2, input().split()))
# print(A)

kisuu = sum(A)  # 奇数個の袋の数
guusuu = N-kisuu  # 偶数個の袋の数

# Pが1のとき，偶数側の袋を任意の数と，奇数側の数を奇数個選ぶ
if P == 1:
    aaa
    tmp_guusuu = 0
    tmp_kisuu = 0
    # 偶数側を任意の個数選ぶ
    for i in range(guusuu+1):
        tmp_guusuu += COM(guusuu, i)
    for i in range(kisuu+1):
        if i % 2 == 0:
            continue
        tmp_kisuu += COM(kisuu, i)
    print(tmp_guusuu*tmp_kisuu)

# Pが0のとき，偶数側の袋を任意の数と，奇数側の数を偶数個選ぶ
elif P == 0:
    tmp_guusuu = 0
    tmp_kisuu = 0
    # 偶数側を任意の個数選ぶ
    for i in range(guusuu+1):
        tmp_guusuu += COM(guusuu, i)
    # 奇数側を0個数以上の偶数個選ぶ
    for i in range(kisuu+1):
        if i % 2 == 1:
            continue
        tmp_kisuu += COM(kisuu, i)
    print(tmp_guusuu*tmp_kisuu)


### FIXED CODE ###

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)]


N, P = map(int, input().split())  # 袋がN個, 2をPにしたい
A = list(map(lambda x: int(x)%2, input().split()))
# print(A)

kisuu = sum(A)  # 奇数個の袋の数
guusuu = N-kisuu  # 偶数個の袋の数

# Pが1のとき，偶数側の袋を任意の数と，奇数側の数を奇数個選ぶ
if P == 1:
    tmp_guusuu = 0
    tmp_kisuu = 0
    # 偶数側を任意の個数選ぶ
    for i in range(guusuu+1):
        tmp_guusuu += cmb(guusuu, i)
    for i in range(kisuu+1):
        if i % 2 == 0:
            continue
        tmp_kisuu += cmb(kisuu, i)
    print(tmp_guusuu*tmp_kisuu)

# Pが0のとき，偶数側の袋を任意の数と，奇数側の数を偶数個選ぶ
elif P == 0:
    tmp_guusuu = 0
    tmp_kisuu = 0
    # 偶数側を任意の個数選ぶ
    for i in range(guusuu+1):
        tmp_guusuu += cmb(guusuu, i)
    # 奇数側を0個数以上の偶数個選ぶ
    for i in range(kisuu+1):
        if i % 2 == 1:
            continue
        tmp_kisuu += cmb(kisuu, i)
    print(tmp_guusuu*tmp_kisuu)
# 190928 D
from math import gcd as bltin_gcd

def coprime2(a, b):
    return bltin_gcd(a, b) == 1

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def divisor(n): #nの約数を全て求める
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table

if __name__ == "__main__":
    A,B = list(map(int,input().split()))
    kotable = sorted(divisor(gcd(A,B)))
    N = len(kotable)
    while True:
        flg = True
        for i in range(0,N-1):
            for j in range(i+1,N,1):
                if coprime2(kotable[i],kotable[j]) == False:
                    kotable.remove(kotable[j])
                    N -= 1
                    flg = False
                    break
            if flg == False:
                break
        if flg == True:
            break
                    
    print(len(kotable))
    

### FIXED CODE ###

# 190928 D

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

A,B = list(map(int,input().split()))
soA = prime_factorize(A)
soB = prime_factorize(B)
output = []
for i in range(len(soA)):
    if soA[i] in soB:
        output.append(soA[i])

print(len(list(set(output))) + 1)