← 返回题目列表

Codeforces · 758/D

D. 转换能力

中文机器翻译题面 查看原题

Alexander 正在学习如何将十进制数字转换为任何其他数字,但是,他不认识英文字母,因此他只能将任何数字写为十进制数字,这意味着他将写数字 10,而不是字母 A。因此,通过将数字 475 从十进制转换为十六进制,他得到 11311 (475 = 1·162 + 13·161 + 11·160)。亚历山大平静地生活着,直到他试图将数字转换回十进制。

Alexander 记得他处理的数字很少,因此他要求找到最小的十进制数,以便通过将其转换为以 n 为基数的系统,他将得到数字 k。

输入

第一行包含整数 n (2 ≤ n ≤ 109)。第二行包含整数k (0 ≤ k < 1060),保证数字k包含不超过60个符号。第二行中的所有数字都严格小于 n。

Alexander保证答案存在且不超过1018。

数字 k 不包含前导零。

输出

打印数字 x (0 ≤ x ≤ 1018) — 问题的答案。

示例

输入 #1

13
12

输出 #1

12

输入 #2

16
11311

输出 #2

475

输入 #3

20
999

输出 #3

3789

输入#4

17
2016

输出#4

594

注意

在第一个示例中,12 可以通过将两个数字转换为以 13 为基数的系统来获得:12 = 12·130 或 15 = 1·131 + 2·130。