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×f(xb)+c×f(xd), for all xZ, x>0. It is known that f(0)=e.

y 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 109+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)mod109+7.

Constraints

For all subtasks:

0a,c,e109

2b,d109

Subtask 1 [10%]

0a,c,e,N10

2b,d10

Subtask 2 [30%]

0N103

Subtask 3 [60%]

0N108

Sample Input

Copy
1 2 3 4 5 6

Sample Output

Copy
95

Comments

There are no comments at the moment.