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

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

tree = [[0 for _ in range(N)] for __ in range(N)]

for i in range(N-1):
    a,b = list(map(int,input().split()))
    tree[a-1][b-1] = 1
    tree[b-1][a-1] = 1

ans = []
def wfs(now,back):
    check = [i for i,x in enumerate(tree[now]) if x == 1]
    if now != 0:
        cnt = K - 2 #まず一個上のを引く。
    else:
        cnt = K - 1
    for nxt in check:
        if nxt != back:
            ans.append(cnt)
            cnt = cnt - 1
            wfs(nxt,now)

ans.append(K)
wfs(0,-1)

ans2 = 1
for j in range(N):
    ans2 = (ans2 * ans[j]) % (10**9+7)
print(ans2)


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)
 

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

tree = [[] for _ in range(N+10)]

for i in range(N-1):
    a,b = list(map(int,input().split()))
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)

ans = []
def wfs(now,back):
    if now != 0:
        cnt = K - 2 #まず一個上のを引く。
    else:
        cnt = K - 1
    for nxt in tree[now]:
        if nxt != back:
            ans.append(cnt)
            cnt = cnt - 1
            wfs(nxt,now)

ans.append(K)
wfs(0,-1)

ans2 = 1
for j in range(len(ans)):
    ans2 = (ans2 * ans[j]) % (10**9+7)
print(ans2)
### BUGGY CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]

b = [x for x in set(a) if a.count(x) % 2 != 0]
print(len(b))

### FIXED CODE ###

import collections

n = int(input())
a = [int(input()) for _ in range(n)]
b = collections.Counter(a)

cnt = 0
for v in b.values():
    if v % 2 == 1:
        cnt += 1

print(cnt)
### BUGGY CODE ###

n = int(input())
P = list(map(int, input().split()))
min_n = [min(P[:i]) for i in range(1, n+1)]
c = 0
for i in range(n):
    if P[i] == min_n[i]:
        c += 1
        
print(c)

### FIXED CODE ###

n = int(input())
P = list(map(int, input().split()))
c = 1
minimum = P.pop(0)
if minimum != 1:
    for p in P:
        if p <= minimum:
            c += 1
            minimum = p
        if p == 1:
            break
print(c)
### BUGGY CODE ###

#17:11
inf = 10 ** 18
n,m = map(int,input().split())
pre = [inf for i in range(n)]
ans = n
for _ in range(m):
  x,y,z = map(int,input().split())
  x -= 1
  y -= 1
  X = [x]
  Y = [y]
  while pre[x] != inf:
    X.append(x)
    x = pre[x]
  while pre[y] != inf:
    Y.append(y)
    y = pre[y]
  if x != y:
    ans -= 1
    for xx in X:
      pre[xx] = y
    for yy in Y:
      pre[yy] = y
    pre[x] = y
#print(pre)
print(ans)

### FIXED CODE ###

#解説チラ見
n,m = map(int,input().split())
ans = n
pre = [i for i in range(n)]
for _ in range(m):
  x,y,z = map(lambda x: int(x)-1, input().split())
  X = [x]
  while pre[x] != x:
    x = pre[x]
    X.append(x)
  Y = [y]
  while pre[y] != y:
    y = pre[y]
    Y.append(y)
  if x != y:
    ans -= 1
    for xx in X:
      pre[xx] = y
    for yy in Y:
      pre[yy] = y
    pre[x] = y
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline

n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
cnt = [0] * (m + 1)
cur = [0] * n
done = [0] * (m + 1)
for i in range(n):
	cnt[a[i][0]] += 1
	cur[i] = a[i][0]
ans = max(cnt)
for _ in range(m - 1):
	col = cnt.index(max(cnt))
	done[col] = 1
	for i in range(n):
		if cur[i] == col:
			j = 0
			while done[a[i][j]]:
				j += 1
			t = a[i][j]
			cur[i] = t
			cnt[t] += 1
	cnt[col] = 0
	ans = min(ans, max(cnt))
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
cnt = [0] * (m + 1)
cur = [0] * n
done = [0] * (m + 1)
for i in range(n):
	cnt[a[i][0]] += 1
	cur[i] = a[i][0]
