Bessie und Canmuu fanden einen Sack mit $N$ Goldmünzen ($1 \leq N \leq 250$), die sie möglichst gleichmäßig aufteilen möchten. Münze $i$ hat Wert $v_i$ ($1 \leq V_i \leq 2{,}000$). Die Kühe wollen zwei gleichwertige Haufen, doch das geht nicht immer. Was ist der kleinste Wertunterschied?

Mehrere Aufteilungen können diesen minimalen Unterschied erreichen. Sie möchten auch deren Anzahl kennen. Ist eine gleichwertige Aufteilung unmöglich, bekommt Bessie den wertvolleren Haufen.

Beispielsweise gibt es fünf Münzen mit Werten $2, 1, 8, 4, 16$. Ein Haufen enthält die Münze $16$, der andere den Rest mit $1+2+4+8=15$. Der Unterschied ist $16-15 = 1$. Diese Aufteilung ist eindeutig, also gibt es $1$ möglichst gleichmäßige Aufteilung.

Gleichwertige Münzen können zwischen Haufen getauscht werden, was mehr optimale Aufteilungen ergibt. So hat $\{1, 1, 1, 1\}$ sechs verschiedene optimale Aufteilungen mit je zwei Münzen.

Eingabe

Lies von der Standardeingabe.

• Zeile $1$: eine ganze Zahl $N$.

• Zeilen $2..N+1$: Zeile $i+1$ enthält eine ganze Zahl $V_i$.

Ausgabe

Schreibe auf die Standardausgabe.

• Zeile $1$: eine ganze Zahl, der kleinste Wertunterschied der Haufen.

• Zeile $2$: die Anzahl Aufteilungen mit dem minimalen Unterschied aus Zeile eins. Diese kann groß sein; gib den Rest bei Division durch $1,000,000$ aus.

Beispiele

Eingabe 1

5
2
1
8
4
16

Ausgabe 1

1
1

Angaben zur Aufgabe: Sherry Wu, ein Klassiker, 2010