← 返回题目列表

Codeforces · 838/D

D. 飞机安排

中文机器翻译题面 查看原题

有一架飞机,从前到后有 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,因为第三位乘客会在没有找到座位的情况下到达前面。