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á 500 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ị là một bội của 7.

Lưu ý rằng đáp án của bài toán này có thể quá lớn để lưu trong một số nguyên 32 bit, vì vậy bạn có thể sẽ cần dùng số nguyên 64 bit (chẳng hạn kiểu long long trong C hoặc C++).

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 500 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ừ \(-10^5\) đến \(10^5\).

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ị là một bội của 7.

Ví dụ

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

Nguồn

USACO 2015 US Open, Silver — Bessie Goes Moo. Tác giả đề: Brian Dean, 2015.

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