def nextnum(a,b,p,q):
    return p*a+q*b

while True:
    try:
        a0,a1,p,q,k=map(int,input().strip().split())
        list1=[]
        list1.append(a0)
        list1.append(a1)
        for i in range(2,k+1):
            list1.append(nextnum(list1[i-1],list1[i-2],p,q))
        print(list1[k]%10000)
    except EOFError:
        break