A tree is given having N nodes numbered from 1 to N, rooted at 1. We are also given a positive integer M, the value of each node can be anything from 1 to M.
Let's say a tree is beautiful if there is at least one leaf node such that gcd of values of each node on the path from that leaf node to the root node is greater than 1.
Now, we need to calculate the number of ways in which we can assign values to all the nodes such that we get a beautiful tree. Two ways are different if there is at least one node having different values. We are supposed to return the answer modulo 1e9 + 7.
Constraints:
- 1 ≤ N ≤ 1e5
- 1 ≤ M ≤ 20
Note: This problem is not from any running contest, it was asked in the campus placement test.