Iterated Linear Function

题意翻译

定义函数$g$: ①$g^0(x)=x$ ②$g^n(x)=Ag^{n-1}(x)+B(n≠0)$ 请求出$g^{n}(x)$的值。**由于答案可能过大，请将其对$10^9+7$取模**。 Translate by @ducati

题目描述

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 $ .

输入输出样例

输入样例 #1

3 4 1 1

输出样例 #1

7

输入样例 #2

3 4 2 1

输出样例 #2

25

输入样例 #3

3 4 3 1

输出样例 #3

79