INCSEQ VN

View as PDF

Submit solution


Points: 0.34 (partial)
Time limit: 0.38s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
Neal Wu -SPOJ
Problem types
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, 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~).


Comments

Please read the guidelines before commenting.