从前,有一个喜欢二进制字符串的国王。 国王想要找出两个长度相等的二进制字符串有多相似。 他擅长计算汉明距离。
汉明距离是由字符不同的位置数量定义的距离度量。 例如,1011101和1001001有不同的第3个和第5个字符,所以 汉明距离为 2。 请注意,不同长度的二进制字符串之间没有定义汉明距离。
从前,国王创建了一个二进制字符串 s_1 的汉明距离为 d_1 和 二进制字符串 我想知道有多少个像 s_2 的汉明距离为 d_2 这样的二进制字符串。
你必须为国王编写一个程序来计算有多少个二进制字符串满足这样的条件。 不过这个数字可能会很大,所以 输出除以10^{9} + 7 后的余数。
入力形式
输入按以下格式给出。
s_1 d_1 s_2 d_2
出力形式
计算满足条件的二进制字符串的个数。 在一行中输出除以 10^{9} + 7 后的余数。
制約
- s_1, s_2仅包含 0 和 1 个字符。
- |s_1| = |s_2|
- 1 \leq |s_1| \leq 10^5
- 0 \leq d_1, d_2 \leq |s_1|
- d_1, d_2是整数。
针对该问题的判断设置了一组15分的测试用例。除了上述约束之外,该组中包含的测试用例还满足以下约束。
- 1 \leq |s_1| \leq 10^2
入出力例
入力例1
1000 2 0100 2
出力例1
4
四个二进制字符串 1110、1101、0010、0001 满足条件。
入力例2
1000 2 0100 1
出力例2
0
入力例3
0000111011111100111110001000011101010111 22 1111010000001001111110111111001111011110 13
出力例3
734254418