Количество битовых строк
По заданному целому числу
n необходимо вычислить число различных битовых строк длины n. Поскольку итоговое значение может быть очень большим, результат следует вывести по модулю (1000000007).Входные данные
Во входных данных содержится единственное целое число
n (1 ≤ n ≤ ).Выходные данные
Необходимо вывести количество битовых строк длины
n по модулю .Примеры
Входные данные | Выходные данные |
3 | 8 |
2 | 4 |
Пояснение
- 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