← 返回题目列表

Codeforces · 1045/H

H. 自我探索

中文机器翻译题面 查看原题

由于厌倦了一遍又一遍地探索月球,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:区间内没有数字满足约束条件