D. Don't be Perfect
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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

Examples
Input
2
1
Output
0
Input
3
1 1
Output
1
Input
6
1 1 3 3 3
Output
2
Input
7
1 1 3 2 3 3
Output
1
Note

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