class Solution {
public:
    int uniqueLetterString(string S) {
        int len = S.size();
        long long curr = 0, res = 0;
        if(!len)return 0;
        const int MOD = 1000000007;
        unordered_map<char, vector<int>> idxes;
        vector<int> peek(len, 0);
        for(int i = 0; i < len; ++i)idxes[S[i]].push_back(i);
        for(auto& p : idxes)
        {
            p.second.push_back(len);
            curr += calculate(idxes, peek, p.first);
        }
        for(const auto& c : S)
        {
            res += curr;
            long long old = calculate(idxes, peek, c);
            ++peek[c - 'A'];
            curr += calculate(idxes, peek, c) - old;
        }
        return res % MOD;
    }
    
private:
    long long calculate(unordered_map<char, vector<int>>& idxes, vector<int>& peek, char c)
    {
        auto idx = idxes[c];
        int i = peek[c - 'A'];
        return i == idx.size() - 1? 0 : idx[i + 1] - idx[i];
    }
};