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