CF1954F.Unique Strings

我们称两个字符串 $a$ 和 $b$ 是相等的，如果可以通过循环移位字符串 $a$ 得到字符串 $b$。例如，字符串 0100110 和 1100100 是相等的，而 1010 和 1100 则不相等。

给定一个长度为 $n$ 的二进制字符串 $s$，其前 $c$ 个字符为 1，后 $n-c$ 个字符为 0。

每次操作，你可以将一个 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 的长度以及最多操作次数。

输出一个整数，表示在不超过 $k$ 次操作内可以得到的不同字符串的数量，对 $10^9+7$ 取模。

在第一个测试用例中，唯一可能的字符串是 1。

在第二个测试用例中，可能的字符串有：100、110 和 111。字符串 101 与 110 是循环等价的，因此不计入。

在第三个测试用例中，可能的字符串有：10000、11000、10100。字符串 10010 与 10100 循环等价，10001 与 11000 循环等价。

由 ChatGPT 4.1 翻译