给定三个非负整数 $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 \cdot 16 + 15 = 31$。
运算符 & 表示对二进制表示进行逐位 AND（按位“与”）运算。
考虑数 $x$ 和 $b$ 的二进制表示，必要时在左侧补零使其长度相同。对每一位 $i$：
$$(x \& b)_i = \begin{cases} 1, & \text{如果 } x_i = 1 \text{ 且 } b_i = 1, \\ 0, & \text{否则。} \end{cases}$$
也就是说，在某一位上，当且仅当两个数在该位上都是 1，结果才为 1。
请确定满足 $l \le x \le r$ 且 $x \& b = b$ 的整数 $x$ 的个数。 输出该数量对 $10^9 + 7$ 取模后的结果。
输入格式
输入包含三行字符串：
第一行包含数字 $l$，第二行包含数字 $r$，第三行包含数字 $b$。
每个数字都以十六进制表示，不含前导零（除非该数本身为 0），由字符 0–9、A–F 组成。
每个字符串的长度不超过 50 000 个字符。
保证 $0 \le l \le r$。
输出格式
输出一个整数——满足题目条件的 $x$ 的个数，对 $10^9 + 7$ 取模。
答案以十进制表示，且不含前导零。
子任务
只有在通过该子任务以及其所需的所有子任务的全部测试后，才会获得该子任务的分数。
| 子任务 | 分值 | 额外限制 | 所需子任务 |
|---|---|---|---|
| 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 |
样例数据
标准输入
8 F 5
标准输出
2
标准输入
2 F9 A
标准输出
60
说明
在第一个样例中，满足条件的 $x$ 为十六进制数 $D$ 和 $F$。