Cửa hàng trà sữa

Sau những ngày chinh chiến cùng các kỳ thi lập trình thi đấu, Tài đã về nhà mở một cửa hàng trà sữa của riêng mình. Cửa hàng có $3$ loại trà đặc biệt là: trà sữa hạnh nhân, trà sữa sen vàng và trà sữa gừng. Các loại trà sữa này được pha chế theo cách rất đặc biệt làm người thưởng thức có trải nghiệm khó quên. Nhân dịp khai trương, cửa hàng xếp các ký tự H, S và G đại diện cho các loại trà sữa trên thành một dãy có độ dài $N$ và mỗi khách đến mua có thể tham gia một chương trình khuyến mãi như sau: khách chọn ra dãy các ký tự liên tiếp tương ứng với các loại trà mà mình muốn mua; Tài sẽ đếm số lượng các ký tự H, S, G có trong dãy đã chọn và nhân các giá trị này lại với nhau; nếu kết quả thu được là một lũy thừa của $2$ thì khách hàng sẽ nhận được phiếu giảm giá.

Yêu cầu: Hãy viết chương trình cho biết với một khách hàng, số cách để nhận được chương trình khuyến mãi của chủ cửa hàng. Cụ thể là đếm số cặp chỉ số $(L,R)$ với $1\le L\le R\le N$ sao cho nếu gọi $a,b,c$ lần lượt là số lượng ký tự H, S, G có trong đoạn dãy con liên tiếp từ $L$ đến $R$ thì tích $a\times b\times c$ là một lũy thừa của $2$.

Lũy thừa của $2$ là các số $2^k$ với $k\ge 0$ nguyên, tức là $1,2,4,8,\dots$ (số $1=2^0$ cũng được tính). Nếu đoạn không chứa đủ cả ba loại ký tự thì tích bằng $0$, không phải lũy thừa của $2$.

Dữ liệu vào

Một dòng duy nhất chứa $N$ ký tự thuộc $\{H,S,G\}$ viết liên tiếp nhau không dấu cách, trong đó $1\le N\le {10}^5$.

Dữ liệu ra

In ra một số nguyên là số cách để nhận được khuyến mãi, cũng chính là số chuỗi con thỏa mãn yêu cầu đã nêu.

Ràng buộc

• $1\le N\le {10}^5$.
• Mỗi ký tự của dãy là H, S hoặc G.

Subtasks

• Subtask 1 ($20\%$ số điểm): $N\le {10}^2$.
• Subtask 2 ($40\%$ số điểm): ${10}^2<N\le {10}^3$.
• Subtask 3 ($40\%$ số điểm): ${10}^3<N\le {10}^5$.

Ví dụ