ans = max(cnt)
for _ in range(m - 1):
	col = cnt.index(max(cnt))
	done[col] = 1
	for i in range(n):
		if cur[i] == col:
			j = 0
			while done[a[i][j]]:
				j += 1
			t = a[i][j]
			cur[i] = t
			cnt[t] += 1
	cnt[col] = 0
	ans = min(ans, max(cnt))
print(ans)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
ans=1
c=0
for n in range(N):
    if A[n]==0:
        c=2
for n in range(N):
    ans=ans*A[n]
    if ans>10**18:
        c=-1
for n in range(N):
    if A[n]==0:
        c=2
if c==-1:
    print(-1)
elif c==2:
    print(0)
else:
    print(ans)


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
ans=1
c=1
for n in range(N):
    if A[n]==0:
        c=0
        break
if c!=0:
    for n in range(N):
        ans=ans*A[n]
        if ans>10**18:
            c=-1
            break
if c==-1:
    print(-1)
elif c==0:
    print(0)
else:
    print(ans)
### BUGGY CODE ###

D = int(input())
C = list(map(int,input().split()))
S = []
for _ in range(D):
    S.append(list(map(int,input().split())))

SELECT = []
for i in range(D):
    SELECT.append(int(input())-1)

def score(selects):
    score = 0
    L = [0 for _ in range(26)]
    def calc(ans, select, n):
        for i, l in enumerate(L):
            if i != select:
                ans -= C[i] * (n - L[i])
            else:
                L[i] = n
        return ans

    for i,select in enumerate(selects):
        score += S[i][select]
        score = calc(score, select, i+1)
    return score

M = int(input())
for _ in range(M):
    i, s = map(int,input().split())
    SELECT[i-1]=s-1
    print(score(SELECT))


### FIXED CODE ###

def main():
    D = int(input())
    C = list(map(int,input().split()))
    S = [list(map(int,input().split()))for _ in range(D)]

    SELECT = []
    for i in range(D):
        SELECT.append(int(input())-1)

    M = int(input())
    d = []
    q = []
    for _ in range(M):
        td, tq = map(int,input().split())
        d.append(td-1)
        q.append(tq-1)

    L_ALL = [[0]*26 for _ in range(D)]
    L = [0]*26
    ans = 0
    for i in range(D):
        ans += S[i][SELECT[i]]
        L[SELECT[i]]=i+1
        if i != 0:
            L_ALL[i] = L_ALL[i-1][:]
        L_ALL[i][SELECT[i]] = i+1
        for j in range(26):
            ans -= C[j]*(i+1-L[j])

    for i in range(M):
        day = d[i]
        before = SELECT[day]
        after = q[i]
        ans -= S[day][before]
        ans += S[day][after]
        SELECT[day] = q[i]

        if day == 0:
            tmp = 0
        else:
            tmp = L_ALL[day-1][before]
        j = day
        while 0<=j<D and L_ALL[j][before]==day+1:
            L_ALL[j][before] = tmp
            ans -= C[before]*(day+1-tmp)
            j += 1

        if day == 0:
            tmp = 0
        else:
            tmp = L_ALL[day-1][after]
        j = day
        while 0<=j<D and L_ALL[j][after]==tmp:
            L_ALL[j][after]=day+1
            ans += C[after] * (day+1-tmp)
            j += 1

        print(ans)

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

import numpy as np
H, W=map(int, input().split())
S=np.array([list(input()) for _ in range(H)])
INF=np.inf
#print(S)
def bfs(sx,sy,gx,gy):
  #dx, dy 四方向に対応したベクトルのリスト
  dx=[1,0,-1,0]
  dy=[0,1,0,-1]
  #P: (x, y)のキュー
  P=[]
  #d: スタートから各点までの最小距離の配列
  d=np.ones((H, W))*INF
  #スタート地点をキューに入れ、その点の距離を0にする
  P.append([sx, sy])
  d[sx,sy]=0
    
  #キューがからになるまでループ
  while len(P)>0:
    #キューの先頭を取り出す
    p=P.pop(0)
    #取り出してきた状態がゴールなら探索をやめる
    if (p[0]==gx and p[1]==gy):
      break
        
    #移動四方向をループ
    for i in range(4):
      #移動した後の点をnx, nyとする
      nx=p[0]+dx[i]
      ny=p[1]+dy[i]
            
      #移動が可能かどうかの判定とすでに訪れたことがあるかどうかの判定（d[nx, ny]!=INFならおtpずれたことがある）
      if 0<=nx and nx<H and 0<=ny and ny<W and S[nx, ny]!="#" and d[nx, ny]==INF:
        #移動できるならキューに入れ、その点の距離をpからの距離＋１で確定する
        P.append([nx, ny])
        d[nx, ny]=d[p[0], p[1]]+1
  #print(d)
  return d[gx, gy]
