Harryxun/stf_run huggingface dataset:
def factorization(n):
    pf_cnt = {}
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i == 0:
            cnt = 0
            while temp%i == 0:
                cnt += 1
                temp //= i
            pf_cnt[i] = cnt

    if temp != 1: pf_cnt[temp] = 1
    if not pf_cnt: pf_cnt[n] = 1

    return pf_cnt


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

al_fac = []
for a in al:
    fac = factorization(a)
    al_fac.append(fac)

gcd_l = [1]*n
gcd_r = [1]*n

gcd_l[0] = al_fac[0]
gcd_r[-1] = al_fac[-1]

for i in range(1,n):
    next_l = al_fac[i]
    next_l_gcd = {}
    for prime,cnt in next_l.items():
        if prime in al_fac[i-1]:
            next_l_gcd[prime] = min(cnt, al_fac[i-1][prime])
    gcd_l[i] = next_l_gcd

    next_r = al_fac[n-i-1]
    next_r_gcd = {}
    for prime,cnt in next_r.items():
        if prime in al_fac[n-i]:
            next_r_gcd[prime] = min(cnt, al_fac[n-i][prime])
    gcd_r[n-i-1] = next_r_gcd

    ans = 1
    for i in range(1,n-1):
        curr_gcd = 1
        for prime,cnt in gcd_l[i-1].items():
            if prime in gcd_r[i+1]:
                min_cnt = min(cnt, gcd_r[i+1][prime])
                curr_gcd *= prime**min_cnt
        ans = max(ans, curr_gcd)
    
    # i = 0
    curr_gcd = 1
    for prime,cnt in gcd_r[1].items():
        curr_gcd *= (prime**cnt)
    ans = max(ans, curr_gcd)

    # i = n-1
    curr_gcd = 1
    for prime,cnt in gcd_l[n-2].items():
        curr_gcd *= (prime**cnt)
    ans = max(ans, curr_gcd)

# print(al_fac)
# print(gcd_l)
# print(gcd_r)
print(ans)

### FIXED CODE ###

from fractions import gcd

def factorization(n):
    pf_cnt = {}
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i == 0:
            cnt = 0
            while temp%i == 0:
                cnt += 1
                temp //= i
            pf_cnt[i] = cnt

    if temp != 1: pf_cnt[temp] = 1
    if not pf_cnt: pf_cnt[n] = 1
    return pf_cnt


def main():
    n = int(input())
    al = list(map(int, input().split()))

    gcd_l = [1]*n
    gcd_r = [1]*n

    gcd_l[0] = al[0]
    gcd_r[-1] = al[-1]

    for i in range(1,n):
        next_l = al[i]
        gcd_l[i] = gcd(next_l, gcd_l[i-1])

        next_r = al[n-i-1]
        gcd_r[n-i-1] = gcd(next_r, gcd_r[n-i])


    ans = max(gcd_r[1], gcd_l[n-2])
    for i in range(1,n-1):
        curr_gcd = gcd(gcd_l[i-1], gcd_r[i+1])
        ans = max(ans, curr_gcd)

    print(ans)


if __name__ == "__main__":
    main()
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
import numpy as np
# from scipy.misc import comb

# 再帰がやばいとき
# import sys
# sys.setrecursionlimit(10**9)

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

def check(h, x, A, B):
    h = [ hi - B * x for hi in h ]
    c = 0
    for hi in h:
        if hi <= 0:
            continue
        c += math.ceil(hi/(A-B))
    return c <= x

def main():
    N, A, B = l_inpl()
    h = line_inpl(N)

    l, r = 0, max(h)//B + 1000
    while l + 1 != r:
        mid = (l+r) // 2
        if check(h, mid, A, B):
            r = mid
        else:
            l = mid
    
    print(r)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

# 再帰がやばいとき
# import sys
# sys.setrecursionlimit(10**9)

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

def check(h, x, A, B):
    h = [ hi - B * x for hi in h ]
    c = 0
    for hi in h:
        if hi <= 0:
            continue
        c += math.ceil(hi/(A-B))
    return c <= x

