## Yet Another Contest 8 P6 - Into the Woods

View as PDF

Points: 20 (partial)
Time limit: 4.0s
Java 7.0s
Python 7.0s
Memory limit: 1G

Author:
Problem types

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 .

for all .

for all .

is prime.

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

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

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

#### Sample Output 2

0
1
931694730