Ánh là một sinh viên xuất sắc ở Trường Đại học Công nghệ Thông tin và Truyền thông Việt Hàn. Cô ấy đặc biệt xuất sắc trong môn toán và lập trình. Hôm nay trong giờ học lập trình thi đấu, thầy giáo của Ánh giao cho cô ấy một bài toán như sau: Cho một dãy \(n\) số nguyên \(a_1, a_2, ..., a_n\), và \(q\) câu hỏi có dạng \((l, r, x, y, k)\). Thầy giáo yêu cầu Ánh tính tích các số nguyên \(a_i^k\) với \(i\) nằm trong khoảng \([l, r]\) và \(a_i\) có giá trị nằm trong khoảng \([x, y]\). Vì đây là một bài toán đơn giản nên Ánh giải quyết nhanh chóng. Tuy nhiên cô ấy chưa chắc chắn với kết quả của mình lắm nên muốn nhờ các bạn lập trình một phiên bản nữa để cô ấy so kết quả. Các bạn hãy giúp Ánh nhé?

Lưu ý: vì kết quả có thể rất lớn nên bạn chỉ cần đưa ra phần dư của đáp số khi chia cho \(10^9 + 7\).

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) \((1 \le n, q \le 2 \times 10^5)\) – độ dài dãy số và số lượng câu hỏi.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, ..., a_n\) \((1 \le a_i \le 10^9)\).
• \(q\) dòng tiếp theo, mỗi dòng chứa năm số nguyên \(l, r, x, y, k\) \((1 \le l \le r \le n, 1 \le x \le y \le 10^9, 1 \le k \le 10^9)\) thể hiện một truy vấn.

Dữ liệu ra

• In ra \(q\) dòng, dòng thứ \(i\) chứa một số nguyên duy nhất là kết quả của truy vấn thứ \(i\), sau khi chia lấy dư cho \(10^9 + 7\).

Scoring

• Subtask 1 (20% số điểm): \(n, q \le 2000, k = 1\).
• Subtask 2 (20% số điểm): \(n, k \le 2000\).
• Subtask 3 (20% số điểm): \(a_i = 2^x\); với mọi \(i\).
• Subtask 4 (20% số điểm): \(k = 1\).
• Subtask 5 (20% số điểm): không có ràng buộc gì thêm.