Harryxun/stf_run huggingface dataset:
#abc123d
 
x,y,z,k=map(int,raw_input().split())
a=sorted(map(int,raw_input().split()),reverse=True)
b=sorted(map(int,raw_input().split()),reverse=True)
c=sorted(map(int,raw_input().split()),reverse=True)
 
ab=sorted([i+j for i in a for j in b],reverse=True)
res=sorted([ij+l for ij in ab[:k] for l in c],reverse=True)
for i in res[:k]:
	print i

### FIXED CODE ###

#abc123d
 
x,y,z,k=map(int,raw_input().split())
a=sorted(map(int,raw_input().split()),reverse=True)
b=sorted(map(int,raw_input().split()),reverse=True)
c=sorted(map(int,raw_input().split()),reverse=True)
 
ab=sorted([i+j for i in a for j in b],reverse=True)
res=sorted([ij+l for ij in ab[:k] for l in c],reverse=True)
for i in res[:k]:
	print i
a, b, c, k = map(int, input().split())

ans = 0
while a > 0:
  a - 1
  k - 1
  ans += 1
  if k = 0:
    brake
  if a = 0:
    brake
while b > 0:
  b - 1
  k - 1
  ans += 0
  if k = 0:
    brake
  if b = 0:
    brake
while c > 0:
  c - 1
  k - 1
  ans -= 1
  if k = 0:
    brake
  if c = 0:
    brake
  

### FIXED CODE ###

A, B, C, K =map(int, input().split())
print(min(A, K) - max(0, K - A - B))
N = int(input())
A = input()
S = A.replace(' ','a')
S = S + 'a'

for i in range(N):
  j = str(i+1) + 'a'
  k = S.count(j)
  print(k)



### FIXED CODE ###

import math

R = int(input())
R = 2*R*math.pi

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


n = int(input())
ans = 1
l = [int(input()) for i in range(n)]

for i in l:
    ans = ans*i/gcd(ans,i)
print(int(ans))

### FIXED CODE ###

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


n = int(input())
ans = 1
l = [int(input()) for i in range(n)]

for i in l:
    ans = ans*i//gcd(ans,i)
print(ans)
n = input()

if n[-2] != '9' and n[-1] != '9':
  n[-2] = '9'
  n[-1] = str(int(n[-1])+1)

print(sum(n))

### FIXED CODE ###

N = list(map(str, input().rstrip()))
print(max(sum([int(i) for i in N]), 9*(len(N)-1)+int(N[0])-1))
import sys

input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))

A_dash = []
for i in range(N):
    A_dash.append(A[i] - (i + 1))

