CF1045H.Self-exploration

Being bored of exploring the Moon over and over again Wall-B decided to explore something he is made of — binary numbers. He took a binary number and decided to count how many times different substrings of length two appeared. He stored those values in $c_{00}$, $c_{01}$, $c_{10}$ and $c_{11}$, representing how many times substrings 00, 01, 10 and 11 appear in the number respectively. For example:

$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 noticed that there can be multiple binary numbers satisfying the same $c_{00}$, $c_{01}$, $c_{10}$ and $c_{11}$ constraints. Because of that he wanted to count how many binary numbers satisfy the constraints $c_{xy}$ given the interval $[A, B]$. Unfortunately, his processing power wasn't strong enough to handle large intervals he was curious about. Can you help him? Since this number can be large print it modulo $10^9 + 7$.

厌倦了一次又一次地探索月球，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$ 取模后的值。

First two lines contain two positive binary numbers $A$ and $B$ ($1 \leq A \leq B \lt 2^{100\,000}$), representing the start and the end of the interval respectively. Binary numbers $A$ and $B$ have no leading zeroes.

Next four lines contain decimal numbers $c_{00}$, $c_{01}$, $c_{10}$ and $c_{11}$ ($0 \leq c_{00}, c_{01}, c_{10}, c_{11} \leq 100\,000$) representing the count of two-digit substrings 00, 01, 10 and 11 respectively.

前两行包含两个正的二进制数 $A$ 和 $B$（$1 \leq A \leq B \lt 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$），分别表示两位子串 00、01、10 和 11 的出现次数。

Output one integer number representing how many binary numbers in the interval $[A, B]$ satisfy the constraints mod $10^9 + 7$.

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

Example 1: The binary numbers in the interval $[10,1001]$ are $10,11,100,101,110,111,1000,1001$. Only number 110 satisfies the constraints: $c_{00} = 0, c_{01} = 0, c_{10} = 1, c_{11} = 1$.

Example 2: No number in the interval satisfies the constraints

示例 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：区间内没有数字满足约束条件