const size_t MODULO = 1'000'000'007;
auto factorials = std::vector<size_t>();
auto modularMultiplicativeInverses = std::vector<size_t>();
auto counts = std::vector<std::unordered_map<char, size_t>>();

size_t findMdularMultiplicativeInverse(
    size_t const & _inverseOfThisNum,
    size_t const _power
){
    if(_power == 0){
        return 1;
    }
    auto  temp = 
        findMdularMultiplicativeInverse(_inverseOfThisNum, _power / 2) %
             MODULO;
    temp = (temp * temp) % MODULO;
    return  ((_power % 2) == 0 ? temp : _inverseOfThisNum * temp) %
        MODULO;
}

void initialize(
    std::string const & _str
){
    factorials.resize(_str.size() / 2 + 1, 1);
    modularMultiplicativeInverses = factorials;
    counts.resize(_str.size() + 1);
    for(size_t indx = 2; indx != factorials.size(); ++indx){
        factorials.at(indx) = (indx * factorials.at(indx - 1)) % MODULO;
        modularMultiplicativeInverses.at(indx) = 
            findMdularMultiplicativeInverse(factorials.at(indx),
                MODULO - 2);
    }
    for(size_t indx = 0; indx < _str.size(); ++indx){
        counts.at(indx + 1) = counts.at(indx);
        ++counts.at(indx + 1)[_str.at(indx)];
    }
}

int answerQuery(
    int const & _begin,
    int const & _end
){
    size_t maxLenthHalf = 0;
    size_t middleChar = 0;
    size_t denominator = 1;
    size_t countCurrent = 0;
    for(auto const & [chr, count]: counts.at(_end)){
        countCurrent = count - counts.at(_begin - 1)[chr];
        if(countCurrent >= 2){
            denominator = (denominator * 
                modularMultiplicativeInverses.at(countCurrent / 2)) %
                    MODULO;
            maxLenthHalf += countCurrent / 2;
        }
        if(countCurrent % 2 == 1){
            ++middleChar;
        }
    }
    return (((factorials.at(maxLenthHalf) * denominator) % MODULO) *
        (middleChar == 0 ? 1 : middleChar)) % MODULO;
}