A_dash.sort()
ans = -float("inf")
if N % 2 == 0:
    tmp = 0
    b = A_dash[N // 2]
    for i in range(N):
        tmp += abs(A_dash[i] - b)
    print(tmp)
else:
    tmp1 = 0
    b = A_dash[N // 2]
    for i in range(N):
        tmp1 += abs(A_dash[i] - b)
    
    tmp2 = 0
    b = A_dash[N // 2 + 1]
    for i in range(N):
        tmp2 += abs(A_dash[i] - b)
    print(min(tmp1, tmp2))

### FIXED CODE ###

import sys

input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))

A_dash = []
for i in range(N):
    A_dash.append(A[i] - (i + 1))

A_dash.sort()
ans = -float("inf")
if N % 2 == 1:
    tmp = 0
    b = A_dash[N // 2]
    for i in range(N):
        tmp += abs(A_dash[i] - b)
    print(tmp)
else:
    tmp1 = 0
    b = A_dash[N // 2 - 1]
    for i in range(N):
        tmp1 += abs(A_dash[i] - b)
    
    tmp2 = 0
    b = A_dash[N // 2]
    for i in range(N):
        tmp2 += abs(A_dash[i] - b)
    print(min(tmp1, tmp2))
n, m = int(input())

a = n - 1
b = m - 1

print(a * b)

### FIXED CODE ###

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

print((n-1)*(m-1))
a = list(map(int,inputr().split()))
b = list(map(int,inputr().split()))
print((a[0]-b[0])*(a[1]-b[1]))

### FIXED CODE ###

a = list(map(int,input().split()))
b = list(map(int,input().split()))
print((a[0]-b[0])*(a[1]-b[1]))
h,w = map(int, input().split())
mat = [[True] * (w+2)]
for _ in range(h):
    mat.append([True] + [a == '#' for a in input()] + [True])
mat.append([True]*(w+2)])

prev = []
for i in range(1,h+1):
    for j in range(1,w+1):
        if mat[i][j]:
            prev.append((i,j))

round = -1
while prev:
    #print(prev)
    #print(mat)
    round += 1
    next = []
    for (x,y) in prev:
        if not mat[x-1][y]:
            next.append((x-1,y))
            mat[x-1][y] = True
        if not mat[x][y-1]:
            next.append((x,y-1))
            mat[x][y-1] = True
        if not mat[x+1][y]:
            next.append((x+1,y))
            mat[x+1][y] = True
        if not mat[x][y+1]:
            next.append((x,y+1))
            mat[x][y+1] = True
    prev = next

print(round)


### FIXED CODE ###

import functools as ft

h,w = map(int, input().split())
mat = [[True] * (w+2)]
for _ in range(h):
    mat.append([True] + [a == '#' for a in input()] + [True])
mat.append([True]*(w+2))

prev = []
for i in range(1,h+1):
    for j in range(1,w+1):
        if mat[i][j]:
            prev.append((i,j))



round = -1
while prev:
    round += 1
    #print(prev)
    #print(mat)
    def calc(next, tup):
        x = tup[0]
        y = tup[1]
        if not mat[x-1][y]:
            next.append((x-1,y))
            mat[x-1][y] = True
        if not mat[x][y-1]:
            next.append((x,y-1))
            mat[x][y-1] = True
        if not mat[x+1][y]:
            next.append((x+1,y))
            mat[x+1][y] = True
        if not mat[x][y+1]:
            next.append((x,y+1))
            mat[x][y+1] = True
        return next
    next = ft.reduce(calc, prev, [])

    prev = next

print(round)
t=list(map(int,input().split()))
a=list(map(int,input().split()))
b=list(map(int,input().split()))
x,y=[(a[0]-b[0])*t[0],(a[1]-b[1])*t[1]]

if x+y==0:
    print("infinity")
#elif (x<0 and y<0) or (x>0 and y>0):
#    print(0)
#elif (x<0 and x+(x+y)>0) or (x>0 and x+(x+y)<0):
#    print(1)

#elif x<0 and x+y>0:
#    print((abs(x)//(x+y))*2+[0,1][abs(x)%(x+y)>0])
#elif x<0 and x+y<0:
#    print((y//abs(x+y))*2)
#elif x>0 and x+y<0:
#    print((x//abs(x+y))*2+[0,1][x%abs(x+y)>0])
elif x>0 and x+y>0 and abs(y)%(x+y)==0:
    print((abs(y)//(x+y))*2)
else:
    print(hhh)

### FIXED CODE ###

T1, T2 = map(int, input().split())
A1, A2 = map(int, input().split())
B1, B2 = map(int, input().split())
 
P = (A1 - B1) * T1
Q = (A2 - B2) * T2
if P > 0:
	P *= -1
	Q *= -1
 
if P + Q < 0:
	print(0)
elif P + Q == 0:
	print("infinity")
else:
	S = (-P) // (P + Q)
	T = (-P) % (P + Q)
	if T != 0:
		print(S * 2 + 1)
	else:
		print(S * 2)
arr = map(int, raw_input().split())
ans = 0
for x in range(arr[0], arr[1] + 1):
  if arr[2] % x == 0:
    ans += 1

print(ans)

### FIXED CODE ###

arr = map(int, raw_input().split())
ans = 0
for x in range(arr[0], arr[1] + 1):
  if arr[2] % x == 0:
    ans += 1

print(ans)
h,w=map(int,input().split())

li=[]
for i in range(h):
    li.append(list(input()))

new_li=[[0]*w for i in range(h)]

#＃の位置をリストに集める
sharp_li=[]
for i in range(h):
    for j in range(w):
        if li[i][j]=='#':
            sharp_li.append([i,j])   

            
for k in range(len(sharp_li)):
    #y行X列を扱う
    y=sharp_li[k][0]
    x=sharp_li[k][1]
    
    #tryの例外処理だとうまくいかなかったので、端の場合を自力で書いて場合わけする
    if x==0:
        xli=[0,1]
    elif x==w-1:
        xli=[w-2,w-1]
    else:
        xli=[x-1,x,x+1]
    
    if y==0:
        yli=[0,1]
    elif y==h-1:
        yli=[h-2,h-1]
    else:
        yli=[y-1,y,y+1]
        
        
    for l in xli:
        for m in yli:
            new_li[m][l]+=1           #m行l列なので
           
        
ans=[]             
for n in range(h):
    stred=list(map(str,new_li[n]))
    ans.append(stred)

#もともとの爆弾の部分を＃に戻す

for o in range(len(sharp_li)):
    ans[sharp_li[o][0]][sharp_li[o][1]]='#'


for p in range(h):
    tans=''.join(ans[p])
    print(tans)

### FIXED CODE ###

h,w=map(int,input().split())

li=[]
for i in range(h):
    li.append(list(input()))

new_li=[[0]*w for i in range(h)]

#＃の位置をリストに集める
sharp_li=[]
for i in range(h):
    for j in range(w):
        if li[i][j]=='#':
            sharp_li.append([i,j])   

for k in range(len(sharp_li)):
    #y行X列を扱う
    y=sharp_li[k][0]
    x=sharp_li[k][1]
    
    #tryの例外処理だとうまくいかなかったので、端の場合を自力で書いて場合わけする
    if x==0:
        if w!=1:             #1行や1列の場合がエラーの原因なので、無理やりif文で処理
            xli=[0,1]
        else:
            xli=[0]
    elif x==w-1:
        xli=[w-2,w-1]
    else:
        xli=[x-1,x,x+1]
    
    if y==0:
        if h!=1:
            yli=[0,1]
        else:
            yli=[0]
    elif y==h-1:
        yli=[h-2,h-1]
    else:
        yli=[y-1,y,y+1]
        
        
    for l in xli:
        for m in yli:
            new_li[m][l]+=1           #m行l列なので
           
        
ans=[]             
for n in range(h):
    stred=list(map(str,new_li[n]))
    ans.append(stred)
#もともとの爆弾の部分を＃に戻す

for o in range(len(sharp_li)):
    ans[sharp_li[o][0]][sharp_li[o][1]]='#'


for p in range(h):
    tans=''.join(ans[p])
    print(tans)
n = input()
n1 = list(input())
n1 = [int(x) for x in n]

num =0
for i in range(len(n1)):
  num += int(n1[i])

if int(n)%num == 0:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

n = str(input())
wa = ""
for i in n:
  wa += "+"+i

if int(n)%(eval(wa)) == 0:
  print("Yes")
else:
  print("No")
N = input()
Sum = 0

for k in range(N):
    i = k+1

    if i % 3 != 0:
        if i % 5 != 0:
            Sum = Sum + i

print(Sum)

### FIXED CODE ###

N = input()
Sum = 0

for k in range(int(N)):
    i = k+1

    if i % 3 != 0:
        if i % 5 != 0:
            Sum = Sum + i

print(Sum)
from collections import deque
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]


def bfs(i, j):  # 引数はスタートの位置(i, j)
    q = deque()
    q.append((i, j))
    log = [[-1] * w for _ in range(h)]
    log[i][j] = 0
    distance = 0
    d = [(1, 0), (0, 1), (-1, 0), (0, -1)]  # 右、上、左、下
    while q:
        p = q.popleft()
        for item in d:
            nx = p[0] + item[0]
            ny = p[1] + item[1]
            if not(0 <= nx < h and 0 <= ny < w):  # 迷路の外にはでれない
                continue
            elif s[nx][ny] == "#":  # 壁には進めない
                continue
            elif log[nx][ny] >= 0:  # 探索済みは探索しない
                continue
            else:
                log[nx][ny] = log[p[0]][p[1]] + 1
                q.append((nx, ny))
                if distance < log[nx][ny]:
                    distance = log[nx][ny]
    return distance


distance = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == "#":  # start地点は壁でない
            continue
        else:
            temp = bfs(i, j)
            if temp >= distance:
                distance = temp
print(distance)

### FIXED CODE ###

a = input()
al = "abcdefjhijklmopqrstuvwxyz"
for i in range(24):
    if a == al[i]:
        print(al[i+1])
n = int(input())
a = list(map(int, input().split(' ')))
q = int(input())
M = list(map(int, input().split(' ')))
S = [0 for i in range(n)]

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 j in M:
    if solve(0, j):
        print('yes')
    else:
        print('no')



### FIXED CODE ###

n = int(input())
a = list(map(int, input().split(' ')))
q = int(input())
M = list(map(int, input().split(' ')))
minA = min(a)
sumA = 0
for i in a:
    sumA += i


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 j in M:
    if j < minA or j > sumA:
        print('no')
    else:
        if solve(0, j):
            print('yes')
        else:
            print('no')
import math

a, b = map(int, input().split())

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

print(lcm(a, b))


### FIXED CODE ###

from fractions import gcd
a, b = map(int, input().split())

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

print(lcm(a, b))
N,X,M = map(int,input().split())
R = [X]
m = min(X,M)
for i in range(m):
    r = R[-1]
    r = r**2%M
    if r in R:
        break
    R.append(r)
for i in range(len(R)):
    if r == R[i]:
        break
a = 0
b = sum(R)
for j in range(i):
    a += R[j]
    b -= R[j]
n = len(R) - i
t = N - i
p = t // n
q = t % n
c = 0
for j in range(q):
    c += R[i+j]
ans = a + b*p + c
print(ans)

### FIXED CODE ###

N,X,M = map(int,input().split())
R = [X]
dr = {}
for i in range(M):
    dr[i] = 0
m = min(N,M)
for i in range(m):
    r = R[-1]
    r = r**2%M
    if dr[r] == 1:
        break
    R.append(r)
    dr[r] = 1
for i in range(len(R)):
    if r == R[i]:
        break
a = 0
b = sum(R)
for j in range(i):
    a += R[j]
    b -= R[j]
n = len(R) - i
t = N - i
p = t // n
q = t % n
c = 0
for j in range(q):
    c += R[i+j]
ans = a + b*p + c
print(ans)
import numpy as np
import sys
input = sys.stdin.readline
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N,M,Q = IL()
cnt = np.zeros((N+1,N+1))

for i in range(M):
    a,b = IL()
    cnt[:a+1,b:] += 1

for i in range(Q):
    c,d = IL()
    print(int(cnt[c][d]))

### FIXED CODE ###

import numpy as np
import sys
input = sys.stdin.readline
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def imos():
  for j in range(N+1):
    cnt = 0
    for i in range(N+1):
      tmp = l[j][i]
      l[j][i] += cnt
      cnt += tmp

  for j in range(N+1):
    cnt = 0
    for i in range(N+1):
      tmp = l[i][j]
      l[i][j] += cnt
      cnt += tmp

N,M,Q = IL()
l = [[0]*(N+1) for i in range(N+1)]
for i in range(M):
  a,b = IL()
  l[1][b] += 1
  if a+1 <= N:
    l[a+1][b] += -1

imos()

ans = [IL() for i in range(Q)]
for i in range(Q):
    print(l[ans[i][0]][ans[i][1]])
n =input()


def judge(x):
  
  if x % 2019 == 0:
    return(1)
  else:
    return(0)

a = 0
for i in range(1,len(n)):
  for j in range(i, len(n)):
    s = n[i:j]
    d = int("s")
    a = a + judge(d)
    
print(a)
    

### FIXED CODE ###

S = [int(a) for a in input()[::-1]]
m = 2019
N = len(S)
s = 0
p = 1
X = [0] * 2019
X[0] = 1
ans = 0
for a in S:
    s = (s + a * p) % m
    ans += X[s]
    X[s] += 1
    p = p * 10 % m
 
print(ans)
n = int(input())
s = list(input())

dp = [[0] * n for _ in range(n)]
for i in range(n-1, -1, -1):
    for j in range(n-1, -1, -1):
        if s[i] == s[j]:
            if j+1 <= n-1 and i+1 <= n-1:
                dp[i][j] = dp[i+1][j+1] + 1
            else:
                dp[i][j] = 1
                
for i in range(n):
    for j in range(n):
        dp[i][j] = min(abs(i-j), dp[i][j])

ans = 0
for i in range(n):
    ans = max(ans, max(dp[i]))
print(ans)

### FIXED CODE ###

a = input()
if a == 'Sunny':
    ans = 'Cloudy'
elif a == 'Cloudy':
    ans = 'Rainy'
else:
    ans = 'Sunny'

print(ans)
aaaa

### FIXED CODE ###

x = int(input())
if (x >= 30):
    print('Yes')
else:
    print('No')
s = input()
k = int(input())

if s[0]!='1':
    ans = int(s[0])
else:
    for i in range(min(k,len(s))):
        if s[i]!='1':
            ans = int(s[i])
            break
            
print(ans)

### FIXED CODE ###

s = input()
k = int(input())

ans = 1
for i in range(min(k,len(s))):
    if s[i]!='1':
        ans = int(s[i])
        break
            
print(ans)
A,B=Imput()
print(int(A)-int(B)*2)


### FIXED CODE ###

A,B=input().split()
ans=int(A)-int(B)*2
if ans > 0:
  print(ans)
else:
  print(0)
from itertools import groupby
from heapq import heapify, heappop

N, K = map(int, input().split())
sushi = [tuple(map(int, input().split())) for _ in range(N)]

srt = sorted(sushi, key=lambda x: x[1], reverse=True)
eat, non_eat = srt[:K], srt[K:]

maxs = []
rems = []
kinds = set()
for k, g in groupby(sorted(eat, key=lambda x: x[0]), key=lambda x: x[0]):
    d = list(list(zip(*g))[1])
    maxs.append(d.pop(0))
    rems.extend(d)
    kinds.add(k)
heapify(rems)
ans = sum(maxs) + sum(rems) + len(kinds)**2

for k, g in groupby(sorted(non_eat, key=lambda x: x[0]), key=lambda x: x[0]):
    if k in kinds:
        continue
    d = list(list(zip(*g))[1])
    maxs.append(d.pop(0))
    heappop(rems)
    kinds.add(k)
    ans = max(ans, sum(maxs) + sum(rems) + len(kinds)**2)

print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
sushi = [list(map(int, input().split())) for _ in range(N)]
sushi.sort(key=lambda x: x[1], reverse=True)

score = 0

remains = []
kinds = set()
for t, d in sushi[:K]:
    if t in kinds:
        remains.append(d)
    kinds.add(t)
    score += d
score += len(kinds)**2

test = score
for t, d in sushi[K:]:
    if not remains:
        break
    if t in kinds:
        continue
    kinds.add(t)
    rm = remains.pop()
    test = test + (d - rm) + (len(kinds)*2 - 1)
    score = max(score, test)

print(score)
h, w = map(int, input().split())
s = []
l = []
r = []
u = []
d = []
for i in range(h):
  s.append(input())
  l.append([0 for j in range(w)])
  r.append([0 for j in range(w)])
  u.append([0 for j in range(w)])
  d.append([0 for j in range(w)])
  
# lみる
for x in range(w):
  for y in range(h):
    if s[y][x] == '.':
      if x == 0:
        l[y][x] = 1
      else:
        l[y][x] = l[y][x-1] + 1
 
# rみる
for x in range(w):
  for y in range(h):
    if s[h-1-y][w-1-x] == '.':
      if x == w-1:
        l[y][x] = 1
      else:
        l[y][x] = l[y][x+1] + 1
 
# uみる
for x in range(w):
  for y in range(h):
    if s[y][x] == '.':
      if y == 0:
        l[y][x] = 1
      else:
        l[y][x] = l[y-1][x] + 1

# dみる
for x in range(w):
  for y in range(h):
    if s[h-1-y][w-1-x] == '.':
      if y == h-1:
        l[y][x] = 1
      else:
        l[y][x] = l[y+1][x] + 1
 

max_all = 0
for y in range(h):
  for x in range(w):
  max_tmp = l[y][x] + r[y][x] + u[y][x] + d[y][x]
  if max_tmp > max_all:
    max_all = max_tmp
print(max_all - 3)

### FIXED CODE ###

h, w = map(int, input().split())
s = []
l = []
r = []
u = []
d = []
for i in range(h):
  s.append(input())
  l.append([0 for j in range(w)])
  r.append([0 for j in range(w)])
  u.append([0 for j in range(w)])
  d.append([0 for j in range(w)])
  
# lみる
for x in range(w):
  for y in range(h):
    if s[y][x] == '.':
      if x == 0:
        l[y][x] = 1
      else:
        l[y][x] = l[y][x-1] + 1
 
# rみる
for x in range(w-1, -1, -1):
  for y in range(h-1, -1, -1):
    if s[y][x] == '.':
      if x == w-1:
        r[y][x] = 1
      else:
        r[y][x] = r[y][x+1] + 1
 
# uみる
for y in range(h):
  for x in range(w):
    if s[y][x] == '.':
      if y == 0:
        u[y][x] = 1
      else:
        u[y][x] = u[y-1][x] + 1
 
# dみる
for y in range(h-1, -1, -1):
  for x in range(w-1, -1, -1):
    if s[y][x] == '.':
      if y == h-1:
        d[y][x] = 1
      else:
        d[y][x] = d[y+1][x] + 1
 
 
max_all = 0
for y in range(h):
  for x in range(w):
    max_tmp = l[y][x] + r[y][x] + u[y][x] + d[y][x]
    if max_tmp > max_all:
      max_all = max_tmp
      
print(max_all - 3)
#!/usr/bin/env python
# -*- coding:utf-8 -*-


obj = input().strip().split(' ')
N, K, Q = map(int, obj)

winner_list = []
for _ in range(Q):
    A_i = int(input().strip())
    winner_list.append(A_i)

point_list = [K for _ in range(N)]

for A_i in winner_list:
    point_list = [k if i == A_i else k - 1 for i in range(1, N + 1)]

is_win = [True if point_list[i] > 0 else False for i in range(N) ]

for i in range(N):
    if is_win[i]:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

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


S = input().strip()

if S == 'Sunny':
    print('Cloudy')

if S == 'Cloudy':
    print('Rainy')

if S == 'Rainy':
    print('Sunny')
class Queue:
    def __init__(self):
        self.items = []

    def enqueue(self, item):
        self.items.insert(0, item)

    def dequeue(self):
        return self.items.pop()

    def size(self):
        return len(self.items)

    def self(self):
        return self.items

s = raw_input()
t = raw_input()
q = Queue()

j = 0
S = list(s)
L = len(s)
while j < L :
    q.enqueue(S[L - (j + 1)])
    j += 1

flag = False
i = 0
while i < q.size():
    x = q.dequeue()
    q.enqueue(x)
    if (list(t) == q.self()):
        flag = True
        break
    i += 1

if flag:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

a, b, c = map(int, raw_input().split())
list = [a, b, c]
list.sort()
cost = (list[2] - list[1]) + (list[1] - list[0])
print(cost)
from math import gcd


def main():
    N, M = list(map(int, input().split(' ')))
    half_A = list(map(lambda x: int(x) // 2, input().split(' ')))
    lcm = 1
    for half_a in half_A:
        lcm *= half_a // gcd(lcm, half_a)
        if lcm > M:
            print(0)
            exit(0)
    for half_a in half_A:
        if (lcm // half_a) % 2 == 0:
            print(0)
            exit(0)
    num_multiples = M // lcm
    print((num_multiples + 1) // 2)  # count only cases that ratios are odd numbers.


if __name__ == '__main__':
    main()

### FIXED CODE ###

from fractions import gcd  # for python 3.5~, use math.gcd


def main():
    N, M = list(map(int, input().split(' ')))
    half_A = list(map(lambda x: int(x) // 2, input().split(' ')))
    lcm = 1
    for half_a in half_A:
        lcm *= half_a // gcd(lcm, half_a)
        if lcm > M:
            print(0)
            exit(0)
    for half_a in half_A:
        if (lcm // half_a) % 2 == 0:
            print(0)
            exit(0)
    num_multiples = M // lcm
    print((num_multiples + 1) // 2)  # count only cases that ratios are odd numbers.


if __name__ == '__main__':
    main()
import math
mod = 1000000007
def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=factorial(n) %p
  b=factorial(k) %p
  c=factorial(n-k) %p
  return (a*pow(b,p-2,p)*pow(c,p-2,p))%p
n,m = map(int, input().split())
def make_prime_list_2(num):
    if num < 2:
        return []

    # 0のものは素数じゃないとする
    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 prime_factorization_2(num):
    if num <= 1:
        return False
    else:
        num_sqrt = math.floor(math.sqrt(num))
        prime_list = make_prime_list_2(num_sqrt)

        dict_counter = {}
        for prime in prime_list:
            while num % prime == 0:
                if prime in dict_counter:
                    dict_counter[prime] += 1
                else:
                    dict_counter[prime] = 1
                num //= prime
        if num != 1:
            if num in dict_counter:
                dict_counter[num] += 1
            else:
                dict_counter[num] = 1

        return dict_counter
x = prime_factorization_2(m)
x = list(x.values())
ans = 1
for i in x:
  ans*= comb(i+n-1,i,mod)
  ans %=mod
print(ans)

### FIXED CODE ###

import math
n,m = map(int, input().split())
mod = 1000000007
fact = [1]*(n+10000+1)
rfact = [1]*(n+10000+1)
for i in range(n+10000):
    fact[i+1] = rr = ((i+1) * fact[i]) % mod
    rfact[i+1] = pow(rr, mod-2, mod)
def comb(N, K,mod):
    return fact[N] * rfact[K] * rfact[N-K] % mod
def make_prime_list_2(num):
    if num < 2:
        return []

    # 0のものは素数じゃないとする
    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 prime_factorization_2(num):
    if num <= 1:
        print(1)
        exit()
        return False
    else:
        num_sqrt = math.floor(math.sqrt(num))
        prime_list = make_prime_list_2(num_sqrt)

        dict_counter = {}
        for prime in prime_list:
            while num % prime == 0:
                if prime in dict_counter:
                    dict_counter[prime] += 1
                else:
                    dict_counter[prime] = 1
                num //= prime
        if num != 1:
            if num in dict_counter:
                dict_counter[num] += 1
            else:
                dict_counter[num] = 1

        return dict_counter
x = prime_factorization_2(m)
x = list(x.values())
ans = 1
for i in x:
  ans*= comb(i+n-1,i,mod)
  ans %=mod
print(ans)