ans=0
for sx in range(H):
  for sy in range(W):
    for gx in range(H):
      for gy in range(W):
        if S[sx,sy]=="#" or S[gx,gy]=="#":
          continue
        res=bfs(sx,sy,gx,gy)
        ans=max(ans, res)
print(int(ans))

### FIXED CODE ###

import numpy as np
H, W=map(int, input().split())
S=np.array([list(input()) for _ in range(H)])
INF=-1
#print(S)
def bfs(sx,sy):
  #dx, dy 四方向に対応したベクトルのリスト
  dx=[1,0,-1,0]
  dy=[0,1,0,-1]
  #P: (x, y)のキュー
  P=[]
  #d: スタートから各点までの最小距離の配列
  d=np.ones((H, W))*INF
  #スタート地点をキューに入れ、その点の距離を0にする
  P.append([sx, sy])
  d[sx,sy]=0
    
  #キューがからになるまでループ
  while len(P)>0:
    #キューの先頭を取り出す
    p=P.pop(0)
    #取り出してきた状態がゴールなら探索をやめる
    """
    if (p[0]==gx and p[1]==gy):
      break
    """
        
    #移動四方向をループ
    for i in range(4):
      #移動した後の点をnx, nyとする
      nx=p[0]+dx[i]
      ny=p[1]+dy[i]
            
      #移動が可能かどうかの判定とすでに訪れたことがあるかどうかの判定（d[nx, ny]!=INFならおtpずれたことがある）
      if 0<=nx and nx<H and 0<=ny and ny<W and S[nx, ny]!="#" and d[nx, ny]==INF:
        #移動できるならキューに入れ、その点の距離をpからの距離＋１で確定する
        P.append([nx, ny])
        d[nx, ny]=d[p[0], p[1]]+1
  """
  #print(d)
  if d[gx,gy]!=INF:
    result=d[gx, gy]
  else:
    result=0
  """
  result=d.max()
  return result
ans=0
Tlen=H*W
for sx in range(H):
  for sy in range(W):
    if S[sx,sy]=="#":
      continue
    res=bfs(sx,sy)
    ans=max(ans, res)
"""
for i in range(Tlen):
  for j in range(i,Tlen):
    sx,sy=i%H, int(i//H)
    gx,gy=j%H, int(j//H)
    
    if S[sx,sy]=="#" or S[gx,gy]=="#":
      continue
    res=bfs(sx,sy,gx,gy)
    ans=max(ans, res)
"""
"""
for sx in range(H):
  for sy in range(W):
    for gx in range(H):
      for gy in range(W):
        if S[sx,sy]=="#" or S[gx,gy]=="#":
          continue
        res=bfs(sx,sy,gx,gy)
        ans=max(ans, res)
"""
print(int(ans))
### BUGGY CODE ###

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

total = 0 

for i in range(len(s)-1):
  for j in range(i+1, len(s)):
    total += s[i] * s[j]

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

### FIXED CODE ###

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

ans= 0
total = sum(s)

for i in range(len(s)-1):
  total -= s[i]
  ans += total * s[i]

print(ans % (10**9 +7))
### BUGGY CODE ###

import itertools

n,m,k = map(int,input().split())
a = list(map(int,('0 '+input()).split()))
b = list(map(int,('0 '+input()).split()))

asum = list(itertools.accumulate(a))
bsum = list(itertools.accumulate(b))

