[AGC005D] ~K Perm Counting

题意翻译

如果一个排列 $P$ 满足对于所有的 $i$ 都有 $|P_i-i|\neq k$,则称排列 $P$ 为合法的。现给出 $n$ 和 $k$,求有多少种合法的排列。 由于答案很大,请输出答案对 $924844033$ 取模的结果。 【数据范围】 $2\leq n\leq 2\times 10^3$,$1\leq k\leq n-1$。

题目描述

[problemUrl]: https://agc005.contest.atcoder.jp/tasks/agc005_d すぬけ君は順列が大好きなので、長さ $ N $ の順列を作ることにしました。 ただしすぬけ君は整数 $ K $ が嫌いなので、以下の条件を満たす順列を作ることにしました。 - 順列を $ a_1,\ a_2,\ ...,\ a_N $ とする。全ての $ i\ =\ 1,2,...,N $ について、 $ |a_i\ -\ i|\ \neq\ K $ を満たす 長さ $ N $ の順列は $ N! $ 通りありますが、そのうち条件をみたすものは何個あるかを求めてください。 ただし答えは非常に大きくなることがあるので、答えを $ 924844033 $ (素数) で割ったあまりを求めてください。

输入输出格式

输入格式


The input is given from Standard Input in the following format: ``` $ N $ $ K $ ```

输出格式


Print the answer modulo $ 924844033 $ .

输入输出样例

输入样例 #1

3 1

输出样例 #1

2

输入样例 #2

4 1

输出样例 #2

5

输入样例 #3

4 2

输出样例 #3

9

输入样例 #4

4 3

输出样例 #4

14

输入样例 #5

425 48

输出样例 #5

756765083

输入样例 #6

3 1

输出样例 #6

2

输入样例 #7

4 1

输出样例 #7

5

输入样例 #8

4 2

输出样例 #8

9

输入样例 #9

4 3

输出样例 #9

14

输入样例 #10

425 48

输出样例 #10

756765083

说明

### 制約 - $ 2\ ≦\ N\ ≦\ 2000 $ - $ 1\ ≦\ K\ ≦\ N-1 $ ### Problem Statement Snuke loves permutations. He is making a permutation of length $ N $ . Since he hates the integer $ K $ , his permutation will satisfy the following: - Let the permutation be $ a_1,\ a_2,\ ...,\ a_N $ . For each $ i\ =\ 1,2,...,N $ , $ |a_i\ -\ i|\ \neq\ K $ . Among the $ N! $ permutations of length $ N $ , how many satisfies this condition? Since the answer may be extremely large, find the answer modulo $ 924844033 $ (prime). ### Constraints - $ 2\ ≦\ N\ ≦\ 2000 $ - $ 1\ ≦\ K\ ≦\ N-1 $ ### Sample Explanation 1 $ (1,\ 2,\ 3) $ , $ (3,\ 2,\ 1) $ の $ 2 $ つが条件を満たす。 ### Sample Explanation 2 $ (1,\ 2,\ 3,\ 4) $ , $ (1,\ 4,\ 3,\ 2) $ , $ (3,\ 2,\ 1,\ 4) $ , $ (3,\ 4,\ 1,\ 2) $ , $ (4,\ 2,\ 3,\ 1) $ の $ 5 $ つが条件を満たす。 ### Sample Explanation 6 $ 2 $ permutations $ (1,\ 2,\ 3) $ , $ (3,\ 2,\ 1) $ satisfy the condition. ### Sample Explanation 7 $ 5 $ permutations $ (1,\ 2,\ 3,\ 4) $ , $ (1,\ 4,\ 3,\ 2) $ , $ (3,\ 2,\ 1,\ 4) $ , $ (3,\ 4,\ 1,\ 2) $ , $ (4,\ 2,\ 3,\ 1) $ satisfy the condition.