answer = []

while(1):

    try:

        a0,a1,p,q,k = map(int, input().split())

        answer.append(a0)

        answer.append(a1)

        for i in range(2,k+1):

            answer.append(p*answer[i-1] + q*answer[i-2])

        print(answer[k]%10000)

    except:

        break