ans = 0
for i in range(n+1):
    for j in range(m,max(-1,ans-i),-1):
        if asum[i]+bsum[j]<=k:
            ans = max(ans,i+j)
            break

print(ans)

### FIXED CODE ###

import itertools

n,m,k = map(int,input().split())
a = list(map(int,('0 '+input()).split()))
b = list(map(int,('0 '+input()).split()))

asum = list(itertools.accumulate(a))
bsum = list(itertools.accumulate(b))

ans = 0
j=m
for i in range(n+1):
    if asum[i]>k:
        break
    
    while asum[i]+bsum[j]>k:
        j-=1
        
    ans = max(ans,i+j)

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

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from math import factorial 
P = int(1e9)+7
def c(n, m):
       ch = 1
       for i in range(m):
           ch *= (n-i)
           ch %= P
       b = factorial(m) 
       b = pow(b, P-2, P)
       return ch*b%P
def main():
    x, y = map(int, readline().split())
    if ((2*y-x)%3) or ((2*x-y)%3):
        print(0)
        return
    a = (2*y-x)//3
    b = (2*x-y)//3
    if a < 0:
        print(0)
        return
    if b < 0:
        print(0)
        return
    print(c(a+b, a)) 
if __name__ == '__main__':
    main()


### FIXED CODE ###

#python3
from math import factorial
from math import floor
MOD = int(1e9+7)

def comb(n, m, mod):
    comb_a = 1
    for i in range(m): 
        comb_a *= (n-i)
        comb_a %= mod
    comb_tmp = factorial(m) 
    comb_b = pow(comb_tmp, mod-2, mod)
    return (comb_a * comb_b)%mod
def main():
    x, y = map(int, input().split())
    k = (2*x-y)/3
    l = (2*y-x)/3

    if floor(k) - k != 0:
        print(0)
        return
    if floor(l) - l != 0:
        print(0)
        return 
    if k<0:
        print(0)
        return
    if l<0:
        print(0)
        return
    k = int(k)
    l = int(l)
    print(comb(k+l, k, MOD)%MOD) 

main()
### BUGGY CODE ###

N = int(input())
price = list(map(int,input().split()))
price.append(0)
stock = 0
money = 1000
for i in range(N):
    if price[i] <= price[i+1]:
        while money >=price[i]:
            stock += 1
            money -= price[i]
    else:
        while stock>0:
            money += price[i]
            stock-=1
print(money)      

### FIXED CODE ###

import math
N = int(input())
price = list(map(int,input().split()))
price.append(0)
stock = 0
money = 1000
for i in range(N):
    if price[i] <= price[i+1]:
        times = math.floor(money/price[i])
        money -= price[i]*times
        stock += times
    else:
        money += price[i]*stock
        stock =0
print(money)
### BUGGY CODE ###

