#
# DO NOT MODIFY!!!!
# This file is automatically generated by Racc 1.5.1
# from Racc grammar file "".
#

require 'racc/parser.rb'


require 'strscan'

class Parser < Racc::Parser


  # 初期化
  def initialize(input)
    @scanner = StringScanner.new(input)
  end
  
  # 自動的に呼び出される
  def next_token
    return nil if @scanner.eos?
    if (s = @scanner.scan(/[012maex?(),]/))
      [s, s]
    else
      nil
    end
  end

##### State transition tables begin ###

racc_action_table = [
     4,    11,    12,    13,     4,     9,    14,     8,     5,     6,
     7,     8,     5,     6,     7,     4,    15,    16,    18,    20,
   nil,   nil,     8,     5,     6,     7 ]

racc_action_check = [
     0,     4,     4,     4,    16,     1,     9,     0,     0,     0,
     0,    16,    16,    16,    16,    18,    10,    15,    17,    19,
   nil,   nil,    18,    18,    18,    18 ]

racc_action_pointer = [
    -2,     5,   nil,   nil,    -6,   nil,   nil,   nil,   nil,     6,
    13,   nil,   nil,   nil,   nil,    13,     2,    13,    13,    13,
   nil ]

racc_action_default = [
   -11,   -11,    -1,    -2,   -11,    -7,    -8,    -9,   -10,   -11,
   -11,    -4,    -5,    -6,    21,   -11,   -11,   -11,   -11,   -11,
    -3 ]

racc_goto_table = [
     1,    10,   nil,   nil,   nil,   nil,   nil,   nil,   nil,   nil,
   nil,   nil,   nil,   nil,   nil,   nil,    17,   nil,    19 ]

racc_goto_check = [
     1,     4,   nil,   nil,   nil,   nil,   nil,   nil,   nil,   nil,
   nil,   nil,   nil,   nil,   nil,   nil,     1,   nil,     1 ]

racc_goto_pointer = [
   nil,     0,   nil,   nil,    -3 ]

racc_goto_default = [
   nil,   nil,     2,     3,   nil ]

racc_reduce_table = [
  0, 0, :racc_error,
  1, 14, :_reduce_none,
  1, 14, :_reduce_none,
  8, 15, :_reduce_3,
  1, 17, :_reduce_none,
  1, 17, :_reduce_none,
  1, 17, :_reduce_none,
  1, 16, :_reduce_7,
  1, 16, :_reduce_8,
  1, 16, :_reduce_9,
  1, 16, :_reduce_10 ]

racc_reduce_n = 11

racc_shift_n = 21

racc_token_table = {
  false => 0,
  :error => 1,
  "m" => 2,
  "x" => 3,
  "(" => 4,
  "," => 5,
  ")" => 6,
  "a" => 7,
  "e" => 8,
  "?" => 9,
  "0" => 10,
  "1" => 11,
  "2" => 12 }

racc_nt_base = 13

racc_use_result_var = true

Racc_arg = [
  racc_action_table,
  racc_action_check,
  racc_action_default,
  racc_action_pointer,
  racc_goto_table,
  racc_goto_check,
  racc_goto_default,
  racc_goto_pointer,
  racc_nt_base,
  racc_reduce_table,
  racc_token_table,
  racc_shift_n,
  racc_reduce_n,
  racc_use_result_var ]

Racc_token_to_s_table = [
  "$end",
  "error",
  "\"m\"",
  "\"x\"",
  "\"(\"",
  "\",\"",
  "\")\"",
  "\"a\"",
  "\"e\"",
  "\"?\"",
  "\"0\"",
  "\"1\"",
  "\"2\"",
  "$start",
  "expr",
  "m_x",
  "primary",
  "ae_" ]

Racc_debug_parser = false

##### State transition tables end #####

# reduce 0 omitted

# reduce 1 omitted

# reduce 2 omitted

def _reduce_3(val, _values, result)
          result =
            case val[1]
            when 'a'
              max(val[4], val[6])
            when 'e'
              mex(val[4], val[6])
            when '?'
              m_x(val[4], val[6])
            end

    result
end

# reduce 4 omitted

# reduce 5 omitted

# reduce 6 omitted

def _reduce_7(val, _values, result)
 result = [1, 0, 0]
    result
end

def _reduce_8(val, _values, result)
 result = [0, 1, 0]
    result
end

def _reduce_9(val, _values, result)
 result = [0, 0, 1]
    result
end

def _reduce_10(val, _values, result)
 result = [1, 1, 1]
    result
end

def _reduce_none(val, _values, result)
  val[0]
end

end   # class Parser


MOD = 998244353

def max(x, y)
  res = [0, 0, 0]
  (0 .. 2).each do |a|
    (0 .. 2).each do |b|
      c = [a, b].max
      res[c] += x[a] * y[b]
      res[c] %= MOD
    end
  end
  res
end

MEX = [
  [1, 2, 1],
  [2, 0, 0],
  [1, 0, 0]
]

def mex(x, y)
  res = [0, 0, 0]
  (0 .. 2).each do |a|
    (0 .. 2).each do |b|
      c = MEX[a][b]
      res[c] += x[a] * y[b]
      res[c] %= MOD
    end
  end
  res
end

def m_x(x, y)
  res = [0, 0, 0]
  (0 .. 2).each do |a|
    (0 .. 2).each do |b|
      c = MEX[a][b]
      res[c] += x[a] * y[b]
      res[c] %= MOD

      c = [a, b].max
      res[c] += x[a] * y[b]
      res[c] %= MOD
    end
  end
  res
end


S = gets.chomp
K = gets.to_i

parser = Parser.new(S)
res = parser.do_parse

puts res[K]