Catering Contracts
A new government has come to power after the elections in Siruseri and has promptly announced that it is reassigning all catering contracts on its rail network.
As is well known, the rail network of Siruseri is organized so that every station is connected to every other station by a unique path. The new scheme requires contractors to bid for a group of K stations at a time. However, the constraint is that all K stations that a contractor bids for must form a connected portion of the network. Having announced this, the government is now scratching its head to figure out how many different combinations of stations contractors can bid for.
For example, suppose the rail network is as given below, and contractors have to bid for 3 stations at a time. Then, there are six possible combinations, namely {1,2,3}, {1,2,5}, {2,3,5}, {2,4,5}, {2,5,6} and {4,5,6}. A combination such as {1,2,4}, for instance, is not permitted because these three stations are not all connected to each other.
You will be given a description of the rail network and the number of stations that a contractor has to bid for. You have to compute the number of different combinations of stations that the contractor can legally bid for, following the rule stipulated by the government.
Input
The first line of input consists of two integer, N and K, where N is the number of stations in the network and K is the number of stations that each bid must contain. The stations are numbered {1,2,...,N}. The next N−1 lines describe the track segments. Each of these lines contains two integers i and j describing one track segment, where i and j are the stations at either end of the segment.
Output
A single integer, denoting the number of combinations that a contractor can legally bid for. You should report your answer modulo 10243.
Test Data
In all inputs, 1 ≤ N ≤ 2500 and 1 ≤ K ≤ 90.
Example
Input:
6 3
1 2
2 5
3 2
4 5
6 5
Output:
6