Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
MOD = 10**9+7
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
if all(ai < 0 for ai in a):
    ans = 1
    if k & 1:
        for ai in a[-k:]:
            ans = ans * ai % MOD
    else:
        for ai in a[:k]:
            ans = ans * ai % MOD
elif n == k:
    ans = 1
    for ai in a:
        ans = ans * ai % MOD
else:
    ans = 1
    a.sort(key=abs, reverse=True)
    cneg = sum(ai < 0 for ai in a[:k])
    if cneg & 1 == 0:
        for ai in a[:k]:
            ans = ans * ai % MOD
    else:
        left = []
        cnt = 0
        for i in range(len(a)):
            if cneg == 1:
                if i < k - 1 and a[i] >= 0:
                    ans = ans * ai % MOD
                    cnt += 1
                else:
                    left.append(a[i])
            else:
                ans = ans * a[i] % MOD
                cnt += 1
                if a[i] < 0:
                    cneg -= 1
        r = k - cnt
        if r == 1:
            ans = ans * [ai for ai in left if ai >= 0][0] % MOD
        else:
            ngs = [ai for ai in left if ai < 0]
            pss = [ai for ai in left if ai >= 0]
            t = -1001001001001001001001
            if len(ngs) >= 2:
                t = ngs[0] * ngs[1]
            if len(pss) >= 2:
                t = max(t, pss[0] * pss[1])
            ans = ans * t % MOD
print(ans)




Fixed submission:
MOD = 10**9+7
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
if all(ai < 0 for ai in a):
    ans = 1
    if k & 1:
        for ai in a[-k:]:
            ans = ans * ai % MOD
    else:
        for ai in a[:k]:
            ans = ans * ai % MOD
elif n == k:
    ans = 1
    for ai in a:
        ans = ans * ai % MOD
else:
    ans = 1
    a.sort(key=abs, reverse=True)
    cneg = sum(ai < 0 for ai in a[:k])
    cpos = sum(ai >= 0 for ai in a[:k])
    if cneg & 1 == 0:
        for ai in a[:k]:
            ans = ans * ai % MOD
    else:
        left = []
        r = k
        for ai in a:
            if ai < 0 and cneg > 1:
                ans = ans * ai % MOD
                cneg -= 1
                r -= 1
            elif ai >= 0 and cpos > 1:
                ans = ans * ai % MOD
                cpos -= 1
                r -= 1
            else:
                left.append(ai)
        ngs = [ai for ai in left if ai < 0]
        pss = [ai for ai in left if ai >= 0]
        if r == 1:
            ans = ans * pss[0] % MOD
        else:
            t = -1001001001001001001001
            if len(ngs) >= 2:
                t = ngs[0] * ngs[1]
            if len(pss) >= 2:
                t = max(t, pss[0] * pss[1])
            ans = ans * t % MOD
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
mod = 10**9 + 7

fact_range = 10**6 * 2
facts = [1] * (fact_range + 1)
for i in range(0, fact_range):
    facts[i+1] = facts[i] * (i + 1) % mod

ifacts = [1] * (fact_range + 1)
ifacts[fact_range] = pow(facts[fact_range], mod - 2, mod)
for i in range(fact_range, 0, -1):
    ifacts[i-1] = ifacts[i] * i % mod

def comb(n, k):
    if k < 0 or n < k:
        return 0
    else:
        return facts[n] * ifacts[n-k] % mod * ifacts[k] % mod

k = int(input())
s = len(input())
ans = 0
for a in range(k + 1):
    ans += pow(25, a, mod) * pow(26, k-a, mod) % mod * comb(s-1+a, a)
    ans %= mod
print(ans)


Fixed submission:
mod = 10**9 + 7

fact_range = 10**6 * 2
facts = [1] * (fact_range + 1)
for i in range(0, fact_range):
    facts[i+1] = facts[i] * (i + 1) % mod

ifacts = [1] * (fact_range + 1)
ifacts[fact_range] = pow(facts[fact_range], mod - 2, mod)
for i in range(fact_range, 0, -1):
    ifacts[i-1] = ifacts[i] * i % mod

