<p>Given an array of integers <code>arr</code>, return <em>the number of subarrays with an <strong>odd</strong> sum</em>.</p>

<p>Since the answer can be very large, return it modulo <code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> arr = [1,3,5]
<strong>Output:</strong> 4
<strong>Explanation:</strong> 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.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> arr = [2,4,6]
<strong>Output:</strong> 0
<strong>Explanation:</strong> 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.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> arr = [1,2,3,4,5,6,7]
<strong>Output:</strong> 16
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= arr.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= arr[i] &lt;= 100</code></li>
</ul>

class Solution {
public:
    int mod = 1e9+7;

    int numOfSubarrays(vector<int>& arr) {
        int n = arr.size();
        int ans = 0;
        // for(int i=0;i<n;i++){
        //     long long sum = 0;
        //     for(int j=i;j<n;j++){
        //         sum += arr[j];
        //         if(sum%2!=0){
        //             ans = (ans+1)%mod;
        //         }
        //     }
        // }
        // return ans;

        //dp1[i] denotes the count of subarrays ending at i with sum=1
        // dp0[i] denotes the subarrays ending at i with sum=0
        vector<int> dp0(n,0) , dp1(n,0);
        if(arr[0]%2==1){
            dp1[0] = 1;
        }
        else{
            dp0[0] = 1;
        }

        for(int i=1;i<n;i++){
            if(arr[i]%2==1){
                dp1[i] = (1+dp0[i-1])%mod;
                dp0[i] = dp1[i-1];
            }
            else{
                dp0[i] = (1+dp0[i-1])%mod;
                dp1[i] = dp1[i-1];
            }
        }

        for(int i=0;i<n;i++){
            ans = (ans+dp1[i])%mod;
        }
        return ans;
    }
};
120900