### inner class

class Fixnum
  def **(n)
    m = 1
    k = self
    while n > 0
      m = (m * k) % $pn if (n & 1) != 0
      k = (k * k) % $pn
      n >>= 1
    end
    m
  end

  def /(n)
    n %= $pn
    raise if n == 0
    (self * (n ** ($pn - 2))) % $pn
  end
end

### main

while true
  pnstr, exp = gets.strip.gsub(' ', '').split(':')
  $pn = pnstr.to_i
  break if $pn == 0

  begin
    ans = eval(exp) % $pn
    puts "#{exp} = #{ans} (mod #{$pn})"
  rescue
    puts 'NG'
  end
end