Liên bang Hành tinh có \(N\) hành tinh được đánh số từ \(1\) đến \(N\). Một số cặp hành tinh được nối bằng đường hầm không gian. Tàu vũ trụ có thể đi qua đường hầm theo cả hai chiều. Có đúng \(N-1\) đường hầm và có thể đi từ bất kỳ hành tinh nào đến bất kỳ hành tinh nào khác bằng các đường hầm.

Ngoài vũ trụ của chúng ta còn có \(D\) vũ trụ song song giống hệt, cũng có cùng các hành tinh và đường hầm. Các vũ trụ song song được đánh số từ \(1\) đến \(D\); vũ trụ của chúng ta được đánh số \(0\). Ký hiệu hành tinh \(x\) trong vũ trụ \(i\) là \(P_x^i\).

Với mỗi \(i\) từ \(0\) đến \(D-1\), ta sẽ đặt đúng một cổng không gian nối từ \(P_{A_i}^i\) đến \(P_{B_i}^{i+1}\), trong đó \(1\le A_i,B_i\le N\).

Sau khi đặt các cổng, con tàu của thuyền trưởng Batthyány bắt đầu hành trình tại \(P_1^0\). Thuyền trưởng Ágnes và trung úy Gábor lần lượt chọn một hành tinh làm điểm đến. Hành tinh được chọn có thể ở cùng vũ trụ nếu có đường hầm nối tới đó, hoặc ở vũ trụ khác nếu có cổng không gian đi tới đó.

Khi một hành tinh \(P_x^i\) đã được ghé thăm thì không được quay lại hành tinh đó, nhưng vẫn có thể ghé thăm hành tinh \(x\) ở một vũ trụ khác. Ágnes đi trước, sau đó đến Gábor, rồi lại đến Ágnes. Nếu đến lượt mà không thể chọn một hành tinh chưa từng được ghé thăm, người chơi đó thua.

Cả Ágnes và Gábor đều biết vị trí của tất cả đường hầm và cổng, và đều chơi tối ưu. Hãy đếm số cách đặt cổng sao cho Ágnes thắng. Hai cách đặt được xem là khác nhau nếu tồn tại một chỉ số \(i\) mà cổng thứ \(i\) nối hai cặp hành tinh khác nhau trong hai cách đặt.

Vì kết quả có thể rất lớn, hãy in phần dư khi chia cho \(10^9+7\).

Dữ liệu vào

Dòng đầu gồm hai số nguyên \(N,D\).

Mỗi dòng trong \(N-1\) dòng tiếp theo gồm hai số nguyên \(u,v\), cho biết có một đường hầm nối \(P_u^i\) với \(P_v^i\) trong mọi vũ trụ \(i\) từ \(0\) đến \(D\).

Dữ liệu ra

In số cách đặt cổng để Ágnes thắng modulo \(10^9+7\).

Ví dụ

3 1
1 2
2 3

4

Chỉ có một cổng và có \(3\cdot3=9\) cách đặt cổng. Bốn cách để Ágnes thắng được minh họa dưới đây.

Ràng buộc

• \(2\le N\le10^5\).
• \(1\le D\le10^{18}\).
• \(1\le u,v\le N\).

Phân nhóm

1. \(0\) điểm: Bộ dữ liệu mẫu.
2. \(7\) điểm: \(N=2\).
3. \(8\) điểm: \(N\le100\) và \(D=1\).
4. \(15\) điểm: \(N\le1000\) và \(D=1\).
5. \(15\) điểm: \(D=1\).
6. \(20\) điểm: \(N\le1000\) và \(D\le10^5\).
7. \(20\) điểm: \(D\le10^5\).
8. \(15\) điểm: Không có ràng buộc nào khác.