Code : Chef Loves Beautiful Strings (Hard Version)

#include <atcoder/modint>
#include <bits/stdc++.h>

using namespace std;
using namespace atcoder;

using mint = modint1000000007;

void solve(string &str) {
    int n = str.length();

    // f[i] = sum of f of all substrings ending at i.
    // lsum[i] = sum of length of all substrings ending at i.
    // gsum[i] = sum of groups of all substrings ending at i.
    vector<mint> fsum(n), lsum(n), gsum(n);

    fsum[0] = 0;
    lsum[0] = 1;
    gsum[0] = 1;

    mint ans = 0;
    for (int i = 1; i < n; i++) {
        if (str[i] != str[i - 1]) {
            fsum[i] = fsum[i - 1] + lsum[i - 1] - i;
            gsum[i] = 1 + gsum[i - 1] + i;
        } else {
            fsum[i] = fsum[i - 1] + gsum[i - 1] - i;
            gsum[i] = 1 + gsum[i - 1];
        }

        lsum[i] = 1 + lsum[i - 1] + i;
        ans += fsum[i];
    }

    cout << ans.val() << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        int n;
        cin >> n;
        string str;
        cin >> str;
        solve(str);
    }
    return 0;
}