Một dãy số đẹp là một dãy gồm ~M~ số nguyên liên tục: ~i, i+1, …, i+M-1~. Hai dãy số đẹp được gọi là khác nhau nếu chúng bắt đầu với các giá trị ~i~ khác nhau.
Cho một dãy số nguyên ~A~ gồm ~M~ số ~a_1, a_2, …, a_M~, các phần tử trong dãy ~A~ có giá trị từ ~1~ đến ~N~ và một dãy số nguyên ~B~ gồm vô hạn số nguyên, các phần tử trong dãy ~B~ có giá trị từ ~1~ đến ~N~.
Từ các số trong dãy ~A~, có thể chọn tối đa ~S~ số nguyên trong dãy ~B~ để tạo thành một dãy số đẹp.
Yêu cầu
Hãy viết chương trình tính xem từ ~M~ số nguyên trong dãy ~A~, kết hợp với việc chọn tối đa ~S~ số nguyên trong dãy ~B~ có thể tạo được bao nhiêu dãy số đẹp khác nhau.
Dữ liệu vào
Dòng thứ nhất chứa ~3~ số nguyên ~N, M, S~ (~1 \leq N \leq 10^9; 1 \leq S < M \leq 10^5~) lần lượt là giá trị lớn nhất của các phần tử trong hai dãy số đã cho, số lượng phần tử trong dãy ~A~, số lượng phần tử tối đa có thể chọn từ dãy ~B~.
Dòng thứ hai chứa ~M~ số nguyên, là các phần tử trong dãy ~A~, mỗi số có giá trị từ ~1~ đến ~N~.
Lưu ý: Các số trên một dòng cách nhau ít nhất một dấu cách.
Kết quả ra
Một số nguyên, là số lượng dãy số đẹp khác nhau có thể tạo được theo cách mô tả ở trên.
Sample Input 1
10 5 2
7 1 3 5 6
Sample Output 1
5
Sample Input 2
11 6 2
5 5 5 5 5 5
Sample Output 2
0
Giải thích: Trong ví dụ 1, có thể tạo được 5 dãy số đẹp:
- Dãy thứ ~1~ gồm: ~1, 2, 3, 4, 5~ (chọn thêm ~2~ số: ~2~ và ~4~ từ dãy ~B~).
- Dãy thứ ~2~ gồm: ~2, 3, 4, 5, 6~ (chọn thêm ~2~ số: ~2~ và ~4~ từ dãy ~B~).
- Dãy thứ ~3~ gồm: ~3, 4, 5, 6, 7~ (chọn thêm ~1~ số: ~4~ từ dãy ~B~).
- Dãy thứ ~4~ gồm: ~4, 5, 6, 7, 8~ (chọn thêm ~2~ số: ~4~ và ~8~ từ dãy ~B~).
- Dãy thứ ~5~ gồm: ~5, 6, 7, 8, 9~ (chọn thêm ~2~ số: ~8~ và ~9~ từ dãy ~B~).
Comments