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

Жюри Московской Олимпиады Школьников по программированию уже много лет проводит олимпиады. За это время у них накопилось огромное количество дипломов. С котятами, с видами на Воробьёвы Горы, с основными достопримечательностями города-героя Москвы и многими другими рисунками на фоне.

На носу была Московская Командная Олимпиада Школьников, на которой будет раздаваться очередной набор дипломов. Последняя проблема, которую всё никак не удавалось решить — кто же будет изображён на дипломах в этом году. Кандидатов было много, но в конце концов остались только Пегас Артур и Единорог Олег. Так как всему составу жюри собраться в одно время в одном месте довольно сложно, было решено провести электронное голосование.

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

И вот пришёл День выборов нового символа для диплома. Ровно в полдень результаты голосования складывались таким образом, что Единорог Олег выигрывал с отрывом в \(a\%\) голосов от Пегаса Артура. Притом известно, что проголосовало только \(p\%\) членов жюри. Пегасу Артуру стало интересно, есть ли у него еще шансы на победу. Вам известно, что победитель считается абсолютным только в том случае, если отрыв от соперника составляет хотя бы один процент голосов. Иначе победителем становится Единорог Олег, так как у него красивые глаза. В случае, если у Пегаса еще есть шансы на абсолютную победу, его интересует, какой минимальный целый процент голосов среди ещё не проголосовавших членов жюри он для этого должен набрать.

«Опять эти задачи про смайлики!» – грустил Серёжа на олимпиаде. Действительно, на этот раз авторы дали бесконечное число задач, пронумерованных натуральными числами \((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\)\(\). Описанный процесс повторяется (независимо от первого раза) второй раз. Вам требуется вычислить вероятность того, что два выписанных слова совпадут.

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

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

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

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