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 subtasks:
For all where
,
.
Subtask 1 [10%]
Subtask 2 [40%]
Subtask 3 [50%]
No additional constraints.
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.
Comments