n=int(input())
mat=[[0]*30 for _ in range(30)]
ary=[]
op=0
a=[]
for _ in range(n):
  t=list(input().split('.'))
  if len(t)==1:
    c=int(t[0])*pow(10,9)
  else:
    c=int(t[0])*pow(10,9)
    r=int((t[1]+'0'*10)[:9])
    c+=r
  n2,n5=0,0
  while (c//pow(2,n2))%2==0:
    n2+=1
  while (c//pow(5,n5))%5==0:
    n5+=1
  n2=min(n2,9+9)
  n5=min(n5,9+9)
  mat[n2][n5]+=1
  a.append((c,n2,n5))
  ary.append((n2,n5))
#for x in a:
#  print(x)
summat=[[0]*31 for _ in range(31)]
for i in range(30):
  for j in range(30):
    summat[i+1][j+1]=summat[i+1][j]+mat[i][j]
for i in range(30):
  for j in range(30):
    summat[i+1][j+1]+=summat[i][j+1]

ans=0
for n2,n5 in ary:
  t2,t5=n2,n5
  t2-=9
  t2*=-1
  t2+=9
  t5-=9
  t5*=-1
  t5+=9
  #print(n2,n5,t2,t5)
  ans+=summat[-1][-1]-summat[t2][-1]-summat[-1][t5]+summat[t2][t5]
  if n2>=9+op and n5>=9+op:ans-=1
print(ans//2)


### FIXED CODE ###

def main(n,a):
  k=60
  mp=[[0]*k for _ in range(k)]
  o=k//2
  ary=[]
  for i in range(n):
    b=list(a[i].split('.'))
    b.append('0')
    x=int(b[0])
    y=int((b[1]+'0'*9)[:9])
    x=x*pow(10,9)+y
    # x10^9
    cnt5=-9
    xx=x
    while xx>1:
      if xx%5==0:
        cnt5+=1
        xx//=5
      else:
        break
    cnt2=-9
    xx=x
    while xx>1:
      if xx%2==0:
        cnt2+=1
        xx//=2
      else:
        break
    #if 0<=cnt5+o<23 and 0<=cnt2+o<23:
    mp[cnt5+o][cnt2+o]+=1
    ary.append([cnt5+o,cnt2+o])

  ans=0
  for i in range(k-1,0,-1):
    for j in range(k):
      mp[j][i-1]+=mp[j][i]
  for i in range(k-1,0,-1):
    for j in range(k):
      mp[i-1][j]+=mp[i][j]
  for x,y in ary:
    if x>=o and y>=o:
      i=1
    else:
      i=0
    x-=o
    x*=-1
    x+=o
    y-=o
    y*=-1
    y+=o
    ans+=mp[x][y]-i
  print(ans//2)
  #mp[o,o]+=10
  #print(mp)

n=int(input())
a=[input() for _ in range(n)]
main(n,a)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

# import collections

n = int(input())
balls = list(map(int, input().split(' ')))

for k in range(n):
    # print(balls[ : k])
    # print(balls[ k + 1: ])
    arr = balls[ : k] + balls[ k + 1 : ]

    total = 0
    # dic = collections.Counter(arr)
    # for v in dic.values():
    #     total += int(v * (v - 1) / 2)

    # print(arr, list(set(arr)))
    for num in list(set(arr)):
        v = arr.count(num)
        total += int(v * (v - 1) / 2)
    print(total)



### FIXED CODE ###

# -*- coding: utf-8 -*-

import collections

n = int(input())
balls = list(map(int, input().split(' ')))

dic = collections.Counter(balls)
total = 0
for v in dic.values():
    if (v < 2):
        continue
    total += int(v * (v - 1) / 2)

for i in range(n):
    num = balls[i]
    print(total - dic[num] + 1)
### BUGGY CODE ###

n=int(input())
s=[]
u=[]
for i in range(n):
    a=input()
    s.append(a)
    if a not in u:
        u.append(a)
d={}
t=0
for i in range(n):
    if s[i] not in d:
        d[s[i]]=1
        if t==0:
            t=1
    else:
        d[s[i]]+=1
        if t<d[s[i]]:
            t=d[s[i]]
b=[]
for i in range(len(u)):
    if d[u[i]]==t and (u[i] not in b):
        b.append(u[i])
b.sort()
for i in range(len(b)):
    print(b[i])

### FIXED CODE ###

n=int(input())
s=[]
for i in range(n):
    s.append(input())
s.sort()
t=1
m=0
a=s[0]
for i in range(n-1):
    if s[i+1]==a:
        t+=1
    else:
        a=s[i+1]
        m=max(t,m)
        t=1
m=max(t,m)
t=1
x=[]
a=s[0]
for i in range(n-1):
    if s[i+1]==a:
        t+=1
    else:
        a=s[i+1]
        if t==m:
            x.append(s[i])
        t=1
if  t==m:
    x.append(s[len(s)-1])
for i in range(len(x)):
    print(x[i])
### BUGGY CODE ###

def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10
    K = II()
    S = input()
    N = len(S)
    def nCr(n,r):
        res = 1
        r = min(r,n-r)
        for i in range(n-r+1,n+1):
            res = res * i % P
        for i in range(2,r+1):
            res = res * pow(i,P-2,P) % P
        return res
    ans = 0
    pow26 = [0] * (K+1)
    pow26[0] = 1
    for i in range(1,K+1):
        pow26[i] = pow26[i-1] * 26 % P
    pow25 = [0] * (K+1)
    pow25[0] = 1
    for i in range(1,K+1):
        pow25[i] = pow25[i-1] * 25 % P
    for t in range(K+1):
        ans += pow26[t]*pow25[K-t]*nCr(N-1+K-t,K-t)
        ans %= P
    print(ans)

    
main()

### FIXED CODE ###

def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10
    K = II()
    S = input()
    N = len(S)
    def gencmb(n,k):
        # N-1+K C K  ... N-1 C 0
        ans = [1]*(k+1)
        for i in range(1,k+1):
            ans[-i-1] = ans[-i] * (N+i-1) * pow(i,P-2,P) % P
        return ans
    ans = 0
    pow26 = [0] * (K+1)
    pow26[0] = 1
    for i in range(1,K+1):
        pow26[i] = pow26[i-1] * 26 % P
    pow25 = [0] * (K+1)
    pow25[0] = 1
    for i in range(1,K+1):
        pow25[i] = pow25[i-1] * 25 % P
    cmb = gencmb(N,K)
    for t in range(K+1):
        ans += pow26[t]*pow25[K-t]*cmb[t]%P
        ans %= P
    print(ans)

    
main()
### BUGGY CODE ###

N,M=map(int, input().split())
p=[set()]+[set([int(x)]) for x in input().split()]
xy=[list(map(int, input().split())) for _ in range(M)]

for _ in range(10):
	for x,y in xy:
		p[x]=p[y]=p[x]|p[y]

print(sum([1 if i in s else 0 for (i, s) in enumerate(p)]))


### FIXED CODE ###

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

uf=[i for i in range(N+1)]

def find(n):
	if uf[n] == n:
		return n
	uf[n] = find(uf[n])
	return uf[n]

def union(n, m):
	uf[find(n)] = find(m)

def same(n, m):
	return find(n) == find(m)

for _ in range(M):
	union(*map(int, input().split()))

for i in range(N+1):
	find(i)

print(sum([1 if same(i+1,v) else 0 for i,v in enumerate(p)]))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

n = int(input())
import sys
vals = [None]*n
def quest(q):
    print(q)
    sys.stdout.flush()
    res = input()
    if res=="Vacant":
        exit()
        res = -1
    elif res=="Male":
        res = 1
    else:
        res = 0
    vals[q] = res
    return res

k = n//2
res1 = quest(0)
res2 = quest(k)

if (res2-res1)%2 == k%2:
    l = k+1
    r = n-1
else:
    l = 1
    r = k
    
while l<r+1:
    m = (l+r)//2
    res = quest(m)
    if (res-vals[l])%2 == (l-m)%2:
        l = m
    else:
        r = m
quest(l)
quest(r)

### FIXED CODE ###

import sys
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

n = int(input())
import sys
vals = [None]*n
def quest(q):
    print(q)
    sys.stdout.flush()
    res = input()
    if res=="Vacant":
        exit()
        res = -1
    elif res=="Male":
        res = 1
    else:
        res = 0
    vals[q] = res
    return res

k = n//2
res1 = quest(0)
res2 = quest(k)

if (res2-res1)%2 != k%2:
    l = 0
    r = k
else:
    l = k
    r = n
    
while l<r+1:
    m = (l+r)//2
    res = quest(m)
    if (res-vals[l])%2 != (l-m)%2:
        r = m
    else:
        l = m
quest(l)
quest(r)
### BUGGY CODE ###

k,s = [int(i) for i in input().split()]
ans = 0
for a in range(k+1):
    for b in range(k+1):
        for c in range(k+1):
            if a+b+c == s:
                ans += 1
            elif a + b + c > s:
                break
            else:
                pass
print(ans)


### FIXED CODE ###

k,s = [int(i) for i in input().split()]
ans = 0
for a in range(k+1):
    for b in range(k+1):
        c = s - a -b
        if  0 <= c <= k:
            ans += 1
print(ans)
### BUGGY CODE ###

import heapq

n,m = map(int,input().split())
lb = []
for _ in range(n):
    lb.append(list(map(int,input().split())))
res = 0
q = []
heapq.heapify(q)
for i in range(1,m+1):
    for b in lb:
        if b[0] == i:
            heapq.heappush(q,b[1] * (-1))
    if q:
        res += heapq.heappop(q) * (-1)

print(res)

### FIXED CODE ###

import heapq

n,m = map(int,input().split())
lb = [[] for _ in range(10**5+5)]
for _ in range(n):
    a,b = map(int,input().split())
    lb[a].append(b)
res = 0
q = []
heapq.heapify(q)
for i in range(1,m+1):
    for b in lb[i]:
        heapq.heappush(q,b * (-1))
    if q:
        res += heapq.heappop(q) * (-1)

print(res)
### BUGGY CODE ###

import math
from collections import Counter
n = int(input())
lis = list(map(str,input().split()))
if n % 2 == 1:
  for i in range(math.ceil(n / 2)):
    if i == 0:
      if lis.count("0") != 1:
        print("0")
        exit()
    else:
      if lis.count(str(i * 2)) != 2:
        print("0")
        exit()
  print(2 ** (math.floor(n/2)))
else:
  for i in range(n//2):
    if lis.count(str(i * 2 + 1)) != 2:
      print("0")
      exit()
  print(2 ** (n//2))

### FIXED CODE ###

import math
n = int(input())
lis = list(map(int,input().split()))
li = [0 for _ in range(math.ceil(n / 2))]

for i in range(n):
  li[math.floor(lis[i] / 2)] += 1
for i in range(len(li)):
  if n % 2 == 1 and i == 0:
    if li[i] != 1:
      print("0")
      exit()
  else:
    if li[i] != 2:
      print("0")
      exit()
cou = 1
for i in range(math.floor(n/2)):
  cou *= 2
  cou %= (10 ** 9 + 7)
print(cou)
### BUGGY CODE ###

a, b, k= map(int, input().split())
for x in range(a,b+1):
  if x < a + k or x > b - k:
    print(x)
  else:
    continue

### FIXED CODE ###

a, b, k= map(int, input().split())
for x in range(a,min(a+k,b+1)):
    print(x)
for x in range(b-k+1,b+1):
    if x < a+k:
        continue
    else:
        print(x)
### BUGGY CODE ###

r,g,b,n=map(int, input().split())

r_max=n//r
g_max=n//g

sum=0

for i in range(n+1):
    for j in range(n+1):
        if (n-(i*r)-(j*g))%b==0 and (n-(i*r)-(j*g))//b>=0:
            sum=sum+1
        #    print(i*r,j*g,(n-(i*r)-(j*g))%b)

print(sum)


### FIXED CODE ###

r,g,b,n=map(int, input().split())

sum=0

for i in range(n//r+1):
    for j in range((n-i*r)//g+1):
        if (n-i*r-j*g)%b==0:
            sum=sum+1
        #    print(i*r,j*g,(n-(i*r)-(j*g))%b)

print(sum)
### BUGGY CODE ###

import sys
n = int(input())
a = list(map(int, input().split()))
tmp=sys.maxsize
s = sum(a)
for i in range(n):
    while tmp > abs(s-sum(a[:i+1])*2):
        tmp = abs(s-sum(a[:i+1])*2)
print(tmp)

### FIXED CODE ###

import sys
n = int(input())
a = list(map(int, input().split()))
tmp=sys.maxsize
s = sum(a)
t = 0
for i in range(n):
    t += a[i]
    tmp = min(tmp,abs(s-t*2))
print(tmp)
### BUGGY CODE ###

n, m = [int(x) for x in input().split()]
a = [int(input()) for _ in range(m)]

dp = [0]*(n+1)
dp[0] = 1

for i in range(1, n+1):
    dp[i] = (dp[i-1] + dp[i-2]) % (10**9+7)
    if i in a:
        dp[i] = 0

print(dp[n])

### FIXED CODE ###

n, m = [int(x) for x in input().split()]
a = set([int(input()) for _ in range(m)])

dp = [0]*(n+1)
dp[0] = 1

for i in range(1, n+1):
    dp[i] = (dp[i-1] + dp[i-2]) % (10**9+7)
    if i in a:
        dp[i] = 0

print(dp[n])