题目描述

公子光设宴邀请吴王僚，吴王僚心存疑虑但仍前来赴宴。公子光早已布置武士埋伏在四周，并让专诸将短剑藏于烤鱼之中，准备在宴席上发动刺杀。

为了评估动手的最佳时机，公子光记录了宴会上每道菜的美味度，形成一个长度为 $n$ 的整数序列 $a_1, a_2, \dots, a_n$。

现在，他想知道有多少个四元组 $(q, w, e, r)$ 满足：

且

这种模式表示在两道美味度相同且较高的菜品出现时，吴王僚的注意力被吸引，是动手的良机。

请输出满足条件的四元组数量对 $10007$ 取模的结果。

输入格式

第一行一个整数 $n$（$1 \le n \le 3000$）。

第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$），整数之间用一个空格隔开。

输出格式

输出一行一个整数，表示答案。

4
1 3 3 2

1