Bài toán đếm dãy con tăng: cho dãy ~A~ độ dài ~N~, hãy đếm số lượng dãy con tăng nghiêm ngặt có độ dài đúng ~K~. Kết quả yêu cầu lấy theo modulo ~10^9+7~.

Yêu cầu

• Cho dãy số nguyên ~A~ độ dài ~N~ và số nguyên dương ~K~.
• Hãy đếm số lượng dãy con tăng nghiêm ngặt độ dài đúng ~K~ của ~A~ (nếu chọn chỉ số ~i_1<i_2<\dots<i_K~ thì ~A_{i_1}<A_{i_2}<\dots<A_{i_K}~).</li>
• In kết quả theo modulo ~10^9+7~

Dữ liệu

• Dòng đầu: hai số nguyên dương ~N~, ~K~ ~(1\le N\le 10^5,\ 1\le K\le 20)~.
• Dòng thứ hai: ~N~ số nguyên ~A_i~ với ~1\le A_i\le N~.

Kết quả

• Một số nguyên: số lượng dãy con tăng độ dài ~K~ của ~A~, lấy theo modulo ~10^9+7~.

Ví dụ

Ví dụ 1

Input

4 2
1 2 4 3

Output

5

Ví dụ 2

Input

3 3
1 2 3

Output

1

Giải thích

Ví dụ 1

Các cặp thoả mãn với ~K=2~ (chọn ~i<j~ và ~A_i<A_j~): ~(1,2),(1,3),(1,4),(2,3),(2,4)~ nên có ~5~ dãy con tăng độ dài ~2~.</p>

Ví dụ 2

Với ~A=[1,2,3]~, chỉ có đúng ~1~ dãy con tăng độ dài ~3~ là chính dãy ban đầu.

Chấm điểm

• 100% số điểm cho lời giải ~\mathcal{O}(K\,N\log N)~ dựa trên quy hoạch động cộng dồn theo giá trị với Fenwick/Segment Tree (do ~1\le A_i\le N~):

  • Duyệt ~i=1..N~; cập nhật từ ~\ell=\min(K,i)\to 2~:

  $$ \mathrm{dp}[\ell][A_i] \mathrel{+}= \sum_{x=1}^{A_i-1} \mathrm{dp}[\ell-1][x], $$

  với khởi tạo ~\mathrm{dp}[1][A_i]\mathrel{+}=1~.

  • Các tổng tiền tố tính nhanh bằng Fenwick/Segment Tree trên trục giá trị ~[1..N]~.
  • Kết quả là ~\sum_x \mathrm{dp}[K][x]~ modulo ~10^9+7~.
• Lưu ý tối ưu I/O; dùng kiểu 64-bit cho trung gian trước khi lấy modulo.