Link-Cut Пельмени

Чмяяяякс очень любит пельмени, поэтому, когда он вернулся с LCOI (Link-Cut Олимпиады по Информатике), он решил поесть немного. Но, к сожалению, в то время, когда он был на олимпиаде, система Link-Cut была перестроена.

Теперь система представляет собой ограниченную плоскость в форме квадрата со стороной длиной $n$, углы которого расположены в точках $(0;0)$, $(0;n)$, $(n;0)$ и $(n;n)$. В каждой точке есть ресторан, где можно купить пельмени. Также существует функция $f(x,y)$, которая определяет вкус пельменей в ресторане в точке $(x;y)$:

где знак $\oplus$ представляет собой побитовую операцию XOR, знак $|$ — побитовую операцию OR, а знак $\&$ — побитовую операцию AND.

Чмяяяякс хочет попробовать самые вкусные пельмени, которые он может найти в системе Link-Cut, поэтому он хочет узнать, среди всех $(n+1)\times (n+1)$ ресторанов в системе, какова максимальная вкусность пельменей и сколько ресторанов с этой вкусностью существует. Пожалуйста, помогите ему определить эти два значения.

Поскольку количество ресторанов может быть очень большим, пожалуйста, выведите это значение по модулю $10^9+7$.

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

Единственная строка содержит одно целое число $n$ ($1\le n<2^{60}$) — длина стороны системы Линк-Разрез.

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

В одной строке необходимо вывести два целых числа: максимальную вкусность пельменей, которую можно найти среди всех ресторанов, и количество ресторанов с этой вкусностью по модулю $10^9+7$. Пожалуйста, обратите внимание, что максимальная вкусность должна быть выведена в ответе так, как она есть (т.е. не по модулю $10^9+7$).

Примеры

Примечание

В первом примере приведены все $16$ точек и значения вкусности пельменей в ресторанах в них:

1. $(0,0)$: $f(0,0)=0+0+0=$0$;$

2. $(0,1)$: $f(0,1)=1+1+0=$2$;$

3. $(0,2)$: $f(0,2)=2+2+0=$4$;$

4. $(0,3)$: $f(0,3)=3+3+0=$6$;$

5. $(1,0)$: $f(1,0)=1+1+0=$2$;$

6. $(1,1)$: $f(1,1)=0+1+1=$2$;$

7. $(1,2)$: $f(1,2)=3+3+0=$6$;$

8. $(1,3)$: $f(1,3)=2+3+1=$6$;$

9. $(2,0)$: $f(2,0)=2+2+0=$4$;$

10. $(2,1)$: $f(2,1)=3+3+0=$6$;$

11. $(2,2)$: $f(2,2)=0+2+2=$4$;$

12. $(2,3)$: $f(2,3)=1+3+2=$6$;$

13. $(3,0)$: $f(3,0)=3+3+0=$6$;$

14. $(3,1)$: $f(3,1)=2+3+1=$6$;$

15. $(3,2)$: $f(3,2)=1+3+2=$6$;$

16. $(3,3)$: $f(3,3)=0+3+3=$6$.$

Как видно, максимальная вкусность всех этих ресторанов составляет $6$, и есть $9$ точек с этой вкусностью.

Во втором примере есть $6$ точек ресторанов с вкусностью $14$:

1. $(2;5)$: $f(2,5)=(2\oplus 5)+(2|5)+(2\&5)=7+7+0=14;$

2. $(3;4)$: $f(3,4)=7+7+0=14;$

3. $(3;5)$: $f(3,5)=6+7+1=14;$

4. $(4;3)$: $f(4,3)=7+7+0=14;$

5. $(5;2)$: $f(5,2)=7+7+0=14;$

6. $(5;3)$: $f(5,3)=6+7+1=14.$

Можно показать, что в заданных границах нет ресторанов с вкусностью более $14$.

Оценивание

1. ($11$ баллов): $n<2^{10}$;

2. ($19$ баллов): $n=2^k-1$ , для некоторого целого $k$ $(1\le k\le 20)$;

3. ($14$ баллов): $n<2^{20}$;

4. ($14$ баллов): $n=2^k-1$ , для некоторого целого $k$ $(1\le k\le 60)$;

5. ($42$ балла): без дополнительных ограничений.