Anzahl der Bit-Strings
Gegeben ist eine ganze Zahl
n. Es soll bestimmt werden, wie viele verschiedene Bit-Strings der Länge n existieren. Da das Ergebnis sehr groß werden kann, soll die Ausgabe die Anzahl der Bit-Strings modulo (1000000007) liefern.Eingabe
Die Eingabe besteht aus einer einzelnen ganzen Zahl
n (1 ≤ n ≤ ).Ausgabe
Das Programm soll die Anzahl der Bit-Strings der Länge
n modulo ausgeben.Beispiele
Eingabe | Ausgabe |
3 | 8 |
2 | 4 |
Erläuterung
- 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