题目描述

小可刚学完了逆序对，他觉得逆序对还是挺简单的，不就是归并排序求一下。$C$ 老师觉得他太嚣张了，给了他一个问题。

给定一个数组 $a$ ，想问你能否从数组中删除一些数字，使得最终逆序对的数量不变？

输出删除的方案数(一个数都不删也是一种方案,但不允许全都删完)。

逆序对：二元组$(i,j)$,满足$i < j$且$a[i]> a[j]$。

输入格式

第一行为 $n$ , 表示数组长度。

接下来一行 $n$ 个整数，以空格隔开，代表给定的数组 $a_i$。

输出格式

输出一个整数，代表方案数，由于结果可能很大，请对 $1e9+7$ 取模。

样例

2
1 2

3

5
3 5 2 1 4

1

6
1 2 3 6 5 4

8

提示

在样例 $1$ 中，什么数都不删、删除第一个数、删除第二个数，总共三种方案，不能同时删除第一个数和第二个数，因为数组不允许删为空。

数据范围

对于前 $20\%$ 的数据，$1 \le n \le 20$.

对于前 $40\%$ 的数据，$1 \le n \le 1000$.

对于前 $60\%$ 的数据，$1 \le n,a_i \le 10^5$.

对于 $100\%$ 的数据，$1 \le n \le 10^5,1 \le a_i \le 10^9$.