Star Trek

연합 행성 연방은 $1$부터 $N$까지 번호가 붙은 $N$개의 행성으로 이루어진 동맹이다. 일부 행성은 우주 터널로 연결되어 있다. 우주선은 우주 터널을 양방향으로 매우 빠르게 날 수 있다. 우주 터널은 정확히 $N-1$개이며, 이 터널을 따라 연방의 어떤 행성에서든 다른 모든 행성으로 갈 수 있다.

추가로 $D$개의 평행 우주가 있다. 각 우주는 우리 우주의 완전한 복사본이며, 행성과 우주 터널이 같다. 우주에는 $1$부터 $D$까지 번호가 붙어 있고, 우리 우주의 번호는 $0$이다. 우주 $i$에 있는 행성 $x$를 $P^i_x$로 쓴다. 우주 사이의 이동에는 차원 포털을 쓴다. 모든 $i$ ($0 \le i \le D-1$)에 대해 $P^i_{A_i}$에서 $P^i_{B_i}$로 날아가는 포털을 정확히 하나 설치한다. 여기서 $1 \le A_i, B_i \le N$이다.

모든 포털을 설치하면 우주선 Batthyány가 첫 항해를 시작하며, 처음에는 $P^0_1$ 궤도를 돌고 있다. Ágnes 대위와 Gábor 중위가 다음 게임을 한다. 두 사람은 번갈아 가며 도착할 행성을 고른다. 같은 우주라도 우주 터널로 갈 수 있으면 고를 수 있고, 다른 우주라도 포털로 갈 수 있으면 고를 수 있다. 두 사람의 목표는 아무도 가 본 적 없는 곳을 방문하는 것이다. 행성 $P^i_x$를 한 번 방문하면 두 사람 모두 그곳에 다시 가지 않는다. 다만 다른 우주의 행성 $x$는 방문할 수 있다. Ágnes 대위가 첫 번째 행성을 고르고, 다음은 Gábor, 그다음은 다시 Ágnes 순서다. 자기 차례에 가 보지 않은 행성을 고를 수 없는 사람이 진다.

두 사람은 모든 터널과 포털의 위치를 알고 있으며 둘 다 최선으로 둔다. Ágnes 대위가 이기는 서로 다른 포털 설치 방법은 몇 가지인가? 어떤 $i$ ($0 \le i \le D-1$)에 대해 $i$번째 포털이 두 설치 방법에서 서로 다른 행성 쌍을 잇는다면, 두 설치 방법은 다른 것이다. 즉 $A_i$나 $B_i$가 다르면 다르다. 답은 $10^9+7$로 나눈 나머지로 구한다.

첫 줄에 정수 $N$과 $D$가 주어진다. 다음 $N-1$개의 줄에는 정수 $u$와 $v$가 주어지며, 이는 모든 $i$ ($0 \le i \le D$)에 대해 $P^i_u$와 $P^i_v$가 우주 터널로 연결되어 있다는 뜻이다.

Ágnes 대위가 이기는 포털 설치 방법의 수를 $10^9+7$로 나눈 나머지를 출력한다.

$2 \le N \le 10^5$

$1 \le D \le 10^{18}$

$1 \le u, v \le N$

포털이 하나뿐이므로 가능한 설치 방법은 $3 \times 3 = 9$가지다. 다음 4가지 설치 방법에서 대위가 이긴다.