Gửi bài giải


Điểm: 0,34 (OI)
Giới hạn thời gian: 0.38s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout

Nguồn bài:
Neal Wu -SPOJ
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho ~1~ dãy số gồm ~N~(~0~ ~<~ ~N~ ~\leq~ ~10000~) số tự nhiên ~S_1~, ~S_2~, ..., ~S_n~ (~0~ ~\leq~ ~S_i~ ~\leq~ ~10^5~), Hãy đếm số lượng dãy con tăng có độ dài ~K~(~0~ ~<~ ~k~ ~\leq~ ~50~).

Input

Dòng đầu tiên là hai số tự nhiên ~N~ và ~K~.

~N~ dòng tiếp sau mô tả dãy ~S~.

Output

Số lượng dãy con thỏa mãn theo Module ~5000000~.

Sample Input

4 3
1
2
2
10

Sample Output

2

Note

Giải thích: Có ~2~ dãy con thỏa mãn (~S_1~, ~S_2~, ~S_4~) và (~S_1~, ~S_3~, ~S_4~): (~1~, ~2~, ~10~).


Bình luận

Hãy đọc nội quy trước khi bình luận.