Bài IMO khó hơn

Sau khi vượt qua vòng cuối của Kỳ thi Thợ săn, Gon giờ đã là một Thợ săn! Nhưng trước khi tiếp tục cuộc hành trình thú vị của mình, Gon quyết định về thăm nhà ở "Đảo While".

Dì Mito rất vui vì Gon đã trở thành Thợ săn và về thăm nhà. Nhưng đồng thời dì cũng lo lắng cho Gon: cuộc sống của một Thợ săn đầy thử thách. Vì vậy dì sẽ không cho Gon rời "Đảo While" trừ khi Gon giải được một câu đố do dì chuẩn bị.

Nhưng nên đưa cho Gon câu đố nào? Dì Mito mở "Đề thi IMO 2019" và tìm thấy bài toán sau:

Ngân hàng Bath phát hành các đồng xu có một mặt là H và mặt kia là T. Giáo sư Tuy có $n$ đồng xu như vậy xếp thành một hàng từ trái sang phải. Ông lặp đi lặp lại thao tác sau: nếu có đúng $k>0$ đồng xu đang ngửa mặt H, ông lật đồng xu thứ $k$ tính từ trái sang; ngược lại, mọi đồng xu đều ngửa mặt T và ông dừng lại. Ví dụ, với $n=3$, quá trình bắt đầu từ cấu hình THT là: THT $\to$ HHT $\to$ HTT $\to$ TTT, dừng lại sau ba thao tác.

Chứng minh rằng với mọi cấu hình ban đầu, giáo sư Tuy sẽ dừng lại sau hữu hạn thao tác.

"Bài này dễ quá", dì Mito nghĩ. "Gon sẽ giải được ngay."

Sau khi suy nghĩ thêm, dì Mito đổi bài toán trên thành phiên bản khó hơn như sau:

Với mỗi cấu hình ban đầu $C$, gọi $L(C)$ là số thao tác được thực hiện trước khi giáo sư Tuy dừng lại. Cho một dãy $S$ gồm các ký tự H, T và ?, biểu diễn một trạng thái ban đầu, trong đó ? là trạng thái chưa biết. Hãy tính giá trị trung bình của $L(C)$ trên tất cả các dãy $C$ được biểu diễn bởi $S$.

Dù Gon rất thông minh, cậu vẫn chưa giải được câu hỏi này. Hãy giúp Gon!

Dữ liệu vào

Dữ liệu vào gồm một dòng khác rỗng có không quá ${10}^6$ ký tự: dãy $S$.

Dữ liệu ra

In ra một số thực là giá trị trung bình của $L(C)$ như mô tả ở trên.

Đáp án được coi là đúng nếu sai số tương đối hoặc tuyệt đối không vượt quá ${10}^{-6}$. Cụ thể, gọi $a$ là đáp án của bạn và $b$ là đáp án của ban giám khảo, chương trình chấm chấp nhận nếu $\frac{|a-b|}{max(1,b)}\le {10}^{-6}$.

Ràng buộc

• $1\le |S|\le {10}^6$
• $S$ chỉ gồm các ký tự H, T và ?.

Ví dụ