the number of different possible color assignments. The number can be quite big, so the King has requested to know the answer modulo 1000000007?

Far, far away, there is the mystical Kingdom of Trees (more formally, "Royal Commonwealth of Connected Undirected Simple Acyclic Graphs"). The King there is very sad because his kingdom is not accepted as a sovereign state in the United Nations. In order to become a member, he needs to make a flag the UN can put on their website.The flag will of course consist of the King's favorite tree, which contains $n$ nodes. The King would be happy to just have the tree colored in black and white, but for the sake of his wife the Queen, he decided that the tree will contain all the favorite colors of their $k$ children (they all have distinct favorite colors). Clearly, no two neighboring nodes can have the same color, but otherwise any coloring of the tree using exactly the $k$ colors would make a feasible flag candidate.How many different flags are possible?

Input:

The first line contains two integers $n$ and $k$ ( $2 \leq k \leq n \leq 2 500$ ), where $n$ is the number of nodes in the King's favorite tree and $k$ is the number of children. Then follow $n - 1$ lines describing the edges in the tree; the $i$ 'th of these lines contains a non-negative integer $p_{i} < i$ , meaning that node $p_{i}$ is the parent of $i$ The nodes are numbered from $0$ to $n - 1$ and the tree is rooted at node $0$ . Note that the embedding of the tree on the flag is already fixed, the only thing that remains is to assign colors.

Output:

the number of different possible color assignments. The number can be quite big, so the King has requested to know the answer modulo

$1 000 000 007$ .

#include <bits/stdc++.h> typedef long long ll; using namespace std; ll n ,k; const ll mod = 1e9 + 7; ll ME(ll x,ll nn,ll M) { ll result=1; while(nn>0) { if(nn % 2 ==1) result=(result * x)%M; x=(x*x)%M; nn=nn/2; } return result; } ll C[3002][3002]; int main() { cin >> n >> k; for(ll i=0;i<=n;i++) C[i][0] = 1; for(ll i=1;i<=n;i++) { for(ll j=1;j<=i;j++) C[i][j] = (C[i-1][j] + C[i-1][j-1])%mod; } ll ans = k; ans = (ans * ME(k-1, n-1, mod))%mod; for(ll i=1;i<k-1;i++){ ll M = 1; if(i&1) M = -1; ans = (ans + (((M*(k-i)*ME(k-i-1, n-1, mod))%mod)*C[k][i])%mod + mod)%mod; } cout << ans << endl; return 0; }

the number of different possible color assignments. The number can be quite big, so the King has requested to know the answer modulo 1000000007?

All Answers

Similar questions

need a help?

find thousands of online teachers now