const cache = new Map(); const factorial = (n) => { let sum = 1n; if (cache.has(n)) return cache.get(n); let tmpN = n; while (n > 0n) { sum *= n; n--; } cache.set(tmpN, sum); return sum; } const getCombination = (n, r) => { n = BigInt(n), r = BigInt(r); return factorial(n) / (factorial(r) * factorial(n - r)); } /** * @param {number[]} nums * @return {number} */ const numOfWays = (nums) => { const findPossibleWays = (numsList) => { if (numsList.length <= 2) return 1n; let root = numsList.shift(), leftList = [], rightList = [], leftCount = 0, rightCount = 0, total = 0; while (numsList.length > 0) { total++; let curr = numsList.shift(); if (curr < root) { leftList.push(curr); } else { rightList.push(curr); } } leftCount = leftList.length, rightCount = rightList.length; return findPossibleWays(leftList) * findPossibleWays(rightList) * getCombination(total, leftCount); } return (findPossibleWays(nums) - 1n) % BigInt(Math.pow(10, 9) + 7); };