Farmer John và cô bò Bessie thích trao đổi các câu đố toán học vào thời gian rảnh. Câu đố gần nhất FJ đưa cho Bessie khá khó và cô không giải được. Giờ đây, cô muốn trả đũa FJ bằng cách đưa cho ông một câu đố hóc búa.

Bessie đưa cho FJ biểu thức \((B+E+S+S+I+E)(G+O+E+S)(M+O+O)\), chứa bảy biến \(B,E,S,I,G,O,M\) (ký tự "\(O\)" là một biến, không phải chữ số không). Với mỗi biến, cô đưa cho FJ một danh sách gồm không quá 20 giá trị nguyên mà biến đó có thể nhận. Cô yêu cầu FJ đếm số cách khác nhau để gán giá trị cho các biến sao cho toàn bộ biểu thức có giá trị chẵn.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(N\). Mỗi dòng trong \(N\) dòng tiếp theo chứa một biến và một giá trị mà biến đó có thể nhận. Mỗi biến xuất hiện trong danh sách ít nhất một lần và nhiều nhất 20 lần. Với cùng một biến, không có giá trị khả dĩ nào được liệt kê quá một lần. Mọi giá trị khả dĩ đều nằm trong khoảng từ \(-300\) đến \(300\).

Dữ liệu ra

In một số nguyên duy nhất: số cách FJ có thể gán giá trị cho các biến sao cho biểu thức trên có giá trị chẵn.

Ví dụ

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

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

Nguồn

USACO 2015 US Open, Bronze — Bessie Gets Even. Tác giả đề: Brian Dean, 2015.

https://usaco.org/index.php?page=viewproblem2&cpid=546