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.

Input

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

Output

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 1

8 3 1
2 3 8

Sample Output 1

3
3

Subtasks

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