题目描述

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

输入格式

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

输出格式

输出一个整数表示 $\red{A( L_n,b)}$的值。

样例

输入样例

2 5

输出样例

1

提示

对于 $\red{20\% }$的数据，满足 $\red{n<=1000 }$。

对于 $\red{100\% }$的数据，满足 $\red{1<=n<=10^{18} ，}$ $\red{2<=b<=10}$。