Sau khi chơi với ngọc chán chê, Tí sắp ~n~ viên ngọc ra một đường thẳng và bắt đầu nhìn ngắm chúng. Tí nhận thấy rằng có không quá ~k~ màu ngọc khác nhau trên bàn và viên ngọc thứ ~i~ từ trái sang thì có màu ~a_i~. Tí muốn chia dãy ngọc thành các đoạn liên tiếp sao cho mỗi đoạn đều có đủ ~k~ màu. Hỏi Tí có bao nhiêu cách chia thỏa mãn như vậy?

Yêu cầu: In số cách chia thỏa mãn sau khi ~\mod 10^9+7~

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n,k~.
• Dòng thứ hai chứa ~n~ số nguyên ~a_1,a_2,...,a_n~.

Output

• Ghi ra một số nguyên là kết quả bài toán.

Constraints

• ~1\leq k\leq n\leq 10^6~
• ~1\leq a_i\leq k~

Scoring

• Subtask ~1~ (~20\%~ số điểm): ~k = 1~.
• Subtask ~2~ (~20\%~ số điểm): ~n\leq 5000~.
• Subtask ~3~ (~20\%~ số điểm): ~n\leq 10^5, k\leq 100~.
• Subtask ~4~ (~40\%~ số điểm): Không có ràng buộc gì thêm.

Example

Sample Input ~1~

5 2
1 2 2 1 2 

Sample Ouput ~1~

3

Explanation

Có ~3~ cách chia như sau: ~(1\ 2) | (2\ 1\ 2), (1\ 2\ 2) | (1\ 2)~, hoặc ~(1\ 2\ 2\ 1\ 2)~.

Hè đã tới, ~mrtee~ muốn cho các học sinh của mình vận động một chút. Thầy đã lập ra một cuộc thi nhảy xa, tuy nhiên điều luật của nó thì rất lạ.

Nếu chiếu trên trục ~OX~, đường nhảy sẽ bắt đầu từ điểm ~1~ và kết thúc tại điểm ~n~. Bạn sẽ xuất phát từ điểm ~0~ và được nhảy bao nhiêu lượt tùy thích, miễn là không ra khỏi phạm vi ~[1,n]~. Tuy nhiên, mỗi lượt bạn phải nhảy một quãng đường nguyên dương và ở lần nhảy thứ ~i~, bạn phải nhảy một quãng đường có độ chia hết cho ~k+i-1~. Tất nhiên, bạn sẽ được cung cấp trước ~2~ giá trị ~n~ và ~k~.

Là một ~coder~ yêu thích toán học, bạn không quan tâm tới việc thắng thua trong cuộc thi này lắm, mà chỉ hứng thú với việc đếm xem với mỗi vị trí ~i~ thuộc đoạn ~[1,n]~, có bao nhiêu cách nhảy khác nhau từ điểm xuất phát tới đó.

Hãy thử lập trình và giải đáp câu hỏi ấy!

Input

• Gồm một dòng chứa hai số nguyên dương ~n, k~.
  
  

Output

• In ra ~n~ số nguyên, số thứ ~i~ là số cách để nhảy từ điểm ~0~ tới điểm ~i~, vì kết quả có thể rất lớn nên hãy lấy phần dư với modulo ~10^9+7~.
  
  

Constraints

• ~1 \le k \le n \le 2*10^5~
  
  

Subtasks

• ~35\%~ số điểm: ~n \le 300~.
• ~40\%~ số điểm: ~n \le 4000~.
• ~25\%~ số điểm: ~n \le 2*10^5~.
  
  

Sample Test 1

Input:

12 1

Output:

1 1 2 2 3 4 5 6 8 10 12 15

Sample Test 2

Input:

15 3

Output:

0 0 1 0 0 1 1 0 1 1 1 2 1 1 3

Giải thích

• Ở ví dụ ~1~, các cách để đến điểm ~6~ là ~[0,6],[0,4,6],[0,2,6],[0,1,3,6]~.
• Ở ví dụ ~2~, các cách để đến điểm ~15~ là ~[0,15],[0,3,12],[0,6,10,15]~

It's not a bug — it's an undocumented feature 😈

Cho một dãy số nguyên ~A~ gồm ~n~ phần tử, được đánh số ~A_1,A_2,...,A_n~.

Ta có một số định nghĩa như sau:

• Trọng số của đoạn con (ở đây là một đoạn con liên tiếp) là tổng các giá trị ~A_i~ trong đoạn.
• Độ cân bằng của dãy ~A~ là trọng số của đoạn con có trọng số lớn nhất trong dãy số.

Bài toán sẽ thật dễ dàng nếu chỉ yêu cầu tính độ cân bằng của dãy ~A~ được cho, vậy nên ~Watermelon~ - người thầy của muôn quả - đã quyết định tăng độ khó bằng cách sau:

