/Biểu thức logic

              #include <iostream>
        #include <string>
        #include <stack>
        using namespace std;
        
        #define LIM 1000000009
        
        class Node {
        public:
          Node* left;
          Node* right;
          char data;
        
          Node(char data) {
            left = nullptr;
            right = nullptr;
            this->data = data;
          }
        };
        
        string getNum(string s) {
          string res = "";
          string a = "";
          int len = s.length();
        
          long long num = 0ll;
        
          int i = len - 1;
        
          while (s[i] != ' ') a += s[i--];
        
          for (int i = a.length() - 1; i >= 0; i--) {
            num = num * 10ll + (a[i] - '0');
          }
        
          while (num > 0) {
            res = (char)(num % 2 + '0') + res;
            num /= 2;
          }
          
          while (res.length() < 32) res = '0' + res;
        
          return res;
        }
        
        // Chuyển tất cả thành kí tự
        string encode(string s) {
          string res = "";
          int len = s.length();
        
          for (int i = 0; i < len; i++) {
            if (s[i] == ' ' && s[i + 1] == '=') break;
        
            if ((s[i] >= 'a' && s[i] <= 'z') || s[i] == ' '
              || s[i] == '(' || s[i] == ')') res += s[i];
            else {
              if (s[i] == 'A') { // AND
                res += '&'; 
                i += 2;
              }
              else if (s[i] == 'O') { // OR
                res += '|'; 
                i++;
              }
              else if (s[i] == 'X') { // XOR
                res += '^';
                i += 2;
              }
            }
          }
        
          return res;
        }
        
        // Chuyển xâu theo format: phần tử 1 - phần tử 2 - toán tử
        string transform(string s) { 
          string res = "";
          s = '(' + s + ')';
          int len = s.length();
        
          stack<char> iDex;
          
          for (int i = 0; i < len; i++) {
            if (s[i] == ' ') continue;
        
            if (s[i] == '(') iDex.push(s[i]);
            else if (s[i] >= 'a' && s[i] <= 'z') res += s[i];
            else if (s[i] == ')') {
              while (true) {
                char ch = iDex.top();
                iDex.pop();
                if (ch == '(') break;
                res += ch;
              }
            }
            else {
              while (!iDex.empty() && iDex.top() != '(') {
                res = res + iDex.top();
                iDex.pop();
              }
              iDex.push(s[i]);
            }
          }
        
          return res;
        }
        
        Node* builtBinaryTree(string s) {
          int len = s.length();
        
          stack<Node*> iDex;
          for (int i = 0; i < len; i++) {
            Node* a = new Node(s[i]);
            if (s[i] < 'a' || s[i] > 'z') {
              a->right = iDex.top();
              iDex.pop();
              a->left = iDex.top();
              iDex.pop();
            }
            iDex.push(a);
          }
        
          return iDex.top();
        }
        
        #define f(x,y) dfs(a->left, x) * dfs(a->right, y) % LIM
        
        long long dfs(Node* a, int n) {
          if (a->data >= 'a' && a->data <= 'z') return 1ll;
        
          if (a->data == '&') 
            return n ? f(1, 1) : ((f(1, 0) + f(0, 1)) % LIM + f(0, 0)) % LIM;
          else if (a->data == '|') 
            return n ? ((f(1, 0) + f(0, 1)) % LIM + f(1, 1)) % LIM : f(0, 0);
          //else if (a->data == '^') 
          return n ? (f(1, 0) + f(0, 1)) % LIM : (f(0, 0) + f(1, 1)) % LIM;
        }
        
        int main() {
          int k;
          cin >> k;
          cin.ignore();
        
          while (k--) {
            string s;
            getline(cin, s);
            
            string num = getNum(s);
        
            s = encode(s);
            s = transform(s);
        
            Node* root = builtBinaryTree(s);
        
            int len = num.length();
        
            long long ans = 1;
        
            for (int i = 0; i < len; i++) {
              ans = (ans * dfs(root, num[i] - '0')) % LIM;
            }
        
            cout << ans % LIM << endl;
          }
          return 0;
        }