种树

时间限制:10s      空间限制:512MB

题目描述

现在需要在一个N*M的网格图上种K棵树,树只能种在格子的四个角上,即实际上有(N+1)*(M+1)个位置可以种树。
这K棵树需要满足以下几个条件:
1、同一个位置最多只能种一棵树;
2、这K棵树需要在同一条直线上;
3、这K棵树两两距离都不能小于D。
现在请你计算满足条件的种树方案,由于答案可能很大,只需输出它对10^9取模的结果。


输入格式

读入四个整数K,N,M,D。


输出格式

输出仅一个整数,表示种树方案数对10^9取模的结果。


样例输入

2 4 4 1

样例输出

300

提示

N,K,D,M<=1500

此题存在版权,故不再支持提交,保留在此只供大家参考题面! 望见谅!


题目来源

没有写明来源