Raviolis Link-Cut#11728
Se connecter

Raviolis Link-Cut

1 seconde
256 mégaoctets
Difficile

Chmyaaax aime beaucoup les raviolis, donc après son arrivée de LCOI (Olympiade Link-Cut en Informatique), il a décidé d'en manger. Mais, malheureusement, au moment où il était à l'olympiade, le système Link-Cut a été reconstruit.

Maintenant, le système est un plan limité en forme de carré avec une longueur de côté dont les coins sont situés aux points , , et . À chaque point, il y a un restaurant où il est possible d'acheter des raviolis. De plus, il existe une fonction f(x, y) qui définit la délicatesse des raviolis dans le restaurant au point :

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

où le signe représente l'opération XOR bit à bit, le signe — l'opération OR bit à bit et le signe — l'opération AND bit à bit.

Chmyaaax veut goûter les raviolis les plus savoureux qu'il peut trouver dans le système Link-Cut, il veut donc savoir, parmi tous les (n + 1) \times (n + 1) restaurants du système, quelle est la plus grande délicatesse des raviolis, et combien de restaurants ont cette délicatesse. S'il vous plaît, aidez-le à déterminer ces deux valeurs.

Étant donné que le nombre de restaurants peut être très grand, veuillez afficher cette valeur modulo 10^9 + 7.

Entrée

Une seule ligne contient un entier (1 \le n < 2^{60}) — la longueur du côté du système Link-Cut.

Sortie

Dans une seule ligne, vous devez afficher deux entiers : la délicatesse maximale des raviolis qui peut être trouvée parmi tous les restaurants et le nombre de restaurants avec cette valeur de délicatesse modulo 10 ^ 9 + 7. Veuillez noter que la délicatesse maximale doit être affichée telle quelle dans la réponse (c'est-à-dire pas modulo 10 ^ 9 + 7).

Exemples

Exemple

Loading
Loading

Exemple 1

Loading
Loading

Exemple 2

Loading
Loading

Exemple 3

Loading
Loading

Note

Dans le premier exemple, voici tous les points et les valeurs de délicatesse des raviolis dans les restaurants à ces points :

  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

Comme nous pouvons le voir, la délicatesse maximale de tous ces restaurants est et il y a points ayant cette valeur.

Dans le deuxième exemple, il y a points de restaurants avec une délicatesse 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.

Il peut être prouvé qu'il n'y a pas de restaurants dans les limites données avec une délicatesse supérieure à .

Notation

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

  2. ( points): n = 2^{k} - 1, pour un entier (1 \le k \le 20);

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

  4. ( points): n = 2^{k} - 1, pour un entier (1 \le k \le 60);

  5. ( points): pas de contraintes supplémentaires.