컴퓨터 과학에서 진법(Numeral System)은 수를 표기하고 표현하는 규칙이다.

현대 컴퓨터는 정보를 0과 1로 표현하는 2진법(Binary)을 기본으로 사용하며, 큰 수를 효율적으로 표기하기 위해 8진법(Octal)이나 16진법(Hexadecimal)을 자주 활용한다.

일상생활에서 널리 쓰이는 표기 체계는 10진법(Decimal)이다.

\(B\)진법(기수 \(B\))으로 표현된 수의 각 자리 숫자는 오른쪽(가장 낮은 자리)부터 왼쪽으로 이동할 때마다 자리의 가중치(자릿값)가 \(B^0, B^1, B^2, \dots\) 순으로 증가한다.

길이가 \(k\)인 \(B\)진법 수 \(S = d_{k-1}d_{k-2}\dots d_1d_0\)의 10진수 값 \(V\)는 각 자리의 값과 해당 자릿값을 곱하여 모두 더한 값과 같다.

\[V = \sum_{i=0}^{k-1} d_i \times B^i = d_{k-1} \times B^{k-1} + d_{k-2} \times B^{k-2} + \dots + d_1 \times B^1 + d_0 \times B^0\]

10 이상의 기수를 다룰 때에는 0부터 9까지의 아라비아 숫자만으로 한 자리를 표현할 수 없으므로, 알파벳 대문자를 차례대로 빌려와 숫자로 사용한다.

• A = 10, B = 11, C = 12, ..., Z = 35

예를 들어, 16진수 2AF를 10진수로 변환하는 과정은 다음과 같다.

• F = \(15 \times 16^0 = 15\)
• A = \(10 \times 16^1 = 160\)
• 2 = \(2 \times 16^2 = 512\)
• 최종 합 = \(512 + 160 + 15 = 687\)

\(B\)진법으로 표현된 문자열 \(S\)와 기수 \(B\)가 주어질 때, 이를 10진수로 변환하여 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 \(B\)진법으로 표현된 수 \(S\)와 기수 \(B\)가 공백으로 구분되어 주어진다. (\(2 \le B \le 36\))

\(S\)는 숫자(0 ~ 9)와 알파벳 대문자(A ~ Z)로만 구성되며, \(B\)진법 체계에서 유효한 문자만 주어진다.

변환된 10진수 값은 항상 \(0\) 이상 \(2^{63}-1\) 이하의 정수임이 보장된다.

출력

첫째 줄에 \(B\)진법 수 \(S\)를 10진수로 변환한 결과를 출력한다.

예제 입력 1

2AF 16

예제 출력 1

687

예제 입력 2

110101 2

예제 출력 2

53

예제 입력 3

ZZZZZ 36

예제 출력 3

60466175

예제 입력 4

0 8

예제 출력 4

0

힌트

• 호너의 방법(Horner's Method)을 이용하면 거듭제곱 연산 없이 왼쪽 자리부터 누적하여 효율적으로 계산할 수 있다: result = result * B + digit
• 진법 = 숫자를 표현하는 방법
• 기수(radix) = 그 진법에서 사용하는 숫자의 개수(2, 8, 10, 16 등)
• 진수(base-N number) = 그 진법으로 표현된 숫자