311240: CF1954F. Unique Strings
Description
Let's say that two strings $a$ and $b$ are equal if you can get the string $b$ by cyclically shifting string $a$. For example, the strings 0100110 and 1100100 are equal, while 1010 and 1100 are not.
You are given a binary string $s$ of length $n$. Its first $c$ characters are 1-s, and its last $n - c$ characters are 0-s.
In one operation, you can replace one 0 with 1.
Calculate the number of unique strings you can get using no more than $k$ operations. Since the answer may be too large, print it modulo $10^9 + 7$.
InputThe first and only line contains three integers $n$, $c$ and $k$ ($1 \le n \le 3000$; $1 \le c \le n$; $0 \le k \le n - c$) — the length of string $s$, the length of prefix of 1-s and the maximum number of operations.
OutputPrint the single integer — the number of unique strings you can achieve performing no more than $k$ operations, modulo $10^9 + 7$.
ExamplesInput1 1 0Output
1Input
3 1 2Output
3Input
5 1 1Output
3Input
6 2 2Output
7Input
24 3 11Output
498062Note
In the first test case, the only possible string is 1.
In the second test case, the possible strings are: 100, 110, and 111. String 101 is equal to 110, so we don't count it.
In the third test case, the possible strings are: 10000, 11000, 10100. String 10010 is equal to 10100, and 10001 is equal to 11000.
Output
如果一个字符串a通过循环移位可以得到字符串b，则认为a和b相等。例如，字符串0100110和1100100相等，而1010和1100不相等。
给定一个长度为n的01字符串s，其中前c个字符为1，后n-c个字符为0。每次操作可以将一个0替换为1。求最多进行k次操作后，可以得到多少个独特的字符串。结果对10^9+7取模。
输入输出数据格式：
输入：
第一行包含三个整数n，c和k（1≤n≤3000，1≤c≤n，0≤k≤n-c），分别表示字符串s的长度，前缀1的长度和最大操作次数。
输出：
输出一个整数，表示最多进行k次操作后，可以得到的独特字符串的数量，结果对10^9+7取模。题目大意： 如果一个字符串a通过循环移位可以得到字符串b，则认为a和b相等。例如，字符串0100110和1100100相等，而1010和1100不相等。 给定一个长度为n的01字符串s，其中前c个字符为1，后n-c个字符为0。每次操作可以将一个0替换为1。求最多进行k次操作后，可以得到多少个独特的字符串。结果对10^9+7取模。 输入输出数据格式： 输入： 第一行包含三个整数n，c和k（1≤n≤3000，1≤c≤n，0≤k≤n-c），分别表示字符串s的长度，前缀1的长度和最大操作次数。 输出： 输出一个整数，表示最多进行k次操作后，可以得到的独特字符串的数量，结果对10^9+7取模。