Description

For two binary strings $a_{1..n}$ and $b_{1..n}$ of length $n$, define their distance as $\operatorname{d(a,b)}=|a_1-b_1|+|a_2-b_2|+...+|a_n-b_n|$.

Given three binary strings $s_1,s_2,s_3$ of length $n$ and three non-negative integers $r_1,r_2,r_3$ $(0\le r_i\le n)$, ask how many binary strings $S$ of length $n$ satisfy that at least one of the following three inequalities holds: $\operatorname{d(S,s[1])}\le r_1$, $\operatorname{d(S,s[2])}\le r_2$, $\operatorname{d(S,s[3])}\le r_3$.

Input Format

The first line contains a positive integer $n$.

The second line contains a non-negative integer $r_1$, followed by a binary string $s_1$ of length $n$.

The third line contains a non-negative integer $r_2$, followed by a binary string $s_2$ of length $n$.

The fourth line contains a non-negative integer $r_3$, followed by a binary string $s_3$ of length $n$.

Output Format

Output one line containing one integer, which is the number of valid $S$ modulo $10^9+7$.

5
2 10110
0 11010
1 00000

19

Hint

For $100\%$ of the testdata, $1\le n\le 10^4$.

Translated by ChatGPT 5