如果一个数字数组满足以下条件，则称其为 W-shaped：

1. 它由四个段组成，顺序分别为递减、递增、递减、递增。
2. 排序是非严格的，因此递增和递减段可以包含连续相等的元素。
3. 每两个相邻的段都有一个公共端点。
4. 每个段都包含至少两个不同的值。

例如，数组 $(3, 1, 2, 1, 1, 4)$ 是 W-shaped 的，因为它由段 $(3, 1)$、$(1, 2)$、$(2, 1, 1)$、$(1, 4)$ 组成。数组 $(3, 1, 2, 2, 2, 4)$ 不是 W-shaped 的。它可以被拆分为段 $(3, 1)$、$(1, 2)$、$(2, 2, 2)$、$(2, 4)$，然而段 $(2, 2, 2)$ 不包含两个不同的值。

给定一个包含 $N$ 个整数的数组，该数组有多少种不同的 W-shaped 排列？如果存在一个位置 $1 \le i \le N$ 使得 $p_i \neq q_i$，则数组的两个排列 $(p_1, p_2, \dots, p_N)$ 和 $(q_1, q_2, \dots, q_N)$ 被认为是不同的。在上面的例子中，$(3, 1, 2, 1, 1, 4)$ 应该只被计算一次，因为对三个 $1$ 进行置换不会产生不同的排列。

输入格式

第一行包含 $N$。第二行包含数组的 $N$ 个值，以空格分隔。

输出格式

输出一个数字：不同的 W-shaped 排列的数量，对 $1,000,000,007$ 取模。

数据范围

• $5 \le N \le 300,000$
• 数组中的值是 $1$ 到 $1,000,000$ 之间的整数（包含边界）。

子任务

测试用例将单独评分。

样例

输入 1

5
3 1 4 2 3

输出 1

6

说明 1

六种不同的 W-shaped 排列为： $3, 1, 3, 2, 4$ $3, 1, 4, 2, 3$ $3, 2, 3, 1, 4$ $3, 2, 4, 1, 3$ $4, 1, 3, 2, 3$ $4, 2, 3, 1, 3$

输入 2

7
1 2 2 2 3 4 4

输出 2

72