DPまとめコンテスト（EDPC）全部通す。(M, N, O, P)

def resolve():
  # 遷移の時に累積和を作るといい感じにできそう、
  from itertools import accumulate # 累積和作るやつ

  mod = 10**9 + 7
  N, K = map(int, input().split(" "))
  A = [int(x) for x in input().split(" ")]

  # dp[i][k] := i 番目の人に飴を配り終わった時に、今まで配った飴の個数が k 個である配り方の組み合わせ
  # ↑ は二次元だけど、前回の値を利用することで 2 本の一次元 DP テーブルを切り替えることで同じ計算ができるので、
  # そのように実装する。
  dp = [0]*(K+1)
  dp[0] = 1

  for i in range(N):
    # 遷移を高速に行うために累積和をとる
    acc = [0] + list(accumulate(dp))
    dp_ = [0]*(K+1)
    for k in range(K+1):
      dp_[k] = (acc[k+1] - acc[max(0, k-A[i])])%mod
    dp = dp_
  print(dp[-1])

resolve()

def resolve():
  from itertools import accumulate # 累積和作るやつ
  N = int(input())
  A = [int(x) for x in input().split(" ")]

  # accA : A の累積和
  # 考察に書いてある sum(A[l:r]) を毎回行うのは無駄なので、累積和を取って O(1) で区間和を出せるようにしておく。
  accA = [0] + [x for x in accumulate(A)]

  # memo[l][r] := 区間 l, r のコストの最小値
  # メモ化再帰をするために使う。（みなさんが変数名をどうしているか気になるのでコメントで教えていただけるとありがたいです。）
  memo = [[None]*(N+1) for _ in range(N)]
  def cost(l, r):
    # r-l == 1 というのは区間の長さが 1、つまりスライムが一匹だけしかいないので合体できない => コスト 0 を返す
    if r-l == 1:
      return 0
    # 再帰で区間 l, r のコストを求める。
    if memo[l][r] is None:
      memo[l][r] = min(cost(l, n) + cost(n, r) for n in range(l+1, r)) + accA[r] - accA[l]
    return memo[l][r]

  print(cost(0, N))

resolve()

def resolve():
  popcnt = lambda x: bin(x).count("1")

  # N の最大値がとても小さいのでこれを利用する。
  inf = 10**18+1
  mod = 10**9+7
  N = int(input())
  A = [[int(x) for x in input().split(" ")] for _ in range(N)]
  # MATCHES[i]: i 番目の男性と相性の良い女性の index
  MATCHES = [[j for j in range(N) if A[i][j] == 1] for i in range(N)]

  # dp[i] := i を二進数で考えた時に x 桁目が 1 の場合に x 番目の女性の相手が既に決まっている時の組み合わせの数
  # ex : i == 0b01001 の時、 [1, 4] 番目の女性は既に相手が決まっていて、[2, 3, 5] 番目の女性はまだ相手が決まっていない。
  dp = [0]*(1<<N)
  dp[0] = 1

  for s in range((1<<N)-1):
    # i: 何番目の男性を見るか？を表すインデックス
    # popcnt(s) は既に相手が決まっている女性の人数。
    # 0-index で考えて popcnt(s) 番目の男性を見るようにする。
    i = popcnt(s)
    for n in MATCHES[i]:
      # n 番目の女性のお相手が既に決まっている場合、遷移できない。
      if s&(1<<n): continue

      # n 番目の女性と i 番目の男性をマッチさせた時、状態は s|(1<<n) になるので、そこに遷移する。
      j = s|(1<<n)
      dp[j] += dp[s]
      if dp[j] >= mod: dp[j]%=mod

  print(dp[-1]%mod)

resolve()

def resolve():
  from collections import deque
  mod = 10**9+7
  N = int(input())

  # EDGES[n]: 頂点 n に繋がっている頂点
  EDGES = [[] for _ in range(N)]
  for _ in range(N-1):
    x, y = [int(x)-1 for x in input().split(" ")]
    EDGES[x].append(y)
    EDGES[y].append(x)

  # checked[n]: 頂点 n が既にチェックされているかどうか
  checked = [False]*N
  checked[0] = True

  # parents[n]: 頂点 n の親。根の親は -1 になる。
  parents = [-1]*N

  # dp[n][c] := 頂点 n が c 色のケースのパターン数
  dp = [[1, 1] for _ in range(N)]

  # DFS をやっていく。
  # 帰り道で子の状態から白、黒のそれぞれのパターン数を計算する。
  que = deque([~0, 0])
  while que:
    current = que.pop()
    if current < 0:
      current = ~current
      for n in EDGES[current]:
        # 子だけを見るので、親ノードだった場合はスキップする。
        if n == parents[current]: continue

        # dp[current][0]: 頂点 current が白色のパターン数。子がどの色でも良い => 子のパターンを全て掛け合わせる。
        dp[current][0] *= sum(dp[n])

        # dp[current][1]: 頂点 current が黒色のパターン数。子全て黒である必要がある。 => 子が黒のパターンを掛け合わせる。
        dp[current][1] *= dp[n][0]

        if dp[current][0] >= mod: dp[current][0]%=mod
        if dp[current][1] >= mod: dp[current][1]%=mod
      continue
    for n in EDGES[current]:
      if checked[n]: continue
      checked[n] = True
      parents[n] = current
      que.append(~n)
      que.append(n)

  print(sum(dp[0])%mod)

resolve()