đượ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 dự đị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 số ~k~ trong khoảng ~[1, m]~.
FireGhost lấy xâu tiền tố độ dài ~k~ của xâu ~s~ 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à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 khi ~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 đó.
Vì xâu ~t~ nhận được là ngẫu nhiên nên FireGhost không biết liệu độ đẹp của xâu ~t~ có tốt hơn xâu ~s~ hay không, hãy giúp FireGhost tính giá trị kì vọng của độ đẹp xâu ~t~ nhé!
Gọi ~X = [k_1, k_2, ..., k_c]~ là tập hợp độ dài các thao tác lần lượt thực hiện; ~f(X)~ là độ đẹp của xâu ~t~ nhận được sau khi thực hiện các thao tác trong ~X~; ~g(X)~ là xác suất thực hiện các thao tác trong ~X~. Gọi ~P~ là tập hợp chứa tất cả các tập hợp các thao tác có thể xảy ra. Giá trị kì vọng của độ đẹp xâu ~t~ được tính bằng ~\sum_{X \in P} f(X) \cdot g(X)~.
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à giá trị kì vọng của độ đẹp xâu ~t~. Đáp án của bạn sẽ được chấp nhận nếu sai số không vượt quá ~10^{-9}~. Nói cách khác, gọi đáp án của bạn là ~a~, đáp án của jury là ~b~, đáp án của bạn sẽ được chấp nhận nếu ~\frac{|a - b|}{max(1,\ |b|)} \le 10^{-9}~.
Subtask
~20\%~ số test có ~n \le 20~.
~30\%~ số test khác có ~n \le 5000~.
~50\%~ số test còn lại không có ràng buộc gì thêm.
Sample Input 1
3
011
Sample Output 1
2.000000000000000
Sample Input 2
5
01010
Sample Output 2
3.266666666666667
Notes
Trong test ví dụ thứ nhất, xét tất cả các tập hợp độ dài có thể xảy ra:
~[1, 1, 1]~: FireGhost nhận được xâu ~t = 111~. Độ đẹp của xâu ~t~ là ~3~. Xác suất xảy ra cách chọn (khả năng) này là ~\frac{1}{3} \cdot \frac{1}{2} \cdot \frac{1}{1} = \frac{1}{6}~.
~[1, 2]~: FireGhost nhận được xâu ~t = 111~. Độ đẹp của xâu ~t~ là ~3~. Xác suất xảy ra cách chọn (khả năng) này là ~\frac{1}{3} \cdot \frac{1}{2} = \frac{1}{6}~.
~[2, 1]~: FireGhost nhận được xâu ~t = 101~. Độ đẹp của xâu ~t~ là ~2~. Xác suất xảy ra cách chọn (khả năng) này là ~\frac{1}{3} \cdot \frac{1}{1} = \frac{1}{3}~.
~[3]~: FireGhost nhận được xâu ~t = 100~. Độ đẹp của xâu ~t~ là ~1~. Xác suất xảy ra cách chọn (khả năng) này là ~\frac{1}{3}~.
Vì vậy, giá trị kì vọng của độ đẹp xâu t là ~3 \cdot \frac{1}{6} + 3 \cdot \frac{1}{6} + 2 \cdot \frac{1}{3} + 1 \cdot \frac{1}{3} = 2~.
Comments