AT_arc035_b.[ARC035B] アットコーダー王国のコンテスト事情

高桥君是 AtCoder 王国的国王。

在他统治的 AtCoder 王国，每年都会举办一次编程竞赛。

在这场竞赛中，会有 $N$ 道题目被出题。此外，排名时有一个要素叫做“罚时”。当你解出某道题时，会根据从比赛开始到解出该题所用的时间，按每题分别计算罚时。所有题目的罚时之和就是本次比赛的总罚时。请注意，这里的罚时规则与 ARC 的罚时不同。

你是一位非常优秀的国民，有能力解出所有题目。而且，你知道每道题需要多少时间才能解出，只要花费恰好这些时间就一定能解出。

你可以以任意顺序解题，请你思考如何解题才能使总罚时最小。

请输出解出所有题目时总罚时的最小值，以及能够达到该最小罚时的解题顺序有多少种。答案对 $1,000,000,007\ (10^9+7)$ 取模。

输入通过标准输入给出。

$N$
$T_1$
$T_2$
$\vdots$
$T_N$

• 第 $1$ 行是一个整数 $N\ (1\leq N\leq 10,000)$，表示题目数。
• 接下来的 $N$ 行，每行一个整数 $T_i\ (1\leq T_i\leq 10,000)$，表示解第 $i$ 道题所需的时间。

请按以下格式输出到标准输出。

• 第 $1$ 行输出总罚时的最小值。注意，32 位整数类型可能会溢出。
• 第 $2$ 行输出能达到最小罚时的解题顺序数，对 $1,000,000,007\ (10^9+7)$ 取模。

部分分

本题存在部分分。

• 在 $100$ 分中的 $50$ 分测试点中，能达到最小罚时的解题顺序只有 $1$ 种。

样例解释 1

先解第 $2$ 道题再解第 $1$ 道题是最优的。

• 比赛开始（时刻：$0$ 分）。
• $10$ 分钟后，解出第 $2$ 道题（时刻：$10$ 分），此时罚时为 $10$ 分。
• 再过 $20$ 分钟，解出第 $1$ 道题（时刻：$30$ 分），此时罚时为 $30$ 分。
• 总罚时为 $40(=10+30)$ 分。

样例解释 3

无论以什么顺序解题都可以。不要忘记取模。

由 ChatGPT 4.1 翻译