Given an array of integers arr. Return the number of sub-arrays with odd sum.
As the answer may grow large, the answer must be computed modulo 10^9 + 7.
 
Example 1:
Input: arr = [1,3,5]
Output: 4
Explanation: All sub-arrays 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 sub-arrays 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

Example 4:
Input: arr = [100,100,99,99]
Output: 4

Example 5:
Input: arr = [7]
Output: 1

 
Constraints:

1 <= arr.length <= 10^5
1 <= arr[i] <= 100

Difficulty: interview

Starter code:

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        

Solutions:
class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        mod = 10**9+7
        odd_presum_cnt = 0
        par = 0
        for a in arr:
            par ^= a & 1
            if par:
                odd_presum_cnt += 1
        return odd_presum_cnt * (len(arr)+1 - odd_presum_cnt)%mod

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        res = odd = even = 0
        for x in arr:
            even += 1
            if x % 2 != 0:
                even,odd = odd,even
            res = (res + odd) % (10 ** 9 + 7)
        return res

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        np = [[0 for i in range(len(arr))] for j in range(2)]
        
        # 0 is even sub array
        # 1 is odd sub array
        np[0][0] = 1 if arr[0] % 2 == 0 else 0
        np[1][0] = 1 if arr[0] % 2 == 1 else 0
        res = np[1][0]
        for i in range(1, len(arr)):
            if arr[i] % 2 == 0:
                np[0][i] = (1 + np[0][i - 1]) % 1000000007
                np[1][i] = np[1][i - 1] % 1000000007
            else:
                np[0][i] = np[1][i - 1] % 1000000007
                np[1][i] = (1 + np[0][i - 1]) % 1000000007
            #print(np)
            res += np[1][i]
        return res % 1000000007

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        s=0
        odd={}
        ok=[]
        even={}
        ek=[]
        for i in range(len(arr)):
            s+=arr[i]
            if(s%2==0):
                even[i]=s
                ek.append(i)
            else:
                odd[i]=s
                ok.append(i)
        j=0
        c=0
        for i in ok:
            while(j<len(ek) and ek[j]<i):
                j+=1
            c+=j
        j=0
        for i in ek:
            while(j<len(ok) and ok[j]<i):
                j+=1
            c+=j
        
        #0:1,1:3,4:15,5:21
        #2:6, 3:10, 6:28
        return (c+len(ok))%(10**9 + 7)


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        mod = 10**9 + 7
        odd_even_count = [[0,0] for _ in range(len(arr)+1)]
        prefix_odd_sum = [-1 for _ in range(len(arr))]
        cur = 0
        odd_count = 0
        even_count = 0
        for idx in range(len(arr)):
            cur += arr[idx]
            prefix_odd_sum[idx] = cur % 2
            if cur % 2 == 1:
                odd_count += 1
            else:
                even_count += 1
            odd_even_count[idx+1] = (odd_count, even_count)
        
        ans = 0
        for idx in range(len(arr)):
            is_odd = prefix_odd_sum[idx]
            ## odd: add 1 + prefix even count
            if is_odd:
                ans += 1 + odd_even_count[idx][1] 
            ## even: add prefix odd count
            else:
                ans += odd_even_count[idx][0]
        return ans % mod
                


class Solution:
    def numOfSubarrays(self, A: List[int]) -> int:
        n = len(A)
        mod = 10**9+7
        ans = 0
        p, ctr = [0]*(n+1), Counter([0]) 
        for i in range(n):
            p[i] = p[i-1]+A[i]
            s = p[i]%2
            ans = ans+ctr[1-s]
            ans = ans%mod 
            ctr[s] += 1
        return ans

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        dp = [0 for i in range(len(arr))] # dp[i] is the number of subarrays that end at i with (odd sum, even sum)
        dp[0] = (1,0) if arr[0] % 2 == 1 else (0,1)
        for i in range(1,len(dp)):
            if arr[i] % 2 == 0: 
                oddCount = dp[i-1][0]
                evenCount = dp[i-1][1] + 1
            else:
                oddCount = dp[i-1][1] + 1
                evenCount = dp[i-1][0]
            dp[i] = (oddCount,evenCount)
        # print(dp)
        return sum([elem[0] for elem in dp]) % (10**9 + 7)

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        MOD = 10**9 + 7
        res = 0
        
        curr_sum = 0
        even_count = 1
        odd_count = 0
        
        for num in arr:
            curr_sum += num
            curr_sum %=2
            
            if curr_sum == 1: # odd
                res += even_count
                odd_count += 1
            else:
                res += odd_count
                even_count += 1
        
        return res % MOD
            
            
            


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        dp = [[0, 0] for _ in range(len(arr)+1)]
        for i, num in enumerate(arr):
            if num % 2 == 0:
                dp[i+1][0] = dp[i][0]
                dp[i+1][1] = dp[i][1] + 1
            else:
                dp[i+1][0] = dp[i][1] + 1
                dp[i+1][1] = dp[i][0]
        
        return sum(dp[i][0] for i in range(len(dp))) % (10**9+7)


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        mod = 10**9 + 7
        dic = collections.Counter()
        dic[0] += 1
        pre = ans = 0
        for i,x in enumerate(arr):
            pre += x
            pre %= 2
            ans = (ans + dic[pre^1]) % mod
            dic[pre] += 1
        return ans

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        if len(arr)<1:
            return None
        if len(arr)==1:
            if arr[0]%2!=0:
                return 1
        mod=10**9 + 7
        flag=False
        for i in arr:
            if i%2!=0:
                flag=True
                break
        if flag==False:
            return 0
        even,odd=0,0
        ret=0
        for i in arr:
            if i%2!=0:
                ret+=even+1
                odd,even=even+1,odd
            else:
                ret+=odd
                odd,even=odd,even+1
        return ret%mod
                
        
                
        


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        N = len(arr)
        dp = [0] * N
        dp[0] = arr[0] & 1
        for i in range(1, N):
            
            if arr[i] & 1:
                dp[i] = i - dp[i - 1] + 1
            else:
                dp[i] = dp[i - 1]
        
        return sum(dp) % (10**9 + 7) 

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        ans = 0
        even = 0
        odd = 0
        for v in arr:
            if v % 2 == 0:
                even, odd = (even + 1)  % 10000000007, odd
            else:
                even, odd = odd, (even + 1)  % 10000000007
            ans = (ans + odd) % 10000000007
        return ans  % 1000000007

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        kMod = int(1e9 + 7)
        n = len(arr)
        
        # dp[i][0] is how many sub-arrays ends with arr[i] have even sum
        # dp[i][1] is how many sub-arrays ends with arr[i] have odd sum
        dp = [[0]*2 for _ in range(n)]
        
        ans = 0
        if arr[0]%2 == 0:
            dp[0][0] = 1
        else:
            dp[0][1] = 1
        ans += dp[0][1]
            
        
        for i in range(1, n):
            if (arr[i] % 2 != 0):
                dp[i][0] = dp[i-1][1]
                dp[i][1] = dp[i-1][0]+ 1
            else:
                dp[i][0] = dp[i-1][0]+1
                dp[i][1] = dp[i-1][1]
            ans += dp[i][1]
            
        return ans % kMod


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        
        dp=[]
        for i in range(len(arr)+1):
            dp.append([0,0])
        
        ans=0
        for i in range(1,len(arr)+1):
            if arr[i-1]%2==0:
                dp[i][0]=dp[i-1][0]+1
                dp[i][1]=dp[i-1][1]
            else:
                dp[i][0]=dp[i-1][1]
                dp[i][1]=dp[i-1][0]+1
            
            ans+=dp[i][1]
        
        
        return ans%(pow(10,9)+7)


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        n = len(arr)
        mod = 10**9+7
        ans = 0
        p = [0]*(n+1)
        counter = Counter([0]) 
        for i in range(n):
            p[i] = p[i-1]+arr[i]
            if p[i]%2: ans += counter[0]
            else: ans += counter[1]
            counter[p[i]%2] += 1
        return ans%mod

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        sum_even = 0
        sum_odd = 0
        out = 0
        for i in range(len(arr)):
            if arr[i] %2 ==0:
                sum_even, sum_odd = sum_even+1, sum_odd
            else:
                sum_even, sum_odd = sum_odd , sum_even +1
            out += sum_odd
        return out % (10**9 + 7)


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        sums = [0]
        
        sum = 0
        for n in arr:
            sum += n
            sums.append(sum)
            
        odd_sum_count = []
        even_sum_count = []
        odd_sum = 0
        even_sum = 0
        for ss in sums:
            odd_sum += 1 if ss % 2 == 1 else 0
            even_sum += 0 if ss % 2 == 1 else 1
            odd_sum_count.append(odd_sum)
            even_sum_count.append(even_sum)
        ans = 0
        for i in range(len(arr)):
            if sums[i+1] % 2 == 0:
                ans += odd_sum_count[i]
            else:
                ans += even_sum_count[i]
            ans = ans % (10 ** 9 + 7)
        return ans

