Lindra has found the formula to eternal life! Unfortunately, they have also proved that no closed form exists, and therefore they are not too sure how to solve it. The formula is recursive, of the form ~F(0) = a, F(1) = b, F(n) = a \times F_{n-1} + b \times F_{n-2}~. If they are able to find the value of ~F(k)~, Lindra will surely be able to achieve immortality. As Indra's PHD supervisor, can you help them find this value?

Since this value can be quite large, output it modulo 1000000007.

Input Format

The input will consist of the three integers from the description on one line, ~a~, ~b~ and ~k~.

Output Format

The output should consist of a single integer, the value of ~F(k)~ modulo ~1e9+7~.

Sample Input

1 2 4

Sample Output

16

Sample Explanation

This sample corresponds to the powers of two. F(0) = 1, F(1) = 2, F(2) = 4, F(3)=8, F(4)=16, etc

Constraints

~1 \le a,b \le 1e3~

~1 \le k \le 1e5~