题目描述

现在需要在一个 $n \times m$ 的网格图上种 $k$ 棵树，树只能种在格子的四个角上，即实际上有 $(n+1) \times (m+1)$ 个位置可以种树。

这 $k$ 棵树需要满足以下几个条件：

• 同一个位置最多只能种一棵树；
• 这 $k$ 棵树需要在同一条直线上；
• 这 $k$ 棵树两两距离都不能小于 $d$。

现在请你计算满足条件的种树方案，由于答案可能很大，只需输出它对 $10^9$ 取模的结果。

输入格式

读入四个整数 $k,n,m,d$。

输出格式

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

2 4 4 1

300

数据规模和约定

对于 $100\%$ 的数据，$n,k,d,m \le 1.5 \times 10^3$。

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