Изучая книгу «Уравнения математической магии» Роман Ойра-Ойра и Кристобаль Хунта обнаружили интересное уравнение: \(a - (a \oplus x) - x = 0\) для заданого \(a\), где знаком \(\oplus\) обозначено побитовое исключающее ИЛИ (XOR) двух чисел (эта операция обозначается как ^ или xor во многих современных языках программирования). Поскольку данное уравнение предназначалось для решения на машине Алдан-3, все вычисления производились над целыми неотрицательными числами по модулю \(2^{32}\). Ойра-Ойра быстро нашел \(x\), являющееся решением, однако Кристобалю Хунте результат Ойры-Ойры показался недостаточно интересным, поэтому он спросил коллегу, сколько всего существует решений данного уравнения. Так как все вычисления производятся по модулю \(2^{32}\), Кристобаля Хунту интересует количество таких решений \(x\), что \(0 \leq x < 2^{32}\). Такая задача оказалась для Ойры-Ойры слишком сложной, поэтому он обратился за помощью к Вам.

«Опять эти задачи про смайлики!» – грустил Серёжа на олимпиаде. Действительно, на этот раз авторы дали бесконечное число задач, пронумерованных натуральными числами \((1, 2, 3, \dots)\), и все они были про смайлики. Серёжа много тренировался перед олимпиадой, и выбрал себе лучшую тактику: после задачи с номером \(x\) он решает задачу с номером \(x\) xor \((x/2)\), где xor – это побитовое исключающее или, а деление производится с округлением вниз. Например, \(4\) xor \(8\) равно \(12\), \(7\) xor \(11\) тоже равно \(12\), \(5\) xor \((5/2)\) равно \(7\).

Серёжа считает задачу с номером \(x\) хорошей, если он решит \(k\) задач (начиная с \(x\), выбирая их по своей тактике, при этом, возможно он решит некоторые задачи не по одному разу), а (\(k + 1\))-й задачей опять окажется \(x\). Помогите Серёже – для данного \(k\) найдите количество хороших задач. Так как ответ может быть большим, выведите его по модулю \(10^9 + 7\).

Мы создали бесконечный кроссворд, взяв прямоугольник размера \(\)\(N \times M\)\(\), заполненный буквами и замостили им бесконечную плоскость. Например, прямоугольник

В данном кроссворде нами случайно (равновероятно) выбирается одна клетка и одно из восьми направлений. Затем начиная с данной клетки в данном направлении выписывается слово длины \(\)\(K\)\(\). Описанный процесс повторяется (независимо от первого раза) второй раз. Вам требуется вычислить вероятность того, что два выписанных слова совпадут.

По мнению Александра Павловича, текст необычайно красив, если некоторые особые слова (например, «коммунизм», «Ленин», «счастье») встречаются не слишком часто, но и не слишком редко, к тому же достаточно равномерно.

Александр Павлович работает корректором. К нему поступают тексты, он имеет право их некоторым образом менять, после чего возвращает уже исправленную версию.

В связи со своими воззрениями о красоте Александру Павловичу постоянно приходится проверять, сколько особых слов сейчас в той или иной части текста.

Он настолько устал от рутинного подсчёта: «а сколько тут особых слов?», «а сколько тут?», что просит вас помочь ему автоматизировать этот процесс.

Места в новом трамвае в Загребе организованы в виде сетки, состоящей из \(N\) рядов, пронумерованных от \(1\) до \(N\), и двух столбцов, пронумерованных от \(1\) до \(2\). Расстояние между между сиденьями \((R_a, C_a)\) и \((R_b, C_b)\) равно евклидому расстоянию между центрами соответствующих клеток, а именно \(\sqrt{(R_a - R_b)^2 + (C_a - C_b)^2}\).

Большинство пассажиров предпочитают уединение при использовании общественного транспорта, и они всегда стараются выбрать место, которое находится как можно дальше от других пассажиров. Точнее говоря, когда пассажир садится в трамвай, он выбирает свободное место, расстояние от которого до ближайшего занятого места максимально. Если имеется более одного такого места, он всегда выбирает место с номером в меньшем ряду, а если есть несколько таких мест, он выбирает место с наименьшим столбцом. После того, как пассажир выберет место, он будет сидеть там до тех пор, пока не покинет трамвай. Если трамвай пуст, следующий пассажир, который будет входить, всегда будет выбирать место в ряду 1 и столбце 1.

Напишите программу, которая, учитывая последовательность событий и тип каждого события, определяет, куда сядет каждый из пассажиров. Трамвай изначально пуст.

События пронумерованы от \(1\) до \(M\) в том порядке, в котором они произошли. Существует два вида событий: событие типа «Е» соответствует пассажиру, входящему в трамвай, а событие типа «L» соответствует пассажиру, покидающему трамвай. Для события типа «L» также дается целое число \(P\) - оно указывает, что уходящий пассажир - это тот, который зашел в трамвай во время события \(P\).

Гарантируется, что в трамвае всегда будет хотя бы одно свободное место, когда пассажир пытается войти.