Counting Binary Strings with Bounded Hamming Distances

Given three binary strings (s_1), (s_2), and (s_3) of length (n), and three non-negative integers (r_1), (r_2), (r_3) (with (0 \le r_i \le n)), count the number of binary strings (S) of length (n) such that at least one of the following holds:

[ \begin{array}{rcl} d(S,s_1) &\le& r_1,\[6mm] d(S,s_2) &\le& r_2,\[6mm] d(S,s_3) &\le& r_3, \end{array} ]

where the Hamming distance between two binary strings (a = a_1a_2\ldots a_n) and (b = b_1b_2\ldots b_n) is defined as

[ d(a,b)=\sum_{i=1}^{n}|a_i-b_i|. ]

Your task is to compute the number of binary strings (S) that satisfy at least one of these conditions.

inputFormat

The first line contains an integer n — the length of the binary strings.

The next three lines each contain a binary string of length n: s1, s2, and s3.

The last line contains three non-negative integers r1, r2, and r3.

outputFormat

Output a single integer — the number of binary strings S that satisfy at least one of the conditions.

sample

3
000
111
010
1 1 1

5