【问题描述】
有n枚金币（1 <= n <= 250），金币有价值（可能相同）。现在希望平均分配这n枚金币成2堆。求2堆金币的最小差值。一枚金币不能进行分割。
例如5枚金币，价值分别为1,2,4,8,16。可以如下分配：1,2,4,8分为一堆，16分为一堆。最小差值为16-15=1。
注意特例：价值相等的金币为不同的金币。假设如果有4枚金币，价值为1,1,1,1。那么分配方法有6种。
【输入格式】
第1行：一个整数n。
第2到n+1行：一个整数，表示第i个金币的价值（<=1000）。
【输出格式】
第1行：一个整数表示分配时候，2堆金币的最小差值。
第2行：达到这个最小差值的分配方法的数量。由于这个数字可能比较大，输出除以1000000的余数。
【输入样例1】
5
2
1
8
4
16
【输出样例1】
1
1
【输出样例2】
4
1
1
1
1
【样例解释2】
0
6
【数据范围与约定】
40%的数据：n <= 20。
100%的数据：n <= 250。数据有梯度。