SP8495 MAXSUB - Maximum Subset of Array

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.

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.

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 ```