Airplane Arrangements

앞에서 뒤까지 n개의 열이 있는 비행기가 있다. 이 비행기에는 m명의 사람이 탑승한다.

이 비행기에는 기체의 맨 앞과 맨 뒤에 출입구가 있다.

각 사람에게는 지정된 좌석이 있다. 여러 사람에게 같은 좌석이 지정될 수도 있다. 사람들은 승객 1부터 한 명씩 차례로 비행기에 탑승한다. 각 사람은 다른 사람과 독립적으로 앞쪽 출입구와 뒤쪽 출입구 중 하나를 선택해 비행기에 들어갈 수 있다.

어떤 사람이 비행기에 들어오면 지정된 좌석까지 곧장 걸어가 그 자리에 앉으려고 한다. 그 좌석이 이미 차 있다면, 빈 좌석에 도달할 때까지 자신이 걸어오던 방향으로 계속 걸어가며, 찾을 수 있는 가장 이른 빈 좌석에 앉는다. 좌석을 찾지 못한 채 열의 끝에 도달하면 화를 낸다.

누구도 화내지 않도록 승객들에게 표를 배정하고 비행기에 탑승시키는 방법의 수를 구하라. 두 방법에서 서로 다른 출입구를 선택한 승객이 존재하거나 지정된 좌석이 다르면, 두 방법은 서로 다르다. 이 수를 109 + 7로 나눈 나머지를 출력한다.

입력의 첫 번째 줄에는 각각 좌석의 수와 승객의 수를 나타내는 두 정수 n, m (1 ≤ m ≤ n ≤ 1 000 000)이 주어진다.

방법의 수를 109 + 7로 나눈 나머지인 하나의 수를 출력한다.

여기서는 승객을 지정받은 좌석과 들어온 쪽으로 나타낸다(앞쪽과 뒤쪽은 각각 "F"와 "B"로 나타낸다).

예를 들어 유효한 방법 중 하나는 3B, 3B, 3B이다(즉, 모든 승객에게 좌석 3이 지정되었고 모두 뒤쪽 출입구로 들어왔다). 또 다른 유효한 방법은 2F, 1B, 3F이다.

유효하지 않은 방법 중 하나는 2B, 2B, 2B이다. 세 번째 승객이 좌석을 찾지 못한 채 앞쪽에 도달하기 때문이다.