55068 - [NOIP2006] 数列 sequence

通过次数

0

提交次数

0

时间限制 : 1 秒
内存限制 : 128 MB

给定一个正整数 k3\leq k\leq 15),把所有 k 的方幂及所有有限个互不相等的 k 的方幂之和构成一个递增的序列,例如,当 k = 3 时,这个序列是:

1, 3, 4, 9, 10, 12, 13, \ldots

(该序列实际上就是:3^0,3^1,3^0+3^1,3^2,3^0+3^2,3^1+3^2,3^0+3^1+3^2,…

请你求出这个序列的第 N 项的值,用 10 进制数表示。

例如,对于 k = 3N = 100,正确答案应该是 981

输入

两个由空格隔开的正整数 k, N3\leq k\leq 1510\leq N\leq 1000)。

输出

一个正整数。整数前不要有空格和其他符号。

样例

输入

3 100

输出

981

来源

NOIP 2006 普及组 第四题