GlobeX Cup '18 J4 - Magical Functions

View as PDF

Submit solution


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

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 cases, 0 \leq a,c,e \leq 10^9, and 2 \leq b,d \leq 10^9.

Subtasks

Subtask 1 [10%]

0 \leq a,c,e,N \leq 10, 2 \leq b,d \leq 10

Subtask 2 [30%]

0 \leq N \leq 10^3

Subtask 3 [60%]

0 \leq N \leq 10^8

Sample Input

1 2 3 4 5 6

Sample Output

95

Comments


  • -5
    ItzMidnightShadowWolf  commented on July 24, 2020, 5:11 p.m. edited

    This comment is hidden due to too much negative feedback. Click here to view it.


    • -5
      Aaeria  commented on July 25, 2020, 6:06 p.m.

      This comment is hidden due to too much negative feedback. Click here to view it.