Red-Black Tree

Time limit3sMemory limit512 MB

Summary

Count the colorings of a binary tree's vertices that satisfy the red-black rules, with fake leaves added at missing children, modulo 1e9+7.

Level: Hard8 of 10
Topics: Dynamic programming, Tree, Combinatorics
Solved: No attempts yet

Problem

Most standard libraries implement the set data structure with a red-black tree. In this problem, you count the ways to color the vertices of a given binary tree so that it becomes a red-black tree. Print the answer modulo $10^9 + 7$ .

In a binary tree, every vertex with fewer than two children gets fake vertices in the places of the missing children. The tree is a red-black tree if all of the following hold.

Each vertex is colored either red or black.
The root and the added fake vertices are black.
The parent of a red vertex is black.
Every path from the root to a fake leaf contains the same number of black vertices.

The parent of a black vertex can be black. Two colorings are different if at least one vertex has a different color.

Input

The first line contains one integer $n$ , the number of vertices in the tree ( $1 \le n \le 500\,000$ ).

The next $n$ lines describe the tree. Line $i$ contains two integers $l_i$ and $r_i$ , the indices of the left and right children of vertex $i$ , or 0 if that child is missing. Here $l_i = 0$ or $i < l_i \le n$ , and $r_i = 0$ or $i < r_i \le n$ . The root is vertex 1. The input always describes a valid tree.

Output

Print one integer, the number of colorings that make the given tree a valid red-black tree, modulo $10^9 + 7$ .

Examples2

Example 1
Input
```
3
2 3
0 0
0 0
```
Expected output
```
2
```
Example 2
Input
```
6
2 4
3 0
0 0
5 6
0 0
0 0
```
Expected output
```
2
```