Harryxun/stf_run huggingface dataset:
mod = 1000000007
from collections import defaultdict
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

N = int(input())
AB = [list(map(int,input().split())) for _ in range(N)]
d1 = defaultdict(lambda:0)
d2 = defaultdict(lambda:0)
for i in range(N):
    a,b = AB[i]
    a_ = abs(a)
    b_ = abs(b)
    d = gcd(a,b)
    a //= d
    b //= d
    if a < 0:
        a *= -1
        b *= -1
    if b>=0:
        d1[(a,b)] += 1
    else:
        d2[(a,b)] += 1
        d1[(-b,a)] += 0

ans = 1
for a,b in d1:
    x = d1[(a,b)]
    y = d2[(b,-a)]
    ans *= pow(2,x,mod)+pow(2,y,mod)-1
    ans %= mod
ans -= 1
print(ans)

### FIXED CODE ###

mod = 1000000007
from collections import defaultdict
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

N = int(input())
AB = [list(map(int,input().split())) for _ in range(N)]
d1 = defaultdict(lambda:0)
d2 = defaultdict(lambda:0)
ca = 0
cb = 0
cc = 0
for i in range(N):
    a,b = AB[i]
    if a==0 and b!=0:
        ca += 1
        continue
    elif a!=0 and b==0:
        cb += 1
        continue
    elif a==0 and b==0:
        cc += 1
        continue
    a_ = abs(a)
    b_ = abs(b)
    d = gcd(a,b)
    if d != 0:
        a //= d
        b //= d
    if a < 0:
        a *= -1
        b *= -1
    if b>0:
        d1[(a,b)] += 1
    else:
        d2[(a,b)] += 1
        d1[(-b,a)] += 0

ans = pow(2,ca)+pow(2,cb)-1
for a,b in d1:
    x = d1[(a,b)]
    y = d2[(b,-a)]
    ans *= pow(2,x,mod)+pow(2,y,mod)-1
    ans %= mod
ans -= 1
ans += cc
ans %= mod
print(ans)
from math import gcd
def lcm(a, b):
    return a // gcd(a, b) * b

def main():
    num = int(input())
    d = list(map(int, input().split()))
    k = 1
    MOD = 1000000007
    ans = 0
    for a in d:
        k = lcm(k, a)
    for a in d:
        ans += k // a % MOD
    print(ans % MOD)

if __name__ == "__main__":
    main()


### FIXED CODE ###

from sys import stdin

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

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

readline = stdin.readline
num = int(readline())
d = list(map(int, readline().split()))
k = 1
MOD = 1000000007
ans = 0
for a in d:
    k = lcm(k, a)
for a in d:
    ans += k // a
print(ans % MOD)
while True:
    s=raw_input()
    if s=="0":break
    s+="".join([raw_input() for i in range(2)])
    L=[(i,i+1,i+2) for i in range(0,9,3)]+[(i,i+3,i+6) for i in range(3)]+[tupl\
e(range(0,9,4))]+[tuple(range(2,7,2))]
    for i,j,k in L:
        if s[i]==s[j]==s[k]:
            print "b" if s[i]=="b" else "w"
            break
    else:
        print "NA"

### FIXED CODE ###

while True:
    s=raw_input()
    if s=="0":break
    s+="".join([raw_input() for i in range(2)])
    L=[(i,i+1,i+2) for i in range(0,9,3)]+[(i,i+3,i+6) for i in range(3)]+[(0,4\
,8),(2,4,6)]
    for i,j,k in L:
        if s[i]==s[j]==s[k]!="+":
            print "b" if s[i]=="b" else "w"
            break
    else:
        print "NA"
#145_D
x,y=map(int,input().split())
mod=10**9+7
if (x+y)%3!=0:
    print(0)
