Micro and Lucky Tree

Micro purchased a tree having A nodes numbered from 1 to A. It is rooted at node numbered 1. But unfortunately that tree turned out to be bad luck. After he purchased that tree, he lost his job and girlfriend. So he went to his astrologer friend Mike for help.

Mike told him to assign a value in the range 1 to B (inclusive) to each node making sure that luck factor of all leaf nodes is 1. Luck factor of a leaf node v is defined as gcd of values of all nodes lying in path from root to v (inclusive). Now Micro wants to know how many ways are there to make his tree lucky. That’s where Mike failed, so he asked for your help.

Input Format:

    First argument of input is a integer A
    Second argument of input is a integer B
    Third argument of input is an integer array C of size A. where  C[i] denote the parent of i+1 th node. C[0] = 1

Output Format:

    Return a single integer denoting answer mod 1000000007

Constraints:

    1 <= A <= 50000
    1 <= M <= 30
    1 <= C[i] <= A

For Example:

Example Input 1:
    A = 3, B = 2, C = [1, 1, 1]
Example Output 1:
    5
Explanation 1:
    possible values of node1, node2, node3 are:
    (2, 1, 1)
    (1, 1, 2)
    (1, 2, 2)
    (1, 1, 1)
    (1, 2, 1)
Example Input 2:
    A = 4, B = 3, C = [1, 3, 1, 3]
Example Output 2:
    71
NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details.
Start solving Micro and Lucky Tree on Interview Code Editor
Sign Up
to access hints and editorial solutions for Micro and Lucky Tree

Discussion


Loading...
Click here to start solving coding interview questions