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
distinct kinds of mushrooms, which he labels from type
to
. He also discovers that these mushrooms have a strange property: when the spores from mushrooms of type
and
come into contact, new mushrooms of type
are produced. Additionally, Andy notices that some of these mushrooms are able to use this method to produce mushrooms of type
, 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
nodes labelled from
to
. The tree is rooted at node
, and the parent of node
is
for all
. He notices that a single type of mushroom grows on each node, and moreover, these types are pairwise distinct. That is,
is a permutation of
, where
is the type of mushroom that grows on node
.
Andy considers of a subtree of this tree,
, to be enigmatic if the following conditions are met:
- The only mushrooms in
are enigma mushrooms.
- All mushrooms types that can be produced through spores by the mushrooms in
are already in
.
- There exists a type of mushroom in
such that it is possible to grow every type of mushroom in
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
, as well as the expected number of enigmatic subtrees, modulo
, supposing that
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
It can be proven that the expected value to be found in this problem can be expressed uniquely as an irreducible fraction
, with
not divisible by
. There exists a unique integer
between
and
, inclusive, such that
. Report this
.
Constraints

for all
.
Subtask 1 [10%]

Subtask 2 [10%]
for all
.
Subtask 3 [20%]
is prime.
Subtask 4 [20%]

Subtask 5 [20%]

Subtask 6 [20%]
No additional constraints.
Input Specification
The first line contains the integer
.
The second line contains
integers
.
Output Specification
On the first line, print the minimal number of enigmatic subtrees over all
.
On the second line, print the maximal number of enigmatic subtrees over all
.
On the third line, print the expected number of enigmatic subtrees over all
, modulo
.
Scoring
You will receive
of the points if you do not print three lines, where the first two lines contain a single integer between
and
, inclusive, and the third line contains a single integer between
and
, inclusive.
You will receive
of the points if your first line of output contains the correct answer.
You will receive
of the points if your second line of output contains the correct answer.
You will receive
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
Copy
5
0 1 1 1
Sample Output 1
Copy
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
are enigmatic, while mushrooms of type
are not.
Now consider the permutation
. In subtrees rooted at node
and
, 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
. The subtree rooted at node
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
in the subtree can produce mushrooms of type
, which then may be used to produce mushrooms of type
and
. Thus, this subtree is an enigmatic subtree. The subtree rooted at
is also enigmatic. It can be shown that this is the maximum possible number of enigmatic subtrees.
It can be shown that over the
different possible permutations of
,
permutations yield
enigmatic subtrees,
permutations yield
enigmatic subtree, while the remaining
permutations yield
enigmatic subtrees. Thus, the desired expected value is
.
Sample Input 2
Copy
15
0 0 1 1 2 2 3 3 4 4 5 5 6 6
Sample Output 2
Copy
0
1
931694730
Comments