分析：
首先要转换为一棵K度树，有N个权为0的叶子节点，有M个权位1的叶子结点。每个非叶子节点的权值为其所有儿子的权值的平均值。
那么设1的点的深度分别为a1,a2,a3……ama_1,a_2,a_3……a_ma1?,a2?,a3?……am?
0的点深度分别为b1,b2,b3……bnb_1,b_2,b_3……b_nb1?,b2?,b3?……bn?
那么由于其是一颗K度树，所以必须满足：
∑k?ai+∑k?bi=1\sum k^{-a_i}+\sum k^{-b_i}=1∑k?ai?+∑k?bi?=1
忽略0的那几项，剩下的就刚好是根节点的权值，显然，其必然为一个K进制数：
0.c1c2c3c4……cl0.c_1c_2c_3c_4……c_l0.c1?c2?c3?c4?……cl?
这个K进制小数必然满足：∑ci≡M(modK?1)\sum c_i \equiv M(mod\ K-1)∑ci?≡M(mod K?1)且∑(K?ci)≡N(modK?1)\sum (K-c_i) \equiv N(mod\ K-1)∑(K?ci?)≡N(mod K?1)
我们可以尝试构造这个K进制小数。
为了方便起见，我们把这个小数最后一位-1，使得∑k?ai+∑k?bi=1?k?l\sum k^{-a_i}+\sum k^{-b_i}=1-k^{-l}∑k?ai?+∑k?bi?=1?k?l，这样一来，每一位的值都为k?1k-1k?1了。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#define SF scanf
#define PF printf
#define MAXN 2010
#define MOD 1000000007
using namespace std;
typedef long long ll;
ll dp[2][MAXN][2],ans;
int sum[MAXN],now;
int n,m,k;
int main(){
SF("%d%d%d",&n,&m,&k);m--;k--;dp[0][0][0]=1;now=1;for(int i=1;i<=max(n,m)*2;i++){
for(int j=0;j<=n;j++)sum[j+1]=(sum[j-1+1]+dp[now^1][j][0]+dp[now^1][j][1])%MOD;//+1 to prevent overflowfor(int j=0;j<=n;j++){
dp[now][j][0]=(sum[j+1]-sum[j-1+1]+MOD)%MOD; dp[now][j][1]=(sum[j-1+1]-sum[max(0,j-k)-1+1]+MOD)%MOD;}for(int j=0;j<=n;j++)if(j%k==n%k&&(i*k-j)%k==m%k&&(i*k-j)<=m)ans=(ans+dp[now][j][1])%MOD;now^=1;}PF("%lld",ans);
}