There are many magical functions in the beautiful world of Mathematics and Computer Science. A magical function is defined as ~f(x) = a \times f(\lfloor \frac{x}{b} \rfloor) + c \times f(\lfloor \frac{x}{d} \rfloor)~, for all ~x \in \mathbb Z~, ~x > 0~. It is known that ~f(0) = e~.

~\lfloor y \rfloor~ is defined as the greatest integer that is less than or equal to ~y~.

Given the constants ~a~, ~b~, ~c~, ~d~, ~e~, and some non-negative integer ~N~, find the value of ~f(N)~ modulo ~10^9 + 7~.

Input Specification

On the first and only line of input, ~a, b, c, d, e, N~ are given, separated by a single space.

~a, b, c, d, e, N~ are all integers.

Output Specification

Output ~f(N) \bmod 10^9 + 7~.

Constraints

For all subtasks:

~0 \le a,c,e \le 10^9~

~2 \le b,d \le 10^9~

Subtask 1 [10%]

~0 \le a,c,e,N \le 10~

~2 \le b,d \le 10~

Subtask 2 [30%]

~0 \le N \le 10^3~

Subtask 3 [60%]

~0 \le N \le 10^8~

Sample Input

1 2 3 4 5 6

Sample Output

95