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 <algorithm>
#include <cstring>
#include <cstdio>

typedef long long LL;

const int MAXN = 2000;
const int MOD = 924844033;

int N, K;
int Fac[MAXN + 5];

int Cnt;
bool Begin[MAXN * 2 + 5];

int Dp[MAXN * 2 + 5][MAXN * 2 + 5][2];

int main() {
	scanf("%d%d", &N, &K);
	Fac[0] = 1;
	for (int i = 1; i <= N; i++)
		Fac[i] = (LL)Fac[i - 1] * i % MOD;
	for (int i = 1; i <= K; i ++) {
		for (int j = i; j <= N; j += K)
			Begin[++Cnt] = (j == i);
		for (int j = i; j <= N; j += K)
			Begin[++Cnt] = (j == i);
	}
	Dp[0][0][0] = 1;
	for (int i = 1; i <= 2 * N; i++) {
		for (int j = 0; j <= i; j++) {
			Dp[i][j][0] = (Dp[i - 1][j][0] + Dp[i - 1][j][1]) % MOD;
			if (!Begin[i] && j)
				Dp[i][j][1] = Dp[i - 1][j - 1][0];
		}
	}
	int Ans = 0;
	for (int i = 0; i <= N; i++) {
		int tmp = (Dp[N * 2][i][0] + Dp[N * 2][i][1]) % MOD;
		if (i & 1)
			tmp = -tmp;
		Ans = ((Ans + (LL)tmp * Fac[N - i] % MOD) % MOD + MOD) % MOD;
	}
	printf("%d", Ans);
}