题目描述

在学校创文知识竞赛中，乐乐和小明总共获得了n(1 <= n<= 250)件奖品，每件奖品都有一 

个价值Vi (1 <= Vi <= 2000)。他们想平均分这些奖品，假如不能平均分就尽量让它们的差 

距最小。现在给出奖品数及它们的价值，乐乐想算出划分后的最小差值，以及划分的方案 

数。 

例如：有5件奖品价值分别是：2

18 4 16。乐乐和小明分为两部分，分别是前面四个为一

部分1+2+4+8=15，16为单独一部分，那么两部分相差：16-15 = 1。这个是差距最小的 

划分方案，并且这种方案的划分方法只有1种。 

相同价值的奖品相交换算不同的方案，如：有四件奖品价值分别为{1 1 1 1}，有6种不同的 

划分方案，使这些奖品分为两部分，每一部分2个奖品。 

输入格式

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

接着有n行，每行一个整数Vi (1

<= Vi <= 2000)代表奖品的价值。

输出格式

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

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

样例

输入

5
2
1
8
4
16

输出

1
1