問題文
高桥先生是Atcoder王国的国王。
Atcoder 王国每年举办一次竞赛,这个王国由一个热爱编程竞赛的人统治。
在本次比赛中 N 将会提出问题。另外,排名的时候 1 有一个要素称为惩罚。 如果您正确回答问题,您将根据比赛开始后的时间对每个问题进行扣分。所产生的罚金总额将作为比赛罚金。请注意,规则与 ARC 处罚不同。
作为一个非常有才华的公民,你有能力解决所有问题。 更重要的是,对于每个问题,他们都知道需要花费多少时间才能解决它,如果他们花同样的时间来解决它,他们总是会解决它。
由于您可以按任何顺序解决问题,因此我决定以最小化比赛惩罚的方式解决它们。
解决所有问题时比赛罚分的最小值是多少?有多少种解决方法? 请给出除以 1,000,000,007(10^9+7) 后的余数。
入力
输入是按以下格式从标准输入给出的。
N T_1 T_2 : T_N
- 1 行包含一个整数,表示竞赛中的问题数。 来自行 N (1 ≦ N ≦ 10,000) 用空格分隔。
- 2 从线 N 行提供了有关解决每个问题所需时间的信息。这几天之一 i (1≦i≦N) 行包含一个整数 如果您对 T_i (1≦T_i≦10,000) 被写入, 解决第i 号问题 表示需要 T_i 分钟。
部分点
这个问题有部分要点。
- 100 点中 50 使值得得分的测试用例的竞赛惩罚最小化的解决方案数量为 1 没错。
出力
按以下格式输出到标准输出。 在
- 1 行中,输出比赛罚分的最小值。请注意,32 位整数类型可能会溢出。
- 2 行表示最小化竞赛惩罚的解决方案的数量。 解决第 1,000,000,007(10^9+7) 后的余数。
入力例1
2 20 10
出力例1
40 1
2 个问题后 最好解决第 1 个问题。
- 比赛开始(时间:0 分)。
- 10 分後、2 题(时间:10 分钟)。此时的处罚是 10 分钟。
- 那 20 分後、1 题(时间: 30 分钟)。此时的处罚是 30 分钟。
比赛罚分是 40(=10+30) 分钟。
入力例2
5 2 1 2 1 2
出力例2
21 12
入力例3
13 1 1 1 1 1 1 1 1 1 1 1 1 1
出力例3
91 227020758
您可以按任何顺序解决它们。别忘了把剩下的带走。 坐标平面上的