import scala.annotation.tailrec
object Main extends App {

  import scala.io.StdIn._

  solve
  def solve: Unit = {
    val args = readLine.trim
    if (args(0) == '0') return
    val prime = args.takeWhile(_ != ':').toInt
    val expression = args.dropWhile(_ != ':').tail.filterNot(_ == ' ')
    FiniteFieldExpression.parse(expression, prime) match {
      case Some(f) ⇒ println(s"$expression = $f (mod $prime)")
      case None ⇒ println("NG")
    }
    solve
  }
  object FiniteFieldExpression{
    def parse(str: String, prime: Int): Option[Int] = {
      implicit val p = prime
      implicit val inv = {i: Int ⇒ Some(i).filter(_ != 0).map(i ⇒ exponent(i, prime - 2, prime))}
      str.toList match {
        case low LowPriority Nil ⇒ low
        case _ ⇒ None
      }
    }
    def unapply(arg: List[Char])(implicit prime: Int, inv: Int => Option[Int]): Option[(Option[Int], List[Char])] = {
      arg match {
        case low LowPriority t ⇒ Some(low, t)
        case _ ⇒ None
      }
    }
    private def exponent(base: Int, exp: Int, prime: Int): Int = {
      exp match {
        case 0 ⇒ 1
        case 1 ⇒ base
        case _ ⇒ exponent(base, exp / 2, prime).let{i ⇒ ((i * i) % prime) * exponent(base, exp % 2, prime) % prime}
      }
    }
  }
  object LowPriority{
    def unapply(arg: List[Char])(implicit prime: Int, inv: Int => Option[Int]): Option[(Option[Int], List[Char])] = {
      arg match {
        case normal NormalPriority t ⇒ Some(parseAll(t, normal))
        case _ ⇒ None
      }
    }
    @tailrec
    private def parseAll(arg: List[Char], term: Option[Int])(implicit prime: Int, inv: Int => Option[Int]): (Option[Int], List[Char]) = {
      arg match {
        case '+'::(normal NormalPriority t) ⇒ parseAll(t, normal.flatMap{l ⇒ term.map{r ⇒ (l + r) % prime}})
        case '-'::(normal NormalPriority t) ⇒ parseAll(t, normal.flatMap{l ⇒ term.map{r ⇒ (r + prime - l) % prime}})
        case _ ⇒ (term, arg)
      }
    }
  }
  object NormalPriority{
    def unapply(arg: List[Char])(implicit prime: Int, inv: Int => Option[Int]): Option[(Option[Int], List[Char])] = {
      arg match {
        case left HighPriority t ⇒ Some(parseAll(t, left))
        case _ ⇒ None
      }
    }
    @tailrec
    private def parseAll(arg: List[Char], term: Option[Int])(implicit prime: Int, inv: Int => Option[Int]): (Option[Int], List[Char]) = {
      arg match {
        case '/'::(high HighPriority t) ⇒ parseAll(t, high.flatMap(inv).flatMap{l ⇒ term.map{r ⇒ l * r % prime}})
        case '*'::(high HighPriority t) ⇒ parseAll(t, high.flatMap(l ⇒ term.map{r ⇒ l * r % prime}))
        case _ ⇒ (term, arg)
      }
    }
  }
  object HighPriority{
    def unapply(arg: List[Char])(implicit prime: Int, inv: Int => Option[Int]): Option[(Option[Int], List[Char])] = {
      arg match {
        case  n Number t ⇒ Some(n, t)
        case '('::(sub FiniteFieldExpression ')'::t) ⇒ Some(sub, t)
        case _ ⇒ None
      }
    }
  }
  object Number {
    def unapply(arg: List[Char])(implicit prime: Int, inv: Int => Option[Int]): Option[(Option[Int], List[Char])] = {
      arg.span(_.isDigit) match {
        case (Nil, _) ⇒ None
        case (num, t) ⇒ Some(Some(num.foldLeft(0){case (l, r) ⇒ l * 10 + r.asDigit}), t)
      }
    }
  }

  implicit class Extension[T](value :T){
    @inline
    def let[A](@inline func: T ⇒ A): A = func(value)
    @inline
    def also(@inline func: T ⇒ Unit): T = {func(value); value}
  }
}


Measured memory_bytes: 225440