Problem Description

Consider the following sequence $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}$

Alice decided to use dynamic programming to find $ a_N $. Specifically, she did the following:

1. Prepare an array $ a $
2. Initialize $ a_0 = x, a_1 = y, a_i = 0 (i > 1) $
3. For $i = 2, 3, \ldots, N$, assign $ a_i = a_{i-1} + a_{i-2} $

In the above procedure, step 3. updates $ i $ in ascending order, which correctly finds the value of $ a_N $. However, Alice is unplanned and updated $ i $ in a random order. There are $ (N-1)! $ possible update orders, and for each, you need to find the final value written in $ a_N $ and compute the sum of these values modulo $ 10^9+7 $.

Input Format

The input is given from the standard input in the following format:

$ x $ $ y $ $ N $

Output Format

Output the sum of the final values of $ a_N $ for all update orders modulo $ 10^9+7 $.

Sample Input and Output

Sample Input #1

0 1 3

Sample Output #1

3

Sample Input #2

0 0 5

Sample Output #2

0

Sample Input #3

1 1 6

Sample Output #3

117

Sample Input #4

12345 67890 1000000

Sample Output #4

418969939

Notes/Hints

Constraints

• All inputs are integers
• $0 \le x, y \le 10^9$
• $2 \le N \le 10^6$

Sample Explanation 1

• If $ i $ is updated in the order $ 2, 3 $, the value of $ a_N $ is $ 2 $. If $ i $ is updated in the order $ 3, 2 $, the value of $ a_N $ is $ 1 $. The total is $ 3 $.

Sample Explanation 2

• Regardless of the order of operations, the final value written in $ a_N $ is $ 0 $.

见题面 Input 部分

见题面 Output 部分