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~ là biểu thức hợp lệ;
• ~((x~ AND ~y)~ OR ~z)~ là 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ểuthứcF ~= P_0~" trong đó ~P_0~ 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ểuthứ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~ 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ểuthứcF ~=~ P0" trong đó biểuthứcF là một biểu thức hợp lệ.

Output

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.

Giới hạn

• 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 \leq P_0 < 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 \leq P_0 < 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 \leq P_0 < 2^{32}~.

Sample Input

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

Sample Output

3
49
294967260