### global variables

$invs = []

$buffer = nil
$bpt = 0

$pn = 0

### subroutines

def calc_invs(pn)
  $invs = [0]

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

def expression()
  ret = term()
  return nil if ret.nil?

  while true
    case $buffer[$bpt]
    when '+'
      $bpt += 1
      n1 = term()
      return nil if n1.nil?

      ret = (ret + n1) % $pn
    when '-'
      $bpt += 1
      n1 = term()
      return nil if n1.nil?

      ret = (ret + $pn - n1) % $pn
    else
      return ret
    end
  end
end

def term()
  ret = factor()
  return nil if ret.nil?

  while true
    case $buffer[$bpt]
    when '*'
      $bpt += 1
      n1 = factor()
      return nil if n1.nil?

      ret = (ret * n1) % $pn
    when '/'
      $bpt += 1
      n1 = factor()
      return nil if n1.nil? || n1 == 0

      ret = (ret * $invs[n1]) % $pn
    else
      return ret
    end
  end
end

def factor()
  if $buffer[$bpt] == '('
    $bpt += 1
    ret = expression()
    return nil if $buffer[$bpt] != ')'
    $bpt += 1
    return ret
  end

  ret = 0
  k = $buffer[$bpt]
  while ! k.nil? && k >= '0' && k <= '9'
    ret = ret * 10 + (k.ord - '0'.ord)
    $bpt += 1
    k = $buffer[$bpt]
  end

  ret
end

### main

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

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

  calc_invs($pn)
  #p [$pn, $buffer]
  #p $invs

  $bpt = 0
  ans = expression()

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