Harryxun/stf_run huggingface dataset:
def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def ilen(it):
    return sum(1 for _ in it)


def solve():
    """
    C[N-K+1][i]*C[K-1][i-1]
    1 1 1
    1 2 3
    1 3 6
    """
    N, K = read_ints()
    C = [
        [0 for _ in range(2001)] for _ in range(2001)
    ]
    modulo = 10**9+7
    C[1][1] = 1
    for i in range(2, 2001):
        for j in range(1, i+1):
            C[i][j] = (C[i-1][j]+C[i-1][j-1])%modulo

    for i in range(1, K+1):
        print((C[N-K+1+1][i+1]*C[K-1+1][i-1+1])%modulo)


if __name__ == '__main__':
    solve()


### FIXED CODE ###



def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def ilen(it):
    return sum(1 for _ in it)


def solve():
    """
    C[N-K+1][i]*C[K-1][i-1]
    1 1 1
    1 2 3
    1 3 6
    """
    N, K = read_ints()
    C = [
        [0 for _ in range(2002)] for _ in range(2002)
    ]
    modulo = 10**9+7
    C[1][1] = 1
    for i in range(2, 2002):
        for j in range(1, i+1):
            C[i][j] = (C[i-1][j]+C[i-1][j-1])%modulo

    for i in range(1, K+1):
        print((C[N-K+1+1][i+1]*C[K-1+1][i-1+1])%modulo)


if __name__ == '__main__':
    solve()
n = int(input())

for i in range(n):
  t,x,y = map(int,input().split())
  if (x + y) > t or (x + y + t) % 2:
    print("No")
    exit()
  print("Yes")

### FIXED CODE ###

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


A = a*b % 2

if A==0:
    print("Even")

else:
    print("Odd")
import math
 
a = int(input())
b = int(input())
print(math.ceil((b-1) / (a-1)))
 

### FIXED CODE ###

import math
A, B = list(map(int, input().split()))
print(math.ceil((B-1)/(A-1)))
def make_guide():
    num: int = int(input())
    lst = [(i, input().split()) for i in range(num)]
    print(lst[0])
    lst = sorted(sorted(lst, key=lambda t: t[1][1]), key=lambda t: t[1][0])
    return lst
 
if __name__ == "__main__":
    display()

### FIXED CODE ###

def make_guide():
    num = int(input())
    lst = [(i + 1, input().split()) for i in range(num)]
    # TODO fix
    # 同じものが存在したら、っていう条件のもとでないとダメ
    # あと数字は降順
    lst = sorted(lst, key=lambda t: int(t[1][1]), reverse=True)
    lst = sorted(lst, key=lambda t: t[1][0])
    return lst


def test_display():
    lst = make_guide()
    for i, guides in lst:
        print(str(i) + " " + guides[0] + " " + guides[1])


def display():
    lst = make_guide()
    for i, guides in lst:
        print(i)


if __name__ == "__main__":
    display()
n = int(input())
a = list(map(int, input().split()))
b = [0 for _ in range(len(a) + 1)]
for i in range(len(a)):
    ri = len(a) - i
    if sum(b[::ri]) % 2 != a[ri - 1]:
        b[ri] = a[ri - 1]
b = b[1:]
print(len(str(b).split("1"))-1)
for i in range(len(b)):
    if b[i]:
        print(i + 1, end="")
        print(" ", end="")

### FIXED CODE ###

print(3 * (int(input()) ** 2))
import numpy as np
N = int(input())
L = list(map(int, input().split()))
L = np.array(L)

ans = L.prod()
if (ans > pow(10,18)):
    print(-1)
else:
    print(ans)

### FIXED CODE ###

A, B = map(int,input().split())
print(A*B)
s=input()
if s=="RRR":
	print(3)
elif s=="RRS" or s=="SRR":
	print(2)
elif s=="SSR" or s=="SRS" or s=="RSS" or s=="RSR:
	print(1)
else:
	print(0)

### FIXED CODE ###

s=input()
if s=="RRR":
	print(3)
elif s=="RRS" or s=="SRR":
	print(2)
elif s=="SSR" or s=="SRS" or s=="RSS" or s=="RSR":
	print(1)
else:
	print(0)
#!/usr/bin/env python3


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

A = sorted(A)[::-1]
total = sum(A)
print(A[M-1])
if A[M] < total * (1 / (4 * M)):
    print('No')
else:
    print('Yes')


### FIXED CODE ###

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

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


