Problem p02985 (python)

Fixed submission:
class perm():
  F = [1, 1]
  Fi = [1, 1]
  I = [0, 1]
  def __init__(self, num, mod):
    self.MOD = mod
    for i in range(2, num + 1):
      self.F.append((self.F[-1] * i) % mod)
      self.I.append(mod - self.I[mod % i] * (mod // i) % mod)
      self.Fi.append(self.Fi[-1] * self.I[i] % mod)
  def per(self, n, k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return self.F[n] * (self.Fi[n - k] % self.MOD) % self.MOD

class Tree:
  C, RL = {}, {}
  R, T, N, D = None, None, None, None
  def __init__(s, num):
    s.N = num
  def setC(s, a, b):
    if a in s.C: s.C[a].append(b)
    else: s.C[a] = [b]
    if b in s.C: s.C[b].append(a)
    else: s.C[b] = [a]
  def makeRank(s, root):
    s.R = [0] * s.N
    s.R[root] = 1
    s.RL[1] = [root]
    F = [root]
    s.D = 2
    while F != []:
      Ft = []
      s.RL[s.D] = []
      for i in F:
        for j in s.C[i]:
          if s.R[j] == 0:
            s.R[j] = s.D
            Ft.append(j)
            s.RL[s.D].append(j)
      s.D += 1
      F = Ft
  def dfs(s, x):
    S = [x]
    ans = K
    while S != []:
      k = S.pop()
      n = 0
      for i in s.C[k]:
        if s.R[i] > s.R[k]:
          n += 1
          S.append(i)
      if n != 0:
        if k == x:
          if n > K - 1:
            return 0
          ans = ans * P.per(K - 1, n) % MOD
        else:
          if n > K - 2:
            return 0
          ans = ans * P.per(K - 2, n) % MOD
    return ans

N, K = list(map(int, input().split()))
ab = [list(map(int, input().split())) for i in range(N - 1)]
MOD = 1000000007

if N == 1:
  print(K)
  exit()
  
P = perm(K, MOD)

T = Tree(N)
for a, b in ab:
  T.setC(a - 1, b - 1)

T.makeRank(0)

print(T.dfs(0))

Buggy submission (verdict: Runtime Error):
class perm():
  F = [1, 1]
  Fi = [1, 1]
  I = [0, 1]
  def __init__(self, num, mod):
    self.MOD = mod
    for i in range(2, num + 1):
      self.F.append((self.F[-1] * i) % mod)
      self.I.append(mod - self.I[mod % i] * (mod // i) % mod)
      self.Fi.append(self.Fi[-1] * self.I[i] % mod)
  def per(self, n, k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return self.F[n] * (self.Fi[n - k] % self.MOD) % self.MOD

class Tree:
  C, RL = {}, {}
  R, T, N, D = None, None, None, None
  def __init__(s, num):
    s.N = num
  def setC(s, a, b):
    if a in s.C: s.C[a].append(b)
    else: s.C[a] = [b]
    if b in s.C: s.C[b].append(a)
    else: s.C[b] = [a]
  def makeRank(s, root):
    s.R = [0] * s.N
    s.R[root] = 1
    s.RL[1] = [root]
    F = [root]
    s.D = 2
    while F != []:
      Ft = []
      s.RL[s.D] = []
      for i in F:
        for j in s.C[i]:
          if s.R[j] == 0:
            s.R[j] = s.D
            Ft.append(j)
            s.RL[s.D].append(j)
      s.D += 1
      F = Ft
  def dfs(s, x):
    S = [x]
    ans = K
    while S != []:
      k = S.pop()
      n = 0
      for i in s.C[k]:
        if s.R[i] > s.R[k]:
          n += 1
          S.append(i)
      if n != 0:
        if k == x:
          if n > K - 1:
            return 0
          ans = ans * P.per(K - 1, n) % MOD
        else:
          if n > K - 2:
            return 0
          ans = ans * P.per(K - 2, n) % MOD
    return ans

N, K = list(map(int, input().split()))
ab = [list(map(int, input().split())) for i in range(N - 1)]
MOD = 1000000007

P = perm(K, MOD)

T = Tree(N)
for a, b in ab:
  T.setC(a - 1, b - 1)

T.makeRank(0)

print(T.dfs(0))

Buggy submission (verdict: Runtime Error):
class perm():
  F = [1, 1]
  Fi = [1, 1]
  I = [0, 1]
  def __init__(self, num, mod):
    self.MOD = mod
    for i in range(2, num + 1):
      self.F.append((self.F[-1] * i) % mod)
      self.I.append(mod - self.I[mod % i] * (mod // i) % mod)
      self.Fi.append(self.Fi[-1] * self.I[i] % mod)
  def per(self, n, k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return self.F[n] * (self.Fi[n - k] % self.MOD) % self.MOD

class Tree:
  C, RL = {}, {}
  R, T, N, D = None, None, None, None
  def __init__(s, num):
    s.T = [[0] * num for _ in range(num)]
    s.N = num
  def setT(s, a, b):
    s.T[a][b] = 1
    s.T[b][a] = 1
  def setC(s, a, b):
    if a in s.C: s.C[a].append(b)
    else: s.C[a] = [b]
    if b in s.C: s.C[b].append(a)
    else: s.C[b] = [a]
  def setTC(s, a, b):
    s.setT(a, b)
    s.setC(a, b)
  def makeRank(s, root):
    s.R = [0] * s.N
    s.R[root] = 1
    s.RL[1] = [root]
    F = [root]
    s.D = 2
    while F != []:
      Ft = []
      s.RL[s.D] = []
      for i in F:
        for j in s.C[i]:
          if s.R[j] == 0:
            s.R[j] = s.D
            Ft.append(j)
            s.RL[s.D].append(j)
      s.D += 1
      F = Ft
  def dfs(s, x):
    S = [x]
    ans = K
    while S != []:
      k = S.pop()
      n = 0
      for i in s.C[k]:
        if s.R[i] > s.R[k]:
          n += 1
          S.append(i)
      if n != 0:
        if k == x:
          if n > K - 1:
            return 0
          ans = ans * P.per(K - 1, n) % MOD
        else:
          if n > K - 2:
            return 0
          ans = ans * P.per(K - 2, n) % MOD
    return ans

N, K = list(map(int, input().split()))
ab = [list(map(int, input().split())) for i in range(N - 1)]
MOD = 1000000007

P = perm(K, MOD)

T = Tree(N)
for a, b in ab:
  T.setC(a - 1, b - 1)

T.makeRank(0)

print(T.dfs(0))

Buggy submission (verdict: Runtime Error):
class perm():
  F = [1, 1]
  Fi = [1, 1]
  I = [0, 1]
  def __init__(self, num, mod):
    self.MOD = mod
    for i in range(2, num + 1):
      self.F.append((self.F[-1] * i) % mod)
      self.I.append(mod - self.I[mod % i] * (mod // i) % mod)
      self.Fi.append(self.Fi[-1] * self.I[i] % mod)
  def per(self, n, k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return self.F[n] * (self.Fi[n - k] % self.MOD) % self.MOD

class Tree:
  C, RL = {}, {}
  R, T, N, D = None, None, None, None
  def __init__(s, num):
    s.T = [[0] * num for _ in range(num)]
    s.N = num
  def setT(s, a, b):
    s.T[a][b] = 1
    s.T[b][a] = 1
  def setC(s, a, b):
    if a in s.C: s.C[a].append(b)
    else: s.C[a] = [b]
    if b in s.C: s.C[b].append(a)
    else: s.C[b] = [a]
  def setTC(s, a, b):
    s.setT(a, b)
    s.setC(a, b)
  def makeRank(s, root):
    s.R = [0] * s.N
    s.R[root] = 1
    s.RL[1] = [root]
    F = [root]
    s.D = 2
    while F != []:
      Ft = []
      s.RL[s.D] = []
      for i in F:
        for j in s.C[i]:
          if s.R[j] == 0:
            s.R[j] = s.D
            Ft.append(j)
            s.RL[s.D].append(j)
      s.D += 1
      F = Ft
  def dfs(s, x):
    S = [x]
    ans = K
    while S != []:
      k = S.pop()
      n = 0
      for i in s.C[k]:
        if s.R[i] > s.R[k]:
          n += 1
          S.append(i)
      if n != 0:
        if k == x:
          if n > K - 1:
            return 0
          ans = ans * P.per(K - 1, n) % MOD
        else:
          if n > K - 2:
            return 0
          ans = ans * P.per(K - 2, n) % MOD
    return ans

N, K = list(map(int, input().split()))
ab = [list(map(int, input().split())) for i in range(N - 1)]
MOD = 1000000007

P = perm(K, MOD)

T = Tree(N)
for a, b in ab:
  T.setTC(a - 1, b - 1)

T.makeRank(0)

print(T.dfs(0))