题目描述

【假如我们相见，肯定能一眼认出彼此。】

【重要的人，不能忘记的人。绝对不能忘的人。就算我不记得你的名字，我也会一直一直拼命的寻找你。】

【那么，如果你能答对下面的问题，就给你一次见面的机会——】

现在，三叶的面前有$n$个相同的白色小球，$m$个相同的黑色小球。三叶需要将这些小球排成一排，使得任意一段连续的小球中，白色小球和黑色小球的数量之差的绝对值不超过$k$。

三叶需要回答出不同的合法排列方案数对 $1e9 + 7$ 取模后的结果。

输入格式

一行，三个正整数，分别表示$n, m, k$。

输出格式

一行一个整数表示方案数 mod $1e9 + 7$ 的结果。

2 2 1

2

19 12 2

0

11 14 4

485072

样例解释

仅有下列两种：

• 白 黑 白 黑
• 黑 白 黑 白

数据规模与约定

对于$30\%$的数据，$1\le n,m \le 20$；

对于另外$20\%$的数据，$k = 1$；

对于$100\%$的数据，$1 \le n,m \le 150, 1\le k \le 20$。

大样例

大样例下载