Cho mảng ~a~ gồm ~n~ phần tử ~a_1, a_2, ..., a_n~ và một số nguyên ~k~. Tìm đoạn ~[l,r]~ thỏa mãn ~(r-l+1) \ge k~, và tổng các số trong đoạn ~[l,r]~ trừ đi tổng của ~k~ số lớn nhất trong đoạn ~[l,r]~ đạt giá trị lớn nhất.

Nói cách khác, đặt ~S[l,r]~ = tổng các số trong đoạn ~[l,r]~, ~T[l,r]~ = tổng ~k~ số lớn nhất trong đoạn ~[l,r]~, hãy tìm ~[l,r]~ thỏa mãn ~S[l,r] - T[l,r]~ đạt giá trị lớn nhất.

Yêu cầu: In ra giá trị lớn nhất tìm được.

Input

Vào từ file văn bản maxsub.inp:

• Dòng đầu gồm hai số nguyên ~n, k~ (~1 \le n \le 3 \cdot 10^5, 0 \le k \le min(n, 100)~).

• Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, ..., a_n~ (~|a_i| \le 10^9~).

Output

Đưa ra file văn bản maxsub.out một số nguyên duy nhất là kết quả cần tìm.

Scoring

Sample Input 1

10 2
-5 9 -1 -1 6 8 -10 10 -2 5

Sample Output 1

5

Sample Input 2

4 2
-6 -8 4 10

Sample Output 2

0

Sample Input 3

2 1
2 6

Sample Output 3

2

Cho dãy ~a~ có ~n~ phần tử: ~a_1, a_2, \ldots, a_n~.

Yêu cầu: Hãy đếm số cặp vị trí ~i~, ~j~ sao cho ~a_i \ge a_j~ và tổ hợp chập ~a_j~ của ~a_i~ chẵn. Hay nói cách khác, bạn hãy đếm số lượng cặp số ~i, j~ sao cho:

• ~1 \le i, j \le n~.

• ~a_i \ge a_j~.

• ~\binom{a_i}{a_j} \equiv 0 \pmod{2}~.

Input

Vào từ file văn bản evencomb.inp:

• Dòng đầu tiên ghi một số nguyên ~n~ là số phần tử của dãy ~a~ (~1 \le n \le 10^6~).

• Dòng thứ hai ghi ~n~ số nguyên mô tả dãy số ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le 10^6~)

Output

Xuất ra file văn bản evencomb.out một số nguyên là số cặp ~i~, ~j~ thỏa mãn yêu cầu đề bài.

Scoring

Sample Input 1

7
4 7 4 2 7 1 1

Sample Output 1

8

Notes

Giải thích ví dụ:

Các cặp số ~(i, j)~ thỏa mãn điều kiện đề bài là:

1. ~(1, 4)~, ~\binom{a_{1}}{a_{4}} = \binom{4}{2} = 6~

2. ~(1, 6)~, ~\binom{a_{1}}{a_{6}} = \binom{4}{1} = 4~

3. ~(1, 7)~, ~\binom{a_{1}}{a_{7}} = \binom{4}{1} = 4~

4. ~(3, 4)~, ~\binom{a_{3}}{a_{4}} = \binom{4}{2} = 6~

5. ~(3, 6)~, ~\binom{a_{3}}{a_{6}} = \binom{4}{1} = 4~

6. ~(3, 7)~, ~\binom{a_{3}}{a_{7}} = \binom{4}{1} = 4~

7. ~(4, 6)~, ~\binom{a_{4}}{a_{6}} = \binom{2}{1} = 2~

8. ~(4, 7)~, ~\binom{a_{4}}{a_{7}} = \binom{2}{1} = 2~

Cho ba số ~n~, ~m~, ~k~ và dãy ~b~ gồm ~n - m + 1~ phần tử, đếm số dãy ~a~ thỏa mãn:

• Dãy ~a~ gồm ~n~ phần tử;

• Mọi phần tử của dãy ~a~ đều có giá trị nằm trong khoảng từ ~1~ đến ~k~, hay ~1 \le a_i \le k~ với ~\forall\ 1 \le i \le n~;

• Nếu ~b_i \ne -1~ thì ~\displaystyle b_i = \max_{i \le j \le i + m - 1} a_j~ với ~\forall\ 1 \le i \le n - m + 1~.

Vì số lượng dãy ~a~ thỏa mãn có thể rất lớn, vì vậy chỉ cần đưa ra phần dư của kết quả trong phép chia cho ~1\ 000\ 000\ 007~.

Input

Vào từ file văn bản SEQUENCE.INP:

• Dòng đầu tiên chứa ba số nguyên dương ~n~, ~m~, ~k~ (~1 \le m \le n \le 100\ 000~, ~2 \le k \le 100\ 000~).

• Dòng thứ hai chứa ~n - m + 1~ số nguyên lần lượt là ~b_1, b_2, \dots, b_{n - m + 1}~ (~b_i = -1~ hoặc ~1 \le b_i \le k~).

Output

Ghi ra file văn bản SEQUENCE.OUT:

• Ghi ra trên một dòng duy nhất là phần dư của số dãy ~a~ thỏa mãn điều kiện đề bài trong phép chia cho ~1\ 000\ 000\ 007~.

Scoring

Sample Input 1

6 2 4
2 2 4 -1 1

Sample Output 1

5

Sample Input 2

6 3 2
-1 1 2 1

Sample Output 2

0

Notes

'Trong ví dụ đầu tiên, có ~5~ dãy ~a~ thỏa mãn đề bài:

• 1 2 1 4 1 1

• 1 2 2 4 1 1

• 2 1 2 4 1 1

• 2 2 1 4 1 1

• 2 2 2 4 1 1

Trong ví dụ thứ hai, không có dãy ~a~ nào thỏa mãn đề bài.