[PIGPEN] Đại tội thứ tám

1000 ms 256 MB Medium

Như bạn đã biết, trong kinh thánh có tất cả 7 đại tội. Nhưng thực tế, tồn tại đại tội thứ 8; đó chı́nh là ở bẩn, và PigPen là đại diện tiêu biểu cho đại tội này.
Vı̀ PigPen không chịu tắm nên nấm đã bắt đầu mọc trên đầu cậu. Ngày thứ nhất, trên đầu PigPen có 𝑘 cây nấm. Với mỗi ngày không tắm tiếp theo, số nấm trên đầu PigPen bằng số nấm của ngày trước đó nhân với 𝑎 rồi cộng thêm 𝑏.
Cụ thể, gọi x_i là số nấm trên đầu PigPen ở ngày thứ i. Khi đó x_1=k và với mọi i>1, ta có x_i=a×x_(i-1)+b. Có 𝑄 truy vấn, mỗi truy vấn thuộc một trong hai loại:
1 𝑘 𝑎 𝑏 𝑛: tı́nh số nấm trên đầu PigPen ở ngày thứ 𝑛.
2 𝑘 𝑎 𝑏 𝑛: tı́nh tổng số nấm trên đầu PigPen từ ngày thứ 1 đến ngày thứ 𝑛.
Yêu cầu: Hãy trả lời 𝑄 truy vấn đã cho.
Dữ liệu vào: Cho từ tệp tin PIGPEN.INP:
Dòng đầu tiên chứa số nguyên dương Q(1≤Q≤〖10〗^6) là số lượng truy vấn;
𝑄 dòng tiếp theo, mỗi dòng chứa năm số nguyên t,k,a,b,n (1≤t≤2; 1≤a,k,n≤〖10〗^9; 0≤b≤〖10〗^9) mô tả một truy vấn;
Kết quả ra: Ghi ra tệp tin PIGPEN.OUT: Với mỗi truy vấn, in ra một dòng chứa một số nguyên là kết quả tương ứng. Vı̀ đáp án có thế rất lớn nên hãy in ra số dư khi chia cho 〖10〗^9+7.
Ví dụ:
PIGPEN.INP
6
1 2 3 1 4
2 2 3 1 4
1 5 1 2 5
2 5 1 2 5
1 3 2 0 5
2 3 2 0 5
PIGPEN.OUT
67
98
13
45
48
93
Ràng buộc:
Có 20% số điểm của bài với tổng các giá trị 𝑛 trong tất cả truy vấn không vượt quá 106;
Có 20% số điểm khác của bài với 𝑏 = 0 trong tất cả truy vấn;
Có 20% số điểm khác của bài với 𝑎 = 1 trong tất cả truy vấn;
Có 20% số điểm khác của bài với Q ≤ 5×〖10〗^4;
Có 20% số điểm còn lại không có điều kiện ràng buộc gı̀ thêm.

Test mẫu

Input

Output

Đăng nhập để nộp bài.