Bí mật của trại Felicity

Cho một xâu nhị phân $b=b_0{b}_1\dots b_{n-1}$ có độ dài $n$ (mỗi ký tự là $0$ hoặc $1$).

Có $n+1$ vị trí có thể đặt nhát cắt: trước $b_0$, giữa $b_0$ và $b_1$, giữa $b_1$ và $b_2$, ..., và sau $b_{n-1}$.

Xét một tập gồm $k$ nhát cắt ($k\ge 2$) đặt tại $k$ vị trí khác nhau. Khi đó giữa hai nhát cắt liên tiếp sẽ có một xâu con nhị phân, tạo thành đúng $k-1$ xâu con. Các ký tự nằm trước nhát cắt đầu tiên và sau nhát cắt cuối cùng bị bỏ đi (không tính đến). Mỗi xâu con được đọc như một số nhị phân (cho phép chữ số $0$ ở đầu).

Gọi $m$ là số lớn nhất trong $k-1$ số thu được. Tập $k$ nhát cắt được gọi là hợp lệ nếu tất cả các số thu được đều dương và tập hợp các số thu được chứa tất cả các số nguyên từ $1$ đến $m$.

Ví dụ với xâu $101101001110$ và $5$ nhát cắt tạo thành:

$$10\mid 11\mid 010\mid 01\mid 1\mid 10$$

thu được $4$ xâu con $11,010,01,1$ ứng với các số $3,2,1,1$. Ở đây $m=3$; mọi số đều dương và ta có đủ các số từ $1$ đến $3$, nên đây là một tập $5$ nhát cắt hợp lệ.

Gọi $f(k)$ là số tập hợp lệ gồm đúng $k$ nhát cắt. Hai tập nhát cắt được coi là khác nhau nếu có một nhát cắt thuộc tập này nhưng không thuộc tập kia.

Hãy tính

$$s=\sum _{k\ge 2}f(k)$$

và in ra $s$ theo modulo ${10}^9+7$.

Dữ liệu vào

• Dòng thứ nhất chứa số nguyên $n$ — độ dài của xâu.
• Dòng thứ hai chứa xâu nhị phân độ dài $n$.

Dữ liệu ra

• In ra một số nguyên duy nhất: giá trị $s$ theo modulo ${10}^9+7$.

Ràng buộc

• $1\le n\le 75$.
• Xâu chỉ gồm các ký tự $0$ và $1$.

Ví dụ