有一个数列 a[1],a[2],...,a[n] ，它是 1,2,...,n 的一个排列。

现在你想对这个数列进行一些变换：每一次可以选择一对 i,j ，满足 1≤i<j≤n 且 a[i]>a[j] ，然后将 a[i] 和a [j] 交换。

问通过若干次(可以 0 次)变换，能得到多少种不同的排列。输出答案对 10^9+7 取模的结果。

第一行，一个整数 n 。
接下来一行 n 个整数 a[1],a[2],...,a[n] 。

输出一个数，表示答案。

4
2 4 1 3

样例输出
8

数据规模
共 10 个测试点。
测试点 1,2,3 满足 n≤10 。
测试点 4,5,6 满足 n≤15 。
对于所有数据，满足 1≤n≤20 。