#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <csetjmp>

static int p;
static char s[100001];

static int inv[46000];
static char *e;
static jmp_buf evaljmp;


static int read(void) {
    int ch;
    
    /* skip whitespaces */
    ch = getchar();
    while (isspace(ch)) {
        ch = getchar();
    }
    if (!isdigit(ch)) {
        return -1;
    }
    
    /* read a number */
    p = 0;
    while (isdigit(ch)) {
        p = p * 10 + (ch - '0');
        ch = getchar();
    }
    
    /* read colon */
    while (isspace(ch)) {
        ch = getchar();
    }
    if (ch != ':') {
        return -1;
    }
    ch = getchar();
    
    /* compress input */
    char *ptr = s;
    for (; ch != '\n'; ch = getchar()) {
        if (isspace(ch)) {
            continue;
        }
        *(ptr++) = ch;
    }
    *ptr = '\0';
    
    return p;
}


static int eval_expression(void);


static int eval_factor(void) {
    int lvalue;

    if (isdigit(*e)) {
        lvalue = 0;
        while (isdigit(*e)) {
            lvalue = lvalue * 10 + (*e - '0');
            ++e;
        }
        lvalue %= p;
    }
    else if (*e == '(') {
        ++e;
        lvalue = eval_expression();
        if (*e != ')') {
            longjmp(evaljmp, -1);
        }
        ++e;
    }
    else {
        longjmp(evaljmp, -1);
    }
    
    return lvalue;
}


static int eval_term(void) {
    int lvalue = eval_factor();
    
    for (;;) {
        if (*e == '*') {
            ++e;
            const int rvalue = eval_factor();
            lvalue = (lvalue * rvalue) % p;
        }
        else if (*e == '/') {
            ++e;
            const int rvalue = eval_factor();
            if (rvalue == 0) {
                longjmp(evaljmp, 1);
            }
            lvalue = (lvalue * inv[rvalue]) % p;
        }
        else {
            return lvalue;
        }
    }
}


static int eval_expression(void) {
    int lvalue = eval_term();
    
    for (;;) {
        if (*e == '+') {
            ++e;
            const int rvalue = eval_term();
            lvalue = (lvalue + rvalue) % p;
        }
        else if (*e == '-') {
            ++e;
            const int rvalue = eval_term();
            lvalue = (lvalue + (p - rvalue)) % p;
        }
        else if (*e == '\0' || *e == ')') {
            return lvalue;
        }
        else {
            longjmp(evaljmp, -1);
        }
    }
}


static int eval(void) {
    inv[0] = 0;
    for (int y = 1; y < p; ++y) {
        int y2d = y;
        inv[y] = 1;
        for (int digits = p - 2; digits > 0; digits /= 2) {
            if (digits % 2 == 1) {
                inv[y] = (inv[y] * y2d) % p;
            }
            y2d = (y2d * y2d) % p;
        }
    }

    if (setjmp(evaljmp) == 0) {
        e = s;
        const int result = eval_expression();
        if (*e != '\0') {
            return -1;
        }
        return result;
    } else {
        return -1;
    }
}


int main(int argc, char *argv[]) {
    for (;;) {
        if (read() == 0) {
            break;
        }
        const int result = eval();
        if (result >= 0) {
            printf("%s = %d (mod %d)\n", s, result, p);
        }
        else {
            puts("NG");
        }
    }
    
    return EXIT_SUCCESS;
}



Measured memory_bytes: 2928