Andy is quite the fun guy. Bored with playing minecraft, he decides to venture out into the real world. Somehow, he wanders into an enchanted forest littered with various magical mushrooms.

After spending some time there, Andy observes that there are ~N~ distinct kinds of mushrooms, which he labels from type ~0~ to ~N-1~. He also discovers that these mushrooms have a strange property: when the spores from mushrooms of type ~x~ and ~y~ come into contact, new mushrooms of type ~xy\pmod{N}~ are produced. Additionally, Andy notices that some of these mushrooms are able to use this method to produce mushrooms of type ~1~, starting with an unlimited number of spores of that mushroom. He calls any such type of mushroom an enigma mushroom.

As Andy journeys further into the woods, he finds a strange tree with ~N~ nodes labelled from ~0~ to ~N-1~. The tree is rooted at node ~0~, and the parent of node ~i~ is ~u_i~ for all ~i > 0~. He notices that a single type of mushroom grows on each node, and moreover, these types are pairwise distinct. That is, ~p_0, \ldots, p_{N-1}~ is a permutation of ~0,\ldots,N-1~, where ~p_i~ is the type of mushroom that grows on node ~i~.

Andy considers of a subtree of this tree, ~S~, to be enigmatic if the following conditions are met:

• The only mushrooms in ~S~ are enigma mushrooms.
• All mushrooms types that can be produced through spores by the mushrooms in ~S~ are already in ~S~.
• There exists a type of mushroom in ~S~ such that it is possible to grow every type of mushroom in ~S~ starting only with spores of this type.

Andy can't identify each mushroom individually, so he wants to know the minimum and maximum possible numbers of enigmatic subtrees over all possible ~p_0,\ldots,p_{N-1}~, as well as the expected number of enigmatic subtrees, modulo ~998244353~, supposing that ~p_0,\ldots,p_{N-1}~ is a uniformly random permutation. He stubbornly refuses to leave until he gets his answers. Can you help out and get Andy out of the woods?

How to print an expected value modulo ~998244353~

It can be proven that the expected value to be found in this problem can be expressed uniquely as an irreducible fraction ~\frac{x}{y}~, with ~y~ not divisible by ~998244353~. There exists a unique integer ~z~ between ~0~ and ~998244352~, inclusive, such that ~yz\equiv x\pmod{998244353}~. Report this ~z~.

Constraints

~2 \le N \le 10^6~

~0\le u_i < i~ for all ~i~.

Subtask 1 [10%]

~2 \le N \le 8~

Subtask 2 [10%]

~u_i = 0~ for all ~i~.

Subtask 3 [20%]

~N~ is prime.

Subtask 4 [20%]

~2 \le N \le 5\times 10^3~

Subtask 5 [20%]

~2 \le N \le 3\times10^5~

Subtask 6 [20%]

No additional constraints.

Input Specification

The first line contains the integer ~N~.

The second line contains ~N-1~ integers ~u_1,\ldots, u_{N-1}~.

Output Specification

On the first line, print the minimal number of enigmatic subtrees over all ~p_0,\ldots,p_{N-1}~.

On the second line, print the maximal number of enigmatic subtrees over all ~p_0,\ldots,p_{N-1}~.

On the third line, print the expected number of enigmatic subtrees over all ~p_0,\ldots,p_{N-1}~, modulo ~998244353~.

Scoring

You will receive ~0\%~ of the points if you do not print three lines, where the first two lines contain a single integer between ~0~ and ~N~, inclusive, and the third line contains a single integer between ~0~ and ~998244352~, inclusive.

You will receive ~10\%~ of the points if your first line of output contains the correct answer.

You will receive ~50\%~ of the points if your second line of output contains the correct answer.

You will receive ~40\%~ of the points if your third line of output contains the correct answer.

The score for a subtask is the minimum score amongst any testcase in the subtask.

Sample Input 1

5
0 1 1 1

Sample Output 1

0
2
399297742

Explanation for Sample Output 1

A diagram of the tree with the nodes labelled is provided below.

First, note that it can be shown that mushrooms of type ~1,2,3,4~ are enigmatic, while mushrooms of type ~0~ are not.

Now consider the permutation ~p=[1, 0, 4, 2, 3]~. In subtrees rooted at node ~0~ and ~1~, there exists a mushroom that is not enigmatic. In any other subtree, it can be shown that it can produce a mushroom type not in the subtree. Thus, there are no enigmatic subtrees.

Then, consider the permutation ~p=[0, 2, 1, 4, 3]~. The subtree rooted at node ~1~ contains all types of enigmatic mushrooms. Moreover, it can be shown that any two mushrooms in the subtree produce another type of mushroom in the subtree. Finally, mushrooms of type ~2~ in the subtree can produce mushrooms of type ~4~, which then may be used to produce mushrooms of type ~1~ and ~3~. Thus, this subtree is an enigmatic subtree. The subtree rooted at ~2~ is also enigmatic. It can be shown that this is the maximum possible number of enigmatic subtrees.

It can be shown that over the ~5!=120~ different possible permutations of ~p_0,\ldots,p_{N-1}~, ~42~ permutations yield ~0~ enigmatic subtrees, ~60~ permutations yield ~1~ enigmatic subtree, while the remaining ~18~ permutations yield ~2~ enigmatic subtrees. Thus, the desired expected value is ~\frac{42}{120}(0)+\frac{60}{120}(1)+\frac{18}{120}(2)=\frac{4}{5}\equiv399297742\pmod{998244353}~.

Sample Input 2

15
0 0 1 1 2 2 3 3 4 4 5 5 6 6

Sample Output 2

0
1
931694730