Paper Cutting

有一个$(H+1)\times(W+1)$的网格，网格中有$H$条水平线和$W$条竖直线。 你需要执行$K$次操作，每次沿一条水平线或竖直线将网格切开。定义一次操作的权值为切割后网格被切分的块数。 定义一个操作序列的权值为$K$次操作的权值和。 求所有操作序列的权值之和，答案对$10^9+7$取模。 其中$1\leq H,W\leq 10^7$，$1\leq K \leq H+W$，且$H,W,K$为整数

[problemUrl]: https://atcoder.jp/contests/keyence2019/tasks/keyence2019_f 縦の長さが $ H+1 $，横の長さが $ W+1 $ の長方形の紙が机に置かれています．$ xy $ 座標系を，紙の四隅の座標がそれぞれ $ (0,\ 0) $, $ (W\ +\ 1,\ 0) $, $ (0,\ H\ +\ 1) $, $ (W\ +\ 1,\ H\ +\ 1) $ となるように定めます． この紙は，直線 $ x\ =\ 1,2,...,W $ と直線 $ y\ =\ 1,2,...,H $ に沿って切ることができます．これらの $ H\ +\ W $ 本の直線から $ K $ 本を選び，それらの直線に沿って何らかの順序で一回ずつ紙を切断していくという長さ $ K $ の操作列を考えます． 紙の $ 1 $ 回の切断のスコアを，その直後の時点で存在する紙の破片の個数とします．操作列のスコアは，$ K $ 回すべての切断のスコアの和です． 考えられる全ての長さ $ K $ の操作列のスコアの和を計算してください．この値は非常に大きくなることがあるので，$ 10^9\ +\ 7 $ で割った余りを出力してください．

入力は以下の形式で標準入力から与えられる． > $ H $ $ W $ $ K $

スコアの和を $ 10^9\ +\ 7 $ で割った余りを出力せよ．

2 1 2

34

30 40 50

616365902

### 制約 - $ 1\ \leq\ H,W\ \leq\ 10^7 $ - $ 1\ \leq\ K\ \leq\ H\ +\ W $ - $ H,\ W,\ K $ は整数 ### Sample Explanation 1 直線 $ x\ =\ 1 $ に沿った切断を $ x_1 $，直線 $ y\ =\ 1 $ に沿った切断を $ y_1 $，直線 $ y\ =\ 2 $ に沿った切断を $ y_2 $ と表記します．考えられる $ 6 $ 通りの操作列とそれぞれのスコアは次の通りです． - $ y_1,\ y_2 $: $ 2\ +\ 3\ =\ 5 $ - $ y_2,\ y_1 $: $ 2\ +\ 3\ =\ 5 $ - $ y_1,\ x_1 $: $ 2\ +\ 4\ =\ 6 $ - $ y_2,\ x_1 $: $ 2\ +\ 4\ =\ 6 $ - $ x_1,\ y_1 $: $ 2\ +\ 4\ =\ 6 $ - $ x_1,\ y_2 $: $ 2\ +\ 4\ =\ 6 $ これらの和は $ 34 $ です． ### Sample Explanation 2 スコアの和を $ 10^9\ +\ 7 $ で割った余りを出力することを忘れないでください．