There is a tree with
Taro has decided to paint each vertex in white or black, so that any black vertex can be reached from any other black vertex by passing through only black vertices.
You are given a positive integer
- Assuming that Vertex
has to be black, find the number of ways in which the vertices can be painted, modulo .
Constraints
- All values in input are integers.
- The given graph is a tree.
Input Specification
The first line will contain two integers
The next
Output Specification
Print
- Assuming that Vertex
has to be black, find the number of ways in which the vertices can be painted, modulo .
Sample Input 1
3 100
1 2
2 3
Sample Output 1
3
4
3
Explanation For Sample 1
There are seven ways to paint the vertices, as shown in the figure below. Among them, there are three ways such that Vertex
Sample Input 2
4 100
1 2
1 3
1 4
Sample Output 2
8
5
5
5
Sample Input 3
1 100
Sample Output 3
1
Sample Input 4
10 2
8 5
10 8
6 5
1 5
4 8
2 10
3 6
9 2
1 7
Sample Output 4
0
0
1
1
1
0
1
0
1
1
Explanation For Sample 4
Be sure to print the answers modulo
Comments