#P5982. [PA2019] Trzy kule

[PA2019] Trzy kule

题目描述

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

给定三个长度为 nn0101s1,s2,s3s_1,s_2,s_3以及三个非负整数 r1,r2,r3(0rin)r_1,r_2,r_3(0\le r_i\le n),问有多少个长度为 nn0101SS满足$\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,然后一个长度为 nn0101s1s_1

第三行一个非负整数 r2r_2,然后一个长度为 nn0101s2s_2

第四行一个非负整数 r3r_3,然后一个长度为 nn0101s3s_3

输出格式

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

5
2 10110
0 11010
1 00000
19

提示

对于 100%100\% 的数据,1n1041\le n\le 10^4