D - ハミング
Editorial
/ 
/ 
Time Limit: 2 sec / Memory Limit: 256 MB
あるところに，バイナリ文字列を好む王様がいた． 王様は，等しい長さの二つのバイナリ文字列がどれくらい似ているかを調べるために， ハミング距離を計算することを得意としていた．
ハミング距離とは，文字が異なる箇所の個数で定義される距離尺度である． 例えば，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 で割った余りを1行で出力せよ．
制約
- 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の4つのバイナリ文字列が条件を満たす．
入力例2
1000 2 0100 1
出力例2
0
入力例3
0000111011111100111110001000011101010111 22 1111010000001001111110111111001111011110 13
出力例3
734254418