Link-Cut Пельмені#11728

Link-Cut Пельмені

1 секунда

256 мегабайтів

Складна

Чмяяяакс дуже любить пельмені, тому після того, як він повернувся з LCOI (Link-Cut Олімпіади з Інформатики), він вирішив поїсти їх. Але, на жаль, під час олімпіади система Link-Cut була перебудована.

Тепер система є обмеженою площиною у формі квадрата зі стороною довжини $n$ , кути якого розташовані в точках $(0, 0)$ , $(0, n)$ , $(n, 0)$ та $(n, n)$ . У кожній точці є ресторан, де можна купити пельмені. Також є функція $f (x, y)$ f(x, y), яка визначає смачність пельменів у ресторані в точці $(x, y)$ :

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

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

де знак $\oplus$ представляє бітове XOR, знак $∣$ — бітове OR, а знак $&$ — бітове AND.

Чмяяяакс хоче спробувати найсмачніші пельмені, які він може знайти в системі Лінк-Різання, тому він хоче дізнатися, серед усіх $(n + 1) \times (n + 1)$ (n + 1) \times (n + 1) ресторанів у системі, яка максимальна смачність пельменів і скільки ресторанів з цією смачністю існує. Будь ласка, допоможіть йому визначити ці два значення.

Оскільки кількість ресторанів може бути дуже великою, будь ласка, виведіть це значення за модулем $1 0^{9} + 7$ 10^9 + 7.

Вхідні дані

Єдиний рядок містить одне ціле число $n$ ( $1 \leq n < 2^{60}$ 1 \le n < 2^{60}) — довжина сторони системи Лінк-Різання.

Вихідні дані

В одному рядку потрібно вивести два цілі числа: максимальну смачність пельменів, які можна знайти серед усіх ресторанів, та кількість ресторанів з цим значенням смачності за модулем $1 0^{9} + 7$ 10^9 + 7. Будь ласка, зверніть увагу, що максимальну смачність потрібно виводити так, як вона є у відповіді (тобто не за модулем $1 0^{9} + 7$ 10^9 + 7).

Приклади

Приклад

6 9

Приклад

14 6

Приклад

Приклад 1

Приклад 2

Приклад 3

Примітка

У першому прикладі наведені всі $16$ точок та значення смачності пельменів у ресторанах у них:

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

Як видно, максимальна смачність усіх цих ресторанів дорівнює $6$ , і є $9$ точок, які мають її.

У другому прикладі є $6$ точок ресторанів зі смачністю $14$ :

$(2, 5) : f (2, 5) = (2 \oplus 5) + (2 ∣ 5) + (2 & 5) = 7 + 7 + 0 = 14$ (2, 5):\ f(2, 5) = (2 \oplus 5) + (2\,|\,5) + (2\,\&\,5) = 7 + 7 + 0 = 14;
$(3, 4) : f (3, 4) = 7 + 7 + 0 = 14$ (3, 4):\ f(3, 4) = 7 + 7 + 0 = 14;
$(3, 5) : f (3, 5) = 6 + 7 + 1 = 14$ (3, 5):\ f(3, 5) = 6 + 7 + 1 = 14;
$(4, 3) : f (4, 3) = 7 + 7 + 0 = 14$ (4, 3):\ f(4, 3) = 7 + 7 + 0 = 14;
$(5, 2) : f (5, 2) = 7 + 7 + 0 = 14$ (5, 2):\ f(5, 2) = 7 + 7 + 0 = 14;
$(5, 3) : f (5, 3) = 6 + 7 + 1 = 14$ (5, 3):\ f(5, 3) = 6 + 7 + 1 = 14.

Можна показати, що немає ресторанів у заданих межах зі смачністю більше ніж $14$ .

Оцінювання

( $11$ балів): $n < 2^{10}$ n < 2^{10};
( $19$ балів): $n = 2^{k} - 1$ n = 2^{k} - 1, для деякого цілого $k$ $(1 \leq k \leq 20)$ (1 \le k \le 20);
( $14$ балів): $n < 2^{20}$ n < 2^{20};
( $14$ балів): $n = 2^{k} - 1$ n = 2^{k} - 1, для деякого цілого $k$ $(1 \leq k \leq 60)$ (1 \le k \le 60);
( $42$ бали): без додаткових обмежень.