Number of Sub-arrays With Odd Sum
Given an array of integers arr, return the number of subarrays with an odd sum.
Since the answer can be very large, return it modulo 10^9 + 7.
Example 1
Input
arr = [1,3,5]Output
4Odd subarray sums are 1, 9, 3, and 5, so the answer is 4.
Example 2
Input
arr = [2,4,6]Output
0All subarrays have even sums, so the answer is 0.
Constraints
- 1 <= arr.length <= 10^5
- 1 <= arr[i] <= 100