Número de bit-strings
Dado um inteiro
n, é necessário calcular quantas bit-strings (sequências de bits) distintas têm comprimento n. Como o resultado pode ser demasiado grande, o programa deve apresentar o número de bit-strings calculado ao abrigo do módulo (1000000007).Entrada
A entrada consiste num único inteiro
n (1 ≤ n ≤ ).Saída
O programa deve imprimir o número de bit-strings de comprimento
n, considerando o módulo .Exemplos
Entrada | Saída |
3 | 8 |
2 | 4 |
Explicação
- 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