Alice has received a beautiful tree as a gift from her math teacher. This tree has N nodes connected by N−1 edges, and each node is assigned a value represented by arr[i].
Alice enjoys playing with this tree by cutting certain edges and dividing it into multiple subtrees. She has a favorite number X, and she's curious to find out the number of ways she can cut the tree into subtrees so that the sum of values in each subtree is divisible by X. The cutting order of the edges doesn't matter.
Help Alice solve this interesting problem by determining the count of good cuttings she can make when dividing the initial tree into 1 subtree, 2 subtrees, 3 subtrees, and so on, up to N subtrees.
As the number of good cuttings can be huge you need to print the answer modulo 109+7.
Input format
Output format
Constraints
In the first test case -: