记录编号	388888	评测结果	AAAAAAAAAA
题目名称	[HAOI 2009]逆序对数列	最终得分	100
用户昵称	kZime	是否通过	通过
代码语言	C++	运行时间	0.041 s
提交时间	2017-03-30 07:22:27	内存使用	8.30 MiB

/*kZime*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <cstdlib>
#include <algorithm>
#define MAXN
#define mod 10000
using namespace std;
inline int read() {
	int k = 0, f = 1; char c = getchar();
	for(; !isdigit(c); c = getchar())if(c == '-') f = -1;
	for(; isdigit(c); c = getchar()) k = k * 10 + c - '0';
	return k * f;
}
/*-----------------------------------------------------------------------------*/

int n, k, f[1023][1023], g[1023][1023];

int main() {
#ifndef MYLAB
	freopen("permut.in", "r", stdin);
	freopen("permut.out", "w", stdout);
#else
//	freopen("in.txt", "r", stdin);
#endif

	n = read();

	k = read();

	f[0][0] = 1;

	for(int i = 0; i <= k; i++) g[0][i] = 1;

	for(int i = 1; i <= n; i++) {
		f[i][0] = 1;
		for(int j = 0; j <= k; j++) {
			f[i][j] = (j >= i) ? ((g[i - 1][j] - g[i - 1][j - i] + mod) % mod) : (g[i - 1][j] % mod);
			g[i][j] = (j) ? ((g[i][j - 1] + f[i][j]) % mod) : (f[i][j] % mod);
		}
	}
	
	printf("%d", f[n][k]);
	
	return 0;
}