题目描述

定义域为 $[1,n]$ ，内的整数，值域为实数集的函数 $f:{1,2,3 \ldots , n} \rightarrow R$ 又被称为有限序列。
而 $f$ 的交替和定义为 $A(f):= \sum_{k=1}^n (-1)^{k-1} f(k)$ 。
现在我们讨论一种特殊的数列 $L_{n,b}$ 的交替和。
$L_{n,b}$ 是这样生成的：假设序列 $L$ 一开始是“空的”。
之后，按照从小到大的顺序将 $[1,n]$ 中的整数在 $b$ 进制中的表示，从高位到低位逐位“添加”进序列 $L$ 。
最后得到的 $L$ 即为 $L_{n,b}$ 。
举例来说，在 $2$ 进制下 $5$ 表示为 $101$ ，那么 $L_{5,2}$ 即为数列 $1,1,0,1,1,1,0,0,1,0,1$ 。
这是将数 $1,2,3,4,5$ 在 $2$ 进制下的表示 $1,10,11,100,101$ 逐位“添加”的结果。
现在对于给定的整数 $b,n$ ，你需要计算 $A(L_{n,b})$ 的值。

输入格式

输入文件包含一行两个整数 $b,n$ 。

输出格式

输出一个整数表示 $A(L_{n,b})$ 的值。

2 239

-42

数据规模与约定

• 对于 $20\%$ 的数据，满足 $n \le 1000$
• 对于 $100\%$ 的数据，满足 $1 \le n \le 10^{18} , 2 \le b \le 10$ 。

题目来源

PKU 3531