Problem Description

You are given three non-negative integers $b$, $l$, and $r$, written in hexadecimal.

As a reminder, hexadecimal (base $16$) uses the digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F, where A corresponds to $10$, B to $11$, C to $12$, D to $13$, E to $14$, and F to $15$. For example, the hexadecimal number 1F equals $1 \cdot 16 + 15 = 31$ (in decimal).

The operation $\mathbin{\&}$ denotes bitwise AND. Consider the binary representations of numbers $x$ and $b$, padding leading zeros if necessary so that they have the same length. For each bit position $i$:

$$(x \mathbin{\&} b)_i = \begin{cases} 1, & \text{if } x_i = 1 \text{ and } b_i = 1,\\ 0, & \text{otherwise.} \end{cases}$$

In other words, a bit in the result is $1$ only when both numbers have $1$ in the corresponding bit.

You need to find the number of integers $x$ such that $l \le x \le r$ and $x \mathbin{\&} b = b$. Output this count modulo $10^9 + 7$.

Input Format

The input consists of three lines: the first line is the number $l$, the second line is the number $r$, and the third line is the number $b$.

Each number is given in hexadecimal, with no leading zeros (except when the number itself is 0), and consists of characters 0-9 and A-F. The length of each line does not exceed $50\,000$ characters. It is guaranteed that $0 \le l \le r$.

Output Format

Output one integer: the number of values $x$ that satisfy the conditions, modulo $10^9 + 7$.

The answer should be written in decimal, without leading zeros.

8
F
5

2

2
F9
A

60

Hint

Sample Explanation

In the first sample, the values of $x$ that satisfy the condition are the hexadecimal numbers D and F.

Scoring

The points for each subtask are awarded only if that subtask and all of its required subtasks pass all testdata.

Subtask	Points	Additional Constraints	Required Subtasks
1	10	$0 \le r, b < 16^4$, $l = 0$
2	5	$0 \le l, r, b < 16^4$	1
3	10	$0 \le r, b < 16^7$, $l = 0$
4	6	$0 \le l, r, b < 16^7$	1–3
5	10	$0 \le r, b < 16^{15}$, $l = 0$	1, 3
6	7	$0 \le l, r, b < 16^{15}$	1–5
7	14	$0 \le r, b < 16^{1000}$, $l = 0$	1, 3, 5
8	7	$0 \le l, r, b < 16^{1000}$	1–7
9	11	$0 \le r, b < 16^{50\,000}$, $l = 0$	1, 3, 5, 7
10	12	$0 \le l, r < 16^{50\,000}$, $b = 0$
11	8	$0 \le l, r, b < 16^{50\,000}$	1–10

Translated by ChatGPT 5