N진수 곱셈 (HUGE)

이 문제는 N진수 곱셈 (tiny)와 $A$와 $B$의 길이 제한만 다른 문제이다.

$N$진법으로 표현된 두 정수 $A$, $B$를 곱하는 프로그램을 작성하자.

$A$와 $B$를 표현할 때 각 자리의 수는 ASCII 순서대로 배치하는데, $0$은 $33$번에 해당하는 문자인 !로, $1$은 $34$번에 해당하는 문자인 "로, ..., $i$는 $33+i$번에 해당하는 문자로 표현한다. 음수를 표현하는 문자는 ~(ASCII 코드 $126$번)로 $N$이 양수일 때만, 맨 앞 글자에 최대 한 번 나타난다.

각 자리를 표기하기 위한 ASCII 문자 대응표

아래는 앞에서 서술한 대로 수를 표현한 예시이다. 이해를 돕기 위해 각 자리의 숫자를 대괄호를 감싸 표기하였다.

$\[1]\[2]\[5]\_{(10)}=$"#&

$-\[1]\[2]\[16]\_{(27)}=$~"#1

$\[9]\[0]\[12]\_{(-15)}=$*!-

$\[43]\[52]\[44]\[40]\_{(69)}=$LUMI

$N$은 음의 정수일 수 있으며, 음의 정수 진법에 대한 설명은 힌트를 참조한다.

첫 번째 줄에는 진법의 밑 $N(2 \le |N| \le 93)$이 주어진다.

두 번째 줄과 세 번째 줄에는 $N$진법으로 표현된 $A, B$가 각각 주어진다. $A, B$는 $N$진법으로 표현했을 때 $3\\,000\\,000$자를 넘기지 않는다.

$A$ 또는 $B$의 앞에 불필요한 !가 오지 않는다. 또한, ~는 $N$이 양의 정수일 때만 맨 앞에 최대 한 번까지 나올 수 있다. $N$이 음의 정수가 될 수 있음에 유의한다.

$A$와 $B$를 곱한 값을 $N$진법으로 출력한다.

음의 정수 $N$에 대하여 $N$진법은 양의 정수 진법과 똑같이 왼쪽으로 한 자리가 넘어갈 경우, $N$배가 된다. 하지만, 각 자리에 들어가는 숫자의 범위를 $0 \le x \lt -N$으로 한정한다.

예를 들어 $10$진법 $9\\,903$은 $-10$진법으로는 $11\\,903$이 된다.

$11\\,903\_{(-10)} = 1 \times (-10) ^ 4 + 1 \times (-10) ^ 3 + 9 \times (-10) ^ 2 + 0 \times (-10) ^ 1 + 3 \times (-10) ^ 0 = 9\\,903 \_{(10)}$.