Unique Strings

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

若字符串 $b$ 可以由字符串 $a$ 经过若干次循环移位得到，则称 $a$ 与 $b$ 等价。例如，0100110 与 1100100 等价，而 1010 与 1100 不等价。

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

一次操作可以把一个 0 改为 1。求至多进行 $k$ 次操作后，最多能得到多少个两两不等价的字符串。答案对 $10^9+7$ 取模。

输入格式

一行三个整数 $n,c,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\le n\le3000$，$1\le c\le n$，$0\le k\le n-c$。

每个测试点独立计分。

说明

对于样例 2，可得到 100、110 和 111 三类。101 与 110 循环等价，因此不重复计数。