题目背景

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

—— 再生 - Nanatsukaze

破碎的点依照破碎的规则进行重组，如此再生的一个结构将会是什么样的呢？

题目描述

现有一棵 $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$ 取模的值。

样例

5
1 1 1 4 4

2

样例 1 解释

仅有图中的两种树满足条件。

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

7181107

数据范围

对于所有数据，保证 $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）：无特殊限制。