Problem Description

Given a tree with \( N \) vertices. The vertices are numbered \( 1, 2, \ldots, N \), and the \( i \)-th edge connects vertices \( a_i \) and \( b_i \).

Consider writing integers \( 1, 2, \ldots, N \) into the vertices, one integer per vertex. Let \( c_i \) be the value written on vertex \( i \).

However, if vertices \( u \) and \( v \) are adjacent, i.e., there is an edge \( (u, v) \), then \( |c_u - c_v| \leq 2 \) must be satisfied.

How many such ways of writing are there? Find the answer modulo \( 1000000007 = 10^9 + 7 \).

Input Format

The input is given from the standard input in the following format:

\( N \) \( a_1 \) \( b_1 \) \( a_2 \) \( b_2 \) \( : \) \( a_{N-1} \) \( b_{N-1} \)

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

5
1 2
1 3
1 4
1 5

Sample Output #1

24

Sample Input #2

6
1 2
1 3
1 4
1 5
1 6

Sample Output #2

0

Sample Input #3

4
1 2
2 3
3 4

Sample Output #3

12

Sample Input #4

7
1 3
2 3
4 3
5 4
5 6
5 7

Sample Output #4

48

Notes/Hints

Constraints

• \( 1 \leq N \leq 50 \)
• \( 1 \leq a_i, b_i \leq N \)
• The input forms a tree

Sample Explanation 1

Vertex \( 1 \) must be written with \( 3 \).

见题面 Input 部分

见题面 Output 部分