「Wdoi-1」蓬莱玉枝
题目背景
辉夜的游戏机没电了。
题目描述
由于游戏机在妖怪之山充电,辉夜玩起了蓬莱玉枝。
具体来说,辉夜面前有 $n$ 条蓬莱玉枝,第 $i$ 条蓬莱玉枝的长度为 $a_i$ 。
辉夜会从这 $n$ 条玉枝中选出若干条来,称作一次选择方案。一个方案被辉夜认为是"不无聊的",当且仅当在选出的玉枝中,存在某三条玉枝能够 **构成一个三角形**。
当一个方案被认为是"无聊的"时,辉夜认为它的有趣程度为 $0$;当一个方案被辉夜认为是"不无聊的"时,若选出的玉枝数量为 $k$,选出的玉枝中最长的玉枝长度为 $m$ ,则这个方案的有趣程度为 $km$ 。
现在,辉夜想要知道,所有选择方案的有趣程度之和是多少。然而,辉夜的玉枝太多了,所以她找到了聪明的你来帮她算出答案,作为回报,你可以得到参加月都万象展的邀请。
辉夜认为一个巨大的数字也是很无趣的,因此你只需要输出答案对 $20060723$ 取模后的结果即可。
输入输出格式
输入格式
输入数据共包括两行。
第一行,一个整数 $n$,表示玉枝的数量。
第二行,$n$ 个整数,第 $i$ 个整数 $a_i$ 表示第 $i$ 条玉枝的长度。
输出格式
一行一个整数,表示有趣程度之和对 $20060723$ 取模后的结果。
输入输出样例
输入样例 #1
4
7 4 8 11
输出样例 #1
134
说明
#### 样例说明
"不无聊的"方案有:
$\left\{4, 7, 8\right\}$,$\left\{4, 8, 11\right\}$,$\left\{7, 8, 11\right\}$ 和 $\left\{4, 7, 8, 11\right\}$。
故答案为 $\left(8 \times 3 + 11 \times 3 + 11 \times 3 + 11 \times 4\right) \bmod 20060723 = 134$。
#### 数据范围与约定
**本题采用捆绑测试:一个子任务通过,当且仅当该子任务中全部测试点通过。**
| 子任务编号 | $n$ | 时限 | 空限 | 分值 |
| :--------: | :-: | :--: | :--: | :--: |
| $1$ | $20$ | $1\operatorname s$ | $500\operatorname{MB}$ | $15$ |
| $2$ | $100$ | $1\operatorname s$ | $500\operatorname{MB}$ | $20$ |
| $3$ | $200$ | $0.5\operatorname s$ | $500\operatorname{MB}$ | $10$ |
| $4$ | $1000$ | $1\operatorname s$ | $500\operatorname{MB}$ | $15$ |
| $5$ | $1500$ | $1\operatorname s$ | $500\operatorname{MB}$ | $15$ |
| $6$ | $2000$ | $5\operatorname s$ | $256\operatorname{MB}$ | $10$ |
| $7$ | $5000$ | $2\operatorname s$ | $500\operatorname{MB}$ | $15$ |
对于 $100\%$ 的数据,$0 < n \le 5000$,$0 < a_i \le 10^9$。