Á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}, \ldots, 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 đoạn \([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\)

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) \((1 \leq n, q \leq 4 \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}, \ldots ,a_{n}\) \((1 \leq a_{i} \leq 10^{9})\).
• \(q\) dòng tiếp theo, mỗi dòng chứa năm số nguyên \(l, r, x, y\) và \(k\) \((1 \leq l \leq r \leq n, 1 \leq x \leq y \leq 10^{9}, 1 \leq k \leq 10^{9})\) thể hiện một truy vấn.

Output

• 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 \leq 2000, k = 1\).
• Subtask \(2\) (\(20\%\) số điểm): \(n, k \leq 2000\).
• Subtask \(3\) (\(20\%\) số điểm): \(a_{i} = 2^{x}; \forall 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.

Example

5 2
5 2 3 4 1
2 4 1 3 1
1 5 3 5 1

6
60