农夫约翰和奶牛贝茜喜欢在业余时间互相出数学题。
约翰给贝茜出了一道相当难的问题,导致她没能解决。
现在,她希望通过给约翰出一道有挑战性的难题来报复他。
贝茜给了约翰一个表达式 (B+E+S+S+I+E)(G+O+E+S)(M+O+O),其中包含七个变量 B,E,S,I,G,O,M(O 是变量,不是零)。
对于每个变量,她给约翰一个列表,表中包含该变量可采用的最多 500 个整数值。
她要求约翰计算,共有多少种给变量赋值的方法可以使得表达式的计算结果是 7 的倍数。
注意,答案可能超过标准的 32 位整数型能够表示的范围,所以你可能需要使用更大的数据类型,例如C/C++中的“long long”。
第一行包含一个整数 N。
接下来 N 行,每行包含一个变量和该变量的一个可能值。
每个变量至少出现 1 次,最多出现 500 次。
同一变量不会多次列出同一可能值。
输出可以使得表达式的计算结果是 7 的倍数的给变量赋值的方法总数。
7≤N≤3500,
所有变量的可能取值范围 [−105,105]
10 B 2 E 5 S 7 I 10 O 16 M 19 B 3 G 1 I 9 M 2
2
两种可能的赋值方式为:
(B,E,S,I,G,O,M) = (2, 5, 7, 9, 1, 16, 19) -> 51,765 = (2, 5, 7, 9, 1, 16, 2 ) -> 34,510
Bessie gives FJ the ex
Note that the answer to this problem can be too large to fit into a 32-bit integer, so you probably want to use 64-bit integers (e.g., "long long"s in C or C++).
The two possible assignments are
[Problem credits: Brian Dean, 2015]
INPUT FORMAT (file bgm.in):
The first line of the input contains an integer N. The next N lines each contain a variable and a possible value for that variable. Each variable will appear in this list at least once and at most 500 times. No possible value will be listed more than once for the same variable. All possible values will be in the range −105 to 105.
OUTPUT FORMAT (file bgm.out):
Print a single integer, giving the number of ways FJ can assign values to variables so the ex
SAMPLE INPUT:
10
B 2
E 5
S 7
I 10
O 16
M 19
B 3
G 1
I 9
M 2
SAMPLE OUTPUT:
2
(B,E,S,I,G,O,M) = (2, 5, 7, 9, 1, 16, 19) -> 51,765
= (2, 5, 7, 9, 1, 16, 2 ) -> 34,510