~K Perm Counting

AtCoder

IDagc005_d

Time2000ms

Memory256MB

Difficulty—

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$ ## Input The input is given from Standard Input in the following format: $N$ $K$ [samples]

Samples

Input #1

3 1

Output #1

2

$2$ permutations $(1, 2, 3)$, $(3, 2, 1)$ satisfy the condition.

Input #2

4 1

Output #2

5

$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.

Input #3

4 2

Output #3

Input #4

4 3

Output #4

Input #5

425 48

Output #5

756765083

API Response (JSON)

{
  "problem": {
    "name": "~K Perm Counting",
    "description": {
      "content": "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 ea",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "agc005_d"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Snuke loves permutations. He is making a permutation of length $N$.\nSince he hates the integer $K$, his permutation will satisfy the following:\n\n*   Let the permutation be $a_1, a_2, ..., a_N$. For ea...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments