/* Author: Nguyen Chi Thanh - High School for the Gifted - VNU.HCM (i2528) */ #include <bits/stdc++.h> using namespace std; // #define int long long #define ull unsigned long long #define ld long double #define pii pair<int, int> #define fi first #define se second #define __builtin_popcount __builtin_popcountll #define all(x) (x).begin(), (x).end() #define BIT(x, i) (((x) >> (i)) & 1) #define MASK(x) ((1ll << (x))) #define debug(a, l, r) for (int _i = (l); _i <= (r); ++_i) cout << (a)[_i] << ' '; cout << '\n'; const int MAXN = 2e6 + 5; int numNodes, n; int type[MAXN]; // ?: 0, max: -1, min = 1 int par[MAXN]; vector<int> adj[MAXN]; void init() { string s; cin >> s; n = count(all(s), '?'); // Build binary tree from the expression int ptr = 0; numNodes = 0; vector<int> st; // Stack-based vector st.push_back(0); // Virtual node while (ptr < (int)s.size()) { if (s[ptr] == '?') { numNodes++; type[numNodes] = 0; par[numNodes] = st.back(); ++ptr; continue; } if (s[ptr] == 'm') { char c = s[ptr + 1]; // max or min ++numNodes; type[numNodes] = (c == 'a' ? -1 : 1); par[numNodes] = st.back(); st.push_back(numNodes); ptr += 4; continue; } if (s[ptr] == ')') { assert(!st.empty()); // For safe ++ptr; st.pop_back(); continue; } if (s[ptr] == ',') {++ptr; continue;} } for (int i = 1; i <= numNodes; ++i) { if (par[i]) { adj[i].push_back(par[i]); adj[par[i]].push_back(i); } } } namespace subtask1 { bool check() {return n <= 9;} int curQues = 0; vector<int> val, perm; void dfs(int u, int par = 0) { if ((int)adj[u].size() == 1) { val[u] = perm[curQues]; curQues++; return; } val[u] = -1; for (int v : adj[u]) { if (v == par) continue; dfs(v, u); if (val[u] == -1) val[u] = val[v]; else { if (type[u] == -1) val[u] = max(val[u], val[v]); else if (type[u] == 1) val[u] = min(val[u], val[v]); } } } void solve() { val.resize(numNodes + 5, 0); perm.resize(n); iota(all(perm), 1); set<int> res; do { curQues = 0; dfs(1); res.insert(val[1]); } while (next_permutation(all(perm))); cout << (int)res.size(); } } namespace subtask2 { bool check() {return n <= 16;} vector<vector<int>> dp; // type = 1: min, -1: max int mergeMask(int mask1, int mask2, int type) { int res = 0; // Enumerate the 1's bit for (int s1 = mask1; s1; s1 -= s1 & -s1) { for (int s2 = mask2; s2; s2 -= s2 & -s2) { int i = __builtin_ctz(s1); int j = __builtin_ctz(s2); int new_val = i; if (type == -1) new_val = max(new_val, j); else if (type == 1) new_val = min(new_val, j); res |= MASK(new_val); } } return res; } void dfs(int u, int par = -1) { if ((int)adj[u].size() == 1) { for (int mask = 0; mask < MASK(n); ++mask) dp[u][mask] = mask; return; } vector<int> children; for (int v : adj[u]) if (v != par) children.push_back(v); int left = children[0], right = children[1]; dfs(left, u); dfs(right, u); for (int mask = 0; mask < MASK(n); ++mask) { // cout << u << ' ' << left << ' ' << right << '\n'; int nxtmask = mask; do { dp[u][mask] |= mergeMask(dp[left][nxtmask], dp[right][mask - nxtmask], type[u]); nxtmask = (nxtmask - 1) & mask; } while (nxtmask != mask); } } void solve() { dp.resize(numNodes + 5, vector<int>(MASK(n) + 5, 0)); dfs(1); cout << __builtin_popcount(dp[1][MASK(n) - 1]); } } signed main() { #ifdef NCTHANH freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif // ios_base::sync_with_stdio(0); // cin.tie(nullptr); cout.tie(nullptr); init(); if (subtask1::check()) return subtask1::solve(), 0; if (subtask2::check()) return subtask2::solve(), 0; return 0; }