Фермер Джон и корова Беси в свободное время любят обмениваться математическими пазлами. Последний пазл, который ФД дал Беси, был довольно сложный и Беси не смогла решить его. Теперь она хочет дать ФД очень сложный пазл.
Беси даёт ФД выражение (B+E+S+S+I+E)(G+O+E+S)(M+O+O), содержащее семь переменных B,E,S,I,G,O,M ( "O" это переменная, а не 0). Для каждой переменной она даёт ФД список до 20 целых чисел, которые эта переменная может принять. Беси просит ФД посчитать количество различных способов назначить значения переменным, чтобы вычисленное выражение было чётным числом.
Входные данные
Первая строка ввода содержит целое число N. Каждая из N следующих строк содержит переменную и возможное значение для этой переменной. Каждая переменная появится в этом списке не менее одного раза и не более 20 раз. Для одной и той же переменной все задаваемые значения различны. Все значения находятся в диапазоне от −300 до 300.
Выходные данные
Выведите единственное целое число, задающее количество способов, которыми ФД может назначить значения переменным, чтобы выражение давало чётный результат.
| Ввод |
Вывод |
10
B 2
E 5
S 7
I 10
O 16
M 19
B 3
G 1
I 9
M 2
|
6 |
Всего имеется 6 подходящих вариантов назначения переменным значений:
(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) рассматриваются как различные назначения, несмотря на то, что они дают одинаковый результат.