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