406089: GYM102263 K Smart Strategies

Jaber loves video games, his favorite game is DS:GO, unfortunately he's very bad at it, that's why he decided to quit competitive programming and train for DS:GO instead.

Maps in DS:GO can be seen as a grid with $$$n$$$ rows and $$$m$$$ columns, Jaber believed that in order to get better he have to fully explore the maps of the game, so he decided to build a strategy for exploring the maps.

In order to build a strategy, for each cell in the map except for the bottom right cell he labels it either with a go right sign $$$\rightarrow$$$ or a go down sign $$$\downarrow$$$, so a strategy can be described as a grid with $$$\rightarrow$$$ and $$$\downarrow$$$ sings(note that he chooses all the signs in the bottom row as $$$\rightarrow$$$ and all the signs in the rightmost column as $$$\downarrow$$$).

To fully explore the map using a strategy he picks a cell, then start the game in that cell, then move using the signs($$$\rightarrow$$$ for right and $$$\downarrow$$$ for down) until reaching the bottom right cell, after that if he visited all cells then he's done training with this map, otherwise he picks another cell, then restarts the game in that cell, repeating that until all cells are visited.

Jaber want's to explore maps as fast as possible, that's why when using a strategy he always chooses the starting cells such that he restarts the game minimum number of times. Now Jaber is wondering how many strategies are there such that the minimum number of times he will start the game is exactly $$$x$$$, since Jaber quit competitive programming, he gave this task to you, calculate the answer module $$$10^9+7$$$.

A single line containing three space separated integers $$$n,m,x$$$($$$1\le n,m \le 100, 1 \le x \le nm$$$).

A single integer containing the answer module $$$10^9+7$$$.

2 3 3

2

3 3 9

0

In the first example, the following are the 2 strategies.