Three Balls

Time limit5sMemory limit1024 MB

Summary

Given n-dimensional hypercube and three balls with radii and binary centers under Manhattan distance, count vertices covered by at least one ball modulo 1e9+7.

Level: Medium7 of 10
Topics: Combinatorics, Math, Intervals
Solved: No attempts yet

Problem

The Central European Regional Contest (CERC) is known for its interesting and well-prepared tasks. One of these tasks asked for the volume of a sum of three balls. That may have been a challenge ten years ago, but contestants today should not spend time on such easy, standard problems. This problem uses an $n$ -dimensional hypercube instead of 3D space, so some definitions come first.

An $n$ -dimensional hypercube has $2^n$ vertices. Each vertex is a sequence of $n$ coordinates, and each coordinate is either $0$ or $1$ . For example, the 3-dimensional hypercube has 8 vertices: 000, 001, 010, 011, 100, 101, 110, 111.

A ball with radius $r$ and center $s$ is a set of vertices at distance at most $r$ from the vertex $s$ . The distance is the Manhattan distance. A vertex $p$ belongs to the ball if and only if $p$ and $s$ differ in at most $r$ positions.

Find the number of vertices that belong to the sum of the three balls, that is, the vertices that belong to at least one of them. Print the result modulo $10^9+7$ .

Input

The first line contains an integer $n$ ( $1 \leq n \leq 10\,000$ ), the number of dimensions.

Each of the next three lines describes one ball. Each line contains an integer $r_i$ ( $0 \leq r_i \leq n$ ), the radius, and a binary string $s_i$ of length $n$ , the center.

Output

Print one integer, the number of vertices in the sum of the three balls, modulo $10^9+7$ .

Hint

The figure below shows the first sample. The 3-dimensional hypercube is a cube. The grey circle marks the center of each ball.

Examples2

Example 1
Input
```
3
1 000
1 100
0 111
```
Expected output
```
7
```
Example 2
Input
```
5
2 10110
0 11010
1 00000
```
Expected output
```
19
```