F. Unique Stringstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputLet'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.ExamplesInput
1 1 0Output
1
Input
3 1 2Output
3
Input
5 1 1Output
3
Input
6 2 2Output
7
Input
24 3 11Output
498062
NoteIn 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.
1 1 0
1 
['combinatorics', 'dp', 'math', '*3100']