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>
#define L long long
using namespace std;
const int q=924844033;
int n,m,t,x[2010],f[2010][2010][4],g[2010],p;
inline void add(int &a,int b)
{
	a=(a+b)%q;
}
int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	int i,j,k;
	scanf("%d%d",&n,&m);
	t=n/m+1;
	f[1][0][0]=f[1][1][2]=1;
	for(i=1;i<t;i++)
	  for(j=0;j<=i;j++)
	    for(k=0;k<4;k++)
	      if(f[i][j][k])
	        {
	  	     add(f[i+1][j][k>>1],f[i][j][k]);
			 if(!(k&1))
			   add(f[i+1][j+1][k>>1],f[i][j][k]);
			 add(f[i+1][j+1][k>>1|2],f[i][j][k]);
			}
	g[0]=1;
	for(i=1;i<=n%m;i++)
	  for(j=n;j>0;j--)
	    for(k=1;k<=j && k<=t;k++)
	      g[j]=(g[j]+(L)g[j-k]*(f[t][k][0]+f[t][k][1]))%q;
	for(;i<=m;i++)
	  for(j=n;j>0;j--)
	    for(k=1;k<=j && k<t;k++)
	      g[j]=(g[j]+(L)g[j-k]*(f[t-1][k][0]+f[t-1][k][1]))%q;
	x[0]=1;
	for(i=1;i<=n;i++)
	  x[i]=(L)x[i-1]*i%q;
	for(i=0,j=1;i<=n;i++,j*=-1)
	  p=(p+(L)j*g[i]*x[n-i])%q;
	p=(p+q)%q;
	printf("%d\n",p);
	return 0;
}