class Solution:
     def numOfSubarrays(self,A) -> int:
        n = len(A)
        MOD = pow(10,9)+7
        dp_even,dp_odd = [0],[0]
        if A[0]%2:
            dp_odd[0] += 1
        else:
            dp_even[0] += 1

        ans = dp_odd[-1]
        
        for i in range(1,n):
            if A[i]%2:
                dp_odd.append( (dp_even[i-1]+1)%MOD )
                dp_even.append( dp_odd[i-1] )
            else:
                dp_odd.append( dp_odd[i-1] )
                dp_even.append( (dp_even[i-1]+1)%MOD )
            ans += dp_odd[i]
            ans %= MOD
        
        #print(dp_even,dp_odd)
        
        return ans

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        memoOdd = arr[0] % 2
        memoEven = -(arr[0] % 2 - 1)
        memoOddSum = memoOdd
        
        for i in range(1, len(arr)):
            memoOdd_temp = memoOdd
            memoEven_temp = memoEven
            memoOdd = memoOdd_temp * (-(arr[i] % 2 - 1)) + memoEven_temp * (arr[i] % 2) + arr[i] % 2
            memoEven = memoOdd_temp * (arr[i] % 2) + memoEven_temp * (-(arr[i] % 2 - 1)) -(arr[i] % 2 - 1)
            memoOddSum += memoOdd
        
        return memoOddSum % 1000000007

class Solution:
    # Make prefix sum, store only whether sum is odd or even
    # Iterate through prefix sum, check if current prefix sum is odd/even and count number of odd/even subarrays behind it
    def numOfSubarrays(self, arr: List[int]) -> int:
        countOdd, countEven, result = 0, 1, 0
        modulo = 1000000007
        prev = 0
        for i in arr:
            prev = (prev + i) % 2
            if prev == 0:
                countEven += 1
                result += countOdd
                if result >= modulo:
                    result %= modulo
            else:
                countOdd += 1
                result += countEven
                if result >= modulo:
                    result %= modulo
        return result

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        ans=0
        evenCount=0
        oddCount=0
        for i in arr:
            if(i%2==0):
                ans+=oddCount
                oddCount, evenCount = oddCount, evenCount+1
            else:
                ans+=evenCount+1
                oddCount, evenCount = evenCount+1, oddCount
        return int(ans%(math.pow(10,9)+7))

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        n = len(arr)
        MOD = int(1e9 + 7)
        even, odd = [0]*(n+1), [0]*(n+1)    
        for i, a in enumerate(arr):
            if a % 2 == 1:
                even[i] = odd[i-1] % MOD
                odd[i] = (even[i-1] + 1) % MOD
            else:
                even[i] = (even[i-1] + 1) % MOD
                odd[i] = odd[i-1] % MOD
        
        return sum(odd) % MOD
                


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        acc=[]
        temp=0
        ones=0
        for u in arr:
            temp+=u%2
            if temp%2==1:
                ones+=1
        L=len(arr)
        return ones*(L-ones+1)%(10**9+7)


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        kMod = int(1e9 + 7)
        n = len(arr)
        
        # dp[i][0] is how many sub-arrays ends with arr[i-1] have even sum
        # dp[i][1] is how many sub-arrays ends with arr[i-1] have odd sum
        dp = [[0]*2 for _ in range(n+1)]
        
        ans = 0          
        
        for i in range(1, n+1):
            if (arr[i-1] % 2 != 0):
                dp[i][0] = dp[i-1][1]
                dp[i][1] = dp[i-1][0]+ 1
            else:
                dp[i][0] = dp[i-1][0]+1
                dp[i][1] = dp[i-1][1]
            ans += dp[i][1]
            
        return ans % kMod


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        evenCount, oddCount = 1, 0
        totalSum = numArrays = 0
        
        for val in arr:
            totalSum += val
            numArrays += evenCount if totalSum%2 else oddCount
            evenCount += totalSum%2 == 0
            oddCount += totalSum%2 == 1
            
        return numArrays % ((10**9)+7)   

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        mod = 10 ** 9 + 7
        n = len(arr)
        dp = [[0] * 2 for _ in range(n)]
        if arr[n - 1] & 1:
            dp[n - 1][1] = 1
        else:
            dp[n - 1][0] = 1
            
        for i in range(n - 2, -1, -1):
            if arr[i] & 1:
                dp[i][1] = (dp[i + 1][0] + 1) % mod
                dp[i][0] = dp[i + 1][1]
            else:
                dp[i][1] = dp[i + 1][1]
                dp[i][0] = (dp[i + 1][0] + 1) % mod
                
        ans = 0
        for i in range(n):
            ans += dp[i][1]
            
        return ans % mod

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        odd, even = 0, 1
        s = res = 0
        for n in arr:
            s += n

            if s % 2 == 0:
                res += odd
                even += 1
            else:
                res += even
                odd += 1

            res %= 1000000007

        return res

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        o = []
        score = 0
        tmp = 0
        pa,no = 0,0
        check = []
        
        for el in arr:
            tmp += el
            
            if tmp % 2 ==0:
                pa += 1
                check.append(0)
            else:
                no += 1
                check.append(1)
                
            o.append((pa, no))
            
        score = 0

        for i in range(len(arr)):
           # print(arr[i], score, 'b')
            if arr[i] % 2 ==1:
                score += 1
                
            if check[i-1] == 0 or i==0:
                score += o[-1][1] - o[i][1]
            else:
                score += o[-1][0] - o[i][0]
          
           # print(o)
           # print(arr[i], score, 'a')

        mod = 10**9 + 7
        return score % mod
            
            
            
       


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        
        odd = 0
        even = 1
        res = 0
        sum = 0
        
        for i in arr:
            sum += i
            if sum%2 == 0:
                even += 1
                res = (res+odd)%1_000_000_007
            else:
                odd += 1
                res = (res+even)%1_000_000_007
                
        return res

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        #dp[i]:the number of odd subarrays ended with arr[i]
        n = len(arr)
        dp = [0]*n

        dp[0] = arr[0]%2

        for i in range(1, n):
            if arr[i]%2 == 0:
                dp[i] = dp[i-1]
            else:
                dp[i] = i-dp[i-1]+arr[i]%2

        return sum(dp)% (1000000000 + 7)


class Solution:
    def numOddEvenSubarrays(self, arr:List[int], start:int) -> (int, int, int):
        if len(arr) == 0:
            return (0, 0, 0)
        if len(arr) == 1 or start == len(arr)-1:
            return (0, 1, 0) if arr[start] % 2 == 0 else (1, 0, 0)
        (odd, even, oldOdd) = self.numOddEvenSubarrays(arr, start+1)
        #print(f'{arr[start:], odd, even, oldOdd}')
        indOdd = (odd + oldOdd) % (10 ** 9 + 7)
        return (odd, even + 1, indOdd) if arr[start] % 2 == 0 else (even + 1, odd, indOdd)
            
    def numOfSubarrays(self, arr: List[int]) -> int:
        (odd, even, oldOdd) = self.numOddEvenSubarrays(arr, 0)
        #print(f'{arr, odd, even, oldOdd}')        
        total = (odd + oldOdd) % (10 ** 9 + 7)
        return total


