由于厌倦了一遍又一遍地探索月球,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$$$)分别代表两位数子串00、01、10和11的个数。
输出
输出一个整数,代表区间 $$$[A, B]$$$ 中有多少个二进制数满足 mod $$$10^9 + 7$$$ 约束。
示例
输入 #1
10 1001 0 0 1 1
输出 #1
1
输入 #2
10 10001 1 2 3 4
输出 #2
0
注意
示例 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:区间内没有数字满足约束条件