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

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

Example

2 100
1 2

1 2

Cho dãy số nguyên dương \(A_1,A_2,...,A_N\). Một bộ ba (\(i,j,k\)) được gọi là đẹp của dãy \(A\) đã cho nếu thỏa mãn:

• \(1 \le i \le j < k \le N\).
• Gọi dãy con liên tiếp \(A_i,A_{i+1},...,A_j\) là \(X\) và dãy con liên tiếp \(A_{j+1},A_{j+2},...,A_k\) là \(Y\) thì hai dãy này thỏa mãn:
  • Với mỗi giá trị xuất hiện trong dãy \(X\) thì cũng xuất hiện trong dãy \(Y\).
  • Với mỗi giá trị xuất hiện trong dãy \(Y\) thì cũng xuất hiện trong dãy \(X\).

Yêu cầu: Cho dãy số \(A\), hãy đếm số bộ ba đẹp (\(i,j,k\)) của dãy số này.

Input

• Dòng đầu chứa số nguyên \(N\) (\(1 \le N \le 2 \times 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên \(A_i\) (\(1 \le A_i \le N\)).

Output

• Ghi ra một số nguyên là số lượng bộ ba đẹp của dãy đã cho.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(N \le 500\).
• Subtask \(2\) (\(20\%\) số điểm): \(N \le 5000\).
• Subtask \(3\) (\(20\%\) số điểm): \(A_i \le 50\).
• Subtask \(4\) (\(20\%\) số điểm): mỗi giá trị xuất hiện đúng hai lần.
• Subtask \(5\) (\(20\%\) số điểm): không có ràng buộc gì thêm.

Example

7
3 1 2 1 2 3 1

4

Có \(2^n\) gia đình cùng sống trong một khu phố, các gia đình được đánh số từ \(1\) đến \(2^n-1\). Sau mỗi ngày, mỗi gai đình đều gửi tặng cho tất cả các gia đình khác một số quả, số quả này tính dựa trên số quả gia đình đó nhận được ngày trước đó. Cụ thể, gọi \(f_i\) là tổng số quả gia đình \(i\) nhận được ngày \(d\) thì sang ngày tiếp theo \(d+1\), gia đình \(i\) sẽ gửi cho gia đình \(j\) (\(j \neq i\)) số quà là \(f_i \times (2 \times (i | j) - i - j)\), trong đó \(|\) là phép toán \(OR\).

Yêu cầu: Cho biết số gia đình trong khu phố và số quả mỗi gia đình được nhận ở ngày \(0\), tính số quả mỗi gia đình nhận được ở ngày \(k\).

Input

• Dòng đầu tiên gồm hai số nguyên dương \(n,k\) (\(n \le 20, k \le 10^9\)).
• Dòng thứ hai chứa \(2^n\) số nguyên không âm, số thứ \(i\) là số quả gia đình \(i\) nhận được ở ngày hiện tại. Các số không vượt quá \(10^9\).

Output

• Ghi ra \(n\) số nguyên trên một dòng, số thứ \(i\) là tổng số quả mà gia đình \(i\) nhận được vào ngày thứ \(k\), lấy phần dư khi chia cho (\(10^9+7\)).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \le 10, k \le 5\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \le 10, k \le 1000\).
• Subtask \(3\) (\(30\%\) số điểm): \(k \le 10^5\).
• Subtask \(4\) (\(10\%\) số điểm): không có ràng buộc gì thêm.

Example

2 1
3 4 5 1

17 20 19 22