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
