Перестановкой p называется упорядоченный набор чисел p1, p2, ..., pn, состоящий из n различных целых положительных чисел, каждое из которых не больше чем n. Обозначим i-ый элемент перестановки p через pi. Число n будем называть размером или длиной перестановки p1, p2, ..., pn.
Назовем позицию i (1 ≤ i ≤ n) в перестановке p1, p2, ..., pn хорошей, если |p[i] - i| = 1. Посчитайте количество перестановок размера n с ровно k хорошими позициями. Ответ выведите по модулю 1000000007 (109 + 7).
Выходные данные
Выведите количество перестановок размера n с ровно k хорошими позициями по модулю 1000000007 (109 + 7).
Примечание
Единственная перестановка размера 1 имеет 0 хороших позиций.
Перестановка (1, 2) имеет 0 хороших позиций, а перестановка (2, 1) — 2 позиции.
Перестановки размера 3:
- (1, 2, 3) — 0 позиций
-
— 2 позиции -
— 2 позиции -
— 2 позиции -
— 2 позиции - (3, 2, 1) — 0 позиций
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 0
|
1
|
|
2
|
2 1
|
0
|
|
3
|
3 2
|
4
|
|
4
|
4 1
|
6
|
|
5
|
7 4
|
328
|