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