Hide

Problem DDon't be Perfect

Mara hates the word “perfect” - it means there’s nothing left to improve! That’s why she really hates graphs with perfect matchings - surely there’s something that can be done to make them better, so they shouldn’t be called perfect!

You are given a randomly generated tree $T$ with $N$ vertices. The $i$-th edge connects vertices $P_{i+1}$ and $i+1$ ($1 \leq i \leq N-1$). The value of $P_ i$ ($2 \leq i \leq N$) is uniformly and independently chosen from the set $\{ 1, 2, \ldots , i-1\}$.

According to Mara, a graph $G = (V, E)$ is good (but definitely not perfect) if all of the following conditions are satisfied:

• The graph is simple, connected, and has no self-loops.

• The graph has $N$ vertices.

• For every edge $(u, v) \in E(T)$ in the tree, the edge $(u, v) \in E(G)$ is in the graph $G$ as well.

• The graph $G$ has no perfect matching. A perfect matching in a graph exists if and only if there is a set of edges $M \subseteq E(G)$ such that each vertex in the graph is incident to exactly one edge in the set $M$.

• For all pairs of vertices such that $1 \leq u < v \leq N$ and the edge $(u, v) \not\in E(G)$ is not in the graph $G$, if we add the edge $(u, v)$ to the graph $G$, the graph will have a perfect matching. In other words, there is no way to add an additional edge to the graph $G$ such that the graph remains simple, connected, has no self-loops, and does not have a perfect matching.

As a gift for Mara, you want to construct a set $S$ of good graphs, such that the size of the set $S$ is maximum possible. However, you realize that two isomorphic graphs are really just duplicates of each other, so you also want to ensure that no two graphs in the set $S$ are isomorphic to each other.

Find the maximum value of $|S|$. Since the value of $|S|$ may be very large, you only need to output the value of $|S| \bmod 998\, 244\, 353$.

Formally, let $\mathcal{G}$ be the set of all good graphs. You want to construct a set $S \subseteq \mathcal{G}$ of good graphs, such that for any distinct pairs of graphs $G_1, G_2 \in S$, $G_1$ and $G_2$ are not isomorphic, and the size of the set $S$ is maximum possible.

Input

The first line of input contains an integer $N$ ($2 \leq N \leq 25$), the number of vertices in the tree.

The second line of input contains $N-1$ integers $P_2, P_3, \ldots , P_ N$ ($1 \leq P_ i \leq i-1$), representing the edges of the tree.

There are 20 test cases in total, excluding the sample test case. It is guaranteed that each $P_ i$ ($2 \leq i \leq N$) is chosen uniformly and independently from the set $\{ 1, 2, \ldots , i-1\}$.

Output

Output a single integer $|S|$, the maximum number of good graphs in the set $S$, modulo $998\, 244\, 353$.

Explanation

In sample 1, the tree $T$ already has a perfect matching, hence there is no way to construct a good graph.

In sample 2, we can construct $S$ with the following graph:

There is no way to add an edge to the graph such that the graph remains simple and has no self-loops, so the graph is good. The maximum value of $|S|$ is 1.

In sample 3, we can construct $S$ with the following two graphs:

Both graphs are good and not isomorphic to each other. It can be proven that the maximum value of $|S|$ is 2.

However, we cannot insert the following graph into $S$, as it is isomorphic to the first graph in $S$:

Sample Input 1 Sample Output 1
2
1

0

Sample Input 2 Sample Output 2
3
1 1

1

Sample Input 3 Sample Output 3
6
1 1 3 3 3

2

Sample Input 4 Sample Output 4
7
1 1 3 2 3 3

1

Hide