Purple rất thích đồ ngọt, và cũng đang học để trở thành thợ làm bánh chuyên nghiệp.

Purple có biết ~n~ nguyên liệu khác nhau để làm bánh, được đánh số từ ~1~ đến ~n~, nguyên liệu thứ ~i~ có độ ngon là ~a_i~. Mỗi ngày Purple mua một số nguyên liệu để làm bánh, là các nguyên liệu được đánh số bởi số nằm trong đoạn ~[l, r]~, mỗi loại nguyên liệu có số lượng vô tận. Vì các nguyên liệu là khác nhau nên cô muốn thử tạo tất cả những chiếc bánh khác nhau có thể tạo, không có hai chiếc bánh nào giống nhau (hai chiếc bánh giống nhau khi chúng đều dùng chung các nguyên liệu), và mỗi chiếc bánh Purple sử dụng đúng k nguyên liệu. Độ ngon của một chiếc bánh là tích của độ ngon của các nguyên liệu thành phần. Cụ thể hơn, nếu chọn các nguyên liệu ~i_1,~ ~i_2,~ ~...,~ ~i_k~ để làm bánh thì cái bánh đó có độ ngon là ~a_{i_1} \times a_{i_2} \times ... \times a_{i_k}~.

Bạn là một phóng viên của Đài Tím nói, bạn sẽ phỏng vấn Purple trong ~q~ ngày. Mỗi ngày trong ~q~ ngày đó, bạn hỏi Purple tổng của độ ngon của tất cả những chiếc bánh Purple có thể tạo, nhưng mà kết quả lớn quá nên bạn đành phải chia nó cho ~10^9+7~ và lấy phần dư. Bây giờ bạn hãy cho mọi người biết kết quả mỗi ngày trong q ngày bạn thu được.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~q~ ~(1 \le n \le 3 \times 10^5, 1 \le q \le 3 \times 10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(1 \le a_i \le 10^9)~.
• Dòng thứ ~i~ trong ~q~ dòng tiếp theo chứa hai số nguyên ~l,~ ~r,~ và ~k~ ~(1 \le l \le r \le n, 1 \le k \le 50)~ mô tả những nguyên liệu Purple đã mua và số nguyên liệu để làm bánh vào ngày thứ ~i~ bạn phỏng vấn.

Output

Tại dòng thứ ~i~ trong ~q~ dòng, đưa ra kết quả mà bạn thu được sau khi phỏng vấn Purple vào ngày thứ ~i~.

Scoring

Sample Input

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

Sample Output

6
5

Explanation

Với ví dụ trên, ở ngày thứ ~2~ mà bạn phỏng vấn Purple, những chiếc bánh Purple có thể làm là ~(1,1),~ ~(1,2),~ ~(1,2)~, tổng độ ngon của những chiếc bánh này là ~1\times 1 + 1\times 2 + 1\times 2~ ~=5~.