Appleby Contest '20 P5 - Ridiculous Tree

View as PDF

Points: 15 (partial)
Time limit: 2.0s
Memory limit: 1G

Author:
Problem types

Ridiculous Ray has a ridiculous tree! Oh what crazy things can he do with thee!

In his ridiculous tree, each index has a parent index such that .

Since he's so ridiculous, he wants to count the number of permutations of the numbers such that for every index , there exists no such that .

As the answer can be very large, he wants you to output the prime factorization of it instead.

Constraints

For all where , .

Input Specification

The first line contains the integer .

The next line contains the integers .

Output Specification

Let be the number of permutations that satisfy Ray's requirements, and be the prime factorization of as defined under the fundamental theorem of arithmetic. The primes in the prime factorization will be ordered such that .

Note: If , print 0 on a single line instead.

It can also be shown that is never possible under the constraints of the problem.

On the first line, output .

Next, output lines of space separated integers, where the line contains the integers .

Sample Input 1

5
1 1 2 3

Sample Output 1

2
2 1
3 1

Sample Explanation 1

There are permutations that satisfy Ray's requirements:

The prime factorization of is .

Sample Input 2

2
1

Sample Output 2

0

Sample Explanation 2

There is permutation that satisfies Ray's requirements:

As the answer is , 0 is outputted instead.