class Solution:
    def numOfSubarrays(self, coll: List[int]) -> int:
        n = len(coll)
        m = 10**9 + 7
        acc = 0
        evens = odds = 0

        for i, x in enumerate(coll):
            if x & 1:
                evens, odds = odds, evens + 1
            else:
                evens += 1
            
            acc += odds
            acc %= m

        return acc

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        res = odd = even = 0
        for x in arr:
            even += 1
            if x % 2 != 0:
                odd,even = even,odd
            res = (res + odd) % (10 ** 9 + 7)
        return res

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        prefix_sum = 0
        
        number_odd = 0
        number_even = 0
        
        total = 0
        
        for i in arr:
            prefix_sum += i
            
            if prefix_sum % 2 == 1:
                number_odd += 1
                total += 1
                total += number_even
            else:
                total += number_odd
                number_even += 1

        return int(total % (1e9 + 7))


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        n = len(arr)
        d = {}
        d[0] = 1
        
        sm = 0
        even = 0
        for i in range(n):
            sm += arr[i] 
            sm %= 2
            if sm < 0:
                sm += 2
            if sm in d:
                even += d[sm]
            if sm not in d:
                d[sm] = 0
            d[sm]+=1
            
        return (n*(n+1)//2-even) % (10**9+7)

class Solution:
  def numOfSubarrays(self, arr: List[int]) -> int:
    res, s, prev_odd, prev_even = 0, 0, 0, 1
    for v in arr:
      s = (s + v) % 2
      if s == 1:
        res += prev_even
        prev_odd += 1
      else:
        res += prev_odd
        prev_even += 1
      
    return res % (10**9 + 7)

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        if len(arr) == 0: 
            return 0
        result = 0
        num_odd = 0
        Cum = [0]
        for i in range(len(arr)):
            Cum.append(Cum[-1] + arr[i])
            if Cum[-1] % 2 != 0:
                num_odd += 1
        #print(num_odd)
        return (len(arr) + 1 - num_odd) * num_odd % (10**9+7)


class Solution:
    def numOfSubarrays(self, coll: List[int]) -> int:
        n = len(coll)
        m = 10**9 + 7
        dp = [(0, 0) for _ in range(n+1)]

        for i, x in enumerate(coll):
            if x & 1:
                dp[i + 1] = (dp[i][1], dp[i][0] + 1)
            else:
                dp[i + 1] = (dp[i][0] + 1, dp[i][1])

        return sum(odds for evens, odds in dp) % m

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        s = 0
        evens, odds = 0, 0
        cnt = 0
        
        for num in arr:
            s += num
            if s % 2 == 1:
                cnt += (evens+1)
                odds += 1
            else:
                cnt += odds
                evens += 1
            cnt = cnt % (10**9+7)
        return cnt

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        res = 0
        odds = 0
        even = 0
        for i, c in enumerate(arr):
            if c & 1:
                odds, even = even + 1, odds
            else:
                even += 1
            res = (res + odds) % 1000000007
        return res % 1000000007


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        
        if not arr:
            return 0
        
        n_even = 0
        n_odd = 0
        res = 0
        
        for x in arr:
            
            if x % 2 == 0:
                n_even, n_odd = n_even + 1, n_odd
            else:
                n_even, n_odd = n_odd, n_even + 1
                
            res += n_odd
            
        return res % (10**9+7)

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        even = [0] * len(arr)
        odd = [0] * len(arr)
        for i in range(len(arr)):
            if i == 0 and arr[i] % 2 == 0:
                even[i] = 1
            elif i == 0:
                odd[i] = 1
            elif arr[i] % 2 == 0:
                even[i] = even[i - 1] + 1
                odd[i] = odd[i - 1]
            else:
                even[i] = odd[i - 1]
                odd[i] = even[i - 1] + 1
        mod = 10 ** 9 + 7
        ans = 0
        for i in range(len(arr)):
            ans = (ans + odd[i]) % mod
        return ans

class Solution:
    def numOfSubarrays(self, A):
        count = [1, 0]
        curr = res = 0
        for a in A:
            curr ^= a & 1
            res += count[1 - curr]
            count[curr] += 1
        return res % (10 ** 9 + 7)

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        res = odd = even = 0
        for x in arr:
            even += 1
            if x % 2:
                odd, even = even, odd
            res = (res + odd) % 1000000007
        return res  

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        arr = list(accumulate(arr))
        count = 0
        prev_even, prev_odd = 0, 0
        for i in range(len(arr)):
            if arr[i] % 2:
                count += 1
                count += prev_even
                prev_odd += 1
            else:
                count += prev_odd
                prev_even += 1
        
        return count % (10**9 + 7)

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        dp = [0,0]
        ans = 0
        for i, num in enumerate(arr):
            dp[0], dp[1] = dp[num%2] + num%2, dp[(num-1)%2] + (num-1)%2
            ans += dp[0]
        return ans % (10**9+7)

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        ans=odd=even=0
        for i in arr:
            if i%2==0:
                even,odd=even+1,odd
            else:
                even,odd=odd,even+1
            ans=(ans+odd)%1000000007
        return ans
        '''
        ans=0
        for i in range (len(arr)):
            temp=0
            for j in range(i,len(arr)):
                temp+=arr[j]
                if temp%2==1:
                    ans+=1
        return ans%1000000007
        '''

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        sum_even = 0
        sum_odd = 0
        out = 0
        for i in range(len(arr)):
            if arr[i] %2 ==0:
                sum_even, sum_odd = sum_even+1, sum_odd
            else:
                sum_even, sum_odd = sum_odd , sum_even +1
            out = (out + sum_odd)
        return out  % 1000000007

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        memoOdd = [arr[0] % 2]
        memoEven = [-(arr[0] % 2 - 1)]
        
        for i in range(1, len(arr)):
            memoOdd.append(memoOdd[i - 1] * (-(arr[i] % 2 - 1)) + memoEven[i - 1] * (arr[i] % 2) + arr[i] % 2)
            memoEven.append(memoOdd[i - 1] * (arr[i] % 2) + memoEven[i - 1] * (-(arr[i] % 2 - 1)) -(arr[i] % 2 - 1))
        
        return sum(memoOdd) % 1000000007

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        n = len(arr)
        mod = 10**9+7
        dp = [[0 for i in range(2)]for j in range(n)]
        
        if arr[0]%2==0:
            dp[0][0] = 1
        else:
            dp[0][1] = 1
        
        for i in range(1,n):
            if arr[i]%2==0:
                dp[i][0] = dp[i-1][0]+1
                dp[i][1] = dp[i-1][1]
            else:
                dp[i][1] = dp[i-1][0]+1
                dp[i][0] = dp[i-1][1]
        ans = 0
        for i in dp:
            ans = (ans+i[1])%mod
            # print(i)
        return ans%mod

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        # keep array that holds # of even/odd sum subarrays that end at that index
        ans = odd = even = 0
        for i in range(len(arr)):
            if arr[i] % 2 == 0: # even
                even = even + 1
                ans += odd
            else:               # odd
                even, odd = odd, even + 1
                ans += odd
                
        return ans % (10**9 + 7)

class Solution:
    # brute force：把所有的substring都for一遍，可以用bit operation优化
    # 其实不用两个数相加再整除2，直接看最后一位是不是1就行，可以用xor代替相加
    # better approach：对于每个index i，维护evens和odds，分别是在i之前的even prefix sum和odd prefix sum数量，然后用位运算优化
    def numOfSubarrays(self, arr: List[int]) -> int:
        n = len(arr)
        ret = 0
        # 当前是odd和是even的prefix sums个数
        odds, evens = 0, 1
        cur = 0 # 当前的prefix sum
        
        for num in arr:
            cur ^= num&1    # 查看奇偶
            if cur:         # 奇数
                # 如果当前prefix sum是奇数，查看在此之前有多少个偶数的prefix sum
                # 用cur减去之前所有是偶数的prefix sum，都可以得到一段奇数的substring
                ret += evens
                odds += 1
            else:
                # vice versa
                ret += odds
                evens += 1
        
        return ret % (10**9 + 7)
        
        
#     def numOfSubarrays(self, arr: List[int]) -> int:
#         n = len(arr)
#         ret = 0
        
#         presum = [0 for i in range(n)]
#         for i in range(n):
#             presum[i] = (arr[i] + (presum[i-1] if i > 0 else 0))&1
        
#         for i in range(n):
#             for j in range(i, n):
#                 if i == j:
#                     if arr[i]&1: ret += 1
#                 elif not i:
#                     if presum[j]: ret += 1
#                 else:
#                     if presum[j]^presum[i-1]: ret += 1

#         return ret


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        res = even = odd = 0
        for x in arr:
            even += 1
            if x % 2 != 0:
                odd,even = even,odd
            res = (res + odd) % (10 ** 9 + 7)
        return res

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        
        # https://leetcode.com/problems/number-of-sub-arrays-with-odd-sum/discuss/758041/Python-O(1)-Space-Clear-Solution
        
        if not arr: return 0
        cum = 0
        odd, even = 0, 1
        res = 0
        MOD = 10**9+7
        for num in arr:
            cum += num
            #print(odd,even, cum)
            if cum % 2:
                res += even
                odd += 1
            else:
                res += odd
                even += 1
            #print(odd,even, res)
            #print(\"________________\")
            res %= MOD
        return res%MOD


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        acc=[]
        temp=0
        ones=0
        for u in arr:
            temp+=u%2
            temp%=2
            if temp==1:
                ones+=1
        L=len(arr)
        return ones*(L-ones+1)%(10**9+7)


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        c,e,o,a=0,1,0,0
        for  i in arr:
            c+=i
            if c%2==0:
                a+=o
                a%=1000000007
                e+=1
            else:
                a+=e
                a%=1000000007
                o+=1
        return a%1000000007


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        # keep array that holds # of even/odd sum subarrays that end at that index
        odd = [0]
        even = [0]
        for i in range(len(arr)):
            if arr[i] % 2 == 0: # even
                even.append(even[-1] + 1)
                odd.append(odd[-1])
            else:               # odd
                even.append(odd[-1])
                odd.append(even[-2] + 1)
                
        # print(\"EVEN:\",even)
        # print(\"ODD: \", odd)
                
        return sum(odd) % (10**9 + 7)

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        run, prev = [], 0
        count = 0
        odd, even = 0, 0
        for ele in arr:
            run.append(prev + ele)
            prev = run[-1]
            if run[-1] % 2 != 0:
                count += even + 1
                odd += 1
            else:
                count += odd
                even += 1
        return count % (10 ** 9 + 7)

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        res = odd = even = 0
        for x in arr:
            even += 1
            if x % 2 != 0:
                even,odd = odd,even
                
            res = (res + odd) % (10 ** 9 + 7)
        return res


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        ans = 0
        even = 0
        odd = 0
        for v in arr:
            if v % 2 == 0:
                even, odd = even + 1, odd
            else:
                even, odd = odd, even + 1
            ans = (ans + odd) % 1000000007
        return ans 

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        acc=[]
        temp=0
        for u in arr:
            temp+=u%2
            acc.append(temp%2)
        L=len(arr)
        ones=sum([u%2 for u in acc])
        return ones*(L-ones+1)%(10**9+7)


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        res = odd = even = 0
        for x in arr:
            even += 1
            if x % 2:
                odd, even = even, odd
            res = (res + odd) % 1000000007             
        return res            

class Solution:
    def numOfSubarrays(self,A) -> int:
        n = len(A)
        dp_even,dp_odd = [0],[0]
        if A[0]%2:
            dp_odd[0] += 1
        else:
            dp_even[0] += 1

        ans = dp_odd[-1]
        
        for i in range(1,n):
            if A[i]%2:
                dp_odd.append( dp_even[i-1]+1 )
                dp_even.append( dp_odd[i-1] )
            else:
                dp_odd.append( dp_odd[i-1] )
                dp_even.append( dp_even[i-1]+1 )
            ans += dp_odd[i]
            ans %= (pow(10,9)+7)
        
        #print(dp_even,dp_odd)
        
        return ans%(pow(10,9)+7)

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        sum_even = 0
        sum_odd = 0
        out = 0
        for i in range(len(arr)):
            if arr[i] %2 ==0:
                sum_even, sum_odd = sum_even+1, sum_odd
            else:
                sum_even, sum_odd = sum_odd , sum_even +1
            out = (out + sum_odd) % 1000000007
        return out 

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        # corner case
        if not arr or len(arr) == 0:
            return 0
        # get total evens, odds after accumulation
        even = 1
        odd = 0
        cur = 0
        ret = 0
        for a in arr:
            cur = (a + cur) 
            if cur % 2 == 0:
                even += 1
                ret += odd
            else:
                odd += 1
                ret += even
            ret = ret % (10 ** 9 + 7)
        return ret


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        
        L = len(arr)
        works = [0] * L 
        not_works = [0] * L 
        
        if arr[0] % 2 == 1:
            works[0] += 1
        else:
            not_works[0] += 1
        
        for i in range(1, L):
            
            if arr[i] % 2 == 0:
                works[i] += works[i-1]
                not_works[i] += not_works[i-1]
            else:
                works[i] += not_works[i-1]
                not_works[i] += works[i-1]
            
            if arr[i] % 2 == 1:
                works[i] += 1
            else:
                not_works[i] += 1

        return sum(works) % (10**9 + 7)


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        '''
        This is an elementary dynamic programming problem.
        odd[i] records the number of subarray ending at arr[i] that has odd sum.
        even[i] records the number of subarray ending at arr[i] that has even sum.
        if arr[i + 1] is odd, odd[i + 1] = even[i] + 1 and even[i + 1] = odd[i]
        if arr[i + 1] is even, odd[i + 1] = odd[i] and even[i + 1] = even[i] + 1
        Since we only required the previous value in odd and even, we only need O(1) space.
        '''
        res = odd = even = 0
        for x in arr:
            even += 1
            if x % 2:
                odd, even = even, odd
            res = (res + odd) % 1000000007             
        return res

'''
https://www.youtube.com/watch?v=iTukzycJ69I
'''


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        
        '''
            here we are calculating prefix sum.
            Along with that we also keep track before
            any index i, how many prefix sum are even 
            and how many prefix sum are odd by using
            variables evenSum and oddSum. Becuase if 
            we subtract 
            
            *************************************
                even value from odd answer is odd
                and odd value from even again answer
                is odd
            *************************************
            
            This above mentioned simple 2 rules helpsto
            keep track of required answer
            
            
        '''
        
        evenSum=0
        oddSum=0
        prefSum=0
        ans=0
        
        
        for ele in arr:
            
            prefSum=prefSum+ele
            
            '''
                prefix sum is odd
            '''
            if prefSum%2==1:
                
                ans+=evenSum+1
                oddSum+=1
            else:
                ans+=oddSum
                evenSum+=1
                
            
            ans%=((10**9)+7)
            
            
            
        return ans
                
                
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
        
        
        
        
            
        
        
        
        


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        n=len(arr)
        dp=[[0 for i in range(2)]for i in range(n)]
        if arr[0]&1 :
            dp[0]=[0,1]
        else:
            dp[0]=[1,0]
        for i in range(1,len(arr)):
            if arr[i]&1:
                dp[i][1]=dp[i-1][0]+1
                dp[i][0]=dp[i-1][1]
            else:
                dp[i][1]=dp[i-1][1]
                dp[i][0]=dp[i-1][0]+1
        # print(dp)
        return sum(x[1] for x in dp)%(10**9+7)

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        
        o = 0 
        e = 0 
        c = 0 
        p = 0

        for i in arr:
            p += i
            if p % 2 ==0:
                c += o
                e += 1
            else:
                c += e
                c += 1
                o += 1
        return c % 1000000007

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        n=len(arr)
        odd,even,re,s=0,1,0,0
        for v in arr:
            s+=v
            if s%2==0:
                re+=odd
                even+=1
            else:
                re+=even
                odd+=1
        return re%1000000007


class Solution:
    def numOfSubarrays(self, A):
        MOD=10**9+7
        ans=0
        even=odd=0
        for x in A:
            if x%2:
                odd,even=1+even,odd
            else:
                even+=1
            ans=(ans+odd)%MOD
        return ans


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        o, e = 0, 0
        res = 0
        for n in arr:
            if n%2 == 0:
                e += 1
            else:
                o, e = e, o
                o += 1
            res += o
            res = res % (10**9+7)
        return res

class Solution:
    def numOfSubarrays(self, A):
        MOD=(10**9+7)
        ans=0
        tt=0
        even=odd=0
        for x in A:
            tt+=x
            if tt%2==0:
                ans=(ans+odd)%MOD
                even+=1
            else:
                ans=(ans+1+even)%MOD
                odd+=1
        return ans


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        n = len(arr)
        MOD = int(1e9 + 7)
        res = even = odd = 0 
        for i, a in enumerate(arr):
            even += 1
            if a % 2 == 1:
                even, odd = odd, even
            res = (res + odd) % MOD
        
        return res 
                


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        even=0
        odd=0
        sum1=0
        result=0
        for num in arr:
            sum1+=num
            if sum1%2==0:
                result+=odd
                even+=1
            else:
                result+=even+1
                odd+=1
            result%=(10**9+7)
                
        return result

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        MOD = 10 ** 9 + 7
        count = [1, 0]
        cur = answer = 0
        for n in arr:
            cur ^= n & 1
            answer = (answer + count[1 ^ cur]) % MOD
            count[cur] += 1
        
        return answer

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        le=len(arr)
        o=0
        s=0
        for i in arr:
            s+=i
            if s%2:
                o+=1
        return (o*((le-o)+1))%1000000007

MOD = 1000000007
class Solution:
    def numOfSubarrays(self, arr):
        n = len(arr)
        pre_sum = [1, 0]
        now_sum = 0
        res = 0
        for i in range(n):
            now_sum += arr[i]
            if now_sum % 2 == 1:
                res += pre_sum[0]
                pre_sum[1] += 1
            else:
                res += pre_sum[1]
                pre_sum[0] += 1
        return res % MOD

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        odds = 0
        evens = 1
        ans = 0
        runningsum = 0
        MOD = 10**9 + 7
        
        for a in arr:
            runningsum += a
            if runningsum%2:
                ans = (ans + evens)%MOD
                odds += 1
            else:
                ans = (ans + odds)%MOD
                evens += 1
        return ans

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        n = len(arr)
        MOD = int(1e9 + 7)
        res = even = odd = 0 
        for a in arr:
            even += 1
            if a % 2:
                even, odd = odd, even
            res = (res + odd) % MOD
        
        return res 
                


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        ans, odd, even = 0, 0, 0
        for i in arr:
            if i & 1:
                odd, even = even + 1, odd                
            else:
                even = even + 1
            ans += odd
                
        return ans % (10**9 + 7)
                    


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        even = 0
        odd = 0
        c = 0
        for e in arr:
            if e % 2 == 1:
                c += 1 + even
                even, odd = odd, even + 1
            else:
                c += odd
                even += 1
        return c % (10**9 + 7)


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:

        odd = 0
        even = 1
        cnt = 0
        res = 0
        mod = 1000000007
        for i in range(len(arr)):
            if arr[i] % 2 == 1:
                cnt += 1
            if cnt % 2 == 1:
                res = (res + even) % mod
                odd += 1
            else:
                res = (res + odd) % mod
                even += 1
                
        return int(res)
            
            
        


MOD = 1000000007
class Solution:
    def numOfSubarrays(self, arr):
        n = len(arr)
        pre_sum = [1, 0]
        now_sum = 0
        res = 0
        for i in range(n):
            now_sum ^= (arr[i] & 1)
            if now_sum == 1:
                res += pre_sum[0]
                pre_sum[1] += 1
            else:
                res += pre_sum[1]
                pre_sum[0] += 1
        return res % MOD

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        ans = 0
        odd = 0
        even = 0
        tot = 0
        for i in range(len(arr)):
            tot += arr[i]
            if tot%2==0:
                even +=1
            else:
                odd += 1
            
            if tot%2!=0:
                ans +=1
                ans += even
            else:
                ans += odd
        
        return ans % (10**9 + 7)

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        ans, odd, even = 0,0,0
        
        for num in arr:
            if num %2 != 0:
                odd, even = even+1, odd
            else:
                odd, even = odd, even+1
            ans += odd
        return ans % int(1e9+7)


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        MOD = int(1e9 + 7)
        res = even = odd = 0 
        for a in arr:
            even += 1
            if a % 2:
                even, odd = odd, even
            res = (res + odd) % MOD
        
        return res 
                


# class Solution:
#     def numOfSubarrays(self, arr: List[int]) -> int:
#         odd = 0
#         even = 0
#         n = len(arr)
#         sumlist = [0]*n
#         output = 0
#         for i in range(n-1, -1, -1):
#             if i != n-1:
#                 sumlist[i] += arr[i] + sumlist[i + 1] 
#             else:
#                 sumlist[i] += arr[i]
#             if sumlist[i] % 2 == 0:
#                 output += odd
#                 even += 1
#             else:
#                 output += 1
#                 output += even
#                 odd += 1
#             output %= (10**9 + 7)
#         return output

# class Solution:
#     def numOfSubarrays(self, A):
#         # prefix sum means the sum of all numbers up to that index
#         # count = [the number of even prefix sums, the number of odd prefix sums]
#         # we start with 1 even prefix sum because 0 is even
#         count = [1, 0]
#         # initialize the current prefix sum (cur) as being even and initialize the result as 0
#         cur = res = 0
#         # go through each of the numbers in the array
#         for a in A:
#             # see if the next number is odd (which is what a&1 is doing since it's a bitwise AND operator), and use the exclusion OR operator to see if the current number and the previous number add up to being even (0) or odd (1)
#             # this can also be written as cur = (cur + (a % 2))%2
#             cur ^= a & 1
#             # if the prefix sum is even, then add the number of odd prefix sums to the results. If the prefix sum is odd, then add the number of even prefix sums to the result.
#             res += count[1 - cur]
#             # increase the counter for the number of even or odd prefix sums seen so far
#             count[cur] += 1
#         return res % (10**9 + 7)

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        res = odd = even = 0
        for x in arr:
            even += 1
            if x % 2:
                odd, even = even, odd
            res = (res + odd) % 1000000007             
        return res         

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        ret = 0
        odd_count, even_count = 0, 0
        
        for num in arr:
            if num % 2 != 0:
                ret += even_count + 1
                odd_count, even_count = even_count + 1, odd_count
            else:
                ret += odd_count
                odd_count, even_count = odd_count, even_count + 1
        
        return ret % (10 ** 9 + 7)

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        odd = even = ans = 0
        mod = (10 ** 9) + 7
        for num in arr:
            if num % 2 == 1:
                ans += (even + 1)
                curr_even = even
                even = odd
                odd = curr_even + 1
            else:
                ans += odd
                even += 1
        
        return ans % mod

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        odd_sums = 0
        even_sums = 0
        ret = 0
        sum_ = 0
        
        
        for num in arr:
            sum_ += num
            
            
            if (sum_ & 1):
                ret += even_sums + 1
                odd_sums += 1
            else:
                ret += odd_sums
                even_sums += 1
                
        return ret % (10 ** 9 + 7)

class Solution:
    def numOfSubarrays(self, A):
        ans=even=odd=0
        for x in A:
            if x%2:
                odd,even=1+even,odd
            else:
                even+=1
            ans+=odd
        return ans%(10**9+7)


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        ans = 0
        even_sums = []
        odd_sums = []
        current_sum = 0
        for i in range(len(arr)):
            current_sum += arr[i]
            if current_sum % 2 == 0:
                # is even
                # if odd_sums[-1]
                # if len(odd_sums) > 0:
                #     ans += i - odd_sums[-1]
                ans += len(odd_sums)
                
                even_sums.append(i)
            else:
                # is odd
                # ans += 1
                ans +=  1 + len(even_sums)
                # j = 1
                # while j <= len(even_sums) and even_sums[-j] == i-1
                #     if 
                #     j += 1
                # if len(even_sums) > 0 and even_sums[-1] == i-1:
                #     ans += 1
                # if len(odd_sums) > 0:
                #     ans += i - odd_sums[-1] + 1
                # else:
                #     ans += i
                # ans += len([]) 
                # last odd 
                # odd_sums[-1]
                odd_sums.append(i)
        return ans % (10**9 + 7)
            
if True:
    print((Solution().numOfSubarrays([1,2,3,4,5,6,7]))) # 16
    print((Solution().numOfSubarrays([100,100,99,99]))) # 4
    print((Solution().numOfSubarrays([7]))) # 1
    print((Solution().numOfSubarrays([2,4,6]))) # 0
            
        
# [1,2,3,4,5,6,7]
# [1]
# [1,2]
# [1]
        
# [1,3,5]
# 1, 1, 

# [2,4,6]
# 0

# set(100), set(99), 200
# [100,100,99,99]
# 1 + 1 + 1

# [1,2,3,4,5,6,7]
# 1 + 1 + 1 + 1 set(1,3) set(2)


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        sumEven = 0
        sumOdd = 0
        cumSum = 0
        
        result = 0
        for num in arr:
            cumSum += num
            if cumSum % 2 == 1:
                result += 1 + sumEven
                sumOdd += 1
            else:
                result += sumOdd
                sumEven += 1
        
        return result % (10**9+7)


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        prefixSum = [0]
        for i in range(1, len(arr)+1):
            prefixSum.append(prefixSum[-1]+arr[i-1])
        out = 0
        prefixEven = 0
        prefixOdd = 0
        for i in range(len(prefixSum)):
            if prefixSum[i]%2 == 0:
                prefixEven += 1
                out += prefixOdd
            else:
                prefixOdd += 1
                out += prefixEven
        return out%(10**9+7)


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        # count of odd numbers, counts of even sums and odd sums
        # default 1 for counts of even sums means 0 even sum is also a valid combination
        odds, counts = 0, [1, 0]
        for x in arr:
            odds += 1 if x % 2 else 0
            counts[odds % 2] += 1
        return counts[0] * counts[1] % (10**9 + 7)

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        n = len(arr)
        MOD = int(1e9 + 7)
        even, odd = [0]*(n+1), [0]*(n+1)    
        for i, a in enumerate(arr):
            if a % 2 == 1:
                even[i] = odd[i-1] 
                odd[i] = (even[i-1] + 1) 
            else:
                even[i] = (even[i-1] + 1) 
                odd[i] = odd[i-1] 
        
        return sum(odd) % MOD
                


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        res = odd = even = 0
        for x in arr:
            even += 1
            if x % 2:
                odd, even = even, odd
            res = (res + odd) % 1000000007             
        return res

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        
        N = len(arr)
        if(N==0):
            return 0
        elif(N==1):
            return abs(arr[0])%2
        s = 0
        tot = 0
        ct_odd = 0
        ct_even = 0
        for i in range(N):
            s += arr[i]
            if(s%2==1):
                tot += 1+ct_even
                ct_odd += 1
            else:
                tot += ct_odd
                ct_even += 1
        return tot%(10**9+7)
        
        '''l1 = 0
        l2 = 0
        if(arr[0]%2):
            l1 += 1
        else:
            l2 += 1
        tot = 0
        tot += l1
        
        for i in range(1,N):
            l3 = 0
            l4 = 0
            if(arr[i]%2):
                l3 = 1+l2
                l4 = l1
            else:
                l3 = l1
                l4 = 1+l2
            l2 = l4
            l1 = l3
            tot += l1
        return tot%(10**9+7)'''


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        count = len(arr)
        pre_odd_count = arr[0] % 2
        pre_even_count = 1 - pre_odd_count
        result = pre_odd_count


        for index in range(1, count):
            isodd = arr[index] % 2
            if isodd:
                temp = pre_odd_count
                pre_odd_count  = 1 + pre_even_count
                pre_even_count = temp
            else:
                pre_odd_count = pre_odd_count
                pre_even_count = 1 + pre_even_count
            result += pre_odd_count

 
        return result % 1000000007

import copy
class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        mod=(10**9)+7
        arr1=arr.copy()
        for i in range(1,len(arr)):
            arr1[i]+=arr1[i-1]
      
        odd,even=0,0
        cou=0
        for i in range(len(arr1)):
            
            if arr1[i]%2==0:
                even+=1
            else:
                odd+=1
        for i in range(len(arr1)):
            
            if arr1[i]%2==1:
                cou+=1
        
       
        
        cou+=odd*even
        
        return cou%mod
        
        
        


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        s, d, ans = 0, 0, 0
        for n in arr:
                if n%2:
                    s, d = d, s
                    s += 1
                else:
                    d += 1
                ans += s
                #print(n, ans)
        return ans%1000000007
                    


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        n = len(arr)
        odd, even = [0] * n, [0] * n
        for i,v in enumerate(arr):
            if not i:
                odd[i] += v%2 == 1
                even[i] += v%2 !=1
            else:
                if v%2:
                    odd[i] += 1 + even[i-1]
                    even[i] += odd[i-1]
                else:
                    odd[i] += odd[i-1]
                    even[i] += 1 + even[i-1]
        return sum(odd) % (10**9+7)


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        result = 0
        dp = [0] * len(arr)
        if (arr[0] % 2 != 0):
            dp[0] = 1
        result = dp[0]
        for i in range(1, len(arr)):
            if (arr[i] % 2 == 0):
                dp[i] = dp[i-1]
            else:
                dp[i] = i - dp[i-1] + 1
            result = (result + dp[i]) % (10 ** 9 + 7)
            
        return result

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        
        N = len(arr)
        if(N==0):
            return 0
        elif(N==1):
            return abs(arr[0])%2
        
        l1 = 0
        l2 = 0
        if(arr[0]%2):
            l1 += 1
        else:
            l2 += 1
        tot = 0
        tot += l1
        
        for i in range(1,N):
            l3 = 0
            l4 = 0
            if(arr[i]%2):
                l3 = 1+l2
                l4 = l1
            else:
                l3 = l1
                l4 = 1+l2
            l2 = l4
            l1 = l3
            tot += l1
        return tot%(10**9+7)


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        M = 10 **9 + 7
        #think all odd as 1 and even as 0 
        new_arr = [ 1 if i %2 == 1 else 0 for i in  arr]
        res = 0
        cucr_sum = 0
        cash = {0:1, 1: 0}
        for end in range(len(new_arr)):
            cucr_sum += new_arr[end]
            if cucr_sum%2 == 1:
                res += cash[0]
                cash[1] += 1
                
            else:
                res += cash[1]
                cash[0] += 1
        
        return res%M
                
            


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        res = even = odd = 0
        for x in arr:
            even += 1
            if x % 2 != 0:
                even,odd = odd,even
            res = (res + odd) % (10 ** 9 + 7)
        return res

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        mod, n = 10 ** 9 + 7, len(arr)
        odd_sum, even_sum, curr_sum, ans = 0, 1, 0, 0
        for i in arr:
            curr_sum += i
            if curr_sum % 2 == 1:
                odd_sum += 1
                ans += even_sum % mod
            else:
                even_sum += 1
                ans += odd_sum % mod
        ans %= mod
        return ans

class Solution:
    # Ref: https://leetcode.com/problems/number-of-sub-arrays-with-odd-sum/discuss/755495/Python-or-O(n)-time-and-O(1)-space-or-prefix-sum(detailed-explanation)
    def numOfSubarrays(self, arr: List[int]) -> int:
        odd_sum, even_sum, cur_sum, ans =  0, 1, 0, 0
        mod = (10**9 + 7)
        for i in arr:
            cur_sum+=i
            
            #Check for odd sum
            if cur_sum % 2 != 0:
                odd_sum+=1
                ans += even_sum % mod
            
            #Check for even sum
            if cur_sum % 2 == 0:
                even_sum+=1
                ans += odd_sum % mod
        
        ans = ans % mod
        
        return ans

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        mod = 10**9+7
        odd = 0
        even = 0
        ans = 0
        for num in arr:
            if num%2:
                odd, even = even + 1, odd
            else:
                even += 1
            ans = (ans+odd)%mod
        return ans

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        
        dp=[0,0]
        res=cur=0
        for i in arr:
            cur^=i&1


            res+=cur+dp[1-cur]

            dp[cur]+=1
 
 
                
        return res%(10**9 + 7)


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        MOD = 10 ** 9 + 7
        
        memo = {0: 0, 1: 0}
        cumsum = 0
        
        # Odd + Even = Odd
        # Even + Even = Even
        # Odd + Odd = Even
        
        res = 0
        
        for v in arr:
            cumsum += v
            
            if cumsum % 2 == 0:
                # Is Even
                memo[0] += 1
                res = (res + memo[1]) % MOD
                
            else:
                # Is Odd
                memo[1] += 1
                res = (1 + res + memo[0]) % MOD
                
        return res

from itertools import accumulate
class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
      # How many non-empty subarrays are there from an array of length k
      def num_subarrays(k):
        return (k * k  + k) // 2
      counts = [0, 0]
      for prefix in accumulate(arr):
        counts[prefix % 2] += 1
      evens, odds = counts
      return (num_subarrays(len(arr)) - (num_subarrays(evens) + (num_subarrays(odds) - odds))) % (10 ** 9 + 7)
      
      
      


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        
        even = 0
        odd = 0
        
        res = 0
        for i in range(len(arr)):
            if arr[i] % 2 == 1:
                odd, even = even + 1, odd
                res += odd
            else:
                even += 1
                res += odd
        
        return res % 1000000007

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        dp = [0] * len(arr)
        dp[0] = arr[0]&1
        for i in range(1,len(arr)):
            if arr[i]&1: # arr[i] is odd, for dp[i] be odd, dp[i-1] must be even
                dp[i] = i - dp[i-1] + 1 # 1 as arr[i] itself
            else: # arr[i] is even
                dp[i] = dp[i-1]
        return sum(dp) % (10**9+7)


class Solution:
  def numOfSubarrays(self, arr: List[int]) -> int:
    prefix = [0]
    
    for num in arr:
      prefix.append(prefix[-1] ^ num & 1)
    
    # now we are looking for the numbr of pairs (i, j) where prefix[i] != prefix[j]
    
    zeros = 0
    ones = 0
    result = 0
    
    for x in prefix:
      if x == 1:
        ones += 1
        result += zeros
      else:
        zeros += 1
        result += ones
    return result % (10 ** 9 + 7)


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        ans = 0
        mod = 1e9 + 7
        seen = [1, 0]
        for i in range(len(arr)):
            if(i > 0):
                arr[i]+=arr[i-1]
            ans += seen[(arr[i]+1)%2]
            ans %= mod
            seen[arr[i]%2]+=1
        return int(ans)

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        pre = [0]
        for n in arr:
            pre.append(pre[-1] + n)
        odd = even = 0
        ans = 0
        for i in range(len(pre)):
            if pre[i] % 2 == 0:
                ans += odd
                even += 1
            else:
                ans += even
                odd += 1
        return ans % (10 ** 9 + 7)

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        count = []
        ans = 0
        odd = 0
        even = 0
        tot = 0
        for i in range(len(arr)):
            tot += arr[i]
            if tot%2==0:
                even +=1
            else:
                odd += 1

            count.append((tot, even, odd))
            if count[i][0]%2 != 0:
                ans +=1
                ans += count[i][1]
            else:
                ans += count[i][2]
        
        return ans % (10**9 + 7)

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

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        ans = 0
        mod = 1e9 + 7
        seen = {0: 1, 1: 0}
        for i in range(len(arr)):
            if(i > 0):
                arr[i]+=arr[i-1]
            ans += seen[(arr[i]+1)%2]
            ans %= mod
            seen[arr[i]%2]+=1
        return int(ans)

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        ans = 0
        even = 0
        odd = 0
        for v in arr:
            if v % 2 == 0:
                even += 1
            else:
                even, odd = odd, even
                odd += 1
            ans += odd
        return ans  % 1000000007

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        memo = {0:1, 1:0}
        cnt = 0
        curr_sum = 0
        K = 10**9+7
        for n in arr:
            curr_sum += n
            if curr_sum%2==0:
                cnt += memo[1]
            else:
                cnt += memo[0]
            memo[curr_sum%2] += 1
            cnt = cnt%K
            # print (memo, cnt)
        return cnt

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        s = [0, 0]
        res = 0
        cur = 0
        for x in arr:
            cur = (cur + x) % 2
            res += s[1-cur]
            res += int(cur == 1)
            s[cur] += 1
        return res % (10 ** 9 + 7)

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        sum_even = 0
        sum_odd = 0
        out = 0
        for i in range(len(arr)):
            if arr[i] %2 ==0:
                sum_even, sum_odd = sum_even+1, sum_odd
            else:
                sum_even, sum_odd = sum_odd , sum_even +1
            out += sum_odd
        return out % (10**9 + 7)




MOD = 10**9 + 7


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        odd_cum_sums = 0
        even_cum_sums = 0

        total_odd_sums = 0
        # Get cumulative sum
        for i in range(len(arr) - 1):
            arr[i + 1] += arr[i]

        for sum_ in arr:
            # Even cumulative sum
            if sum_ % 2 == 0:
                total_odd_sums += odd_cum_sums
                even_cum_sums += 1
            # Odd cumulative sum
            else:
                total_odd_sums += 1 + even_cum_sums
                odd_cum_sums += 1

        return total_odd_sums % MOD


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        evenSum=0
        oddSum=0
        prefSum=0
        ans=0


        for ele in arr:

            prefSum=prefSum+ele

            '''
                prefix sum is odd
            '''
            if prefSum%2==1:

                ans+=evenSum+1
                oddSum+=1
            else:
                ans+=oddSum
                evenSum+=1


            ans%=((10**9)+7)



        return ans

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        ans = 0
        seen_odd, seen_even = set(), set()
        odd_count, even_count = 0, 1
        psum = 0
        mod = 10**9 + 7
        for a in arr:
            psum += a
            if psum % 2 == 0:
                ans = (ans + odd_count) % mod
                seen_even.add(psum)
                even_count += 1
            else:
                ans = (ans + even_count) % mod
                seen_odd.add(psum)
                odd_count += 1
                
        return ans

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        c = collections.defaultdict(int)
        s = 0
        c[0] += 1
        res = 0
        mod = 10 ** 9 + 7
        for x in arr:
            s ^= x%2
            res += c[1-s]
            res %= mod
            c[s] += 1
        return res


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        A = [i%2 for i in arr]
        n = len(A)
        
        lst = [[0,0]]
        lst[0][A[0]&1] = 1
        
        for i in range(1, n):
            if A[i]:
                lst.append([lst[-1][1], 1+lst[-1][0]])
            else:
                lst.append([1+lst[-1][0], lst[-1][1]])
                
        # print(lst)
        
        return sum([x[1] for x in lst]) % (10**9+7)

def accumulate(arr):
    acc = 0
    for elem in arr:
        acc = (acc + elem) % 2
        yield acc

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        parity_array = (x % 2 for x in arr)
        cumulative_array = accumulate(parity_array)
        
        prev = [1, 0]
        ans = 0
        for elem in cumulative_array:
            ans += [prev[1], prev[0]] [elem]
            prev[elem] += 1
        
        return ans % (10 ** 9 + 7)


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


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        cumsum = 0
        even = 1
        odd = 0
        ans = 0
        MOD = 10**9 + 7
        
        for num in arr:
            cumsum += num
            if cumsum % 2 == 0:
                ans = (ans + odd) % MOD
                even += 1
            else:
                ans = (ans + even) % MOD
                odd += 1
        
        return ans
                


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        count = len(arr)
        isodd = [item%2 for item in arr]
        odd_end_total = [0] * count
        even_end_total = [0] * count

        odd_end_total[0] = isodd[0]
        even_end_total[0] = 1 - odd_end_total[0]

        for index in range(1, count):
            if isodd[index]:
                odd_end_total[index] = 1 + even_end_total[index-1]
                even_end_total[index] = odd_end_total[index-1]
            else:
                odd_end_total[index] = odd_end_total[index-1]
                even_end_total[index] = 1 + even_end_total[index-1]

        result = 0
        for index in range(count):
            result += odd_end_total[index]

        return result % 1000000007

def isEven(n):
    return n % 2 == 0
def isOdd(n):
    return not isEven(n)

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        od = list(range(len(arr)))
        ev = list(range(len(arr)))
        
        if isEven(arr[0]):
            od[0] = 0
            ev[0] = 1
        else:
            od[0] = 1
            ev[0] = 0

        for i, num in enumerate(arr):
            if i == 0:
                continue
            if isOdd(num):
                od[i] = ev[i-1] + 1
                ev[i] = od[i-1]
            else:
                od[i] = od[i-1]
                ev[i] = ev[i-1] + 1
        ans = 0
        
        for num in od:
            ans += num
        return ans % (10 ** 9 + 7)

#744

M = int(1e9+7)


class Solution:
  def numOfSubarrays(self, arr: List[int]) -> int:
      n = len(arr)
      odd = [-1] * n
      even = [-1] * n
      
      odd[0] = 1 if arr[0] % 2 == 1 else 0
      even[0] = 1 if arr[0] % 2 == 0 else 0
      
      for i in range(1, n):
        v = arr[i]
        if v % 2 == 1:
          odd[i] = (1 + even[i-1]) % M
          even[i] = odd[i-1]
        else:
          odd[i] = odd[i-1]
          even[i] = (even[i-1] + 1) % M
      
      
      ret = 0
      for v in odd:
        ret = (ret + v) % M
      return ret

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        n = len(arr)
        even = [0]*(n)
        odd = [0]*(n)
        # dp, where odd[i], even[i] are numbers of sub arrays that end at i
        # we then sum them up together
        for i, x in enumerate(arr):
            if i == 0:
                if x % 2 == 0:
                    even[i] = 1
                else:
                    odd[i] = 1
            else:
                if x % 2 == 0:
                    even[i] = even[i-1] + 1     
                    odd[i] = odd[i-1]
                else:
                    even[i] = odd[i-1]
                    odd[i] = even[i-1] + 1
                 
        return sum(odd) % (int(1e9) + 7)

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        limit = 10**9 + 7
        # use dp:
        
        # the number of odd sums ending at each index
        final = 0 
        dp_even = [0] * (len(arr ) + 1)
        dp_odd = [0] * (len(arr ) + 1)
        for i in range(len(arr)):
            num = arr[i]
            if num%2 == 0:
                # if this number is even, so we need to find the count of prev odd
                odd_cur = dp_odd[i]
                even_cur = 1 + dp_even[i]
                final += odd_cur
                dp_even[i + 1] = even_cur
                dp_odd[i + 1] = odd_cur
                # so we need to calculate the number odd and even sum ending at each index
            else:
                odd_cur = dp_even[i] + 1
                even_cur = dp_odd[i]
                final += odd_cur
                dp_odd[i + 1] = odd_cur
                dp_even[i + 1] = even_cur
                
        return final % limit

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        '''
        odd[i] = number of sub arrays with odd sum and end at i
        even[i] = number of sub arrays with even sum and end at i
        '''
        odd = [0 for x in arr]
        even = [0 for x in arr]
        odd[0] = 1 if arr[0] % 2 == 1 else 0
        even[0] = 1 if arr[0] % 2 == 0 else 0
        for i in range(1, len(arr)):
            if arr[i] % 2 == 0:
                odd[i] = odd[i-1]
                even[i] = even[i-1] + 1
            else:
                odd[i] = even[i-1] + 1
                even[i] = odd[i-1]
        return sum(odd) % 1000000007


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        mod = 10**9+7
        for i in range(len(arr)):
            arr[i] %= 2
        
        n = len(arr)
        dp = []
        ones = 0
        zeroes = 0
        for i in arr:
            if not dp:
                dp.append(i)
            else:
                dp.append(dp[-1]+i)
            
            dp[-1] %= 2
            if dp[-1] == 0:
                zeroes += 1
            else:
                ones += 1
        
        #print(ones,zeroes)
        total = n*(n+1)//2
        total -= ones*(ones-1)//2
        total -= (zeroes+zeroes*(zeroes-1)//2)
        
        return total%mod

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        r=0
        e=0
        o=0
        for i in arr:
            if(i%2==1):
                r+=(e+1)
                o,e=e+1,o
            else:
                r+=o
                o,e=o,e+1
        a=(10**9)+7
        return r%a


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        odd = 0
        even = 0
        n = len(arr)
        sumlist = [0]*n
        output = 0
        for i in range(n-1, -1, -1):
            if i != n-1:
                sumlist[i] += arr[i] + sumlist[i + 1] 
            else:
                sumlist[i] += arr[i]
            if sumlist[i] % 2 == 0:
                output += odd
                even += 1
            else:
                output += 1
                output += even
                odd += 1
            output %= (10**9 + 7)
        return output

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        ans = 0
        even = 0
        odd = 0
        for v in arr:
            if v % 2 == 0:
                even, odd = even + 1, odd
            else:
                even, odd = odd, even + 1
            ans += odd
        return ans  % 1000000007

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        odd, even = 0,0
        arr = [i % 2 for i in arr]
        
        if arr[0] != 0:
            odd += 1
        else:
            even += 1
                    
        for i in range(1,len(arr)):         
            arr[i] = arr[i - 1] + arr[i]
            if arr[i] % 2 == 0:
                even += 1
            else:
                odd += 1

        ans = 0
        for i in arr[::-1]:
            if i % 2 == 0 and odd > 0:
                ans += odd
                even -= 1
            elif i % 2 == 1:
                ans += (even+1)
                odd -= 1
            else:
                continue
        return ans % (10**9 + 7)

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        odd, even = 0,0
        arr = [i % 2 for i in arr]
        
        if arr[0] != 0:
            odd += 1
        else:
            even += 1
                    
        for i in range(1,len(arr)):         
            arr[i] = arr[i - 1] + arr[i]
            if arr[i] % 2 == 0:
                even += 1
            else:
                odd += 1

        ans = 0
        for i in arr[::-1]:
            if i % 2 == 0 and odd > 0:
                ans += odd
                even -= 1
            elif i % 2 == 1:
                ans += (even+1)
                odd -= 1
            else:
                break
        return ans % (10**9 + 7)

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        dp = [[0, 0]]
        
        ans = 0
        for i in arr:
            if i % 2 == 0:
                dp.append([dp[-1][0] + 1, dp[-1][1]])
            else:
                dp.append([dp[-1][1], dp[-1][0] + 1])
               
            ans += dp[-1][1]
        
        return int(ans % (1e9 + 7))

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        
        dp=[-1 for i in range(len(arr))]
        dp[0]=[(arr[0]+1)%2,arr[0]%2]
        total=dp[0][1]
        for k in range(1,len(arr)):
            if arr[k]%2==0:
                dp[k]=[(dp[k-1][0]+1)%(10**9+7),(dp[k-1][1])%(10**9+7)]
                total+=dp[k][1]
                total=total%(10**9+7)
            else:
                dp[k]=[(dp[k-1][1])%(10**9+7),(dp[k-1][0]+1)%(10**9+7)]
                total+=dp[k][1]
                total=total%(10**9+7)
        return total%(10**9+7)
        
            
      


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        mod = 10**9 + 7
        result = 0
        sumOdd = [0] * (len(arr))
        sumEven = [0] * (len(arr))
        if arr[0] % 2 == 1:
            sumOdd[0] = 1
            sumEven[0] = 0
        else:
            sumOdd[0] = 0
            sumEven[0] = 1
        for i in range(1,len(sumOdd)):
            if arr[i] % 2 == 0:
                sumOdd[i] = sumOdd[i - 1]
                sumEven[i] = sumEven[i - 1] + 1
            else:
                sumOdd[i] = sumEven[i - 1] + 1
                sumEven[i] = sumOdd[i - 1]
        return sum(sumOdd) % mod


class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        n = len(arr)
        dp = [[0]*2 for _ in range(n+1)]
        kMod = 1e9+7
        for i, num in enumerate(arr):
           
            if num&1:
                #even
                dp[i+1][0] = dp[i][1]
                #odd
                dp[i+1][1] = dp[i][0]+1
            else:
                #even
                dp[i+1][0] = dp[i][0] + 1
                #odd
                dp[i+1][1] = dp[i][1]
        
        return int(sum([dp[i][1] for i in range(n+1)])%kMod)

class Solution:
    def numOfSubarrays(self, A: List[int]) -> int:
        n = len(A)
        mod = 10**9+7
        ans = 0
        prefix, ctr = 0, Counter([0]) 
        for i in range(n):
            prefix = prefix+A[i]
            s = prefix%2
            ans = ans+ctr[1-s]
            ans = ans%mod 
            ctr[s] += 1
        return ans

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        even, odd = 1, 0
        total = 0
        ans = 0
        for i in arr:
            total += i
            if total % 2 == 1:
                ans += even
                odd += 1
            else:
                ans += odd
                even += 1
            ans %= 10**9 + 7
        return ans