MOD = 998244353 def precompute_paren_map(s): stack = [] paren_map = {} for i, c in enumerate(s): if c == '(': stack.append(i) elif c == ')': if stack: opening = stack.pop() paren_map[opening] = i return paren_map def find_comma(s, start, end): depth = 0 for i in range(start, end + 1): c = s[i] if c == '(': depth += 1 elif c == ')': depth -= 1 elif c == ',' and depth == 0: return i return -1 def main(): s = input().strip() K = int(input()) n = len(s) if n == 0: print(0) return paren_map = precompute_paren_map(s) stack = [(0, n-1, None)] processed = [] while stack: start, end, state = stack.pop() if state is None: if start > end: continue if s[start] in '012?': # Digit node if s[start] == '?': dp = [1, 1, 1] else: val = int(s[start]) dp = [0] * 3 dp[val] = 1 processed.append(('digit', dp)) else: # Function call func_start = start while func_start <= end and s[func_start] != '(': func_start += 1 func_name_part = s[start:func_start] possible_funcs = [] for f in ['max', 'mex']: valid = True for k in range(3): c = func_name_part[k] if k < len(func_name_part) else '?' if c != '?' and c != f[k]: valid = False break if valid: possible_funcs.append((f, 1)) opening = func_start if opening not in paren_map: processed.append(('function', [0, 0, 0])) continue closing = paren_map[opening] comma_pos = find_comma(s, opening + 1, closing - 1) if comma_pos == -1: processed.append(('function', [0, 0, 0])) continue stack.append((start, end, ('function', possible_funcs, opening, closing, comma_pos))) stack.append((comma_pos + 1, closing - 1, None)) stack.append((opening + 1, comma_pos - 1, None)) else: # Process function node possible_funcs, opening, closing, comma_pos = state[1:] arg2 = processed.pop()[1] arg1 = processed.pop()[1] dp = [0] * 3 for (f_type, f_count) in possible_funcs: combined = [0] * 3 for a in range(3): for b in range(3): if arg1[a] == 0 or arg2[b] == 0: continue if f_type == 'max': res = max(a, b) else: mex_val = 0 while mex_val == a or mex_val == b: mex_val += 1 res = mex_val if mex_val <= 2 else 2 if res <= 2: combined[res] = (combined[res] + arg1[a] * arg2[b]) % MOD for i in range(3): dp[i] = (dp[i] + f_count * combined[i]) % MOD processed.append(('function', dp)) if not processed: print(0) else: result = processed[0][1][K] % MOD print(result) if __name__ == "__main__": main()