All Tracks Math Number Theory Problem

Monk and Number
Tag(s):

Math, Medium, approved

Problem
Editorial
Analytics

Problems never seem to end for Mike and Monk, and this time they need to deal with a really old foe of theirs i.e Charles Forstman. Forstman is a rich rich man, and is rather extremely good with numbers. This might not be the case with Mike and Monk thus, to get the better of them, Forstman gives them the following task :

You have been given an integer $$K$$ expressed as the product of $$N$$ integers $$A[1],A[2],A[3]...A[N]$$. In short, $$K=\prod_{i=1}^{N} (A[i]) $$.

Now, we define $$2$$ functions :

$$ F(x) $$ = $$ \sum_{d|x} \space G(d) $$

$$ G(x) $$ = $$ \sum_{d|x} \space d $$

$$ d | x $$ denotes all integers $$d$$, that divide $$x$$ evenly.

Given the array $$A$$, you need to find $$F(K)$$. As the answer can be rather large find it Modulo $$10^9+7$$. Can you help Monk ?

Input Format :

The first line contains a single integer $$T$$ denoting the number of test cases in a single input file. Each test case consists of $$2$$ lines, and is as follows :

The first line of each test case consists of a single integer $$N$$ denoting the size of array $$A$$. The next line consists of $$N$$ space separated integers, where the $$i^{th}$$ integer denotes $$A[i]$$.

Output Format :

For each test case, print the required answer on a new line. As the may be rather large, print it Modulo $$10^9+7$$.

Constraints :

$$ 1 \le T \le 5 $$

$$ 1 \le N \le 500 $$

$$ 2 \le A[i] \le 10^9 $$, where $$ 1 \le i \le N $$

Subtasks :

For 20% of the points :

$$ 1 \le N \le 5 $$

$$ 1 \le A[i] \le 100 $$

For 100% of the points :

Original constraints

SAMPLE INPUT
1
4
3 3 2 3
SAMPLE OUTPUT
232
Explanation

$$ 3 \times 3 \times 2 \times 3 $$ = $$54$$. The divisors of $$54$$ are :

  1. $$1$$. $$G(1)$$ = $$1$$

  2. $$2$$. $$G(2)$$ = $$3$$

  3. $$3$$. $$G(3)$$ = $$4$$

  4. $$6$$. $$G(6)$$ = $$12$$.

  5. $$9$$. $$G(9)$$ = $$13$$

  6. $$18$$. $$G(18)$$ = $$39$$

  7. $$27$$. $$G(27)$$ =$$40$$

  8. $$54$$. $$G(54)$$ = $$120$$

Thus , $$F(54)$$ = $$G(1)+G(2)+G(3)+G(6)+G(9)+G(18)+G(27)+G(54)$$= $$1+3+4+12+13+39+40+120$$ = $$232$$

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic, Kotlin

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

CodeMonk (Checkpoint - I)

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications