product-divisors-6

Oz is in love with number theory, so he expects you to love it too and solve his problems. The current problem which has been given by Oz to you is in the form of an array. So, he has given you N integers i.e a1,a2,..,aN to deal with. You have to find the number of divisors of the product of all these integers. 

Input :
The first line contains a single integer N. The second line contains N space seperated integers - a1,a2,..,aN.

Output :
Output a single integer — number of divisors of the product of all these integers. Since the answer can be very large, output it modulo 1000000007(10^9+7).

Constraints :
1 ≤ N ≤ 10^3.
1 ≤ ai ≤ 10^6 where i=1, 2, 3 ... N

SAMPLE INPUT
2
2 3

SAMPLE OUTPUT
4

Explanation

The product is 6 and it has 4 factors:  1, 2, 3, 6

Source: hackerearth | Difficulty: EASY
Tags: Number theory


Solutions:
from sys import stdin

n = int(stdin.readline())
s = list(map(int,stdin.readline().split()))

dl = [dict() for x in range(1000001)]

ll = [x for x in range(1000001)]

for i in range(2,1000000):
	if ll[i]!= 1:
		j = i
		while(j<=1000000):
			###
			count = 0
			temp = ll[j]
			while(temp%i == 0):
				count = count + 1
				temp = temp/i
			if(count != 0):
				dl[j][i] = count
			ll[j] = temp
			j = j + i
dt = {}
m = 1000000007
for num in s:
	for key in dl[num]:
		if key in dt:
			dt[key] = (dt[key] + dl[num][key])%m
		else:
			dt[key] = dl[num][key]

res = 1

for key in dt:
	res = (res*(dt[key]+1))%m

print(res)
			
	


from math import sqrt	
A,Val,v=[1]*1000050,[0]*1000050,[2];
sq=int(sqrt(1000050));
for i in range(2,sq+1):
	if A[i]:
		for j in range(i*i,1000050,2*i):
			A[j]=0;

for i in range(3,1000050,2):
	if A[i]:	v.append(i);

N=eval(input());	Z=list(map(int,input().split()));
for n in Z:
	sq=int(sqrt(n));	i=0;
	while v[i]<=sq and n>1:
		ct=0;
		while n%v[i]==0:
			n/=v[i];	ct+=1;
		Val[v[i]]+=ct;
		i+=1;
	if n>1:	Val[n]+=1;
res=1;	s=len(v);
for i in range(s):	res=(res*(Val[v[i]]+1))%1000000007;
print(res);


def factor(n):
	r = {}
	q = 2
	w = int(n**.5)+1
	while n > 1 and q <= w:
		c = 0
		while n % q == 0: n /= q; c += 1
		if c: r[q] = c
		q += 1
	if n > 1: r[n] = 1  
	return r
 
def join(f, g):
	for k in g:
		if k in f:
			f[k] += g[k]
		else:
			f[k] = g[k]
l = eval(input())
s = list(map(int,input().split()))
f = {}
for q in s:
	g = factor(q)
	join(f, g)
p = 1
for d in list(f.values()):
	p = ((p)*(d + 1))%1000000007;
print(p)   


from collections import Counter
n=eval(input())
array=[int(i) for i in input().split()]
prod=1
for val in array:
	prod=prod*val



def primes(n):
    primfac = []
    d = 2
    while d*d <= n:
        while (n % d) == 0:
            primfac.append(d)  
            n //= d
        d += 1
    if n > 1:
       primfac.append(n)
    return primfac



temp=  Counter(primes(prod))
value=1

for val in list(temp.values()):
	value=value*(val+1)

print(value% (10**9+7))


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
from math import sqrt
N=int(input())
ip=[int(i) for i in input().strip().split()]
mdic={}
for i in ip:
	q=i
	try:
		mdic[i][0]+=1
		continue
	except:
		pass
	dic={}
	while not i%2:
		try:
			i/=2
			dic[2]+=1
		except:
			dic[2]=1
	x=3
	z=int(sqrt(i))
	if i!=1:
		while x<=z:
			if not i%x:
				break
			x+=2
		else:
			dic[i]=1
			mdic[q]=[1,dic]
			continue
			
	x=3
	while x<=i:
		while not i%x:
			try:
				i/=x
				dic[x]+=1
			except:
				dic[x]=1
		x+=2
	mdic[q]=[1,dic]
 
