Bessie Goes Moo

Time limit1sMemory limit256 MB

Summary

Count assignments of listed values to seven variables that make (B+E+S+S+I+E)(G+O+E+S)(M+O+O) a multiple of 7.

Level: Medium4 of 10
Topics: Math, Brute force, Combinatorics
Solved: No attempts yet

Problem

Farmer John and Bessie the cow trade math puzzles whenever they have free time. The last puzzle John gave Bessie was hard enough that she could not solve it, so now she wants to hand John a hard puzzle of her own.

Bessie gives John the expression $(B+E+S+S+I+E)(G+O+E+S)(M+O+O)$ , which uses the seven variables $B$ , $E$ , $S$ , $I$ , $G$ , $O$ , $M$ . The $O$ is a variable, not a zero. For each variable Bessie lists up to 500 integer values that the variable is allowed to take. John has to count how many different assignments of values to the variables make the whole expression a multiple of 7.

The answer does not always fit in a 32-bit integer, so use a 64-bit integer type.

Input

The first line contains an integer $N$ . Each of the next $N$ lines contains a variable name and one value that variable is allowed to take. Each variable appears at least once and at most 500 times, so $7 \le N \le 3500$ . The same value is never listed twice for the same variable. Every value is in the range $-10^5$ to $10^5$ .

Output

Print one integer, the number of assignments of values to the variables that make the expression a multiple of 7.

Hint

In the first example the two assignments that count are

(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

Examples4

Example 1

Input

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

Expected output

Example 2
Input
```
7
B 0
E 0
S 0
I 0
G 0
O 0
M 0
```
Expected output
```
1
```
Example 3
Input
```
7
B 1
E 1
S 1
I 1
G 1
O 1
M 1
```
Expected output
```
0
```

Example 4

Input

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

Expected output