#!/usr/bin/ruby
class Fixnum
	def pow_binary_mod(y)
		x = self
		z = 1
		while y != 0
			while y % 2 == 0
				x = x * x % $N
				#y = y / 2
				y = y >> 1
			end
			y = y - 1
			z = z * x % $N
		end
		z
	end
	def +(n)
		(self.to_f+n.to_f).to_i%$N
	end
	def -(n)
		(self.to_f-n.to_f+$N).to_i%$N
	end
	def *(n)
		(self.to_f*n.to_f).to_i%$N
	end
	def /(n)
		raise if n==0
		self*n.pow_binary_mod($N-2)%$N
	end
end
loop{
	s=gets.chomp
	idx=s.index(':')
	$N=s[0...idx].to_i
	break if $N==0
	exp=s[idx+1..-1].gsub(' ','')
	begin
		puts "#{exp} = #{eval(exp)} (mod #{$N})"
	rescue
		puts :NG
	end
}