| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 | 1024 MB | 47 | 16 | 13 | 33.333% |
Central European Regional Contest (CERC) is a contest famous for its interesting and always well-prepared tasks. One of these tasks was about finding a volume of a sum of three balls. Maybe it was a challenge 10 years ago, but nowadays contestants should not be bothered with so easy and standard problems. Instead of using 3D space, we will use $n$-dimensional hypercube. Obviously, it requires some definitions.
$n$-dimensional hypercube has 2ドル^n$ vertices, each of them is represented by a sequence of $n$ coordinates which are either 0ドル$ or 1ドル$. For example, 3ドル$-dimensional hypercube has 8ドル$ vertices: 000, 001, 010, 011, 100, 101, 110, 111.
Ball with radius $r$ and center $s$ is a subset of vertices of hypercube which have distance at most $r$ to the vertex $s$. We compute the distance in Manhattan metric which means that vertex $p$ belongs to this ball if and only if coordinates of vertices $p$ and $s$ differ on at most $r$ positions.
Find the number of vertices which belong to the sum of three balls, i.e. number of vertices which belong to at least one of these balls. Print the result modulo 10ドル^9+7$.
First line of input contains one integer $n$ (1ドル \leq n \leq 10,000円$), denoting number of dimensions.
Description of three balls follow. Each description takes one line and $i$-th line contains integer $r_i$ (0ドル \leq r_i \leq n$) and binary word $s_i$ consisting of $n$ characters which are either 0ドル$ or 1ドル$. These are the radius and the center of the ball, respectively.
You need to print one integer --- number of vertices belonging to sum of these three balls, modulo 10ドル^9+7$.
3 1 000 1 100 0 111
7
5 2 10110 0 11010 1 00000
19
Explanation to first sample test: 3ドル$-dimensional hypercube is just a mere cube. Following pictures show which vertices belong to following balls. Grey circle denotes center of a ball.
First ball contains vertices 000, 100, 010, 001. Second ball contains vertices 100, 000, 110, 101. Third ball is just a single vertex 111. Sum of these balls contains 7ドル$ vertices --- all of them except 011.