Bé Tommy rất thích tìm hiểu về các số đặc biệt, hôm trước trong giờ học lập trình thầy giáo dạy cho bé về số hoàn hảo (số hoàn hảo là số có tổng các ước (không kể nó) bằng chính nó, ví dụ số ~6~ là số hoàn hảo vì ~6=1+2+3~), bé cảm thấy hứng thú với con số này. Về nhà bé nghĩ ra khá nhiều bài toán xử lí số hoàn hảo. Nhưng hôm nay, thầy cho bé một bài tập rất hóc búa, nghĩ mãi không ra cách làm tốt nhất để được tối đa điểm của bài, nên bé nhờ các bạn học sinh giỏi làm giúp. Bài toán như sau:

Cho dãy ~a_1,a_2,…,a_n~ , ban đầu tất cả các phần tử có giá trị bằng ~0~. Có ~m~ phép biến đổi dạng ~(u,v,k)~: tăng giá trị các phần tử từ vị trí ~u~ đến vị trí ~v~ lên ~k~ đơn vị. Dữ liệu đảm bảo sau ~m~ phép biến đổi ~0<a_i \le 10^6~ ~(\forall i=1..n)~ và có ít nhất một số hoàn hảo trong dãy. </p>

Yêu cầu:

• Với dãy ~a_1,a_2,…,a_n~ sau ~m~ phép biến đổi, thầy yêu cầu đưa ra vị trí các số hoàn hảo theo thứ tự tăng dần.

Input

• Dòng đầu là hai số nguyên dương ~n,m~ tương ứng là số phần tử của dãy và số lượng phép biến đổi;
• ~m~ dòng sau mỗi dòng là ba số nguyên dương ~u,v,k~ ~(0 < u \le v \le n)~.

Output

• In ra các dòng, mỗi dòng chứa một số nguyên dương là vị trí của số hoàn hảo tìm được trong dãy theo thứ tự tăng dần.

Subtask

• Subtask ~1~ (~35\%~ số điểm): ~ 1 \le n,m \le 10^2~
• Subtask ~2~ (~35\%~ số điểm): ~n \le 10^5, m \le 10^3~
• Subtask ~3~ (~30\%~ số điểm): ~n \le 10^5, m \le 10^5~

Sample Input 1

6 3
1 6 6
2 3 4
3 5 22

Sample Output

1
4
5
6

Explanation 1

• Dãy thu được sau ~3~ phép biến đổi là: 6 10 32 28 28 6

Cho một dãy số gồm ~n~ phần tử ~a_1~, ~a_2~, ..., ~a_n~. Với một dãy số gồm ~m~ phần tử ~b_1~, ~b_2~, ..., ~b_m~, trọng số của dãy ~b~ được định nghĩa là tích của giá trị lớn nhất và nhỏ nhất của dãy. Hãy tìm tổng trọng số của các dãy con của dãy ~a~.

Dãy con của dãy ~a~ được định nghĩa là một tập ~a_{i_1}~, ~a_{i_2}~, ..., ~a_{i_k}~ với 1 ~\le~ ~i_1~ < ~i_2~ < ... < ~i_k~ ~\le~ ~n~.

INPUT

• Dòng đầu chứa số nguyên dương ~n~ (~1~ ~\le~ ~n~ ~\le~ ~10^5~).
• Dòng thứ hai chứ ~n~ số nguyên không âm ~a_i~ (~0~ ~\le~ ~a_i~ ~\le~ ~10^9~).

OUTPUT

• In ra một số nguyên duy nhất là tổng trọng số của tất cả các dãy con. Do output có thể rất lớn nên hãy in ra kết quả mod ~10^9 + 7~.

SAMPLE TEST

Input:

5
4 2 1 3 4

Output:

208

SUBTASKS

• ~30\%~ số điểm có ~n~ ~\le~ ~20~.
• ~30\%~ số điểm có ~n~ ~\le~ ~10^3~.
• ~40\%~ số điểm còn lại có ~n~ ~\le~ ~10^5~.

Tương truyền, Ngưu Lang và Chức Nữ yêu nhau thắm thiết đến độ có thể thần giao cách cảm. Để kiểm chứng điều này, Ngọc Hoàng đã đưa cho họ một số nguyên dương ~n~. Hàng năm vào ngày rằm tháng bảy, Ngọc Hoàng sẽ đưa cho họ thêm một số nguyên dương k, sau đó bảo hai người họ mỗi người chọn một tập con của ~{1, 2, . . . , n}~.

Nếu tổng các số Ngưu Lang chọn cộng với tổng các số Chức Nữ chọn bằng đúng ~k~ thì họ sẽ được gặp nhau.

Yêu cầu: Hãy giúp cặp đôi này tính toán số cách chọn khác nhau cho từng năm để họ được gặp nhau. Hai cách chọn được cho là khác nhau nếu tập mà Ngưu Lang chọn là khác nhau trong hai cách đó hoặc tập mà Chức Nữ chọn là khác nhau trong hai cách đó

Input

• Dòng đầu chứa hai số nguyên dương ~n~ ~Q~ với ~Q~ là số năm
• Mỗi dòng trong ~Q~ dòng tiếp theo ghi một số nguyên dương ~k~

Constraints

• ~n,k,Q \le 10^5~

Subtask

• Subtask ~1~ ~(25\%)~: ~k \le 500~
• Subtask ~2~ ~(25\%)~: ~n \le 500~
• Subtask ~3~ ~(25\%)~: ~Q \le 500~
• Subtask ~4~ ~(25\%)~: Không có ràng buộc gì thêm.

Output

• Ghi ~Q~ dòng là số cách chọn tương ứng cho ~Q~ năm, sau khi chia lấy dư cho ~10^9 + 7~

Sample Input 1

5 5
1
2
3
4
5

Sample Output 1

2
3
6
9
14