Su tarea consiste en calcular la cantidad 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 tiene un entero ~n~.

Salida

Imprima el resultado módulo 10^9+7.

Restricciones

• ~1 \leq n \leq 10^6~.

Ejemplo de Entrada

3

Ejemplo de Salida

8