Problem: 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


Output

Print the answer modulo 924844033.

Examples

Input

3 1


Output

2


Input

4 1


Output

5


Input

4 2


Output

9


Input

4 3


Output

14


Input

425 48


Output

756765083

Solution (in CPP):

Solution:
#include <bits/stdc++.h>

const int P = 924844033;
const int N = 2010;

long long jc[N], g[N << 1], f[N << 1][N][2], cnt;

int main() {

  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
    
  int n, k;
  std::cin >> n >> k;
   
  jc[0] = 1;
  for (int i = 1; i <= n; ++i) jc[i] = (jc[i - 1] * i) % P;
  for (int i = 1; i <= k; ++i) {
    for (int j = i; j <= n; j += k) g[++cnt] = (i == j);
    for (int j = i; j <= n; j += k) g[++cnt] = (i == j);
  } 
  f[0][0][0] = 1;
  for (int i = 1; i <= cnt; ++i) {
    for (int j = 0; j <= std::min(i, n); ++j) {
      f[i][j][0] = (f[i - 1][j][1] + f[i - 1][j][0]) % P;
      if (!g[i]) f[i][j][1] = f[i - 1][j - 1][0];
    }
  } 
  long long ans = 0;
  for (int i = 0; i <= n; ++i) {
    long long tmp = (f[cnt][i][0] + f[cnt][i][1]) % P;
    tmp = (tmp * jc[n - i]) % P;
    if (i & 1) ans = (ans - tmp + P) % P;
    else ans = (ans + tmp) % P;
  }
  std::cout << ans << '\n';
       
  return 0;
}