DMOPC '20 Contest 1 P4 - Victor Makes Bank

View as PDF

Submit solution


Points: 17 (partial)
Time limit: 2.0s
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

Forget school, I wanna farm horseshoe crabs ~ Victor, 2019

Victor, deciding that school is dumb and boring, decides to farm horseshoe crabs. After he has bred enough crabs, he sells them to the highest bidder—babies at one thousand dollars each, and adults at two thousand dollars each.

At the end of every month, each adult crab in Victor's care gives birth to K babies (this crab species is capable of parthenogenesis, so all the crabs are female and can give birth without mating). A baby crab takes T months to grow to adulthood.

If Victor starts off with C adult crabs at the beginning of the first month, and sells all his crabs (babies and adults) in the middle of the N-th month, how many thousands of dollars will he make? Since this number may be very large, please output it modulo 10^9 + 7.

Constraints

1 \leq K, C \leq 10^9
1 \leq T \leq 100

Subtask 1 [15%]

1 \leq N \leq 10^{6}

Subtask 2 [85%]

1 \leq N \leq 10^{18}

Input Specification

4 space-separated integers, N, K, T, and C.

Output Specification

The amount of money (in thousands of dollars) made from selling all the crabs in the middle of the N-th month, mod 10^9 + 7.

Sample Input 1

4 2 1 1

Sample Output 1

16

Explanation of Sample 1

The number of crabs in Victor's tank at the beginning of every month is as follows:

Month # of Adults # of Babies
1 1 0
2 1 2
3 3 2
4 5 6

Victor can then sell the adult crabs for 10 thousand dollars and the baby crabs for 6 thousand dollars, for a total of 16 thousand dollars.

Sample Input 2

8 1 3 2

Sample Output 2

38

Comments

There are no comments at the moment.