## MAXSUB - Maximum Subset of Array

no tags

Given an array find the sum of the maximum non-empty subset of the array and also give the count of the subset. A subset of an array is a list obtained by striking off some (possibly none) numbers.

A non-empty subset implies a subset with at least 1 element in it.

### Input

First line contains an integer T which is the number of integers. Following this T-cases exist.

Each case starts with a line containing an integer n which is the number of elements in the array.

The next line contains n-integers which contain the value of this subset.

### Constraints

T <= 20

n <= 50,000

Each element in the array <= 1,000,000,000

### Output

For each test case output the value of the maximum subset and the count of the subsets modulo 1000,000,009

### Example

```Input:
2
5
1 -1 1 -1 1
6
-200 -100 -100 -400 -232 -450

Output:
3 1
-100 2```

## Code Examples

### #1 Code Example with Python Programming

```Code - Python Programming```

``````modulo = 1000000009
def power(a, b):
if b == 0:
return 1
if b % 2 == 1:
return power(a, b - 1) * a % modulo
half = power(a, b >> 1)
return half * half % modulo
T = int(input())
for c in range(T):
N = int(input())
assert N > 0
a = map(int, raw_input().split())
big = -1 << 30
sum = 0
zeroes = 0
count = 0
for i in a:
if i > big:
big = i
count = 1
elif i == big:
count += 1
if i > 0:
sum += i
if i == 0:
zeroes += 1
if big == 0:
print('0 %d' %(power(2, count) - 1))
elif big < 0:
print('%d %d' %(big, count % modulo))
else:
print('%d %d' %(sum, power(2, zeroes)))``````
Copy The Code &

Input

cmd
2
5
1 -1 1 -1 1
6
-200 -100 -100 -400 -232 -450

Output

cmd
3 1
-100 2