Pháo hoa

Nhằm chào mừng các ngày lễ lớn trong năm 2005 người ta đã chế tạo một loại đạn pháo hoa mới, khi bắn, đạn nổ thành bông hoa $2n$ cánh màu ($1\le n\le 30$). Nguyên vật liệu cho phép tạo được $m$ màu khác nhau, đánh số từ $1$ đến $m$ ($2\le m\le 32$).

Để đảm bảo tính mỹ thuật, việc chuyển tiếp màu giữa $2$ cánh hoa kề nhau phải tuân theo quy tắc chuyển màu cầu vồng sau đây:

• Bên cạnh cánh hoa màu $i$ phải là cánh hoa màu $i-1$ hoặc $i+1$, với $1<i<m$.
• Bên cạnh cánh hoa màu $1$ chỉ có thể là cánh hoa màu $2$.
• Bên cạnh cánh hoa màu $m$ chỉ có thể là cánh hoa màu $m-1$.

Một bông hoa không nhất thiết phải có đầy đủ $m$ màu. Các cánh hoa xếp thành một vòng tròn, nên mỗi bông hoa tương ứng với một vòng tròn $2n$ số thể hiện màu của các cánh hoa (cánh cuối cùng và cánh đầu tiên cũng kề nhau). Mỗi bông hoa được mô tả bằng dãy $2n$ số nguyên liệt kê các chỉ số màu của các cánh hoa theo chiều kim đồng hồ, bắt đầu từ một cánh bất kỳ.

Ví dụ, bông hoa $24$ cánh ($n=12$) có các cánh theo chiều kim đồng hồ lần lượt mang màu

3 4 3 2 1 2 3 4 3 2 1 2 3 4 3 2 1 2 3 4 3 4 3 2

có thể được mô tả bằng dãy số trên (bắt đầu đọc từ một cánh màu $3$), hoặc bằng bất kỳ dãy nào nhận được khi bắt đầu đọc từ một cánh khác.

Dãy có thứ tự từ điển nhỏ nhất trong các dãy có thể dùng để mô tả hoa được gọi là mã hoa. Khi đó, mã hoa của bông hoa trên sẽ là: 1 2 3 4 3 2 1 2 3 4 3 2 1 2 3 4 3 4 3 2 3 4 3 2.

Trong các ngày lễ, Ban tổ chức yêu cầu bắn các đạn pháo hoa $2n$ cánh có đúng $k$ cánh màu $C$ ($0\le k\le 2$). Các mã hoa thỏa mãn yêu cầu vừa nêu cũng được sắp xếp theo thứ tự từ điển và đánh số bắt đầu từ $1$.

Hơn nữa, nhằm tạo ra các hoa không giống nhau, đội bắn pháo hoa cần đảm bảo hai viên đạn pháo hoa bắn liên tiếp phải có mã khác nhau. Do vậy, người ta đã thiết kế một Hệ thống chụp ảnh và phân tích tự động để báo cho đội bắn pháo hoa biết số thứ tự của viên đạn pháo hoa vừa nổ trên trời. Em được giao viết chương trình giải quyết nhiệm vụ chính trong phần mềm phân tích tự động này.

Yêu cầu: Cho biết $n$, $m$, $k$ và $C$. Gọi $X$ là tập tất cả các mã hoa $2n$ cánh có đúng $k$ cánh màu $C$.

• Hãy xác định số lượng $p$ các phần tử của $X$.
• Cho một mã hoa nào đó trong tập $X$. Hãy xác định số thứ tự từ điển của nó trong $X$.

Dữ liệu vào

• Dòng đầu tiên chứa $4$ số nguyên $n$, $m$, $k$, $C$.
• Dòng tiếp theo chứa $2n$ số nguyên mô tả một mã hoa thuộc tập $X$.

Các số trên một dòng cách nhau ít nhất một dấu cách.

Dữ liệu ra

• Dòng đầu tiên in ra số nguyên $p$.
• Dòng tiếp theo in ra số thứ tự tìm được của mã hoa.

Ràng buộc

• $1\le n\le 30$, $2\le m\le 32$.
• $0\le k\le 2$, $1\le C\le m$.
• Mã hoa cho trong dữ liệu vào thuộc tập $X$.
• Các đáp số không vượt quá ${10}^{17}$.

Ví dụ