Dumplings Link-Cut#11728
Iniciar sesión

Dumplings Link-Cut

1 segundo
256 megabytes
Difícil

A Chmyaaax le gustan mucho los dumplings, así que después de haber llegado de LCOI (Olimpiada Link-Cut en Informática), decidió comer algunos. Pero, desafortunadamente, en el momento en que estaba en la olimpiada, el sistema Link-Cut había sido reconstruido.

Ahora el sistema es un plano limitado en forma de cuadrado con longitud de lado con sus esquinas ubicadas en los puntos , , y . En cada punto, hay un restaurante donde se pueden comprar dumplings. Además, hay una función f(x, y) que define la delicia de los dumplings en el restaurante en el punto :

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

donde el signo representa la operación XOR a nivel de bits, el signo — operación OR a nivel de bits y el signo — operación AND a nivel de bits.

Chmyaaax quiere probar los dumplings más sabrosos que pueda encontrar en el sistema Link-Cut, por lo que quiere saber, entre todos los (n + 1) \times (n + 1) restaurantes en el sistema, cuál es la mayor delicia de los dumplings y cuántos restaurantes tienen esta delicia. Por favor, ayúdalo a determinar estos dos valores.

Dado que el número de restaurantes puede ser muy grande, por favor, imprime este valor módulo 10^9 + 7.

Entrada

Una sola línea contiene un entero (1 \le n < 2^{60}) — la longitud del lado del sistema Link-Cut.

Salida

En una sola línea, necesitas imprimir dos enteros: la máxima delicia de los dumplings que se puede encontrar entre todos los restaurantes y el número de restaurantes con este valor de delicia módulo 10 ^ 9 + 7. Por favor, ten en cuenta que la máxima delicia debe ser impresa tal como está en la respuesta (es decir, no módulo 10 ^ 9 + 7).

Ejemplos

Ejemplo

Loading
Loading

Ejemplo 1

Loading
Loading

Ejemplo 2

Loading
Loading

Ejemplo 3

Loading
Loading

Nota

En el primer ejemplo, aquí están todos los puntos y los valores de la delicia de los dumplings en los restaurantes en ellos:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Como podemos ver, la máxima delicia de todos estos restaurantes es y hay puntos que la tienen.

En el segundo ejemplo, hay puntos de restaurantes con una delicia de :

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

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

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

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

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

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

Se puede demostrar que no hay restaurantes en los límites dados con una delicia mayor que .

Puntuación

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

  2. ( puntos): n = 2^{k} - 1, para algún entero (1 \le k \le 20);

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

  4. ( puntos): n = 2^{k} - 1, para algún entero (1 \le k \le 60);

  5. ( puntos): sin restricciones adicionales.