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)}$.