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。