Tập hợp

Cho một dãy gồm \(n\) số nguyên dương đôi một khác nhau \(a_{1}, a_{2}, a_{3}, ... , a_{n}\) một tập được gọi là 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_{3}, ... , 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_{3}, ... , 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 gồm hai số nguyên \(n\) và \(k\) \((k ≤ 10^9)\)

• Dòng thứ hai gồm \(n\) số nguyên dương \(a_{1}, a_{2}, a_{3}, ... , a_{n}\) \((a_i ≤ 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\) điểm): \(n ≤ 20\);

Subtask \(2\) (\(40\) điểm): \(n ≤ 10^6\);

Subtask \(3\) (\(10\) điểm): \(n \leq 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\)).