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