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