Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

One Day Mr. Professor was taking His schedule class on Discrete Mathematics. In this lecture, He was talking about set theory.

Alice was very lazy and Inattentive in this class. Mr. Professor notices him and thinks How to punish him.

After finishing His class Mr. Professor Write Two Function on the blackboard and some description.

g(k) = sum of all subsets from a given set which has cardinality k.

F(S) = ∑g(d); where d is a divisor of the cardinality of the set S.

Example if S ={1,2,3,4}; Here cardinality of S is |S| = 4

F(S) = g(1) + g(2) + g(4);

g(1) = {1} + {2} + {3} + {4} = 1 + 2 + 3 + 4 = 10

g(2) = {1,2} + {1,3} + {1,4} + {2,3} + {2,4}+{3,4} = 3 + 4 + 5 + 5 + 6 + 7 = 30

g(4) = {1,2,3,4} = 10

F(S) = 10 + 30+ 10 = 50

Mr. Professor gives the task to Alice and to write a bug-free c++ or c code to solve the problem for a given set.

You know Alice is a good problem solver, so he asks Mr. Professor about the Constraints of the problem.

Then Mr. professor add Three more lines on the board,

1 <= |S| <= 106

-109 <= Si <= 109 , Si ∈ S\

As the value of F(S) will very Big so print only F(S) mod 999999937

The first line contains an integer T, number of test case.

The second line contains an integer N, size of the set S.

Next line contains N integers, elements of the set Si.

1≤ T ≤ 10

1 <= N, |S| <= 106

-109 ≤ Si ≤ 109, Si ∈ S

For each test case, print a single line containing one integer ― the value of F(S) mod 999999937.

Input | Output |
---|---|

1 4 1 2 3 4 | 50 |

64% Solution Ratio

abcdef123Earliest,

prodip_bsmrstuFastest, 0.0s

prodip_bsmrstuLightest, 8.0 MB

steinumShortest, 393B

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.