#include<bits/stdc++.h>

using namespace std;

typedef pair<string, bool> sb;

int countWays(string expr, bool result, map<sb, int> &memo) {
    if(expr.size() == 0) {
        return 0;
    }
    if(expr.size() == 1) {
        return (expr[0] - '0') == result;
    }

    if(memo.find(sb(expr, result)) != memo.end()) {
        return memo[sb(expr, result)];
    }

    int ways = 0;

    for(int i = 1; i < expr.size(d); i += 2) {
        string left = expr.substr(0, i);
        string right = expr.substr(i + 1, string::npos);

        int leftTrue = countWays(left, true, memo);
        int leftFalse = countWays(left, false, memo);
        int rightTrue = countWays(right, true, memo);
        int rightFalse = countWays(right, false, memo);

        int totalWays = (leftTrue + leftFalse) * (rightFalse + rightTrue);

        int totalTrue = 0;

        switch(expr[i]) {
            case '^':
                totalTrue += leftTrue*rightFalse + leftFalse*rightTrue;
                break;
            case '|':
                totalTrue += leftTrue*rightFalse + leftTrue*rightTrue + leftFalse*rightTrue;
                break;
            case '&':
                totalTrue += leftTrue*rightTrue;
                break;
        }

        if(result) {
            ways += totalTrue;
        } else {
            ways += totalWays - totalTrue;
        }
    }

    return memo[sb(expr, result)] = ways;
}

int countWays(string expr, bool result) {
    map<sb, int> memo;
    return countWays(expr, result, memo);
}

void test0() {
    string expr = "1^0|0|1";
    bool result = false;

    int test = countWays(expr, result);
    int control = 2;

    assert(test == control);
}

void test1() {
    string expr = "0&0&0&1^1|0";
    bool result = true;

    int test = countWays(expr, result);
    int control = 10;

    assert(test == control);
}

int main() {
    test0();
    test1();

    cout << "success" << endl;

    return 0;
}