Tập số

Trên tập số $\{1,2,...,n\}$, Alice tiến hành xóa đi $k$ ($k<n$) số $a_1,a_2,...,a_k$ để nhận được tập $S$. Một cách chọn các số trên tập $S$ được gọi là cách chọn tối ưu bậc $d$ nếu:

• Hiệu hai số bất kì được chọn có giá trị tuyệt đối lớn hơn $d$;
• Số lượng số được chọn là lớn nhất.

Ví dụ, trên tập số $\{1,2,3,4,5,6,7,8\}$, xóa đi ba số $2,3,8$ được tập $S=\{1,4,5,6,7\}$, ba tập $\{1,4,6\}$, $\{1,4,7\}$ và $\{1,5,7\}$ đều là cách chọn tối ưu bậc $1$.

Cho $n,k,d$ và dãy $a_1,a_2,...,a_k$, hãy giúp Alice tính số lượng số chọn được trong cách chọn tối ưu bậc $d$ và số cách chọn tối ưu. Chú ý, hai cách chọn được gọi là khác nhau nếu tồn tại một số của $S$ thuộc trong cách chọn này nhưng không thuộc trong cách chọn kia.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên dương $n,k,d$ ($k<n\le {10}^7$; $k\le {10}^5$; $d\le n$);
• Dòng thứ hai chứa $k$ số nguyên dương phân biệt $a_1,a_2,...,a_k$ ($a_i\le n$, $1\le i\le k$);

Dữ liệu ra

Hai dòng, dòng thứ nhất là số lượng số chọn được trong cách chọn tối ưu, dòng thứ hai là số cách chọn tối ưu chia dư cho (${10}^9+7$).

Ràng buộc

• $k<n\le {10}^7$
• $k\le {10}^5$
• $d\le n$
• Subtask 1 (20 điểm): $n-k\le 20$
• Subtask 2 (25 điểm): $n-k\le 200$
• Subtask 3 (25 điểm): $n-k\le 2\times {10}^5$
• Subtask 4 (30 điểm): Không có ràng buộc gì thêm.

Ví dụ