Бессі отримує парне#11167

Бессі отримує парне

1 секунда

128 мегабайтів

Середня

Фермер Джон і корова Бессі люблять обмінюватися математичними головоломками у вільний час. Остання головоломка, яку FJ дав Бессі, виявилася доволі складною, і вона не змогла її розв'язати. Тепер вона хоче поквитатися з FJ, запропонувавши йому складну головоломку.

Бессі пропонує FJ наступний вираз

(B + E + S + S + I + E) (G + O + E + S) (M + O + O),

(B + E + S + S + I + E)(G + O + E + S)(M + O + O),

який містить сім змінних $B, E, S, I, G, O$ B, E, S, I, G, O та $M$ .

(Зверніть увагу, що $O$ є змінною, а не цифрою $0$ .)

Для кожної змінної Бессі надає FJ список, що містить не більше $20$ цілих значень, які може приймати ця змінна. Вона просить FJ підрахувати кількість різних способів присвоїти значення змінним так, щоб увесь вираз у результаті мав парне значення.

Вхідні дані

У першому рядку міститься ціле число $n$ .

У наступних $n$ рядках кожен рядок містить змінну та можливе значення цієї змінної. Кожна змінна зустрічається в цьому списку щонайменше один раз і не більше $20$ разів. Одне й те саме можливе значення не зустрічається більше одного разу для однієї й тієї самої змінної.

Усі можливі значення знаходяться в діапазоні від $- 300$ до $300$ .

Вихідні дані

Виведіть одне ціле число — кількість способів присвоїти значення змінним так, щоб наведений вище вираз мав парне значення.

Приклади

Існує $6$ можливих способів присвоїти значення змінним:

(B,E,S,I,G,O,M) = (2, 5, 7, 10, 1, 16, 19) -
                = (2, 5, 7, 10, 1, 16, 2)  -
                = (2, 5, 7, 9,  1, 16, 2)  -
                = (3, 5, 7, 10, 1, 16, 2)  -
                = (3, 5, 7, 9,  1, 16, 19) -
                = (3, 5, 7, 9,  1, 16, 2)  -

Note Зверніть увагу, що $(2, 5, 7, 10, 1, 16, 19)$ (2,5,7,10,1,16,19) і $(3, 5, 7, 9, 1, 16, 19)$ (3,5,7,9,1,16,19) вважаються різними способами присвоєння значень, незважаючи на те, що вони дають однакове значення виразу, оскільки значення змінним присвоєні по-різному.

Приклад 1