Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

def main():
    def gcd(v1, v2):
        # if v2 == 0:
        #     return v1
        # return gcd(v2, v1%v2)
        
        while v2 > 0:
            tmp = v1
            v1 = v2
            v2 = tmp%v1
        return v1


    N = int(input())
    a_list = list(map(int, input().split()))

    MOD = 10**9 + 7

    a_lcm = a_list[0]
    for a in a_list[1:]:
        a_lcm *= a // gcd(a_lcm, a)

    res = 0
    for a in a_list:
        res = (res + a_lcm // a) % MOD
    print(res)

if __name__ == "__main__":
    main()


### FIXED CODE ###


from fractions import gcd
def main():

    N = int(input())
    a_list = list(map(int, input().split()))

    MOD = 10**9 + 7

    a_lcm = a_list[0]
    for a in a_list[1:]:
        a_lcm *= a // gcd(a,a_lcm)

    res = 0
    for a in a_list:
        res += a_lcm // a
    print(res%MOD)

if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n = int(input()) #odd
p = list(map(float,input().split()))

#dp[i][j] = i枚まで投げた時の表がj枚出た時の確率。

dp = [[0]*(n+1)for i in range(n+1)]
dp[0][0] = 1
dp[1][0] = 1-p[0]
for i in range(1,n):
    dp[i+1][0] =  dp[i][0] *(1-p[i]) 


for i in range(n):
    for j in range(n):
        dp[i+1][j+1] =  dp[i][j+1] * (1-p[i]) + dp[i][j] * p[i]

ans = 0

for i in range(n//2+1,n+1):
    ans += dp[n][i] 

print(ans)

### FIXED CODE ###

n = int(input())#奇数
p = [0] + list(map(float,input().split()))
ans = 0
#dp[i][j] = i番目までのコインで表がj枚になる確率
'''dp[i][j] = dp[i-1][j-1]*p[i] + dp[i-1][j]*(1-p[i])
ans = dp[n][n//2+1]+...+dp[n][n]
'''
dp = [[0]*(n+1) for i in range(n+1)]
dp[0][0] = 1
for i in range(1,n+1):
  dp[i][0] = dp[i-1][0]*(1-p[i])
for i in range(1,n+1):
  for j in range(1,i+1):
    dp[i][j] = dp[i-1][j-1]*p[i] + dp[i-1][j]*(1-p[i])
for j in range(n//2+1,n+1):
  ans += dp[n][j]
print(ans)
### BUGGY CODE ###

def func(n):
  if n==1:return 1
  if n==0:return 1
  if dp[n]!=-1:return dp[n]
  f1=func(n-1) if n-1 not in a else 0
  f2=func(n-2) if n-2 not in a else 0
  tmp=(f1+f2)%1000000007
  dp[n]=tmp
  return tmp
import sys
sys.setrecursionlimit(1000000)
n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
dp=[-1]*(n+1)
print(func(n)%1000000007)

### FIXED CODE ###

def func(n):
  if n==1:return 1
  if n==0:return 1
  if dp[n]!=-1:return dp[n]
  f1=func(n-1) if n-1 not in a else 0
  f2=func(n-2) if n-2 not in a else 0
  tmp=(f1+f2)%1000000007
  dp[n]=tmp
  return tmp
import sys
sys.setrecursionlimit(1000000)
n,m=map(int,input().split())
a={int(input()) for i in range(m)}
dp=[-1]*(n+1)
print(func(n)%1000000007)
### BUGGY CODE ###

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

for i in range(a,b+1):
    if i<a+x or i>b-x:
        print(i)

### FIXED CODE ###

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

if b-a+1<=2*k:
    for i in range(a,b+1):
        print(i)
    exit()

else:
    for i in range(a,a+k):
        print(i)
    for j in range(b-k+1,b+1):
        print(j)
### BUGGY CODE ###

import queue
import sys
sys.setrecursionlimit(10**7)
n = int(input())

abc = [[] for i in range(n+1)]

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

Q,k = map(int,input().split())
xy = [[int(i) for i in input().split()] for j in range(Q)]

q = queue.Queue()

q.put(k)

path = [-1]*(n+1)
path[k] = 0

def dfs(p):
    for i in range(len(abc[p])):
        num = abc[p][i][0]
        if path[num] != -1:
            continue
        else:
            path[num] = path[p] + abc[p][i][1]
            dfs(num)

dfs(k)

for i in range(Q):
    print(path[xy[i][0]]+path[xy[i][1]])

### FIXED CODE ###

import queue
n = int(input())

abc = [[] for i in range(n+1)]

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

Q,k = map(int,input().split())
xy = [[int(i) for i in input().split()] for j in range(Q)]

q = queue.Queue()

q.put(k)

path = [-1]*(n+1)
path[k] = 0

while not q.empty():
    tmp = q.get()
    for i in range(len(abc[tmp])):
        #print(abc[tmp])
        #exit()
        num = abc[tmp][i][0]
        if path[num] != -1:
            continue
        else:
            path[num] = path[tmp] + abc[tmp][i][1]
            q.put(num)
            
for i in range(Q):
    print(path[xy[i][0]]+path[xy[i][1]])
### BUGGY CODE ###

import fractions
import sys
input = sys.stdin.readline
N = int(input())
a = tuple(map(int,input().split()))
g = 1
MOD = 10**9+7
for elem in a:
    g *= elem//fractions.gcd(g,elem)
res = 0
for elem in a:
    res += g//elem
print(res%MOD)


### FIXED CODE ###

import fractions
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int,input().split()))
g = 1
res = 0
MOD = 10**9+7
for elem in a:
    tmp = g*elem//fractions.gcd(g,elem)
    res *= tmp//g
    g = tmp
    res += g//elem
print(res%MOD)
### BUGGY CODE ###

import itertools as it
N=input()
a_l=[int(i) for i in input().split()]

sum1=0
for (i,j) in it.combinations(a_l, 2):
        sum1+=i^j
print(sum1%(7+10**9))

### FIXED CODE ###

n=int(input())
lis=list(map(lambda x:format(int(x),'b'),input().split()))
l=0
for i in range(n):
    l=max(l,len(lis[i]))

d0=[0]*60
d1=[0]*60

for i in range(n):
    lis[i]=lis[i].zfill(l)
    for j in range(l):
        if lis[i][-j-1]=='0':
            d0[j]+=1
        else:
            d1[j]+=1

ans=0
for i in range(60):
    ans+=(d0[i]*d1[i]*2**i)%(10**9+7)
print(ans%(10**9+7))
### BUGGY CODE ###

from collections import defaultdict
from heapq import heappush, heappop
N, T = map(int, input().split())
dic = defaultdict(list)
ls = []
pre = []
log = [[1]*N]*T
dp = [0]*(T)
for i in range(N):
  a, b = map(int, input().split())
  ls += [(a,b)]
  if a<T:
    for j in range(T-1,a-1,-1):
      if dp[j-a]+b>dp[j]:
        dp[j] = dp[j-a]+b
        log[j] = log[j-a][:]
        log[j][i] = 0
  else:
    heappush(pre, -b)
m = 0
ind = -1
his = None
for j in range(T):
  if dp[j]>m:
    m = dp[j]
    ind = j
for c in range(N):
  if log[ind][c]:
    heappush(pre,-ls[c][1])

if pre:
  m -= heappop(pre)
print(m)

### FIXED CODE ###

N, T = map(int, input().split())
dp = [[0]*T for i in range(N+1)]

ls = []
for i in range(N):
  a, b = map(int, input().split())
  ls += [(a,b)]
ls.sort(key=lambda x:x[0])

for i in range(N):
  a, b = ls[i]
  for j in range(T-1, a-1, -1):
    dp[i+1][j] = max(dp[i][j], dp[i][j-a]+b)
    
pre = [0]*N
pre[-1] = ls[-1][1]
for i in range(N-2, -1, -1):
  pre[i] = max(pre[i+1], ls[i][1])
    
ans = 0
for i in range(N-1):
  ans = max(ans, max(dp[i+1])+pre[i+1])
ans = max(ans, max(dp[-1]))
print(ans)
### BUGGY CODE ###

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

count = 0;

def cnt_uniq(li):
    uniq = []
    for i in li:
        if i not in uniq:
            uniq.append(i)
    ret = []
    for i in uniq:
        ret.append(li.count(i))
    return ret

uniq = sorted(cnt_uniq(a))
while k < len(uniq):
    count += uniq[0]
    uniq.pop(0)

print(count)


### FIXED CODE ###

from collections import Counter
n, k = map(int, input().split())
a = list(map(int, input().split()))

def cnt_uniq(li):
    return Counter(li).values()

uniq = sorted(cnt_uniq(a), reverse = True)[k:]
print(sum(uniq))
### BUGGY CODE ###

N, M, K = map(int, input().split())
friends_table = [set() for i in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    friends_table[a-1].add(b-1)
    friends_table[b-1].add(a-1)

blocks_table = [set() for i in range(N)]
for _ in range(K):
    a, b = map(int, input().split())
    blocks_table[a-1].add(b-1)
    blocks_table[b-1].add(a-1)

group_list = [i for i in range(N)]
friends_candidate = [[] for i in range(N)]

for i in range(N):
    friend = set([i])
    # すでにDFS済み
    if i != group_list[i]:
        continue
    next_stack = list(friends_table[i])
    while next_stack:
        next = next_stack.pop()
        # 訪問済み
        if i == group_list[next]:
            continue
        friend.add(next)
        group_list[next] = i
        next_stack += list(friends_table[next])
    for f in friend:
        friends_candidate[f] = friend

for i in range(N):
    print(len(friends_candidate[i].difference(friends_table[i]|blocks_table[i]))-1)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N, M, K = map(int, input().split())
friends_table = [[] for i in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    friends_table[a-1] += [b-1]
    friends_table[b-1] += [a-1]

group_list = [i for i in range(N)]
friends_candidate = [[] for i in range(N)]

for i in range(N):
    # すでにDFS済み
    if i != group_list[i]:
        continue
    next_stack = [i]
    friend = [i]
    while next_stack:
        u = next_stack.pop(-1)
        for v in friends_table[u]:
            # 訪問済み
            if i == group_list[v]:
                continue
            friend += [v]
            group_list[v] = i
            next_stack += [v]
    for f in friend:
        friends_candidate[f] = friend

blocks_table = [[] for i in range(N)]
for _ in range(K):
    a, b = map(int, input().split())
    if group_list[a-1] == group_list[b-1]:
        blocks_table[a-1] += [b-1]
        blocks_table[b-1] += [a-1]

for i in range(N):
    print(len(friends_candidate[i]) - len(friends_table[i]) - len(blocks_table[i])-1)
### BUGGY CODE ###

from heapq import heapify, heappushpop

n, m = map(int, input().split())
alist = list(map(int, input().split()))
heapify(alist)

for _ in range(m):
  b, c = map(int, input().split())
  for _ in range(b):
    if alist[0] >= c:
      break
    else:
      heappushpop(alist, c)

print(sum(alist))


### FIXED CODE ###

n, m = map(int, input().split())
alist = list(sorted(map(int, input().split())))
bc = []
total = 0
for _ in range(m):
  bc.append(tuple(map(int, input().split())))

lim = n-1
total = 0
ans = 0
for b, c in sorted(bc, key=lambda x: -x[1]):
  while lim >= 0 and alist[lim] >= c:
    ans += alist[lim]
    lim -= 1
    total += 1
  ans += c * min(b, n-total)
  total += min(b, n-total)
  if total == n:
    break
if total == n:
  print(ans)
else:
  print(ans + sum(alist[total:]))
### BUGGY CODE ###

n,*l=map(int,open(0).read().split())
p=0,0
d=p
i=0
for l in l:d+=max(l+d[-2],[d,p][i&1][-1]),;p+=l+p[-2],;i+=1
print(d[-1])

### FIXED CODE ###

n,*l=map(int,open(0).read().split());p=[0]*n;d=p[:]
for i,l in enumerate(l):p[i]+=l+p[i-2];d[i]=max(l+d[i-2],[d,p][i&1][i-1])
print(d[-1])
### BUGGY CODE ###

n, m = map(int, input().split())
ab = []
c= []
keys = ["" for _ in range(m)]

for i in range(m):
    ab.append(list(map(int, input().split())))
    kari = list(map(int, input().split()))
    c.append(kari)
    for j in range(n):
        if j+1 in kari:
            keys[i] = keys[i]+"1"
        else:
            keys[i] = keys[i] + "0"

all_patterns = ["0","1"]
options = ["0", "1"]

for _ in range(n-1):
    all_patterns = [j+i for i in (options) for j in all_patterns]

dp_dict = dict()
for pattern in all_patterns:
    dp_dict[pattern] = 1e+10
dp_dict["0"*n] = 0

for j in range(m):
    for key in dp_dict.keys():
        kari1 = dp_dict[key]+ab[j][0]
        kari2 = dp_dict[format(int(key,2)|int(keys[j],2),"0"+str(n)+"b")]
        if kari1 < kari2:
            dp_dict[format(int(key,2)|int(keys[j],2),"0"+str(n)+"b")] = kari1

if dp_dict["1"*n] != 1e+10:
    print(dp_dict["1"*n])
else:
    print(-1)

### FIXED CODE ###


n, m = map(int, input().split())
ab = []
c= []
keys = ["" for _ in range(m)]

for i in range(m):
    ab.append(list(map(int, input().split())))
    kari = list(map(int, input().split()))
    c.append(kari)
    for j in range(n):
        if j+1 in kari:
            keys[i] = keys[i]+"1"
        else:
            keys[i] = keys[i] + "0"

all_patterns = ["0","1"]
options = ["0", "1"]

for _ in range(n-1):
    all_patterns = [j+i for i in (options) for j in all_patterns]

dp = [1e+10 for i in range(2**n)]
dp[0] = 0

#%%
for j in range(m):
    for i in range(len(dp)):
        kari1 = dp[i]+ab[j][0]
        kari2 = dp[i|int(keys[j],2)]
        if kari1 < kari2:
            dp[i|int(keys[j],2)] = kari1

if dp[-1] != 1e+10:
    print(dp[-1])
else:
    print(-1)
### BUGGY CODE ###

import numpy as np

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

MOD = 998244353

dp = np.zeros(s+1) #動的計画法を用いる
dp[0] = 1

for i in range(n):
    ddp = dp * 2
    for ss in range(s,-1,-1):
        if(ss >= a[i]):
            ddp[ss] += dp[ss-a[i]]%MOD #非常に大きな数になると考えられるため先にMOD計算を行う
    dp = ddp % MOD


print(int(dp[s]))

### FIXED CODE ###

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

MOD = 998244353

dp = [[0]*(s+1) for i in range(n+1)] #動的計画法を用いる
dp[0][0] = 1

for i in range(n):
    for ss in range(s+1):
        if(ss >= a[i]):
            dp[i+1][ss] = (dp[i][ss]*2 + dp[i][ss-a[i]])%MOD #非常に大きな数になると考えられるため先にMOD計算を行う
        else:
            dp[i+1][ss] = dp[i][ss]*2 % MOD

print(dp[n][s])
### BUGGY CODE ###

import heapq
def SME(start,end):
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        if None not in ANS[a[1]:a[1]+L] : continue
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] : continue
                else :
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in range(L):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS
[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
A = []
parameter = 0.99975
ANS = [None]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
from itertools import product#accumulate, combinations, product
#import bisect# lower_bound etc
import numpy as np
#from copy import deepcopy
#from collections import deque
def run():
    H,W,K = map(int, sysread().split())
    S = []
    for i in range(H):
        S.append(list(map(int, list(input()))))
    S = np.array(S)
    ret = float('inf')
    for w in range(1, W):
        S[:,w] += S[:,w-1]
    for h in range(1, H):
        S[h,:] += S[h-1,:]

    for idxes_ in product((0,1), repeat=H-1):
        l = 0
        r = 1
        idxes = [0]
        for i, val in enumerate(idxes_, 1):
            if val == 1:
                idxes.append(i)
        idxes.append(H)
        min_cut = len(idxes) - 2
        while r <= W:
            for i in range(len(idxes)-1):
                if idxes[i] == 0 and l == 0:
                    cri = S[idxes[i+1]-1, r-1]
                elif l == 0:
                    cri = S[idxes[i+1]-1, r-1] - S[idxes[i]-1, r-1]
                elif idxes[i] == 0:
                    cri = S[idxes[i+1]-1, r-1] - S[idxes[i+1]-1, l-1]
                else:
                    cri = S[idxes[i+1]-1, r-1] - S[idxes[i]-1, r-1] - S[idxes[i+1]-1, l-1] + S[idxes[i]-1, l-1]

                if cri > K:
                    r -= 1
                    if l == r:
                        min_cut = float('inf')
                        r = W+1
                        break
                    l = r
                    min_cut += 1
                    break
            r += 1
        ret = min(ret, min_cut)

    print(ret)




if __name__ == "__main__":
    run()


### FIXED CODE ###

# coding: utf-8
from itertools import combinations as combs

H,W,K = list(map(int, input().split()))
arr = []
for i in range(H):
  arr.append(list(map(int, list(input()))))

def cut_sum(arr, x1, x2, y):
  ret = 0
  for i in range(x1, x2):
    ret += arr[i][y]
  return ret

row_idxes = list(range(1,H))
min_val = float('inf')

for n_rows in range(H):
  for row_set in combs(row_idxes, n_rows):
    count = len(row_set)
    row_lines = [0] + list(row_set)+ [H]
    col1, col2 = 0, 1
    sums = [0] * (len(row_lines) - 1)
    while col2 <= W:
      row1 = 0
      for box, row2 in enumerate(row_lines[1:]):
        sums[box] += cut_sum(arr, row1, row2, col2-1)
        if sums[box] > K:
          if (col2 - col1) == 1:
            count = float('inf')
            break
          count += 1
          col1 = col2 - 1
          col2 -= 1
          sums = [0] * (len(row_lines) - 1)
          break
        row1 = row2
      if count >= min_val:
        break
      col2 += 1
    
    if min_val > count:
      min_val = count
print(min_val)
### BUGGY CODE ###

import numpy as np
from itertools import product

h, w, k = map(int, input().split())
s = np.array([list(map(int, input())) for _ in range(h)], dtype=np.int32)


def hsplit(pat):
    prev = 2
    ret = np.zeros((h + 1, w), dtype=np.int32)
    white = np.zeros(w, dtype=np.int32)
    cnt = 0
    for i, e in enumerate(pat):
        if e == prev:
            white += s[i]
        else:
            ret[cnt] = white.copy()
            white = s[i].copy()
            cnt += 1

        prev = e

    ret[cnt] = white.copy()
    cnt += 1

    return ret[1:cnt]


def greedy(arr):
    acc = np.zeros_like(arr, dtype=np.int32)
    ww = arr.shape[1]
    cnt = 0
    for i in range(ww):
        if i == 0:
            acc[:, i] = arr[:, i]
        else:
            acc[:, i] = acc[:, i-1] + arr[:, i]

        if acc[:, i].max() > k:
            cnt += 1
            acc[:, i] = arr[:, i]

    return cnt


ans = float("inf")
for pat in product([0, 1], repeat=h):
    if pat[0]:
        break

    hsp = hsplit(pat)

    if hsp.max() > k:
        continue

    wsp_cnt = greedy(hsp)
    hsp_cnt = hsp.shape[0] - 1

    cnt = hsp_cnt + wsp_cnt
    ans = min(ans, cnt)

print(ans)


### FIXED CODE ###

from itertools import product

h, w, k = map(int, input().split())
s = [list(map(int, input())) for _ in range(h)]

ans = float("inf")
for pat in product([1, 0], repeat=h):
    prev = 2
    sm = -1
    for e in pat:
        if e != prev:
            sm += 1
        prev = e
    #print(pat)
    #print(sm)

    ss = [[0] * w for _ in range(h)]
    for wi in range(w):
        acc = 0
        prev = 2
        for hi, e in enumerate(pat):
            if e != prev:
                acc = 0
            if s[hi][wi]:
                acc += 1
            ss[hi][wi] = acc
            prev = e

    sss = [[0] * w for _ in range(h)]
    for hi in range(h):
        for wi in range(w):
            if wi == 0:
                sss[hi][wi] = ss[hi][wi]
            else:
                sss[hi][wi] = sss[hi][wi-1] + ss[hi][wi]

    base = [0] * h
    cp_prev = [0] * h
    for wi in range(w):
        mx = 0
        cp = [0] * h
        for hi in range(h):
            mx = max(mx, sss[hi][wi] - base[hi])
            cp[hi] = sss[hi][wi]
        if mx > k:
            if wi == 0:
                sm = 10000
            sm += 1
            base = cp_prev
        cp_prev = cp

    ans = min(ans, sm)

print(ans)
### BUGGY CODE ###

n,m = list(map(int,input().split()))
a = []
b = []
for i in range(n):
    x,y = list(map(int,input().split()))
    a.append(x)
    b.append(y)
count = 0

while m > 0:
    if m - b[a.index(min(a))] > 0 : # Bi本買う
        m = m-b[a.index(min(a))]
        count += b[a.index(min(a))] * min(a)
    else:
        count += m * min(a)
        break
    d = a.index(min(a))
    del a[d]
    del b[d]

print(count)




### FIXED CODE ###

n,m = list(map(int,input().split()))
a = []
b = []
dic = {}
count = 0
data = [0] * n
for i in range(n):
    x,y = list(map(int,input().split()))
    data[i] = [x,y]
data = sorted(data,key = lambda x : x[0])
for i in range(n):
    if m > data[i][1]:
        count += data[i][0] * data[i][1]
        m -= data[i][1]
    else:
        count += data[i][0] * m
        break
print(count)

"""
for i in range(n):
    x,y = list(map(int,input().split()))
    dic[x] = y
dic = sorted(dic.items())



for key in dic:
    if m - dic[key] > 0:
        count += key * dic[key]
        m = m - dic[key]
    else:
        count += m * key
        break
print(count)
"""
            

"""

for i in range(n):
    x,y = list(map(int,input().split()))
    a.append(x)
    b.append(y)
count = 0


while m > 0:
    mi = min(a)
    d = a.index(mi)
    if m > b[d]  : # Bi本買う
        m -= b[d]
        count += b[d] * mi
    else:
        count += m * mi
        break
    del a[d]
    del b[d]
print(count)



"""
### BUGGY CODE ###

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

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


N, M = [int(_) for _ in input().split()]
S = input()
T = input()

L = lcm(N, M)


X = ['_' for i in range(L)]

j = 0
for i in range(L):
    if i % (L // N) == 0:
        X[i] = S[j]
        j += 1

j = 0
for i in range(L):
    if i % (L // M) == 0:
        if X[i] != '_' and X[i] != T[j]:
            print("-1")
            exit()
        X[i] = T[j]
        j += 1

print(L)


### FIXED CODE ###

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

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


N, M = [int(_) for _ in input().split()]
S = input()
T = input()

L = lcm(N, M)
D = lcm(L // M, L // N)

for i in range(0, L, D):
    if S[i // (L // N)] != T[i // (L // M)]:
        print("-1")
        exit()
else:
    print(L)
### BUGGY CODE ###

import bisect
from collections import Counter
from itertools import combinations
from math import factorial
n, a = list(map(int, input().split()))
xs = list(map(lambda x: int(x) - a, input().split()))

xs.sort()
l, r = bisect.bisect_left(xs, 0), bisect.bisect_right(xs, 0)
low, zeros, high = xs[:l], xs[l:r], xs[r:]

factor = 2 ** len(zeros)
lsums = sum((Counter(map(sum, combinations(low, 1 + i))) for i in range(len(low))), Counter())
hsums = sum((Counter(map(sum, combinations(high, 1 + i))) for i in range(len(high))), Counter())

ans = 0
for lsum, cnt in lsums.items():
    ans += cnt * hsums[-lsum]
ans *= factor
if len(zeros):
    ans += (2 ** len(zeros) - 1)

print(ans)

### FIXED CODE ###

import bisect
from collections import Counter, deque
from itertools import combinations, accumulate
from math import factorial
from operator import neg
n, a = list(map(int, input().split()))
xs = list(map(lambda x: int(x) - a, input().split()))

xs.sort()
l, r = bisect.bisect_left(xs, 0), bisect.bisect_right(xs, 0)
low, n0, high = list(map(neg, xs[:l][::-1])), r - l, xs[r:]

def sums(arr):
    cntr = Counter([0])
    for v in arr:
        tmps = tuple(cntr.items())
        for u, cnt in tmps:
            cntr[u + v] += cnt
    del cntr[0]
    return cntr

lsums = sums(low)
hsums = sums(high)

ans = sum(hsums[a] * b for a, b in lsums.items())

ans *= 2 ** n0
ans += 2 ** n0 - 1

print(ans)