A = sorted(A)[::-1]
total = sum(A)
thre = total * (1 / (4*M))
if A[M-1] < thre:
    print('No')
else:
    print('Yes')
import Counter
n=int(input())
a=[int(input()) for i in range(n)]
c=Counter(a).most_common()
ans=0
for v in c:
  if v[1]%2==1:
    ans+=1
print(ans)

### FIXED CODE ###

from collections import Counter
n=int(input())
a=[int(input()) for i in range(n)]
c=Counter(a).most_common()
ans=0
for v in c:
  if v[1]%2==1:
    ans+=1
print(ans)
def calc(N, h, n):
    base = 4/N - 1/h - 1/n
    if base == 0:
        return False, 0
    ret = 1/base
    return ret == int(ret) and 0 <= ret <= 3500, int(ret)

N = int(input())

def f(N):
    for h in range(1, 3501):
        for n in range(1, 3501):
            judge, ret = calc(N,h,n)
            if judge:
                return h, n, ret

print(*f(N))


### FIXED CODE ###

def calc(N, h, n):
    base = 4 * h * n - N * n - N * h
    if base <= 0:
        return False, -1
    ret = (N*h*n) / base
    return ret == int(ret) and 0 <= ret <= 3500, int(ret)

N = int(input())

def f(N):
    for h in range(1, 3501):
        for n in range(1, 3501):
            judge, ret = calc(N,h,n)
            if judge:
                return h, n, ret
    return -1, -1, -1

print(*f(N))
n = input().split()

n = n.split()
n = [int(i) for i in n]
if(n[0] < n[1] and n[1] < n[2]):
    print("Yes")
else:
    print("No")


### FIXED CODE ###

n = input().split()
n = [int(i) for i in n]
if(n[0] < n[1] and n[1] < n[2]):
    print("Yes")
else:
    print("No")
#coding:utf-8
n = input()
s = 0

for i in range(0, n):
    s += int(n[i])

if int(n) % s == 0:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

#coding:utf-8
n = input()
s = 0

for i in range(0, len(n)):
    s += int(n[i])

if int(n) % s == 0:
    print('Yes')
else:
    print('No')
import fractions
N = int(input())
T = [int(input()) for i in range(N)]
T = list(set(T))
pro = T[0]
for i in range(1,len(T)):
    gcd = fractions.gcd(pro,T[i])
    lcm = (pro * T[i]) // gcd
    pro = lcm
print(lcm)

### FIXED CODE ###

from functools import reduce
from fractions import gcd
N = int(input())
T = [int(input()) for i in range(N)]
def lcm(x,y):
    return (x * y) // gcd(x,y)
ans = reduce(lcm,T)
print(ans)
import math

N = int(input())
lis_all = []
lis_pat = []
lis_num = []

def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

count = 0
for i in range(N):
    lis_S = list(str(input()))
    lis_S.sort()
    if lis_S not in lis_all:
        lis_pat.append(lis_S)
    lis_all.append(lis_S)

ans = 0
for i in lis_pat:
    lis_num.append(lis_all.count(i))
    if lis_all.count(i) != 1:
        ans += math.factorial(lis_all.count(i))/2        
   
print(int(ans))

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
N=int(input())
dic={}
sum=0
for i in range(N):
    s=list(input())
    s.sort()
    s = "".join(s)
    if s in dic:
        sum+=dic[s]
        dic[s]+=1
    else:
        dic[s]=1
print(sum)
[n,m] = [int(i) for i in input().split()]
ab = []
dic = {}
for i in range(m):
  ab.append([int(i) for i in input().split()])

for i in range(m):
  if ab[i][0] in dic.keys():
	  dic[ab[i][0]] += 1
  else:
    dic[ab[i][0]] = 1
    
  if  ab[i][1] in dic.keys():
	  dic[ab[i][1]] += 1
  else:
    dic[ab[i][1]] = 1
    
for i in range(n):
  print(dic[i+1])
    

### FIXED CODE ###

[n,m] = [int(i) for i in input().split()]
ab = []
dic = {}
for i in range(m):
  ab.append([int(j) for j in input().split()])

for i in range(m):
  if ab[i][0] in dic.keys():
    dic[ab[i][0]] += 1
  else:
    dic[ab[i][0]] = 1
    
  if  ab[i][1] in dic.keys():
    dic[ab[i][1]] += 1
  else:
    dic[ab[i][1]] = 1
    
for i in range(n):
  if i+1 in dic.keys():
    print(dic[i+1])
  else:
    print(0)