def main():
    N, A, B = l_inpl()
    h = line_inpl(N)

    l, r = 0, max(h)//B + 1000
    while l + 1 != r:
        mid = (l+r) // 2
        if check(h, mid, A, B):
            r = mid
        else:
            l = mid
    
    print(r)

if __name__ == "__main__":
    main()
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


def argsort(li, key=None, reverse=False):
    return [i for _, i in sorted(
        [(a, i) for i, a in enumerate(li)], key=(lambda t: key(t[0])) if key else None, reverse=reverse
    )]


N, M = list(map(int, sys.stdin.buffer.readline().split()))
D = list(map(int, sys.stdin.buffer.readline().split()))
VU = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]

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

for i, (v, u) in enumerate(VU):
    v -= 1
    u -= 1
    graph[v].append(u)
    graph[u].append(v)

edges = {}
ans = [0] * M
colors = [None] * M
for v in argsort(D):
    d = D[v]
    for u in graph[v]:
        if colors[u] is not None:
            edges[v, u] = d
            colors[v] = not colors[u]
            break
        if D[u] == d:
            edges[v, u] = d
            colors[v] = True
            colors[u] = False
            break
    if colors[u] is None:
        print(-1)
        exit()
S = ''
for c in colors:
    S += 'B' if c else 'W'
ans = []
for v, u in VU:
    v -= 1
    u -= 1
    if (v, u) in edges:
        ans.append(edges[v, u])
    elif (u, v) in edges:
        ans.append(edges[u, v])
    else:
        ans.append(10 ** 9)

print(S)
print(*ans, sep='\n')


### FIXED CODE ###

import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


def argsort(li, key=None, reverse=False):
    return [i for _, i in sorted(
        [(a, i) for i, a in enumerate(li)], key=(lambda t: key(t[0])) if key else None, reverse=reverse
    )]


N, M = list(map(int, sys.stdin.buffer.readline().split()))
D = list(map(int, sys.stdin.buffer.readline().split()))
VU = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]

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

for i, (v, u) in enumerate(VU):
    v -= 1
    u -= 1
    graph[v].append(u)
    graph[u].append(v)

edges = {}
colors = [None] * N
for v in argsort(D):
    d = D[v]
    if colors[v] is not None:
        continue
    for u in graph[v]:
        if colors[u] is not None:
            edges[v, u] = d
            colors[v] = not colors[u]
            break
        if D[u] == d:
            edges[v, u] = d
            colors[v] = True
            colors[u] = False
            break
    if colors[u] is None:
        print(-1)
        exit()
S = ''
for c in colors:
    S += 'B' if c else 'W'
ans = []
for v, u in VU:
    v -= 1
    u -= 1
    if (v, u) in edges:
        ans.append(edges[v, u])
    elif (u, v) in edges:
        ans.append(edges[u, v])
    else:
        ans.append(10 ** 9)

print(S)
print(*ans, sep='\n')
import sympy
from sympy import nextprime
x=int(input())
print(nextprime(x))

### FIXED CODE ###

x=int(input())

def isprime(n):
    if n==1:
        return False
    else:
        for i in range(2,int(n**0.5)+1):
            if n%i==0:
                return False
        return True
        
while True:
    if isprime(x):
        print(x)
        exit()
    else:
        x+=1
N, A = int(input()), list(map(int, input().split()))
X=[]
for i in range(1, N+1):
  P = A.index(i) + 1
  X.append(P)
print(' '.join([str(x) for x in X]))

### FIXED CODE ###

a = int(input())
if a % 2 == 0:
  print(a/(2*a))
else:
  print((a+1)/(2*a))
A = map(int, input())
B = map(int, input())
A, B = list(A)[0], list(B)[0]

if A > 8 or B > 8:
    print(':(')
else:
    print('Yay!')

### FIXED CODE ###

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

if A > 8 or B > 8:
    print(':(')
else:
    print('Yay!')
from sys import stdin
from collections import deque
import heapq

N, K = [int(x) for x in stdin.readline().rstrip().split()]
P = [int(x) for x in stdin.readline().rstrip().split()]

