Tu tarea es calcular el número de cadenas de bits de longitud n.

Por ejemplo, si ~n=3~, la respuesta correcta es 8, porque las cadenas de bits posibles son ~000, 001, 010, 011, 100, 101, 110~ y ~111~.

Entrada

La única línea de entrada contiene un entero n.

Salida

Imprime el resultado módulo ~10^9+7~.

Restricciones

~1 \le n \le 10^6~

Ejemplo

Entrada:

3

Salida:

8