# https://leetcode.com/problems/number-of-sub-arrays-with-odd-sum

from typing import List

MOD = 10 ** 9 + 7
class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        odd_count = int(arr[0] % 2 == 1)
        for i in range(1, len(arr)):
            arr[i] += arr[i -1]
            odd_count += int(arr[i] % 2 == 1)

        result = odd_count
        curr = 0
        for i in range(len(arr)):
            if (arr[i] - curr) % 2 == 1:
                odd_count -= 1
                odd_count = len(arr) - i - 1 - odd_count
            result += odd_count
            curr = arr[i]
        return result % MOD