Gửi bài giải
Điểm:
0,75 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C++, Pascal, Python
Ibuki Suika rất thích uống rượu nhưng uống rượu không thì rất chán nên cô đi mua xiên que về ăn. Có ~n~ cửa hàng bán thịt xếp theo thứ tự từ trái sang phải và cửa hàng thứ ~i~ bán một miếng thịt loại ~a_i~. Cô muốn xiên của mình có ~m~ miếng thịt. Đến một cửa hàng cô hoặc là không mua cửa hàng đó hoặc mua miếng thịt và xiên vào que theo thứ tự. Hỏi có tất cả bao nhiêu cách xiên thịt khác nhau.
Input:
- Dòng đầu tiên là hai số tự nhiên ~n~ và ~m~.
- Dòng tiếp theo gồm ~n~ số lần lượt là loại thịt các cửa hàng bán.
Output:
- In ra một số nguyên duy nhất là số cách xiên thịt khác nhau modulo ~10^9+7~
Sample Test 1
Input:
3 2
1 2 3
Output:
3
Sample Test 2
Input:
4 3
2 3 3 2
Output:
3
Giải thích:
- Ở test 1 có 3 xiên là ~\{1, 2\}, \{1, 3\}, \{2, 3\}~
- Ở test 2 có 3 xiên là ~\{2, 3, 2\}, \{2, 3, 3\}, \{3, 3, 2\}~
Ràng buộc
- ~n, m \le 1000, a_i \le 10^9~