有\(n\)个\(x\)和\(m\)个\(y\)，每次选\(k\)个数，删掉它们并加入它们的平均数。
问最后形成的数不同的方案数有多少个。
\(n,m,k\le 3000\)
如果\(x=y\)显然；如果\(x\neq y\)，结果和\(x,y\)的具体取值没有关系。
证明：操作的过程可以用一棵树来表示。设\(x_i,y_i\)分别表示深度。那么最终的取值为\(x\sum k^{-x_i}+y\sum k^{-y_i}\)
假设我们得到了两组不同的\((\{x_i\},\{y_i\})\)，然后列个方程。
两边同时除以\(x\)，现在得到了一个与\(\frac{y}{x}\)有关的一元一次方程。
整理成\(ax=b\)的形式。
如果\(x\)有多个解，当且仅当\(a=b=0\)。显然不可能成立（不然可证两组\((\{x_i\},\{y_i\})\)相等）。
接着发现这个问题中\(x=1\)一定是解。
钦定\(x=0,y=1\)。最终权值为\(\sum k^{-y_i}\)。如果令\(x=y=1\)建一棵同构的树，那么有\(\sum k^{-x_i}+\sum k^{-y_i}=1\)。这启示我们：如果一个状态合法，当且仅当存在\(z\)可以如此表示：\(z=\sum k^{-y_i},1-z=\sum k^{-x_i}\)
假如\(z=\sum_{i>0} c_ik^{-i}\)。如果不进位，\(\sum c_i=m\)，进位后\(\sum c_i\)减少\(k-1\)。所以\(\sum c_i\le m\and \sum c_i=m \pmod {k-1}\)。
类似的计算\(1-z\)的限制，如果小数点最后不为\(0\)的位置为\(len\)，则\(1-z\)的\(\sum c'_i=len(k-1)-\sum c_i+1\)。
最终问题变成了统计多少不同的合法\(\sum c_i\)，直接DP解决。
using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 3005
#define ll long long
#define mo 1000000007
int n,m,k;
ll x,y;
int mxd;
int f[N*2][N][2];
int main(){
freopen("justice.in","r",stdin);
freopen("justice.out","w",stdout);
// freopen("in.txt","r",stdin);
scanf("%d%d%d%lld%lld",&m,&n,&k,&x,&y);
if (x==y){
printf("1\n");
return 0;
}
mxd=(m+n-1)/(k-1);
f[0][0][0]=1;
for (int i=0;i<mxd;++i)
for (int j=0;j<m && j<=i*(k-1);++j)
for (int c=0;c<=1;++c){
if (!f[i][j][c]) continue;
for (int t=0;t<k;++t)
(f[i+1][j+t][t!=0]+=f[i][j][c])%=mo;
}
ll ans=0;
for (int i=1;i<=mxd;++i)
for (int j=1;j<=m && j<=i*(k-1);++j){
int j_=i*(k-1)-j+1;
if ((m-j)%(k-1)==0 && j_<=n && (n-j_)%(k-1)==0)
ans+=f[i][j][1];
}
ans%=mo;
printf("%lld\n",ans);
return 0;
}