Coffee Break 001
コンテスト日時
2021/06/05 (Sa) 17:30 - 20:00

F - Sorting Power Sum

ผักชี
4
s
1024
MB
700

問題文

正整数 $N,M,S$ が与えられます。$N$ 個の $A$ と、$M$ 個の $B$ を横一列に並べたものを列と呼ぶことにします。ある列に対するポイントを以下のように定義します。

  • 全ての $A$ に対する、その $A$ よりも左にある $B$ の個数の和

列としてあり得るものは $\binom{N+M}{N}$ 通りありますが、その全てに対して、列のポイントを $X$ とした時の $S^X$ の総和を求めてください。
ただし、解は非常に大きくなるかもしれないので、$1000000007$ で割った余りを出力してください。

制約

・入力は全て正整数である。
・$1 \le N,M \le 10^5$
・$1 \le S \le 10^{18}$

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $S$

出力

列としてあり得るものは $\binom{N+M}{N}$ 通りありますが、その全てに対して、列のポイントを $X$ とした時の $S^X$ の総和を $1000000007$ で割った余りを出力せよ。

入力例 1
2 3 2
出力例 1
155

例えば、列として $ABBAB$ を考えます。この場合の点数は $0+2=2$ となります。
列としてあり得るものは $10$ 通りありますが、その全てに対してポイントを $X$ とした時の $2^X$ の総和は、$155$ になります。

入力例 2
100 100 2021
出力例 2
483579436
提出
C++23 (g++ 12.2.0)