dic={}
for l in list(mdic.values()):
	for k,v in list(l[1].items()):
		try:
			dic[k]+=v*l[0]
		except:
			dic[k]=v*l[0]
t=1
for v in list(dic.values()):
	t*=(v+1)
print((t%1000000007))



from collections import Counter
n=eval(input())
array=[int(i) for i in input().split()]
prod=1
for val in array:
	prod=prod*val



def primes(n):
    primfac = []
    d = 2
    while d*d <= n:
        while (n % d) == 0:
            primfac.append(d)  # supposing you want multiple factors repeated
            n //= d
        d += 1
    if n > 1:
       primfac.append(n)
    return primfac



temp=  Counter(primes(prod))
value=1

for val in list(temp.values()):
	value=value*(val+1)

print(value% (10**9+7))


from math import *
n = int(input())
a = list(map(int,input().split()))
ans = {}
mod = 10**9+7
for v in a:
	for i in range(2,int(sqrt(v))+1):
		while (v%i==0):
			if not i in ans:
				ans[i]=0
			ans[i]+=1
			v=v/i
	if v>1:
		if not v in ans:
			ans[v]=0;
		ans[v]+=1
res = 1
for key in ans:
	res*=(ans[key]+1)
print(res%mod)


#Read Inputs

def find_number_of_divisor(n,arr,modulo):
	counter={}
	for i in range(n):
		number = arr[i]
		factor=2
		while factor*factor<=number:
			while number%factor ==0:
				if factor in counter:
					counter[factor] +=1
				else:
					counter[factor]=1
				number = number/factor
			factor +=1
		if number>1:
			if number in counter:
				counter[number] +=1
			else:
				counter[number] =1
	answer =1
	for i in counter:
		answer *= (counter[i]+1)
	print(answer%modulo)
	
n = eval(input())
arr = list(map(int,input().split()))
modulo = 10**9 + 7
find_number_of_divisor(n,arr,modulo)
	


mod = 1000000007
length = int(input())
arr = list(map(int, input().split()))
dict1 = dict()
for num in arr:
	i = 2
	while i*i <= num:
		while num % i == 0:
			dict1[i] = dict1.get(i, 0) + 1
			num /= i
		i += 1
	if num > 1:
		dict1[num] = dict1.get(num, 0) + 1
res = 1
for key, val in list(dict1.items()):
	res = (res %mod * (val + 1)%mod)%mod
print(res) 


mod = 1000000007
length = int(input())
arr = list(map(int, input().split()))
dict1 = dict()
for num in arr:
	i = 2
	while i*i <= num:
		while num % i == 0:
			dict1[i] = dict1.get(i, 0) + 1
			num /= i
		i += 1
	if num > 1:
		dict1[num] = dict1.get(num, 0) + 1
res = 1
for key, val in list(dict1.items()):
	res = (res %mod * (val + 1)%mod)%mod
print(res) 


from collections import Counter

def primes_sieve(limit):
	limitn = limit+1
	not_prime = set()
	primes = []

	for i in range(2, limitn):
		if i in not_prime:
			continue

		for f in range(i*2, limitn, i):
			not_prime.add(f)

		primes.append(i)

	return primes

SEIVE = primes_sieve(10**6) # seive upto max
MODULO = 1000000007
def sum_of_factors(counter):
	sum = 1
	for num, count in counter.items():
		sum = pow(sum * (count + 1), 1, MODULO)
	return sum

def factorize(n):
	pos = 0
	prime_factors = []
	while n != 1:
		d = SEIVE[pos]
		while (n % d) == 0:
			prime_factors.append(d)
			n //= d
		pos += 1
	return Counter(prime_factors)


_ = int(input()) # do not care about length
a = list(map(int, str(input()).split(" ")))
# a = [i for i in range(10000, 12000)]
factors = Counter()
for num in a:
	factors += factorize(num)

