3284 - 不等式

有M个未各数X1,X2....Xm,求满足以下条件不等式的 正整数解 1:1<=i<=N,Xi<=t 2:X1+X2+...+Xm<=s

输入

一行四个数S,T,N,M S<=10^18,N<=10^9,N*T<=S,m-n<=1000

输出

输出方案数Mod 10^9+7

样例

输入

5 2 2 3

输出

8
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题