Như chúng ta đều biết, có một sự khác biệt lớn giữa đa thức bậc 4 và đa thức bậc 5. Câu hỏi về việc không tồn tại công thức nghiệm tổng quát cho đa thức bậc 5 đã tạo ra lý thuyết Galois nổi tiếng, mà theo như tác giả thấy, không có liên quan gì đến bài toán của chúng ta ở đây.

Chúng ta chỉ xem xét các đa thức nhiều biến có bậc tối đa là 4, trên 26 biến, được đại diện bởi tập hợp 26 chữ cái tiếng Anh viết thường. Dưới đây là một đa thức như vậy:

aber+aab+c

Cho một chuỗi \(s\), chúng ta tính giá trị của đa thức trên chuỗi đó. Việc tính toán cho kết quả \(p(S)\) như sau: Mỗi biến được thay thế bằng số lần xuất hiện của chữ cái đó trong \(S\).
Ví dụ, lấy đa thức ở trên và giả sử \(S\) = "abracadabra edgar". Có sáu chữ 'a', hai chữ 'b', một chữ 'c', một chữ 'e', và ba chữ 'r'. Vì vậy

p(S) = 6 * 2 * 1 * 3 + 6 * 6 * 2 + 1 = 109.

Cho một từ điển gồm các từ phân biệt chỉ chứa các chữ cái viết thường, chúng ta gọi một chuỗi \(S\) là một d-cụm từ (d-phrase) nếu

S = "S1 S2 S3 ... Sd",

trong đó \(S_i\) là bất kỳ từ nào trong từ điển, với \(1 \le i \le d\). Nghĩa là, \(S\) có dạng \(d\) từ trong từ điển ngăn cách bởi các khoảng trắng. Cho một số K \(\le 10\), nhiệm vụ của bạn là, với mỗi \(1 \le d \le \mathbf{K}\), hãy tính tổng của \(p(S)\) trên tất cả các \(d\)-cụm từ. Vì kết quả có thể rất lớn, bạn được yêu cầu tính số dư khi chia kết quả cho 10009.

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ test T. T bộ test tiếp theo. Định dạng của mỗi bộ test là:
Một dòng chứa biểu thức \(p\) cho đa thức nhiều biến, như mô tả bên dưới, sau đó là một khoảng trắng, tiếp theo là một số nguyên K.
Một dòng với một số nguyên n, số lượng từ trong từ điển.
Sau đó là n dòng, mỗi dòng chứa một từ, chỉ gồm các chữ cái viết thường. Không có từ nào bị lặp lại trong cùng một bộ test.

Chúng ta luôn viết đa thức dưới dạng tổng của các số hạng; mỗi số hạng là tích của các biến. Chúng ta viết \(a^t\) đơn giản là \(t\) chữ \(a\) viết liền nhau. Ví dụ, \(a^2b\) được viết là \(aab\). Các biến trong mỗi số hạng luôn được sắp xếp không giảm theo thứ tự từ điển.

Dữ liệu ra

Với mỗi bộ test, in ra một dòng có dạng

Case #X: sum1 sum2 ... sumK

trong đó \(X\) là số thứ tự bộ test bắt đầu từ 1, và \(sum_i\) là tổng của \(p(S)\), với \(S\) chạy qua tất cả các \(i\)-cụm từ, modulo 10009.

Ràng buộc

• \(1 \le \mathbf{T} \le 100\).
• Chuỗi \(p\) gồm một hoặc nhiều số hạng nối với nhau bằng dấu '+'. Nó sẽ không bắt đầu hoặc kết thúc bằng dấu '+'. Sẽ có tối đa 5 số hạng cho mỗi \(p\). Mỗi số hạng gồm ít nhất 1 và tối đa 4 chữ cái viết thường, được sắp xếp theo thứ tự không giảm. Không có hai số hạng nào trong cùng một đa thức giống nhau.
• Mỗi từ không rỗng, chỉ gồm các chữ cái tiếng Anh viết thường và không dài quá 50 ký tự. Không có từ nào bị lặp lại trong cùng một từ điển.

Phân nhóm

• Small dataset: \(1 \le \mathbf{n} \le 20\), \(1 \le \mathbf{K} \le 5\).
• Large dataset: \(1 \le \mathbf{n} \le 100\), \(1 \le \mathbf{K} \le 10\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

2
ehw+hwww 5
6
where
when
what
whether
who
whose
a+e+i+o+u 3
4
apple
orange
watermelon
banana

Case #1: 15 1032 7522 6864 253
Case #2: 12 96 576

Nguồn

Google Code Jam 2009, Vòng 3, bài Alphabetomials.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.