题目描述
对于两个长度为 n 的 01 串 a1..n,b1..n,定义它们的距离 d(a,b)=∣a1−b1∣+∣a2−b2∣+...+∣an−bn∣。
给定三个长度为 n的 01 串 s1,s2,s3以及三个非负整数 r1,r2,r3(0≤ri≤n),问有多少个长度为 n 的 01 串 S满足d(S,s[1])≤r1,d(S,s[2])≤r2,d(S,s[3])≤r3 这三个不等式中至少有一个成立。
输入格式
第一行一个正整数 n。
第二行一个非负整数 r1,然后一个长度为 n 的 01 串 s1。
第三行一个非负整数 r2,然后一个长度为 n 的 01 串 s2。
第四行一个非负整数 r3,然后一个长度为 n 的 01 串 s3。
输出格式
输出一行一个整数,即满足条件的 S 的数量模 109+7。
提示
对于 100% 的数据,1≤n≤104。