A tree, rooted at node 1 with N nodes is given and an integer M.

Tree is to be decorated. We have M types of decorations (infinite amount of each is available). A decoration will have a value between 1 to M.

A beautiful leaf is one in which the GCD of the decoration values from root to leaf is greater than one.

For the tree to be beautiful atleast one leaf must be beautiful. Find the number of ways to beautifully decorate the tree (mod 1e9 + 7).

Not Necessarily binary tree

Constraints:
M<=20
N<= 10^5