贝茜的报复

题目描述:

农夫约翰和奶牛贝茜喜欢在业余时间互相出数学题。

约翰给贝茜出了一道相当难的问题，导致她没能解决。

现在，她希望通过给约翰出一道有挑战性的难题来报复他。

贝茜给了约翰一个表达式
 ( B + E + S + S + I + E )( G + O + E + S )( M + O + O )，其中包含七个变量 B, E, S, I, G, O, M（ O 是变量，不是零 ）。

对于每个变量，她给约翰一个列表，表中包含该变量可采用的最多 20 个整数值。

她要求约翰计算，共有多少种给变量赋值的方法可以使得表达式的计算结果为偶数。

输入格式:

第一行包含一个整数 N。

接下来 N 行，每行包含一个变量和该变量的一个可能值。

每个变量至少出现 1 次，最多出现 20 次。

同一变量不会重复列出同一可能值。

输出格式:

输出可以使得表达式的计算结果是偶数的给变量赋值的方法总数。

数据范围:

7 ≤ N ≤ 140 ,
所有变量的可能取值范围 [ −300, 300 ]

本题答案不会超出int范围。

样例输入:

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

样例输出:

6

提示:

共有 66 种可能的赋值方式：

(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

注意，(2, 5, 7, 10, 1, 16, 19)  和 (3, 5, 7, 9, 1, 16, 19)，虽然计算结果相同，但是赋值方式不同，所以要分别计数。

时间限制: 1000ms
空间限制: 256MB

---

来源: USACO 2015 US Open Bronze