 Final
 Elimination
 Third qual
 Second qual
 First qual
 Warmup
Second qualification round completed
Tasks
Show one task per page / all tasks on one page
Time limit  3 seconds 

Memory limit  256 megabytes 
Did you now that most standard libraries use redblack tree to implement "set" data structure? In this problem you have to find the number of ways to color the vertices of the given binary tree so that it became redblack. Print the answer modulo 10^{9} + 7.
Consider a binary tree. If the vertex has less than two children, add fake vertices to the potential places of the missing children. The tree is called a redblack tree if the following constraints are satisfied:
 Each vertex is colored one of the two colors: red or black.
 The root of the tree and added fake vertices are colored black.
 The parent of a red vertex is black.
 All paths the root to fake leafs contain the same number of black vertices.
Note that the parent of a black vertex can be black itself.
Two ways to color the tree are different if there is a vertex that has different colors.
The picture shows two ways to color the tree from the second test case.
Input format 
The first line contains one integer n — the number of vertices in a tree (1 ≤ n ≤ 500 000). The following n lines describe a tree. The ith of these lines contains two integers l_{i} and r_{i} — the indices of the left and the right child of the ith vertex, or 0 if the corresponding child is missing (l_{i} = 0 or i < l_{i} ≤ n; r_{i} = 0 or i < r_{i} ≤ n). The root of the tree has number 1. Input describes the correct tree. 

Output format 
Output one integer — the number of ways to color the given tree so that it was a correct redblack tree. The answer must be printed modulo 10^{9} + 7. 
Examples 
Input data
3 2 3 0 0 0 0
Output data
2 
Input data
6 2 4 3 0 0 0 5 6 0 0 0 0
Output data
2 

