这一天小G被辅导员派来东区寝室查寝，他想到一种查寝的方法，每次查完一个寝室后进行一次操作来确定下次要查的寝室号。（假设东区巨大无比 寝室号没有上限）

该操作为：下次查的寝室号=目前的寝室号+目前寝室号的最大奇因子 (包括它本身）

小G太懒了，他想让你帮他算出他经过 $k$ 次操作后他要查的寝室号是多少。

他要进行 $1$ 轮查寝，首先他确定第一次查寝的寝室号 $n$ ，他想知道经过 $k$ 次操作后要查的寝室号是多少(由于房号可能特别大，你需要让答案对 $1000000007$ 取模)。

注：只对最终结果取模，而不是在每次操作结束后对房间号取模。

输入仅两个数字，第一个数字输入此轮第一次查寝的寝室号 $n$ 第二个数字输入小G进行的操作次数 $k$ 。

保证 $1 \le n \le 1000$ ; $1 \le k \le 500000$ 。

输出一个寝室号 $ans$，表示经过 $k$ 次操作后小G要查的寝室号。答案对 $1000000007$ 取模。

第一次查寝的寝室号为 $3$ ,共进行 $4$ 次操作，查寝过程为：$3\to 6\to 9\to 18\to 27$。故进行 $4$ 次操作后要查的寝室号为 $27$。