P7118 Galgame

As everyone knows, as_lky likes Galgame.

as_lky has obtained many Galgames (really many!). A Galgame can be described as a combination of many scenes (Scene), which form a binary tree **rooted at 1**. Each node is a scene. The left child and right child of a node correspond to the scenes you can reach by choosing option A and option B in that scene (you may reach an empty scene, i.e. the game ends). We call them the A scene and the B scene. as_lky defines which of two different Galgame scenes is more interesting (and which of two Galgames is more interesting depends on which initial scene is more interesting) as follows: 1. If the total number of scenes reachable from these two scenes (i.e. the total number of distinct scenes that can be reached by any choices, including the scene itself) is different, then the one from which more scenes are reachable is more interesting. 2. If their A scenes are not equally interesting, then the scene whose A scene is more interesting is more interesting. 3. Otherwise, which one is more interesting is completely equivalent to which one has a more interesting B scene. Note that the number of scenes reachable from an empty scene is defined as 0.  For example, for the case shown in the figure above (if you cannot view it normally, please `right click -> view image`), we determine which of scenes 1 and 7 is more interesting as follows: - First, the numbers of reachable scenes from 1 and 7 are both 6, so we first try to compare their A scenes: 2 and 8. - Since the numbers of reachable scenes from 2 and 8 are different (3 and 2 respectively), scene 2 is more interesting than scene 8; therefore, scene 1 is more interesting than scene 7. as_lky defines two Galgame scenes to be essentially the same if and only if both scenes are empty scenes, or their A scenes are essentially the same and their B scenes are essentially the same. as_lky believes that the interestingness of a Galgame is the number of all possible Galgames that are essentially different and are not as interesting as this Galgame. Now as_lky gives you a Galgame. Please tell him the interestingness of this Galgame. as_lky thinks this number may be large, so he wants you to output the result modulo $998244353$.

The first line contains a positive integer $n$, which represents the number of scenes in this Galgame. The next $n$ lines each contain two non-negative integers $a_i$ and $b_i$, which represent the A scene and the B scene of this scene respectively. 0 represents an empty scene. The input is guaranteed to be valid.

Output one non-negative integer in one line, representing the interestingness modulo $998244353$.

### Sample Explanation Sample 1: The figure below shows the Galgame given to you by as_lky (left) and all four Galgames that are less interesting than this Galgame (right): (if you cannot view it normally, please `right click -> view image`).  ### Constraints **This problem uses bundled tests.** For all testdata, $1\le n\le 10^6$, $0\le a_i,b_i\le n$. The specific limits for each subtask are shown in the table below: | Subtask ID | Points | $n\le$ | Special Property | |:-:|:-:|:-:|:-:| | 1 | 10 | $10$ | $\times$ | | 2 | 20 | $5000$ | $\times$ | | 3 | 30 | $10^6$ | $\surd$ | | 4 | 40 | $10^6$ | $\times$ | Special property: The data is guaranteed to be generated uniformly at random. That is, when $n$ is fixed, if there are $S$ essentially different Galgames with $n$ scenes in total, then each essentially different Galgame appears with probability $\frac{1}{S}$. **The input size is large, so please use a fast input method.** Translated by ChatGPT 5