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.

&nbsp;
Example 1:

Input: arr = [1,3,5]
Output: 4
Explanation: All subarrays are [[1],[1,3],[1,3,5],[3],[3,5],[5]]
All sub-arrays sum are [1,4,9,3,8,5].
Odd sums are [1,9,3,5] so the answer is 4.


Example 2:

Input: arr = [2,4,6]
Output: 0
Explanation: All subarrays are [[2],[2,4],[2,4,6],[4],[4,6],[6]]
All sub-arrays sum are [2,6,12,4,10,6].
All sub-arrays have even sum and the answer is 0.


Example 3:

Input: arr = [1,2,3,4,5,6,7]
Output: 16


&nbsp;
Constraints:


	1 &lt;= arr.length &lt;= 105
	1 &lt;= arr[i] &lt;= 100


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        ce, co = 0, 0
        s = 0
        for x in arr:
            if x % 2 == 0:
                ce += 1
            else:
                old_co = co
                co = ce + 1
                ce = old_co
            
            s += co
            
        return s % (10**9+7)
//odd-even=odd
//even-odd=odd
class Solution {
    public int numOfSubarrays(int[] arr) {
        long ans=0;
        int even=0;
        int odd=0;
        
        long sum=0;
        
        for(int i=0;i<arr.length;i++){
            sum+=arr[i];
            
            if(sum%2==0){
                ans+=odd;
                even++;
            }else{
                ans+=even+1;
                odd++;
            }
        }
        
        return (int)(ans%(1000000007));
    }
}
class Solution {
public:
    int mod = 1e9 + 7;
    int solve(int ind, int n, vector<int> &arr, int req, vector<vector<int>> &dp) {
        
        if(ind == n) return 0;
        if(dp[ind][req] != -1) return dp[ind][req];
        if(req == 1) {
            if(arr[ind] % 2 == 0) {
                return dp[ind][req] = solve(ind + 1, n, arr, req, dp);
            }
            else {
                return dp[ind][req] = (1 + solve(ind + 1, n, arr, !req, dp)) %mod;
            }
        }
        else {
            if(arr[ind] % 2 == 0) {
                return dp[ind][req] = (1 + solve(ind + 1, n, arr, req, dp)) %mod;
            }
            else {
                return  dp[ind][req] = solve(ind + 1, n, arr, !req, dp);
            }
        }
    }
    int numOfSubarrays(vector<int>& arr) {
        int n = arr.size();
        vector<vector<int>> dp(n, vector<int> (2, -1));
        int count = 0;
        for(int i = 0; i < n; i++) {
            count = (count +  solve(i, n, arr, 1, dp))% mod;
        }
        return count;
    }
};
var numOfSubarrays = function(arr) {
    let mod=1e9+7,sum=0,odds=0,evens=0
	//Notice that I do not need to keep track of the prefixSums, I just need the total count of odd and even PrefixSums
    for(let i=0;i<arr.length;i++){
        sum+=arr[i]
        odds+=Number(sum%2==1)
        evens+=Number(sum%2==0)
    }
    return (odds*evens+odds)%mod
};
Number of Sub-arrays With Odd Sum