Mizzie là một người rất thích giải các bài toán về tin học. Lần này, Mizzie có một dãy nhị phân độ dài . Mizzie được phép thực hiện thao tác, tại mỗi thao tác, Mizzie được phép chọn một trong vị trí đó và đảo ngược bit tại vị trí đó ( thành hoặc thành ).
Sau thao tác này, Mizzie phải đưa về dãy bit với toàn bit . Việc này không khó với Mizzie, tuy nhiên, Mizzie muốn biết số cách khác nhau để mình thực hiện công việc này.
Dữ liệu vào:
Dòng đầu tiên ghi ra số nguyên dương là số lượng test ;
Mỗi test bắt đầu bằng số nguyên dương và ;
Tiếp sau đó là số nguyên thể hiện dãy bit của Mizzie.
Dữ liệu ra:
Gồm dòng, mỗi dòng là một số nguyên theo modulo tương ứng là kết quả của các test trong dữ liệu vào.
