## No more modification

Time Limit: 1 sec
Memory Limit: 256 MB
Attempts: 22
Accuracy: 18.18%
Author: Akashdeep Goel

Lord Voldemort(finally) is weak now. He must protect Nagini if he want to survive. For the same he again devised a problem for Harry and as usual Harry seeks for your help.

You are a given a tree with N nodes. Let M denote the number of simple paths with at least two nodes. Notice that M=(N*(N-1))/2.

You are asked to select X simple paths at random (repetitions allowed) and find the expected value of xor sum of their lengths. Expected value can always be represented as an irreducible fraction P/Q. You need to report P*Q^{-1} modulo 1000000007 . See the explanation section for further clarification.

Input format:

First line contains two space separated integers N and X.

Next N-1 lines contain two space separated integers u and v indicating edge between node u and node v.

Output format:

Single integer denoting the answer found.

Constraints:

1 <= N <= 1e5

1 <= X <= 1e9

1 <= u,v <= N

Sample Input:

3 2

1 2

1 3

Sample Output:

333333337

Sample Explanation:

There are 3 simple paths for the above tree: {1,2} , {1,3} , {2,1,3}

Following are the possible case for selection of X=2 simple paths:

Choose {1,2} and {1,2}: xor(1,1)=0

Choose {1,2} and {1,3}: xor(1,1)=0

Choose {1,2} and {2,1,3}: xor(1,2)=3

Choose {1,3} and {1,2}: xor(1,1)=0

Choose {1,3} and {1,3}: xor(1,1)=0

Choose {1,3} and {2,1,3}: xor(1,2)=3

Choose {2,1,3} and {1,2}: xor(2,1)=3

Choose {2,1,3} and {1,3}: xor(2,1)=3

Choose {2,1,3} and {2,1,3}: xor(2,2)=0

Expected value = 0/9 + 0/9 + 3/9 + 0/9 + 0/9 + 3/9 + 3/9 + 3/9 + 0/9 = 4/3

So the answer is 333333337.

ID

SUBMITTED AT

STATUS

LANGUAGE

TIME

MEMORY USED

USER

TIME

STATUS

LANGUAGE

TIME

MEMORY USED