Description

ys draws a coordinate axis, he wants to know how many ways to move from (0, 0) to (x, y) with exactly k steps. ys is able to move towards 4 directions (up, down, left, right) at each step. Could you help ys to solve the problem? The result could be very large, so the answer must mod 1000000007(10^9 + 7).

Input

There are multiple test cases.(the number of test cases <= 110)

For each test case, There is only one line, which contains three integers x y k.

(0 <= x <= 100000, 0 <= y <= 100000, 0 <= k <= 100000)

Output

For each test case, you should output a integer in a line, which indicates how many ways to move from (0, 0) to (x, y) with k steps (mod 1000000007).

Sample Input

0 3 3
0 1 3
0 2 4
1 1 4

Sample Output

1
9
16
24

Author

ys1988