from functools import reduce

MOD = 10**9 + 7

# return matrix product A*B^T
def mprod(A,B):
    return [[sum(p*q for p,q in zip(r,c)) for c in B] for r in A]

def solve(a,b,n):
    b_str = '1' + format(n,'b')[::-1]
    pows = [[[1,0],[0,1]],
            [[1,1],[1,0]]]
    for _ in range(len(b_str)-1):
        pows.append(mprod(pows[-1],pows[-1]))
    F = reduce(mprod,[M for M,c in zip(pows,b_str) if c=='1'])
    k1,k2 = F[1]
    return (k1*b + k2*a)%MOD