Giải bài trực tuyến

Dãy số A gồm n số nguyên khác nhau từng đôi: a₁, a₂, ..., a_n được gọi là hoàn hảo nếu như nó thỏa mãn tính chất sau: "Không tồn tại 3 chỉ số p < q < r sao cho hoặc a_p < a_q < a_r hoặc a_p < a_r < a_q hoặc a_q < a_p < a_r".

Cho A là dãy hoàn hảo, một phép chèn một số nguyên b vào dãy A để tạo thành dãy B (b có thể được chèn vào trước a₁, hoặc giữa a_i, a_i+1 với 1 ≤ i < n, hoặc sau a_n) được gọi là hợp lệ nếu như các điều kiện sau được thỏa mãn:

• b > a_i với mọi 1 ≤ i ≤ n
• Dãy B là hoàn hảo

Yêu cầu

• Hãy tính số lượng phép chèn hợp lệ một số b vào dãy A.
• Giả sử B là một dãy thu được bởi một phép chèn hợp lệ b vào A. Hãy tính số lượng dãy hoàn hảo thu được bằng cách hoán vị các phần tử của B.

Dữ liệu

• Dòng thứ nhất chứa hai số nguyên n và b tương ứng với số lượng phần tử của dãy A và số nguyên cần chèn. Biết rằng 3 ≤ n ≤ 10⁵, |b| ≤ 10⁶.
• Dòng thứ hai chứa n số nguyên a₁, a₂, ..., a_n, mỗi số có trị tuyệt đối ≤ 10⁶.
• Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Kết quả

• Dòng thứ nhất ghi một số nguyên là số phép chèn hợp lệ số b vào dãy A.
• Dòng thứ hai ghi một số nguyên là phần dư trong phép chia cho 10⁹ của số lượng dãy hoàn hảo thu được bằng cách hoán vị các phần tử của dãy B. Nếu không thể chèn được b vào dãy A, ta ghi ra 0.

Ví dụ

Input:
4 2012
55 25 9 20

Output:
2
8

Giới hạn

Có 50% số test có n ≤ 15.