假设两个字符串 $$$a$$$ 和 $$$b$$$ 相等,如果你可以通过循环移位字符串 $$$a$$$ 得到字符串 $$$b$$$。例如,字符串 0100110 和 1100100 相等,而 1010 和 1100 则不同。
给你一个长度为$$$n$$$的二进制字符串$$$s$$$。其前 $$$c$$$ 字符为 1-s,最后 $$$n - c$$$ 字符为 0-s。
在一次操作中,可以将一个 0 替换为 1。
计算使用不超过 $$$k$$$ 操作可以获得的唯一字符串的数量。由于答案可能太大,请打印 $$$10^9 + 7$$$ 的模。
输入
第一行也是唯一一行包含三个整数 $$$n$$$、$$$c$$$ 和 $$$k$$$ ($$$1 \le n \le 3000$$$; $$$1 \le c \le n$$$; $$$0 \le k \le n - c$$$) — 字符串 $$$s$$$ 的长度、1-s 前缀的长度以及最大操作次数。
输出
打印单个整数 - 您可以执行不超过 $$$k$$$ 运算而获得的唯一字符串的数量,以 $$$10^9 + 7$$$ 为模。
示例
输入 #1
1 1 0
输出 #1
1
输入 #2
3 1 2
输出 #2
3
输入 #3
5 1 1
输出 #3
3
输入#4
6 2 2
输出#4
7
输入 #5
24 3 11
输出 #5
498062
注意
在第一个测试用例中,唯一可能的字符串是 1。
在第二个测试用例中,可能的字符串是:100、110和111。字符串101等于110,所以我们不计算它。
在第三个测试用例中,可能的字符串为:10000、11000、10100。字符串 10010 等于 10100,10001 等于 11000。