#P5548. [PA2019]Trzy kule

    ID: 4551 传统题 1000ms 768MiB 尝试: 9 已通过: 6 难度: 8 上传者: 标签>CF2500提高+/省选-补集计数暴力枚举一维前缀和扫描中维护贡献阶乘逆元预处理乘法原理

[PA2019]Trzy kule

[PA2019] Trzy kule

题目描述

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

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

输入格式

第一行一个正整数 nn。

第二行一个非负整数 r1r_1,然后一个长度为 nn 的 0101 串 s1s_1。

第三行一个非负整数 r2r_2,然后一个长度为 nn 的 0101 串 s2s_2。

第四行一个非负整数 r3r_3,然后一个长度为 nn 的 0101 串 s3s_3。

输出格式

输出一行一个整数,即满足条件的 SS 的数量模 109+710^9+7。

样例 #1

样例输入 #1

5
2 10110
0 11010
1 00000

样例输出 #1

19

提示

对于 100%100\% 的数据,1≤n≤1041\le n\le 10^4。

鸣谢Claris上传