题目内容

小蓝定义了一种字符串生成规则：将正整数 $n$ 表示为 $k$ 进制。设其各位数字从低位到高位依次为 $d_0, d_1, \dots, d_m$，满足 $0 \le d_i < k$ 且 $d_m eq 0$。对于每个 $i$，若 $d_i > 0$，则生成数字 $i+1$ 并重复 $d_i$ 次。将所有生成的数字按 $i$ 从大到小的顺序拼接起来，形成最终结果。

给定 $n$ 和 $k$，请你计算该结果。

约束：$1 \le n \le 10^{18}$，$2 \le k \le 2 \times 10^5$。

输入描述

输入只有一行，包含两个整数 $n$ 和 $k$，用空格分隔。

输出描述

输出一个整数，表示拼接后得到的十进制数。

样例1

输入

6 2

输出

32

说明

将 $n=6$ 表示为 $2$ 进制：$6_{10}=110_2$，低位在前，各位数字依次为 $d_0=0$，$d_1=1$，$d_2=1$。 按 $i$ 从大到小处理：

• $i=2$，$d_2=1>0$，生成数字 $i+1=3$ 并重复 $1$ 次，得到 3；
• $i=1$，$d_1=1>0$，生成数字 $2$ 并重复 $1$ 次，得到 2；
• $i=0$，$d_0=0$，跳过。 将生成的数字按顺序拼接，最终结果为 32。

样例2

输入

10 3

输出

31

说明

将 $n=10$ 表示为 $3$ 进制：$10_{10}=101_3$，低位在前，$d_0=1$，$d_1=0$，$d_2=1$。 按 $i$ 从大到小处理：

• $i=2$，$d_2=1>0$，生成数字 $3$ 并重复 $1$ 次，得到 3；
• $i=1$，$d_1=0$，跳过；
• $i=0$，$d_0=1>0$，生成数字 $1$ 并重复 $1$ 次，得到 1。 拼接后得到 31。

样例3

输入

100 10

输出

3

说明

将 $n=100$ 表示为 $10$ 进制：$100_{10}=100_{10}$，低位在前，$d_0=0$，$d_1=0$，$d_2=1$。 只有 $d_2=1>0$，生成数字 $i+1=3$ 并重复 $1$ 次，得到 3。其余位均为 $0$，跳过。最终结果为 3。

样例4

输入

1 2

输出

1

说明

将 $n=1$ 表示为 $2$ 进制：$1_{10}=1_2$，只有 $d_0=1$。 $d_0>0$，生成数字 $0+1=1$ 并重复 $1$ 次，得到 1。这是最小的边界情况。