Background

Original problem link: https://oier.team/problems/X6F。

このまま$\\$ らったった$\\$ 音に乗って$\\$ 今きっと世界で僕だけだ$\\$ 後ろ向きな歌を聴いて$\\$ 少しだけ$\\$ 前向きに生きていく

—— 再生 - Nanatsukaze

Broken points are recombined according to broken rules. What kind of structure will be “regenerated” in this way?

Problem Description

You are given a labeled rooted tree with $n$ nodes, and the array top obtained from its long-chain decomposition. Please output how many different trees can produce this top array after long-chain decomposition. The answer should be taken modulo $20051131$ (a prime).

More precisely, for a tree $T$, define the height $h_u$ of every node $u$:

• If $u$ is a leaf, then $h_u = 1$。
• Otherwise, let the set of children of $u$ be $S_u$, then $h_u = \max\limits_{v \in S_u} h_v + 1$。

Given an array $t_{1\cdots n}$, you need to count how many trees satisfy:

• For the root node $r$, $t_r = r$。
• For every non-leaf node $u$, there exists exactly one child $v$ such that $h_v + 1 = h_u$ and $t_v = t_u$, and every other child satisfies $t_v = v$。

Take the result modulo $20051131$ (a prime).

Two trees are different if and only if their roots are different or their edge sets are different.

It is guaranteed that the answer is not $\bf 0$ before taking modulo, but it is not guaranteed to be non-zero modulo $20051131$.

Input Format

The first line contains a positive integer $n$。

The next line contains $n$ positive integers $t_{1\cdots n}$ separated by spaces, representing the top array.

Output Format

Output one integer: the answer modulo $20051131$。

5
1 1 1 4 4

2

16
1 2 1 4 1 4 1 4 9 1 1 12 1 1 12 1

7181107

Hint

Sample Explanation #1

Only the two trees in the figure satisfy the conditions.

Constraints

For all testdata, it is guaranteed that $1 \leq n \leq 5 \times 10^5$，$1 \leq t_i \leq i$，and the answer before taking modulo is not $0$。

Bundled test: 5 subtasks, with the following limits:

• Subtask 1 (11 pts): $t_i = 1$。
• Subtask 2 (24 pts): $n \leq 5$。
• Subtask 3 (17 pts): $n \leq 16$。
• Subtask 4 (22 pts): $n \leq 2 \times 10^3$。
• Subtask 5 (26 pts): no special restrictions.

Translated by ChatGPT 5