Bessie y Canmuu encontraron un saco de $N$ monedas de oro ($1 \leq N \leq 250$) y desean repartirlas lo más equitativamente posible. La moneda $i$ vale $v_i$ ($1 \leq V_i \leq 2{,}000$). Las vacas quieren dos montones iguales, pero no siempre es posible. ¿Cuál es la menor diferencia de valor?

Puede haber varias formas de lograr la diferencia mínima. También quieren contar los repartos más justos. Si no pueden dividir por igual, Bessie recibe el montón de mayor valor.

Por ejemplo, cinco monedas valen $2, 1, 8, 4, 16$. Un montón contiene la de $16$ y el otro las restantes por $1+2+4+8=15$. La diferencia es $16-15 = 1$. Es la única forma de este reparto, por lo que el número de formas más justas es $1$.

Intercambiar monedas de igual valor entre montones aumenta el número de repartos óptimos. Así, $\{1, 1, 1, 1\}$ tiene seis repartos óptimos distintos, cada montón con dos monedas.

Entrada

Lee de la entrada estándar.

• Línea $1$: un entero $N$.

• Líneas $2..N+1$: la línea $i+1$ contiene un entero $V_i$.

Salida

Escribe en la salida estándar.

• Línea $1$: un entero, la menor diferencia entre valores de montones.

• Línea $2$: número de repartos con la diferencia mínima de la primera línea. Puede ser grande; imprime el resto al dividir por $1,000,000$.

Ejemplos

Entrada 1

5
2
1
8
4
16

Salida 1

1
1

Créditos: Sherry Wu, un clásico, 2010