A tree is an undirected connected graph without cycles.

You are given a tree of n vertices. Find the number of ways to choose exactly k vertices in this tree (i. e. a k-element subset of vertices) so that all pairwise distances between the selected vertices are equal (in other words, there exists an integer c such that for all u, v (u ≠ v, u, v are in selected vertices) d_{u,v}=c, where d_{u,v} is the distance from u to v).

Since the answer may be very large, you need to output it modulo 10^9 + 7.

Input

The first line contains one integer t (1 ≤ t ≤ 10) — the number of test cases. Then t test cases follow.

Each test case is preceded by an empty line.

Each test case consists of several lines. The first line of the test case contains two integers n and k (2 ≤ k ≤ n ≤ 100) — the number of vertices in the tree and the number of vertices to be selected, respectively. Then n - 1 lines follow, each of them contains two integers u and v (1 ≤ u, v ≤ n, u ≠ v) which describe a pair of vertices connected by an edge. It is guaranteed that the given graph is a tree and has no loops or multiple edges.

Output

For each test case output in a separate line a single integer — the number of ways to select exactly k vertices so that for all pairs of selected vertices the distances between the vertices in the pairs are equal, modulo 10^9 + 7 (in other words, print the remainder when divided by 1000000007).

Example

Input


3

4 2
1 2
2 3
2 4

3 3
1 2
2 3

5 3
1 2
2 3
2 4
4 5


Output


6
0
1
#include<bits/stdc++.h>
using namespace std;
template<class T,class S=T>inline bool umin(T&m,const S&x){return x<m?m=x,1:0;}
template<class T,class S=T>inline bool umax(T&m,const S&x){return m<x?m=x,1:0;}
auto operator<<(ostream&o,const auto&v)->enable_if_t<!is_constructible_v<string,decltype(v)>,decltype(o<<*end(v))>{int f=0,u=&o==&cerr&&o<<"[";for(auto&&x:v)(f++?o<<(u?", ":" "):o)<<x;return u?o<<"]":o;}
auto operator<<(ostream&o,const auto&t)->decltype(o<<get<0>(t)){o<<"<";apply([&o](auto&...x){int f=0;(((f++?o<<", ":o)<<x),...);},t);return o<<">";}
#ifdef BIZON
    #define rr(...) [](auto&&...x){ cerr << boolalpha << "\e[1;38;5;68m" << #__VA_ARGS__ << " "; int f=0; ((cerr<<"\e[0;38;5;61m"<<",="[!f++]<<"\e[0m "<<x),...)<<endl; }(__VA_ARGS__);
#else
    #define rr(...) 0;
    #define endl '\n'
#endif
#define ALL(c) begin(c), end(c)
#define II(...) __VA_ARGS__; [](auto&...x){(cin>>...>>x);}(__VA_ARGS__);
#define ii(...) int II(__VA_ARGS__)
using ll = long long;

template<class ...T> struct edge_t : public tuple<size_t,T...> {
    edge_t(auto&&... args): tuple<size_t,T...>(args...) { }
    operator size_t() const { return get<0>(*this); }
};
template<class...T> struct std::tuple_size<edge_t<T...>> : tuple_size<tuple<size_t,T...>> {};
template<size_t I, class...T> struct std::tuple_element<I,edge_t<T...>> : tuple_element<I,tuple<size_t,T...>> {};

template<class ...T> struct graph_t {
    using E = conditional_t<sizeof...(T), edge_t<T...>, size_t>;
    explicit graph_t(size_t n): g(n) {}
    void add_dir_edge(size_t from, size_t to, auto&&... args) {
        assert(from<size() && to<size());
        g[from].emplace_back(to, args...);
    }
    void add_edge(size_t x, size_t y, auto&&... args) {
        add_dir_edge(x, y, args...);
        add_dir_edge(y, x, args...);
    }
    const vector<E>& operator[](size_t i) const { return g[i]; }
    size_t size() const { return g.size(); }
    private: vector<vector<E>> g;
};
using graph = graph_t<>;

int inv_mod(int a, int m){
    assert(0<a);
    assert(a<m);
    return a==1 ? 1 : m-m*int64_t(inv_mod(m%a, a))/a;
}

template<int mod> struct modint {
    modint(): x(0) {}
    modint(const auto &val): x(val%mod) { if(x<0) x+=mod; }
    static int get_mod() { return mod; }
    void operator+=(const modint &b){ x+=b.x; if(x>=mod) x-=mod; }
    void operator-=(const modint &b){ x-=b.x; if(x<0) x+=mod; }
    void operator*=(const modint &b){ x = int64_t(x)*b.x %mod; }
    void operator/=(const modint &b){ x = int64_t(x)*inv_mod(b.x,mod) %mod; }
    friend modint operator+(modint a, const modint &b){ a+=b; return a; }
    friend modint operator-(modint a, const modint &b){ a-=b; return a; }
    friend modint operator*(modint a, const modint &b){ a*=b; return a; }
    friend modint operator/(modint a, const modint &b){ a/=b; return a; }
    friend modint operator-(modint a){ if(a.x) a.x = mod - a.x; return a; }
    friend modint pow(modint a, uint64_t n) { modint p=1; for(; n; n>>=1, a*=a) if(n&1) p*=a; return p; }
    friend bool operator==(const modint &a, const modint &b){ return a.x==b.x; }
    friend bool operator!=(const modint &a, const modint &b){ return a.x!=b.x; }
    friend ostream& operator<<(ostream &o, const modint &m){ return o<<m.x; }
    explicit operator int(){ return x; }
    private: int x;
};
using mint = modint<(int)1e9+7>;
mint operator""m(unsigned long long x){ return mint(x); }


void do_test(const int test) { rr(test)
    ii(n,need)
    graph g(n);
    for(int k=0;k<n-1;++k) {
        ii(i,j)
        g.add_edge(--i, --j);
    }
    
    mint ans = 0;
    for(int r=0;r<n;++r) {
        vector dp(n, vector<mint>(need+1));
        
        for(int d=0;d<n;++d) dp[d][0] = 1;
        
        function<void(int,int,int)> go = [&](int v, int p, int d) {
            
            for(int k=need-1;k>=0;--k) dp[d][k+1]+=dp[d][k];
            
            for(int i : g[v]) if(i!=p) {
                go(i, v, d+1);
            }
        };
        
        for(int i : g[r]) {
            go(i, r, 1);
        }
        
        for(int d=1;d<n;++d) ans+=dp[d][need];
    }
    
    cout<<ans<<endl;
}

int main() {
    if(auto f="in.txt"; fopen(f,"r") && freopen(f,"r",stdin));
    cin.tie(0)->sync_with_stdio(0);
    
    int tn = (0 ?: (cin>>tn, tn));
    for(int t=1; t<=tn; ++t) {
        //cout<<"Case #"<<t<<": ";
        do_test(t);
    }
    
    
    return 0;
}
