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.