19017번 - Automorphism 다국어

문제

You are given a rooted tree. Initially, it contains one vertex labeled as 1ドル$.

Your task is to process $m$ operations of two types:

• Add a new vertex to the tree.
• Calculate the number of automorphisms of the subtree rooted at vertex $u$.

As the numbers can be very large, find them modulo 998ドル,244円,353円$.

For a rooted tree, whose root is $r$ and vertex set is $S,ドル the automorphism is a bijection $f: S \to S$ such that $f(r) = r$ and $\forall u, v \in S,ドル $f(u)$ is the parent of $f(v)$ if and only if $u$ is the parent of $v$.

입력

The first line contains one integer $m$ (1ドル \leq m \leq 3 \cdot 10^5$).

In the following $m$ lines, each line indicates an operation.
Each of these lines contains two integers $t$ and $x$ (0ドル \leq t \leq 1$).

If $t = 0,ドル add a new vertex labeled by the current maximum label plus 1ドル$. Add an edge between this new vertex and the vertex $x$.

If $t = 1,ドル calculate the number of automorphisms of the subtree of vertex $x$.

It is guaranteed that, for each operation, the value of $x$ is between 1ドル$ and the current maximum label.

출력

For each calculate operation, print a single line with the number of automorphisms modulo 998ドル,244円,353円$.

제한

힌트