← 返回题目列表

Codeforces · 285/E

E. 排列中的位置

中文机器翻译题面 查看原题

排列 p 是整数 p1, p2, ..., pn 的有序集合,由 n 个不同的正整数组成,每个不超过 n。我们将排列 p 的第 i 个元素表示为 pi。我们将数字 n 称为排列 p1、p2、...、pn 的大小或长度。

我们称排列 p1, p2, ..., pn 中的位置 i (1 ≤ i ≤ n) 为好,如果 |p[i] - i| = 1. 计算大小为 n 且正好有 k 个好位置的排列数。打印答案模 1000000007 (109 + 7)。

输入

单行包含两个空格分隔的整数 n 和 k (1 ≤ n ≤ 1000, 0 ≤ k ≤ n)。

输出

打印长度为 n 的排列数,其中恰好有 k 个好位置以 1000000007 (109 + 7) 为模。

示例

输入 #1

1 0

输出 #1

1

输入 #2

2 1

输出 #2

0

输入 #3

3 2

输出 #3

4

输入#4

4 1

输出#4

6

输入 #5

7 4

输出 #5

328

注意

大小为 1 的唯一排列有 0 个好位置。

排列 (1, 2) 有 0 个好位置,排列 (2, 1) 有 2 个位置。

大小 3 的排列:

1. (1, 2, 3) — 0 个位置
2. $$(1,3,2)$$ — 2 个位置
3. $$(2,1,3)$$ — 2 个位置
4. $$(2,3,1)$$ — 2 个位置
5. $$(3,1,2)$$ — 2 个位置
6. (3, 2, 1) — 0 个位置