A10412. Iterated Linear Function

Consider a linear function $f(x)=Ax+B$ . Let's define $g^{(0)}(x)=x$ and $g^{(n)}(x)=f(g^{(n-1)}(x))$ for $n>0$ . For the given integer values $A$ , $B$ , $n$ and $x$ find the value of $g^{(n)}(x)$ modulo $10^{9}+7$ .

The only line contains four integers $A$ , $B$ , $n$ and $x$ ( $1<=A,B,x<=10^{9},1<=n<=10^{18}$ ) — the parameters from the problem statement.

Note that the given value $n$ can be too large, so you should use $64$ -bit integer type to store it. In C++ you can use the long long integer type and in Java you can use long integer type.

Print the only integer $s$ — the value $g^{(n)}(x)$ modulo $10^{9}+7$ .