{"problem":{"name":"Paper Cutting","description":{"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 ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"keyence2019_f"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   $1 \\leq H,W \\leq 10^7$\n*   $1 \\leq K \\leq H + W$\n*   $H, W$ and $K$ are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$H$ $W$ $K$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"keyence2019_f","tags":[],"sample_group":[["2 1 2","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$."],["30 40 50","616365902\n\nBe sure to print the sum modulo $10^9 + 7$."]],"created_at":"2026-03-03 11:01:14"}}