排列

题目描述 有一个数列 𝑎𝑎1 , 𝑎𝑎2 , … , 𝑎𝑎𝑛𝑛 ，它是1,2, … , 𝑛𝑛 的一个排列。

现在你想对这个数列进行一些变换：每一次可以选择一对 𝑖𝑖, 𝑗𝑗，满足1 ≤ 𝑖𝑖 < 𝑗𝑗 ≤ 𝑛𝑛 且𝑎𝑎𝑖𝑖 > 𝑎𝑎𝑗𝑗 ，然后将𝑎𝑎𝑖𝑖 和𝑎𝑎𝑗𝑗 交换。

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

输入格式 第一行，一个整数𝑛𝑛。

接下来一行𝑛𝑛个整数𝑎𝑎1 , 𝑎𝑎2 , … , 𝑎𝑎𝑛𝑛 。

输出格式 输出一个数，表示答案。

样例输入 1 4 2 4 1 3

样例输出 1 8

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

数据规模 共 10 个测试点。

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

测试点4,5,6满足𝑛𝑛 ≤ 15。

对于所有数据，满足1 ≤ 𝑛𝑛 ≤ 20。