Cho hàm tuyến tính \(f(x) = Ax + B\). Định nghĩa \(g_0(x) = x\) và \(g_n(x) = f(g_{n-1}(x))\) với \(n \ge 1\). Cho trước các số \(A, B, n, x\). Hãy tính \(g_n(x)\) mod cho \(10^9+7\)

Input

Đọc từ file văn bản HAMSO.INP

• Một dòng duy nhất gồm các số \(A, B, n, x (1 \le A, B, x \le 10^9, 1 \le n \le 10^{18})\)

Output

• Một dòng duy nhất là đáp án

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(1 \le A, B, x \le 10^6, 1 \le n \le 10^6\)
• Subtask \(2\) (\(60\%\) số điểm): \(1 \le A, B, x \le 10^9, 1 \le n \le 10^{18}\)

Example

3 4 1 1

7