• Đầu tiên, thầy đưa ra một dãy số nguyên gồm ~n~ phần tử ~B_1,B_2,...,B_n~.
• Có tối đa ~k~ lượt chỉnh sửa, mỗi lượt bạn được chọn một đoạn con các phần tử từ vị trí thứ ~l~ đến vị trí thứ ~r~ ~(1 \le l \le r \le n)~ và thực hiện phép gán ~A_i = A_i*B_i~ với ~\forall i \in [l,r]~.

Yêu cầu: Đưa ra được độ cân bằng lớn nhất với tối đa ~k~ lượt chỉnh sửa.

Hoa Quả Sơn đã phải bó cành trước bài toán mới này, bạn hãy giúp họ tìm kiếm câu trả lời.

Input: watermelon.inp

• Dòng đầu tiên gồm hai số nguyên ~n~ và ~k~ ~(1 \le n \le 10^5, 0 \le k \le 10)~.
• Dòng thứ hai gồm ~n~ số nguyên dương miêu tả dãy số nguyên ~A_1, A_2, ..., A_n~ ~(|A_i| \le 1000)~.
• Dòng thứ ba gồm ~n~ số nguyên dương miêu tả dãy số nguyên ~B_1, B_2, ..., B_n~ ~(|B_i| \le 10)~.

Output: watermelon.out

• In ra một số nguyên duy nhất là độ cân bằng lớn nhất tìm được của dãy ~A~ sau khi sử dụng tối đa ~k~ lượt chỉnh sửa.

Scoring:

• Subtask ~1~ ~(15\%)~: ~k = 0~.
• Subtask ~2~ ~(15\%)~: ~k = 1~ và ~n \le 5000~.
• Subtask ~3~ ~(20\%)~: ~k = 1~.
• Subtask ~4~ ~(25\%)~: ~k = 2~.
• Subtask ~5~ ~(25\%)~: Không ràng buộc gì thêm.

Sample Input 1

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

Sample Output 1

13

Sample Input 2

3 0
-4 -10 -8
2 2 -1

Sample Output 2

-4

Explanation:

• Trong ví dụ thứ nhất, cách tối ưu nhất là chọn đoạn ~[3, 4]~ để tác động. Như vậy dãy ~A~ mới là ~[-3, 4, 5, 4, -2]~. Vậy độ cân bằng của dãy này là ~13~.
• Trong ví dụ thứ ~2~, khi ~k = 0~, bạn không thực hiện lượt chỉnh sửa nào và đưa ra độ cân bằng của dãy ~A~ ban đầu là ~-4~.

Tiếp tục là Châu và câu chuyện hành trình trở thành thợ code của anh ấy. MrTee sau khi thấy Châu đã quá thợ nên đã gửi anh ấy cho thầy Hưng Cao dạy. Thử thách đầu tiên thầy Hưng giao cho Châu là Con cáo và chùm nho (không phải bài nhạc mà các bạn biết). Thử thách có nội dung như sau:

Cho chùm nho có ~N~ quả và ~M~ cành cây, mỗi cành cây nối 2 quả nào đó với nhau. Giữa 2 quả bất kì có thể có nhiều cành cây nối chúng (cây bị down). Cũng có thể có những quả có cành cây nối với chính nó. Đơn giản thì chùm nho là mô hình đồ thị ~N~ đỉnh, ~M~ cạnh.

Các quả nho được đánh số từ ~1~ đến ~N~. Quả thứ ~i~ có độ cao là ~A_i~. Độ dốc giữa cành cây nối giữa 2 quả được tính bằng giá trị tuyệt đối chênh lệch chiều cao giữa 2 quả nho. Ví dụ cành cây nối giữa 2 quả ~x~ và ~y~ sẽ có độ dốc là ~|A_x - A_y|~.

Dù trong nhiều câu chuyện, cáo luôn là phản diện nhưng chúng là loài động vật thông minh. Ai cũng thích động vật thông minh và Châu và thầy Hưng cũng vậy. Để giúp con cáo lấy được chuỗi các quả nho xịn và nhiều nhất, Châu phải thiết kế 1 con đường leo cây siêu nhanh. Xuất phát từ 1 quả nho nào đó, đi đến các quả nho khác với điều kiện các quả nhỏ sau cao hơn quả nho trước, không những thế, độ dốc của cành cây sau cũng phải lớn hơn độ dốc của cành cây trước đó. Nghĩa là, nếu như Châu quyết định chọn một hành trình đi qua các quả nho theo thứ tự ~P_1, P_2, ..., P_k~ thì hành trình đó sẽ phải thỏa mãn tính chất:

~0 < A_{P_2}-A_{P_1} < A_{P_3}-A_{P_2} < ... < A_{P_k}-A_{P_{k-1}}~

