Dãy số ~A~ gồm ~n~ số nguyên khác nhau từng đôi: ~a_{1}~, ~a_{2}~, ..., ~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_{1}~, hoặc giữa ~a_{i}~, ~a_{i + 1}~ với ~1 \leq 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 \leq i \leq 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~.

Input

• 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 \leq n \leq 10^{5}~, ~|b| \leq 10^{6}~.
• Dòng thứ hai chứa ~n~ số nguyên ~a_{1}~, ~a_{2}~, ..., ~a_{n}~, mỗi số có trị tuyệt đối ~\leq 10^{6}~.
• 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.

Output

• 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^{9}~ 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~.

Giới hạn

Có ~50\%~ số test có ~n \leq 15~.

Sample Input

4 2012
55 25 9 20

Sample Output

2
8