問題
서기 10^5년, 인류는 우주를 자유롭게 돌아다닐 수 있는 것은 물론, 멀티버스의 존재 또한 발견했고 멀티버스로 이동도 할 수 있게 되었다.
인류는 지금 총 N개의 은하를 관리하고 있다. 하지만 우주는 너무나도 광활하기 때문에 고속 이동 장치가 필요했고, 그에 따라 N-1개의 고속 이동 장치를 배치하여 어떤 두 은하 사이에도 이동이 가능하게 만들었다.
멀티버스는 지금의 우주의 모양과 정확히 같은 다른 우주로, 위에서 언급한 고속 이동 장치의 배열도 같다.
하지만 멀티버스 간의 여행에는 제약이 있다. 지금이 i번 멀티버스라면, 우리는 i+1번 멀티버스로만 이동할 수 있다. 즉, 멀티버스 간의 이동은 단방향이다.
멀티버스 간의 이동은 굉장히 어렵기 때문에, 정해진 은하에서 정해진 은하로만 이동할 수 있다. 즉, i-1번 멀티버스의 Ai번 은하에서 i번 멀티버스의 Bi번 은하로만 이동할 수 있다.
또, 멀티버스가 발견된지 얼마 안됐기 때문에, 이동할 수 있는 멀티버스의 수는 제한적이다. 지금 위치한 우주가 0번 멀티버스라면, 우리는 최대 D번 멀티버스까지밖에 이동할 수 없다.
정올이와 한컴이는 모험가이다. 그러기에 서로 누가 더 모험을 잘하는지 경쟁하려 한다. 정올이부터 시작해서 번갈아가면서, 이동할 다음 은하를 선택하여 움직인다. 단, 전에 한번 방문했던 은하는 다시 방문하지 않으며, 다른 멀티버스의 은하는 다른 은하로 취급한다. 만약 더 이상 움직이지 못한다면 그 사람이 패배한다.
시작점이 0번 멀티버스의 1번 은하일 때, 정올이가 무슨 일이 있어도 항상 승리할 수 있는 (A1, ..., AD, B1, ..., BD) 쌍의 개수를 구하시오.
답이 매우 커질 수 있으므로 10^9+7로 나눈 나머지를 대신 출력하여라.
入力
첫 줄에 N과 D가 주어진다. (2<=N<=10^5, 1<=D<=10^18)
그 다음 N-1줄에 걸쳐, 고속 이동 장치의 양 끝을 나타내는 두 정수 ui, vi가 주어진다. (1<=ui, vi<=N)
出力
시작점이 0번 멀티버스의 1번 은하일 때, 정올이가 승리할 수 있는 (A1, ..., AD, B1, ..., BD) 쌍의 개수를 10^9+7로 나눈 나머지를 출력하시오.
部分問題
| 番号 | 点数 | 条件 |
|---|---|---|
| #1 | 7点 | N=2 |
| #2 | 8点 | N<=100, D=1 |
| #3 | 15点 | N<=1000, D=1 |
| #4 | 15点 | D=1 |
| #5 | 20点 | N<=1000, D<=10^5 |
| #6 | 20点 | D<=10^5 |
| #7 | 15点 | 제한 없음 |
例題
3 1
1 2
2 3
4
ログインしないとコードを書けません。