Дівчинка Ангеліна зовсім не в захваті від програмування. Вона не дуже його розуміє і щиро сподівається, що на екзамені з алгоритмізації їй пощастить. Проте Халек вирішив, що покладатися лише на удачу - не найкраща ідея, тому вирішив допомогти Ангеліні підготуватися.

Щоб тренування було корисним, Халек дав Ангеліні таку задачу.

Дано три невід'ємні цілі числа 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_{16}\) у десятковій системі дорівнює \(1 \times 16 + 15 = 31\).

Крім того, в задачі використовується операція побітового AND, яка позначається символом \&. Розглянемо двійкові записи чисел x і b; за необхідності доповнимо їх зліва нулями до однакової довжини. Для кожного біта i:

\((x \& b)_i\) = 1, якщо \(x_i\) = 1 і \(b_i\) = 1,

\((x \& b)_i\) = 0 --- в усіх інших випадках.

Інакше кажучи, у кожному біті результат дорівнює 1 тоді і тільки тоді, коли в цьому біті в обох чисел стоїть 1.

Ангеліна, дивлячись на цю умову, одразу засмутилася, але Халек запевнив її, що задача не така вже й страшна. Вам потрібно визначити кількість цілих чисел x, для яких виконується нерівність \(l \le x \le r\) і при цьому x \& b = b.

Допоможіть Ангеліні впоратися із завданням, щоб вона поскорше змогла знову насолоджуватись переглядом улюблених фільмів.

Input Specification

У вхідних даних подано три рядки, які Халек дав Ангеліні для тренування:

у першому рядку міститься число l,

у другому рядку міститься число r,

у третьому рядку міститься число b.

Кожне з чисел задане у шістнадцятковій системі числення без провідних нулів (виняток - число 0) і складається лише з символів 0--9 та A--F.

Довжина кожного рядка не перевищує 50 000 символів. Гарантується, що \(0 \le l \le r\).

Output Specification

Виведіть одне ціле число --- кількість значень x, для яких виконуються умови задачі, за модулем \(10^9 + 7\).

Відповідь необхідно вивести у десятковій системі числення без провідних нулів.

Sample Input 1

4
A
CB

Sample Output 1

0