Link-Cut Dumplings#11728
Sign in

Link-Cut Dumplings

1 second
256 megabytes
Hard

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 with its corners located at the points , , and . 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 dumplings in the restaurant in the point :

f(x, y) = (x \oplus y) + (x\,|\,y) + (x\,\&\,y),

where the 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 know, 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 (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

Example

Input
3
Output
6 9

Example

Input
5
Output
14 6

Example

Loading
Loading

Example 1

Loading
Loading

Example 2

Loading
Loading

Example 3

Loading
Loading

Note

In the first example, here are all the 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 and there are points having it.

In the second example, there are points of restaurants with deliciousness of :

  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 .

Scoring

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

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

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

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

  5. ( points): no additional constraints.