Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

No tag edit access

B. Jzzhu and Sequences

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputJzzhu has invented a kind of sequences, they meet the following property:

You are given *x* and *y*, please calculate *f*_{n} modulo 1000000007 (10^{9} + 7).

Input

The first line contains two integers *x* and *y* (|*x*|, |*y*| ≤ 10^{9}). The second line contains a single integer *n* (1 ≤ *n* ≤ 2·10^{9}).

Output

Output a single integer representing *f*_{n} modulo 1000000007 (10^{9} + 7).

Examples

Input

2 3

3

Output

1

Input

0 -1

2

Output

1000000006

Note

In the first sample, *f*_{2} = *f*_{1} + *f*_{3}, 3 = 2 + *f*_{3}, *f*_{3} = 1.

In the second sample, *f*_{2} = - 1; - 1 modulo (10^{9} + 7) equals (10^{9} + 6).

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/18/2018 19:19:03 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|