Lặp Hàm Tuyến Tính

Cho hàm $f(t)=A\cdot t+B$. Bắt đầu từ $x$ và áp dụng $f$ đúng $n$ lần; hãy tính giá trị cuối cùng theo modulo $1000000007$.

Input

• Một dòng chứa bốn số nguyên $A,B,n,x$ theo đúng thứ tự này.

Output

• In $f$ lặp đúng $n$ lần tại $x$, lấy modulo $1000000007$.

Constraints

• $1\le A,B,x\le 10^9$.
• $1\le n\le 10^{18}$.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n\le 10^6$.
• Subtask $2$ ($50\%$ số điểm): không có giới hạn bổ sung.

Example

2 5 4 3

123