Problem:


有限体電卓

0以外のすべての実数の逆数は実数になりますが、整数の逆数が整数になるとは限りません。Ｃ言語などで 3.0/2.0*2.0 = 3.0 なのに 3/2*2 = 2 になってしまうのはこのためです。ですが、素数で割った余りが等しい整数を同じものとみなすと、0以外のすべての整数が逆数をもつようにできます。

整数 x と y を p で割った余りが等しいとき、x &equiv; y (mod p) と書きます。p が素数のとき、このような x と y を同じものとみなすなら、すべての整数 n は0から p&minus;1 までのどれかの整数 x に対して x &equiv; n (mod p) となるので、けっきょく { 0, 1, 2, ..., p&minus;1 } という集合だけからなる世界を考えればよいことがわかります。

この世界での加減乗除は以下のようになります。

 加算 x+y の値は、x+y &equiv; z (mod p) となる 0 から p&minus;1 までの数 z になります。

 減算 x&minus;yの値は、y+m &equiv; 0 (mod p) となる 0 から p&minus;1 までの数 m（これが  y に相当します）について、x&minus;y &equiv; x + m (mod p) となることから得られます。たとえば、p = 5のとき、4+1 &equiv; 0 (mod 5) となります。このとき、2&minus;4 &equiv; 2+1 &equiv; 3 (mod 5) より、2&minus;4の値は3になります。

 乗算 x*y の値は、x*y &equiv; z (mod p) となる 0 から p&minus;1 までの数 z になります。

 除算 x/y の値は、y*d &equiv; 1 (mod p)となる 0 から p&minus;1 までの数 d （これがyの逆数になります）について、x/y &equiv; x*d (mod p) となることから得られます。たとえば、p = 5 のとき、2*3 ≡ 1 (mod 5) より 3 は 2 の逆数になります。このとき、1/2 ≡ 1*3 ≡ 3 (mod 5) より、1/2 の値は 3 になります。

このようにして加減乗除の四則演算がすべて0からp&minus;1の範囲に収まります。このとき、集合 { 0,1,...,p&minus;1 } を p の有限体といいます。この有限体の中で、加減乗除、0 から p&minus;1 までの数、カッコを使って 算術式を構成することができます。

p の有限体の 0 以外のすべての要素が逆数をもつことは、フェルマーの小定理と呼ばれる有名な定理 ap&minus;1 &equiv; 1 (mod p) からわかります（ただし、p は素数、a と p は互いに素）。p の有限体のすべての要素 x は p と互いに素なので、この定理から x*xp-2 &equiv; 1 (mod p) となり xp-2 が x の逆数になるからです。

では、素数と式が与えられたときに、その素数の有限体で式を計算する電卓プログラムを作成してください。

入力

入力は複数のデータセットからなる。入力の終わりは0の後にコロンが１つ続くだけの行 0: で示される。各データセットは以下の形式で与えられる。

p:exp

データセットは１行であり、p (2 ≤ p ≤ 46000) は素数、exp は算術式を示す。exp は加減乗除（それぞれ +, -, *, /）とカッコ、0 から p&minus;1 までの数から構成される。演算子、数、カッコなどの前後には1つ以上の空白が現れる可能性がある。exp の長さは 100,000 を超えない。

データセットの数は 1000 を超えない。

出力

データセットごとに、計算結果を出力する。出力形式は以下の通りである。

exp = val (mod p)

val は、p の有限体での算術式 exp の計算結果である。ただし、0 での除算が含まれるときは NG と出力する。また、exp に現れる加減乗除、カッコ、数の前後には空白を空けないこと。ただし、= の前後には空白を一つずつ空ける。また、valと開きカッコの間、modとp の間にも空白を一つずつ空ける。

入力例

5: 2 - 3
17: 1 + 3 * (2 + 3 / 5 * 2) + 7
11: 1 / 8 - 5 - 8 * 2
19: 8 / (2 - 3 * 7)
1153: 10 * 3 / 7 + ( 50 + 81 / 22 ) + 11
0:

出力例

2-3 = 4 (mod 5)
1+3*(2+3/5*2)+7 = 4 (mod 17)
1/8-5-8*2 = 8 (mod 11)
NG
10*3/7+(50+81/22)+11 = 915 (mod 1153)



Sample input:
5: 2 - 3
17: 1 + 3 * (2 + 3 / 5 * 2) + 7
11: 1 / 8 - 5 - 8 * 2
19: 8 / (2 - 3 * 7)
1153: 10 * 3 / 7 + ( 50 + 81 / 22 ) + 11
0:


Sample output:
2-3 = 4 (mod 5)
1+3*(2+3/5*2)+7 = 4 (mod 17)
1/8-5-8*2 = 8 (mod 11)
NG
10*3/7+(50+81/22)+11 = 915 (mod 1153)

Submission status: Wrong Answer

Solution code:
if eval('1') != 1:
 raise Exception("a")
print("b")

Submission status: Time Limit Exceeded

Solution code:
import re

p = 0
class N(int):
    def __add__(self,n):
        return N((int(self) + int(n)) % p)
    def __sub__(self,n):
        return N((int(self) - int(n)) % p)
    def __mul__(self,n):
        return N((int(self) * int(n)) % p)
    def __floordiv__(self,n):
        if not n:
            raise ZeroDivisionError
        return N((int(self)*int(n**(p-2))) % p)

while True:
    s = input()
    p,s = s.split(':')
    p = int(p)
    if not p:
        break
    s = s.replace(' ','')
    try:
        n = eval(re.sub(r'(\d+)',r'N(\1)',s).replace('/','//'))
        print('%s = %s (mod %s)'%(s,n,p))
    except ZeroDivisionError:
        print('NG')

Submission status: Time Limit Exceeded

