#include using namespace std; template struct modint { unsigned long long value; constexpr modint(const unsigned long long x=0) { value=x%MOD; } constexpr modint operator+(const modint other) { return modint(*this)+=other; } constexpr modint operator-(const modint other) { return modint(*this)-=other; } constexpr modint operator*(const modint other) { return modint(*this)*=other; } constexpr modint operator/(const modint other) { return modint(*this)/=other; } constexpr modint &operator+=(const modint other) { value+=other.value; if (value>=MOD) { value-=MOD; } return *this; } constexpr modint &operator-=(const modint other) { if (value>=1,_this*=_this) { if (x&1) { ret*=_this; } } return ret; } constexpr modint inv() { return pow(MOD-2); } friend ostream& operator<<(ostream& os, const modint &x) { return os<>(istream& is, modint &x) { is>>x.value; x.value%=MOD; if (x.value<0) { x.value+=MOD; } return is; } }; using mint=modint<1000000007>; int main() { ios::sync_with_stdio(0); cin.tie(0); int n,k; cin>>n>>k; vector> g(n); for (int i=0;i>a>>b; g[a].push_back(b); g[b].push_back(a); } //a[i]:=部分木のうち、i個の頂点が黒く塗られるような通り数 auto merge=[&](vector &a, vector &b) -> vector { vector ret(a.size()+b.size()-1); for (int i=0;i vector { //83行目と同じ定義 //最初は頂点数1から始める vector dp(2); dp[0]=1; for (int nxt:g[now]) { if (nxt!=pre) { auto ndp=dfs(dfs,nxt,now); dp=merge(dp,ndp); } } dp.back()=1; return dp; }; auto dp=dfs(dfs,0,0); cout<