Link-Cut Dumplings

Chmyaaax likes dumplings very much, so after he had arrived from LCOI (Link-Cut Olympiad in Informatics), he decided to eat some. But, unfortunately, at the time he was at the olympiad, the Link-Cut system has been rebuilt.

Now the system is a limited plane in the shape of a square with side length $n$ with its corners located at the points $(0;0)$, $(0;n)$, $(n;0)$ and $(n;n)$. In each point, there is a restaurant, where it is possible to buy dumplings. Also, there is a function $f(x,y)$ that defines the deliciousness of the dumpings in the restaurant in the point $(x;y)$:

where the $\oplus$ sign represents bitwise XOR operation, the $|$ sign — bitwise OR operation and the $\&$ sign — bitwise AND operation.

Chmyaaax wants to taste the most tasty dumplings he can find in the Link-Cut system, thus he wants to now, among all $(n+1)\times (n+1)$ restaurants in the system, what is the largest deliciousness of dumplings, and how many restaurants with this deliciousness there are. Please, help him to determine these two values.

Since the number of restaurants can be very large, please, output this value modulo $10^9+7$.

Input

A single line contains one integer $n$ ($1\le n<2^{60}$) — the length of the side of the Link-Cut system.

Output

In a single line, you need to output two integers: the maximum deliciousness of the dumplings that can be found among all the restaurants and the number of restaurants with this value of deliciousness modulo $10^9+7$. Please, note that the maximum deliciousness should be output as it is in the answer (i.e., not modulo $10^9+7$).

Examples

Note

In the first example, here are all the $16$ points and the values of dumplings deliciousness in restaurants at them:

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$.$

As we can see, the maximum deliciousness of all these restaurants is $6$ and there are $9$ points having it.

In the second example, there are $6$ points of restaurants with deliciousness of $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.$

It can be shown that there are no restaurants in the given borders with deliciousness of more than $14$.

Scoring

1. ($11$ points): $n<2^{10}$;

2. ($19$ points): $n=2^k-1$ , for some integer $k$ $(1\le k\le 20)$;

3. ($14$ points): $n<2^{20}$;

4. ($14$ points): $n=2^k-1$ , for some integer $k$ $(1\le k\le 60)$;

5. ($42$ points): no additional constraints.