All Tracks Algorithms Dynamic Programming Dynamic Programming and Bit Masking Problem

Micro and Lucky Tree
Tag(s):

Algorithms, Bitmask, Dynamic Programming, Medium

Problem
Editorial
Analytics

Micro purchased a tree having $$N$$ nodes numbered from $$1$$ to $$N$$. 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 $$M$$ (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:
First line consists of a single integer denoting $$N$$ and $$M$$.
Each of the following $$N-1$$ lines consists of two space separated integers $$X$$ and $$Y$$ denoting there is an edge between nodes numbered $$X$$ and $$Y$$.

Output:
Print the number of ways to make the tree lucky. Since the answer can be large, print it modulo $$10^9+7$$.

Constraints:
$$1 \le N \le 10^5$$
$$1 \le M \le 20$$
$$1 \le X, Y \le N$$

SAMPLE INPUT
3 2
1 2
1 3
SAMPLE OUTPUT
5
Explanation

Following are the 5 valid ways:
$$val[1] = 2, \space val[2] = 1, \space val[3]=1$$
$$val[1] = 1, \space val[2] = 1, \space val[3]=2$$
$$val[1] = 1, \space val[2] = 2, \space val[3]=2$$
$$val[1] = 1, \space val[2] = 1, \space val[3]=1$$
$$val[1] = 1, \space val[2] = 2, \space val[3]=1$$

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic, Kotlin

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

March Easy '17

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications