Background

As is well known, as_lky enjoys Galgames.

Problem Description

as_lky has acquired a large number of Galgames (truly a lot!). A Galgame can be described as a combination of many scenes, forming a binary tree rooted at 1, where each node represents a scene. The left and right children of a node correspond to the scenes reached by choosing option A or B in that scene, respectively (which might lead to an empty scene, i.e., the end of the game), referred to as the A-scene and B-scene.

as_lky defines which of two different Galgame scenes is more interesting (the more interesting Galgame depends on which of their initial scenes is more interesting) as follows:

1. If the total number of reachable scenes (i.e., the number of different scenes reachable through any choice, including the scene itself) is different, the one with more reachable scenes is more interesting.
2. If the A-scenes of these two scenes are not equally interesting, the one with the more interesting A-scene is more interesting.
3. Otherwise, the interest of these two scenes is equivalent to the interest of their B-scenes.

Note that the number of reachable scenes for an empty scene is defined as 0.

For example, for the example given in the image (if it does not display properly, please right-click -> view image), we determine which of scenes 1 and 7 is more interesting as follows:

• First, both 1 and 7 have 6 reachable scenes, so we first attempt to compare their A-scenes: 2 and 8.
• Since the number of reachable scenes for 2 and 8 are different (3 and 2, respectively), scene 2 is more interesting than scene 8; consequently, scene 1 is more interesting than scene 7.

as_lky defines two Galgame scenes as essentially the same if and only if both scenes are empty, or their A-scenes and B-scenes are essentially the same.

as_lky considers the interestingness of a Galgame to be the number of possible, essentially different, and less interesting Galgames. Now as_lky has given you a Galgame, please tell him the interestingness of this Galgame modulo $998244353$.

Input Format

The first line contains a positive integer $n$, representing the total number of scenes in this Galgame.

The next $n$ lines each contain two non-negative integers $a_i$ and $b_i$, representing the A-scene and B-scene of that scene, with 0 representing an empty scene. The data is guaranteed to be valid.

Output Format

A single line containing a non-negative integer, representing the interestingness modulo $998244353$.

Sample Input and Output

Input Sample #1

3
0 2
3 0
0 0

Output Sample #1

4

Input Sample #2

7
2 3
4 5
6 7
0 0
0 0
0 0
0 0

Output Sample #2

410

Input Sample #3

9
2 3
4 5
0 0
0 0
6 7
0 0
8 9
0 0
0 0

Output Sample #3

5206

Notes

Sample Explanation

Sample 1: The images below show the Galgame given by as_lky (left) and all four Galgames that are less interesting (right): (if it does not display properly, please right-click -> view image)

Test Point Constraints

This problem is bundled testing.

For all data, $1 \le n \le 10^6$, $0 \le a_i, b_i \le n$.

Specific restrictions for each subtask are shown in the table below:

Special Properties: The data is guaranteed to be uniformly randomly generated, i.e., when $n$ is given, if there are $S$ essentially different Galgames with $n$ scenes, each essentially different Galgame appears with a probability of $\frac{1}{S}$.

The input is large, please use fast input methods.

见题面 Input 部分

见题面 Output 部分