Master Jie has a country with N cities and N-1 roads which form a tree and the capital city 1 is considered as the root of the tree.
As the king of the country,Master Jie wants todominate this country .Since he likes Orz pandas well much,so he decidesto sendN Orz pandas to those cities and each city will have one and only oneOrz panda.
Now Master Jie has NOrz pandas numbered 1 to N,and the ithOrz pandas has an ability value i.
In his country, there are M cities is considered "important",and theOrz pandaof an important city must be a "dominator".
We think anOrz pandais adominatorif and only if he has the maximum ability value in his subcities.
His subcities means the cities in the subtree of his city.
Now Master Jie wants to know how many different ways he has to send theOrz pandas so that each important city has adominator.
But he is too busy to manage his country, can you help him ?