Persecution Problem

X has a total of n+m numbers: n copies of 1 and m additional numbers whose values can be chosen arbitrarily by X before any operation. There are k persons with numbers from 1 to k. X can "persecute" a person if and only if he can select some of the numbers in his hand whose sum equals the target person’s number. (Note that the numbers are not consumed after use.)

X will try to persecute persons starting from person 1, one by one, in order. Being exceptionally wicked, X can choose the m numbers optimally. Meanwhile, one of the persons is his friend Z, and Z is very worried. You are to tell him the maximum count of consecutive persons (starting from person 1) that can be persecuted by X. Since the answer can be huge, output it modulo \(10^9+7\).

Observation: With n copies of 1, one can represent all numbers in the range \([0, n]\). Moreover, by choosing the extra coin as \(n+1\) (i.e. \(X+1\) where \(X\) is the current reachable sum) in each of the m steps, the maximum representable number becomes

[ T = 2^m\cdot (n+1) - 1. ]

Since there are only k persons, the final answer is:

[ answer = \min\Big(k,, 2^m\cdot (n+1)-1\Big)\pmod{10^9+7}. ]

inputFormat

The input consists of a single line containing three space-separated integers: n, m, and k.

outputFormat

Output a single integer — the maximum number of consecutive persons (from person 1) that can be persecuted modulo \(10^9+7\).

sample

3 1 10

7