Cantidad de cadenas de bits
Dado un entero
n, se solicita calcular el número de diferentes cadenas de bits de longitud n. Como este valor puede ser muy grande, la salida debe mostrar el resultado de ese conteo tomado módulo (1000000007).Entrada
La entrada contiene un único entero
n (1 ≤ n ≤ ).Salida
El programa debe imprimir la cantidad de cadenas de bits de longitud
n módulo .Ejemplos
Input | Output |
3 | 8 |
2 | 4 |
Explicación
- 3: 000, 001, 010, 011, 100, 101, 110, 111
- 2: 00, 01, 10, 11
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB