Nombre de chaînes de bits
Étant donné un entier
n, vous devez calculer combien de chaînes de bits différentes peuvent exister de longueur n. Comme le résultat peut être extrêmement grand, on vous demande d’afficher ce nombre modulo (1000000007).Entrée
L’entrée contient un unique entier
n (1 ≤ n ≤ ).Sortie
Le programme doit afficher le nombre de chaînes de bits de longueur
n modulo .Exemples
Entrée | Sortie |
3 | 8 |
2 | 4 |
Explication
- 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