import fractions
lst=list(int(input()) for _ in range(int(input())))
ans = lst[0]
for i in range(1, N):
    ans = ans * a[i] // fractions.gcd(ans, lst[i])
print(ans)


### FIXED CODE ###

import fractions
n=int(input())
lst=list(int(input()) for _ in range(n))
ans = lst[0]
for i in range(1, n):
    ans = ans * lst[i] // fractions.gcd(ans, lst[i])
print(ans)
import numpy as np

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

for _ in range(min(K,100)):
    imos = np.zeros(N+1,int)
    for i in range(N):
        l, r = max(i-A[i],0), min(i+A[i],N-1)
        imos[l] += 1
        imos[r+1] += -1
    
    A = np.cumsum(imos)[:N]

print(' '.join(A.astype(str)))



### FIXED CODE ###

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

for _ in range(K):
    flag = True
    for a in A:
        if a != N: flag = False
    if flag: break

    imos = [0] * (N+1)
    for i in range(N):
        l = max(i-A[i],0)
        r = min(i+A[i],N-1)
        imos[l] += 1
        imos[r+1] += -1
    
    for i in range(N):
        imos[i+1] += imos[i]
    
    A = imos[:N]

for a in A[:N]:
    print(a, end=" ")
print()
n,m = map(int, input().split())
a = list(map(int, input().split()))
bc = [list(map(int, input().split())) for _ in range(m)]

a.sort()
bc.sort(reverse=True, key=lambda x:x[1])
i = 0
ans = 0
for b, c in bc:
    for _ in range(b):
        if a[i] < c:
            ans += c
            i += 1
        else: break
print(ans + sum(a[i:]))

### FIXED CODE ###

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

ans = []
for b,c in BC:
  n = len(ans)
  for i in range(b):
    if n >  N-1: break
    if A[n] < c:
      ans.append(c)
      n += 1
    else: break

