Cho một dãy gồm ~n~ phần tử đôi một khác nhau, hãy đếm số dãy con tăng ngặt có đúng ~k + 1~ phần tử.

Dữ liệu đảm bảo đáp án không vượt quá ~8 \cdot 10^{18}~.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~ — độ dài của dãy và số ~k~.
• ~n~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~a_i~ — phần tử thứ ~i~ của dãy. Các giá trị ~a_i~ đôi một khác nhau.

Kết quả

In ra một số nguyên duy nhất — số dãy con tăng ngặt có đúng ~k + 1~ phần tử.

Ví dụ

Đầu vào:

5 2
1
2
3
5
4

Đầu ra:

7

Giải thích: Bảy dãy con tăng có ~3~ phần tử là ~(1,2,3)~, ~(1,2,5)~, ~(1,2,4)~, ~(1,3,5)~, ~(1,3,4)~, ~(2,3,5)~ và ~(2,3,4)~.

Giới hạn

• ~1 \le n \le 10^5~
• ~0 \le k \le 10~
• ~1 \le a_i \le n~, các ~a_i~ đôi một khác nhau

Gọi ~f_{j,i}~ là số dãy con tăng có ~j~ phần tử và kết thúc tại vị trí ~i~. Ta có ~f_{1,i} = 1~ và ~f_{j,i} = \sum f_{j-1,t}~ với ~t < i~, ~a_t < a_i~. Hãy dùng ~k + 1~ cây chỉ số nhị phân, cây thứ ~j~ lưu tổng các giá trị ~f_{j,\cdot}~ theo giá trị của phần tử.