세 개의 초구

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

요약

n차원 초입방체의 꼭짓점 중 세 중심 s_i로부터 해밍 거리가 r_i 이하인 공 가운데 하나 이상에 속하는 꼭짓점의 수를 10^9+7로 나눈 나머지로 구합니다.

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

문제

중앙유럽 지역 대회(CERC)는 흥미롭고 준비가 철저한 문제로 알려진 대회다. 이 대회의 한 문제는 세 개의 구의 합집합의 부피를 구하는 것이었다. 합집합이란 세 구 중 적어도 하나에 속하는 점들의 집합이다. 십 년 전이라면 도전이 되었겠지만, 지금은 참가자에게 이렇게 쉽고 평범한 문제를 내면 지루해한다. 그래서 3차원 공간 대신 n차원 초입방체를 쓰겠다. 물론 먼저 정의가 필요하다.

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

반지름이 r이고 중심이 s인 초구는 s와의 맨해튼 거리가 r 이하인 초입방체 꼭짓점들의 집합이다. 꼭짓점 p는 p와 s의 좌표가 서로 다른 위치가 r 이하일 때, 그리고 그때에만 이 초구에 속한다.

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

입력

첫 줄에 차원 수 n ( $1 \le n \le 10\,000$ )이 주어진다. 다음 세 줄에는 각각 i번째 초구의 반지름 $r_i$ ( $0 \le r_i \le n$ )과 중심 $s_i$ 를 나타내는 0과 1로 이루어진 길이 n의 이진 문자열이 차례로 주어진다.

출력

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

힌트

첫 번째 예시는 3차원 초입방체, 즉 정육면체다. 아래 그림은 각 초구에 속하는 꼭짓점을 보여준다. 회색 원은 초구의 중심을 나타낸다.

첫 번째 초구는 000, 100, 010, 001 꼭짓점을 포함한다. 두 번째 초구는 100, 000, 110, 101을 포함한다. 세 번째 초구는 111 하나뿐이다. 세 초구의 합집합은 011을 제외한 7개의 꼭짓점을 포함한다.

예제2

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