else:
    n=(2*x-y)//3
    m=(2*y-x)//3
    f=[1 for i in range(m+n+1)]
    for i in range(2,m+n+1):
        f[i]=f[i-1]*i%mod
    print(f[m+n]*pow(f[n],mod-2,mod)*pow(f[m],mod-2,mod)%mod)

### FIXED CODE ###

#145_D
x,y=map(int,input().split())
mod=10**9+7
if (x+y)%3!=0:
    print(0)
else:
    n=(2*x-y)//3
    m=(2*y-x)//3
    if n<0 or m<0:
        print(0)
    else:
        f=[1 for i in range(m+n+1)]
        for i in range(2,m+n+1):
            f[i]=f[i-1]*i%mod
        print(f[m+n]*pow(f[n],mod-2,mod)*pow(f[m],mod-2,mod)%mod)
from numba import njit
import numpy as np
 
N, K = map(int, input().split())
A = list(map(int, input().split()))
 
@njit
for k in range(K):
  B = [0]*N
  for i in range(N): 
    start = max(0, i-A[i])
    end = min(N, i+A[i]+1)
    B[start] += 1
    if end <= N - 1:
      B[end] -= 1
  B = np.cumsum(B)
  #for i in range(1, N):
    #B[i] = B[i-1] + B[i] 
  A = B
  if min(A) == N:
    break
 
print(*A)

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
 
 
for k in range(K):
  B = [0]*N
  for i in range(N): 
    start = max(0, i-A[i])
    end = min(N, i+A[i]+1)
    B[start] += 1
    if end <= N - 1:
      B[end] -= 1
 
  for i in range(1, N):
    B[i] = B[i-1] + B[i] 
  A = B
  if min(A) == N:
    break
 
print(*A)
n=int(input())
ans = ''
while n>0:
        n = n-1
        s += chr(ord('a') + (n)% 26)
        n//=26
ans = ans[::-1]
print(ans)

### FIXED CODE ###

n=int(input())
ans = ''
while n>0:
        n = n-1
        ans += chr(ord('a') + (n)% 26)
        n//=26
ans = ans[::-1]
print(ans)
n,m= map(int,input().split())
c = [True]*(n+1)
for _ in range(m):
    c[int(input())] = False
d = [0]*(n)
if c[1] : d[1] = 1
if c[2] : d[2] = d[1] + 1
for i in range(3,n+1):
    if c[i] : d[i] = ( d[i-1] + d[i-2] ) % 1000000007
print(d[n])

### FIXED CODE ###

# DP
mod = 1000000007
 
n, m = map(int, input().split())
b_list = [True] * (n+1)
dp = [0 for _ in range(n+1)]
for i in range(m):
    b_list[int(input())] = False
 
dp[0] = 1
for i in range(n):
    for j in range(i+1, min(n, i+2)+1):
        if b_list[j] == True:
            dp[j] += dp[i]
            dp[j] %= mod
# print(b_list)
# print(dp)
print(dp[n])
N, Y = map(int, input().split())
for i in range(N + 1):
    for j in range(N - i + 1):
        if i * 10000 + j * 5000 + (N - i - j) * 1000 == y:
            print(i, j, N - i - j)
            exit()
print("-1 -1 -1")

### FIXED CODE ###

N, Y = map(int, input().split())
for i in range(N + 1):
    for j in range(N - i + 1):
        if i * 10000 + j * 5000 + (N - i - j) * 1000 == Y:
            print(i, j, N - i - j)
            exit()
print("-1 -1 -1")
import math
n=int(input())
a=list(map(int,input().split()))
a.sort()
ls=[0]
cnt=0
for i in range(1,2**n):
  if a[i]>a[i-1]:
    cnt+=1
  ls.append(cnt)
for i in range(2**n):
  if i<2**n-1:
    lmt=n-int(math.log2(2**n-i-1))-1
    if ls[i]<lmt:
      print("No")
      break
  if i==2**n-1:
    if ls[i]<n-1:
      print("No")
      break
else:
  print("Yes")

