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 to dominate this country .Since he likes Orz pandas well much,so he decides to send N Orz pandas to those cities and each city will have one and only one Orz panda.
Now Master Jie has N Orz pandas numbered 1 to N,and the ith Orz pandas has an ability value i.
In his country, there are M cities is considered "important",and the Orz panda of an important city must be a "dominator".
We think an Orz panda is a dominator if 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 the Orz pandas so that each important city has a dominator.
But he is too busy to manage his country, can you help him ?