#3762. 种树

现在需要在一个N*M的网格图上种K棵树，树只能种在格子的四个角上，即实际上有(N+1)*(M+1)个位置可以种树。

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

1、同一个位置最多只能种一棵树；

2、这K棵树需要在同一条直线上；

3、这K棵树两两距离都不能小于D。

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