Alexander is learning how to convert numbers from the decimal system to any other, however, he doesn't know English letters, so he writes any number only as a decimal number, it means that instead of the letter A he will write the number 10. Thus, by converting the number 475 from decimal to hexadecimal system, he gets 11311 (475 = 1·16^2 + 13·16^1 + 11·16^0). Alexander lived calmly until he tried to convert the number back to the decimal number system.

Alexander remembers that he worked with little numbers so he asks to find the minimum decimal number so that by converting it to the system with the base n he will get the number k.


-----Input-----

The first line contains the integer n (2 ≤ n ≤ 10^9). The second line contains the integer k (0 ≤ k < 10^60), it is guaranteed that the number k contains no more than 60 symbols. All digits in the second line are strictly less than n.

Alexander guarantees that the answer exists and does not exceed 10^18.

The number k doesn't contain leading zeros.


-----Output-----

Print the number x (0 ≤ x ≤ 10^18) — the answer to the problem.


-----Examples-----
Input
13
12

Output
12
Input
16
11311

Output
475
Input
20
999

Output
3789
Input
17
2016

Output
594


-----Note-----

In the first example 12 could be obtained by converting two numbers to the system with base 13: 12 = 12·13^0 or 15 = 1·13^1 + 2·13^0.

Difficulty: HARD
Tags: Constructive algorithms

String algorithms

Greedy algorithms

Dynamic programming

Mathematics
Skill types: Dynamic programming

Greedy algorithms

Starter code:

Solutions:
n = input()
l = len(n)
(n, k) = (int(n), input())
(K, d, ans) = ([], 1, 0)
while k:
	ll = l
	while ll > len(k) or int(k[-ll:]) >= n or k[-ll] == '0':
		if ll > 1:
			ll -= 1
		else:
			break
	K += [int(k[-ll:])]
	k = k[:-ll]
for x in K:
	ans += x * d
	d = d * n
print(ans)


base = int(input())
num = input()
a = 0
n = ''
l = []
sk = len(str(base))
while num:
	nn = num[-sk:]
	j = 0
	while int(nn) >= base:
		j += 1
		nn = nn[1:]
	while len(nn) > 1 and nn[0] == '0':
		j += 1
		nn = nn[1:]
	l.append(int(nn))
	num = num[:-sk + j]
p = 1
for n in l:
	a += p * n
	p *= base
print(a)


n = int(input())
m = int(input())
ln = len(str(n))
ans = 0
i = 0
while m != 0:
	dgt = m % 10 ** ln
	if dgt < n and len(str(dgt)) == ln:
		ans += dgt * n ** i
		i += 1
		m = m // 10 ** ln
		ln = len(str(n))
	else:
		ln -= 1
print(ans)


import math
N = int(input())
S = str(input())
K = len(S)
dp = []
ans = math.inf
for i in range(66):
	dp.append([])
	for j in range(66):
		dp[i].append(-1)
dp[K][0] = 0

def comp(x, y, v):
	if dp[x][y] == -1 or dp[x][y] > v:
		dp[x][y] = v
for i in range(K - 1, -1, -1):
	for j in range(1, K + 1):
		cur = 0
		if S[i] == '0':
			dp[i][j] = dp[i + 1][j - 1]
			continue
		for k in range(i, K):
			cur = cur * 10 + int(S[k])
			if cur >= N:
				break
			if dp[k + 1][j - 1] != -1:
				comp(i, j, cur * N ** (j - 1) + dp[k + 1][j - 1])
for i in range(1, K + 1):
	if dp[0][i] != -1:
		ans = min(ans, dp[0][i])
print(ans)


n = int(input())
k = input()
dp = [10 ** 18] * len(k) + [0]
st = [100] * len(k) + [-1]
for l in range(len(k) - 1, -1, -1):
	for r in range(l + 1, len(k) + 1):
		if int(k[l:r]) >= n or (k[l] == '0' and r > l + 1):
			break
		(dp[l], st[l]) = (min(dp[l], dp[r] + int(k[l:r]) * n ** (st[r] + 1)), min(st[l], st[r] + 1))
print(dp[0])


import sys

def debug(*args, **kwargs):
	print(*args, **kwargs, file=sys.stderr)
n = int(input())
s = input()
h = len(s)
k = int(s)
dec = [0] * (h + 1)
if k < n:
	print(k)
else:
	dec[0] = 0
	for i in range(1, h + 1):
		dec[i] = dec[i - 1] * n + int(s[i - 1])
		for j in range(2, i + 1):
			if s[i - j] != '0':
				lastdig = int(s[i - j:i])
				if lastdig >= n:
					break
				newdec = dec[i - j] * n + lastdig
				dec[i] = min(dec[i], newdec)
	print(dec[h])


import sys
dpp = [[0] * 100 for i in range(100)]
used = [[0] * 100 for i in range(100)]
inf = 1 << 300

def dp(pos, i):
	if pos >= k:
		return '0'
	hh = n ** i
	if pos == k - 1:
		return str(int(s[pos]) * hh)
	if used[pos][i]:
		return dpp[pos][i]
	used[pos][i] = 1
	temp = s[pos]
	ans = inf
	best = '999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999'
	ctr = pos
	while int(temp) < n:
		if temp[0] == '0' and len(temp) > 1:
			if ctr == k - 1:
				break
			ctr += 1
			temp = s[ctr] + temp
			continue
		tt = dp(ctr + 1, i + 1)
		gg = str(int(tt) + int(temp) * hh)
		if int(gg) < ans:
			ans = int(gg)
			best = gg
		if ctr == k - 1:
			break
		ctr += 1
		temp = s[ctr] + temp
	dpp[pos][i] = best
	return best
n = int(input())
s = input()[::-1]
k = len(s)
print(int(dp(0, 0)))


n = int(input())
x = input()
l = len(x)
dp = [[1e+18 for i in range(l + 1)] for i in range(l + 1)]
for i in range(l + 1):
	dp[l][i] = 0
for i in range(l - 1, -1, -1):
	sum = 0
	for j in range(i, l):
		sum = sum * 10 + (ord(x[j]) - ord('0'))
		if sum >= n:
			break
		for k in range(l):
			dp[i][k + 1] = min(dp[i][k + 1], dp[j + 1][k] + sum * n ** k)
		if sum == 0:
			break
ans = 10 ** 18
for i in range(l + 1):
	ans = min(ans, dp[0][i])
print(ans)


INF = 100000000000000000000
b = int(input())
s = input()
n = len(s)
dp = [INF for i in range(n + 1)]
dp[0] = 0
for i in range(n):
	if s[i] == '0':
		dp[i + 1] = min(dp[i + 1], dp[i] * b)
		continue
	for j in range(i + 1, n):
		if int(s[i:j]) < b:
			dp[j] = min(dp[j], b * dp[i] + int(s[i:j]))
		else:
			break
	else:
		if int(s[i:]) < b:
			dp[n] = min(dp[n], b * dp[i] + int(s[i:]))
print(dp[n])


def ri():
	return map(int, input().split())
n = int(input())
k = input()
ans = 0
p = 0
while True:
	kk = k[:]
	for i in range(len(kk)):
		if int(kk[i]) == 0 and len(kk[i:]) != 1:
			continue
		if n > int(kk[i:]):
			ans += int(kk[i:]) * n ** p
			p += 1
			if i == 0:
				print(ans)
				exit()
			k = kk[:i]
			break


def convert_base(base, result_number, counter):
	if result_number == '':
		return 0
	else:
		slice_range = 0
		slice_num = 0
		for i in range(len(result_number), 0, -1):
			raw_num = result_number[-i:]
			slice_num = int(raw_num)
			if slice_num < base:
				if raw_num[0] == '0' and len(raw_num) != 1:
					continue
				slice_range = i
				break
		return slice_num * base ** counter + convert_base(base, result_number[:-slice_range], counter + 1)
base_n = int(input())
result_number = input()
print(convert_base(base_n, result_number, 0))


import sys
n = int(sys.stdin.readline())
s = sys.stdin.readline()[:-1]
l = []
m = len(s)
i = m - 1
dp = [0 for x in range(m)]
for i in range(m):
	zero = False
	fzero = -1
	j = i
	while j >= 0:
		if s[j] == '0':
			zero = True
		if int(s[j:i + 1]) < n:
			last = j
			j -= 1
		else:
			break
	if zero:
		while last < i:
			if s[last] == '0':
				last += 1
			else:
				break
		if last == i and s[i] == 0:
			dp[i] = 0
			continue
		else:
			dp[i] = int(s[last:i + 1])
			continue
	else:
		dp[i] = int(s[last:i + 1])
