AT_ttpc2019_j 動的無計画法

[problemUrl]: https://atcoder.jp/contests/ttpc2019/tasks/ttpc2019_j 次の数列 $ a\ =\ (a_0,\ a_1,\ \ldots\ ,\ a_N) $ を考えます。 $ \begin{aligned}\ a_i\ =\ \begin{cases}\ x\ &\ (\ i\ =\ 0\ )\ \\ y\ &\ (\ i\ =\ 1\ )\ \\ a_{i-1}\ +\ a_{i-2}\ &\ (\ \text{otherwise}\ )\ \end{cases}\ \end{aligned} $ アリスは動的計画法を用いて $ a_N $ を求めることにしました。具体的には次のようにしました。 1. 配列 $ a $ を用意する 2. $ a_{0}\ =\ x,\ a_{1}\ =\ y,\ a_{i}\ =\ 0\ (i\ >\ 1) $ と初期化する 3. $ i\ =\ 2,\ 3,\ \ldots\ ,\ N $ に対して、$ a_{i} $ に $ a_{i-1}+a_{i-2} $ を代入する 上記の手順の 3. において $ i $ が小さい順に更新していくと正しい $ a_{N} $ の値が求まります。 しかし、アリスは無計画なので $ i $ を適当な順番で更新しました。 このとき、更新の順番は $ (N-1)! $ 通りありますが、それぞれについて最終的に $ a_{N} $ に書き込まれている値を求め、その合計を $ 10^9+7 $ で割ったあまりを計算してください。

入力は以下の形式で標準入力から与えられる。 > $ x $ $ y $ $ N $

全ての更新の順番における最終的な $ a_{N} $ の値の総和を $ 10^9+7 $ で割った余りを出力せよ。

### 制約 - 入力は全て整数 - $ 0\ \le\ x,\ y\ \le\ 10^9 $ - $ 2\ \le\ N\ \le\ 10^6 $ ### Sample Explanation 1 \- $ i $ を $ 2,\ 3 $ の順に更新すると $ a_{N} $ の値は $ 2 $ に、$ i $ を $ 3,\ 2 $ の順に更新すると $ a_{N} $ の値は $ 1 $ になり、合計は $ 3 $ です。 ### Sample Explanation 2 \- どのような順番で操作を行ったとしても、最終的に $ a_{N} $ に書き込まれている値は $ 0 $ です。