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

hide comments
kshubham02: 2018-12-15 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, non-empty) of the array. As many subsets can give the same maximum sum, also output the number of distinct such subsets.
Two subsets are defined to be distinct if there exists an element which is present in one of the subsets but not in the other.

sas1905: 2017-07-06 06:59:12

1000,000,009 NOT 1000,000,007!! 1 WA :(

coolio_1: 2017-06-24 14:41:35

One Word!!! Modular exponentiation!! ( okay 2 words :-D)

shubham: 2017-06-08 11:07:11

Last edit: 2017-06-08 12:15:38
geoffreymace7: 2017-05-31 17:40:57

Don't apply modulo operation on the sum of maximum subset.

swatantragupta: 2016-12-25 11:26:53

language is confusing..comments helped:)

Wumbolo: 2016-07-20 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: 2016-04-21 22:30:03

"output the value of the maximum subset and the count of the subsets modulo 1000,000,009"

--_--

ROHIT Kumar: 2015-08-12 19:00:47

used modular expo....nice question...2 hr of brain sucking finally got ac

rk: 2015-06-29 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:2011-03-07
Time limit:0.507s-2.450s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64