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 \text{ AND } y)~, ~(x \text{ OR } y)~, ~(x \text{ 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 \text{ AND } B)~, ~(A \text{ OR } B)~, ~(A \text{ XOR } B)~ là các biểu thức hợp lệ.

Ví dụ: ~x \text{ và } ((x \text{ AND } y) \text{ OR } z)~ là các biểu thức hợp lệ; ~(x \text{ AND } y \text{ AND } z)~ là biểu thức không hợp lệ vì thiếu dấu ngoặc đóng; ~(x \text{ AND } y) \text{ 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ứcF = 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ứcF, ta thu được một đẳng thức đúng.

Input

• 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~ nhóm dòng, mỗi nhóm (tương ứng với một bộ dữ liệu) chứa một xâu có dạng "biểu thứcF = P0" trong đó biểu thứcF là một biểu thức hợp lệ.

Output

• Ghi ra kết quả chuẩn ~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.

Sample Input 1

3
(a OR b) = 2
(a OR (b OR c)) = 3
(x XOR y) = 2

Sample Output 1

3
49
294967260

Subtasks

• Subtask 1 (15 điểm): Giải 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 \le P0 < 8~.
• Subtask 2 (20 điểm): Giải 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 \le P0 < 8~.
• Subtask 3 (15 điểm): Giải 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 toàn bộ thức chỉ chứa toàn phép XOR.
• Subtask 4 (20 điểm): Giải thiết là số lượng biến không vượt quá 26 và ~0 \le P0 < 2^{32}~.