Galgame Interestingness

A Galgame is represented as a collection of scenes arranged in a binary tree with node 1 as its root. Each non‐empty scene is a node that has an A option (left child) and a B option (right child). Choosing an option leads to another scene or to an end (represented as an empty scene). We define an ordering between two (non‐empty) scenes (or games) as follows:

1. If the total number of scenes reachable from the two scenes (including the scene itself) differ, the one with more reachable scenes is more interesting. (An empty scene, by convention, has 0 reachable scenes.)
2. If they have the same reachable scene count then compare the A (left) scenes – the scene whose A option is more interesting is deemed more interesting.
3. If the A scenes are equally interesting then the decision is completely determined by comparing their B (right) scenes.

Note that two Galgame scenes are defined as essentially equivalent if and only if both are empty or their A scenes are essentially equivalent and their B scenes are essentially equivalent.

The interestingness of a Galgame is defined as the number of possible, essentially different Galgames that are strictly less interesting than it. Since this number can be large, you are asked to output it modulo \(998244353\).

The game is given as a binary tree. The input begins with an integer n (\(n \ge 1\)) representing the number of non-empty scenes. The scenes are numbered from 1 to n with scene 1 as the root. Then n lines follow; the i-th line (1-indexed) contains two integers representing the indices of the A scene (left child) and the B scene (right child) of scene i. A value of 0 indicates that the corresponding child is an empty scene (i.e. the game ends).

Ordering and Counting Details. For any Galgame scene \(T\):

• Let \(r(T)\) be the total number of scenes reachable from \(T\) (including \(T\) itself). Hence, for a non-empty scene \(T\) with left and right subtrees \(L\) and \(R\), we have \[ r(T)=1+r(L)+r(R),\] and for the empty scene, \(r(\varnothing)=0\).
• For two non-empty scenes \(T_1=(L_1, R_1)\) and \(T_2=(L_2, R_2)\), the ordering is defined by:
  1. If \(r(T_1) \neq r(T_2)\), then \(T_1\) is more interesting if \(r(T_1)>r(T_2)\).
  2. If \(r(T_1)=r(T_2)\) but the A (left) scenes differ in interestingness, then the one with the more interesting A scene is more interesting.
  3. If the A scenes are essentially equivalent then the decision is determined by comparing the B (right) scenes.

Denote by \(a(n)\) the number of essentially different Galgame scenes (binary trees) that have exactly \(n\) nodes (non-empty scenes). They are defined recursively by:

[ a(0)=1 \quad (\text{empty scene}), \qquad a(n)=\sum_{t=0}^{n-1} a(t)\cdot a(n-1-t) \quad \text{for } n\ge1. ]

Let the given Galgame have a total of \(N\) nodes. Then all Galgames with fewer nodes (i.e. reachable scene count less than \(N\)) are automatically less interesting. For those with exactly \(N\) nodes, assume that a non-empty Galgame \(T=(L,R)\) (with \(r(T)=N\)) has a rank defined as follows:

[ \text{rank}(T)= \sum_{t=0}^{i-1}a(t)\cdot a((i+j)-t) ; + ; \text{rank}(L)\cdot a(j) ; + ; \text{rank}(R), ]

where \(i=r(L)\) and \(j=r(R)\) (so that \(i+j=N-1\)). The interestingness of the Galgame is then

[ \text{Answer} = \left(\sum_{k=0}^{N-1}a(k)\right) + \text{rank}(T) \mod 998244353. ]

</p>

Your task is to compute this value.

inputFormat

The first line of input contains a single integer n (\(1 \le n \le \text{small}\)) representing the number of non-empty scenes.

Each of the following n lines contains two integers. The i-th line contains two integers representing the indices of the A scene (left child) and the B scene (right child) of scene i. A value of 0 denotes an empty scene.

outputFormat

Output a single integer: the interestingness of the given Galgame modulo \(998244353\).

sample

3
2 3
0 0
0 0

4

</p>