ans = 0
Q_max = [-x for x in P[:K]]
Q_min = [x for x in P[:K]]
heapq.heapify(Q_min)
heapq.heapify(Q_max)
D = deque([x for x in P[:K]])
oc = 0
ordered_twice = False

for i in range(len(D) - 1):
    if D[i] <= D[i + 1]:
        oc += 1

for i in range(N - K + 1):
    if i == 0:
        ans += 1
        if oc == K - 1:
            ordered_twice = True
    else:
        D.popleft()
        D.append(P[i + K - 1])
        if P[i - 1] <= D[0]:
            oc -= 1
        if D[K - 2] <= D[K - 1]:
            oc += 1
        if oc == K - 1:
            if not ordered_twice:
                ordered_twice = True
                if P[i - 1] > Q_min[0] or D[K - 1] < -Q_max[0]:
                    ans += 1
        else:
            if P[i - 1] > Q_min[0] or D[K - 1] < -Q_max[0]:
                ans += 1
        if P[i - 1] == Q_min[0]:
            heapq.heappop(Q_min)
        if P[i - 1] == -Q_max[0]:
            heapq.heappop(Q_max)
        if D[K - 1] >= -Q_max[0]:
            heapq.heappush(Q_max, -D[K - 1])
        if D[K - 1] <= Q_min[0]:
            heapq.heappush(Q_min, D[K - 1])

print(ans)

### FIXED CODE ###

from sys import stdin
from collections import deque

N, K = [int(x) for x in stdin.readline().rstrip().split()]
P = [int(x) for x in stdin.readline().rstrip().split()]

ans = N - K + 1

D = deque([x for x in P[:K]])
oc = 0
ordered_twice = False

for i in range(len(D) - 1):
    if D[i] <= D[i + 1]:
        oc += 1

Q = deque([])
Q_min = []
Q_max = []

for i in range(N):
    while len(Q) > 0 and P[Q[len(Q) - 1]] >= P[i]:
        Q.pop()
    Q.append(i)
    if Q[len(Q) - 1] >= K - 1:
        Q_min.append(P[Q[0]])
        if Q[0] == i + 1 - K:
            Q.popleft()

PP = [-x for x in P]
Q = deque([])

for i in range(N):
    while len(Q) > 0 and PP[Q[len(Q) - 1]] >= PP[i]:
        Q.pop()
    Q.append(i)
    if Q[len(Q) - 1] >= K - 1:
        Q_max.append(-PP[Q[0]])
        if Q[0] == i + 1 - K:
            Q.popleft()

for i in range(N - K + 1):
    if i > 0:
        D.popleft()
        D.append(P[i + K - 1])
        if P[i - 1] <= D[0]:
            oc -= 1
        if D[K - 2] <= D[K - 1]:
            oc += 1

        if (Q_min[i - 1] == P[i - 1] and Q_max[i] == D[-1]) or (oc == K - 1 and ordered_twice):
            ans -= 1

    if oc == K - 1:
        ordered_twice = True

print(ans)
a,b,c=input().split()
a=list(a)
b=list(b)
c=list(c)
if a[len(a)]==b[0] and b[len(b)]==c[0]:
  print('YES')
else:
  print('NO')

### FIXED CODE ###

a,b,c=input().split()
a=list(a)
b=list(b)
c=list(c)
if a[len(a)-1]==b[0] and b[len(b)-1]==c[0]:
  print('YES')
else:
  print('NO')
p,r=input,range
A=sum([list(map(int,p().split()))for _ in r(3)],[])
b=[int(p())for _ in r(int(p()))]
print('YNeos'[[v for v in[7,56,73,84,146,273,292,448]if sum(1<<i for i in r(9)if A[i]in b)&v==v]::2])

### FIXED CODE ###

A = [list(map(int, input().split())) for _ in range(3)]
N = int(input())
b = [int(input()) for _ in range(N)]

