← 返回题目列表

AtCoder · iroha2019_day4_k

K. 世界线

中文机器翻译题面 查看原题

配点 : 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

解説

解説