Trên tập số \(\{1, 2, \ldots, n\}\), Alice tiến hành xóa đi số \(k\) \((k \leq n)\) số \(a_{1}, a_{2}, \ldots, 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\); và 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}, \ldots, 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 \leq 10^{7}, k \leq 10^{5}, d \leq n)\).
• Dòng thứ hai chứa \(k\) số nguyên dương phân biệt \(a_{1}, a_{2}, \ldots, a_{k}\) \((a_{i} \leq n, 1 \leq i \leq k)\).

Dữ liệu ra

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

Scoring

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

Input 1

8 3 1
2 3 8

Output 1

3
3