MAXSUB  Maximum Subset of Array
Given an array find the sum of the maximum nonempty 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 nonempty 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 Tcases exist.
Each case starts with a line containing an integer n which is the number of elements in the array.
The next line contains nintegers 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
hide comments
kshubham02:
20181215 18:10:17
Problem statement is ambiguous, so here is some clarification : you need to find the maximum possible sum using a subset(not necessarily contiguous, nonempty) of the array. As many subsets can give the same maximum sum, also output the number of distinct such subsets.


sas1905:
20170706 06:59:12
1000,000,009 NOT 1000,000,007!! 1 WA :( 

coolio_1:
20170624 14:41:35
One Word!!! Modular exponentiation!! ( okay 2 words :D)


shubham:
20170608 11:07:11
Last edit: 20170608 12:15:38 

geoffreymace7:
20170531 17:40:57
Don't apply modulo operation on the sum of maximum subset. 

swatantragupta:
20161225 11:26:53
language is confusing..comments helped:) 

Wumbolo:
20160720 09:58:56
I don't like this problem, also the comments spoiled it. I didn't understand the problem at all so I looked in the comments. 

Dushyant Singh:
20160421 22:30:03
"output the value of the maximum subset and the count of the subsets modulo 1000,000,009"


ROHIT Kumar:
20150812 19:00:47
used modular expo....nice question...2 hr of brain sucking finally got ac 

rk:
20150629 11:52:22
what m i going to state now is really funny despite of taking mod 10^9+9 i took mod with 10^9+7 which was present in my template before hand ,lol be aware of this :) and Nice question by the way

Added by:  .:: Pratik ::. 
Date:  20110307 
Time limit:  0.507s2.450s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 