In a strange kingdom, there are N months in one year and there are M days in one month. A day in a year of the Kingdom can be represented by a pair (x, y) where 1 ≤ x ≤ N denotes the month and 1 ≤ y ≤ M denotes the day.

A nonempty set of days S is given. Charlotte's birthday is one of the elements of S. Alice, Bob and David know this fact but they didn't know any other information about her birthday. Let's denote Charlotte's birthday as (c_x, c_y).

Charlotte tells Alice the value of c_x and tells Bob the value of c_y.
After that, the following exchange happened exactly L times :

Alice says that she does not know Charlotte's birthday after hearing the last statement (if any) and Bob says that he does not know Charlotte's birthday after Alice's last statement.

After the above happens L times, Alice says that she knows Charlotte's birthday (i.e. she figured out the value of c_y). After hearing that, Bob says that he knows Charlotte's birthday as well (i.e. he figured out the value of c_x. Note that he might also have figured out Charlotte's birthday before Alice's statement). Finally, after hearing both statements, David says that he knows Charlotte's Birthday (i.e. he figured out both values c_x, c_y, possibly before some statements are made).

Assume that all the people are perfect logicians and do not lie.

Among the 2^NM - 1 possible nonempty sets of days S, how many of them are there such that the scenario above is possible, modulo 10⁹ + 7?

The input contains three space-separated integers, N, M, L (1 ≤ N, M, L ≤ 30).

Output a single integer, the answer to the problem.

3 3 1

18