Description

给定 A0,A1，以及 An=p*An−1+q×An−2 中的 p,q。

这里 n≥2。

求第 k 个数 Ak 对 10000 的模。

Input

输入包括 5 个整数：A0、A1、p、q、k。

Output

第 k 个数 Ak 对 10000 的模。 1≤A0,A1,p,q,k≤10000

Samples

20 1 1 14 5

8359

Limitation

1s, 1024KiB for each test case.