#pragma GCC optimize("O3")

#include "bits/stdc++.h"
// Custom Header {{{
#define ALL(x) x.begin(), x.end()
using namespace std;
using i64 = long long;
using pii = pair<i64, i64>;
template<class A, class B>inline bool chmax(A &a, const B &b){return b>a ? a=b,1 : 0;}
template<class A, class B>inline bool chmin(A &a, const B &b){return b<a ? a=b,1 : 0;}
constexpr int INF  = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;
// }}}

class modint { // {{{
private:
    using i64 = long long;
    i64 n;
public:
    static int MOD;
    inline modint(i64 n_ = 0) : n((n_ < MOD) ? n_ : n_ % MOD) {}
    inline modint operator~() const { return pow(n, MOD-2); }
    inline modint& operator+=(modint o) { n = (n + o.n) % MOD; return *this; }
    inline modint& operator-=(modint o) { n = (n - o.n + MOD) % MOD; return *this; }
    inline modint& operator*=(modint o) { n = (n * o.n) % MOD; return *this; }
    inline modint& operator/=(modint o) { n = (n * (~o).n) % MOD; return *this; }
    inline bool operator==(modint o) const { return n == o.n; }
    inline bool operator!=(modint o) const { return !(*this == o); }
    template<class Int> explicit inline operator Int() const { return n; }
    friend ostream& operator<<(ostream &os, modint o) { os << o.n; return os; }
    friend istream& operator>>(istream &is, modint &o) { is >> o.n; return is; }
    static modint pow(i64 n, i64 p) {
        i64 ret = 1;
        for(; p > 0; p >>= 1) {
            if (p & 1) ret = (ret * n) % MOD;
            n = (n * n) % MOD;
        }
        return ret;
    }
};
int modint::MOD = int(1e9) + 7;
modint operator+(modint a, modint b) { return modint(a) += b; }
modint operator-(modint a, modint b) { return modint(a) -= b; }
modint operator*(modint a, modint b) { return modint(a) *= b; }
modint operator/(modint a, modint b) { return modint(a) /= b; }
//}}}

inline vector<string> convertToReversePolishNotation(const vector<string> &infixNotation) // {{{
{
    static const auto rank = [](char c) {
        switch(c) {
        case '+': case '-': return 1;
        case '*': case '/': case '%': return 2;
        default: return 0;
        }
    };

    vector<string> ret;
    stack<string> st;

    for (const auto &e : infixNotation) {
        const char c = e[0];
        if (isdigit(c)) {
            ret.emplace_back(e);
        }
        else if (c == '(') {
            st.emplace(e);
        }
        else if (c == ')') {
            while(st.top()[0] != '(') {
                ret.emplace_back(move(st.top()));
                st.pop();
            }
            st.pop();
        }
        else {
            while (!st.empty() && rank(c) <= rank(st.top()[0])) {
                ret.emplace_back(move(st.top()));
                st.pop();
            }
            st.emplace(e);
        }
    }

    while(!st.empty()) {
        ret.emplace_back(st.top()); st.pop();
    }

    return ret;
} // }}}

inline vector<string> exprTokens(const string &expr) // {{{
{
    vector<string> ret;
    string buf;

    const auto store = [&ret](string &s) {
        if (!s.empty()) { ret.emplace_back(move(s)); s.clear(); }
    };

    for (char c : expr) {
        if (isspace(c)) store(buf);
        else if (isdigit(c)) buf += c;
        else store(buf), ret.emplace_back(string() + c);
    }
    store(buf);

    return ret;
} // }}}

signed main()
{
    char buf[100010];
    int mod;

    while(scanf("%d:", &mod), mod != 0) {
        fgets(buf, sizeof(buf), stdin);
        const auto tokens = exprTokens(buf);
        const auto rpn = convertToReversePolishNotation(tokens);

        modint::MOD = mod;
        stack<modint> st;

        for (const auto &e: rpn) {
            if (isdigit(e[0])) {
                st.push(stoi(e));
            } else {
                const modint b = st.top(); st.pop();
                const modint a = st.top(); st.pop();
                switch(e[0]) {
                case '+': st.push(a + b); break;
                case '-': st.push(a - b); break;
                case '*': st.push(a * b); break;
                case '/':
                          if (b == 0) { puts("NG"); goto UKUNIKIA; }
                          else st.push(a / b);
                }
            }
        }

        for (const auto &e : tokens) printf("%s", e.c_str());

        printf(" = %d (mod %d)\n", int(st.top()), mod);

UKUNIKIA:;
    }

    return 0;
}

// vim: set foldmethod=marker :



Measured memory_bytes: 4828