Dãy nghịch thế độ dài K

View as PDF

Submit solution


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

Problem source:
Dmitry Gozman Contest 1
Problem types
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho dãy ~N~ số nguyên dương ~A_1~, ...~A_N~ là một hoán vị của ~1~, ~2~, ~3~, ...~N~.

Một dãy nghịch thế độ dài ~k~ là ~1~ dãy ~A_{j_1} > A_{j_2} > A_{j_3} \dots > A_{j_k}~ với ~j_1 < j_2 < j_3 < \dots < j_k~. Hãy đếm xem có tất cả bao nhiêu dãy nghịch thế độ dài ~k~.

Input

Dòng ~1~: ~2~ số nguyên dương ~N~ và ~k~ (~2 \leq N \leq 10000~, ~2 \leq k \leq 10~).

Dòng ~2~: ~N~ số nguyên dương ~A_1~ ...~A_N~.

Output

Giả sử ~T~ là số lượng dãy nghịch thế có độ dài ~k~, hãy ghi ra ~T~ mod ~10^9~.

Sample Input

3 2
3 2 1

Sample Output

3

Comments

Please read the guidelines before commenting.


There are no comments at the moment.