Một biểu thức logic là biểu thức gồm các biến (được kí hiệu bằng các chữ cái in thường nhận giá trị là số nguyên 32 bit không dấu) với các toán tử logic AND, OR, XOR và các dấu ngoặc. Một biểu thức hợp lệ được định nghĩa như sau:

• Nếu x, y là biến thì: x là biểu thức hợp lệ; y là biểu thức hợp lệ; (x AND y), (x OR y), (x XOR y) là các biểu thức hợp lệ.
• Nếu A, B là biểu thức hợp lệ thì: (A AND B), (A OR B), (A XOR B) là các biểu thức hợp lệ.

Ví dụ: x và ((x AND y) OR z) là các biểu thức hợp lệ; (x AND y là biểu thức không hợp lệ vì thiếu dấu ngoặc đóng; (x AND y) OR z là biểu thức không hợp lệ vì thiếu cặp dấu ngoặc bao ở ngoài cùng.

Trong bài toán này chỉ xét biểu thức hợp lệ mà mỗi biến chỉ xuất hiện một lần.

Yêu cầu: Cho một phương trình có dạng “biểu_ thức_F = P0” trong đó P0 là một số nguyên 32 bit không dấu. Hãy đếm số các bộ giá trị của các biến để khi thay vào biểu_ thức_F, ta thu được một đẳng thức đúng.

Dữ liệu

Vào từ thiết bị vào chuẩn:

• Dòng đầu tiên ghi số nguyên dương K là số lượng bộ dữ liệu.
• Tiếp đến là K dòng, mỗi dòng (tương ứng với một bộ dữ liệu) chứa một xâu có dạng “biểu_thức_F = P0” trong đó biểu_thức_F là một biểu thức hợp lệ.

Kết quả

Ghi ra thiết bị ra chuẩn gồm K dòng, mỗi dòng ghi một số nguyên là phần dư của phép chia số lượng các bộ giá trị để phương trình đúng cho 1000000009 (10^9 + 9) tương ứng với bộ dữ liệu trong file dữ liệu vào.

• Subtask 1 (15/70 điểm): Giả thiết là biểu thức chỉ chứa phép OR, số lượng biến không vượt quá 8 và 0 ≤ P0 < 8
• Subtask 2 (20/70 điểm): Giả thiết là biểu thức chỉ chứa phép OR, số lượng biến không vượt quá 26 và 0 ≤ P0 < 8.
• Subtask 3 (15/70 điểm): Giả thiết là số lượng biến không vượt quá 26 và biểu thức chỉ chứa toàn phép AND hoặc biểu thức chỉ chứa toàn phép XOR.
• Subtask 4 (20/70 điểm): Giả thiết là số lượng biến không vượt quá 26 và 0 ≤ P0 < 2^32.

Ví dụ:

Dữ liệu
3
(a OR b) = 2
(a OR (b OR c)) = 3
(x XOR y) = 2

Kết quả
3
49
294967260