using System.Text;
using static System.Math;
using System.Text.RegularExpressions;
using System.Linq;
using System.Collections.Generic;
using System;

class Modulo
{
    private int _MOD;
    private readonly int[] m_facs;
    public int Mul(int a, int b) => (int)(BigMul(a, b) % _MOD);
    public Modulo(int n, int MOD)
    {
        _MOD = MOD;
        m_facs = new int[n + 1];
        m_facs[0] = 1;
        for (int i = 1; i <= n; ++i)
            m_facs[i] = Mul(m_facs[i - 1], i);
    }
    public int Fac(int n) => m_facs[n];
    public int Pow(int a, int m)
    {
        switch (m)
        {
            case 0:
                return 1;
            case 1:
                return a;
            default:
                int p1 = Pow(a, m / 2);
                int p2 = Mul(p1, p1);
                return ((m % 2) == 0) ? p2 : Mul(p2, a);
        }
    }
    public int Div(int a, int b) => Mul(a, Pow(b, _MOD - 2));
}


public class hello
{
    public static int M;
    public static void Main()
    {
        var sb = new StringBuilder();
        while (true)
        {
            var s = Console.ReadLine().Trim();
            if (s == "0:") break;
            s = s.Replace(": ", ":");
            string[] line = s.Split(':');
            M = int.Parse(line[0]);
            var res = conv(line[1]);
            var line2 = res.Split(' ');
            var q = conv2(line2);
            var ans = getAns(q, M);
            if (ans == -1) sb.Append("NG\n");
            else
            {
                var exp = line[1].Replace(" ", "");
                sb.Append(string.Format("{0} = {1} (mod {2})\n", exp, ans, M));
            }
        }
        Console.Write(sb);
    }
    static int getAns(Queue<string> q, int M)
    {
        var md = new Modulo(M, M);
        var st = new Stack<int>();
        while (q.Count() > 0)
        {
            var w = q.Dequeue();
            if (w == "+")
            {
                var t = (st.Pop() + st.Pop()) % M;
                st.Push(t);
            }
            else if (w == "-")
            {
                var t = (-st.Pop() + st.Pop()) % M;
                if (t < 0) t += M;
                st.Push(t);
            }
            else if (w == "*")
            {
                var t = (st.Pop() * st.Pop()) % M;
                st.Push(t);
            }
            else if (w == "/")
            {
                var a1 = st.Pop();
                if (a1 == 0) { return -1; }
                var a2 = st.Pop();
                var t = md.Div(a2, a1);
                st.Push(t);
            }
            else st.Push(int.Parse(w));
        }
        return st.Pop();
    }

    static Queue<string> conv2(string[] line)
    {
        var q = new Queue<string>();
        var st = new Stack<string>();
        foreach (var x in line)
        {
            if (x == "(") st.Push(x);
            else if (x == "+" | x == "-")
            {
                if (st.Count() == 0) st.Push(x);
                else
                {
                    if (st.Peek() == "*" | st.Peek() == "/")
                    {
                        q.Enqueue(st.Pop());
                        if (st.Count() > 0 && (st.Peek() == "+" | st.Peek() == "-")) q.Enqueue(st.Pop());
                        st.Push(x);
                    }
                    else if (st.Peek() == "+" | st.Peek() == "-")
                    {
                        q.Enqueue(st.Pop());
                        st.Push(x);
                    }
                    else if (st.Peek() == "(") { st.Push(x); }
                }
            }
            else if (x == "*" | x == "/")
            {
                if (st.Count() == 0) st.Push(x);
                else
                {
                    if (st.Peek() == "*" | st.Peek() == "/")
                    { q.Enqueue(st.Pop()); st.Push(x); }
                    else if (st.Peek() == "+" | st.Peek() == "-")
                    { st.Push(x); }
                    else if (st.Peek() == "(") { st.Push(x); }
                }
            }
            else if (x == ")")
            {
                while (true)
                {
                    if (st.Peek() == "(") { st.Pop(); break; }
                    else q.Enqueue(st.Pop());
                }
            }
            else if (x == "") continue;
            else q.Enqueue(x);
        }
        while (st.Count() > 0)
        {
            q.Enqueue(st.Pop());
        }
        return q;
    }
    static string conv(string s)
    {
        var res = s.Replace("(", " ( ");
        res = res.Replace(")", " ) ");
        res = res.Replace("+", " + ");
        res = res.Replace("-", " - ");
        res = res.Replace("*", " * ");
        res = res.Replace("/", " / ");
        res = res.Replace(":", "");
        res = Regex.Replace(res, @" +", " ");
        return res;
    }
}



Measured memory_bytes: 43660