P15132 [ROIR 2026] Bit Magic.

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$.

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 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.

### 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$ | 1 | | 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