题目描述

小明正在玩一个取数游戏，首先他有 $N$ 个整数，从中任取出 $4$ 个整数 $a$，$b$，$c$，$d$ (每个数只能取一次)，若满足 $a = b \lt c = d$，则称这样的四个数( $a$,$b$,$c$,$d$ )为胜利四元组，可以取得胜利。例如: 共有 4 个数，分别为 1,1,3,3; $a$ 取第 $1$ 个，$b$ 取第 $2$ 个，$c$ 取第 3 个，$d$ 取第 $4$ 个数，那么就可以满足条件。注意，这里 $a$,$b$,$c$,$d$ 四个数是独立取的，因此 $a$ 取第$2$ 个，$b$ 取第 1 个，$c$ 取第 $3$ 个，$d$ 取第 $4$ 个也算作不同的方案。所以这样 $4$ 个数共有 $4$ 种取法小明想要知道，有多少种取数方案，可以取出胜利四元组，方案数可能很多，小明只要知道结果除以 $1000000007$ 的余数即可。

输入格式

第一行一个整数 $N$ ，表示小明共有 $N$ 个整数

第二行 $N$ 个整数，第 $i$ 个数 $a_i$，表示第 $i$ 个整数

输出格式

一个整数，表示满足条件的四元组取法，最终结果对 $1000000007$ 取模。

样例

4
3 1 3 1

4

数据规模

对于 100% 的数据 $1 \le n \le 30000$，$1 \le a_i \le 1000000000$。