Cho hai dãy ~a~ và ~b~ gồm ~n~ phần tử nguyên dương. Bạn được nhận thêm một số nguyên dương ~k~, hãy đếm số cặp ~(i,j)~ ~(1 \le i,j \le n)~ sao cho ~\overline{a_ib_j}~ ~\vdots~ ~k~.

Nói cách khác, hãy đếm số cặp ~(i,j)~ sao cho số nguyên dương ~X~ được tạo bởi cách viết liền ~a_i~ và ~b_j~ với nhau chia hết cho số nguyên dương ~K~ cho trước.

Ví dụ:

• ~a_i = 5, b_j = 77 \Rightarrow X = 577~
• ~a_i = 66, b_j = 99 \Rightarrow X = 6699~

Input

• Dòng đầu tiên gồm số hai nguyên dương ~n~ và ~k~ ~(1 \le n,k \le 3 \times 10^5)~
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1,a_2,...,a_n~ ~(1 \le a_i \le 3 \times 10^5)~.
• Dòng thứ hai gồm ~n~ số nguyên dương ~b_1,b_2,...,b_n~ ~(1 \le b_i \le 3 \times 10^5)~.

Output:

• Gồm một dòng in ra số cặp ~(i,j)~ thỏa mãn.

Subtask:

• Subtask ~1~ (~40\%~ số điểm): ~n \le 2000~.
• Subtask ~2~ (~30\%~ số điểm): ~a_i,b_j \le 2000~ ~\forall i,j \in [1,n]~.
• Subtask ~3~ (~30\%~ số điểm): Không có ràng buộc gì thêm.

Sample Input 1

4 3
1 4 3 6
11 2 4 21 

Sample Output 1

6

Explanation 1

Có các cặp sau:

• ~(1,1) = 111~
• ~(1,2) = 12~
• ~(2,1) = 411~
• ~(2,2) = 42~
• ~(3,4) = 321~
• ~(4,4) = 621~

Chặt nhị phân là một kĩ thuật tìm kiếm quen thuộc đối với tất cả các lập trình viên. Một dãy số ~a~ là một dãy có thể chặt nhị phân được nếu như nó là một dãy số đồng biến. Cụ thể hơn, dãy đồng biến là dãy thoả mãn tính chất: ~(a_i - a_j) \cdot (a_j - a_k) \ge 0 \ \ \forall 1 \le i < j < k \le n~. Chú ý rằng theo định nghĩa này, mọi dãy số có không, một hoặc hai phần tử đều là dãy đồng biến.

Cho dãy số ~a_1, a_2, \ldots, a_n~, hãy đếm xem có bao nhiêu dãy con khác nhau của dãy này là dãy đồng biến.

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

Một dãy ~b~ được gọi là dãy con của dãy ~a~ nếu như ta có thể bỏ bớt một vài phần tử của ~a~ và giữ nguyên thứ tự của các phần tử còn lại để thu được dãy ~b~.

Hai dãy con được gọi là khác nhau nếu tồn tại một vị trí ~i~ sao cho phần tử thứ ~i~ của dãy ~a~ được bỏ đi để tạo ra dãy con thứ nhất, nhưng không được bỏ đi để tạo ra dãy con thứ hai.

Input

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

Output

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

Subtask

• Subtask ~1~ (~20\%~ số điểm): ~n \le 20~; Dãy ~a~ là một hoán vị của ~n~ số nguyên dương đầu tiên
• Subtask ~2~ (~20\%~ số điểm): ~n \le 80~; Dãy ~a~ là một hoán vị của ~n~ số nguyên dương đầu tiên
• Subtask ~3~ (~20\%~ số điểm): ~n \le 300~; Dãy ~a~ là một hoán vị của ~n~ số nguyên dương đầu tiên
• Subtask ~4~ (~20\%~ số điểm): ~n \le 5000~; Dãy ~a~ là một hoán vị của ~n~ số nguyên dương đầu tiên
• Subtask ~5~ (~10\%~ số điểm): Dãy ~a~ là một hoán vị của ~n~ số nguyên dương đầu tiên
• Subtask ~6~ (~10\%~ số điểm): Không có ràng buộc gì thêm

Sample input 1

5
4 2 1 5 3

Sample output 1

17

Explaination

Các dãy con đồng biến là:

• []
• [4], [2], [1], [5], [3]
• [4, 2], [4, 1], [4, 5], [4, 3], [2, 1], [2, 5], [2, 3], [1, 5], [1, 3], [5, 3]
• [4, 2, 1]

Cho một đồ thị vô hướng có dạng cây, tức là đồ thị gồm ~n~ đỉnh và ~n-1~ cạnh. Các đỉnh được đánh số từ ~1~ tới ~n~, đỉnh thứ ~i~ có trọng số là ~w_i~.

Chắc hẳn các bạn đều biết khái niệm về cây con, giả sử ta có một cây có gốc là ~1~ như sau:

• Cây con có gốc là ~2~ sẽ bao gồm các đỉnh : ~\{2,6,5,4\}~.
• Cây con có gốc là ~3~ sẽ bao gồm các đỉnh : ~\{3\}~.

Ta định nghĩa ~S(root,a)~ là tổng trọng số các đỉnh trong cây con gốc ~a~ khi gốc của cây là ~root~. Hay ~S(root,a) = \sum_u^{u \in subtree(a)} w[u]~ khi gốc của cây là ~root~.

Bạn cần trả lời ~q~ câu hỏi, mỗi câu hỏi có dạng như sau:

• ~a~ ~b~ : Hãy in ra ~S(a,b)~.

Input:

• Dòng đầu tiên gồm hai số nguyên dương ~n,q~ ~(n,q \le 2 \times 10^5)~ miêu tả số đỉnh và số truy vấn.
• Dòng thứ hai gồm ~n~ phần tử miêu tả dãy ~w~ ~(1 \le w_i \le 10^6)~.
• ~n-1~ dòng tiếp theo, dòng thứ ~i~ gồm hai số ~u_i~ và ~v_i~ miêu tả cạnh ~(u_i,v_i)~ của cây ~(1 \le u_i,v_i \le n)~.
• ~q~ dòng tiếp theo, dòng thứ ~i~ gồm hai số nguyên dương ~a_i,b_i~ ~(1 \le a_i,b_i \le n)~ miêu tả truy vấn tương ứng.

Output:

• Với mỗi truy vấn, in ra đáp án tương ứng.

Subtask:

• Subtask ~1~ (~25\%~ số điểm): ~n,q \le 2000~
• Subtask ~2~ (~25\%~ số điểm): ~a_i = 1~ với mọi truy vấn.
• Subtask ~3~ (~25\%~ số điểm): ~b_i = 1~ với mọi truy vấn.
• Subtask ~4~ (~25\%~ số điểm): Không có giới hạn gì thêm.

Sample Input 1

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

Sample Output 1

10
6
12
3

Explanation 1

Đối với hai truy vấn đầu tiên, gốc của cây bằng ~1~.

• ~S(1,2) = w[2] + w[6] + w[5] + w[4] = 10~
• ~S(1,6) = w[6] + w[5] = 6~

Đối với truy vấn thứ ba, gốc của cây bằng ~4~:

• ~S(4,2) = w[2] + w[6] + w[5] + w[1] + w[3] = 12~

Đối với truy vấn thứ tư, gốc của cây bằng ~2~

• ~S(2,1) = w[1] + w[3] = 3~

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]~