← 返回题目列表

AtCoder · arc035_b

B. Atcoder王国大赛情况

中文机器翻译题面 查看原题

問題文

高桥先生是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

您可以按任何顺序解决它们。别忘了把剩下的带走。 坐标平面上的