#P18554. Guess The Sequence 2
Guess The Sequence 2
Guess The Sequence 2
Little K 有一个 的随机排列 。他准备给朋友 Little Cyan Fish 出一道猜排列的题。
Little K 可以选择排列的一个子段集合,并告诉 Little Cyan Fish 每个所选子段的最大值。
形式化地,他可以选择集合 ,其中对所有 都有 。随后,Little Cyan Fish 会得到 个三元组
其中 ,表示第 个所选子段的最大值。
Little Cyan Fish 需要猜出 Little K 的排列。作为最好的朋友,Little K 希望自己给出的信息足以使对方正确猜出排列。因此,必须恰好只有一个 的排列满足所提供的全部信息。
Little K 想知道,有多少个不同的子段集合能够使 Little Cyan Fish 唯一确定这个排列。请帮助他计算答案。答案可能很大,请输出它对 取模后的值。
这里选择的是集合,相同子段不会重复出现,提供信息的顺序不产生新方案。
输入格式
第一行包含一个整数 ()。
第二行包含 个整数 (),它们构成 的一个排列。
保证给定排列是从长度为 的全部排列中等概率随机选出的。
输出格式
输出一行一个整数,表示答案对 取模后的值。
原样例 1
2
1 2
6
原样例 2
4
1 4 2 3
532