hoang24112009
:
Tham gia Đại hội thể thao có n vận động viên có chiều cao đổi một phân biệt. Đánh số các vận động viên từ 1 đến n, vận động viên thứ t (1 ≤ t ≤ n) có chiều cao ht. Theo yêu cầu n vận động viên sẽ được xếp thành một hàng dọc sao cho không tồn tại bộ ba vận động viên i,j, k thỏa mãn:
1) Vận động viên i đứng trước vận động viên j, vận động viên j đứng trước vận động viên k; 2) Chiều cao vận động viên j thấp hơn chiều cao vận động viên i và chiều cao vận động viên i thấp hơn chiều cao vận động viên k.
Yêu cầu: Gọi s là số cách xếp thỏa mãn, tính s % (10 + 7), trong đó % là phép toán chia lấy dư.
Input
- Dòng đầu chứa số nguyên dương n (n >3);
Dòng thứ hai gồm n số nguyên dương h, h2, ..., hn (hi <10).
Output
Gồm một dòng chứa một số nguyên là giá trị s % (10 + 7).
Input
3
1 2 3
Output
5
Subtask 1 (20 điểm): n ≤ 10;
Subtask 2 (30 điểm): n ≤ 20;
Subtask 3 (30 điểm): n ≤ 10^3;
Subtask 4 (20 điểm): n ≤ 10^6