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