Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

Fito se come la mitad de un caramelo cada día. El comienza con un paquete de exactamente $N$ caramelos. El primer día, escoge un caramelo aleatorio, lo pica en dos partes, toma una mitad y pone la otra de vuelta en el paquete. En los subsecuentes días, escoge un caramelo aleatorio (que puede ser un caramelo entero o una mitad) del paquete. Si escoge una mitad, entonces se lo come, si es uno entero, entonces se come una mitad y pone la otra en el paquete. ¿De cuántas formas puede Fito comerse todos los caramelos? Representando la secuencia de caramelos que tomó del paquete en el curso de los siguientes $2N$ días como cadenas, donde el $i$-ésimo símbolo será $W$ si tomó un caramelo completo, y $H$ si tomó la mitad de uno $(1 \leq i \leq 2N)$. ¿Cuántas cadenas válidas diferentes existen que dejen el paquete vacío?

Input

La entrada contendrá casos de pruebas para a lo sumo $1000$ instancias del problema. Para cada instancia habrá una línea con un entero positivo $N \leq 1000$, el número de caramelos en el paquete. El fin de la entrada será indicado con $0$.

Output

Por cada instancia del problema, la salida contendrá un simple entero, el número de formas diferentes de vaciar el paquete. Imprima la salida módulo $987654321$.

Sample test(s)