Một dãy số đẹp là một dãy gồm \(m\) số nguyên liên tục: \(i,\ i + 1,\ \ldots,\ 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},\ \ldots,\ 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 có \(m\) phần tử.

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: số lượng dãy số đẹp khác nhau có thể tạo được theo cách mô tả ở trên.

Ví dụ 1:

Ví dụ 2:

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).