GlobeX Cup '18 J4 - Magical Functions

View as PDF

Submit solution


Points: 7 (partial)
Time limit: 0.6s
Memory limit: 64M

Author:
Problem type

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

Comments

There are no comments at the moment.