Bessie Goes Moo

시간 제한1초메모리 제한256 MB

요약

일곱 변수에 주어진 값을 대입할 때 (B+E+S+S+I+E)(G+O+E+S)(M+O+O)이 7의 배수가 되는 경우의 수를 셉니다.

난이도: 보통10점 중 4점
유형: 수학, 완전 탐색, 조합론
정답자: 아직 제출이 없습니다

문제

농부 존과 소 베시는 시간이 날 때마다 서로 수학 퍼즐을 낸다. 존이 마지막으로 낸 퍼즐은 너무 어려워서 베시가 풀지 못했다. 이번에는 베시가 존에게 어려운 퍼즐을 내려고 한다.

베시가 존에게 준 식은 $(B+E+S+S+I+E)(G+O+E+S)(M+O+O)$ 이고, 변수는 $B$ , $E$ , $S$ , $I$ , $G$ , $O$ , $M$ 일곱 개다. 여기서 $O$ 는 숫자 0이 아니라 변수다. 베시는 변수마다 그 변수가 가질 수 있는 정수 값의 목록을 최대 500개까지 알려준다. 존은 식 전체의 값이 7의 배수가 되는 값 배정이 몇 가지인지 세야 한다.

정답은 32비트 정수 범위를 넘을 수 있으므로 64비트 정수를 쓴다.

입력

첫째 줄에 정수 $N$ 이 주어진다. 다음 $N$ 개의 줄에는 변수 이름과 그 변수가 가질 수 있는 값 하나가 차례로 주어진다. 변수는 각각 적어도 한 번, 많아도 500번 등장하므로 $7 \le N \le 3500$ 이다. 같은 변수에 같은 값이 두 번 주어지지는 않는다. 모든 값은 $-10^5$ 이상 $10^5$ 이하다.

출력

식의 값이 7의 배수가 되는 값 배정의 개수를 정수 하나로 출력한다.

힌트

첫 번째 예제에서 조건을 만족하는 배정은 다음 두 가지다.

(B,E,S,I,G,O,M) = (2, 5, 7, 9,  1, 16, 19) -> 51,765
                = (2, 5, 7, 9,  1, 16, 2 ) -> 34,510

예제4

예제 1

입력

10
B 2
E 5
S 7
I 10
O 16
M 19
B 3
G 1
I 9
M 2

예상 출력

예제 2
입력
```
7
B 0
E 0
S 0
I 0
G 0
O 0
M 0
```
예상 출력
```
1
```
예제 3
입력
```
7
B 1
E 1
S 1
I 1
G 1
O 1
M 1
```
예상 출력
```
0
```

예제 4

입력

14
B -100000
B 100000
E -99999
E 0
S 100000
S -1
I -100000
I 1
G -7
G 7
O -3
O 3
M -100000
M 100000

예상 출력