세 개의 공

시간 제한5초메모리 제한1024 MB

요약

n차원 초입방체에서 세 구의 반지름과 중심이 주어질 때, 적어도 하나의 구에 속하는 꼭짓점의 수를 10^9+7로 나눈 나머지로 구합니다.

난이도: 보통10점 중 7점
유형: 조합론, 수학, 구간
정답자: 아직 제출이 없습니다

문제

중앙 유럽 지역 대회(CERC)는 흥미롭고 늘 잘 준비된 문제로 알려져 있다. 그중 문제 하나가 세 공의 합의 부피를 구하는 것이었다. 10년 전에는 도전적인 문제였을지 모르지만, 지금의 참가자가 이렇게 쉽고 표준적인 문제에 시간을 쓸 필요는 없다. 이 문제에서는 3차원 공간 대신 $n$ 차원 초입방체를 사용한다. 먼저 정의를 살펴보자.

$n$ 차원 초입방체는 $2^n$ 개의 꼭짓점을 가진다. 각 꼭짓점은 $n$ 개의 좌표로 이루어진 열이고, 각 좌표는 $0$ 또는 $1$ 이다. 예를 들어 3차원 초입방체의 꼭짓점은 000, 001, 010, 011, 100, 101, 110, 111의 8개다.

반지름이 $r$ 이고 중심이 $s$ 인 공은 꼭짓점 $s$ 로부터 거리가 $r$ 이하인 꼭짓점들의 집합이다. 거리는 맨해튼 거리로 잰다. 꼭짓점 $p$ 는 $p$ 와 $s$ 가 서로 다른 위치가 $r$ 개 이하일 때, 그리고 그때에만 공에 속한다.

세 공의 합에 속한 꼭짓점의 개수, 즉 세 공 중 적어도 하나에 속하는 꼭짓점의 수를 구하라. 답은 $10^9+7$ 로 나눈 나머지로 출력한다.

입력

첫째 줄에 차원의 수 $n$ ( $1 \leq n \leq 10\,000$ )이 주어진다.

이어지는 세 줄에는 공을 하나씩 기술한다. 각 줄에는 반지름 $r_i$ ( $0 \leq r_i \leq n$ )와 중심을 나타내는 길이 $n$ 의 이진 문자열 $s_i$ 가 주어진다.

출력

세 공의 합에 속한 꼭짓점의 개수를 $10^9+7$ 로 나눈 나머지로 한 줄에 출력한다.

힌트

첫 번째 샘플에 대한 설명이다. 3차원 초입방체는 정육면체다. 아래 그림은 각 공에 속하는 꼭짓점을 보여준다. 회색 원은 공의 중심이다.

예제2

예제 1
입력
```
3
1 000
1 100
0 111
```
예상 출력
```
7
```
예제 2
입력
```
5
2 10110
0 11010
1 00000
```
예상 출력
```
19
```