field = 0
for v in b:
	for i in range(9):
		if A[i // 3][i % 3] == v:
			field = field | (1 << i)
ans = False
for v in sum([[273,84],sum([[73<<i,7<<i*3]for i in range(3)],[])],[]):
  ans = ans or field&v==v;
print('Yes' if ans else 'No')
from fractions import Fraction as fa

n = int(input())
arr= [int(x) for x in input().split()]
ans = 0
for i in arr:
  ans += fa(1,i)
  
ans = str(ans).split('/')

print(int(ans[1])/int(ans[0]))

### FIXED CODE ###

n = int(input())
arr= [1/int(x) for x in input().split()]
print(1/sum(arr))
N = int(input())

a_list = []

for i in range(N):
  a_list.append(list(input()))
  
a_num = len(set(a_list))

print(a_num)

### FIXED CODE ###

N = int(input())
a_list=[]
for i in range(N):
  a_list.append(input())
  
a_set = set(a_list)

a_num = len(a_set)

print(a_num)
import sys
sys.setrecursionlimit(10**7)

n = int(input())

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

ans = [0]*(N-1)
def col(now,color):
    c = 1
    for (b,j) in graph[now]:
        if c == color:
            c += 1
    ans[j] = c
    col(b,c)
    c += 1

col(0,0)
print(max(ans))
[print(a) for a in ans]


### FIXED CODE ###

s = str(input())

if s == 'SUN':
    print(7)
elif s == 'SAT':
    print(1)
elif s == 'FRI':
    print(2)
elif s == 'THU':
    print(3)
elif s == 'WED':
    print(4)
elif s == 'TUE':
    print(5)
else:
    print(6)
import math
a, b, c = map(int, input().split())
print("YES" if c%(math.gcd(a,b)) == 0 else "NO")

### FIXED CODE ###

import fractions
a, b, c = map(int, input().split())
print("YES" if c%(fractions.gcd(a,b)) == 0 else "NO")
s=input()
a=-1
z=0
for i in range(s.len()):
  if a<0 and s[i]=='A':a=i
  if s[i]=='Z':z=i
print(z-a+1)

### FIXED CODE ###

s=input()
a=-1
z=0
for i in range(len(s)):
  if a<0 and s[i]=='A':a=i
  if s[i]=='Z':z=i
print(z-a+1)
def rec(i):
    if dp[i] < INF:
        return dp[i]
    if i == 0:
        return 0

    res = INF

    res = min(res, rec(i-1) + abs(h[i] - h[i-1]))
    if i > 1:
        res = min(res, rec(i-2) + abs(h[i] - h[i-2]))

    dp[i] = res
    return dp[i]

INF = 105 * 10**7
dp = [INF] * 100010

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

print(rec(N-1))


### FIXED CODE ###

INF = 105 * 10**7
dp = [INF] * 100010

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

dp[0] = 0

for i in range(1, N):
    dp[i] = min(dp[i], dp[i-1] + abs(h[i] - h[i-1]))
    if i > 1:
        dp[i] = min(dp[i], dp[i-2] + abs(h[i] - h[i-2]))

print(dp[N-1])
rom collections import deque
 
K = int(input())
que = deque([i for i in range(1, 10)])
lunlun = []
 
while que:
    num = que.pop()
    lunlun.append(num)
    for i in range(10):
        if abs(int(str(num)[-1]) - i) <= 1:
            cand = int(str(num) + str(i))
            if cand < 10000000000:
                que.append(cand)
 
lunlun.sort()
print(sorted(lunlun)[K - 1])

### FIXED CODE ###

from collections import deque

K = int(input())
que = deque([i for i in range(1, 10)])
lunlun = []

while que:
    num = que.pop()
    lunlun.append(num)
    for i in range(10):
        if abs(int(str(num)[-1]) - i) <= 1:
            cand = int(str(num) + str(i))
            if cand < 10000000000:
                que.append(cand)

lunlun.sort()
print(sorted(lunlun)[K - 1])
n=int(input())
l=list(map(int,input().split()))
xl=list(reversed(l))
g=[]
a=1
k=0
f=0
if n==0:
  print(l(0))
for i in xl:
  k+=i
  g.append(k)
g.reverse()
for i in range(len(g)):
  if a<=0:
    f+=1
    break
  if g[i]>=a:
    g[i]=a
  a-=l[i]
  a*=2
if f==0 and n!=0:
  print(sum(g))
elif n==0:
  if l[0]==0:
    print(0)
  elif l[0]==1:
    print(1)
  else:
    print(-1)
else:
  print(-1)

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
xl=list(reversed(l))
g=[]
a=1
k=0
f=0
for i in xl:
  k+=i
  g.append(k)
g.reverse()
for i in range(len(g)):
  if g[i]>=a:
    g[i]=a
  a-=l[i]
  a*=2
  if a<=0 and i!=len(g)-1:
    f+=1
    break
  if a<0 and i==len(g)-1:
    f+=1
    break
if f==0 and n!=0:
  print(sum(g))
elif n==0:
  if l[0]==1:
    print(1)
  else:
    print(-1)
else:
  print(-1)
import math
a,b=map(int,input().split())
print(a*b//math.gcd(a,b))

### FIXED CODE ###

import fractions
a,b=map(int,input().split())
print(a*b//fractions.gcd(a,b))
class int(int):  
  def times(self, callback):
    for times in range(0,self):
      callback()

class list(list):
  def maps(self, callback):
    return list(map(callback, self))

  def each(self, callback):
    list(map(callback, self))
    return self

  # index will sent to the function as a second parameter.
  def each_with_index(self,callback):
    list(map(callback, self, range(0,len(self))))
    return self

# Make sure you initialize object with class name.
# Ex: int(10).times, array = list([1,2,3,4,5])

target, length = input().split()
target = int(target)
length = int(length)
o_nums = list(input().split())

if length == 0:
  def convert(arg):
    return int(arg)

  o_nums = o_nums.maps(convert)
  diffs = list()
  nums = list()
  for exclude_num in range(min(o_nums), max(o_nums)+1):
    if exclude_num in o_nums:
      continue
    else:
      nums.append(exclude_num)

  for num in nums:
    diffs.append(target - num)

  def absm(arg):
    return abs(arg)

  diffs_abs = diffs.maps(absm)
  smallest_diff_index = diffs_abs.index(min(diffs_abs)) #絶対値が最も小さいもの

  if -(diffs_abs[smallest_diff_index]) in diffs: # ターゲットよりも小さい、最も差分が小さい値を探す
    index = diffs.index(-(diffs_abs[smallest_diff_index]))
    print(nums[index])
  else:
    print(nums[smallest_diff_index])

elif length == 1:
  print(o_nums[0])

else:
  print(target)

### FIXED CODE ###

class int(int):  
  def times(self, callback):
    for times in range(0,self):
      callback()

class list(list):
  def maps(self, callback):
    return list(map(callback, self))

  def each(self, callback):
    list(map(callback, self))
    return self

  # index will sent to the function as a second parameter.
  def each_with_index(self,callback):
    list(map(callback, self, range(0,len(self))))
    return self

# Make sure you initialize object with class name.
# Ex: int(10).times, array = list([1,2,3,4,5])

target, length = input().split()
target = int(target)
length = int(length)
nums = list(input().split())

def convert(arg):
    return int(arg)
nums = nums.maps(convert)

for i in range(0,101):
  a = target - i
  if a not in nums:
    print(a)
    exit()

  b = target + i
  if b not in nums:
    print(b)
    exit()
a,b,c=map(int,input().split())
n=0
for i in range(a,b+1):if c%i==0:n+=1
print(n)

### FIXED CODE ###

a,b,c=map(int,input().split())
print(sum(c%i==0 for i in range(a,b+1)))
import random
A, B = map(int, input().split())
r = random.randrange(5)
if r == 0:
    print(1/0)
elif r == 1:
    print(A+B)
elif r == 2:
    while True:
        B += 1
else:
    X = []
    for i in range(10**6):
	    X += [a for a in range(1000)]

### FIXED CODE ###

A, B = map(int, input().split())
print(max(A*2-1,A+B,B*2-1))
l = ["Sunny", "Cloudy", "Rainy"]
w = input()

if l.index(w) = 2:
    print("Sunny")

else:
    print(l[l.index(w) + 1])

### FIXED CODE ###

l = ["Sunny", "Cloudy", "Rainy"]
w = input()

if l.index(w) == 2:
    print("Sunny")

else:
    print(l[l.index(w) + 1])
a=int(input())
b=int(input())
if a!=1 and b!=1:
    print(1)
elif a!=2 and b!=1:
    print(2)
else a!=3 and b!=3:
    print(3)

### FIXED CODE ###

a=int(input())
b=int(input())
if a!=1 and b!=1:
    print(1)
elif a!=2 and b!=2:
    print(2)
elif a!=3 and b!=3:
    print(3)
N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]

def perm(a, b):
    s = 1
    for i in range(a-b+1, a+1):
        s *= i
    return s

if N == 1:
    print(K)
else:
    mod = 1000000007
    d = {}
    for a, b in links:
        if a in d:
            d[a].append(b)
        elif b in d:
            d[b].append(a)
        else:
            d[a].append(b)
    start = links[0][0]
    b = len(d[start])
    if K - 1 < b:
        print(0)
    else:
        ans = K * perm(K - 1, b)
        root = d[start]
        a = K - 2
        while True:
            children = []
            for i in root:
                if i in d:
                    b = len(d[i])
                    if a < b:
                        print(0)
                        break
                    ans *= perm(a, b)
                    children.extend(d[i])
            else:
                if children == []:
                    print(ans % mod)
                    break
                root = children
                continue
            break

### FIXED CODE ###

N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)
a, b, x = map(int, input().split())
s = set()
for i in [j for j in range(a, min(b + 1, a + x))] :
  print(i)
  s.add(i)
for i in [j for j in range(max(a, b - x + 1), b + 1)] :
  if i not in s:
    print(i)


### FIXED CODE ###

print(["No","Yes"]["".join(sorted(input()))=="abc"])
N, A, B = map(int, input().split())

counter = [0 for _ in range(N)]
ans = 0
for i in range(N):
    string = str(i)
    for j in range(len(str)):
        counter[i] += string[j]
    if(counter[i]>=A && counter[i]<=B):
        ans += i
print(ans)

### FIXED CODE ###

N, A, B = map(int, input().split())
ans = 0

for i in range(1, N+1):
    num_sum = 0
    for j in str(i):
        num_sum += int(j)
    if A<= num_sum <= B:
        ans += i

print(ans)
n = int(input())
A = list(map(int,input().split()))

dic = [False]*7

cnt = 0

for i in range(n):
  tmp = A[i] // 400
  if(tmp >= 8):
    cnt += 1
  else:
    dic[tmp] = True
  
print(sum(dic))
print(sum(dic) + cnt)

### FIXED CODE ###

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

dic = [False]*8

cnt = 0

for i in range(n):
  tmp = A[i] // 400
  if(tmp >= 8):
    cnt += 1
  else:
    dic[tmp] = True
if(sum(dic) == 0 and cnt > 0):
  print('1 ' + str(cnt))
else:
  print(str(sum(dic)) + ' ' + str(sum(dic) + cnt))
s = input()
    
if s[0] != 'A' or s[1].islower() == False or s[-1].islower() == False:
    print('WA')
elif s[2:-1].count('C') != 1:
    print('WA')
else:
    #and s[3:-2].islower() and
    for i in range(3, len(s)-2):
        if s[i].islower():
            flag = 'AC'
        else:
            flag = 'WA'
            break
    print(flag)

### FIXED CODE ###

s = input()
    
if s[0] != 'A' or s[1].islower() == False or s[-1].islower() == False:
    print('WA')
elif s[2:-1].count('C') != 1:
    print('WA')
else:
    flag = 'AC'
    for i in range(3, len(s)-1):
        if s[i].islower() or s[i] == 'C':
            flag = 'AC'
        else:
            flag = 'WA'
            break
    print(flag)