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

Source: leetcode | Difficulty: MEDIUM
Tags: Mathematics

Dynamic programming

Data structures

Range queries

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)]
		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
			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
		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]
			if is_odd:
				ans += 1 + odd_even_count[idx][1]
			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[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)
		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:
				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(1000000000.0 + 7)
		n = len(arr)
		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
		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:

	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(1000000000.0 + 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:
		(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)):
			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]
		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) % 1000000007
			else:
				odd += 1
				res = (res + even) % 1000000007
		return res


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)
		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)
		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:
		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 % (1000000000.0 + 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
		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:
		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)
		ret = 0
		(odds, evens) = (0, 1)
		cur = 0
		for num in arr:
			cur ^= num & 1
			if cur:
				ret += evens
				odds += 1
			else:
				ret += odds
				evens += 1
		return ret % (10 ** 9 + 7)


class Solution:

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


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:
		odd = [0]
		even = [0]
		for i in range(len(arr)):
			if arr[i] % 2 == 0:
				even.append(even[-1] + 1)
				odd.append(odd[-1])
			else:
				even.append(odd[-1])
				odd.append(even[-2] + 1)
		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:
		if not arr or len(arr) == 0:
			return 0
		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:
		evenSum = 0
		oddSum = 0
		prefSum = 0
		ans = 0
		for ele in arr:
			prefSum = prefSum + ele
			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)
		(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, 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(1000000000.0 + 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)


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(1000000000.0 + 7)


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, 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:
				ans += len(odd_sums)
				even_sums.append(i)
			else:
				ans += 1 + len(even_sums)
				odd_sums.append(i)
		return ans % (10 ** 9 + 7)
if True:
	print(Solution().numOfSubarrays([1, 2, 3, 4, 5, 6, 7]))
	print(Solution().numOfSubarrays([100, 100, 99, 99]))
	print(Solution().numOfSubarrays([7]))
	print(Solution().numOfSubarrays([2, 4, 6]))


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:
		(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)
		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)


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
		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
			elif 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:
		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
		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:
		(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:

	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
			if cur_sum % 2 != 0:
				odd_sum += 1
				ans += even_sum % mod
			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:
		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
		res = 0
		for v in arr:
			cumsum += v
			if cumsum % 2 == 0:
				memo[0] += 1
				res = (res + memo[1]) % MOD
			else:
				memo[1] += 1
				res = (1 + res + memo[0]) % MOD
		return res


from itertools import accumulate

class Solution:

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

		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:
		prefix = [0]
		for num in arr:
			prefix.append(prefix[-1] ^ num & 1)
		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 = 1000000000.0 + 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:
		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:
		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
		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)


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
		for i in range(len(arr) - 1):
			arr[i + 1] += arr[i]
		for sum_ in arr:
			if sum_ % 2 == 0:
				total_odd_sums += odd_cum_sums
				even_cum_sums += 1
			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:
		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]])
		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:
		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)


M = int(1000000000.0 + 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:
		limit = 10 ** 9 + 7
		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:
				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
			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 = [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
		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:
		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 % (1000000000.0 + 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