MOD = 10**9 + 7

def fib_fast_doubling(n, f0=0, f1=1):
    """Computes F(n) given F(0)=f0, F(1)=f1 using fast doubling (O(log n))."""
    def _fib(k):
        if k == 0:
            return (0, 1)
        else:
            a, b = _fib(k >> 1)
            c = (a * ((b * 2 - a) % MOD)) % MOD
            d = (a * a + b * b) % MOD
            if k & 1:
                return (d, (c + d) % MOD)
            else:
                return (c, d)
    fn, fn1 = _fib(n)
    # Combine results to support custom f0, f1
    return (fn * f1 + (fn1 - fn) * f0) % MOD

def solve(a, b, n):
    return fib_fast_doubling(n, f0=a, f1=b)