[AdditionalFile3223.zip](file://AdditionalFile3223.zip?type=additional_file)

#3223. 「PA 2019」Trzy kule

标签: 传统 | 时间限制: 1000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 PA 2019 Runda 5 Trzy kule

对于两个长度为 $n$ 的 $01$ 串 $a_1, a_2, \dots, a_n$ 和 $b_1, b_2, \dots, b_n$，定义它们的距离 $d(a, b) = \sum_{i=1}^{n} |a_i - b_i|$。

给定三个长度为 $n$ 的 $01$ 串 $s_1, s_2, s_3$ 以及三个非负整数 $r_1, r_2, r_3$，问有多少个长度为 $n$ 的 $01$ 串 $S$ 满足 $d(S, s_1) \le r_1, d(S, s_2) \le r_2, 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$。

样例 1

输入

3
1 000
1 100
0 111

输出

7

样例 2

输入

5
2 10110
0 11010
1 00000

输出

19

数据范围与提示

$1 \le n \le 10000, 0 \le r_i \le n$