### FIXED CODE ###

import math
def cmb(n,r):
  return math.factorial(n)//(math.factorial(r)*math.factorial(n-r))
n=int(input())
a=list(map(int,input().split()))
a.sort()
ls=[0]
cnt=0
for i in range(1,2**n):
  if a[i]>a[i-1]:
    cnt+=1
  ls.append(cnt)
lmt = []
for i in range(n+1):
  lmt.extend([i]*cmb(n,i))
bias = ls[-1]-lmt[-1]
jdg = 0
ulmt = 0
for i in range(n):
  jdg += ls.count(i)
  ulmt += 2**(n-i-1)
  if jdg > ulmt:
    print("No")
    exit()
for x,l in zip(ls,lmt):
  if x-l > bias:
    print("No")
    break
else:
  print("Yes")
import sys
from collections import defaultdict

def solve():
    input = sys.stdin.readline
    N, P = map(int, input().split())
    S = input().strip("\n")
    modSum = 0
    modSum = int(S[0]) % P
    modDict = defaultdict(int)
    ans = 0

    if P == 2 or P == 5:
        for i in range(N):
            if int(S[i]) % P == 0:
                ans += i + 1
        
    else:
        modDict[modSum[0]] += 1
        for i in range(1, N):
            modSum = ((modSum * 10) + int(S[i])) % P
            modDict[modSum] += 1

        for key in modDict:
            v = modDict[key]
            if key > 0: ans += v * (v - 1) // 2
            else: ans += v + (v * (v - 1) // 2)
    
    print(ans)

    return 0

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys

def solve():
    input = sys.stdin.readline
    N, P = map(int, input().split())
    S = list(input().strip("\n"))

    if P == 2 or P == 5:
        count = 0
        for i in range(N):
            s = int(S[N - 1 - i])
            if s % P == 0: count += N - i
        print(count)
    else:
        modDict = dict()
        modDict[0] = 1
        sSum = 0
        for i in range(N):
            s = int(S[N - 1 - i])
            sSum += s * pow(10, i, P)
            sSum %= P
            if sSum in modDict: modDict[sSum] += 1
            else: modDict[sSum] = 1
        count = 0
        for key in modDict:
            count += modDict[key] * (modDict[key] - 1) // 2
        print(count)
            

    return 0

if __name__ == "__main__":
    solve()
R = int(input())

if R < 1200:
    print('ABC')
elif 1200 <= R < 2800
    print('ARC')
else:
    print('AGC')

### FIXED CODE ###

R = int(input())

if R < 1200:
    print('ABC')
elif 1200 <= R < 2800:
    print('ARC')
else:
    print('AGC')
A, B, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
# 2次元配列
grid = []
for i in range(M):
    array = list(map(int, input().strip().split()))
    grid.append(array)
    
sum_fee = []
comb_pro = list(itertools.product(a, b))
for com in comb_pro:
    sum_fee.append(sum(com))

for l, m , n in grid:
    sum_fee.append(a[l-1] + b[m-1] - n)
    
print(min(sum_fee))

### FIXED CODE ###

import itertools
A, B, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

#2次元配列
grid = []
for i in range(M):
    array = list(map(int, input().strip().split()))
    grid.append(array)
    
sum_fee = []
a_min = min(a)
b_min = min(b)
sum_fee.append(a_min+b_min)

for l, m, n in grid:
    sum_fee.append(a[l-1] + b[m-1] - n)
    

print(min(sum_fee))
#!/usr/bin/env python3

def main():
    n = int(input())
    adjs = [[] for i in range(n)]
    for i in range(n - 1):
        u, v, w = map(int, input().split())
        adjs[u - 1].append((v - 1, w))
        adjs[v - 1].append((u - 1, w))
    colors = [None for i in range(n)]
    visited = [False for i in range(n)]
    dfs(0, 0, adjs, visited, colors)
    for i in range(n):
        print(colors[i])

def dfs(i, color, adjs, visited, colors):
    visited[i] = True
    colors[i] = color
    for v, w in adjs[i]:
        if visited[v]:
            continue
        dfs(v, (color + w) % 2, adjs, visited, colors)

if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

import sys

def main():
    sys.setrecursionlimit(10 ** 6)
    n = int(input())
    adjs = [[] for i in range(n)]
    for i in range(n - 1):
        u, v, w = map(int, input().split())
        adjs[u - 1].append((v - 1, w))
        adjs[v - 1].append((u - 1, w))
    colors = [None for i in range(n)]
    visited = [False for i in range(n)]
    dfs(0, 0, adjs, visited, colors)
    for i in range(n):
        print(colors[i])

def dfs(i, color, adjs, visited, colors):
    visited[i] = True
    colors[i] = color
    for v, w in adjs[i]:
        if visited[v]:
            continue
        dfs(v, (color + w) % 2, adjs, visited, colors)

if __name__ == "__main__":
    main()
import fractions

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

print(a * b / fracions.gcd(a * b))


### FIXED CODE ###

import fractions

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

print(a * b // fractions.gcd(a, b))
import sys 
from collections import deque
import numpy as np
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def R(x):
    r = round(x)
    if r+0.5 <= x:
        r += 1
    return int(r)

def main():
    tmp = deque(LI())
    n,k = tmp.popleft(),tmp.popleft()
    a = LI()
    for _ in range(k):
        table = np.zeros(n)
        for j in range(n):
            left = R(max(0,j-a[j]-0.5))
            right = int(min(n-1,j+a[j]+0.5))
            table[left:right+1] += 1
        a = table[:]
    for i in range(n):
        print(str(a[i])+' ',end='')
    return

if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
from itertools import accumulate

def solve(n,k,a):
    for _ in range(k):
        if a==[n]*n:    return a
        t = [0]*(n+1)
        for i,x in enumerate(a):
            t[max(0,i-x)] += 1
            t[min(n,i+x+1)] -=1
        a = list(accumulate(t))[:-1]
    return a

n,k = map(int,sys.stdin.readline().rstrip().split())
a = list(map(int,sys.stdin.readline().rstrip().split()))

print(*solve(n,k,a))
N,Q=map(int,input().split())
S=input()
for i in range(N):
  A.append(S[0:i+1].count("AC"))
for i in range(Q):
  l,r=map(int,input().split())
  print(A[r-1]-A[l-1])

### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
A=[0]
res=0
for i in range(N):
  if i !=0:
    if S[i-1]=="A" and S[i]=="C":
      res+=1
      A.append(res)
    else:
      A.append(res)
for i in range(Q):
  l,r=map(int,input().split())
  print(A[r-1]-A[l-1])
n, m = map(int, input().split())
ship = []
for i in range(m):
    ship.append(tuple(map(int, input().split())))

ship.sort()
for s in ship:
    if s[0] != 1 and s[1] != n:
        ship.remove(s)

i = 0

while ship[i][0]:
    i += 1

for j in range(i):
    for k in range(i+1, m):
        if ship[j][1] == ship[k][0]:
            print("POSSIBLE")
            exit()

print("IMPOSSIBLE")


### FIXED CODE ###

n, m = map(int, input().split())
ship_1 = [False]*(n+1)
ship_n = [False]*(n+1)
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        ship_1[b] = True
    elif b == n:
        ship_n[a] = True

for i in range(len(ship_1)):
    if ship_1[i] and ship_n[i]:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")
def StrConv(S, T, F, C):
  ans = ''
  if T == '1':
    #ans = S[::-1]
  else:
    if F == '1':
      ans = C + S
    else:
      ans = S + C
  return ans
  
#パラメータの取得
S = input()
Q = int(input())
dumy = '|' #仮の文字列くみ上げ変数
cnt = 0   #反転回数カウンタ

#処理実体処理
for i in range(Q):
  tmp = str(input())
  #Q各行の値を、T, F, Cに基づいて処理
  if tmp[0] == '1':
    T = tmp[0]
    F = '-'
    C = '-'
    cnt += 1
  else:
    T, F, C = tmp.split(' ')
  #変換処理本体
  dumy = StrConv(dumy, T, F, C)

#文字列結合処理
if (cnt % 2) == 0:
  ans = dumy[0:dumy.find('|')] + S + dumy[dumy.find('|')+1:]
else:
  ans = dumy[0:dumy.find('|')] + S[::-1] + dumy[dumy.find('|')+1:]
print(ans)


### FIXED CODE ###

#パラメータの取得
S = input()
Q = int(input())
cnt = 0   #反転回数カウンタ
head = ''
tail = ''

#処理実体処理
for i in range(Q):
  tmp = str(input())
  #Q各行の値を、T, F, Cに基づいて処理
  if tmp[0] == '1':
    cnt += 1
  else:
    T, F, C = tmp.split(' ')
    if cnt % 2 == 1:
      if F == '1':
        tail = tail + C
      else:
        head = C + head
    else:
      if F == '1':
        head = C + head
      else:
        tail = tail + C
    #cnt = 0
  #print('head=',head)
  #print('tail=',tail)

#print('cnt=',cnt)
if cnt % 2 == 0:
  ans = head + S + tail
else:
  ans = tail[::-1] + S[::-1] + head[::-1]
print(ans)
import math
math.pi
R=int(input())
print(R*2*pi)

### FIXED CODE ###

import math
R=int(input())
print(R*2*math.pi)
N = int(raw_input())
S = list(raw_input())
D = [[0, 0]]
W = [0] * (N+2)
E = [0] * (N+2)
for i in range(N):
 if S[i] == 'W':
  W[i+1] = W[i]+1
for i in range(N)[::-1]:
 if S[i] == 'E':
  E[i] = E[i+1]+1
ans = N+1
for w, e in zip(W, E):
  if w+e < ans:
  ans = w+e
print ans


### FIXED CODE ###

N = int(raw_input())
S = list(raw_input())
S = ['X']+S+['X']
D = [[0, 0]]
W = [0] * (N+2)
E = [0] * (N+2)
for i in range(1,N+2):
 W[i] = W[i-1]+(1 if S[i-1]== 'W' else 0)
for i in range(N+1)[::-1]:
 E[i] = E[i+1]+(1 if S[i+1]== 'E' else 0)
ans = N
for i in range(N):
  if W[i+1]+E[i+1] < ans:
   ans = W[i+1]+E[i+1]
print ans
i = 0
j = i+1
ans = 0
while i != n - 1:
    ans = (ans+(a[i] * a[j])) % 1000000007
    j += 1
    if j == n:
        i += 1
        j = i + 1
print(ans)


### FIXED CODE ###

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

sum = [0 for i in range(n+1)]
for i in range(n - 1, -1, -1):
    sum[i] = sum[i + 1] + a[i]
ans = 0
for i in range(n):
    ans = (ans+(a[i]*sum[i+1])) % 1000000007
print(ans)
A,B=input().split()

if (int(A)+int(B))%2 == 1:
    print(IMPOSSIBLE)
else:
    print(int((int(A)+int(B))/2))


### FIXED CODE ###

A,B=input().split()

if (int(A)+int(B))%2 == 1:
    print("IMPOSSIBLE")
else:
    print(int((int(A)+int(B))/2))
a,b,c,x = map(int,[input() for i in range(4)])
c = 0
for i in range(a+1):
    for j in range(b+1):
        for n in range(c+1):
            if t = i*500 + j*100 + n*50 == x:
                c +=1
print(c)

### FIXED CODE ###

a, b, c, x = map(int, [input() for i in range(4)])
count = 0
for i in range(a+1):
    for j in range(b+1):
        for k in range(c+1):
            if i*500 + j*100 + k*50 == x:
                count+=1
print(count)
A,B,C=map(int,input().split())
cnt=0
for i in range(C):
    if B-=A>=0:
        cnt+=1
    else:
        break
print(cnt)  

### FIXED CODE ###

A,B,C=map(int,input().split())
cnt=0
for i in range(C):
    B-=A
    if B>=0:
        cnt+=1
    else:
        break
print(cnt)
from math import gcd
from functools import reduce
def lcm(a,b):
    return (a*b)//gcd(a,b)

def lcm_list(numbers):
    return reduce(lcm,numbers,1)

n=int(input())
a=list(map(int,input().split()))
b=lcm_list(a)
y=0
for x in a:
    y+=x-1
print(y)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
y=0
for x in a:
    y+=x-1
print(y)
import math
def comb(N, r):
    return math.factorial(N) // (math.factorial(N - r) * math.factorial(r))

for i in range(num):
    A=target.copy()
    A.pop(i)
    out=0
    for j in set(A):
        if A.count(j)>1:
            base = comb(A.count(j),2)
            out=out+base
    print(out)

### FIXED CODE ###

import collections
n = int(input())
arr = list(map(int, input().split()))
cnt = collections.Counter(arr)
total = 0
for i in cnt.keys():
  patern = cnt[i]*(cnt[i]-1)//2
  total += patern
for j in range(n):
  tmp = total
  total -= cnt[arr[j]]*(cnt[arr[j]]-1)//2
  total += (cnt[arr[j]]-1)*(cnt[arr[j]]-2)//2
  print(total)
  total = tmp
v

### FIXED CODE ###

n=int(input())
a = list(map(int,input().split()))
cnt=0
for i in range(n):
    while a[i]%2==0:
        a[i]=a[i]//2
        cnt+=1
print(cnt)
#!/usr/bin/env python3
import sys
try:
    from math import gcd
except Exception:
    from fraction import gcd

YES = "Yes"  # type: str
NO = "No"  # type: str

def solve(N: int):
    return NO if bool(N % (sum([int(v) for v in str(N)]))) else YES


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    result = solve(N)
    print(result)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
try:
    from math import gcd
except Exception:
    from fractions import gcd

YES = "Yes"  # type: str
NO = "No"  # type: str

def solve(N: int):
    return NO if bool(N % (sum([int(v) for v in str(N)]))) else YES


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    result = solve(N)
    print(result)

if __name__ == '__main__':
    main()
a = 0
N = input()
n = int(N)
for i in range(1,n+1):
    if i % 5 != 0 and i % 3 != 0:
        a = a + i
    else:
        continue
return(a)

### FIXED CODE ###

a = 0
N = input()
n = int(N)
for i in range(1,n+1):
    if i % 5 != 0 and i % 3 != 0:
        a = a + i
    else:
        continue
print(a)
N = int(input())

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

print(sum 1/x for x in A)

### FIXED CODE ###

N = int(input())

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

print(1/sum(1/x for x in A))
a,b=map(int,input().split())
c=list(map(int,input().split()))
d=c.sort()
print(d)
ans=0
for i in range(0,b):
 ans+=d[i]

print(ans)

### FIXED CODE ###

a,b=map(int,input().split())
c=list(map(int,input().split()))
d=sorted(c)
ans=0
for i in range(0,b):
 ans+=d[i]
print(ans)
N, K = list(map(int,input().split()))
ab = [list(map(int, input().split())) for _ in range(N - 1)]
MOD = 1000000007

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

for i in range(N - 1):
    tree[ab[i][0] - 1].append(ab[i][1] - 1)
    tree[ab[i][1] - 1].append(ab[i][0] - 1)


ans = K * (K - 1) % MOD

def f(x, y):
    global ans
    count = 2
    for i in range(len(tree[y])):
        if tree[y][i] != x:
            f(y, tree[y][i])
            ans = ans * (K - count) % MOD
            count += 1


first = 0
for i in range(N):
    if len(tree[i]) == 1:
        first = i
        break
f(first, tree[first][0])


print(ans)



### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000000)
N, K = list(map(int,input().split()))
ab = [list(map(int, input().split())) for _ in range(N - 1)]
MOD = 1000000007
if N == 1:
    print(K)
    exit()

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

for i in range(N - 1):
    tree[ab[i][0] - 1].append(ab[i][1] - 1)
    tree[ab[i][1] - 1].append(ab[i][0] - 1)


ans = K * (K - 1) % MOD

def f(x, y):
    global ans
    count = 2
    for i in range(len(tree[y])):
        if tree[y][i] != x:
            f(y, tree[y][i])
            ans = ans * (K - count) % MOD
            count += 1


first = 0
for i in range(N):
    if len(tree[i]) == 1:
        first = i
        break
f(first, tree[first][0])


print(ans)
from queue import Queue

def bfs(start):
    global visited, time
    while start.qsize() > 0:
        hh, ww = start.get()
        time[hh][ww] = calc_min(hh, ww)
        visited[hh][ww] = 1
        h_w_list = [[hh + 1, ww], [hh, ww + 1], [hh - 1, ww], [hh, ww - 1]]
        for h_, w_ in h_w_list:
            if (h_ in range(h)) & (w_ in range(w)):
                if visited[h_][w_] == 0:
                    start.put([h_, w_])

def calc_min(hh, ww):
    h_w_list = [[hh + 1, ww], [hh, ww + 1], [hh - 1, ww], [hh, ww - 1]]
    for h_, w_ in h_w_list:
        if (h_ in range(h)) & (w_ in range(w)):
            min_num = min(time[hh][ww], time[h_][w_] + 1)
    return min_num

inf = 10 ** 9
h, w = map(int, input().split())
a = []
for hh in range(h):
    a.append(list(input()))
time = [[inf for _ in range(w)] for _ in range(h)]
start = Queue()
visited = [[0 for _ in range(w)] for _ in range(h)]
for hh in range(h):
    for ww in range(w):
        if a[hh][ww] == "#":
            start.put([hh, ww])
            time[hh][ww] = 0
bfs(start)
ans = max([max(c) for c in time])
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

H,W = map(int,input().split())
INF = 10**18
q = []

visited = [[True]*(W+2)]
visited += [[True] + [x == '#' for x in input().rstrip()] + [True] for _ in range(H)]
visited.append([True]*(W+2))
for i in range(1,H+1):
  for j in range(1,W+1):
    if visited[i][j]:
      q.append((i,j))

moves = [(0,1),(0,-1),(1,0),(-1,0)] #全方向調べる

ans = -1
while q:
  qq = []
  ans += 1
  for x,y in q:
    if not visited[x-1][y]:
      visited[x-1][y] = True
      qq.append((x-1,y))
    if not visited[x+1][y]:
      visited[x+1][y] = True
      qq.append((x+1,y))
    if not visited[x][y-1]:
      visited[x][y-1] = True
      qq.append((x,y-1))
    if not visited[x][y+1]:
      visited[x][y+1] = True
      qq.append((x,y+1))
  q = qq
  
print(ans)
S = int(input())

if S == "SUN":
    print(7)
elif S == "MON":
    print(6)
elif S == "TUE":
    print(5)
elif S == "WED":
    print(4)
elif S == "THU":
    print(3)
elif S == "FRI":
    print(2)
else*
    print(1)


### FIXED CODE ###

S = str(input())

if S == "SUN":
    print(7)
elif S == "MON":
    print(6)
elif S == "TUE":
    print(5)
elif S == "WED":
    print(4)
elif S == "THU":
    print(3)
elif S == "FRI":
    print(2)
else:
    print(1)