Dividing the Gold

Bessie and Canmuu found a sack of $N$ gold coins that they want to divide as evenly as possible. Coin $i$ has value $v_i$. Splitting the coins into two piles of exactly equal value is not always possible, so they want to make the difference between the two piles as small as they can. What is that smallest difference?

There may also be several ways to achieve that smallest difference. Bessie and Canmuu also want to know the number of ways to split the coins as fairly as possible. If the two piles cannot be made exactly equal, Bessie takes the more valuable pile.

For example, suppose there are five coins of values $2, 1, 8, 4, 16$. Put the coin of value $16$ in one pile and the rest in the other pile; the other pile is worth $1 + 2 + 4 + 8 = 15$, so the difference is $16 - 15 = 1$. This is the only way to reach that difference, so the number of fairest splits is $1$.

Coins of equal value can be swapped between the piles and still give an optimal split, which can increase the number of ways. For instance, four coins that are all worth $1$, i.e. ${1, 1, 1, 1}$, can be split into two piles of two coins each in $6$ different ways.

To count the ways, count the number of coin subsets that form the lighter pile — the subset whose total does not exceed half of the overall value and is as close to that half as possible. Coins of equal value are still treated as distinct coins.

Constraints: $1 \le N \le 250$ and $1 \le v_i \le 2000$.

• Line 1: a single integer $N$.
• Lines 2 through $N+1$: line $i+1$ contains a single integer $v_i$, the value of coin $i$.

• Line 1: a single integer, the smallest possible difference between the two piles.
• Line 2: a single integer, the number of ways to split the coins achieving that minimum difference. Because this number can be very large, print it modulo $1{,}000{,}000$.