• 问题描述

  给定排列 $A$，求有多少排列 $B$ 可以通过合法的交换从 $A$ 得到。

  交换指交换排列中两个数的位置。一个交换是合法的，当且仅当交换完后逆序对数减少。

  输入格式

  第一行输入 $n$，表示序列 $A$ 的长度。

  第二行读入 $n$ 个整数，表示序列 $A$。

  输出格式

  一行一个数表示答案对 $10^9 + 7$ 取模后的结果。

样例

样例输入 1

4 1 4 2 3

样例输出 1

4

数据范围

对于 $100\%$ 的数据：

• $2 \le n \le 20$
• $A$ 是一个排列