← 返回题目列表

Codeforces · 1954/F

F. 独特的字符串

中文机器翻译题面 查看原题

假设两个字符串 $$$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。