AT_abc418_d [ABC418D] XNOR Operation

> This problem is a subproblem of Problem G. A non-empty string $ S $ consisting of `0` and `1` is called a beautiful string when it satisfies the following condition: - (Condition) You can perform the following sequence of operations until the length of $ S $ becomes $ 1 $ and make the only character remaining in $ S $ be `1`. 1. Choose any integer $ i $ satisfying $ 1 \leq i \leq |S| - 1 $ . 2. Define an integer $ x $ as follows: - If $ S_i = $ `0` and $ S_{i+1} = $ `0`, let $ x = 1 $ . - If $ S_i = $ `0` and $ S_{i+1} = $ `1`, let $ x = 0 $ . - If $ S_i = $ `1` and $ S_{i+1} = $ `0`, let $ x = 0 $ . - If $ S_i = $ `1` and $ S_{i+1} = $ `1`, let $ x = 1 $ . 3. Remove $ S_i $ and $ S_{i+1} $ , and insert the digit corresponding to $ x $ in their place. For example, if $ S= $ `10101` and you choose $ i=2 $ , the string after the operation is `1001`. You are given a string $ T $ of length $ N $ consisting of `0` and `1`. Find the number of beautiful strings that are substrings of $ T $ . Even if two substrings are identical as strings, count them separately if they are taken from different positions. What are substrings?A **substring** of $ S $ is a string obtained by deleting zero or more characters from the beginning and zero or more characters from the end of $ S $ . For example, `10` is a substring of `101`, but `11` is not a substring of `101`.

The input is given from Standard Input in the following format: > $ N $ $ T $

Print the number of beautiful strings that are substrings of $ T $ .

### Sample Explanation 1 The string `11` obtained by taking the 1st through 2nd characters of $ T $ is a beautiful string, because if you choose $ i=1 $ and perform the operation, the string becomes `1`. The beautiful strings that are substrings of $ T $ are the following three strings: - The string `1` obtained by taking the 1st character of $ T $ . - The string `1` obtained by taking the 2nd character of $ T $ . - The string `11` obtained by taking the 1st through 2nd characters of $ T $ . ### Constraints - $ 1 \leq N \leq 2 \times 10^5 $ - $ N $ is an integer. - $ T $ is a string of length $ N $ consisting of `0` and `1`.