Bessie와 Canmuu는 금화 $N$개 ($1 \leq N \leq 250$)가 든 자루를 찾아 최대한 균등하게 나누려 합니다. 금화 $i$의 가치는 $v_i$ ($1 \leq V_i \leq 2{,}000$)입니다. 두 소는 두 더미의 가치를 같게 하려 하지만 항상 가능하지는 않습니다. 최소 가치 차이는 얼마일까요?

최소 차이를 이루는 분할이 여러 개일 수 있습니다. 가장 공평한 분할의 개수도 알고 싶습니다. 균등하게 나눌 수 없다면 Bessie가 더 큰 가치의 더미를 받습니다.

예를 들어 다섯 금화의 가치가 $2, 1, 8, 4, 16$이면, 한 더미에는 $16$ 하나, 다른 더미에는 나머지가 있어 $1+2+4+8=15$입니다. 차이는 $16-15 = 1$입니다. 이 분할은 유일하므로 최대한 균등한 분할 수는 $1$입니다.

같은 가치의 금화를 더미 사이에서 바꾸면 최적 분할의 수가 늘어납니다. 따라서 $\{1, 1, 1, 1\}$에는 각 더미 두 개씩인 서로 다른 최적 분할 여섯 개가 있습니다.

입력

표준 입력에서 읽습니다.

• 줄 $1$: 정수 하나 $N$.

• 줄 $2..N+1$: 줄 $i+1$에 정수 하나 $V_i$.

출력

표준 출력에 씁니다.

• 줄 $1$: 두 더미 가치의 최소 차이인 정수 하나.

• 줄 $2$: 첫 줄의 최소 차이를 이루는 분할 수인 정수 하나. 매우 클 수 있으므로 $1,000,000$으로 나눈 나머지를 출력합니다.

예제

입력 1

5
2
1
8
4
16

출력 1

1
1

문제 제공: Sherry Wu, 고전 문제, 2010