排列

题目描述 小 L 喜欢排列。

这天，小 L 生成了一个排列 {𝑝𝑝𝑛𝑛 }，又在上面进行了若干次操作。

每次操作可以把相邻两个数变成他们的较小值。

小 L 想知道，在进行任意次操作后，他一共可以得到多少种序列。

答案对 109 + 7 取模。

输入格式 第一行一个整数 𝑛𝑛 表示排列长度。

接下来一行 𝑛𝑛 个整数表示排列。

输出格式 一行一个整数表示答案对 109 + 7 取模后的结果。

样例输入 1 4 2 3 1 4

样例输出 1 6

样例解释 1 可以得到 {1}, {2,1}, {1,4}, {2,1,4}, {2,3,1}, {2,3,1,4} 六种数列。

样例输入输出 2 见下发文件。

样例输入输出 3 见下发文件。

数据规模 共 10 个测试点。

测试点1,2满足𝑛𝑛 ≤ 10。

测试点3,4满足𝑛𝑛 ≤ 1000。 测试点5,6满足𝑛𝑛 ≤ 3 × 105 , 𝑝𝑝𝑖𝑖 = 𝑖𝑖。

测试点7,8满足𝑛𝑛 ≤ 3 × 105 。

对于所有数据满足𝑛𝑛 ≤ 2 × 106 。