题目描述

小蓝正在两台电脑之间拷贝数据，数据是一个 $n \times m$ 大小的正整数矩阵，因此总共有 $n \times m + 2$ 个由空格分开的整数，其中前两个整数分别为 $n$ 和 $m$。然而，有黑客入侵了小蓝的电脑，导致这 $n \times m + 2$ 个正整数的顺序被打乱了。小蓝想知道最多可能有多少个不同的原矩阵。

两个矩阵相同当且仅当它们行数相同、列数相同，且每个位置上的数相同。

输入格式

输入的第一行包含一个正整数 $n \times m + 2$。

第二行包含 $n \times m + 2$ 个正整数 $a_1, a_2, \cdots, a_{n \times m+2}$，相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。答案可能很大，请输出答案除以 $1000000007$ 的余数。

样例

6
2 2 1 4 3 3

24

解释 #1

可能的原矩阵情况包括：

1. $(n,m)=(1,4)$：有 $6$ 种原矩阵：$(2, 2, 3, 3), (2, 3, 2, 3), (2, 3, 3, 2), (3, 2, 2, 3), (3, 2, 3, 2), (3, 3, 2, 2)$；
2. $(n,m)=(4,1)$：有 $6$ 种原矩阵；
3. $(n,m)=(2,2)$：有 $12$ 种原矩阵；

总计 $6 + 6 + 12 = 24$ 种。

数据范围

• 对于 $40\%$ 的评测用例，$1 \leq n \times m + 2 \leq 10$；
• 对于所有评测用例，$1 \leq n \times m + 2 \leq 5 \times 10^5$，$1 \leq a_i \leq 5 \times 10^5$。