Number of Subsequences with Even and Odd Sum

Your task is to determine the number of subsequences with odd sums and the number of subsequences with even sums from a given array of positive integers. As resulting numbers can be large, return both counts modulo 10⁹ + 7.

Definition:

• An even sum subsequence is one where the total sum of elements is divisible by 2.
• An odd sum subsequence is one where the total sum leaves a remainder of 1 when divided by 2.

Example:

Input:

T = 1
N = 3
array = [1, 2, 3]

Output:

3 4

Explanation:

The possible non-empty subsequences are {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}. Out of these, the odd sum subsequences are {1}, {3}, {2,3}, {1,2,3} and the even sum ones are {2}, {1,2}, {1,3}.

Constraints:

• 1 <= T <= 100
• 1 <= N <= 104
• 1 <= ARR[i] <= 109

Note:

• There are 2N - 1 non-empty subsequences for an array of size N.
• Subsequences can contain duplicate elements from the array.
• The modulo operation 10⁹ + 7 ensures the numbers remain manageable.
• The function that you implement does not need to handle I/O operations.