print(sum_of_factors(dict(factors)))


import sys

MOD = 1000000007

n = int(sys.stdin.readline())

ar = list(map(int, sys.stdin.readline().split(' ')))

factors = dict()
factors[2] = 0
factors[3] = 0
largest_prime_till_now = 3

def factorize(n, factors, largest_prime_till_now):
	for factor in factors.keys():
		while n%factor == 0 and n!=1:
			factors[factor] += 1
			factors[factor] %= MOD
			n /= factor

	while n!=1:
		largest_prime_till_now += 2
		while n%largest_prime_till_now == 0 and n!=1:
			if largest_prime_till_now in factors:
				factors[largest_prime_till_now] += 1
			else:
				factors[largest_prime_till_now] = 1
			factors[largest_prime_till_now] %= MOD
			n /= largest_prime_till_now

result = 1
found_zero = False
for i in ar:
	if i == 0:
		found_zero = True

if not found_zero:
	for i in ar:
		factorize(i, factors, largest_prime_till_now)
	if factors[2] == 0:
		factors.pop(2)
	if factors[3] == 0:
		factors.pop(3)
	for i in list(factors.keys()):
		result = result*(factors[i]+1)
		result %= MOD

print(result)


import os
import sys

N = int(input())
l = input().strip()
l = l.split(' ')
arr = [int(x) for x in l]
facts = [[] for x in range(0,1000001)]
isprime = [True for x in range(0,1000001)]
for x in range(2,1000001) :
	if isprime[x] :
		facts[x].append(x)
		j = 2*x
		while j < 1000001 :
			isprime[j] = False
			facts[j].append(x)
			j += x
#print facts[:20]
powcnt = dict()
for x in arr :
	for y in facts[x] :
		cnt = 0;
		k = x
		while k>1 and k%y==0 :
			k = k/y
			cnt+=1
		if y in powcnt :
			powcnt[y] = powcnt[y]+cnt
		else :
			powcnt[y] = cnt

divs = 1
for k,v in powcnt.items() :
	divs = (divs*(v+1))%1000000007

print(divs)



		


import math
prime_freq = {}
MOD = 1000000007
def prime_factors(n):
	while(n%2==0):
		prime_freq[2] = prime_freq.get(2,0) + 1
		n = n/2
	for i in range(3,int(math.sqrt(n))+1,2):
		while(n%i==0) :
			prime_freq[i] = prime_freq.get(i,0) + 1
			n = n/i
	if n >2:
		prime_freq[n] = prime_freq.get(n,0) + 1

N = int(input())
numbers = list(map(int,input().strip().split()))

for num in numbers:
	prime_factors(num)

ans = 1
for value in list(prime_freq.values()):
	ans = (ans * (value+1)) % MOD

print(ans % MOD)



MOD = 10**9 + 7


def prime(num):
    
	for j in range(2, int(num**(1.0/2))+1):
		if num%i:
			return False
	return True
		
def prime_factors(number):
	
	gg = number
	cnt = 1
	for j in range(2,int(gg**(1.0/2))+1):
		while (gg % j == 0):
				try:
					uniq_primes[j]+=1
				except:
					uniq_primes[j]=1
				gg /= j;
	if gg > 1:
		try:
			uniq_primes[gg]+=1
		except:
			uniq_primes[gg]=1


n = eval(input())
uniq_primes = {}
a = list(map(int, input().split()))

tot = 1
for num in a:
	prime_factors(num)
for ke, val in list(uniq_primes.items()):
	tot*=((val+1)%MOD)
print(tot%MOD)


import copy
prime = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107,
	109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
	233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359,
	367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491,
	499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641,
	643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787,
	797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941,
	947, 953, 967, 971, 977, 983, 991, 997]
count = {}
N = int(input())
A = list(map(int, input().strip().split(' ')))
res = 1
for i in prime:
    count[i] = 0
for j in A:
    c=copy.copy(j)
    for i in prime:
        if c % i == 0:
	   temp = 1
	   while c % i == 0:
	       c=c/i
	       temp += 1
	   count[i] += temp-1
    if c>1000:
        prime.append(c)
        count[c]=1
