[CEOI2020] 星际迷航

题目背景

原时空限制:0.2s,32m

题目描述

星际联邦由 $N$ 颗行星组成,分别编号为 $1 \sim N$。一些行星间由星际通道相连。通过这些星际通道,飞船可以在短时间内往返于各星球之间。整个星际联邦中恰好有 $N-1$ 条星际通道,并且通过这些星际通道,任意两颗行星之间均能相互抵达。 除了我们所处的宇宙之外,还有 $D$ 个平行宇宙,这些平行宇宙是我们的宇宙的完全复刻,它们的行星,星际通道都和我们的完全相同。我们将这些平行宇宙编号为 $1 \sim D$(我们的宇宙编号为 $0$),记第 $i$ 个宇宙的第 $x$ 颗行星为 $P_{x}^i$。通过星门,我们可以在这些平行宇宙间穿梭。$\forall i \in [0,D)$,我们将选择一个 $A_i$ 和一个 $B_i$(要求 $1 \leq A_i,B_i \leq N$),在 $P_{A_i}^i$ 和 $P_{B_i}^{i+1}$ 之间搭建一个**单向**(只能从 $P_{A_i}^i$ 前往 $P_{B_i}^{i+1}$)星门。 当所有的星门都准备就绪后,联邦星舰 Batthyány 号将会开始它的处女航,它目前正环绕着 $P_1^0$ 行星。Ágnes 舰长准备和 Gábor 中尉玩这样一个游戏:两个人交替选择星舰接下来前往的目的地,要求该目的地可以通过星际通道或星门直接抵达。他们希望每次前往的星球都是之前未抵达过的。即,如果星舰抵达了 $P_{x}^i$,他们将不再经过这个星球(但是可以抵达 $x$ 在其他平行宇宙中的相应星球)。由 Ágnes 舰长作为先手开始游戏,Gábor 中尉作为后手,当一位玩家在他的回合中,不能选择一个合法的目的地时,他就输掉了游戏。 舰长和中尉都是绝对聪明的,他们知道所有星际通道和星门的排布方案,并且他们每次都按照最优方案行动。你需要求出,有多少种布置星门的方案,使得作为先手的 Ágnes 舰长必胜?两种布置星门的方案是不同的,当且仅当存在一个整数 $i$,使得 $A_i$ 或 $B_i$ 不同。

输入输出格式

输入格式


第一行两个整数 $N,D$,分别代表星际联邦拥有的行星数和平行宇宙的数量。 接下来 $N-1$ 行,每行两个整数 $u,v$,表示 $\forall i \in [0,D]$,$P_u^i,P_v^i$ 之间有星际通道相连。

输出格式


输出能使舰长必胜的星门布置方案数对 $10^9+7$ 取模的结果。

输入输出样例

输入样例 #1

3 1
1 2
2 3

输出样例 #1

4

说明

### 样例解释 共有 $3 \times 3=9$ 种本质不同的布置星门的方案,下面列出四种舰长必胜的情况。 ![](https://cdn.luogu.com.cn/upload/image_hosting/vblsc4g6.png) ### 子任务 所有数据均满足:$1 \leq N \leq 10^5$,$1 \leq D \leq 10^{18}$,$1 \leq u,v \leq N$。 各子任务的约束条件如下: | 子任务编号 | 分值 | 约束 | | ---------- | ---- | ---------------------------- | | $1$ | $0$ | 样例 | | $2$ | $7$ | $N=2$ | | $3$ | $8$ | $N \leq 100$,$D=1$ | | $4$ | $15$ | $N \leq 1000$,$D=1$ | | $5$ | $15$ | $D=1$ | | $6$ | $20$ | $N \leq 1000$,$D \leq 10^5$ | | $7$ | $20$ | $D \leq 10^5$ | | $8$ | $15$ | 无特殊约束 |