Background

Kaguya's game console ran out of battery.

Problem Description

Since the game console is charging on Youkai Mountain, Kaguya started playing with the Penglai Jade Branches.

More specifically, there are $n$ Penglai Jade Branches in front of Kaguya, and the length of the $i$-th branch is $a_i$.

Kaguya will choose some of these $n$ branches; this is called a selection plan. A plan is considered "not boring" by Kaguya if and only if among the chosen branches, there exist three branches that can form a triangle.

When a plan is considered "boring", Kaguya thinks its fun value is $0$. When a plan is considered "not boring", if the number of chosen branches is $k$ and the maximum length among the chosen branches is $m$, then the fun value of this plan is $km$.

Now, Kaguya wants to know the sum of fun values over all selection plans. However, Kaguya has too many branches, so she asked you, the smart one, to help compute the answer. In return, you can get an invitation to the Lunar Capital Expo.

Kaguya thinks a huge number is also very boring, so you only need to output the result modulo $20060723$.

Input Format

The input consists of two lines.

The first line contains an integer $n$, representing the number of branches.

The second line contains $n$ integers, where the $i$-th integer $a_i$ represents the length of the $i$-th branch.

Output Format

Output one integer in one line, representing the sum of fun values modulo $20060723$.

4
7 4 8 11

134

Hint

Sample Explanation

The "not boring" plans are:

$\left\{4, 7, 8\right\}$, $\left\{4, 8, 11\right\}$, $\left\{7, 8, 11\right\}$, and $\left\{4, 7, 8, 11\right\}$.

Therefore, the answer is $\left(8 \times 3 + 11 \times 3 + 11 \times 3 + 11 \times 4\right) \bmod 20060723 = 134$.

Constraints and Notes

This problem uses bundled testdata: a subtask is passed if and only if all test points in that subtask are passed.

For $100\%$ of the data, $0 < n \le 5000$, and $0 < a_i \le 10^9$.

Translated by ChatGPT 5