for i in prime:
    if count[i]:
        res *= (count[i]+1)
print(res % 1000000007)


MAXI = 1000010
def get_prime():
	prime_list = [True]*MAXI
	prime_list[0] = prime_list[1] = False
	for i in range(0, 1010):
		if prime_list[i]:
		    # print i
		    for val in range(i*i, MAXI, i):
			prime_list[val] = False
	#print len(prime_list)
	return prime_list

N = int(input())
arr = list(map(int, input().split()))
prime_list = [idx for idx, val in enumerate(get_prime()) if val]
sz = len(prime_list)
#print sz, prime_list
power = {val:0 for val in prime_list}
#print {1:2}
MOD = 1000000007
for val in arr:
	for idx, prime in enumerate(prime_list):
		if prime > val:
			break
		
		while val > 1 and val%prime == 0:
			#print prime, power[prime]
			power[prime] += 1
			val /= prime
	if val > 1:
	    	power[val] += 1

ans = 1
#print power
for val, p in list(power.items()):
	ans *= (p+1)
	ans %= MOD
print(ans)
		


from collections import Counter
n=eval(input())
array=[int(i) for i in input().split()]
prod=1
for val in array:
	prod=prod*val



def primes(n):
    primfac = []
    d = 2
    while d*d <= n:
        while (n % d) == 0:
            primfac.append(d)  
            n //= d
        d += 1
    if n > 1:
       primfac.append(n)
    return primfac



temp=  Counter(primes(prod))
value=1

for val in list(temp.values()):
	value=value*(val+1)

print(value% (10**9+7))


import operator
from functools import reduce

def PrimesPlus():
	yield 2
	yield 3
	i = 5
	while i!=1000001:
		yield i
		if i % 6 == 1:
			i += 2
		i += 2


def GetPrimeDecomp(n):
	d = {}
	primes = PrimesPlus()
	for p in primes:
		while n % p == 0:
			n /= p
			d[p] = d.setdefault(p, 0) + 1
		if n == 1:
			return d

def NumberOfDivisors(n):
	d = GetPrimeDecomp(n)
	powers_plus = [x+1 for x in list(d.values())]
	return reduce(operator.mul, powers_plus, 1)




n = input()
numbers = list(map(int, input().split()))
s=1
for x in numbers:
	s = s*x
	
	
print(NumberOfDivisors(s)%1000000007)




'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
from math import sqrt
N=int(input())
ip=[int(i) for i in input().strip().split()]
mdic={}
for i in ip:
	q=i
	try:
		mdic[i][0]+=1
		continue
	except:
		pass
	dic={}
	while not i%2:
		try:
			i/=2
			dic[2]+=1
		except:
			dic[2]=1
	x=3
	z=int(sqrt(i))
	if i!=1:
		while x<=z:
			if not i%x:
				break
			x+=2
		else:
			dic[i]=1
			mdic[q]=[1,dic]
			continue
			
	x=3
	while x<=i:
		while not i%x:
			try:
				i/=x
				dic[x]+=1
			except:
				dic[x]=1
		x+=2
	mdic[q]=[1,dic]

dic={}
for l in list(mdic.values()):
	for k,v in list(l[1].items()):
		try:
			dic[k]+=v*l[0]
		except:
			dic[k]=v*l[0]
t=1
for v in list(dic.values()):
	t*=(v+1)
print((t%1000000007))


n = int(input())
A = list(map(int, input().split(' ')))

primes = [1] * 1000002
for i in range(2, len(primes)):
	j = 2
	while i*j < len(primes):
		primes[i*j] = 0
		j += 1

primes = [i for i in range(len(primes)) if primes[i] == 1][2:]
# print primes

factors = [1] * 1000002

for num in A:
	if num != 0:
		index = 0
		while num != 1:
			div = primes[index]
			while num % div == 0:
				factors[div] += 1
				num /= div
			index += 1

ans = 1
for num in factors:
	ans = (ans * num) % 1000000007

print(ans)