Cho một dãy gồm \(n\) số nguyên dương đôi một khác nhau \(a_1,a_2,...a_n\), một tập \(DSET\) nếu là tập con có lực lượng lớn nhất trong các tập con của tập \(\{a_1,a_2,...,a_n\}\) và nếu \(x\) thuộc tập thì \(2x\) sẽ không thuộc tập.

Yêu cầu: Cho \(a_1,a_2,...,a_n\), hãy tìm lực lượng của tập \(DSET\) và số cách khác nhau để chọn tập \(DSET\).

Input

• Dòng đầu ghi hai số nguyên \(n\) và \(k\) (\(k \le 10^9\)).
• Dòng thứ hai gồm \(n\) số nguyên dương \(a_1,a_2,...,a_n\) (\(a_i \le 10^9\)).

Output

• Gồm một dòng chứa hai số \(s,d\), trong đó \(s\) là lực lượng của tập \(DSET\), \(d\) là số cách khác nhau để chọn tập \(DSET\) chia dư cho \(k\).

Example

2 100
1 2

1 2

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n \le 20\).
• Subtask \(2\) (\(40\%\) số điểm): \(n \le 10^6\).
• Subtask \(3\) (\(10\%\) số điểm): \(n \le 10^9, a_i = i\) (khi đó file dữ liệu vào chỉ gồm một dòng chứa hai số nguyên \(n,k\)).