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.

Чмяяяакс хоче спробувати найсмачніші пельмені, які він може знайти в системі Лінк-Різання, тому він хоче дізнатися, серед усіх $(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$ бали): без додаткових обмежень.