Bit Strings.
Su tarea consiste en calcular la cantidad de cadenas de bits de longitud .
Por ejemplo, si
, la respuesta correcta es 8, porque las cadenas de bits posibles son
y
.
Entrada
La única línea de entrada tiene un entero .
Salida
Imprima el resultado módulo 10^9+7.
Restricciones
.
Ejemplo de Entrada
3
Ejemplo de Salida
8
Comments