FireGhost130104 đượ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~.