Inicialmente se tiene un conjunto ~S~, con los elementos ~{1, 2, 3, ..., n}~.

Mientras el conjunto tenga al menos dos elementos, se realizará una de las siguientes dos operaciones con probabilidad ~\frac{1}{2}~ cada una:

• Se elimina el mayor elemento de S.

• Se elimina el menor elemento de S.

Diga para cada elemento de ~S~, cual es la probabilidad de que él sea el elemento que quede en el conjunto al final de todas las operaciones.

Se puede notar que esta probabilidad se puede expresar de la forma ~\frac{P}{Q}~, donde ~P~ y ~Q~ son coprimos, y ~Q \not\equiv 0~ ~(\mod 10^9+7)~, imprima ~P \cdot Q^{-1}~ módulo ~10^9+7~, ~(1000000007)~.

Recuerde que ~Q^{-1} (\mod m) \equiv Q^{m-2} (\mod m)~, si ~Q~ y ~m~ son coprimos.

Subtareas

Subtarea 1: ~2 \leq n \leq 16~ (25 puntos)

Subtarea 2: ~2 \leq n \leq 1000~ (35 puntos)

Subtarea 3: ~2 \leq n \leq 10^5~ (40 puntos)

Entrada

n

Salida

P_1 P_2 P_3 ... P_n

P_i es la probabilidad de que el elemento que quede en el conjunto sea ~i~.

Ejemplo de entrada

3

Ejemplo de salida

250000002 500000004 250000002

Las probabilidades son ~\frac{1}{4}~, ~\frac{1}{2}~, ~\frac{1}{4}~.