고장난 계산기

진우는 정수론 기말고사 시험에서 사용할 계산기를 구매했다. 이 계산기는 음이 아닌 정수의 덧셈과 곱셈, 그리고 괄호로 연산 순서를 지정하는 기능을 지원한다. 아래 BNF에서 <expr>에 해당하는 형태의 수식을 계산하고, 그 값을 $P$로 나눈 나머지를 구할 수 있다.

• <expr> ::= <term> | <expr> + <term>
• <term> ::= <factor> | <term> * <factor>
• <factor> ::= <number> | ( <expr> )
• <number> ::= <digit> | <number> <digit>
• <digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

보통의 계산기는 곱셈을 덧셈보다 먼저 계산하고, 괄호 안의 연산을 괄호 밖의 연산보다 먼저 계산한다. 우선순위가 같은 연산은 왼쪽부터 계산한다. 하지만 이 계산기는 고장났다. 덧셈과 곱셈의 우선순위를 같게 취급하며, 우선순위가 같은 연산을 임의의 순서로 계산한다. 예를 들어 (2+2*2)+3은 괄호 안의 덧셈을 먼저 계산하면 (4*2)+3 = 11이 되고, 곱셈을 먼저 계산하면 (2+4)+3 = 9가 된다.

진우는 시험 10분 전에 계산기가 고장났다는 사실을 알아챘다. 급한 대로 여는 괄호 (와 닫는 괄호 )를 적당히 추가해서, 고장난 계산기로도 항상 의도한 대로 계산되도록 수식을 입력하려 한다. 진우가 계산하려던 수식 $S$가 주어질 때, 고장난 계산기가 항상 진우의 의도한 결과를 내도록 괄호를 삽입해 수식을 변환하는 프로그램을 작성하라.

첫 번째 줄에 수식의 길이 $N$과 법 $P$가 공백을 사이에 두고 주어진다.

두 번째 줄에 진우가 계산하려던 수식 $S$가 주어진다.

첫 번째 줄에 변환된 수식 $T$의 길이 $M$을 출력한다.

두 번째 줄에 변환된 수식 $T$를 출력한다.

• $1\le N\le 50$
• $2\le P\le 20$
• $1\le M\le 100$
• $S$와 $T$는 숫자와 +, *, (, )로 이루어진 문자열이다.
• $S$는 위 BNF에서 <expr>에 해당하는 형태의 수식이다.
• $T$는 $S$에 여는 괄호와 닫는 괄호만 삽입한 문자열이다.