# Beautiful String

FireGhost được bạn tặng xâu nhị phân $s$ có độ dài $n$. Vì chưa cảm thấy hài lòng với độ đẹp của xâu $s$, FireGhost quyết định tạo ra xâu $t$ bằng cách thực hiện các thao tác sau:

- Gọi độ dài hiện tại của xâu $s$ là $m$. FireGhost sẽ chọn ngẫu nhiên một số trong khoảng $[1, m]$ (giả sử là $k$).
- FireGhost lấy ra xâu tiền tố độ dài $k$ của xâu $s$ và bỏ ra khỏi xâu $s$. Nếu kí tự đầu của xâu tiền tố là $0$, FireGhost sẽ lật toàn bộ xâu tiền tố lại (đổi $0$ thành $1$ và ngược lại).
- Sau đó, FireGhost sẽ thêm xâu tiền tố vừa được thay đổi vào cuối xâu $t$.
- Tiếp tục thực hiện cho đến khi xâu $s$ rỗng.

Ví dụ về một khả năng xảy ra: $s = 1001011$:

- Ở bước đầu tiên, FireGhost chọn $k = 4$. Anh ấy lấy ra xâu tiền tố $1001$. Vì kí tự đầu của xâu tiền tố này là $1$ nên xâu tiền tố không thay đổi. Sau đó, FireGhost sẽ thêm xâu tiền tố này vào cuối xâu $t$. Lúc này, $s = 011$, $t = 1001$.
- Ở bước thứ hai, FireGhost chọn $k = 3$. Anh ấy lấy ra xâu tiền tố $011$. Vì kí tự đầu của xâu tiền tố này là $0$ nên xâu tiền tố này sẽ bị lật thành $100$. Sau đó, FireGhost sẽ thêm xâu tiền tố này vào cuối xâu $t$. Lúc này, $s = \emptyset$, $t = 1001100$.

Gọi độ đẹp của một xâu là số kí tự $1$ nằm trong xâu đó. Xét tất cả khả năng có thể xảy ra lên xâu $s$, hãy cho biết giá trị kì vọng của độ đẹp xâu $t$ là bao nhiêu?

# Input

Dòng đầu tiên gồm số nguyên $n$ ($1 \le n \le 5 \cdot 10^5$) --- độ dài của xâu $s$.

Dòng thứ hai gồm xâu nhị phân $s$ độ dài $n$.

# Output

In ra một dòng duy nhất là đáp án của bài toán: giá trị kì vọng của độ đẹp xâu $t$ khi xét tất cả khả năng xảy ra. Đáp án làm tròn đến $9$ chữ số sau dấu thập phân.

# Lời giải

Gọi $f[i]$ là giá trị kì vọng của xâu tạo ra từ $s[1...n]$.

Dễ thấy, $f[i] = \frac{1}{n - i + 1} \cdot \sum_{j = i}^{n} f[j + 1]\ +$ (số vị trí $k$ thỏa mãn $i \le k \le j$ và $s[i] = s[k]$). Tuy nhiên, độ phức tạp của cách làm này là $O(n^2)$.

Nhận xét: $\sum_{j = i}^{n}$ (số vị trí $k$ thỏa mãn $i \le k \le j$ và $s[i] = s[k]$) $= \sum_{s_j = s_i} (n - j + 1)$. Với nhận xét này, ta có thể cải tiến lời giải lên $O(n)$.