CF1045H Self-exploration

Wall-B 厌倦了一遍又一遍地探索月球，决定去探索他自身的组成——二进制数。他取了一个二进制数，决定统计所有长度为 $2$ 的不同子串出现的次数。他将这些值分别存储在 $c_{00}$、$c_{01}$、$c_{10}$ 和 $c_{11}$ 中，分别表示子串 $00$、$01$、$10$ 和 $11$ 在该数中出现的次数。例如： $10111100 \rightarrow c_{00} = 1,\ c_{01} = 1,\ c_{10} = 2,\ c_{11} = 3$ $10000 \rightarrow c_{00} = 3,\ c_{01} = 0,\ c_{10} = 1,\ c_{11} = 0$ $10101001 \rightarrow c_{00} = 1,\ c_{01} = 3,\ c_{10} = 3,\ c_{11} = 0$ $1 \rightarrow c_{00} = 0,\ c_{01} = 0,\ c_{10} = 0,\ c_{11} = 0$ Wall-B 发现，可能有多个二进制数满足相同的 $c_{00}$、$c_{01}$、$c_{10}$ 和 $c_{11}$ 约束。因此，他想统计在区间 $[A, B]$ 内，有多少个二进制数满足给定的 $c_{xy}$ 约束。不幸的是，他的计算能力不足以处理他感兴趣的大区间。你能帮帮他吗？由于答案可能很大，请输出对 $10^9 + 7$ 取模后的结果。

前两行分别包含两个正二进制数 $A$ 和 $B$（$1 \leq A \leq B < 2^{100\,000}$），表示区间的起点和终点。二进制数 $A$ 和 $B$ 没有前导零。 接下来的四行包含十进制整数 $c_{00}$、$c_{01}$、$c_{10}$ 和 $c_{11}$（$0 \leq c_{00}, c_{01}, c_{10}, c_{11} \leq 100\,000$），表示长度为 $2$ 的子串 $00$、$01$、$10$ 和 $11$ 出现的次数。

输出一个整数，表示区间 $[A, B]$ 内有多少个二进制数满足约束，结果对 $10^9 + 7$ 取模。

示例 1：区间 $[10,1001]$ 内的二进制数有 $10,11,100,101,110,111,1000,1001$。只有 $110$ 满足约束：$c_{00} = 0, c_{01} = 0, c_{10} = 1, c_{11} = 1$。 示例 2：区间内没有任何数满足约束。 由 ChatGPT 4.1 翻译