Link-Cut Knödel#11728
Anmelden

Link-Cut Knödel

1 Sekunde
256 Megabyte
Schwer

Chmyaaax mag Knödel sehr, also beschloss er, nachdem er von der LCOI (Link-Cut Olympiade in Informatik) zurückgekehrt war, einige zu essen. Aber leider wurde das Link-Cut-System während der Olympiade umgebaut.

Jetzt ist das System eine begrenzte Fläche in Form eines Quadrats mit der Seitenlänge , dessen Ecken an den Punkten , , und liegen. An jedem Punkt gibt es ein Restaurant, in dem man Knödel kaufen kann. Außerdem gibt es eine Funktion f(x, y), die die Köstlichkeit der Knödel im Restaurant am Punkt definiert:

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

wobei das Zeichen die bitweise XOR-Operation, das Zeichen — bitweise OR-Operation und das Zeichen — bitweise AND-Operation darstellt.

Chmyaaax möchte die schmackhaftesten Knödel probieren, die er im Link-Cut-System finden kann. Daher möchte er wissen, was die größte Köstlichkeit der Knödel unter all den (n + 1) \times (n + 1) Restaurants im System ist und wie viele Restaurants es mit dieser Köstlichkeit gibt. Bitte helfen Sie ihm, diese beiden Werte zu bestimmen.

Da die Anzahl der Restaurants sehr groß sein kann, geben Sie bitte diesen Wert modulo 10^9 + 7 aus.

Eingabe

Eine einzige Zeile enthält eine ganze Zahl (1 \le n < 2^{60}) — die Länge der Seite des Link-Cut-Systems.

Ausgabe

In einer einzigen Zeile müssen Sie zwei ganze Zahlen ausgeben: die maximale Köstlichkeit der Knödel, die in den Restaurants gefunden werden kann, und die Anzahl der Restaurants mit diesem Wert der Köstlichkeit modulo 10 ^ 9 + 7. Bitte beachten Sie, dass die maximale Köstlichkeit so ausgegeben werden sollte, wie sie in der Antwort steht (d.h. nicht modulo 10 ^ 9 + 7).

Beispiele

Beispiel

Loading
Loading

Beispiel 1

Loading
Loading

Beispiel 2

Loading
Loading

Beispiel 3

Loading
Loading

Notiz

Im ersten Beispiel sind hier alle Punkte und die Werte der Köstlichkeit der Knödel in den Restaurants an diesen Punkten:

  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

Wie wir sehen können, ist die maximale Köstlichkeit all dieser Restaurants und es gibt Punkte, die sie haben.

Im zweiten Beispiel gibt es Punkte von Restaurants mit einer Köstlichkeit von :

  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.

Es kann gezeigt werden, dass es in den gegebenen Grenzen keine Restaurants mit einer Köstlichkeit von mehr als gibt.

Bewertung

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

  2. ( Punkte): n = 2^{k} - 1, für eine ganze Zahl (1 \le k \le 20);

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

  4. ( Punkte): n = 2^{k} - 1, für eine ganze Zahl (1 \le k \le 60);

  5. ( Punkte): keine zusätzlichen Einschränkungen.