有一架飞机,从前到后有 n 排。将有 m 人登上这架飞机。
这架飞机的最前面和最后面都有一个入口。
每个人都有一些分配的座位。多个人可以拥有相同的指定座位。然后,从1号人开始,依次登机。每个人可以自主选择从前门或后门进入飞机。
当一个人走进飞机时,他们会直接走到指定的座位并尝试坐在里面。如果座位被占用,他们将继续朝他们走进的方向行走,直到找到空座位——他们将占据他们能找到的最早的空座位。如果他们排到最后没有找到座位,他们会生气。
找出多种方式给乘客分配机票并在没有人生气的情况下登机。如果有乘客在两种方式中选择了不同的入口,或者分配的座位不同,则两种方式是不同的。打印此计数以 109 + 7 为模。
输入
输入的第一行将包含两个整数 n、m (1 ≤ m ≤ n ≤ 1 000 000),分别是座位数和乘客数。
输出
打印单个数字,数的方式,模 109 + 7。
示例
输入 #1
3 3
输出 #1
128
注意
在这里,我们将表示乘客被分配到哪个座位,以及他们来自哪一侧(“F”或“B”分别代表前面或后面)。
例如,一种有效的方式是 3B、3B、3B(即所有乘客都被分配到座位 3 并从后门进入)。另一种有效的方式是 2F、1B、3F。
一种无效的方式是 2B,2B,2B,因为第三位乘客会在没有找到座位的情况下到达前面。