Stock Price Sequence

During a period of K days, a stock's price always remains a positive integer not exceeding N. On day 1, any price between 1 and N is allowed. For days 2 through K, the price is strictly higher than the previous day and the increase on each day, i.e. \(d_i = p_i - p_{i-1}\), satisfies \(1 \le d_i \le M\). It is also given that \(M(K-1) < N\), which guarantees that there is at least one valid sequence. Given these constraints, compute the total number of possible stock price sequences over \(K\) days.

The mathematical formulation is as follows: Let the sequence be \(p_1, p_2, \ldots, p_K\) with \(p_1 \in [1, N]\) and for \(i \ge 2\), \(1 \le p_i - p_{i-1} \le M\). A sequence is valid if \(p_1 + \sum_{i=2}^{K} (p_i - p_{i-1}) \le N\). Equivalently, if we denote \(S = \sum_{i=2}^{K}(p_i-p_{i-1})\) with each term in \([1, M]\), then the number of valid sequences is given by:

[ \sum_{S = K-1}^{\min(M(K-1),N-1)} f(S) \times (N - S), ]

where \(f(S)\) is the number of ways to obtain the sum \(S\) with \(K-1\) numbers each between 1 and \(M\). Note that when \(K = 1\) (i.e. only one day), the answer is simply \(N\).

inputFormat

The input consists of a single line containing three positive integers:

1. N — the maximum possible stock price.
2. M — the maximum possible daily increase.
3. K — the number of days under consideration.

It is guaranteed that \(M(K-1) < N\).

outputFormat

Output a single integer — the number of valid stock price sequences over \(K\) days.

sample

10 2 3

28