You are given three non-negative integers $b$, $l$, and $r$, written in hexadecimal notation.
Recall that the hexadecimal numeral system (base 16) uses 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 & denotes the bitwise AND applied to the binary representations of numbers.
Consider the binary representations of numbers $x$ and $b$. If necessary, pad them with leading zeros to make their lengths equal. For each bit position $i$: $$ (x \& b)_i = \begin{cases} 1, & \text{if } x_i = 1 \text{ and } b_i = 1, \\ 0, & \text{otherwise}. \end{cases} $$ That is, in each bit position, the result is $1$ if and only if both numbers have a $1$ in that bit.
Determine the number of integers $x$ such that $l \le x \le r$ and the condition $x \& b = b$ holds.
Output the remainder of this count modulo $10^9 + 7$.
Input Format
The input consists of three lines:
- the first line contains the number $l$,
- the second line contains the number $r$,
- the third line contains the number $b$.
Each number is given in hexadecimal notation without leading zeros (except for the number $0$ itself) and consists of characters $0$–$9$, $A$–$F$.
The length of each string does not exceed $50\,000$ characters.
It is guaranteed that $0 \le l \le r$.
Output Format
Output a single integer — the number of values $x$ satisfying the conditions of the problem, modulo $10^9 + 7$.
The answer must be printed in decimal notation without leading zeros.
Scoring
Points for each subtask are awarded only if all tests for that subtask and all required subtasks are passed successfully.
| 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^{50000}$, $l = 0$ | 1, 3, 5, 7 |
| 10 | 12 | $0 \le l, r < 16^{50000}$, $b = 0$ | — |
| 11 | 8 | $0 \le l, r, b < 16^{50000}$ | 1–10 |
Example
Input
8 F 5
Output
2
Input
2 F9 A
Output
60
Note
In the first example, the suitable values of $x$ are the hexadecimal numbers $D$ and $F$. ```