Module: Iterate over all subpatterns of a given mask


Problem

7 /7


Bessie got even

Problem

Farmer John and Besi the cow love to trade math puzzles in their free time. The last puzzle FD gave to Besie was quite difficult and Besie couldn't solve it. Now she wants to give FD a very difficult puzzle.

Besi gives a FD expression  (B+E+S+S+I+E)(G+O+E+S)(M+O+O), containing seven variables B,E, S,I,G,O,M ("O" is a variable, not 0). For each variable, it gives the FD a list of up to 20 integers that this variable can accept. Besi asks the FD to count the number of different ways to assign values ​​to variables so that the calculated expression is an even number.

Input

The first line of input contains an integer N. Each of N the following lines contains a variable and a possible value for that variable. Each variable will appear in this list at least once and at most 20 times. For the same variable, all given values ​​are different. All values ​​range from −300 to 300.

Output

Print a single integer that specifies the number of ways the FD can assign values ​​to variables in order for the expression to give an even result.

 

Input Output
10
B2
E 5
S7
I 10
O 16
M19
B3
G1
I 9
M2
6
 

There are 6 possible options for assigning values ​​to 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 that (2,5,7,10,1,16,19) and (3,5,7,9,1,16,19) are treated as different assignments even though they give the same result.