在学校创文知识竞赛中，明明和文文总共获得了n(1≦ n≦250)件奖品，每件奖品都有一个价值V_i (1 ≦ V_i ≦ 2,000)。他们想按价值平均分享这些奖品，假如不能平均分就尽量让它们的差距最小。现在给出奖品数及它们的价值，明明想算出划分后的最小差值，以及划分的方案数。

例如：有5件奖品价值分别是：2, 1,8, 4, 16。明明和文文分为两部分，分别是前面四个为一部分1+2+4+8=15，16为单独一部分，那么两部分相差：16-15 = 1。这个是差距最小的划分方案，并且这种方案的划分方法只有1种。

相同价值的奖品相交换算不同的方案，如：有四件奖品价值分别为{1, 1, 1, 1}，有6种不同的划分方案，使这些奖品分为两部分，每一部分2个奖品。

第一行：一个整数n(1≦n≦250)；

接着有n行，每行一个整数V_i (1 ≦ V_i ≦ 2,000)代表每件奖品的价值。

5

2

1

8

4

16

第一行：一个整数，代表划分的两部分的最小差值。

第二行：一个整数，代表最小差值的划分方案数，结果对1,000,000求余（mod  1,000,000）。

1

1