Biểu thức logic

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$ và $((x\text{AND}y)\text{OR}z)$ là các biểu thức hợp lệ; $(x\text{AND}y$ 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.

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ểuthứcF, ta thu được một đẳng thức đúng.

Dữ liệu vào

• 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ểuthứcF là một biểu thức hợp lệ.

Dữ liệu ra

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.

Ràng buộc

• Subtask 1 (15 điểm): 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): 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): 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 điểm): Số lượng biến không vượt quá $26$ và $0\le P0<2^{32}$.

Ví dụ