Перестановкой 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).
Примечание
Единственная перестановка размера 1 имеет 0 хороших позиций.
Перестановка (1, 2) имеет 0 хороших позиций, а перестановка (2, 1) — 2 позиции.
Перестановки размера 3:
- (1, 2, 3) — 0 позиций
-
— 2 позиции -
— 2 позиции -
— 2 позиции -
— 2 позиции - (3, 2, 1) — 0 позиций