种树
时间限制：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
此题存在版权，故不再支持提交，保留在此只供大家参考题面！ 望见谅！
题目来源
没有写明来源