#2067. 「CEOI2020」星际迷航

「CEOI2020」星际迷航

题目描述

星际联邦由 NN 颗行星组成,分别编号为 1N1 \sim N。一些行星间由星际通道相连。通过这些星际通道,飞船可以在短时间内往返于各星球之间。整个星际联邦中恰好有 N1N-1 条星际通道,并且通过这些星际通道,任意两颗行星之间均能相互抵达。

除了我们所处的宇宙之外,还有 DD 个平行宇宙,这些平行宇宙是我们的宇宙的完全复刻,它们的行星,星际通道都和我们的完全相同。我们将这些平行宇宙编号为 1D1 \sim D(我们的宇宙编号为 00),记第 ii 个宇宙的第 xx 颗行星为 PxiP_{x}^i。通过星门,我们可以在这些平行宇宙间穿梭。i[0,D)\forall i \in [0,D),我们将选择一个 AiA_i 和一个 BiB_i(要求 1Ai,BiN1 \leq A_i,B_i \leq N),在 PAiiP_{A_i}^iPBii+1P_{B_i}^{i+1} 之间搭建一个单向(只能从 PAiiP_{A_i}^i 前往 PBii+1P_{B_i}^{i+1})星门。

当所有的星门都准备就绪后,联邦星舰 Batthyány 号将会开始它的处女航,它目前正环绕着 P10P_1^0 行星。Ágnes 舰长准备和 Gábor 中尉玩这样一个游戏:两个人交替选择星舰接下来前往的目的地,要求该目的地可以通过星际通道或星门直接抵达。他们希望每次前往的星球都是之前未抵达过的。即,如果星舰抵达了 PxiP_{x}^i,他们将不再经过这个星球(但是可以抵达 xx 在其他平行宇宙中的相应星球)。由 Ágnes 舰长作为先手开始游戏,Gábor 中尉作为后手,当一位玩家在他的回合中,不能选择一个合法的目的地时,他就输掉了游戏。

舰长和中尉都是绝对聪明的,他们知道所有星际通道和星门的排布方案,并且他们每次都按照最优方案行动。你需要求出,有多少种布置星门的方案,使得作为先手的 Ágnes 舰长必胜?两种布置星门的方案是不同的,当且仅当存在一个整数 ii,使得 AiA_iBiB_i 不同。

输入格式

第一行两个整数 N,DN,D,分别代表星际联邦拥有的行星数和平行宇宙的数量。

接下来 N1N-1 行,每行两个整数 u,vu,v,表示 i[0,D]\forall i \in [0,D]Pui,PviP_u^i,P_v^i 之间有星际通道相连。

输出格式

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

3 1
1 2
2 3
4

共有 33=93 * 3=9 种本质不同的布置星门的方案,下面列出四种舰长必胜的情况。

数据范围与提示

所有数据均满足:1N1051 \leq N \leq 10^51D10181 \leq D \leq 10^{18}1u,vN1 \leq u,v \leq N

各子任务的约束条件如下:

子任务编号 分值 约束
11 00 样例
22 77 N=2N=2
33 88 N100N \leq 100D=1D=1
44 1515 N1000N \leq 1000D=1D=1
55 1515 D=1D=1
66 2020 N1000N \leq 1000D105D \leq 10^5
77 2020 D105D \leq 10^5
88 1515 无特殊约束