시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
8 초 512 MB 0 0 0 0.000%

문제

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$.

예제 입력 1

10
0 1
0 1
1 1
0 2
0 3
1 1
0 3
0 3
1 3
1 1

예제 출력 1

2
2
6
6