【MX-X6-T5】再生
题目背景
> _このまま$\\$
らったった$\\$
音に乗って$\\$
今きっと世界で僕だけだ$\\$
後ろ向きな歌を聴いて$\\$
少しだけ$\\$
前向きに生きていく_
>
>_—— [再生 - Nanatsukaze](https://music.163.com/#/song?id=2133659925)_
破碎的点依照破碎的规则进行重组，如此再生的一个结构将会是什么样的呢？
题目描述
现有一棵 $n$ 个点的有标号有根树，给定其长链剖分得到的 top 数组，请你输出有多少种不同的树可以在长链剖分之后得到该 top 数组。答案对 $20051131$（质数）取模。
具体来说，对于一棵树 $T$，对所有点 $u$ 定义其树高 $h_u$：
- 如果 $u$ 是叶子，则 $h_u=1$。
- 否则设 $u$ 的孩子集合为 $S_u$，则 $h_u=\max\limits_{v\in S_u}h_v + 1$。
给定数组 $t_{1\cdots n}$，你需要计算有多少种树满足：
- 对于根节点 $r$，满足 $t_r=r$。
- 对于每一个不是叶子的节点 $u$，存在恰好一个孩子 $v$ 满足 $h_v+1=h_u$ 并且 $t_v=t_u$，其他孩子满足 $t_v=v$。
模 $20051131$（质数）。
两棵树不同当且仅当它们的根不同或它们的边集不同。
**保证答案不为 $\bf 0$，但是不保证答案在模意义下不为 $\bf 0$。**
输入输出格式
输入格式
第一行一个正整数 $n$。
接下来一行，$n$ 个空格分隔的正整数 $t_{1\cdots n}$，表示 top 数组。
输出格式
一行一个整数表示答案对 $20051131$ 取模的值。
输入输出样例
输入样例 #1
5
1 1 1 4 4输出样例 #1
2输入样例 #2
16
1 2 1 4 1 4 1 4 9 1 1 12 1 1 12 1输出样例 #2
7181107说明
**【样例解释 #1】**
仅有图中的两种树满足条件。
**【数据范围】**
对于所有数据，保证 $1\leq n\leq 5\times 10^5$，$1\leq t_i\leq i$，保证取模前答案不为 $0$。
**捆绑测试**，共 5 个 Subtask，具体限制如下所示：
- 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）：无特殊限制。