题目描述

对于两个长度为 $n$ 的 $01$ 串 $a_{1..n},b_{1..n}$，定义它们的距离 $\operatorname{d(a,b)}=|a_1-b_1|+|a_2-b_2|+...+|a_n-b_n|$。

给定三个长度为 $n$的 $01$ 串 $s_1,s_2,s_3$以及三个非负整数 $r_1,r_2,r_3(0\le r_i\le n)$，问有多少个长度为 $n$ 的 $01$ 串 $S$满足$\operatorname{d(S,s[1])}\le r_1,\operatorname{d(S,s[2])}\le r_2,\operatorname{d(S,s[3])}\le r_3$ 这三个不等式中至少有一个成立。

输入格式

第一行一个正整数 $n$。

第二行一个非负整数 $r_1$，然后一个长度为 $n$ 的 $01$ 串 $s_1$。

第三行一个非负整数 $r_2$，然后一个长度为 $n$ 的 $01$ 串 $s_2$。

第四行一个非负整数 $r_3$，然后一个长度为 $n$ 的 $01$ 串 $s_3$。

输出格式

输出一行一个整数，即满足条件的 $S$ 的数量模 $10^9+7$。

5
2 10110
0 11010
1 00000

19

提示

对于 $100\%$ 的数据，$1\le n\le 10^4$。