Độ phức tạp ghép cặp khiêu vũ

Cho một số nguyên $n$. Có hai nhóm, mỗi nhóm gồm $2^n$ thành viên được đánh số từ $0$ đến $2^n-1$.

Ta ghép cặp mỗi thành viên $i$ của nhóm thứ nhất với thành viên $i\oplus x$ của nhóm thứ hai, trong đó $x$ là một số nguyên cố định cho trước và $\oplus$ là phép XOR (hoặc loại trừ) trên biểu diễn nhị phân.

Độ phức tạp của cách ghép là số cặp $((a,b),(c,d))$ thỏa mãn $a<c$ nhưng $b>d$, với $(a,b)$ và $(c,d)$ là hai cặp ghép khác nhau (nghĩa là số cặp "nghịch thế" trong hoán vị $i\mapsto i\oplus x$).

Số $x$ được cho dưới dạng một chuỗi nhị phân độ dài $n$ (có thể có các chữ số $0$ ở đầu). Hãy tính độ phức tạp của cách ghép, lấy phần dư khi chia cho ${10}^9+7$.

Dữ liệu vào

Một dòng duy nhất chứa chuỗi nhị phân $x$ độ dài $n$ (chuỗi có thể có các chữ số $0$ ở đầu).

Dữ liệu ra

In ra một số nguyên: độ phức tạp của cách ghép, lấy phần dư khi chia cho ${10}^9+7$.

Ràng buộc

• $1\le n\le 100$
• $x$ chỉ gồm các chữ số $0$ và $1$.

Ví dụ