English · Original
Chinese · Translation
Formal · Original
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.
## Input
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.
## Output
Print a single number, the number of ways, modulo 109 + 7.
[samples]
## Note
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.
有一架飞机，从前往后共有 #cf_span[n] 排座位。将有 #cf_span[m] 名乘客登机。
该飞机在最前部和最后部各有一个入口。
每位乘客都有一个指定的座位，多个乘客可能被分配到同一个座位。乘客将按顺序依次登机，从第 #cf_span[1] 号乘客开始。每位乘客可以独立选择从前门或后门进入飞机。
当一名乘客进入飞机后，他会直接走向自己的指定座位，并尝试坐下。如果该座位已被占用，他会沿着自己进入的方向继续前行，直到找到第一个空座位并坐下。如果他走到行末仍未找到座位，他会生气。
求有多少种方式分配座位并安排登机顺序，使得没有人生气。两种方式不同，当且仅当存在某位乘客在两种方式中选择了不同的入口，或被分配的座位不同。请输出该计数对 #cf_span[109 + 7] 取模的结果。
输入的第一行包含两个整数 #cf_span[n, m] (#cf_span[1 ≤ m ≤ n ≤ 1 000 000])，分别表示座位数和乘客数。
输出一个数字，表示满足条件的方案数，对 #cf_span[109 + 7] 取模。
在这里，我们用乘客被分配的座位编号以及他们进入的入口（"F" 表示前门，"B" 表示后门）来表示一位乘客。
例如，一种合法的方式是 3B, 3B, 3B（即所有乘客都被分配到座位 3 并从后门进入）。另一种合法方式是 2F, 1B, 3F。
一种非法的方式是 2B, 2B, 2B，因为第三位乘客会走到前部仍找不到座位。
## Input
输入的第一行包含两个整数 #cf_span[n, m] (#cf_span[1 ≤ m ≤ n ≤ 1 000 000])，分别表示座位数和乘客数。
## Output
输出一个数字，表示满足条件的方案数，对 #cf_span[109 + 7] 取模。
[samples]
## Note
在这里，我们用乘客被分配的座位编号以及他们进入的入口（"F" 表示前门，"B" 表示后门）来表示一位乘客。例如，一种合法的方式是 3B, 3B, 3B（即所有乘客都被分配到座位 3 并从后门进入）。另一种合法方式是 2F, 1B, 3F。一种非法的方式是 2B, 2B, 2B，因为第三位乘客会走到前部仍找不到座位。
**Definitions**
Let $ n, m \in \mathbb{Z} $ with $ 1 \le m \le n \le 10^6 $.
Let $ S = \{1, 2, \dots, n\} $ be the set of seats, indexed from front (1) to back ($n$).
Let $ P = \{1, 2, \dots, m\} $ be the set of passengers, boarding in order.
Each passenger $ i \in P $ is assigned a seat $ a_i \in S $ and chooses an entrance $ e_i \in \{F, B\} $.
The assignment is a pair $ (A, E) $, where:
- $ A = (a_1, a_2, \dots, a_m) \in S^m $ is the seat assignment sequence,
- $ E = (e_1, e_2, \dots, e_m) \in \{F, B\}^m $ is the entrance choice sequence.
**Constraints**
For each passenger $ i $, upon entering via $ e_i $:
- They walk toward their assigned seat $ a_i $ along the row in the direction dictated by $ e_i $:
- If $ e_i = F $, they walk from seat 1 to seat $ n $.
- If $ e_i = B $, they walk from seat $ n $ to seat 1.
- They occupy the first empty seat encountered **in their walking direction** starting from $ a_i $, continuing until a seat is found.
- If no empty seat is found before reaching the end of the row in their direction, the passenger is angry (invalid configuration).
A configuration $ (A, E) $ is **valid** if no passenger becomes angry.
**Objective**
Count the number of valid pairs $ (A, E) \in S^m \times \{F, B\}^m $, modulo $ 10^9 + 7 $.
API Response (JSON)
{
"problem": {
"name": "D. Airplane Arrangements",
"description": {
"content": "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 h",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF838D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "There is an airplane which has _n_ rows from front to back. There will be _m_ people boarding this airplane.\n\nThis airplane has an entrance at the very front and very back of the plane.\n\nEach person h...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "有一架飞机，从前往后共有 #cf_span[n] 排座位。将有 #cf_span[m] 名乘客登机。\n\n该飞机在最前部和最后部各有一个入口。\n\n每位乘客都有一个指定的座位，多个乘客可能被分配到同一个座位。乘客将按顺序依次登机，从第 #cf_span[1] 号乘客开始。每位乘客可以独立选择从前门或后门进入飞机。\n\n当一名乘客进入飞机后，他会直接走向自己的指定座位，并尝试坐下。如果该座位已被占用，他会...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, m \\in \\mathbb{Z} $ with $ 1 \\le m \\le n \\le 10^6 $. \nLet $ S = \\{1, 2, \\dots, n\\} $ be the set of seats, indexed from front (1) to back ($n$). \nLet $ P = \\{1, 2, \\dots, m\\...",
"is_translate": false,
"language": "Formal"
}
]
}