i = m - 1
while i >= 0:
	cur = str(dp[i])
	a = len(cur)
	l.append(cur)
	while a > 0:
		i -= 1
		a -= 1
l.reverse()
k = len(l)
i = 0
res = 0
k -= 1
while k >= 0:
	res += int(l[i]) * n ** k
	k -= 1
	i += 1
print(res)


n = 0
k = ''
mem = [[-1 for xx in range(66)] for yy in range(66)]

def go(ind, po):
	global n
	global k
	global mem
	if ind >= len(k):
		return 0
	if mem[ind][po] != -1:
		return mem[ind][po]
	for i in range(ind, len(k)):
		cur = int(k[ind:i + 1][::-1])
		if cur >= n:
			break
		if k[i] == '0' and i != ind:
			continue
		if mem[ind][po] == -1:
			if go(i + 1, po + 1) != -1:
				mem[ind][po] = cur * pow(n, po) + go(i + 1, po + 1)
		elif go(i + 1, po + 1) != -1:
			mem[ind][po] = min(mem[ind][po], cur * pow(n, po) + go(i + 1, po + 1))
	return mem[ind][po]
n = int(input())
k = input()
k = k[::-1]
print(go(0, 0))


n = input()
s = input()
n = int(n)
t1 = len(s)
k = 1
sum = 0
while t1 > 0:
	m = 0
	for i in range(0, t1):
		w = int(s[i:t1])
		if w < n:
			m = i
			break
	while m < t1 - 1 and s[m] == '0':
		m = m + 1
	sum += k * w
	k *= n
	t1 = m
print(sum)


import sys
k = int(input())
t = input()
n = len(t)
inf = 10 ** 18 + 1
dp = [inf] * (n + 1)
for i in range(n + 1):
	dp[i] = [inf] * (n + 1)
t = t[::-1]
dp[0][0] = 0
for i in range(n + 1):
	for j in range(n + 1):
		if dp[i][j] == inf:
			continue
		cur = 0
		for len in range(0, n):
			if i + len >= n:
				break
			symb = ord(t[i + len]) - ord('0')
			if symb == 0 and len > 0:
				continue
			cur = cur + symb * 10 ** len
			if cur >= k:
				break
			neww = dp[i][j] + cur * k ** j
			dp[i + len + 1][j + 1] = min(dp[i + len + 1][j + 1], neww)
ans = -1
for i in range(1, n + 1):
	if ans == -1 or ans > dp[n][i]:
		ans = dp[n][i]
print(ans)


inf = int(1e+18)
B = int(input())
s = input()
power = []
power.append(1)
LIMIT = 0
dp = []

def value(l, r):
	ans = 0
	for i in range(l, r + 1):
		c = int(s[i]) - int('0')
		ans = ans * 10 + c
	return ans

def min(a, b):
	if a < b:
		return a
	else:
		return b

def f(l, r, i):
	if i >= LIMIT:
		return inf
	if dp[l][r][i] != -1:
		return dp[l][r][i]
	if l == 0:
		return value(l, r) * power[i]
	opt1 = inf
	opt2 = inf
	opt3 = inf
	temp = value(l - 1, r)
	if temp < B:
		opt1 = f(l - 1, r, i)
	if s[l] == '0':
		if l == r:
			opt2 = f(l - 1, r - 1, i + 1)
		dp[l][r][i] = min(opt1, opt2)
		return dp[l][r][i]
	opt3 = f(l - 1, l - 1, i + 1) + value(l, r) * power[i]
	ans = min(opt1, opt2)
	dp[l][r][i] = min(ans, opt3)
	return dp[l][r][i]
for i in range(1, 61):
	power.append(power[i - 1] * B)
	if power[i] > inf:
		LIMIT = i
		break
for i in range(0, 65):
	dp.append([])
	for j in range(0, 65):
		dp[i].append([])
		for k in range(0, 65):
			dp[i][j].append(-1)
l = len(s)
print(f(l - 1, l - 1, 0))


dp = [float('inf') for i in range(100)]
dp[0] = 0
n = int(input())
s = input()
ln = len(s)
s = '.' + s
for i in range(1, ln + 1):
	for j in range(1, i + 1):
		e = s[j:i + 1]
		e = int(e)
		if i - j + 1 > len(str(e)):
			continue
		vl = dp[j - 1]
		if e >= n:
			continue
		dp[i] = min(dp[i], dp[j - 1] * n + e)
print(dp[ln])


n = int(input())
s = input()
dp = [0] * (len(s) + 1)
pn = [0] * (len(s) + 1)
pn[len(pn) - 1] = 1
for k in range(len(s) - 1, -1, -1):
	num = 0
	dp[k] = -1
	if s[k] == '0':
		dp[k] = pn[k + 1] * num + dp[k + 1]
		pn[k] = pn[k + 1] * n
		continue
	for i in range(k, len(s)):
		num = num * 10 + int(s[i])
		if num >= n:
			break
		if dp[k] == -1 or pn[i + 1] * num + dp[i + 1] < dp[k]:
			dp[k] = pn[i + 1] * num + dp[i + 1]
			pn[k] = pn[i + 1] * n
print(dp[0])


n = int(input())
k = list(map(int, list(input())))
m = len(k)
rec = [0] * (m + 1)
for i in range(m):
	u = rec[i] * n
	if k[i] > 0:
		d = 0
		for j in range(i, m):
			d = d * 10 + k[j]
			if d >= n:
				break
			if rec[j + 1]:
				rec[j + 1] = min(rec[j + 1], u + d)
			else:
				rec[j + 1] = u + d
	elif rec[i + 1]:
		rec[i + 1] = min(rec[i + 1], u)
	else:
		rec[i + 1] = u
print(rec[-1])


n = int(input())
s = input()
i = len(s)
j = i - 1
tot = 0
mul = 1
while i > 0 and j >= 0:
	while j >= 0:
		_num = int(s[j:i])
		if _num >= n:
			j += 1
			while s[j] == '0' and i - j > 1:
				j += 1
			break
		num = _num
		j -= 1
	tot += mul * num
	mul *= n
	j -= 1
	i = j + 1
print(tot)


n = int(input())
s = input()[::1]
m = len(s)
dp = [[-1 for i in range(100)] for j in range(100)]
INF = 1e+20

def get(i, j):
	if dp[i][j] == -1:
		ans = INF
		if i == 0 and j == 0:
			ans = 0
		elif j == 0:
			ans = INF
		else:
			for leng in range(1, 10):
				if i >= leng:
					num = s[m - i:m - i + leng]
					if num == '' or int(num) >= n or (num[0] == '0' and len(num) != 1):
						continue
					num = int(num)
					ans = min(ans, get(i - leng, j - 1) + num * pow(n, j - 1))
				else:
					break
		dp[i][j] = ans
	return dp[i][j]
ans = INF
for i in range(1, m + 1):
	dp = [[-1 for i in range(100)] for j in range(100)]
	ans = min(ans, get(m, i))
print(ans)


k = int(input())
n = input()
if n == '0':
	print(0)
	exit(0)
cp = 1
ans = 0
cn = ''
cz = 0
for i in range(len(str(n))):
	ls = n[-1]
	n = n[:-1]
	if ls == '0':
		cz += 1
	else:
		sn = ls + '0' * cz + cn
		if int(sn) < k:
			cn = sn
			cz = 0
		else:
			if cn != '':
				ans += cp * int(cn)
				cp *= k
			cn = ls + '0' * cz
			while int(cn) >= k:
				cn = cn[:-1]
				cp *= k
			cz = 0
ans += cp * int(cn)
print(ans)


from math import floor
base = input()
num_str = input()
base = int(base)
bs_max_radix = len(str(base - 1))
skipCount = 0
exponent = 0
result = 0
for idx in reversed(range(len(num_str))):
	if skipCount > 0:
		skipCount -= 1
		continue
	chars = num_str[max(idx - bs_max_radix + 1, 0):idx + 1]
	num = int(chars)
	if num < base:
		result += num * pow(base, exponent)
		if num != 0:
			skipCount = len(str(int(chars))) - 1
		exponent += 1
	else:
		num = int(chars[1:])
		sigFigs = len(str(num))
		if num != 0:
			result += num * pow(base, exponent)
		exponent += 1
		skipCount = sigFigs - 1
print(result)


n = int(input())
s = input()
prr = []
while len(s) > 0:
	k = 0
	for i in range(len(s) - 1, -1, -1):
		if s[i] == '0':
			continue
		if int(s[i:]) >= n or len(s[i:]) > len(str(n)):
			k = i + 1
			while k < len(s) and s[k] == '0':
				k += 1
			if k == len(s):
				k = len(s) - 1
			break
	prr.append(int(s[k:]))
	s = s[:k]
