Road Maintenance

 Byteland has  cities (numbered from  to ) and  bidirectional roads. A path is comprised of  or more connected roads. It is guaranteed that there is a path from any city to any other city.

Steven is a road maintenance worker in Byteland. He is required to maintain exactly  paths on any given workday. He cannot work on the same road twice in one day (so no  paths can contain the same  roads). Steven can start his workday in any city and, once he has finished maintaining a path, teleport to his next starting city.

Given , help Steven determine how many different possible path sets will allow him to perform his maintenance duties. Then print the answer modulo .

Input Format

The first line contains  space-separated integers,  (the number of cities) and  (the number of roads to maintain).
Each line  of the  subsequent lines contains  space-separated integers, , describing a bidirectional road between cities  and .

Constraints

Output Format

Find the number of different path sets that will allow Steven to complete  orders, and print the answer .

Sample Input

4 2
1 2
2 3
2 4

Sample Output

6

Explanation

For the following Byteland map:  Steven can maintain  roads using any of the following  routes:

1.  and 
2.  and 
3.  and 
4.  and 
5.  and 
6.  and 

Thus, we print the result of  on a new line, which is .

SOLUTION:

#include <bits/stdc++.h>

using namespace std;

#define pb push_back

#define foreach(i,x) for(type(x)i = x.begin(); i != x.end(); i++)

#define FOR(ii, aa, bb) for(int ii = aa; ii <= bb; ii++)

#define type(x) __typeof(x.begin())

typedef long long ll;

const int mod = (int) 1e9 + 7;

const int N = 2e5 + 5;

int n, m, x, y, dp[N][11][11], temp[N][11][11];

vector<int> v[N];

void dfs(int node, int root) {

    dp[node][0][0] = 1;

    foreach(it, v[node]) {

        if(*it == root) continue;

        dfs(*it, node);

        FOR(i, 0, 10){

            FOR(j, 0, 10) {

                temp[node][i][j] = dp[node][i][j];

                dp[node][i][j] = 0;

            }

        }

        FOR(i, 0, m){

            FOR(j, 0, m - i){

                FOR(k, 0, m){

                    dp[node][i + j][k] = (dp[node][i + j][k] + temp[node][i][k] * (ll) dp[*it][j][0]) % mod;

                    dp[node][i + j][k + 1] = (dp[node][i + j][k + 1] + temp[node][i][k] * (ll) dp[*it][j][1]) % mod;

                    if(k) dp[node][i + j + 1][k - 1] = (dp[node][i + j + 1][k - 1] + temp[node][i][k] * (ll) dp[*it][j][1] % mod * k) % mod;

                    dp[node][i + j + 1][k] = (dp[node][i + j + 1][k] + temp[node][i][k] * (ll) dp[*it][j][1] % mod) % mod;

                }

            }

        }

    }   

    FOR(i, 0, m) dp[node][i][1] = (dp[node][i][1] + dp[node][i][0]) % mod;

}

int main() {

    cin >> n >> m;

    FOR(i, 2, n) {

        cin >> x >> y;

        v[x].pb(y);

        v[y].pb(x);

    }

    dfs(1, 0);

    cout << dp[1][m][0] << endl;

    return 0;

}