Bessie 和 Canmuu 找到了一袋 $N$（$1 \leq N \leq 250$）枚金币，希望尽可能均分。第 $i$ 枚价值为 $v_i$（$1 \leq V_i \leq 2{,}000$）。奶牛想尽量平均分成两堆，但未必能做到。两堆价值之差最小是多少？

此外，达到最小差值的分法可能不止一种。她们也想知道尽可能公平地分金币的方案数。如果不能均分，Bessie 会得到价值较高的一堆。

例如，五枚金币价值为 $2, 1, 8, 4, 16$。一堆是价值 $16$ 的一枚，另一堆是其余金币，价值 $1+2+4+8=15$。差值为 $16-15 = 1$。这是唯一能这样分配的方案，因此尽量平均分配的方案数为 $1$。

注意，可以在两堆之间交换同值金币，增加最优分配的方案数。因此，金币集合 $\{1, 1, 1, 1\}$ 有六种不同的最优分法，每堆两枚。

输入格式

从标准输入读取。

• 第 $1$ 行：一个整数 $N$。

• 第 $2..N+1$ 行：第 $i+1$ 行包含一个整数 $V_i$。

输出格式

写入标准输出。

• 第 $1$ 行：一个整数，表示两堆价值差的最小值。

• 第 $2$ 行：一个整数，表示达到第一行最小差值的方案数。因为可能很大，输出对 $1,000,000$ 取模的余数。

样例

输入格式 1

5
2
1
8
4
16

输出格式 1

1
1

题目作者：Sherry Wu，经典题，2010