我们定义自然数上的函数 $f$ 为：

$$f(x) = \begin{cases} x/2, & \text{若 } x \text{ 为偶数}, \\ 3x + 1, & \text{若 } x \text{ 为奇数}. \end{cases}$$

令 $g(x)$ 为将 $f$ 自身迭代 $k$ 次的结果：

$$g(x) = \underbrace{f(f(\dots f}_{k \text{ 次}}(x)\dots)).$$

你的任务是给定 $N$ 和 $k$，计算以下和：

$$S = \sum_{x=1}^{N} g(x) \pmod{10^9 + 7}.$$

输入格式

一行，包含两个整数 $N$ 和 $k$ ($1 \le N \le 10^{12}$, $0 \le k \le 32$)。

输出格式

输出一个数字，即和 $S$ 对 $10^9 + 7$ 取模后的值。

样例

样例输入 1

10 2

样例输出 1

73

样例输入 2

999888777666 1

样例输出 2

990122835

说明

在第一个样例中，函数 $g(i)$ 对于连续的 $i$ 的值分别为：2, 4, 5, 1, 8, 10, 11, 2, 14, 16。它们的和为 73。

在第二个样例中，$S = 874805371740356549439861$。