Bessie et Canmuu ont trouvé un sac de $N$ pièces d'or ($1 \leq N \leq 250$), à partager aussi équitablement que possible. La pièce $i$ vaut $v_i$ ($1 \leq V_i \leq 2{,}000$). Les vaches veulent deux tas de même valeur, mais ce n'est pas toujours possible. Quelle est leur différence minimale ?

Plusieurs partages peuvent atteindre cette différence minimale. Elles veulent aussi compter les partages les plus équitables. Si les valeurs ne peuvent être égales, Bessie reçoit le tas de plus grande valeur.

Par exemple, cinq pièces valent $2, 1, 8, 4, 16$. Un tas contient la pièce de $16$, l'autre les restantes de valeur $1+2+4+8=15$. La différence est $16-15 = 1$. Ce partage est unique, donc le nombre de partages aussi équitables est $1$.

Échanger des pièces de même valeur entre les tas augmente le nombre de partages optimaux. Ainsi, $\{1, 1, 1, 1\}$ a six partages optimaux distincts, avec deux pièces par tas.

Entrée

Lisez l'entrée standard.

• Ligne $1$ : un entier $N$.

• Lignes $2..N+1$ : la ligne $i+1$ contient un entier $V_i$.

Sortie

Écrivez sur la sortie standard.

• Ligne $1$ : un entier, la différence minimale des valeurs des tas.

• Ligne $2$ : le nombre de partages ayant la différence minimale de la première ligne. Ce nombre peut être grand ; affichez son reste modulo $1,000,000$.

Exemples

Entrée 1

5
2
1
8
4
16

Sortie 1

1
1

Crédits : Sherry Wu, un classique, 2010