Битовая магия

Даны три неотрицательных целых числа b, l и r, записанные в шестнадцатеричной системе счисления.

Напомним, что шестнадцатеричная система счисления (основание 16) использует цифры 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F, где A соответствует числу 10, B – 11, C – 12, D – 13, E – 14, F – 15. Например, число 1F в шестнадцатеричной системе равно 1 · 16 + 15 = 31 в десятичной системе.

Операция & обозначает побитовое AND (побитовое «И») над двоичными представлениями чисел. Рассмотрим двоичные записи чисел x и b, при необходимости дополним их слева нулями до равной длины. Для каждого разряда i:

То есть в каждом бите результат равен 1 тогда и только тогда, когда в этом бите у обоих чисел стоит 1.

Определите количество целых чисел x, таких, что l ≤ x ≤ r и выполняется условие x & b = b. Выведите остаток от деления этого количества на 10⁹ + 7.

Входные данные

Во входном файле INPUT.TXT даны три строки: первая строка содержит число l, вторая строка содержит число r, третья строка содержит число b.

Каждое число задано в шестнадцатеричной системе счисления без ведущих нулей (кроме случая самого числа 0) и состоит из символов 0–9, A–F. Длина каждой строки не превосходит 50 000 символов. Гарантируется, что 0 ≤ l ≤ r.

Выходные данные

В выходной файл OUTPUT.TXT выведите одно целое число – количество значений x, для которых выполняются условия задачи, по модулю 10⁹ + 7. Ответ выведите в десятичной системе счисления без ведущих нулей.

Примеры

Примечание

В первом примере из условия подходящими значениями x являются шестнадцатеричные числа D и F.

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]