Numero di stringhe di bit
Dato un intero
n, si richiede di calcolare quante stringhe di bit di lunghezza n esistono. Poiché il risultato può essere molto grande, è necessario restituire il numero di stringhe di bit modulo (1000000007).Dati di ingresso
L’input contiene un singolo intero
n (1 ≤ n ≤ ).Dati di uscita
Il programma deve stampare il numero di stringhe di bit di lunghezza
n, calcolato modulo .Esempi
Ingresso | Uscita |
3 | 8 |
2 | 4 |
Spiegazione
- 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