### global variables

$invs = []

### inner class

class Fixnum
  def /(n)
    n %= $pn
    raise if $n == 0
    (self * $invs[n]) % $pn
  end
end

### subroutines

def calc_invs()
  $invs = [nil, 1]

  for k0 in (2...$pn)
    m = 1
    k = k0
    n = $pn - 2

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

    $invs[k0] = m
  end
end

### main

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

  calc_invs()

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