import Control.Monad
import Control.Applicative
import Control.Exception
import Text.Parsec hiding ((<|>))

solve p exp = fromRight $ parse expr "" exp
 where 
  fromRight (Right x) = x
  chr x y = char x *> pure y
  pf f x y = (x `f` y) `mod` p
  add = chr '+' $ pf (+)
  sub = chr '-' $ pf (-)
  mul = chr '*' $ pf (*)
  pdiv x 0 = throw DivideByZero
  pdiv x y = x * y^(p-2) `mod` p
  div = chr '/' pdiv
  number = read <$> many1 digit
  par = between (char '(') (char ')')
  expr = chainl1 term (add <|> sub)
  term = chainl1 factor (mul <|> div)
  factor = number <|> par expr

main = do
 l <- getLine
 let (p,_:exp) = break (==':') l
 let p' = read p
 when (p' /= 0) $ do 
  let exp' = filter (/=' ') exp
  let s = exp' ++ " = " ++ show (solve p' exp') ++ " (mod " ++ p ++ ")"
  catch (putStrLn s)
   $ \DivideByZero -> putStrLn "NG"
  main