금화 나누기

베시와 칸무는 금화 $N$개가 들어 있는 자루를 발견하고, 이 금화들을 최대한 공평하게 두 더미로 나누려고 합니다. $i$번째 금화의 가치는 $v_i$입니다. 두 더미의 가치를 정확히 똑같이 맞추는 것이 항상 가능하지는 않으므로, 두 더미의 가치 차이를 가능한 한 작게 만들려고 합니다. 그 최소 차이는 얼마입니까?

또한 그 최소 차이를 만드는 방법이 여러 가지일 수도 있습니다. 베시와 칸무는 가장 공평하게 나누는 방법의 수도 알고 싶어 합니다. 두 더미를 정확히 똑같이 나눌 수 없다면 베시가 가치가 더 큰 더미를 가집니다.

예를 들어 가치가 각각 $2, 1, 8, 4, 16$인 금화 5개가 있다고 합시다. 가치 $16$인 금화 하나를 한 더미에 넣고 나머지를 다른 더미에 넣으면, 다른 더미의 가치는 $1 + 2 + 4 + 8 = 15$이므로 두 더미의 차이는 $16 - 15 = 1$입니다. 이 차이를 만드는 방법은 이 한 가지뿐이므로 가장 공평하게 나누는 방법의 수는 $1$입니다.

가치가 같은 금화들은 두 더미 사이에서 서로 자리를 바꾸어도 여전히 최적의 분할이 되므로 방법의 수가 늘어날 수 있습니다. 예를 들어 가치가 모두 $1$인 금화 4개 $\{1, 1, 1, 1\}$을 각각 2개씩 두 더미로 나누는 최적 분할은 $6$가지입니다.

방법의 수를 셀 때는, 전체 가치의 절반을 넘지 않으면서 그 절반에 가장 가까운 값을 이루는 더 가벼운 더미를 구성하는 금화들의 조합(부분집합)의 개수를 셉니다. 이때 가치가 같은 금화라도 서로 다른 금화로 구분합니다.

제약: $1 \le N \le 250$, $1 \le v_i \le 2000$.

• 첫째 줄: 정수 $N$.
• 둘째 줄부터 $N+1$번째 줄까지: $i+1$번째 줄에 $i$번째 금화의 가치 $v_i$가 하나씩 주어집니다.

• 첫째 줄: 두 더미로 나눌 수 있는 최소 가치 차이를 나타내는 정수.
• 둘째 줄: 그 최소 차이를 만드는 분할 방법의 수. 이 값이 매우 커질 수 있으므로 $1{,}000{,}000$으로 나눈 나머지를 출력합니다.