Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

combinatorics

dp

math

*3100

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Unique Strings

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard 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$$$.

Input

The 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.

Output

Print the single integer — the number of unique strings you can achieve performing no more than $$$k$$$ operations, modulo $$$10^9 + 7$$$.

Examples

Input

1 1 0

Output

1

Input

3 1 2

Output

3

Input

5 1 1

Output

3

Input

6 2 2

Output

7

Input

24 3 11

Output

498062

Note

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.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/09/2024 20:56:17 (l1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|