Như đã nói, để giúp con cáo, hành trình này cũng phải thỏa mãn việc nó có đi qua nhiều quả nho nhất. Ngoài ra thầy Hưng cũng muốn biết thêm có bao nhiêu cách đi như vậy để còn giật dây hành trình của con cáo.

Vì là thợ đặc cấp nên Châu dễ dàng vượt qua thử thách này và được dạy cho nhiều câu punchline như một phần thưởng.

Liệu bạn có thợ như Châu?

Yêu cầu:

• Tìm đường đi qua nhiều quả nho nhất và thỏa mãn yêu cầu đề bài. Đồng thời tìm xem có bao nhiêu đường đi khác nhau đi qua nhiều quả nho nhất.

Input: dincpath.inp

• Dòng đầu tiên chứa 2 số nguyên ~N~ và ~M~ ~(1 \le N \le 3 * 10 ^ 5, 1 \le M \le 5 * 10^5)~.
• Dòng thứ hai chứa độ cao của ~N~ quả nho là ~N~ số nguyên dương ~A_1, A_2, ..., A_n~ ~(1 \le A_i \le 10^9)~.
• Dòng thứ ~i~ trong số ~M~ dòng tiếp theo chứa cặp số nguyên dương ~(U_i, V_i)~ là chỉ số hai quả nho và là hai đầu của cành cây thứ ~i~ ~(1 \le U_i, V_i \le N)~.

Output: dincpath.out

• Dòng đầu tiên ghi ra một số nguyên là số lượng quả nho của hành trình tìm được.
• Dòng thứ hai ghi ra một số nguyên là phần dư trong phép chia số lượng hành trình khác nhau tìm được cho ~10^9 + 7~.

Subtasks

• Có ~20\%~ số test ứng với ~N \le 20~.
• Có ~20\%~ số test khác ứng với ~N \le 500~.
• Có ~20\%~ số test khác ứng với đồ thị tương ứng là một mạch thẳng (đồ thị dạng cây nhưng mỗi đỉnh chỉ có tối đa 2 cạnh).
• Có ~20\%~ số test khác ứng với ~M = N - 1~, và các đỉnh trong đồ thị liên thông với nhau.
• ~20\%~ còn lại không có giới hạn gì thêm.

Sample Input 1

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

Sample Output 1

3
1

Cho một đồ thị liên thông vô hướng gồm ~n~ đỉnh, ~n - 1~ cạnh (đây còn được gọi là đồ thị dạng cây). Cạnh thứ ~i~ nối giữa đỉnh ~u_i~ với ~v_i~ và có trọng số là ~w_i~. Quân đưa cho bạn ~m~ tập đỉnh, tập thứ ~i~ gồm ~t_i~ đỉnh là ~a_{i_1}, a_{i_2}, . . . , a_{i_{t_i}}~.

Giả sử ta có hai tập đỉnh ~p~ và ~q~ (một tập không có hai đỉnh giống nhau, nhưng một đỉnh có thể xuất hiện ở cả hai tập).

Đặt ~f(p,q)~ là tổng khoảng cách giữa các cặp đỉnh ~(u, v)~ trong đó ~u~ nằm trong tập ~p~ và ~v~ nằm trong tập ~q~ (khoảng cách giữa hai đỉnh là tổng trọng số các cạnh trên đường đi giữa chúng).

Cụ thể, nếu gọi ~dist(u,v)~ là khoảng cách giữa cặp đỉnh ~(u,v)~ trên cây, ta có tập ~p~ ~=~ ~ \{2,3\}~ và tập ~q~ ~=~ ~\{1,4,3\}~, thì ~f(p,q)~ sẽ được tính như sau:

• ~f(p,q) = dist(2,1) + dist(2,4) + dist(2,3) + dist (3,1) + dist(3,4) + dist(3,3)~.

Quân muốn bạn tính giá trị của biểu thức sau: ~S = \sum_{i=1}^m \sum_{j=i+1}^m f(i,j)~.

Vì kết quả có thể rất lớn, hãy in ra phần dư của ~S~ khi chia cho ~10^9 + 7~.

Dữ liệu vào từ tệp văn bản: tongcay.inp

• Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~m~ ~(1 \le n,m \le 10^6)~.
• ~n-1~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên dương ~u_i,v_i,w_i~ ~(1 \le u_i,v_i \le n; u_i \neq v_i; w_i \le 10^5)~.
• Ở mỗi dòng trong ~m~ dòng cuối cùng, số đầu tiên là ~t_i~, theo sau đó là ~t_i~ số ~a_{i_1},a_{i_2},...,a_{t_i}~ ~(1 \le a_x \le n; a_x \neq a_y \forall x \neq y)~.

Tổng ~t_1 + t_2 + ... + t_m~ không vượt quá ~10^6~.

Kết quả ghi ra tệp văn bản: tongcay.out

