CF838D.Airplane Arrangements

There is an airplane which has n rows from front to back. There will be m people boarding this airplane.

This airplane has an entrance at the very front and very back of the plane.

Each person has some assigned seat. It is possible for multiple people to have the same assigned seat. The people will then board the plane one by one starting with person 1. Each person can independently choose either the front entrance or back entrance to enter the plane.

When a person walks into the plane, they walk directly to their assigned seat and will try to sit in it. If it is occupied, they will continue walking in the direction they walked in until they are at empty seat - they will take the earliest empty seat that they can find. If they get to the end of the row without finding a seat, they will be angry.

Find the number of ways to assign tickets to the passengers and board the plane without anyone getting angry. Two ways are different if there exists a passenger who chose a different entrance in both ways, or the assigned seat is different. Print this count modulo 109 + 7.

一架飞机从前到后共有 $n$ 排座位。将有 $m$ 名乘客登机。

该飞机在机舱最前部和最后部各有一个入口。

每名乘客均被分配了一个指定座位。允许多名乘客被分配到同一座位。乘客将按编号顺序依次登机，即从第 1 号乘客开始。每位乘客可独立选择从前端入口或后端入口登机。

当一名乘客进入飞机后，会直接走向其被分配的座位，并尝试坐在该座位上。若该座位已被占用，则该乘客将继续沿其进入方向（即从前端进入则继续向后走，从后端进入则继续向前走）行走，直至找到一个空座位——他将选择沿此方向遇到的第一个空座位坐下。若走到该方向尽头仍未找到空座位，则该乘客会生气。

求使得所有乘客均不生气的座位分配方案与登机方式的总数。两种方案被视为不同，当且仅当存在某位乘客，在两种方案中所选入口不同，或被分配的座位不同。请输出该总数对 $10^9 + 7$ 取模的结果。

The first line of input will contain two integers n, m (1 ≤ m ≤ n ≤ 1 000 000), the number of seats, and the number of passengers, respectively.

输入的第一行包含两个整数 $n$ 和 $m$（$1 ≤ m ≤ n ≤ 1 000 000$），分别表示座位数和乘客数。

Print a single number, the number of ways, modulo 109 + 7.

输出一个整数，即方案数对 $10^9 + 7$ 取模的结果。

Here, we will denote a passenger by which seat they were assigned, and which side they came from (either "F" or "B" for front or back, respectively).

For example, one valid way is 3B, 3B, 3B (i.e. all passengers were assigned seat 3 and came from the back entrance). Another valid way would be 2F, 1B, 3F.

One invalid way would be 2B, 2B, 2B, since the third passenger would get to the front without finding a seat.

此处，我们将用乘客被分配的座位号及其进入方向（“F”表示从前门进入，“B”表示从后门进入）来表示一名乘客。

例如，一种合法的安排方式是：3B、3B、3B（即所有乘客均被分配到 3 号座位，且均从后门进入）。另一种合法的安排方式是：2F、1B、3F。

一种非法的安排方式是：2B、2B、2B，因为第三名乘客在到达前门时将无法找到空座位。