Given an array of integers arr, return the number of subarrays with an odd sum. Since the answer can be very large, return it modulo 109 + 7.

numOfSubarrays.js

/**
 * @param {number[]} arr
 * @return {number}
 */
var numOfSubarrays = function(arr) {
    const MOD = 10**9 + 7;
    let n = arr.length;
    let count = 0;
    let prefixSum = 0;
    let oddCount = 0;
    let evenCount = 1; // Start with 1 to count the empty prefix

    for (let num of arr) {
        // Update the prefix sum
        prefixSum += num;

        // Check if the prefix sum is odd or even
        if (prefixSum % 2 === 0) {
            // If even, add the number of odd prefix sums seen so far
            count += oddCount;
            evenCount++; // Increment the even prefix count
        } else {
            // If odd, add the number of even prefix sums seen so far
            count += evenCount;
            oddCount++; // Increment the odd prefix count
        }

        // Apply the modulo operation to handle large numbers
        count %= MOD;
    }

    return count;
};