def comb(n, k):
    if k < 0 or n < k:
        return 0
    else:
        return facts[n] * ifacts[n-k] % mod * ifacts[k] % mod

k = int(input())
s = len(input())
ans = 0
for a in range(k + 1):
    ans += pow(25, a, mod) * pow(26, k-a, mod) % mod * comb(s-1+a, a)
    ans %= mod
print(ans)

Buggy python submission (verdict: Runtime Error):
mod = 10**9 + 7

fact_range = 10**6
facts = [1] * (fact_range + 1)
for i in range(0, fact_range):
    facts[i+1] = facts[i] * (i + 1) % mod

ifacts = [1] * (fact_range + 1)
ifacts[fact_range] = pow(facts[fact_range], mod - 2, mod)
for i in range(fact_range, 0, -1):
    ifacts[i-1] = ifacts[i] * i % mod

def comb(n, k):
    if k < 0 or n < k:
        return 0
    else:
        return facts[n] * ifacts[n-k] % mod * ifacts[k] % mod

k = int(input())
s = len(input())
ans = 0
for a in range(k + 1):
    ans += pow(25, a, mod) * pow(26, k-a, mod) % mod * comb(s-1+a, a)
    ans %= mod
print(ans)


Fixed submission:
mod = 10**9 + 7

fact_range = 10**6 * 2
facts = [1] * (fact_range + 1)
for i in range(0, fact_range):
    facts[i+1] = facts[i] * (i + 1) % mod

ifacts = [1] * (fact_range + 1)
ifacts[fact_range] = pow(facts[fact_range], mod - 2, mod)
for i in range(fact_range, 0, -1):
    ifacts[i-1] = ifacts[i] * i % mod

def comb(n, k):
    if k < 0 or n < k:
        return 0
    else:
        return facts[n] * ifacts[n-k] % mod * ifacts[k] % mod

k = int(input())
s = len(input())
ans = 0
for a in range(k + 1):
    ans += pow(25, a, mod) * pow(26, k-a, mod) % mod * comb(s-1+a, a)
    ans %= mod
print(ans)
Buggy python submission (verdict: Runtime Error):
d=[i:=0]*8**7
for j in[*open(0)][1].split():d[int(j)]+=1
while i<1e6:
 i+=1;j=i
 while j<1e6:j+=i;d[j]*=d[i]<1
print(d.count(1))

Fixed submission:
d = [0] * (10**6 + 1)
n = int(input())
for a in map(int, input().split()):
    d[a] += 1
ans = 0
for i in range(1, 10**6 + 1):
    if d[i] == 1:
        ans += 1
    if d[i] > 0:
        for j in range(i, 10**6 + 1, i):
            d[j] = 0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
d=[i:=0]*8**7
for j in[*open(0)][1].split():d[int(j)]+=1
while i<1e6:
 i+=1;j=i
 while j<1e6:j+=i;d[j]*=d[i]<1
print(d.count(1))

Fixed submission:
d = [0] * (10**6 + 1)
n = int(input())
for a in map(int, input().split()):
    d[a] += 1
ans = 0
for i in range(1, 10**6 + 1):
    if d[i] == 1:
        ans += 1
    if d[i] > 0:
        for j in range(i, 10**6 + 1, i):
            d[j] = 0
print(ans)

Buggy python submission (verdict: Runtime Error):
d=[i:=0]*8**7
for j in[*open(0)][1].split():d[int(j)]+=1
while i<1e6:
 i+=1;j=i
 while j<1e6:j+=i;d[j]*=d[i]<1
print(d.count(1))

Fixed submission:
d = [0] * (10**6 + 1)
n = int(input())
for a in map(int, input().split()):
    d[a] += 1
ans = 0
for i in range(1, 10**6 + 1):
    if d[i] == 1:
        ans += 1
    if d[i] > 0:
        for j in range(i, 10**6 + 1, i):
            d[j] = 0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
d=[0]*8**7
for i in[*open(0)][1].split():d[int(i)]+=1
i=r=0
while i<1e6:
 i+=1;r+=d[i]==1;j=i
 while j<1e6:j+=i;d[j]&=d[i]<1
