题目描述

译自 ROI Regional 2026 Day2 T2. Битовая магия

给定三个非负整数 $b$、$l$ 和 $r$，以十六进制形式给出（无前导零，除非数字本身为 $0$）。十六进制使用字符 0-9、A-F，其中 A-F 分别对应十进制的 10-15。

操作 & 表示位与（bitwise AND）：对两个数的二进制表示（必要时左补零至相同长度），每一位结果为 $1$ 当且仅当该位上两个数均为 $1$。要求计算满足以下条件的整数 $x$ 的个数：$l \leq x \leq r$ 且 $x\ \&\ b = b$ （即 $x$ 在 $b$ 的所有 1 位上也必须为 1，$x$ 包含了 $b$ 的所有位）。

输出该数量对 $10^9 + 7$ 取模的结果（十进制，无前导零）。

输入格式

输入共三行：

• 第一行：十六进制字符串表示 $l$
• 第二行：十六进制字符串表示 $r$
• 第三行：十六进制字符串表示 $b$

每个字符串长度不超过 $50000$，仅含大写字符 0-9、A-F，无前导零。

保证 $0 \leq l \leq r$。

输出格式

输出一个整数：满足条件的 $x$ 数量对 $10^9 + 7$ 取模的结果（十进制）。

8
F
5

2

满足条件的 $x$（十六进制）为 D 和 F，共 $2$ 个。

2
F9
A

60

数据范围与提示

详细子任务附加限制及分值如下表所示：