#P4361. isn

    ID: 3564 传统题 1000ms 512MiB 尝试: 1247 已通过: 449 难度: 7 上传者: 标签>CF2200提高+/省选-计数 DP树状数组离散化补集计数双射计数排列数计算滚动数组数据结构优化DP

isn

题目描述

给出一个长度为 nn 的序列 a1,a2,…,ana_1, a_2, \dots, a_n。
如果序列 aa 不是非降的,你必须不断从中删去一个数,直到 aa 非降为止。

求有多少种不同的操作方案,答案对 109+710^9 + 7 取模。

定义:操作方案不同当且仅当删除的顺序或次数不同。

格式要求

输入

第一行一个整数 nn。
第二行 nn 个整数,表示序列 aa。

输出

一行一个整数,表示操作方案总数对 109+710^9 + 7 取模的结果。

样例

4
1 7 5 3
18

限制

1≤n≤2×1031 \leq n \leq 2 \times 10^3