print(r)

Fixed submission:
d = [0] * (10**6 + 1)
n = int(input())
for a in map(int, input().split()):
    d[a] += 1
ans = 0
for i in range(1, 10**6 + 1):
    if d[i] == 1:
        ans += 1
    if d[i] > 0:
        for j in range(i, 10**6 + 1, i):
            d[j] = 0
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
_,a=open(0)
t=1
for b in a.split():t*=int(b)
print(-~t*(t<=10**18)-1)

Fixed submission:
n = int(input())
a = list(map(int, input().split()))
if 0 in a:
    print(0)
    exit()
ans = 1
for ai in a:
    ans *= ai
    if ans > 10**18:
        print(-1)
        break
else:
    print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
MOD = 998244353
class mint:
    def __init__(self, i):
        self.i = i
    def __add__(self, m):
        t = self.i + (m.i if isinstance(m, mint) else m)
        if t > MOD:
            t -= MOD
        return mint(t)
    def __radd__(self, m):
        t = self.i + (m.i if isinstance(m, mint) else m)
        if t > MOD:
            t -= MOD
        return mint(t)
    def __mul__(self, m):
        return mint(self.i * (m.i if isinstance(m, mint) else m) % MOD)
    def __sub__(self, m):
        t = self.i - (m.i if isinstance(m, mint) else (m % MOD))
        if t < 0:
            t += MOD
        return mint(t)
    def __pow__(self, m):
        i = self.i
        return mint(pow(i, m, MOD))
    def __truediv__(self, m):
        return mint(self.i * pow(m, MOD - 2, MOD) % MOD)
    def __repr__(self):
        return repr(self.i)


n, s = map(int, input().split())
dp = [mint(0)] * (s + 1)
dp[0] = mint(2) ** n
i2 = mint(2) ** (MOD-2)
for a in map(int, input().split()):
    for i in range(s, -1, -1):
        if a + i <= s:
            dp[a + i] += dp[i] * i2
print(dp[s])


Fixed submission:
MOD = 998244353
class mint:
    def __init__(self, i):
        self.i = i
    def __add__(self, m):
        t = self.i + (m.i if isinstance(m, mint) else m)
        if t > MOD:
            t -= MOD
        return mint(t)
    def __radd__(self, m):
        t = self.i + (m.i if isinstance(m, mint) else m)
        if t > MOD:
            t -= MOD
        return mint(t)
    def __mul__(self, m):
        return mint(self.i * (m.i if isinstance(m, mint) else m) % MOD)
    def __sub__(self, m):
        t = self.i - (m.i if isinstance(m, mint) else (m % MOD))
        if t < 0:
            t += MOD
        return mint(t)
    def __pow__(self, m):
        i = self.i
        return mint(pow(i, m, MOD))
    def __truediv__(self, m):
        return mint(self.i * pow(m, MOD - 2, MOD) % MOD)
    def __repr__(self):
        return repr(self.i)


n, s = map(int, input().split())
dp = [mint(0)] * (s + 1)
dp[0] = mint(2) ** n
i2 = mint(2) ** (MOD-2)
for a in map(int, input().split()):
    for i in range(s, -1, -1):
        if a + i <= s:
            dp[a + i] += dp[i] * i2
print(dp[s])
Buggy python submission (verdict: Runtime Error):
n,*t=map(int,open(0).read().split())
r=[0]+[1]*n
for a,b in zip(t[n::2],t[n+1::2]):r[a]&=t[a]>t[b];r[b]&=t[b]>t[a]
print(sum(r))

Fixed submission:
n, m = map(int, input().split())
h = list(map(int, input().split()))
ans = [1] * n
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if h[a] <= h[b]:
        ans[a] = 0
    if h[b] <= h[a]:
        ans[b] = 0
print(sum(ans))
Buggy python submission (verdict: Time Limit Exceeded):
i=j=c=x=int(input())
while i**5-j**5-x:i=c%128;j=c>>7;c-=1
print(i,j)

