<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:
        o = [i for i,n in enumerate(arr) if n%2==1]
        if not o:
            return 0

        mod = 7+10**9

        l = len(arr)
        
        if len(o)==len(arr):
            if l%2==0:
                a = l//2
                return a*(a+1) % mod
            else:
                a = l//2
                b = a + 1
                return (a*(a+1)//2 + b*(b+1)//2)%mod
        

        o = [-1] + o + [l]
        l = len(o)-2
        front = [o[i]-o[i-1] for i in range(1,l+1)]
        back = [o[i+1]-o[i] for i in range(1,l+1)]
        del o
        s = 0
        d = {}
        d[0] = sum([v for i, v in enumerate(back) if i%2==0])
        d[1] = sum([v for i, v in enumerate(back) if i%2==1])
        for i in range(2,len(back)):
            d[i] = d[i-2]-back[i-2]
        for i in range(l):
            s += front[i]*d[i]%mod
            s = s%mod
        return s
27600