• In ra một số nguyên không âm là kết quả bài toán.

Ràng buộc

• Có ~25\%~ số test thỏa mãn: ~n \le 100; m \le 100; t_1 + t_2 + ... + t_m \le 100~.
• Có ~25\%~ số test thỏa mãn: ~n \le 100; m \le 100; t_1 + t_2 + ... + t_m \le 10^5~.
• Có ~20\%~ số test thỏa mãn: ~n \le 10^5; m \le 100; t_1 + t_2 + ... + t_m \le 10^5~.
• Có ~20\%~ số test thỏa mãn: ~n, m, t_1 + t_2 + ... + t_m \le 10^5~.
• ~10\%~ số test còn lại không có ràng buộc gì thêm.

Ví dụ

Input

3 3
1 2 1
2 3 1
1 1
1 2
2 1 3

Output

5

Giải thích

~f(1,2) = dist(1,2) = 1~ ~f(1,3) = dist(1,1) + dist(1,3) = 0 + 2 =2~ ~f(2,3) = dist(2,1) + dist(2,3) = 1 + 1 = 2~

Vậy ~S = 1 + 2 + 2 = 5~

Có ~N+2~ thị trấn xếp thẳng hàng. Các thị trấn được đánh số từ ~0~ đến ~N+1~ từ trái sang phải. Mỗi thị trấn ~i~ ~(1 \leq i \leq N)~ có một nơi trú ẩn có thể chứa tối đa ~A_i~ người.

Hiện tại, có ~S~ người đang di chuyển cùng nhau và ghé thăm một trong các thị trấn. Tuy nhiên, bạn không biết họ đang ghé thăm thị trấn nào.

Bạn vừa nhận được thông tin có ~Q~ thiên thạch có thể rơi xuống các thị trấn. Thiên thạch thứ ~i~ có thể rơi vào các thị trấn từ ~L_i, L_i+1, \cdots, R_i~. Để đảm bảo an toàn cho người đi đường, đối với mỗi thiên thạch, bạn cần tính chi phí sơ tán mà chính quyền cần bỏ ra.

Chi phí sơ tán cho một thiên thạch được tính như sau:

• Chi phí sơ tán là tổng chi phí tối thiểu cần thiết để đảm bảo tất cả người đi đường được an toàn bất kể họ đang ở thị trấn nào.
• Một người được coi là an toàn nếu người đó ở trong một nơi trú ẩn hoặc ở một thị trấn nằm ngoài khu vực ảnh hưởng của thiên thạch (vậy thì người đó sẽ không cần vào nơi trú ẩn ở thị trấn đó).
• Mỗi người cần ~1~ đơn vị chi phí để di chuyển đến thị trấn liền kề (hai thị trấn được coi là liền kề nếu chỉ chênh lệch nhau đúng ~1~ đơn vị số thứ tự).

Lưu ý rằng chỉ di chuyển người mới tốn chi phí, và các hành động khác (như cho người vào nơi trú ẩn) không tốn chi phí. Đảm bảo rằng các thị trấn ~0~ và ~N+1~ sẽ không bao giờ bị ảnh hưởng bởi thiên thạch, vì vậy luôn có cách để đảm bảo tất cả người đi đường an toàn.

Input

Dữ liệu được cho theo định dạng sau

~N~ ~S~

~A_1 A_2 ⋯ A_N~

~Q~

~L_1~ ~R_1~

~L_2~ ~R_2~

⋮

~L_Q~ ~R_Q~

Ràng buộc

• ~1 \leq N \leq 2 \times 10^5~
• ~1 \leq S \leq 10^{12}~
• ~0 \leq A_i \leq S~
• ~A_1 + A_2 + ⋯ + A_N \leq 10^{12}~
• ~1 \leq Q \leq 2 \times 10^5~
• ~1 \leq L_i \leq R_i \leq N~

Tất cả các giá trị trong đầu vào đều là số nguyên.

Subtask

• Subtask ~1~: ~n,q \le 100~ ~(20\%)~
• Subtask ~2~: ~n,q \le 2000~ ~(20\%)~
• Subtask ~3~: ~L_i = 1~ ~(30\%)~
• Subtask ~4~: Không giới hạn gì thêm ~(30\%)~

Output

• In ra ~q~ dòng, dòng thứ ~i~ là đáp án cho truy vấn thứ ~i~.

Example

Sample Input 1

5 10
2 1 1 4 6
3
2 5
5 5
1 4

Sample Output 1

13
4
15

Explanation

Ở truy vấn ~1~, nếu nhóm người đang ở thành phố ~3~ thì sẽ mất tổng số chi phí là ~13~.

Ở truy vấn ~2~, ~4~ người không có chỗ trú ẩn có thể đi hết sang thành phố ~6~ để thoát khỏi nguy hiểm.