Consider a linear function *f*(*x*) = *Ax* + *B*. Let's define *g*<sup class="upper-index">(0)</sup>(*x*) = *x* and *g*<sup class="upper-index">(*n*)</sup>(*x*) = *f*(*g*<sup class="upper-index">(*n* - 1)</sup>(*x*)) for *n* &gt; 0. For the given integer values *A*, *B*, *n* and *x* find the value of *g*<sup class="upper-index">(*n*)</sup>(*x*) modulo 10<sup class="upper-index">9</sup> + 7.
The only line contains four integers *A*, *B*, *n* and *x* (1 ≤ *A*, *B*, *x* ≤ 10<sup class="upper-index">9</sup>, 1 ≤ *n* ≤ 10<sup class="upper-index">18</sup>) — 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.
none
3 4 1 1
7
3 4 2 1
25
3 4 3 1
79
1 1 1 1
2
3 10 723 6
443623217
14 81 51 82
908370438
826504481 101791432 76 486624528
621999403
475965351 844435993 96338 972382431
83709654
528774798 650132512 6406119 36569714
505858307
632656975 851906850 1 310973933
230360736
1 1 352875518515340737 1
45212126
978837295 606974665 846646545585165081 745145208
154788991
277677243 142088706 8846851 253942280
221036825
1 192783664 1000000000000000000 596438713
42838179
1 1000000000 1000000000000000000 1
999999665
1 1000000000 1000000000000000000 1000000000
999999657
1 100000000 10000000000000 1000000000
48993
1 1171281 1000000000000000000 100
57392869
1 1000000000 100000000000000000 1000000000
899999965
1 100000000 100000000000000000 10000
490010000
1 100000456 10000000000000000 54165
129054389
1 1000000000 10000000000000 1
490001
1 100000000 10000000000000000 10000
49010000
1 1000000000 10000000000 12
502
1 999999999 999999999999999999 12345678
12345294
1 1000000 1000000000000000000 100000
49100000
1 1000000000 1000000000000 12
49012
1 10000 1000000000000000000 5
490005
1 10000 1000000000000000000 10000
500000
1 1000000000 10000000000000 12
490012
1 1000000000 1000000000000000 12
49000012
1 1000000000 1000000000000000000 12
999999676
1 10000000 100000000000000000 100000
49100000
114514 114514 114514 114514
623380685
2 1 1000000006 1
1
1 1234 10 9
12349
#迭代
def quick_pow(a,n,mod):
    ans = 1
    while(n):
        if(n&1):    ans = ans * a % mod
        a = a * a % mod
        n >>= 1
    return ans

A, B, n, x = list(map(int,input().split()))
mod = 1000000000+7
A_n = quick_pow(A,n,mod)
ans = (A_n * x + B * ((1 - A_n) // (1 - A) )) % mod
print(ans)
 		 	  		 	 		     	 			  		