P3010 [USACO11JAN] Dividing the Gold S

Bessie and Canmuu found a sack of N (1

\* Line 1: A single integer: N \* Lines 2..N+1: Line i+1 contains a single integer: V\_i

\* Line 1: A single integer that is the smallest difference of two partitions. \* Line 2: A single integer that is the number of ways to split the coins with the minimum difference printed in line 1. Since this number can get quite large, print the remainder when divided by 1,000,000.