Bessie e Canmuu encontraram um saco de $N$ moedas de ouro ($1 \leq N \leq 250$) e querem dividir o mais igualmente possível. A moeda $i$ vale $v_i$ ($1 \leq V_i \leq 2{,}000$). As vacas querem duas pilhas iguais, mas nem sempre é possível. Qual a menor diferença entre seus valores?

Pode haver vários modos de atingir a diferença mínima. Elas também querem contar as divisões mais justas. Se não for possível igualdade, Bessie recebe a pilha de maior valor.

Por exemplo, cinco moedas valem $2, 1, 8, 4, 16$. Uma pilha tem a de $16$, a outra as restantes por $1+2+4+8=15$. A diferença é $16-15 = 1$. Essa divisão é única, então há $1$ modo de dividir tão igualmente.

Trocar moedas de igual valor entre pilhas aumenta o número de divisões ótimas. Assim, $\{1, 1, 1, 1\}$ tem seis divisões ótimas distintas, com duas moedas por pilha.

Entrada

Leia da entrada padrão.

• Linha $1$: um inteiro $N$.

• Linhas $2..N+1$: a linha $i+1$ contém um inteiro $V_i$.

Saída

Escreva na saída padrão.

• Linha $1$: um inteiro, a menor diferença dos valores das pilhas.

• Linha $2$: número de divisões com a diferença mínima da primeira linha. Pode ser grande; imprima o resto da divisão por $1,000,000$.

Exemplos

Entrada 1

5
2
1
8
4
16

Saída 1

1
1

Créditos: Sherry Wu, um clássico, 2010