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

require 'racc/parser.rb'


require 'strscan'

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

class Parser < Racc::Parser

module_eval(<<'...end yc1677.rb.y/module_eval...', 'yc1677.rb.y', 79)

  # 初期化
  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

...end yc1677.rb.y/module_eval...
##### State transition tables begin ###

racc_action_table = [
     2,     5,     6,     7,     2,     2,     3,    15,    12,    13,
    14,    15,    12,    13,    14,     8,     9,    10,    18,    20 ]

racc_action_check = [
    10,     2,     2,     2,    18,     0,     1,    10,    10,    10,
    10,    18,    18,    18,    18,     3,     4,     9,    11,    19 ]

racc_action_pointer = [
     3,     6,    -6,    15,    13,   nil,   nil,   nil,   nil,    13,
    -2,    13,   nil,   nil,   nil,   nil,   nil,   nil,     2,    13,
   nil ]

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

racc_goto_table = [
    11,     1,     4,   nil,   nil,   nil,   nil,   nil,    19 ]

racc_goto_check = [
     3,     1,     2,   nil,   nil,   nil,   nil,   nil,     3 ]

racc_goto_pointer = [
   nil,     1,     0,   -10,   nil ]

racc_goto_default = [
   nil,    16,   nil,   nil,    17 ]

racc_reduce_table = [
  0, 0, :racc_error,
  8, 14, :_reduce_1,
  1, 15, :_reduce_none,
  1, 15, :_reduce_none,
  1, 15, :_reduce_none,
  1, 17, :_reduce_5,
  1, 17, :_reduce_6,
  1, 17, :_reduce_7,
  1, 17, :_reduce_8,
  1, 16, :_reduce_none,
  1, 16, :_reduce_none ]

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",
  "m_x",
  "op",
  "expr",
  "primary" ]

Racc_debug_parser = false

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

# reduce 0 omitted

module_eval(<<'.,.,', 'yc1677.rb.y', 5)
  def _reduce_1(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 2 omitted

# reduce 3 omitted

# reduce 4 omitted

module_eval(<<'.,.,', 'yc1677.rb.y', 18)
  def _reduce_5(val, _values, result)
     result = [1, 0, 0]
    result
  end
.,.,

module_eval(<<'.,.,', 'yc1677.rb.y', 19)
  def _reduce_6(val, _values, result)
     result = [0, 1, 0]
    result
  end
.,.,

module_eval(<<'.,.,', 'yc1677.rb.y', 20)
  def _reduce_7(val, _values, result)
     result = [0, 0, 1]
    result
  end
.,.,

module_eval(<<'.,.,', 'yc1677.rb.y', 21)
  def _reduce_8(val, _values, result)
     result = [1, 1, 1]
    result
  end
.,.,

# reduce 9 omitted

# reduce 10 omitted

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

end   # class Parser


S = gets.chomp
K = gets.to_i

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

puts res[K]