暂无测试数据。

小 Y 这两天学习了幂函数，他在老师的课后练习题中看到了这么一个问题：给定正整数 $n,k$，求函数 $y=x^k-n$ 的零点个数（零点即函数与 $x$ 轴的交点）。

小 Y 一眼就看出了这个问题等价于求方程 $x^k=n$ 的解的个数。

可是他觉得这个问题很没意思，于是稍稍修改了一下这个问题：求方程 $x^k\equiv n\pmod {x+1}$ 的解的个数。

现在轮到你来解决这个问题了。

输入格式

共一行，两个正整数 $n,k$

输出格式

共一行，一个整数 $ans$ 表示解的个数。

数据范围

对于 $50\%$ 的数据，$k=1$

对于 $100\%$ 的数据，$2\le k,n \le 10^{14}$

14 1

3