#3223. 「PA 2019」Trzy kule

内存限制:1024 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

题目译自 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

样例输出 1

7

样例输入 2

5
2 10110
0 11010
1 00000

样例输出 2

19

数据范围与提示

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