题解 | #递推数列#

def multply(m1, m2):
    list1 = [[0, 0], [0, 0]]
    for i in range(2):
        for j in range(2):
            for k in range(2):
                list1[i][j] += m1[i][k] * m2[k][j]
    return list1


while True:
    try:
        a0, a1, p, q, k = map(int, input().strip().split())
        k -= 1
        m1 = [[p, q], [1, 0]]
        m2 = [[1, 0], [0, 1]]
        m3 = [[a0], [a1]]
        while k > 0:
            if k & 1 != 0:
                m2 = multply(m1, m2)
            m1 = multply(m1, m1)
            k >>= 1
        ans = (m2[0][0]*a1+m2[0][1]*a0)
        print(ans%10000)
    except EOFError:
        break