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 $\text{AND}$, $\text{OR}$, $\text{XOR}$ và các dấu ngoặc. Các toán tử thực hiện theo từng bit (như các toán tử &, |, ^ trong 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.

Yêu cầu: Cho một phương trình có dạng "$F=P_0$" trong đó $F$ là một biểu thức hợp lệ và $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 (chỉ xét các biến có mặt trong $F$, mỗi biến nhận một giá trị trong đoạn $[0,2^{32}-1]$) để khi thay vào biểu thức $F$, 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 "$F=P_0$" trong đó $F$ là một biểu thức hợp lệ.

Trong biểu thức, mỗi toán tử được viết bằng chữ in hoa (AND, OR, XOR) và có đúng một dấu cách ở mỗi bên; dấu ngoặc viết liền với biến hoặc dấu ngoặc bên cạnh; dấu = có đúng một dấu cách ở mỗi bên.

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 các bộ dữ liệu theo thứ tự trong dữ liệu vào.

Ràng buộc

• $1\le K\le 1000$.
• Số lượng biến trong mỗi biểu thức là $n$ với $1\le n\le 26$; các biến là các chữ cái in thường đôi một khác nhau.
• $0\le P_0<2^{32}$.

Subtasks

• Subtask 1 ($15$ điểm): biểu thức chỉ chứa phép $\text{OR}$, $n\le 8$ và $0\le P_0<8$.
• Subtask 2 ($20$ điểm): biểu thức chỉ chứa phép $\text{OR}$, $n\le 26$ và $0\le P_0<8$.
• Subtask 3 ($15$ điểm): $n\le 26$ và mỗi biểu thức chỉ chứa toàn phép $\text{AND}$ hoặc chỉ chứa toàn phép $\text{XOR}$.
• Subtask 4 ($20$ điểm): $n\le 26$ và $0\le P_0<2^{32}$.

Biểu thức chỉ gồm một biến (không có toán tử) thỏa mãn điều kiện về phép toán của mọi subtask.

Ví dụ