https://leetcode.com/problems/count-the-number-of-square-free-subsets

function squareFreeSubsets(nums: number[]): number {
    const mod = (Math.pow(10, 9) + 7);

    // core approach to this - modular arithemetic - see https://en.wikipedia.org/wiki/Modular_arithmetic#Integers_modulo_n
    // specifically, these simplification rules:
    //   (a + b) % n === (a % n) + (b % n)
    //   (a * b) % n === (a % n) * (b % n)
    // ie. when you're just doing addition and multiplication, you can apply the modulus operation right away
    //   you don't have to wait until the end to apply it.  This can make sure you never have to operate
    //   on any number bigger than mod*mod

    // however, in Javascript, even mod*mod is too big to fit in a fully-precise number - https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Number#number_encoding
    // to fix that, we use this method to split that into two separate multiplications
    //   the first divided by 1000, and the second with just that leftover 1000 part
    //   taking advantage of the fact that (a+b)*c === (a*c)+(b*c)
    //   which we can then use modular artithmetic rules to prevent an overflow
    function safeModMult(v1: number, v2: number) {
        if (v1 > v2) {
            return safeModMult(v2, v1);
        }
        var shift = Math.pow(10, 4);
        var part1 = (Math.floor(v1/shift) * (v2 % mod)) % mod;
        var part2 = ((v1 % shift) * (v2 % mod)) % mod;
        return ((part1 * shift) % mod + part2) % mod;
    }

    // I'm sure there's a mathematical way to calculate this, but I recognized pascal's triangle and just went with that
    const triangles = new Map<number, number[]>();
    triangles.set(0, [1]);
    function getTriangle(n: number): number[] {
        if (triangles.has(n)) {
            return triangles.get(n);
        }
        const prev = getTriangle(n-1);
        const next = [1];
        for(let i=1; i<prev.length; i++) {
            next.push((prev[i] + prev[i-1]) % mod);
        }
        next.push(1);
        triangles.set(n, next);
        return next;
    }

    // can't use any numbers that are themselves square or a multiple of a square
    const squares = Array.from(new Array(25)).map((i, ix) => ix + 2).map(i => i*i);
    const candidates = nums.filter(i => !squares.some(ii => i % ii === 0));

    // we also can't use any number twice, so we'll track duplicates
    const counts = new Map<number, number>();
    for(const i of candidates) {
        if (counts.has(i)) {
            counts.set(i, counts.get(i) + 1);
        } else {
            counts.set(i, 1);
        }
    }

    // for each unique number, there are count+1 valid configs for it (none present, exactly 1 present)
    // so we just multiply them all together (and subtract one because "none present" for all of them isn't valid)
    // const sum = Array.from(counts.values()).reduce((a,b) => a * (b+1), 1) - 1;
    // however, this doesn't work in situations where there's multiple numbers with a prime inside them
    // ie. [2,6] - we can't keep them both, as that'd result in 12, which has a 4 in it.
    // we also have to account for the fact that we can keep as many 1s as we want

    const allNumbers = Array.from(counts.keys());
    function getSubsets(soFar: number[], ix: number) {
        if (ix >= allNumbers.length) {
            return soFar.length ? 1 : 0;
        }
        const n = allNumbers[ix];
        const count = counts.get(n)!;

        let r: number;
        // 1 is special, since we can add as many or as few of them as we like
        if (n === 1) {
            const combo1s = getTriangle(count).reduce((a,b) => (a+b)%mod,-1);
            r = getSubsets(soFar, ix+1) + safeModMult(combo1s, getSubsets([...soFar, n], ix+1));
        }
        else if (soFar.some(i => squares.some(s => (i * n) % s === 0)))
        {
            // this number would conflict with an earlier one - can't add any
            r = getSubsets(soFar, ix+1);
        }
        else
        {
            // we _can_ add this, but we don't have to
            r = getSubsets(soFar, ix+1) + safeModMult(count,  getSubsets([...soFar, n], ix+1));
        }

        return r % mod;
    }

    return getSubsets([], 0);
};