Problem Description

Lord Takahashi is the king of AtCoder Kingdom.

In the AtCoder Kingdom, which he rules over and where people love programming contests, a contest is held once a year.

This contest features $ N $ problems. There is also a concept of penalty, which is one of the factors in determining the rankings. When a problem is solved correctly, a penalty equal to the time elapsed from the start of the contest is incurred for each problem. The sum of these penalties is the contest penalty. Note that this rule differs from the penalty rule in ARC.

As a highly skilled citizen, you have the ability to solve all the problems. Moreover, you know exactly how much time is needed to solve each problem, and if you spend exactly that amount of time on a problem, you can solve it correctly.

You can solve the problems in any order you like, so you want to minimize the contest penalty.

Find the minimum possible contest penalty when solving all the problems and the number of ways to achieve this minimum penalty, modulo $ 1,000,000,007(10^9+7) $.

Input Format

The input is given from the standard input in the following format:

$ N $ $ T_1 $ $ T_2 $ : $ T_N $

• The first line contains an integer $N\ (1\ ≦\ N\ ≦\ 10,000)$, representing the number of problems in the contest.
• The next $ N $ lines contain the information about the time required to solve each problem. The $i\ (1≦i≦N)$ -th line contains an integer $T_i\ (1≦T_i≦10,000)$, indicating that it takes $ T_i $ minutes to solve the $ i $ -th problem.

Output Format

Output the results to the standard output in the following format:

• The first line should contain the minimum contest penalty. Be aware that the 32-bit integer type may overflow.
• The second line should contain the number of ways to achieve the minimum contest penalty, modulo $ 1,000,000,007(10^9+7) $.

Sample Input and Output

Sample Input #1

2
20
10

Sample Output #1

40
1

Sample Input #2

5
2
1
2
1
2

Sample Output #2

21
12

Sample Input #3

13
1
1
1
1
1
1
1
1
1
1
1
1
1

Sample Output #3

91
227020758

Notes/Hints

Partial Points

This problem has partial points.

• For $ 50 $ out of $ 100 $ points, there is only one way to achieve the minimum contest penalty.

Sample Explanation 1

It is better to solve the second problem first and then the first problem. - The contest starts (time: $ 0 $ minutes). - After $ 10 $ minutes, the second problem is solved correctly (time: $ 10 $ minutes). The penalty at this point is $ 10 $ minutes. - After another $ 20 $ minutes, the first problem is solved correctly (time: $ 30 $ minutes). The penalty at this point is $ 30 $ minutes. The total contest penalty is $ 40(=10+30) $ minutes.

Sample Explanation 3

Any order of solving the problems is acceptable. Do not forget to take the modulo.

见题面 Input 部分

见题面 Output 部分