sum = 0
for i in range(len(prr) - 1, -1, -1):
	sum *= n
	sum += prr[i]
print(sum)


import math

def binpow(x, y):
	ret = 1
	while y > 0:
		if y % 2 == 1:
			ret *= x
		x *= x
		y //= 2
	return ret
n = int(input())
k = input()
dp = [[-1 for i in range(100)] for j in range(100)]
dp[len(k)][0] = 0
tmp = 0
for i in range(len(k), -1, -1):
	for j in range(1, len(k) + 1):
		tmp = 0
		for s in range(i, len(k)):
			tmp *= 10
			tmp += ord(k[s]) - ord('0')
			if tmp >= n:
				break
			if dp[s + 1][j - 1] != -1 and dp[i][j] == -1 or dp[s + 1][j - 1] + tmp * binpow(n, j - 1) < dp[i][j]:
				dp[i][j] = dp[s + 1][j - 1] + tmp * binpow(n, j - 1)
			if s == i and k[s] == '0':
				break
ans = 10 ** 18 + 1
for i in range(1, len(k) + 1):
	if dp[0][i] != -1:
		ans = min(ans, dp[0][i])
print(ans)


n = int(input())
s = input()
dp = [0]
for i in range(1, len(s) + 1):
	dp.append(1000000000000000000000000000000000000)
	for j in range(1, 10):
		if j <= i:
			can = s[i - j:i]
			tmp = int(can)
			if tmp < n and (can[0] != '0' or can == '0'):
				val = dp[i - j] * n + tmp
				if val < dp[i]:
					dp[i] = val
			if tmp >= n:
				break
print(dp[len(s)])


3
import sys
import re
import pprint

def dbg(x, y=''):
	if len(y) > 0:
		y += ' = '
	sys.stderr.write('\n>>> ' + y + pprint.pformat(x) + '\n')
	sys.stderr.flush()
oo = 4557430888798830399

def minn(x, y):
	if x[0] < y[0]:
		return x
	if x[0] > y[0]:
		return y
	if x[1] < y[1]:
		return x
	if x[1] > y[1]:
		return y
	return x

def main():
	n = int(input())
	s = input()
	m = len(s)
	s = '0' + s
	power = [1]
	for i in range(1, 61):
		power.append(power[i - 1] * n)
	dp = [(int(1e+70), int(1e+70))] * 65
	dp[m + 1] = (0, 0)
	for i in range(m, 0, -1):
		if s[i] == '0':
			tmp = dp[i + 1]
			dp[i] = (1 + tmp[0], tmp[1])
			continue
		for j in range(i, min(m + 1, i + 9)):
			d = int(s[i:j + 1])
			if d >= n:
				break
			tmp = dp[j + 1]
			dp[i] = minn(dp[i], (1 + tmp[0], d * power[tmp[0]] + tmp[1]))
	print(dp[1][1])
main()


n = int(input())
k = input()
INF = 10 ** 100
dp = [[INF] * 100 for i in range(len(k) + 1)]
dp[len(k)][0] = 0
dp[len(k) - 1][0] = int(k[len(k) - 1])
deg = [1] * 1000
for i in range(1, 100):
	deg[i] = deg[i - 1] * n
for i in range(len(k) - 1, -1, -1):
	if k[i] == '0':
		for cur_deg in range(1, 61):
			dp[i][cur_deg] = dp[i + 1][cur_deg - 1]
		continue
	if int(k[i:]) < n:
		dp[i][0] = int(k[i:])
	for cur_deg in range(1, 61):
		j = i
		cur_num = 0
		while j < len(k) and cur_num < n:
			cur_num = cur_num * 10 + int(k[j])
			if dp[j + 1][cur_deg - 1] == INF or cur_num >= n:
				j += 1
				continue
			dp[i][cur_deg] = min(dp[i][cur_deg], dp[j + 1][cur_deg - 1] + cur_num * deg[cur_deg])
			j += 1
print(min(dp[0]))


(n, m) = (int(input()), int(input()))
(i, cnt, l) = (0, 0, len(str(n)))
while m != 0:
	t = m % 10 ** l
	if t < n and len(str(t)) == l:
		cnt += t * n ** i
		i += 1
		m = m // 10 ** l
		l = len(str(n))
	else:
		l -= 1
print(cnt)


inf = 10 ** 100
b = int(input())
s = input()
n = len(s)
dp = []
for i in range(n + 1):
	dp.append([inf] * (n + 2))
dp[n][0] = 0
for i in range(n - 1, -1, -1):
	for j in range(i + 1, min(i + 12, n + 1)):
		if j - i > 1 and s[i] == '0':
			continue
		cur = int(s[i:j])
		if cur >= b:
			continue
		for p in range(n + 1):
			dp[i][p + 1] = min(dp[i][p + 1], dp[j][p] + cur)
			cur *= b
res = inf
for p in range(n + 2):
	res = min(res, dp[0][p])
print(res)


def solve(n, k):
	dp = [420] * (len(k) + 1)
	dp[-1] = 0
	idx = len(k) - 1
	n_num = int(n)
	while idx >= 0:
		if k[idx] != '0':
			for shift in range(1, len(k) - idx + 1):
				ok = int(k[idx:idx + shift]) < n_num
				if ok:
					dp[idx] = min(dp[idx], 1 + dp[idx + shift])
				else:
					break
		else:
			dp[idx] = 1 + dp[idx + 1]
		idx -= 1
	digits = list()
	idx = 0
	while idx < len(k):
		shift = 1
		while idx + shift <= len(k):
			if dp[idx + shift] + 1 == dp[idx]:
				digits.append(int(k[idx:idx + shift]))
				break
			else:
				shift += 1
		idx += shift
	(tot_res, n_pow) = (0, 1)
	for el in reversed(digits):
		tot_res += n_pow * el
		n_pow *= n_num
	return tot_res
N = input()
K = input()
print(solve(N, K))


import math
MAX = 10 ** 18 + 5
n = int(input())
k = input()
dp = [[MAX, 0] for _ in range(len(k) + 1)]
m = math.ceil(math.log(n, 10))
p = 0
dp[-1] = [0, -1]
for i in range(len(dp) - 2, -1, -1):
	s = ''
	p = dp[i + 1][1] + 1
	for j in range(0, m):
		if i >= j:
			s = k[i - j] + s
			if int(s) < n:
				if s[0] == '0':
					if len(s) == 1:
						x = int(s) * pow(n, p) + dp[i + 1][0]
				else:
					x = int(s) * pow(n, p) + dp[i + 1][0]
				if x <= 10 ** 18:
					if x <= dp[i - j][0]:
						dp[i - j] = [x, p]
		else:
			break
print(dp[0][0])


n = int(input())
s = input()
s = ''.join((j for j in [i for i in reversed(s)]))
cnt = 0
t = n
while t != 0:
	cnt += 1
	t //= 10
dp = [[-1 for i in range(100)] for j in range(100)]
dp[0][0] = ord(s[0]) - ord('0')
len = len(s)
for i in range(1, len):
	for j in range(len):
		for k in range(i, -1, -1):
			if j == 0:
				if s[i] == '0':
					continue
				else:
					get = int(''.join((i for i in reversed(s[0:i + 1]))))
					if get < n and i + 1 <= cnt:
						dp[i][j] = get
			elif s[i] == '0':
				dp[i][j] = dp[i - 1][j - 1]
			else:
				get = int(''.join((i for i in reversed(s[k:i + 1]))))
				if get < n and i - k + 1 <= cnt:
					if dp[k - 1][j - 1] != -1:
						new_val = get * n ** j + dp[k - 1][j - 1]
						if dp[i][j] == -1 or dp[i][j] > new_val:
							dp[i][j] = new_val
ans = 2e+18
for i in range(len):
	if dp[len - 1][i] != -1:
		ans = min(ans, dp[len - 1][i])
print(ans)


def check(i, new, s):
	d = ''
	while i >= 0 and (not int(s[i])):
		d = s[i] + d
		i -= 1
	if i >= 0:
		d = s[i] + d
	if int(d + new) >= n:
		return ''
	return d
n = int(input())
s = input()
m = []
i = len(s) - 1
while i >= 0:
	new = s[i]
	i -= 1
	add = check(i, new, s)
	while i >= 0 and add:
		new = add + new
		i -= len(add)
		add = check(i, new, s)
	m.append(int(new))