Fixed submission:
x=int(input())
[print(i,j)+exit()for i in range(200)for j in range(-i,i)if i**5-j**5==x]

Buggy python submission (verdict: Time Limit Exceeded):
x=int(input())
c=0
while c-x:i=c%120;j=c%217-98;c=i**5-j**5
print(i,j)

Fixed submission:
x=int(input())
[print(i,j)+exit()for i in range(200)for j in range(-i,i)if i**5-j**5==x]

Buggy python submission (verdict: Time Limit Exceeded):
x=int(input())
i=j=0
while i**5-j**5-x:i=i%120+1;j=(j+99)%219-98
print(i,j)

Fixed submission:
x=int(input())
[print(i,j)+exit()for i in range(200)for j in range(-i,i)if i**5-j**5==x]
Buggy python submission (verdict: Time Limit Exceeded):
l=[0]*2019
l[0]=1
s,k=0,1
for c in reversed(input()):k*=10;s+=int(c)*k;l[s%2019]+=1
print(sum(v*(v-1)//2for v in l))

Fixed submission:
m=2019
l=[0]*m
l[0]=1
s,k=0,1
for c in reversed(input()):k=k*10%m;s=(s+int(c)*k)%m;l[s]+=1
print(sum(v*(v-1)//2for v in l))
Buggy python submission (verdict: Time Limit Exceeded):
x,*s=open(0)
h,w,k,*m=map(int,x.split())
for b in range(512):
 r=t=j=0;d=[0]*h
 while j<w:
  i=c=0
  while h-i:
   d[c]+=s[i][j]>'0';x=d[c]>k
   if(t<j)&x:r+=1;t=j;d=[0]*h;break
   r+=x*h*w;c+=b>>i&1;i+=1
  else:j+=1
 while b:r+=b&1;b>>=1
 m+=r,
print(min(m))

Fixed submission:
x,*s=open(0)
h,w,k,*m=map(int,x.split())
for b in range(512):
 r=t=j=0;d=[0]*h
 while j<w:
  i=c=0
  while h-i:
   d[c]+=s[i][j]>'0';x=d[c]>k
   if(t<j)&x:r+=1;t=j;d=[0]*h;break
   r+=x*h*w;c+=b>>i&1;i+=1
  else:j+=1
 while b:r+=b&1;b>>=1
 m+=r,
print(min(m))

Buggy python submission (verdict: Runtime Error):
x,*s=open(0)
h,w,k=map(int,x.split())
p=lambda b:b and(b&1)+p(b>>1)
g=lambda b,j,t,d,i=0,c=0:j==w and~p(b)or i==h and g(b,j+1,t,d)or d.__setitem__(c,d[c]+int(s[i][j]))or d[c]>k and(t<j and-1+g(b,j,j,[0]*h)or h*w)or g(b,j,t,d,i+1,c+(b>>i&1))
print(min(~g(b,0,0,[0]*h)for b in range(512)))

Fixed submission:
x,*s=open(0)
h,w,k,*m=map(int,x.split())
for b in range(512):
 r=t=j=0;d=[0]*h
 while j<w:
  i=c=0
  while h-i:
   d[c]+=s[i][j]>'0';x=d[c]>k
   if(t<j)&x:r+=1;t=j;d=[0]*h;break
   r+=x*h*w;c+=b>>i&1;i+=1
  else:j+=1
 while b:r+=b&1;b>>=1
 m+=r,
print(min(m))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = [int(s) for s in input().split()]
d = 0
ans = 0
mod = 10**9+7
for d in range(60):
	c0 = 0
	c1 = 0
	for v in a:
		if v >> d & 1:
			c1 += 1
		else:
			c0 += 1
	ans = (ans + (c0 * c1 << d)) % mod
print(ans)

Fixed submission:
n = int(input())
a = [int(s) for s in input().split()]
d = 0
ans = 0
mod = 10**9+7
for d in range(60):
	c0 = 0
	c1 = 0
	for v in a:
		if v >> d & 1:
			c1 += 1
		else:
			c0 += 1
	ans = (ans + (c0 * c1 << d)) % mod
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = input()
ans = 0
import re
for i in range(10):
    for j in range(10):
        for k in range(10):
            if re.search(f'{i}.*{j}.*{k}', s):
                ans += 1
print(ans)

Fixed submission:
n = int(input())
s = list(map(int, input()))
ans = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            p = 0
            while p < len(s) and s[p] != i: p += 1
            p += 1
            while p < len(s) and s[p] != j: p += 1
            p += 1
            while p < len(s) and s[p] != k: p += 1
            if p < len(s):
                ans += 1
print(ans)
Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
a = list(map(int, input().split()))
f = list(map(int, input().split()))
a.sort()
f.sort(reverse=True)
costs = [(ai * fi, fi) for ai, fi in zip(a, f)]
costs.sort(reverse=True)
# l impossible, r ok
l, r = -1, costs[0][0]
while(r - l > 1):
    c = (l + r) // 2
    train = 0
    for cost, step in costs:
        if cost > c:
            train += (cost - c + step - 1) // step
    if train <= k:
        r = c
    else:
        l = c
print(r)


Fixed submission:
from math import atan, pi
a, b, x = map(int, input().split())
if 2*x <= a**2*b:
    print(180 * atan(a * b ** 2 / (2 * x)) / pi)
else:
    print(180 * atan(2*(a**2*b-x)/a**3)/pi)
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
a = list(map(int, input().split()))
f = list(map(int, input().split()))
a.sort()
f.sort(reverse=True)
costs = [(ai * fi, fi) for ai, fi in zip(a, f)]
costs.sort(reverse=True)
# l impossible, r ok
l, r = -1, costs[0][0]
while(r - l > 1):
    c = (l + r) // 2
    train = 0
    for cost, step in costs:
        if cost > c:
            train += (cost - c + step - 1) // step
    if train <= k:
        r = c
    else:
        l = c
print(r)


Fixed submission:
n, k = map(int, input().split())
a = list(map(int, input().split()))
f = list(map(int, input().split()))
a.sort()
f.sort(reverse=True)
costs = [(ai * fi, fi) for ai, fi in zip(a, f)]
costs.sort(reverse=True)
# l impossible, r ok
l, r = -1, costs[0][0]
while(r - l > 1):
    c = (l + r) // 2
    train = 0
    for cost, step in costs:
        if cost > c:
            train += (cost - c + step - 1) // step
    if train <= k:
        r = c
    else:
        l = c
print(r)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
l = [int(c) for c in input().split()]
l.sort()
def bin_search(l, r, f):
    while r - l > 1:
        c = (l + r) // 2
        if f(c):
            r = c
        else:
            l = c
    return r

llen = len(l)
ans = 0
for i in range(llen):
    a = l[i]
    for j in range(i + 1, llen):
        b = l[j]
        s = a + b
        upper = bin_search(j, n, lambda x: l[x] >= s)
        #print(i, j, upper)
        ans += upper - (j + 1)
print(ans)



Fixed submission:
n = int(input())
l = [int(c) for c in input().split()]
l.sort()
def bin_search(l, r, f):
    while r - l > 1:
        c = (l + r) // 2
        if f(c):
            r = c
        else:
            l = c
    return r

llen = len(l)
ans = 0
for i in range(llen):
    a = l[i]
    for j in range(i + 1, llen):
        b = l[j]
        s = a + b
        upper = bin_search(j, n, lambda x: l[x] >= s)
        #print(i, j, upper)
        ans += upper - (j + 1)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
n = int(input())
c = list(Counter(ai for ai in map(int, input().split())).values())
c.sort()

s = [0] * (len(c) + 1)
for i in range(len(c)):
    s[i + 1] = s[i] + c[i]

def bin_search_max(l, r, f):
    while r - l > 1:
        c = (l + r) // 2
        if f(c):
            l = c
        else:
            r = c
    return l

for i in range(1, n + 1):
    rest = len(c) - i
    if rest < 0:
        print(0)
        continue
    def f(v):
        lim = bin_search_max(-1, len(c), lambda x: c[x] < v) + 1
        return lim * v - s[lim] <= rest * v
    print(bin_search_max(0, c[-1] * len(c) + 1, f))


Fixed submission:
from collections import Counter
n = int(input())
c = list(Counter(ai for ai in map(int, input().split())).values())
c.sort()

clen = len(c)

s = [0] * (clen + 1)
for i in range(clen):
    s[i + 1] = s[i] + c[i]

for i in range(1, n + 1):
    rest = clen - i
    if rest < 0:
        print(0)
        continue
    l1 = 0
    r1 = s[clen] // i + 2
    while r1 - l1 > 1:
        c1 = (l1 + r1) // 2

        l2 = -1
        r2 = clen
        while r2 - l2 > 1:
            c2 = (r2 + l2) // 2
            if c[c2] < c1:
                l2 = c2
            else:
                r2 = c2

        if (r2 - rest) * c1 <= s[r2]:
            l1 = c1
        else:
            r1 = c1
    print(l1)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
n = int(input())
c = list(Counter(ai for ai in map(int, input().split())).values())
c.sort()

s = [0] * (len(c) + 1)
for i in range(len(c)):
    s[i + 1] = s[i] + c[i]

def bin_search_max(l, r, f):
    while r - l > 1:
        c = (l + r) // 2
        if f(c):
            l = c
        else:
            r = c
    return l

for i in range(1, n + 1):
    rest = len(c) - i
    if rest < 0:
        print(0)
        continue
    def f(v):
        lim = bin_search_max(-1, len(c), lambda x: c[x] < v) + 1
        return lim * v - s[lim] <= rest * v
    print(bin_search_max(0, c[-1] * len(c) + 1, f))


Fixed submission:
from collections import Counter
n = int(input())
c = list(Counter(ai for ai in map(int, input().split())).values())
c.sort()

clen = len(c)

s = [0] * (clen + 1)
for i in range(clen):
    s[i + 1] = s[i] + c[i]

for i in range(1, n + 1):
    rest = clen - i
    if rest < 0:
        print(0)
        continue
    l1 = 0
    r1 = s[clen] // i + 2
    while r1 - l1 > 1:
        c1 = (l1 + r1) // 2

        l2 = -1
        r2 = clen
        while r2 - l2 > 1:
            c2 = (r2 + l2) // 2
            if c[c2] < c1:
                l2 = c2
            else:
                r2 = c2

        if (r2 - rest) * c1 <= s[r2]:
            l1 = c1
        else:
            r1 = c1
    print(l1)
Buggy python submission (verdict: Runtime Error):
n, k = map(int,input().split())
print(len([*filter(lambda hi: hi >= k, map(int,input().split()))]))

Fixed submission:
n, k = map(int,input().split())
print(len(list(filter(lambda hi: hi >= k, map(int,input().split())))))
Buggy python submission (verdict: Time Limit Exceeded):
MOD = 10**9 + 7
s = input()
now = [0] * 13
now[0] = 1
k = 1
for c in reversed(s):
    nxt = [0] * 13
    if c == '?':
        for i in range(10):
            a = k * i % 13
            for j in range(13):
                nxt[(j + a) % 13] += now[j]
                nxt[(j + a) % 13] %= MOD
    else:
        i = int(c)
        a = k * i % 13
        for j in range(13):
            nxt[(j + a) % 13] += now[j]
            nxt[(j + a) % 13] %= MOD
    now = nxt
    k = k * 10 % 13
print(now[5])


Fixed submission:
MOD = 10**9 + 7
s = input()
now = [0] * 13
now[0] = 1
k = 1
for c in reversed(s):
    nxt = [0] * 13
    if c == '?':
        for i in range(10):
            a = k * i % 13
            for j in range(13):
                nxt[(j + a) % 13] += now[j]
                nxt[(j + a) % 13] %= MOD
    else:
        i = int(c)
        a = k * i % 13
        for j in range(13):
            nxt[(j + a) % 13] += now[j]
            nxt[(j + a) % 13] %= MOD
    now = nxt
    k = k * 10 % 13
print(now[5])
Buggy python submission (verdict: Runtime Error):
def iig(vn, en):
    res = [[] for _ in range(vn)]
    for _ in range(en):
        ai, bi = map(lambda x: int(x) - 1, input().split())
        res[ai].append(bi)
        res[bi].append(ai)
    return res

def sep_pc(graph, root=0):
    parent = [-1 for _ in range(n)]
    children = [None for _ in range(n)]
    def f(x, p):
        parent[x] = p
        children[x] = [y for y in graph[x] if y != p]
        for y in graph[x]:
            if y != p:
                f(y, x)
        return
    f(root, -1)
    return parent, children

def itree(n, root=0):
    return sep_pc(iig(n, n - 1), root)

mod = 10**9 + 7

fact_range = 10**5 + 3
facts = [1] * (fact_range + 1)
for i in range(0, fact_range):
    facts[i+1] = facts[i] * (i + 1) % mod

ifacts = [1] * (fact_range + 1)
ifacts[fact_range] = pow(facts[fact_range], mod - 2, mod)
for i in range(fact_range, 0, -1):
    ifacts[i-1] = ifacts[i] * i % mod

n, k = map(int, input().split())
p, c = itree(n)
def dfs(i=0, cur=k, avail=k-1):
    sz = len(c[i])
    if avail <= 0 and sz > 0 or sz > avail:
        return 0
    cur = cur * facts[avail] * ifacts[avail - sz] % mod
    for u in c[i]:
        cur = dfs(u, cur, k - 2)
    return cur
print(dfs())


Fixed submission:
import sys
sys.setrecursionlimit(10**6)

def iig(vn, en):
    res = [[] for _ in range(vn)]
    for _ in range(en):
        ai, bi = map(lambda x: int(x) - 1, input().split())
        res[ai].append(bi)
        res[bi].append(ai)
    return res

def sep_pc(graph, root=0):
    parent = [-1 for _ in range(n)]
    children = [None for _ in range(n)]
    def f(x, p):
        parent[x] = p
        children[x] = [y for y in graph[x] if y != p]
        for y in graph[x]:
            if y != p:
                f(y, x)
        return
    f(root, -1)
    return parent, children

def itree(n, root=0):
    return sep_pc(iig(n, n - 1), root)

mod = 10**9 + 7

fact_range = 10**5 + 3
facts = [1] * (fact_range + 1)
for i in range(0, fact_range):
    facts[i+1] = facts[i] * (i + 1) % mod

ifacts = [1] * (fact_range + 1)
ifacts[fact_range] = pow(facts[fact_range], mod - 2, mod)
for i in range(fact_range, 0, -1):
    ifacts[i-1] = ifacts[i] * i % mod

n, k = map(int, input().split())
p, c = itree(n)
def dfs(i=0, cur=k, avail=k-1):
    sz = len(c[i])
    if avail <= 0 and sz > 0 or sz > avail:
        return 0
    cur = cur * facts[avail] * ifacts[avail - sz] % mod
    for u in c[i]:
        cur = dfs(u, cur, k - 2)
    return cur
print(dfs())
Buggy python submission (verdict: Time Limit Exceeded):
MOD = 10 ** 9 + 7
n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))

dp = [0] * n
ndp = [0] * n
for tj in t:
    for i in range(n):
        ndp[i] = 0
    acc = 0
    for i, si in enumerate(s):
        if si == tj:
            ndp[i] = (dp[i] + acc + 1) % MOD
        else:
            ndp[i] = dp[i]
        acc = (acc + dp[i]) % MOD
    dp, ndp = ndp, dp
print((sum(dp) + 1) % MOD)


Fixed submission:
MOD = 10 ** 9 + 7
n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))

dp = [0] * n
ndp = [0] * n
for tj in t:
    for i in range(n):
        ndp[i] = 0
    acc = 0
    for i, si in enumerate(s):
        if si == tj:
            ndp[i] = (dp[i] + acc + 1) % MOD
        else:
            ndp[i] = dp[i]
        acc = (acc + dp[i]) % MOD
    dp, ndp = ndp, dp
print((sum(dp) + 1) % MOD)