配点 : 1300 点
故事
这次,我们终于打倒了敌人。回家的途中,我想起了一件事。
在世界的里侧,这个世界的基盘之外也存在着基盘。那些基盘已经完全破碎,可能已经灭亡了。也许,在那个世界里也发生了像这次一样的事情,于是新的基盘和世界被创造出来,如果是这样的话——我们就阻止了那个连锁反应。
正当我在想着这些事情时,从身后传来了色叶酱的声音。
“前辈!”
問題文
N 两个世界左右排成一列。
每个世界都拥有“自然性”这一固有的数值,从左到右。p_1,p_2,..,p_N的顺序排列,1 减去 N 组成了重新排列的数列。
这个数列,N 仅以为元素的长度 1 列为起点,通过“选择一个项,在其右边插入一个比它小的值”这种操作重复而生成的。
求给定数列生成方法的可能种类数,10^9+7 除的余数。
但是,两种“数列生成方法”不同,是指在某一次操作中,选中的项和插入的值至少有一个不同。 1 以上 N-1 的整数
给出了 k 存在,
由k 这意味着,在某一次操作中,选中的项和插入的值至少有一方同时不同。
制約
- 所有输入均为整数
- 1 \leq N \leq 2\times 10^5
- p_1 = N
- p_1,p_2,...,p_N 是 您也可以写 \{1,...,N\} 的排列 给出了
入力
输入是按以下格式从标准输入给出的。
N p_1 p_2 ... p_N
出力
请打印答案。 到达
入力例 1
4 4 2 3 1
出力例 1
3
产生这个排列的操作方法是实现以下所示的列变化3是的。
请注意,我们正在寻找除以
、{4}→{4,3}→{4,2,3}→{4,2,3,1}
、{4}→{4,3}→{4,3,1}→{4,2,3,1}
、{4}→{4,1}→{4,3,1}→{4,2,3,1}
入力例 2
4 4 3 2 1
出力例 2
6
入力例 3
7 7 6 3 4 1 2 5
出力例 3
36
入力例 4
30 30 4 26 15 21 19 14 8 12 7 16 20 2 5 25 13 3 23 18 29 10 27 1 28 9 6 11 24 22 17
出力例 4
321470237