問題文

次の数列 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 で割ったあまりを計算してください。

制約

• 入力は全て整数
• 0 \le x, y \le 10^9
• 2 \le N \le 10^6

入力例 1

0 1 3

出力例 1

3

• i を 2, 3 の順に更新すると a_{N} の値は 2 に、i を 3, 2 の順に更新すると a_{N} の値は 1 になり、合計は 3 です。

入力例 2

0 0 5

出力例 2

0

• どのような順番で操作を行ったとしても、最終的に a_{N} に書き込まれている値は 0 です。

入力例 3

1 1 6

出力例 3

117

入力例 4

12345 67890 1000000

出力例 4

418969939