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 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\le K,C\le {10}^9$
$1\le T\le 100$

Subtask 1 [15%]

$1\le N\le {10}^6$

Subtask 2 [85%]

$1\le N\le {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:

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