Bessie Gets Even

Interview

Time limit1sMemory limit256 MB

Summary

Count assignments of listed values to seven letters that make the product (B+E+S+S+I+E)(G+O+E+S)(M+O+O) even.

Level: Easy3 of 10
Topics: Brute force, Combinatorics, Math
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 get even by handing him a hard one.

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 she lists up to 20 integer values that the variable is allowed to take. John has to count the number of different ways to assign values to the variables so that the whole expression evaluates to an even number.

Input

The first line contains an integer $N$ . Each of the next $N$ lines contains a variable and one possible value for that variable, separated by a space. Every variable appears in this list at least once and at most 20 times. The same value is never listed twice for the same variable. All values are between $-300$ and $300$ . So $N$ is between 7 and 140.

Output

Print, on one line, the number of ways John can assign values to the variables so that the expression evaluates to an even number.

Hint

In the example with $N = 10$ there are six possible assignments.

(B,E,S,I,G,O,M) = (2, 5, 7, 10, 1, 16, 19) -> 53244
                = (2, 5, 7, 10, 1, 16, 2 ) -> 35496
                = (2, 5, 7, 9,  1, 16, 2 ) -> 34510
                = (3, 5, 7, 10, 1, 16, 2 ) -> 36482
                = (3, 5, 7, 9,  1, 16, 19) -> 53244
                = (3, 5, 7, 9,  1, 16, 2 ) -> 35496

$(2,5,7,10,1,16,19)$ and $(3,5,7,9,1,16,19)$ give the same value, but they assign different values to the variables, so they count as two different assignments.

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 0
S 0
I 0
G 1
O 0
M 1
```
Expected output
```
0
```

Example 4

Input

8
B -300
B -299
E -1
S -2
I -297
G -5
O -300
M -7

Expected output