9999010 - 数学,很美妙吧

给定三个正整数 n, m, k,考虑所有大小为 k 的可重集合 a1, a2...ak,要求 ∑k i=1 ai = n,定义这样一个集 合的权值为: ∑k i=1 a m i 请求出所有满足条件的可重集合的权值之和,由于答案可能过大,你只需要输出答案对 109 + 7 取模的 结果。

输入

第一行三个整数 n, k m。

输出

共一行,一个非负整数表示答案对 109 + 7 取模的结果。

样例

输入

5 2 3

输出

100
时间限制 1 秒
内存限制 512 MB
统计
上一题 下一题