题目描述

给定三个非负整数 $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$（十进制）。

运算 $\mathbin{\&}$ 表示按位 AND（按位“与”）。考虑数字 $x$ 和 $b$ 的二进制表示，必要时在左边补零使它们长度相同。对于每一位 $i$：

$$(x \mathbin{\&} 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 \mathbin{\&} 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$ 取模的结果。

答案以十进制表示，不带前导零。

8
F
5

2

2
F9
A

60

提示

样例解释

在第一个样例中，满足条件的 $x$ 值是十六进制数 D 和 F。

评分规则

每个子任务的分数仅在该子任务及其所有必需子任务的全部测试通过时授予。

子任务	分值	额外限制	必要子任务
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