Bessie Gets Even#11167

Bessie Gets Even

1 second

128 megabytes

Medium

Farmer John and Bessie the cow love to exchange math puzzles in their free time. The last puzzle FJ gave Bessie was quite difficult, and she failed to solve it. Now she wants to get even with FJ by giving him a challenging puzzle.

Bessie gives FJ the expression

(B + E + S + S + I + E) (G + O + E + S) (M + O + O),

(B + E + S + S + I + E)(G + O + E + S)(M + O + O),

which contains the seven variables $B, E, S, I, G, O$ B, E, S, I, G, O, and $M$ .

(Note that $O$ is a variable, not the digit zero.)

For each variable, Bessie gives FJ a list of up to $20$ integer values that the variable can take. She asks FJ to count the number of different ways to assign values to the variables such that the entire expression evaluates to an even number.

Input

The first line contains an integer $n$ .

The next $n$ lines each contain a variable and a possible value for that variable. Each variable appears in the list at least once and at most $20$ times. No possible value is listed more than once for the same variable.

All possible values are in the range $- 300$ to $300$ .

Output

Print one integer giving the number of ways FJ can assign values to the variables such that the expression above evaluates to an even number.

Examples

There are $6$ possible assignments of values to the variables:

(B,E,S,I,G,O,M) = (2, 5, 7, 10, 1, 16, 19) -> 53,244
                = (2, 5, 7, 10, 1, 16, 2)  -> 35,496
                = (2, 5, 7, 9,  1, 16, 2)  -> 34,510
                = (3, 5, 7, 10, 1, 16, 2)  -> 36,482
                = (3, 5, 7, 9,  1, 16, 19) -> 53,244
                = (3, 5, 7, 9,  1, 16, 2)  -> 35,496

Note Note that $(2, 5, 7, 10, 1, 16, 19)$ (2,5,7,10,1,16,19) and $(3, 5, 7, 9, 1, 16, 19)$ (3,5,7,9,1,16,19) count as different assignments even though they produce the same value of the expression, because the variables are assigned different values.

Example 1