print(sum(ans) + sum(A[len(ans):]))
n=int(input())
r=n-1
for i in range(int(n**0.5)+1):
    if (n%i==0):
        s=(n//i)+i-2
        if s<r:
            r=s
print(r)


### FIXED CODE ###

n=int(input())
r=n-1
for i in range(1,int(n**0.5)+1):
    if (n%i==0):
        s=(n//i)+i-2
        if s<r:
            r=s
print(r)
N,M,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
time = 0
i = 0
j = 0
count = 0
while time <= K:
    if i ==len(A) and j == len(B):
        break
    elif i >= len(A):
        for s in range(j,len(B)):
            time +=B[s]
            if time <= K:
                count +=1
    elif j >= len(B):
        for t in range(i,len(A)):
            time +=B[t]
            if time <=K:
                count += 1
    elif A[i] > B[j]:
        time += B[j]
        j += 1
        if time <= K:
            count += 1
    elif B[j]>=A[i]:
        time += A[i]
        i += 1
        if time <= K:
            count += 1
print(count)

### FIXED CODE ###

N,M,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
a = [0]
b = [0]
ans = 0
max_num = 0
j = M
for i in range(N):
    a.append(a[i]+A[i])
for i in range(M):
    b.append(b[i]+B[i])
for i in range(N+1):
    if a[i] > K:
        break
    else:
        while b[j] > K - a[i]:
            j -=1
            if j <0:
                break
    if K>= a[i] + b[j]:
        ans = max(ans,i + j)
print(ans)
n=input()
result=''
for i in n:
    if i=='1':
        result.append('9')
    else:
        result.append('1')
    print(result)

### FIXED CODE ###

n=input()
result=''
for i in n:
    if i=='1':
        result+='9'
    else:
        result+='1'
print(result)
import bisect
n = int(input())
k = int(input())
array = list(map(int,input().strip().split()))
array.sort()
index = bisect.bisect_left(array,k)
print (n - index)


### FIXED CODE ###

import bisect
n,k = input().strip().split()
n,k = [int(n),int(k)]
array = list(map(int,input().strip().split()))
array.sort()
index = bisect.bisect_left(array,k)
print (n - index)
N, M, K = map(int, raw_input().split(' '))
 
for n in xrange(N+1):
  for m in xrange(M+1):
    if n*M + m*N - 2*n*m == K:
      print 'Yes'
      exit()
 
print 'No'

### FIXED CODE ###

N, M, K = map(int, raw_input().split(' '))

for n in xrange(N+1):
  for m in xrange(M+1):
    if n*M + m*N - 2*n*m == K:
      print 'Yes'
      exit()

print 'No'
A,B = map(int,input().split())
o = -1
if A >= 10 or B >= 10:
    print(o)
else:
print(A*B)
end:

### FIXED CODE ###

A,B = map(int,input().split())
o = -1
if A >= 10 or B >= 10:
    print(o)
else:
    print(A*B)
K,X = map(int,input().split())
for i in range(X-(K-1),X+(K-1)):
  print(i + " ")

### FIXED CODE ###

K,X = map(int,input().split())
for i in range(X-(K-1),X+K):
  print(str(i) + " ")
a, b = map(int, raw_input().split():)

print a * b , a * 2 + b * 2

### FIXED CODE ###


l = map(int, raw_input().split())
 
print "%d %d" % (l[0]*l[1], (l[0]+l[1])*2)
n,k=map(int,input().split())
l=[]
for j in range(0,n):
    l.append(input().split())
ans=0
for a in range(0,k):
     for b in range(0,k):
         i=0
         total=0
         while i<n:
           m=(abs(int(l[i][0])-a)//k)%2
           h=(abs(int(l[i][1])-b)//k)%2
           if ((m+h)%2==0 and str(l[i][2])=="W") or ((m+h)%2==1 and str(l[i][2])=="B"):
               total=total+1
               i=i+1
           else:
               i=i+1

         else:
              ans=max(ans,total,n-total)
print(ans)

### FIXED CODE ###

a,b=map(int,input().split())
if (a*b)%2==0:
     print('Even')
else:
     print("Odd")
def main():
    from collections import deque, defaultdict
    n = int(input())
    t = [[] for _ in range(n + 1)]
    m = []

    for _ in range(n - 1):
        i, j = map(int, input().split())
        t[i].append(j)
        m.append([i, j])
    d = defaultdict(dict)

    def f(u, i):
        z = t[u]
        c = 1
        for v in z:
            if c == i:
                c += 1
            d[u].update({v: c})
            f(v, c)
            c += 1

    f(m[0][0], len(t[m[0][0]]) + 1)

    ans = ''
    if t.count([]) == n:
        ans += str(n - 1) + '\n'
    else:
        ans += str(max(len(i) for i in t) + 1) + '\n'

    for (u, v) in m:
        ans += str(d[u][v]) + '\n'

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def f(u, i, d, t, vis):
    if vis[u]:
        return
    vis[u] = True
    z = t[u]

    c = 1
    for v in z:
        if vis[v]:
            continue
        if c == i:
            c += 1
        d[u].update({v: c})
        f(v, c, d, t, vis)
        c += 1


def main():
    from collections import defaultdict
    import sys
    sys.setrecursionlimit(100000)
    n = int(input())
    t = [[] for _ in range(n + 1)]
    m = []

    for _ in range(n - 1):
        i, j = map(int, input().split())
        t[i].append(j)
        t[j].append(i)
        m.append([i, j])
    d = defaultdict(dict)
    vis = [False for _ in range(n + 1)]
    f(1, len(t[1]) + 1, d, t, vis)

    ans = ''
    if t.count([]) == n:
        ans += str(n - 1) + '\n'
    else:
        ans += str(max(len(i) for i in t)) + '\n'

    for (u, v) in m:
        ans += str(d[u][v]) + '\n'

    print(ans)


if __name__ == '__main__':
    main()
while True:
	d = raw_input()
	if d != '':
		size = 0
		d = int(d)
		fd = d
		for x in range(1,600/d):
			size += d*(fd**2)
			fd += d
		print size
		continue
	else:
		break

### FIXED CODE ###

while True:
	try:
		d = raw_input()
		size = 0
		d = int(d)
		fd = d
		for x in range(1,600/d):
			size += d*(fd**2)
			fd += d
		print size
	except: break
N = int(input())
a = [[] for i in range(N)]
edge = {}
for i in range(N-1):
  A, B, C = map(int, input().split())
  a[A-1].append(B-1)
  a[B-1].append(A-1)
  edge[str(A-1)+"and"+str(B-1)] = C
  edge[str(B-1)+"and"+ str(A-1)] = C
dist = [-1]*N
Q, K = map(int, input().split())
dist[K-1] = 0

def  dfs(now):
  for i in a[now]:
    if dist[i] == -1:
      dist[i] = dist[now] + edge[str(now) + "and" +str(i)]
      dfs(i)

def main():
  dfs(K-1)
  ans = []
  for i in range(Q):
    x, y = map(int, input().split())
    ans.append(dist[x-1]+dist[y-1])
  print(*ans, sep = "\n")

if __name__ == "__main__":
  main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
N = int(input())
a = [[] for i in range(N)]
for i in range(N-1):
  A, B, C = map(int, input().split())
  a[A-1].append([B-1, C])
  a[B-1].append([A-1, C])
dist = [-1]*N
Q, K = map(int, input().split())
dist[K-1] = 0

def dfs(now):
  for i, dis_e in a[now]:
    if dist[i] == -1:
      dist[i] = dist[now] + dis_e
      dfs(i)

def main():
  dfs(K-1)
  ans = []
  for i in range(Q):
    x, y = map(int, input().split())
    print(dist[x-1]+dist[y-1])
  #print(*ans, sep = "\n")

if __name__ == "__main__":
  main()
N, T = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB.sort(key=lambda x: x[1])

def dfs(i, sum, time, remain):
    global answer
    if i == N:
        if time < T and len(remain) >= 1:
            sum += AB[max(remain)][1]
        if sum > answer:
            answer = sum
    else:
        dfs(i+1, sum, time, remain)
        if time < T:
            dfs(i+1, sum + AB[i][1], time + AB[i][0], remain-{i})

answer = 0
dfs(0, 0, 0, set(range(N)))
print(answer)

### FIXED CODE ###

import sys
import numpy as np

n, t = map(int, input().split())
knapsack = np.zeros(t, dtype=np.int64)
cuisines = [tuple(map(int, line.split())) for line in sys.stdin]
cuisines.sort()
tmp_ans = 0
for a, b in cuisines:
    tmp_ans = max(tmp_ans, knapsack.max() + b)
    knapsack[a:] = np.maximum(knapsack[a:], knapsack[:-a] + b)
print(tmp_ans)
import numpy as np

def count(s):
    prev = ""
    cnt = 0
    dp = np.zeros(len(s)+1, dtype=int)
    for i, c in enumerate(s):
        if (prev == "A") and (c == "C"):
            cnt += 1
        prev = c
        dp[i+1] = cnt
    return dp

def solve(n, q, s, l, r):
    dp = count(s)
    for i in range(q):
        print(dp[r[i]] - dp[l[i]])

n, q = map(int, input().split())
s = input()
l = np.zeros(n, dtype=int)
r = np.zeros(n, dtype=int)
for i in range(q):
    l[i], r[i] = map(int, input().split())
print(solve(n, q, s, l, r))

### FIXED CODE ###

import numpy as np

def count(s):
    prev = ""
    cnt = 0
    dp = np.zeros(len(s)+1, dtype=int)
    for i, c in enumerate(s):
        if (prev == "A") and (c == "C"):
            cnt += 1
        prev = c
        dp[i+1] = cnt
    return dp

def solve(n, q, s, l, r):
    dp = count(s)
    for i in range(q):
        print(dp[r[i]] - dp[l[i]])

n, q = map(int, input().split())
s = input()
l = np.zeros(q, dtype=int)
r = np.zeros(q, dtype=int)
for i in range(q):
    l[i], r[i] = map(int, input().split())
solve(n, q, s, l, r)
N, M = map(int, input().split())
table = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    table[a-1].append(b-1)

visit = [False] * N
visit2 = [False] * N
g = []


def dfs(v):
    g.append(v)
    if visit[v]:
        return True
    visit[v] = True
    visit2[v] = True
    for u in table[v]:
        if dfs(u):
            return True
    g.pop()
    visit[v] = False
    return False


for i in range(N):
    g = []
    if not visit2[i]:
        if dfs(i):
            break
else:
    print(-1)
    exit()
print(0)
# ans = [v+1 for v in g[g.index(g[-1]):-1]]
# print(len(ans))
# print(*ans, sep="\n")


### FIXED CODE ###

from sys import setrecursionlimit
setrecursionlimit(10000)
N, M = map(int, input().split())
table = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    table[a-1].append(b-1)

visit = [False] * N
visit2 = [False] * N
g = []


def dfs(v):
    g.append(v)
    if visit[v]:
        return True
    visit[v] = True
    visit2[v] = True
    for u in table[v]:
        if dfs(u):
            return True
    g.pop()
    visit[v] = False
    return False


for i in range(N):
    g = []
    if not visit2[i]:
        if dfs(i):
            break
else:
    print(-1)
    exit()
print(0)
# ans = [v+1 for v in g[g.index(g[-1]):-1]]
# print(len(ans))
# print(*ans, sep="\n")
s = input()
t = input()
n = len(s)
s.split()
t.split()
ans = 0
for i in range(n):
    if s[i] != t[i]:
        s[i] = t[i]
        x += 1
    else:
        pass
print(ans)

### FIXED CODE ###

a = int(input())
print(a+a**2+a**3)
def main():
    N = int(input())
    S = input()
    if N % 2 == 1:
        print("No")
        quit()
    n = N / 2
    yesno = "Yes" if S[:n] == S[n:] else "No"
    print(yesno)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N = int(input())
    S = input()
    if N % 2 == 1:
        print("No")
        quit()
    n = N // 2
    yesno = "Yes" if S[:n] == S[n:] else "No"
    print(yesno)


if __name__ == "__main__":
    main()
from collections import defaultdict
from fractions import gcd

INF = 2 << 30
MAX_V = 1002
G = [[] for _ in xrange(MAX_V)]
visited = [False]*MAX_V

def add_edge(fro, to, cap):
    G[fro].append([to,cap,len(G[to])])
    G[to].append([fro,0,len(G[fro])-1])

def dfs(v,t,f):
    global visited
    if v == t:
        return f
    visited[v] = True
    for i,(to,cap,rev) in enumerate((G[v])):
        if visited[to] or cap == 0:            
            continue        
        d = dfs(to,t,min(f,cap))
        if d > 0:
            G[v][i][1] -= d
            G[to][rev][1] += d
            return d
    return 0

def max_flow(s,t):
    global visited
    flow = 0
    while True:
        visited = [False]*MAX_V
        f = dfs(s,t,INF)
        if f == 0:
            return flow
        flow += f

while True:
    m,n = map(int,raw_input().split())
    if m|n == 0:
        break
    G = [[] for _ in xrange(MAX_V)]
    data = []
    while len(data) < n+m:
        data += map(int,raw_input().split())    
    blue = data[:m]
    red = data[m:]
    for i,b in enumerate(blue):
        add_edge(MAX_V-2,i,1)
    for i,r in enumerate(red):
        add_edge(i+m,MAX_V-1,1)
    for i in xrange(m):
        for j in xrange(n):
            if gcd(blue[i],red[j]) != 1:
                add_edge(i,j+m,1)
    print max_flow(MAX_V-2,MAX_V-1)

### FIXED CODE ###

from fractions import gcd

V = 1001
G = []
visited = []
match = []

def add_edge(u,v):
    G[u].append(v)
    G[v].append(u)

def dfs(v):
    visited[v] = True
    for u in G[v]:
        w = match[u]
        if w < 0 or not visited[w] and dfs(w):
            match[v] = u
            match[u] = v
            return True

def bipartite_matching():
    global match,visited
    res = 0
    match = [-1]*V
    for v in xrange(V):
        if match[v] < 0:
            visited = [False]*V
            if dfs(v):
                res += 1
    return res

while True:
    m,n = map(int,raw_input().split())
    V = m+n
    if V == 0:
        break
    G = [[] for _ in xrange(V)]
    data = []
    while len(data) < V:
        data += map(int,raw_input().split())
    for i,b in enumerate(data[:m]):
        for j,r in enumerate(data[m:],m):
            if gcd(b,r) != 1:
                add_edge(i,j)
    print bipartite_matching()
MOD=10**9+7
N,M=map(int,input().split())
A=[int(input()) for _ in range(M)]
L=[-1 for _ in range(N)]
p=0
if 1 == A[p]:
  L[0] = 0
  if p < M-1:
    p +=1
else:
  L[0] = 1
if N>1:
  if 2 == A[p]:
    L[1] = 0
    if p < M-1:
      p+=1
  else:
    L[1]=L[0]+1
for i in range(2,N):
  if i+1 == A[p]:
    L[i] = 0
    if p < M-1:
      p+=1
  else:
    L[i]=L[i-1]+L[i-2]
print(L[-1]%MOD)

### FIXED CODE ###

MOD=10**9+7
N,M=map(int,input().split())
A=[int(input()) for _ in range(M)]
L=[-1 for _ in range(N)]
p=0
if A == []:
  A=[0]
if 1 == A[p]:
  L[0] = 0
  if p < M-1:
    p +=1
else:
  L[0] = 1
if N>1:
  if 2 == A[p]:
    L[1] = 0
    if p < M-1:
      p+=1
  else:
    L[1]=L[0]+1
for i in range(2,N):
  if i+1 == A[p]:
    L[i] = 0
    if p < M-1:
      p+=1
  else:
    L[i]=L[i-1]+L[i-2]
print(L[-1]%MOD)