<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:
    def numOfSubarrays(self, arr: List[int]) -> int:
        #
        #   1 3 5 7
        # 1 1
        # 3 4 3
        # 5 9 8
        # 7
        #      s
        #        e
        # sum[0,0]=arr[0]
        # sum[0,1]=sum[0,0]+arr[1]
        # sum[0,2]=sum[0,1]+arr[2]
        # sum[1,1]=arr[1]=sum[0,1]-sum[0,0]
        # sum[1,2]=sum[0,2]-sum[0,1]
        # sums = []
        reduced = [n % 2 for n in arr]  # 1,1,1
        n = len(reduced)

        # From left
        ending0 = 1 - reduced[0]  # 0 1 1
        ending1 = reduced[0]  # 1 1 2
        count = ending1

        for i in range(n - 1):
            if reduced[i + 1] == 0:
                ending0, ending1 = 1 + ending0, ending1 
            else:
                ending0, ending1 = ending1, 1 + ending0 # 
            count += ending1
        

        return count % (10**9 + 7)

19900