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

In his ridiculous tree, each index ~i~ ~(2 \le i \le N)~ has a parent index ~p_i~ such that ~1 \le p_i < i~.

Since he's so ridiculous, he wants to count the number of permutations ~q_1, q_2, \dots, q_N~ of the numbers ~1, 2, \dots, N~ such that for every index ~i~ ~(2 \le i \le N)~, there exists no ~j~ ~(1 \le j < i)~ such that ~p_{q_j}=q_i~.

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

Constraints

For all subtasks:

~2 \le N \le 4 \cdot 10^5~

For all ~i~ where ~2 \le i \le N~, ~1 \le p_i < i~.

Subtask 1 [10%]

~2 \le N \le 7~

Subtask 2 [40%]

~2 \le N \le 3\,000~

Subtask 3 [50%]

No additional constraints.

Input Specification

The first line contains the integer ~N~.

The next line contains the integers ~p_2, p_3, \dots, p_N~.

Output Specification

Let ~A~ be the number of permutations that satisfy Ray's requirements, and ~a_1^{b_1} \times a_2^{b_2} \times \dots \times a_k^{b_k}~ be the prime factorization of ~A~ as defined under the fundamental theorem of arithmetic. The primes in the prime factorization will be ordered such that ~a_1 < a_2 < \dots < a_k~.

Note: If ~A=1~, print 0 on a single line instead.

It can also be shown that ~A = 0~ is never possible under the constraints of the problem.

On the first line, output ~k~.

Next, output ~k~ lines of space separated integers, where the ~i^\text{th}~ line contains the integers ~a_i, b_i~.

Sample Input 1

5
1 1 2 3

Sample Output 1

2
2 1
3 1

Sample Explanation 1

There are ~6~ permutations that satisfy Ray's requirements:

• ~1, 2, 3, 4, 5~
• ~1, 2, 3, 5, 4~
• ~1, 2, 4, 3, 5~
• ~1, 3, 2, 4, 5~
• ~1, 3, 2, 5, 4~
• ~1, 3, 5, 2, 4~

The prime factorization of ~6~ is ~2^1 \times 3^1~.

Sample Input 2

2
1

Sample Output 2

0

Sample Explanation 2

There is ~1~ permutation that satisfies Ray's requirements:

• ~1, 2~

As the answer is ~1~, 0 is outputted instead.