Cho dãy gồm \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\). Hiệp đố Đức Anh tính số cách chọn ra một dãy con (không cần liên tiếp) có tổng bằng \(k\) trong dãy trên, Đức Anh khôn nên giải trong đúng \(36\) giây. Hiệp lại tăng độ khó, Hiệp hỏi \(q\) truy vấn \(l, r, k\) với ý nghĩa tính số cách chọn một dãy con có tổng bằng \(k\) trong dãy \(a_l, a_{l + 1}, \ldots, a_r\). Đức Anh gà nên nhờ bạn giúp, hãy giúp anh ấy.

Input

• Dòng đầu là hai số nguyên dương \(n\) và \(q\) \((1 \le n, q \le 10^5)\).
• Dòng thứ hai là \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) \((0 \le a_i \le 100)\).
• \(q\) dòng tiếp theo, mỗi dòng là ba số nguyên dương \(l, r, k\) thể hiện một truy vấn \((1 \le l \le r \le n, k \le 100)\).

Output

• \(q\) dòng là đáp án cho \(q\) truy vấn, lấy dư cho \(10^9 + 7\).

Example

5 3
1 9 8 1 2
1 5 2
1 4 10
1 5 3

2
3
2