Solution code:
import re
class c(int):
    global p
    def __add__(self,n):
        return c((int(self)+int(n))%p)
    def __sub__(self,n):
        return c((int(self)-int(n))%p)
    def __mul__(self,n):
        return c((int(self)*int(n))%p)
    def __truediv__(self,n):
        if n==0:raise ZeroDivisionError
        return self*(int(n)**(p-2))%p
  
while 1:
    p,f=input().replace(' ','').split(':')
    p=int(p)
    if p==0:break
    try:print('%s = %s (mod %s)'%(f,eval(re.sub(r'(\d+)',r'c(\1)',f)),p))
    except:
        print('NG')

Submission status: Accepted

Solution code:
def reverse_polish_notation(exp):
    priority = {'+':0,'-':0,'/':1,'*':1}
    exp = deque(exp)
    stack = deque()
    buffer = deque()
    
    while len(exp):
        token = exp.pop()
        if token.isnumeric():
            buffer.append(token)
        elif token == '(':
            while True:
                token = stack.pop()
                if token == ')':
                    break
                buffer.append(token)
        elif token == ')':
            stack.append(token)
        else:
            while len(stack):
                if stack[-1] == ')' or priority[stack[-1]] <= priority[token]:
                    break
                buffer.append(stack.pop())
            stack.append(token)
    
    while len(stack):
        buffer.append(stack.pop())
        
    return buffer    

def power(x, n, p):
    if n == 0:
        return 1
    res = power(x * x % p, n // 2, p)
    if n & 1:
        res = res * x % p
    return res

from collections import deque
def getval(p, exp):
    exp = reverse_polish_notation(exp)
    stack = deque()
    while len(exp):
        token = exp.popleft()
        if token.isnumeric():
            stack.append(int(token))
        else:
            a, b = stack.pop(), stack.pop()
            if token == '+':
                stack.append((a + b) % p)
            elif token == '-':
                stack.append((a - b) % p)
            elif token == '*':
                stack.append((a * b) % p)
            elif token == '/':
                if b == 0:
                    stack.append(float('nan'))
                else:
                    stack.append((a * power(b, p - 2, p)) % p)

    return stack.pop()

import sys
import math
import re
f = sys.stdin


pattern = re.compile('(\d+|\D)')
while True:
    p, exp = f.readline().split(':')
    if p == '0':
        break
    exp = ''.join(exp.split()).strip()
    
    val = getval(int(p), pattern.findall(exp))
    if math.isnan(val):
        print('NG')
    else:
        print('{} = {} (mod {})'.format(exp, val, p))

Submission status: Accepted

Solution code:
import re

p = 0
class N(int):
    def __add__(self,n):
        return N((int(self) + int(n)) % p)
    def __sub__(self,n):
        return N((int(self) - int(n)) % p)
    def __mul__(self,n):
        return N((int(self) * int(n)) % p)
    def __floordiv__(self,n):
        if not n:
            raise ZeroDivisionError
        return self*pow(int(n),p-2,p)

while True:
    s = input()
    p,s = s.split(':')
    p = int(p)
    if not p:
        break
    s = s.replace(' ','')
    try:
        n = eval(re.sub(r'(\d+)',r'N(\1)',s).replace('/','//'))
        print('%s = %s (mod %s)'%(s,n,p))
    except ZeroDivisionError:
        print('NG')

Submission status: Accepted

Solution code:
import re
class c(int):
    global p
    def __add__(self,n):
        return c((int(self)+int(n))%p)
    def __sub__(self,n):
        return c((int(self)-int(n))%p)
    def __mul__(self,n):
        return c((int(self)*int(n))%p)
    def __truediv__(self,n):
        if n==0:raise ZeroDivisionError
        return self*pow(int(n),p-2,p)
  
while 1:
    p,f=input().replace(' ','').split(':')
    p=int(p)
    if p==0:break
    try:print('%s = %s (mod %s)'%(f,eval(re.sub(r'(\d+)',r'c(\1)',f)),p))
    except:print('NG')

Submission status: Accepted

Solution code:
import sys
from string import digits

sys.setrecursionlimit(10**6)
def calc(S, MOD):
    L = len(S)
    S = S + "$"
    ok = 1
    cur = 0
    def expr():
        nonlocal cur
        op = "+"
        res = 0
        while cur < L:
            val = term()
            if op == "+":
                res += val
            else: # '-'
                res -= val
            res %= MOD
            if S[cur] not in "+-":
                break
            op = S[cur]
            cur += 1 # '+' or '-'
        return res % MOD
    def term():
        nonlocal cur, ok
        op = "*"
        res = 1
        while cur < L:
            val = factor()
            if op == "*":
                res *= val
            else: # '/'
                if val == 0:
                    ok = 0
                res *= pow(val, MOD-2, MOD)
            res %= MOD
            if S[cur] not in "*/":
                break
            op = S[cur]
            cur += 1 # '*' or '/'
        return res
    def factor():
        nonlocal cur
        if S[cur] == '(':
            cur += 1 # '('
            val = expr()
            cur += 1 # ')'
            return val
        return number()
    def number():
        nonlocal cur
        val = 0
        while S[cur] in digits:
            val = (10*val + int(S[cur])) % MOD
            cur += 1 # '0123456789'
        return val
    res = expr()
    return res if ok else -1

while 1:
    S = input()
    if S == '0:':
        break
    p, S = S.split(":")
    p = int(p)
    S = S.replace(" ", "")
    res = calc(S, p)
    if res == -1:
        print("NG")
    else:
        print("%s = %d (mod %d)" % (S, res, p))

Submission status: Runtime Error

Solution code:
raise Exception((eval("'a'")))

Submission status: Runtime Error

Solution code:
if eval('1') == 1:
 raise Exception("a")
print("b")