/**
 * @param {string[]} words
 * @return {number[][]}
 */
var palindromePairs = function(words) {
    let mod = BigInt(1);
    
    for (let i = 0; i < 64; i++) {
        mod *= BigInt(2);
    }
    mod = BigInt(1000000009);
    mod *= BigInt(1000000007);
    
    const b = BigInt(37);
    let powers = new Array(301);
    powers[0] = BigInt(1);
    for (let i = 1; i < powers.length; i++) {
        powers[i] = powers[i - 1] * b % mod;
    }  
    
    var hash = (str) => {
        let res = BigInt(0);
        for (let i = 0; i < str.length; i++) {
            res = res * b  + BigInt(str.charCodeAt(i) - 96);
            res %= mod;
        }
        return res;
    };
    
    let hf = new Array(words.length);
    let hb = new Array(words.length);
    
    for (let i = 0; i < words.length; i ++) {
        hf[i] = hash(words[i]);
        hb[i] = hash(words[i].split('').reverse().join(''));
    }
    
    let sum = (h1, h2, l) => {
        return (h2 + powers[l] * h1); // % mod;
    };

    let res = [];
    for (let i = 0; i < hf.length; i++) {
        for (let j = 0; j < hb.length; j++) {
            if (i != j) {
                let sumOfForwardHash = sum(hf[i], hf[j], words[j].length);
                let sumOfBackwardHash = sum(hb[j], hb[i], words[i].length);
                
                if (sumOfForwardHash === sumOfBackwardHash) {
                    res.push([i,j]);
                }
            }
        }
    }
    return res;
    
};