Cho bốn số nguyên dương a, b, c, d, từ hai số b, c ta xây dựng được dãy số x_n với công thức như sau:

• x₁ = b;
• x_n  = x_n-1 * b + c với mọi n >= 2

Sau khi tạo ra được dãy số đó, Thúy muốn bạn tính giá trị a^x_d. Kết quả của bài toán sẽ rất lớn nên Thúy chỉ yêu cầu bạn chia lấy dư cho 1000000007.

Dữ liệu:  Gồm một dòng duy nhất chứa 4 số nguyên dương a, b, c, d. (a, b, c, d <= 10¹⁸ )

Kết quả:  In ra giá trị a^x_d  % 1000000007