Сложность: 24%
Уровень ЧСВ (Чувства собственной важности) у Руслана зашкаливает. Если выразить ЧСВ среднестатического обывателя числом , то ЧСВ Руслана – это выражение вида .
Например, если ЧСВ обывателя равно , то ЧСВ Руслана равно , а если ЧСВ обывателя , то у Руслана . Обратите внимание, что ЧСВ Руслана обладает правой ассоциативностью, то есть вычисляется сверху вниз: .
Вычислите уровень ЧСВ Руслана, зная уровень ЧСВ среднестатистического обывателя. Так как ответ может быть достаточно большим (например, ЧСВ уровня содержит более цифр), выведите его по модулю .
Входные данные
В единственной строке записано число () - уровень ЧСВ среднестатистического обывателя.
Выходные данные
Выведите одно число - значение ЧСВ Руслана. Ответ нужно вывести по модулю .
Подзадачи
№ | баллы | необх. подзадачи | ограничения |
1 | 60 | - | |
2 | 40 | 1 | Нет дополнительных ограничений |
STDIN | STDOUT |
2 | 4 |
3 | 587290362 |