Hello ! I have a problem that goes :

Given $$$N$$$ positive integers $$$A_1, A_2, \dots, A_N$$$. Find $$$LCM(A_1, A_2, \dots, A_N)\text{ }(\text{mod } 1000000007)$$$.

Constraint : $$$1\leq N \leq 10^4,$$$ $$$1\leq A_i \leq 10^9$$$

My approach :

Use sieve to list all primes up to $$$M = \sqrt{A_{max}}$$$. For every prime $$$p$$$ up to $$$M$$$, divide each $$$A_i$$$ by $$$p$$$ as many time as possible (as long as $$$A_i$$$ is divisible by $$$p$$$), and note the largest exponent for each $$$p$$$.

After every $$$A_i$$$ is 'reduced' (divided by all prime up to $$$M$$$), $$$A_i$$$ must be equal to $$$1$$$ or a prime greater than $$$M$$$. Note every distinct final result of $$$A_i$$$. This was done using std::set.

To calculate $$$LCM(A_1, A_2, \dots, A_N)$$$, I used binary exponentiation to calculate the 'contribution' for every small prime $$$p \leq M$$$, and then multiply them with the 'contribution' for large prime, which is equal to the product of all distinct final result of $$$A_i$$$ 's.

However, this approach yields TLE and I cannot figure out a faster way to solve the problem. Any ideas to solve the problem and explanations are appreciated. Thanks in advance.

This problem is from simulation phase of a contest I joined. Both the simulation and the contest itself was over by September 25th, 2021.