### constant

PRI = {'+' => 0, '-' => 0, '*' => 1, '/' => 1}

### subroutines

def get_invs(pn)
  invs = [nil]

  for i in (1...pn)
    for j in (1...pn)
      if (i * j) % pn == 1
        invs[i] = j
        break
      end
    end
  end

  invs
end

def exp2rpn(exp)
  rpn = []
  stack = []
  bl = 0
  prev_int = false

  for i in (0...exp.length)
    ch = exp[i]

    case ch
    when '0'..'9'
      k = ch.to_i
      if prev_int
        k = rpn.pop * 10 + k
      end
      rpn << k
      prev_int = true
    when '('
      bl += 2
      prev_int = false
    when ')'
      bl -= 2
      prev_int = false
    else
      pri = PRI[ch] + bl
      while ! stack.empty? && pri <= stack.last[1]
        rpn << stack.pop[0]
      end
      stack << [ch, pri]
      prev_int = false
    end
  end

  while ! stack.empty?
    op, pri = stack.pop
    rpn << op
  end

  rpn
end

def calc_rpn(rpn, pn)
  stack = []

  for op in rpn
    if op.is_a? Integer
      stack << op
      next
    end

    n2 = stack.pop
    n1 = stack.pop
    n0 = 0

    case op
    when '+'
      n0 = (n1 + n2) % pn
    when '-'
      n0 = (n1 + pn - n2) % pn
    when '*'
      n0 = (n1 * n2) % pn
    when '/'
      return nil if n2 == 0
      n0 = (n1 * $invs[n2]) % pn
    end

    stack << n0
  end

  stack.last
end

### main

while true
  line = gets.strip
  break if line == '0:'

  pnstr, exp = line.split(/:\s+/)
  pn = pnstr.to_i
  exp.delete!(' ')

  $invs = get_invs(pn)
  #p [pn, exp]
  #p $invs

  rpn = exp2rpn(exp)
  #p rpn

  ans = calc_rpn(rpn, pn)

  if ans.nil?
    puts 'NG'
  else
    puts "#{exp} = #{ans} (mod #{pn})"
  end
end