l = len(m)
for i in range(l // 2):
	(m[i], m[l - i - 1]) = (m[l - i - 1], m[i])
ans = 0
for i in range(l):
	ans += m[i] * n ** (l - i - 1)
print(ans)


import math

def find(n, k, length):
	if k < n:
		return [k]
	else:
		MAX = 0
		index = 1
		for i in range(1, length + 1):
			temp = k % 10 ** i
			if temp >= n:
				break
			elif temp >= 10 ** (i - 1):
				MAX = temp
				index = i
		res = k - MAX
		res = res // 10 ** index
		return find(n, res, length) + [MAX]
n = int(input())
k = int(input())
length = int(math.log(n - 1, 10)) + 1
ANS = find(n, k, length)[::-1]
ans = 0
temp = 1
for i in range(len(ANS)):
	ans += ANS[i] * temp
	temp *= n
print(ans)


(t, m) = (input(), input())
(n, d) = (int(t), len(t))
(s, p) = (0, 1)
j = len(m)
while j:
	i = max(0, j - d)
	k = int(m[i:j])
	if k >= n:
		i += 1
		k = int(m[i:j])
	while m[i] == '0' and i < j - 1:
		i += 1
	j = i
	s += k * p
	p *= n
print(s)


n = int(input())
K = input()
m = len(K)
inf = 10 ** 100
dp = [inf] * (m + 1)
dp[0] = 0
for i in range(m):
	if K[i] == '0':
		dp[i + 1] = min(dp[i + 1], dp[i] * n + int(K[i]))
	else:
		val = 0
		for j in range(i, m):
			val = val * 10 + int(K[j])
			if val >= n:
				break
			dp[j + 1] = min(dp[j + 1], dp[i] * n + val)
print(dp[m])


n = input()
k = input()
digit = len(n)
lst = []

def recul(k):
	if len(k) == 0:
		return
	if k[-digit:] < n:
		lst.append(k[-digit:])
		if k[-digit:][0:1] == '0' and len(k[-digit:]) != 1:
			recul(k[:-digit] + '0')
		else:
			recul(k[:-digit])
	else:
		temp = -digit + 1
		while k[temp:temp + 1] == '0' and temp < 0:
			temp += 1
		if temp == 0:
			lst.append('0')
			recul(k[:-1])
			return
		lst.append(k[temp:])
		recul(k[:temp])
if digit == 1:
	print(int(k, int(n)))
	exit()
recul(k)
ans = 0
for x in range(len(lst)):
	ans += int(lst[x]) * int(n) ** x
print(ans)


def init(dp):
	for i in range(70):
		for j in range(70):
			dp[i][j] = -1

def memo(cnt, power, N, K, dp):
	if cnt >= len(K):
		return 0
	if dp[cnt][power] >= 0:
		return dp[cnt][power]
	res = 1 << 100
	base = N ** power
	if power < 0:
		return res
	if K[cnt] == '0':
		dp[cnt][power] = memo(cnt + 1, power - 1, N, K, dp)
		return dp[cnt][power]
	tmp = ''
	for i in range(cnt, len(K)):
		tmp += K[i]
		d = int(tmp)
		if d >= N:
			break
		res = min(res, memo(i + 1, power - 1, N, K, dp) + d * base)
	dp[cnt][power] = res
	return res
N = int(input())
K = input()
M = len(K)
dp = [[0 for i in range(70)] for j in range(70)]
limit = 10 ** 18
result = 1 << 100
for x in range(65, -1, -1):
	init(dp)
	result = min(result, memo(0, x, N, K, dp))
print(result)


n = int(input())
k = list(map(int, input()))
k = k[::-1]
(ans, cur, i) = (0, 1, 0)
while i < len(k):
	(nxt, sm, temp, mul) = (i + 1, k[i], k[i], 10)
	for j in range(i + 1, len(k)):
		temp += mul * k[j]
		mul *= 10
		if k[j] != 0 and temp < n:
			nxt = j + 1
			sm = temp
	ans += sm * cur
	i = nxt
	cur *= n
print(ans)


n = int(input())
k = input()
a = 0
p = 1
while len(k) > 0:
	i = len(k) - 1
	while i >= 0 and int(k[i:]) < n:
		i -= 1
	i += 1
	r = int(k[i:])
	k = k[0:len(k) - len(str(r))]
	a += r * p
	p *= n
print(a)


n = int(input())
s = input()
if s == '0':
	print(0)
	exit(0)

def dig(c):
	return ord(c) - ord('0')

def ind(i, cnt, len):
	return i + cnt * 65 + len * 65 * 65
dp = [int(10 ** 71)] * 70 * 70 * 70
dp[ind(0, 0, 1)] = 0
m = len(s)
for i in range(m):
	for cnt in range(0, 64):
		for len in range(1, 64):
			if dp[ind(i, cnt, len)] == int(10 ** 71):
				continue
			curDp = dp[ind(i, cnt, len)]
			if i != m - 1:
				dp[ind(i + 1, cnt, len + 1)] = min(dp[ind(i + 1, cnt, len + 1)], curDp)
			curKekNum = int(s[i - len + 1:i + 1])
			bad = False
			if s[i - len + 1] == '0' and len != 1:
				bad = True
			if bad == False and curKekNum < n:
				newDp = curDp * n + curKekNum
				dp[ind(i + 1, cnt + 1, 1)] = min(dp[ind(i + 1, cnt + 1, 1)], newDp)
ans = int(10 ** 71)
for cnt in range(1, 70):
	ans = min(ans, dp[ind(m, cnt, 1)])
print(ans)


def main():
	QWE = 'trick'
	INF = 10 ** 18 + 9
	EPS = 10 ** (-7)
	import sys, math
	n = input()
	ln = len(n)
	n = int(n)
	s = input()
	m = len(s)
	d = [0] * (m + 1)
	for i in range(1, m + 1):
		d[i] = INF
		for j in range(max(1, i - ln), i + 1):
			if s[j - 1] != '0' or j == i:
				q = int(s[j - 1:i])
				if q < n:
					d[i] = min(d[i], d[j - 1] * n + q)
	print(d[m])
main()


INF = int(1e+18)

def reverse(s):
	for i in range(len(s) // 2):
		(s[i], s[len(s) - i - 1]) = (s[len(s) - i - 1], s[i])
	return s
dp = []
for i in range(61):
	dp += [[]]
	for j in range(61):
		dp[i] += [[]]
		for k in range(61):
			dp[i][j] += [INF]
n = int(input())
ff = input()
k = []
for i in range(len(ff)):
	k += ff[i]
k = reverse(k)
dp[0][0][0] = 0
for kk in range(1, len(k) + 1):
	for i in range(1, len(k) + 1):
		s = ''
		for j in range(1, i + 1):
			s += k[i - j]
			if k[i - j] == '0':
				if j == 1:
					mn = INF
					for jj in range(0, 61):
						mn = min(mn, dp[i - j][jj][kk - 1])
					if mn != INF:
						dp[i][j][kk] = mn
			if s[0] == '0':
				continue
			d = int(s)
			if d < n:
				mn = INF
				for jj in range(0, 61):
					mn = min(mn, dp[i - j][jj][kk - 1])
				if mn != INF:
					dp[i][j][kk] = mn + pow(n, kk - 1) * d
ans = INF
n = len(k)
for k in range(1, 61):
	for j in range(0, 61):
		ans = min(ans, dp[n][j][k])
print(ans)


from sys import stdin, stdout
base = stdin.readline().strip()
num = stdin.readline().strip()
ans = []
i = len(num) - len(base)
while i >= 0:
	j = i
	while num[j] == '0' and j < i + len(base) - 1:
		j += 1
	if int(num[j:i + len(base)]) >= int(base):
		j += 1
		while num[j] == '0' and j < i + len(base) - 1:
			j += 1
		ans.append(num[j:i + len(base)])
	else:
		ans.append(num[j:i + len(base)])
	i = j - len(base)
i += len(base)
if i:
	ans.append(num[:i])
cnt = 0
for i in range(len(ans)):
	cnt += int(base) ** i * int(ans[i])
stdout.write(str(cnt))


a = int(input())
b = input()
la = len(str(a))
ans = 0
c = 0
k = 0
i = 0
ch = 0
while True:
	if len(b) < la:
		if len(b) == 0:
			break
		else:
			ans += int(b) * a ** i
			i += 1
			break
	c = int(b[len(b) - la:len(b)])
	k = la
	while b[len(b) - la + ch] == '0' and la - ch != 1:
		ch += 1
		c = int(b[len(b) - la + ch:len(b)])
		k = la - ch
	while c >= a:
		ch += 1
		if b[len(b) - la + ch] != '0' or la - ch == 1:
			c = int(b[len(b) - la + ch:len(b)])
			k = la - ch
	ch = 0
	ans += c * a ** i
	i += 1
	b = b[0:len(b) - k]
print(ans)


def recursion(n, string, step, last, con):
	ss = ''
	minim = 10 ** 18 + 1
	i = last
	while i > 0:
		ss = string[i] + ss
		if len(ss) > 19:
			break
		nn = int(ss)
		if nn >= n:
			break
		nn = nn * step
		if nn > con:
			break
		if string[i] != '0' or len(ss) == 1:
			minim = min(minim, nn + recursion(n, string, step * n, i - 1, con))
		i -= 1
	sss = ''
	for i in range(last + 1):
		sss += string[i]
	if len(sss) > 19:
		return minim
	nnn = int(sss)
	sas = nnn * step
	if nnn < n and sas >= 0 and (sas <= con):
		minim = min(minim, nnn * step)
	return minim
con = 10 ** 18
n = int(input())
string = input()
answer = 0
if n <= 10:
	step = 1
	for i in range(len(string)):
		ss = ''
		ss += string[len(string) - i - 1]
		answer += step * int(ss)
		step = step * n
	print(answer)
else:
	answer = recursion(n, string, 1, len(string) - 1, con)
	print(answer)


n = int(input())
a = input()
cn = 0
fn = 0
tp = 0
c10p = 0
maxi = -1
while len(a) != 0:
	maxi = -1
	for i in range(1, len(a) + 1):
		ds = int(a[-i:])
		if ds < n and int(a[-i]) != 0:
			maxi = i
	if maxi == -1 and int(a[-1]) == 0:
		a = a[:-1]
		tp += 1
	else:
		fn += int(a[-maxi:]) * n ** tp
		tp += 1
		a = a[:-maxi]
print(fn)


def convertTo(act, param):
	return int(act) * param

def rmLeading(act):
	while act[0] == '0':
		act = act[1:]
	return act

def pureZero(act):
	for i in act:
		if i != '0':
			return False
	return True

def getTheAct(act, i, n, k):
	while i >= 0 and int(k[i] + act) < int(n):
		act = k[i] + act
		i = i - 1
	if pureZero(act):
		return '0'
	act = rmLeading(act)
	return act
n = input()
k = input()
act = ''
rpta = 0
mult = 1
i = len(k) - 1
while i >= 0:
	act = getTheAct('', i, n, k)
	i = i - len(act)
	rpta = rpta + convertTo(act, mult)
	mult = mult * int(n)
print(rpta)


n = int(input())
k = input()
dp = [10 ** 70] * (len(k) + 1)
dp[0] = 0
for i in range(1, len(k) + 1):
	for j in range(i):
		if int(k[j:i]) < n and (k[j] != '0' or j == i - 1):
			dp[i] = min(dp[i], dp[j] * n + int(k[j:i]))
print(dp[-1])


n = int(input())
k = [0] + list(map(int, list(input())))

def calc(l, r):
	if k[l] == 0 and l < r - 1:
		return -1
	res = 0
	for i in range(max(l, 0), r):
		res *= 10
		res += k[i]
	return res
z = []
last_index = len(k)
index = len(k) - 1
while index >= -1:
	c = calc(index, last_index)
	while c >= n:
		li = index + 1
		nw = calc(li, last_index)
		while nw < 0:
			li += 1
			nw = calc(li, last_index)
		z.append(nw)
		last_index = li
		c = calc(index, last_index)
	index -= 1
li = index + 1
nw = calc(li, last_index)
while nw < 0:
	li += 1
	nw = calc(li, last_index)
z.append(nw)
last_index = li
c = calc(index, last_index)
z = z[::-1]
ans = 0
for i in z:
	ans *= n
	ans += i
print(ans)


n = int(input())
s = input()
dp = [[10 ** 100] * len(s) for _ in range(len(s))]
for i in range(len(s) - 1, -1, -1):
	for j in range(i, len(s)):
		a = int(s[i:j + 1])
		if len(str(a)) == j - i + 1 and a < n:
			if j == len(s) - 1:
				dp[i][0] = min(dp[i][0], a)
			else:
				for k in range(1, len(s)):
					dp[i][k] = min(dp[i][k], a * n ** k + dp[j + 1][k - 1])
print(min(dp[0]))


n = int(input())
k = input()
l = len(k)
ans = 0
b = 1
i = l - 1
while i >= 0:
	sum = 0
	res = i
	for j in range(i, -1, -1):
		sum += (ord(k[j]) - ord('0')) * 10 ** (i - j)
		res = j
		if sum >= n:
			res = j + 1
			break
	for j in range(res, i + 1):
		if k[j] == '0':
			res = j + 1
		else:
			break
	res = min(res, i)
	sum = 0
	for j in range(res, i + 1):
		sum = sum * 10 + ord(k[j]) - ord('0')
	ans += sum * b
	b *= n
	i = res - 1
print(ans)


m = int(input())
s = input()
n = len(s)
s = s[::-1]
inf = 10 ** 18 + 213
f = [0] * (n + 1)
for i in range(n + 1):
	f[i] = [inf] * (n + 1)
f[0][0] = 0
for prefix in range(n + 1):
	for base in range(n + 1):
		if f[prefix][base] == inf:
			continue
		for len in range(1, n + 1):
			if prefix + len > n:
				break
			if s[prefix + len - 1] == '0' and len > 1:
				continue
			val = 0
			for k in range(len):
				val *= 10
				val += int(s[prefix + len - k - 1])
			if val < m:
				val *= m ** base
				f[prefix + len][base + 1] = min(f[prefix + len][base + 1], f[prefix][base] + val)
ans = inf
for i in range(n + 1):
	ans = min(ans, f[n][i])
print(ans)


def findMin(base, number, power):
	len_base = len(base)
	len_number = len(number)
	BASE = int(base)
	if int(number) < int(base):
		return int(number) * int(base) ** power
	else:
		for i in range(len_base, 0, -1):
			if number[-1 * i] == '0':
				continue
			elif int(number[len_number - i:]) < BASE:
				answer = int(number[len_number - i:]) * int(base) ** power
				number = number[:len_number - i]
				return answer + findMin(base, number, power + 1)
		number = number[:len_number - 1]
		return findMin(base, number, power + 1)
base = input()
number = input()
print(findMin(base, number, 0))


n = int(input())
k = input()
ans = 0
p = 1
i = len(k) - 1
j = len(k)
while i >= 0:
	if k[i] != '0' or j - i == 1:
		v = int(k[i:j])
		if v < n:
			x = i
		else:
			ans += p * int(k[x:j])
			p *= n
			i = j = x
	i -= 1
if j > 0:
	ans += p * int(k[0:j])
print(ans)


base = int(input())
num = input()
result = 0
place_value = 1
end = len(num)
while end > 0:
	begin = end - 1
	good_begin = begin
	while begin >= 0:
		if int(num[begin:end]) >= base:
			break
		elif num[begin] != '0':
			good_begin = begin
		begin -= 1
	begin = good_begin
	result += place_value * int(num[begin:end])
	place_value *= base
	end = begin
print(result)


b = int(input())
s = input()
n = len(s)
pwr = [1]
for _ in range(60):
	if pwr[-1] * b <= 10 ** 18:
		pwr.append(pwr[-1] * b)
	else:
		break
digit = len(pwr)
ans = 10 ** 18
dp = [[10 ** 20 for _ in range(digit + 10)] for _ in range(n)]
for j in range(digit):
	dp[0][j] = int(s[0]) * pwr[j]
for i in range(1, n):
	if int(s[:i + 1]) < b:
		dp[i][0] = int(s[:i + 1])
	for j in range(digit):
		dp[i][j] = min(dp[i][j], dp[i - 1][j + 1] + int(s[i]) * pwr[j])
		for k in range(i - 1, 0, -1):
			if s[k] != '0' and int(s[k:i + 1]) < b:
				dp[i][j] = min(dp[i][j], dp[k - 1][j + 1] + int(s[k:i + 1]) * pwr[j])
		if int(s[:i + 1]) < b:
			dp[i][j] = min(dp[i][j], int(s[:i + 1]) * pwr[j])
print(dp[n - 1][0])


n = int(input().strip())
s = input().strip()
ans = 0
j = 0
while len(s) > 0:
	i = 1
	while i < len(s) and int(s[-i:]) < n:
		i += 1
	if int(s[-i:]) >= n:
		i -= 1
	while s[-i:][0] == '0' and len(s[-i:]) > 1:
		i -= 1
	ans += int(s[-i:]) * pow(n, j)
	j += 1
	s = s[:-i]
print(ans)


n = int(input())
k = input()
z = 0
w = 0
j = len(k) - 1
i = j
while j >= 0:
	r = j - 1
	while r >= 0 and k[r] == '0':
		r -= 1
	if j >= 0 and k[j] == '0' and (i - r + 1 > 10 or int(k[r:i + 1]) >= n):
		if j == i:
			w += 1
			j -= 1
			i -= 1
		else:
			z += pow(n, w) * int(k[j + 1:i + 1])
			i = j
			w += 1
		continue
	elif i - j + 1 >= 10 or int(k[j:i + 1]) >= n:
		z += pow(n, w) * int(k[j + 1:i + 1])
		i = j
		w += 1
		continue
	else:
		j -= 1
		continue
z += pow(n, w) * int(k[j + 1:i + 1])
print(z)


import sys
input = sys.stdin.readline
n = int(input())
k = input().rstrip()
dp = [10 ** 70] * (len(k) + 1)
dp[0] = 0
for i in range(1, len(k) + 1):
	for j in range(i):
		if int(k[j:i]) < n and (k[j] != '0' or j == i - 1):
			dp[i] = min(dp[i], dp[j] * n + int(k[j:i]))
print(dp[-1])


def main():
	n = int(input())
	k = int(input())
	if k == 0:
		print(0)
		return
	ans = 0
	np = 1
	while k > 0:
		i = 10
		ok = k
		p10 = 1
		x = 0
		while ok > 0:
			c = ok % 10
			x += p10 * c
			p10 *= 10
			if x >= n:
				break
			if c != 0:
				i = p10
			ok //= 10
		x = k % i
		k //= i
		ans += x * np
		np *= n
	print(ans)
main()


import sys
import array
dp = [[[0 for k in range(70)] for j in range(70)] for i in range(70)]
mark = [[[0 for k in range(70)] for j in range(70)] for i in range(70)]
pot = []
n = 0
k = ''
lim = 0

def f(i, j, expo):
	global k, n, lim, dp, mark, pot
	aux = k[j:i][::-1]
	val = int(aux)
	if val >= n:
		return 1000000000000000000
	if i == lim:
		if aux[0] == '0' and len(aux) > 1:
			return 1000000000000000000
		return val * pot[expo]
	if mark[i][j][expo] == 1:
		return dp[i][j][expo]
	ret = f(i + 1, j, expo)
	if aux[0] != '0' or len(aux) == 1:
		ret = min(ret, f(i + 1, i, expo + 1) + val * pot[expo])
	mark[i][j][expo] = 1
	dp[i][j][expo] = ret
	return dp[i][j][expo]

def main():
	global k, n, lim, dp, mark, pot
	n = int(input())
	k = str(input())
	k = k[::-1]
	pot.append(1)
	for i in range(65):
		pot.append(pot[-1] * n)
	lim = len(k)
	print(f(1, 0, 0))
main()


n = int(input())
d = input()
l = len(d)
dp = [[0, 0] for i in range(0, l + 1)]
dp[l - 1] = [ord(d[l - 1]) - ord('0'), 1]
for i in range(1, l):
	w = l - 1 - i
	m = (ord(d[w]) - ord('0')) * n ** i + dp[w + 1][0]
	dp[w] = [m, i + 1]
	if d[w] == '0':
		dp[w][0] = dp[w + 1][0]
		dp[w][1] = dp[w + 1][1] + 1
		continue
	for j in range(w, l):
		subs = int(d[w:j + 1])
		u = dp[j + 1]
		if subs < n:
			re = subs * n ** u[1] + u[0]
			if re < dp[w][0] or (re == dp[w][0] and 1 + u[1] < dp[w][1]):
				dp[w][0] = re
				dp[w][1] = 1 + u[1]
		else:
			break
print(dp[0][0])


n = int(input())
k = input()
a = ''
ans = 0
base = 0
i = len(k) - 1
while i >= 0:
	p_a = a
	a = k[i] + a
	i -= 1
	a_i = int(a)
	if a_i >= n:
		i += 1
		a = p_a
		while len(a) > 1 and a[0] == '0':
			a = a[1:]
			i += 1
		ans += int(a) * n ** base
		a = ''
		base += 1
ans += int(a) * n ** base
print(ans)


def check(s, n):
	ans = 0
	if s != '':
		ans = int(s)
	return ans < n
n = int(input())
k = input()
s = ''
i = len(k) - 1
ans = 0
add = 1
while i >= 0:
	while i >= 0 and check(k[i] + s, n):
		s = k[i] + s
		i -= 1
	while len(s) > 1 and s[0] == '0':
		s = s[1:]
		i += 1
	ans += int(s) * add
	add *= n
	s = ''
print(ans)


def getint(a):
	return int(''.join(map(str, a)))
b = int(input())
s = input()
s = list(map(int, list(s)))
n = len(s)
DP = [(-1, 0) for i in range(n + 1)]
for i in range(n - 1, -1, -1):
	pass
	for j in range(i + 1, n + 1):
		a = getint(s[i:j])
		pass
		if a >= b:
			break
		if a > 9:
			t = DP[j]
			a = a * b ** t[1]
			if t[0] != -1:
				a += t[0]
			p = (a, t[1] + 1)
			if DP[i][0] == -1:
				DP[i] = p
			elif DP[i][0] > p[0]:
				DP[i] = p
		else:
			t = DP[j]
			a = a * b ** t[1]
			if t[0] != -1:
				a += t[0]
			p = (a, t[1] + 1)
			if DP[i][0] == -1:
				DP[i] = p
			elif DP[i][0] > p[0]:
				DP[i] = p
	pass
for i in range(n):
	pass
print(DP[0][0])


n = int(input())
k = input().strip()
power = [1]
for i in range(20):
	power.append(power[-1] * 10)
dp = [10 ** 18] * len(k)
for i in range(len(k)):
	for j in range(min(10, i + 1)):
		if k[i - j] == '0' and j > 0:
			continue
		s = int(k[i - j:i + 1])
		if s >= n:
			break
		if i - j > 0:
			dp[i] = min(dp[i], dp[i - j - 1] * n + s)
		else:
			dp[i] = min(dp[i], s)
print(dp[len(k) - 1])


n = input()
s = input()
k = len(n)
n = int(n)
a = []
i = len(s) - 1
l = 0
while i - k + 1 >= 0:
	if int(s[i - k + 1:i + 1]) < n:
		z = len(str(int(s[i - k + 1:i + 1])))
		a.append(int(s[i - z + 1:i + 1]))
		i -= z
	else:
		z = len(str(int(s[i - k + 2:i + 1])))
		a.append(int(s[i - z + 1:i + 1]))
		i -= z
else:
	if i > -1 and int(s[0:i + 1]) < n:
		a.append(int(s[0:i + 1]))
		i -= k
for i in range(len(a)):
	l += a[i] * n ** i
print(min(l, 10 ** 18))


n = int(input())
k = input()
if int(k) < n:
	print(k)
else:
	power = 0
	digits = 0
	ans = 0
	while len(k) > 0:
		current = 0
		while int(k[current:]) >= n and current < len(k) or (int(k[current]) == 0 and len(k) > 1 and (current < len(k) - 1)):
			current += 1
		if current == len(k):
			power += 1
		else:
			ans += int(k[current:]) * n ** power
			power += 1
			k = str(k[:current])
	print(ans)


base = int(input())
k = input()
k = k[::-1]
n = len(k)
dp = [[int(1e+18) for i in range(0, 2 * n + 1)] for j in range(0, n + 1)]
for i in range(0, n + 1):
	dp[n][i] = 0
for i in reversed(range(0, n)):
	for k1 in range(0, n):
		for j in range(i, n):
			if k[j] == '0' and i != j:
				continue
			num = int(k[j - n:i - n - 1:-1])
			if num >= base:
				break
			num *= base ** k1
			if dp[i][k1] > num + dp[j + 1][k1 + 1]:
				dp[i][k1] = num + dp[j + 1][k1 + 1]
print(int(dp[0][0]))


n = int(input())
k = int(input())
l = 1
t = n - 1
while True:
	t //= 10
	if t <= 0:
		break
	l += 1
b = 10 ** l
p = []
while k > 0:
	u = b
	m = k % u
	while m > 0:
		if m < n and 10 * m >= u:
			k //= u
			break
		u //= 10
		m = k % u
	else:
		k //= 10
	p.append(m)
r = 0
for (k, i) in enumerate(p):
	r += n ** k * i
print(r)


n = int(input())
s = input()
pw = [1]
last = 1
for i in range(70):
	if last > 1e+19:
		break
	pw.append(last * n)
	last = last * n
dp = [1e+19] * 100
for i in range(100):
	dp[i] = [1e+19] * 100
dp[len(s)][0] = 0
for i in range(len(s), -1, -1):
	for power in range(0, len(pw)):
		cur = ''
		for j in range(i - 1, -1, -1):
			cur = s[j] + cur
			if int(cur) > n or int(cur) * pw[power] > 1e+19:
				break
			if (cur[0] != '0' or len(cur) == 1) and int(cur) < n:
				dp[j][power + 1] = min(dp[j][power + 1], dp[i][power] + int(cur) * pw[power])
print(min(dp[0]))


n = int(input())
k = input()
pos = len(k)
ans = []
while pos > 0:
	tmp = 0
	l = pos - 1
	mark = l
	while l >= 0:
		a = int(k[l:pos])
		if a >= n:
			break
		else:
			if a != tmp:
				mark = l
			tmp = a
			l -= 1
	if tmp == 0:
		pos -= 1
		ans.append(0)
	else:
		pos = mark
		ans.append(tmp)
aans = 0
for i in ans[::-1]:
	aans = aans * n + i
print(aans)


from _collections import defaultdict
n = int(input())
s = input()
l = len(s)
ll = len(str(n))
d = defaultdict(int)
for i in range(l):
	for j in range(1, ll + 1):
		if i - j + 1 >= 0 and (s[i - j + 1] != '0' or j == 1) and (d[i - j] or i - j == -1):
			ss = d[i - j]
			add = int(s[i - j + 1:i + 1])
			if add < n:
				ss = ss * n + add
				if not d[i]:
					d[i] = ss
				else:
					d[i] = min(ss, d[i])
print(d[l - 1])


n = int(input())
s = str(input())
m = len(s)
x = m - 1
inf = int(1e+19)
dp = [[inf for p in range(m + 1)] for z in range(m + 1)]
pows = [1]
for i in range(m + 1):
	pows.append(pows[-1] * n)
for j in range(m - 1, -1, -1):
	if j == m - 1:
		dp[j][0] = int(s[j])
		continue
	if s[j] == '0':
		for x in range(m):
			dp[j][x + 1] = dp[j + 1][x]
		continue
	r = ''
	for k in range(j, m):
		r = r + s[k]
		y = int(r)
		if y >= n:
			break
		if k == m - 1:
			dp[j][0] = y
		else:
			for x in range(m):
				dp[j][x + 1] = min(dp[j][x + 1], dp[k + 1][x] + pows[x + 1] * y)
ans = inf
for i in range(m + 1):
	ans = min(ans, dp[0][i])
print(ans)


n = int(input())
k = input()
answ = []
i = len(k)
while True:
	j = i - 1
	while int(k[j:i]) < n:
		j -= 1
		if j < 0:
			j = 0
			break
	while int(k[j:i]) >= n or (j + 1 != i and k[j] == '0'):
		j += 1
	answ.append(k[j:i])
	i = j
	if i <= 0:
		break
res = 0
p = 1
for i in map(int, answ):
	res += i * p
	p *= n
print(res)


was = {}
dp = {}

def solve(id, cnt):
	if id == -1:
		return 0
	if was.get((id, cnt)) != None:
		return dp[id, cnt]
	else:
		was[id, cnt] = True
		dp[id, cnt] = 10 ** 18
		for i in range(0, id + 1):
			cur = 0
			for j in range(i, id + 1):
				cur = cur * 10 + ord(k[j]) - 48
			if cur < n and k[i] != '0':
				dp[id, cnt] = min(dp[id, cnt], solve(i - 1, cnt + 1) + cur * n ** cnt)
		if k[id] == '0':
			dp[id, cnt] = min(dp[id, cnt], solve(id - 1, cnt + 1))
		return dp[id, cnt]
n = input()
k = input()
n = int(n)
print(solve(len(k) - 1, 0))


import math
import random
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
import threading
from collections import defaultdict
threading.stack_size(10 ** 8)
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
sys.setrecursionlimit(300000)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class TreeNode:

	def __init__(self, k, v):
		self.key = k
		self.value = v
		self.left = None
		self.right = None
		self.parent = None
		self.height = 1
		self.num_left = 1
		self.num_total = 1

class AvlTree:

	def __init__(self):
		self._tree = None

	def add(self, k, v):
		if not self._tree:
			self._tree = TreeNode(k, v)
			return
		node = self._add(k, v)
		if node:
			self._rebalance(node)

	def _add(self, k, v):
		node = self._tree
		while node:
			if k < node.key:
				if node.left:
					node = node.left
				else:
					node.left = TreeNode(k, v)
					node.left.parent = node
					return node.left
			elif node.key < k:
				if node.right:
					node = node.right
				else:
					node.right = TreeNode(k, v)
					node.right.parent = node
					return node.right
			else:
				node.value = v
				return

	@staticmethod
	def get_height(x):
		return x.height if x else 0

	@staticmethod
	def get_num_total(x):
		return x.num_total if x else 0

	def _rebalance(self, node):
		n = node
		while n:
			lh = self.get_height(n.left)
			rh = self.get_height(n.right)
			n.height = max(lh, rh) + 1
			balance_factor = lh - rh
			n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
			n.num_left = 1 + self.get_num_total(n.left)
			if balance_factor > 1:
				if self.get_height(n.left.left) < self.get_height(n.left.right):
					self._rotate_left(n.left)
				self._rotate_right(n)
			elif balance_factor < -1:
				if self.get_height(n.right.right) < self.get_height(n.right.left):
					self._rotate_right(n.right)
				self._rotate_left(n)
			else:
				n = n.parent

	def _remove_one(self, node):
		replacement = node.left or node.right
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = replacement
			else:
				node.parent.right = replacement
			replacement.parent = node.parent
			node.parent = None
		else:
			self._tree = replacement
			replacement.parent = None
		node.left = None
		node.right = None
		node.parent = None
		self._rebalance(replacement)

	def _remove_leaf(self, node):
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = None
			else:
				node.parent.right = None
			self._rebalance(node.parent)
		else:
			self._tree = None
		node.parent = None
		node.left = None
		node.right = None

	def remove(self, k):
		node = self._get_node(k)
		if not node:
			return
		if AvlTree._is_leaf(node):
			self._remove_leaf(node)
			return
		if node.left and node.right:
			nxt = AvlTree._get_next(node)
			node.key = nxt.key
			node.value = nxt.value
			if self._is_leaf(nxt):
				self._remove_leaf(nxt)
			else:
				self._remove_one(nxt)
			self._rebalance(node)
		else:
			self._remove_one(node)

	def get(self, k):
		node = self._get_node(k)
		return node.value if node else -1

	def _get_node(self, k):
		if not self._tree:
			return None
		node = self._tree
		while node:
			if k < node.key:
				node = node.left
			elif node.key < k:
				node = node.right
			else:
				return node
		return None

	def get_at(self, pos):
		x = pos + 1
		node = self._tree
		while node:
			if x < node.num_left:
				node = node.left
			elif node.num_left < x:
				x -= node.num_left
				node = node.right
			else:
				return (node.key, node.value)
		raise IndexError('Out of ranges')

	@staticmethod
	def _is_left(node):
		return node.parent.left and node.parent.left == node

	@staticmethod
	def _is_leaf(node):
		return node.left is None and node.right is None

	def _rotate_right(self, node):
		if not node.parent:
			self._tree = node.left
			node.left.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.left
			node.left.parent = node.parent
		else:
			node.parent.right = node.left
			node.left.parent = node.parent
		bk = node.left.right
		node.left.right = node
		node.parent = node.left
		node.left = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	def _rotate_left(self, node):
		if not node.parent:
			self._tree = node.right
			node.right.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.right
			node.right.parent = node.parent
		else:
			node.parent.right = node.right
			node.right.parent = node.parent
		bk = node.right.left
		node.right.left = node
		node.parent = node.right
		node.right = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	@staticmethod
	def _get_next(node):
		if not node.right:
			return node.parent
		n = node.right
		while n.left:
			n = n.left
		return n

class SegmentTree1:

	def __init__(self, data, default=2 ** 51, func=lambda a, b: a & b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] < key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def binary(x, length):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] >= k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater

def calc(n):
	c = 0
	while n > 0:
		c += 1
		n //= 10
	return c
n = int(input())
k = list(input())
i = len(k) - 1
c = 0
ans = 0
t = 0
cur = 0
while i != -1:
	w = int(k[i])
	if w == 0:
		c += 1
		i -= 1
		continue
	if w * pow(10, c) + cur < n:
		c += 1
		cur += w * pow(10, c - 1)
	else:
		new = w
		t1 = t
		if int(k[i + 1]) == 0:
			if cur == 0:
				t1 -= 1
			y = i + 1
			u = y
			while int(k[u]) == 0:
				t1 += 1
				u += 1
				if u >= len(k):
					break
			while new < n and int(k[y]) == 0:
				new *= 10
				t1 -= 1
				y += 1
				if y >= len(k):
					break
			if new >= n:
				new //= 10
				t1 += 1
		ans += pow(n, t) * cur
		cur = new
		c = calc(new)
		t = t1 + 1
	i -= 1
ans += pow(n, t) * cur
print(ans)


n = int(input())
s = input()
l = len(s)
dp = [[10 ** 20] * l for i in range(l)]
for i in range(l - 1, -1, -1):
	for j in range(l):
		for k in range(i, l):
			if s[i] == '0' and i != k:
				continue
			x = int(s[i:k + 1])
			if x < n:
				if j == 0 and k == l - 1:
					dp[i][j] = min(dp[i][j], x)
				elif j != 0 and k < l - 1:
					dp[i][j] = min(dp[i][j], x * n ** j + dp[k + 1][j - 1])
print(min(dp[0]))


n = int(input())
k = input()

def solve(k, n):
	ans = 0
	exp = 0
	cur_index = len(k)
	while cur_index != 0:
		next_index = cur_index - 1
		while next_index >= 0 and int(k[next_index:cur_index]) < n:
			if k[next_index] != '0' or next_index == cur_index - 1:
				valid_index = next_index
			next_index -= 1
		ans += int(k[valid_index:cur_index]) * n ** exp
		cur_index = valid_index
		exp += 1
	return ans
print(solve(k, n))


n = int(input())
s = input()
ans = 0
cs = ''
cp = 1

def get_digit(s, n):
	for i in range(len(s)):
		if int(s[i:]) < n and s[i] != '0':
			return (int(s[i:]), s[:i])
	return (0, s[:-1])
while s:
	(d, s) = get_digit(s, n)
	ans += d * cp
	cp *= n
print(ans)


n = int(input())
k = int(input())
out = 0
base = 1
while k != 0:
	big = 10000000000
	while k % big >= n and big > 10:
		big //= 10
	out += k % big * base
	base *= n
	cpy = big
	while k % big < cpy // 10 and cpy > 10:
		cpy //= 10
	big = cpy
	k //= big
print(out)


n = input()
k = input()
nums = []
intn = int(n)
l = len(n)
i = len(k)
curl = l
while True:
	if i - curl < 0:
		cur = k[:i]
	else:
		cur = k[i - curl:i]
	if len(cur) > 1 and cur[0] == '0':
		curl -= 1
		continue
	if int(cur) < intn:
		nums.append(int(cur))
		i = i - curl
		curl = l
	else:
		curl -= 1
	if i <= 0:
		break
r = 0
p = 1
for num in nums:
	r += num * p
	p *= intn
print(r)


def powr(a, r):
	if r == 0:
		return 1
	tmp = powr(a, r >> 1)
	tmp = tmp * tmp
	if r & 1:
		tmp *= a
	return tmp
n = int(input(''))
k = str(input())
l = len(k)
dp = [(1e+20, 1e+20) for i in range(l + 1)]
dp[l] = (0, 0)
dp[l - 1] = (int(k[l - 1]), 1)
for i in range(l - 2, -1, -1):
	if k[i] == '0':
		dp[i] = (dp[i + 1][0], dp[i + 1][1] + 1)
		continue
	num = 0
	for j in range(i, l):
		num = num * 10 + int(k[j])
		if num >= n:
			break
		dp[i] = min(dp[i], (dp[j + 1][0] + num * powr(n, dp[j + 1][1]), dp[j + 1][1] + 1))
print(dp[0][0])


b = 0
value = 0
v = ''
b = int(input(''))
v = input('')
vetor = []
aux = ''
while len(v) > 0:
	n = v[-1] + aux
	if int(n) >= b:
		vetor.append(aux)
		if aux[0] == '0' and len(aux) > 1:
			i = 0
			while i < len(aux) - 1:
				if aux[i] == '0':
					v += aux[i]
				else:
					break
				i += 1
		aux = ''
	else:
		aux = v[-1] + aux
		v = v[:-1]
vetor.append(aux)
soma = 0
i = 0
for I in vetor:
	soma += int(I) * b ** i
	i += 1
print(soma)


inf = 10 ** 18 + 1
n = int(input())
num = ['0'] + list(input())[::-1]
T = [inf for i in range(len(num))]
P = [inf for i in range(len(num))]
T[0] = 0
P[0] = -1
for i in range(1, len(num)):
	if num[i] != '0':
		min_pow = inf
		for j in range(0, i):
			if n > int(''.join(num[j + 1:i + 1][::-1])):
				min_pow = min([min_pow, P[j]])
		P[i] = min_pow + 1
		for j in range(0, i):
			if P[j] == min_pow and n > int(''.join(num[j + 1:i + 1][::-1])):
				T[i] = min([T[i], int(''.join(num[j + 1:i + 1][::-1])) * n ** P[i] + T[j]])
	else:
		P[i] = P[i - 1] + 1
		T[i] = T[i - 1]
print(T[len(num) - 1])


(n, k) = (int(input()), input())
ten = []
counter = 1
while k:
	target = k[-counter:]
	if False:
		pass
	elif int(target) >= n and target[0] != '0' and (int(target[1:]) == 0):
		for i in range(1, len(target)):
			if int(target[:-i]) < n:
				ten.extend(list(map(int, target[-i:])))
				if len(target) != 2:
					ten.append(int(target[:-i]))
				else:
					counter -= 1
				break
		k = k[:-counter]
		counter = 0
	elif target == k:
		ten.append(int(target))
		counter = 0
		break
	elif 0 < int(target) < n <= int(k[-(counter + 1):]):
		ten.append(int(target))
		for i in range(len(target)):
			if target[i] != '0':
				counter -= i
				break
		k = k[:-counter]
		counter = 0
	counter += 1
print(sum([n ** i * ten[i] for i in range(len(ten))]))


n = int(input())
k = input()
r = len(k)
a = []
i = len(k) - 1
while i >= 0:
	if k[i] != '0':
		if int(k[i:r]) >= n:
			a.append(int(k[i + 1:r]))
			r = i + 1
			i -= 1
		else:
			i -= 1
	else:
		j = i
		while j >= 0 and k[j] == '0':
			j -= 1
		if int(k[j:r]) >= n:
			if i == r - 1:
				a.append(int(k[i:r]))
				r = i
				i -= 1
			else:
				a.append(int(k[i + 1:r]))
				r = i + 1
				i -= 1
		else:
			i = j - 1
ans = 0
a.append(int(k[0:r]))
for i in range(len(a)):
	ans += a[i] * n ** i
print(ans)


n = int(input())
k = [int(i) for i in input()]
sz = len(k)
dp = [[int(1e+19), -1] for i in range(sz)]
dp.append([0, 1])
for i in range(sz - 1, -1, -1):
	if k[i] == 0:
		dp[i] = [dp[i + 1][0], dp[i + 1][1] * n]
		continue
	tp = 0
	for j in range(i, sz):
		tp = tp * 10 + k[j]
		if tp >= n:
			break
		if dp[i][0] > tp * dp[j + 1][1] + dp[j + 1][0]:
			dp[i] = [tp * dp[j + 1][1] + dp[j + 1][0], dp[j + 1][1] * n]
print(dp[0][0])


base = int(input())
number = input()
n = i = len(number) - 1
ans = power = 0
while n >= 0:
	i = n
	while i >= 0 and int(number[i:n + 1]) < base:
		i -= 1
	while i < n - 1 and number[i + 1] == '0':
		i += 1
	ans += int(number[i + 1:n + 1]) * base ** power
	n = i
	power += 1
print(ans)


n = int(input())
k = int(input())
arr = []
idx = 0
while k > 0:
	while 10 ** idx <= k and k % 10 ** idx < n:
		idx += 1
	if k % 10 ** idx >= n:
		idx -= 1
	while idx > 1 and k % 10 ** idx == k % 10 ** (idx - 1):
		idx -= 1
	arr.append(k % 10 ** idx)
	k //= 10 ** idx
	idx = 0
mul = 1
sm = 0
for item in arr:
	sm += item * mul
	mul *= n
print(sm)


N = input().strip()
K = input().strip()
al = []
while K != '':
	best = 0
	for i in range(len(K)):
		if int(K[i:len(K)]) < int(N) and K[i] != '0' or (K[i] == '0' and i == len(K) - 1):
			best = i
			break
	al.append(K[best:len(K)])
	K = K[0:best]
ans = 0
for i in range(len(al)):
	ans += int(al[i]) * int(N) ** i
print(str(ans) + '\n')