题目描述

给出一个长度为 $n$ 的序列 $a_1, a_2, \dots, a_n$。
如果序列 $a$ 不是非降的，你必须不断从中删去一个数，直到 $a$ 非降为止。

求有多少种不同的操作方案，答案对 $10^9 + 7$ 取模。

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

格式要求

输入

第一行一个整数 $n$。
第二行 $n$ 个整数，表示序列 $a$。

输出

一行一个整数，表示操作方案总数对 $10^9 + 7$ 取模的结果。

样例

4
1 7 5 3

18

限制

$1 \leq n \leq 2 \times 10^3$