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:
/* In the name of Allah */
#include<bits/stdc++.h>
using namespace std;

const int N = 2e3 + 5, P = 924844033;
int fact[N] = {1}, dp[N][N], cnt[N] = {1};

int main() {
	int n, k;
	cin >> n >> k;
	for (int i = 0; i <= n; i++) {
		for (int j = dp[i][0] = 1; j <= i; j++)
			dp[i][j] = (dp[i - 1][j] + dp[i - 2][j - 1]) % P;
		fact[i + 1] = (i + 1LL) * fact[i] % P;
	}
	for (int i = 0, s = 0; i < k; i++) {
		int x = (n + k - i - 1) / k;
		for (int j = (s += (x + 1) / 2); ~j; j--) {
			int ans = 0;
			for (int k = max(j - s + (x + 1) / 2, 0); k <= min((x + 1) / 2, j); k++)
				(ans += 1LL * cnt[j - k] * dp[x][k] % P) %= P;
			cnt[j] = ans;
		}
		for (int j = (s += x / 2); ~j; j--) {
			int ans = 0;
			for (int k = max(j - s + x / 2, 0); k <= min(x / 2, j); k++)
				(ans += 1LL * cnt[j - k] * dp[x][k] % P) %= P;
			cnt[j] = ans;
		}
	}
	int ans = 0;
	for (int i = 0; i <= n; i++)
		(ans += (i & 1? -1LL: 1LL) * cnt[i] * fact[n - i] % P) %= P;
	cout << (ans + P) % P;
}