该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

每年一度的「魔法大陆大赛」在王都盛大举行。来自大陆各地的魔法师们齐聚一堂，经过四个关卡的考验，争夺象征无上荣耀的「魔法之冠」。

今年的大赛设下了四个连续的挑战，每一关都考验着魔法师的智慧、策略与实力。你将作为参赛者，亲身经历这段冒险。

在魔法大陆的第一赛场，有一条传说中的秘径，被称作「流光之途」。

• 若你此刻立于编号为偶数魔塔，大地会裂开一道光之缝隙，将你送往编号为它一半的魔塔。
• 若你立于编号为奇数魔塔，则会有一枚古老的传送水晶爆发光芒，将你抛向编号 $\times 3$ 再 $+1$ 的远方魔塔。

无论旅者从哪座魔塔出发，最终都会被引入一个永恒三塔轮回：$1\to 4\to 2\to 1$。在那里，流光不断闪烁，旅人会无休止地巡游，无法逃离。

魔法学者将这一现象称为「流光咒文」（人类学者称之为“冰雹猜想”或“角谷猜想”）。

形式化描述：任取一个正整数，若它为偶数，则将它除以 $2$；若它为奇数，则将它乘 $3$ 再加上 $1$。反复进行上述运算，经过有限步后，必将进入循环 $1\to 4\to 2\to 1$。

设一位旅者从第一天所在魔塔编号 $a_1$ 出发，记 $a_n$ 为其第 $n$ 天所驻足的魔塔编号，满足递推：

$$a_{n+1}= \begin{cases} \dfrac{a_n}{2}, & \text{if } a_n \text{ is even},\\[6pt] 3a_n+1, & \text{if } a_n \text{ is odd}. \end{cases} $$

给定 $a_1$ 与旅行天数 $m$，请计算这 $m$ 天中旅者驻足的魔塔编号之和

$$a_1+a_2+\cdots+a_m,$$

并将结果对 $10^9+7$ 取模。

---

输入格式

一行两个整数 $a_1,\,m$，分别表示旅者第一天所在的魔塔编号与旅行天数。

输出格式

输出一个整数，表示

$$\left(a_1+a_2+\cdots+a_m\right)\bmod (10^9+7).$$

---

样例

样例 1 输入

3 7

样例 1 输出

48

样例 1 解释

$a_1+\cdots+a_7=3+10+5+16+8+4+2=48$，对 $10^9+7$ 取模仍为 $48$。

---

样例 2 输入

6 15

样例 2 输出

69

样例 2 解释

$S=a_1+\cdots+a_{15}=6+3+10+5+16+8+4+2+1+4+2+1+4+2+1=69$，对 $10^9+7$ 取模仍为 $69$。

---

样例 3 输入

69988 323959

样例 3 输出

1291743

---

样例 4 输入

41829 780561781152365398

样例 4 输出

940121576

---

数据范围

• 对于所有测试点：$1\le a_1\le 10^7$，$1\le m\le 10^{18}$。

测试点编号与约束

测试点	$a_1\le$	$m\le$	$a_1$ 性质
$1$	$10$		无特殊限制
$2,3$	$7\times 10^{4}$	$10^{6}$
$4,5$		$10^{18}$
$6$	$4$		$a_1\in\{1,2,4\}$
$7,8,9,10$	$10^{7}$		无特殊限制