Задача #0251
Фрактал
Вова интересуется фигурами в виде фрактала. Он придумал новую такую фигуру, и начал заполнять так:
- На первом шаге он нарисовал круг с радиусом \(R\).
- На втором шаге вокруг круга из первого шага нарисовал 3 квадрата.
- На третьем шаге он нарисовал круги по углам квадрата из второго шага.
- …
- На шаге \(2*k\) он нарисовал 3 квадрата вокруг круга из шага \(2*k-1\).
- На шаге \(2*k+1\) он нарисовал 4 круга по углам квадрата из шага \(2*k\).
- …
|
1-шаг |
2-шаг |
3-шаг |
|
|
|
|
Он осознал что ему трудно будет дорисовать все фигуры до \(n\)-го шага, но также понял что можно узнать количество фигур (круг и квадрат) в \(n\)-ом шаге. Надо найти количество фигур в \(n\)-ом шаге.
Входные данные:
Во входном файле дается одно целое число \(N (1 ≤ N ≤ 10^{18})\).
Выходные данные:
Во выходном файле надо вывести остаток от деления количества фигур в \(n\)-ом шаге на \(1000000007(10^9+7)\)!
Примеры
| # | input.txt | output.txt |
|---|---|---|
| 1 |
1 |
1 |
| 2 |
2 |
4 |
| 3 |
3 |
16 |
Отправить решение
Пожалуйста, войдите в систему,
чтобы выполнить это действие,если у вас нет учетной записи,
вы можете зарегистрироваться
в любое время
канал в Telegram, чтобы получать последние новости