Уровень ЧСВ (Чувства собственной важности) у Руслана зашкаливает. Если выразить ЧСВ среднестатического обывателя числом $n$, то ЧСВ Руслана – это выражение вида $\underbrace{n^{n^{...^n}}}_{n}$.

Например, если ЧСВ обывателя равно $4$, то ЧСВ Руслана равно $4^{4^{4^4}}$, а если ЧСВ обывателя $= 3$, то у Руслана $3^{3^3}$. Обратите внимание, что ЧСВ Руслана обладает правой ассоциативностью, то есть вычисляется сверху вниз: $4^{4^{4^4}} = 4^{(4^{(4^4)})}$.

Вычислите уровень ЧСВ Руслана, зная уровень ЧСВ среднестатистического обывателя. Так как ответ может быть достаточно большим (например, ЧСВ уровня $4^{4^{4^4}}$ содержит более $10^{153}$ цифр), выведите его по модулю $10^9 + 1337$.

Входные данные

В единственной строке записано число $n$ ($1 \le n \le 10 \ 000$) - уровень ЧСВ среднестатистического обывателя.

Выходные данные

Выведите одно число - значение ЧСВ Руслана. Ответ нужно вывести по модулю $10^9 + 1337$.

Подзадачи