{"raw_statement":[{"iden":"problem statement","content":"There is a rectangular sheet of paper with height $H+1$ and width $W+1$. We introduce an $xy$\\-coordinate system so that the four corners of the sheet are $(0, 0)$, $(W + 1, 0)$, $(0, H + 1)$ and $(W + 1, H + 1)$.\nThis sheet can be cut along the lines $x = 1,2,...,W$ and the lines $y = 1,2,...,H$. Consider a sequence of operations of length $K$ where we choose $K$ of these $H + W$ lines and cut the sheet along those lines one by one in some order.\nLet the score of a cut be the number of pieces of paper that exist just after the cut. The score of a sequence of operations is the sum of the scores of all of the $K$ cuts.\nFind the sum of the scores of all possible sequences of operations of length $K$. Since this value can be extremely large, print the number modulo $10^9 + 7$."},{"iden":"constraints","content":"*   $1 \\leq H,W \\leq 10^7$\n*   $1 \\leq K \\leq H + W$\n*   $H, W$ and $K$ are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$H$ $W$ $K$"},{"iden":"sample input 1","content":"2 1 2"},{"iden":"sample output 1","content":"34\n\nLet $x_1$, $y_1$ and $y_2$ denote the cuts along the lines $x = 1$, $y = 1$ and $y = 2$, respectively. The six possible sequences of operations and the score of each of them are as follows:\n\n*   $y_1, y_2$: $2 + 3 = 5$\n*   $y_2, y_1$: $2 + 3 = 5$\n*   $y_1, x_1$: $2 + 4 = 6$\n*   $y_2, x_1$: $2 + 4 = 6$\n*   $x_1, y_1$: $2 + 4 = 6$\n*   $x_1, y_2$: $2 + 4 = 6$\n\nThe sum of these is $34$."},{"iden":"sample input 2","content":"30 40 50"},{"iden":"sample output 2","content":"616365902\n\nBe sure to print the sum modulo $10^9 + 7$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}