Многие криптографические алгоритмы работают только с целыми числами, что не вызывает проблем, если надо выполнить сложение, вычитание или умножение. Однако с делением – так просто.

Допустим, множество чисел, с которыми вы можете работать – это остатки от деления на некоторое натуральное число p.

Такое множество будем обозначать Zp. И Zp = \{0,1,2,…, p-1\}.

Арифметические операции в Zp реализуются как обычно, только результат заменяется его остатком от деления на p. Здесь a, b принадлежат Zp:

(a+b) в Zp = (a+b) mod p

(a-b) в Zp = (a-b) mod p

(a*b) в Zp = (a*b) mod p

С делением ситуация несколько сложней, потому что результат деления a / b тоже должен принадлежать Zp. Поэтому

где b^{-1} – число, обратное к b в Zp. Иными словами (b * b^{-1}) mod p = 1

Причем число b^{-1} существует, если числа p и b – взаимно простые, т.е. НОД(b,p) = 1. Здесь НОД – наибольший общий делитель.

Если же числа p и b – не взаимно простые, то b^{-1} не существует, и вычислить значение выражения не возможно.

Вам необходимо вычислить значение выражения в Zp. Выражение представляет собой строку, содержащую целые десятичные числа и знаки операций «+», «*» и «/». В конце строки символ «=». Других символов в строке нет.

В первой строке – число P. P < 10^{10}.

Во второй строке – строка, содержащая арифметическое выражение, состоящее из целых десятичных чисел и знаков операций «+», «*» и «/». В конце строки символ «=». Других символов в строке нет. Длина строки – не больше 1000 символов. Числа, которые используются в выражении, не больше 10^{10}.

В первой строке – целое десятичное число, равное значению введенного выражения. Либо символ «@», если вычислить значение выражения не удалось.

стандартный ввод	стандартный вывод
7 1=	1
7 1*10+12/5=	4
8 1*10+12/6*4+98+5/7/7/7/7=	@