Penglai Jade Branches Game

In this problem, you are given n Penglai Jade Branches. The i-th branch has a length of \(a_i\). Kaguya will select a subset of these branches (possibly empty or the whole set) to form a "selection scheme." A scheme is considered non-boring if and only if among the selected branches there exists three branches that can form a triangle (i.e. for some three distinct branches with lengths \(x\le y\le z\), we have \(x+y > z\)).

The interestingness of a scheme is defined as follows:

• If the scheme is boring (i.e. no three branches can form a triangle) then its interestingness is 0.
• If the scheme is non-boring and the scheme contains k branches with the maximum branch length among them equal to \(m\), then its interestingness is \(k \times m\).

Your task is to compute the sum of the interestingness of all selection schemes modulo \(20060723\). Note that a selection scheme is obtained by choosing an arbitrary subset of the branches.

Triangle Formation Reminder

It is a well-known fact that given three side lengths \(x \le y \le z\), they can form a (non‐degenerate) triangle if and only if \(x+y>z\).

inputFormat

The first line contains a single integer \(n\) (the number of branches). The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\) representing the lengths of the branches.

It is guaranteed that \(1 \le n \le 2000\) and \(1 \le a_i \le 10^9\).

outputFormat

Output a single integer, the sum of the interestingness over all selection schemes taken modulo \(20060723\).

sample

4
3 4 5 8

71