题目描述

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

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

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

输入格式

第一行：一个整数 $n$（$1 le n le 250$）；

接着有 $n$ 行，每行一个整数 $V_i$（$1 le V_i le 2000$）代表奖品的价值。

输出格式

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

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

样例

5
2
1
8
4
16

1
1

数据范围

• $1 le n le 250$
• $1 le V_i le 2000$