Một xâu được gọi là xâu đối xứng nếu đọc xâu đó từ trái qua phải thu được xâu giống như đọc từ phải qua trái. Một xâu nhị phân được gọi là xâu nhị phân gần đối xứng nếu sau khi sắp xếp lại các ký tự của nó ta thu được một xâu đối xứng.

Ví dụ: Các xâu nhị phân ‘110’, ‘1010’, ‘10000’ là các xâu nhị phân gần đối xứng vì sau khi sắp xếp lại các ký tự của chúng ta thu được các xâu tương ứng‘101’, ‘1001’, ‘00100’ là các xâu đối xứng.

Yêu cầu: Cho hai số nguyên n, t và xâu nhị phân gần đối xứng s độ dài n,tìm số nhị phân gần đối xứng có độ dài n có thứ tự từ điển thứ t và tìm thứ tự từ điển của xâu s.

Dữ liệu: Vào trong file văn bản NBS.INP có dạng:

• Dòng 1:chứa số nguyên dương n (n  <= 1E6 ).

• Dòng 2: chứa số nguyên dương t  (t  <= 1E100).

• Dòng 3: chứa xâu s.

Kết quả:Ghi ra file văn bản NBS.OUT có dạng:

• Dòng 1: xâu nhị phân gần đối xứng độ dài n thứ  t;

• Dòng 2: số thứ tự của xâu nhị phân gần đối xứng s mod 111539786.