Bessie i Canmuu znalazły worek $N$ złotych monet ($1 \leq N \leq 250$), które chcą podzielić jak najrówniej. Moneta $i$ ma wartość $v_i$ ($1 \leq V_i \leq 2{,}000$). Krowy chcą równych wartości dwóch stosów, lecz nie zawsze jest to możliwe. Jaka jest najmniejsza różnica?

Minimalną różnicę może osiągać kilka podziałów. Chcą też poznać liczbę najbardziej sprawiedliwych podziałów. Jeśli równość jest niemożliwa, Bessie dostaje stos o większej wartości.

Na przykład pięć monet ma wartości $2, 1, 8, 4, 16$. Jeden stos zawiera monetę $16$, drugi pozostałe o wartości $1+2+4+8=15$. Różnica to $16-15 = 1$. Taki podział jest jedyny, więc liczba najrówniejszych podziałów wynosi $1$.

Monety o tej samej wartości można zamieniać między stosami, zwiększając liczbę optymalnych podziałów. Zatem $\{1, 1, 1, 1\}$ ma sześć różnych optymalnych podziałów po dwie monety w stosie.

Wejście

Czytaj ze standardowego wejścia.

• Wiersz $1$: jedna liczba całkowita $N$.

• Wiersze $2..N+1$: wiersz $i+1$ zawiera jedną liczbę całkowitą $V_i$.

Wyjście

Pisz na standardowe wyjście.

• Wiersz $1$: liczba całkowita, najmniejsza różnica wartości stosów.

• Wiersz $2$: liczba podziałów z minimalną różnicą z pierwszego wiersza. Może być duża; wypisz resztę z dzielenia przez $1,000,000$.

Przykład

Wejście 1

5
2
1
8
4
16

Wyjście 1

1
1

Autorstwo: Sherry Wu, klasyczne zadanie, 2010