Beautiful Grid Patterns

Wolfycz adores grid diagrams. He wishes to paint some black cells on an N×M grid where each column contains exactly one black cell. However, in order to make the pattern appealing, the black cells must be connected in a downward fashion when moving from left to right.

There are two variations of what is considered a "beautiful grid":

• Non-decreasing condition: For every column i (with 2 ≤ i ≤ M), if the black cell in column i is in row a_i and in column i-1 is in row a_{i-1}, then \[ a_i \ge a_{i-1} \] The total number of valid grids in this case is \(\binom{N+M-1}{M}\).
• Strictly increasing condition: For every column i (with 2 ≤ i ≤ M), the condition is \[ a_i > a_{i-1} \] In this case, if \(N < M\) the answer is 0, otherwise the total number of grids is \(\binom{N}{M}\).

You are given three integers N, M, and a mode indicator. When mode = 0, apply the non-decreasing condition; when mode = 1, apply the strictly increasing condition.

Two grids are considered different if and only if there exists at least one column where the row number of the black cell differs.

inputFormat

The input consists of a single line containing three integers: N, M, and mode (where mode = 0 means the non-decreasing condition, and mode = 1 means the strictly increasing condition).

outputFormat

Output a single integer representing the number of beautiful grids that Wolfycz can draw.

sample

3 2 0

6