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

Yêu cầu: 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 từ thiết bị vào chuẩn (bàn phím) có khuôn dạng:

• Dòng đầu chứa ba số nguyên dương \(n,k,d (k<n≤10^7;k≤10^5;d≤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≤n, 1≤i≤k);\)

Kết quả: Ghi ra thiết bị ra chuẩn (màn hình) 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).\)

Sample Input

8 3 1
2 3 8

Sample Output

3
3

Ràng buộc

• Subtask 1 (20 điểm): \(n-k≤20;\)

• Subtask 2 (25 điểm): \(n-k≤200;\)

• Subtask 3 (25 điểm): \(n-k≤2×10^5;\)

• Subtask 4 (30 điểm): Không có ràng buộc gì thêm.