Một hôm đang ngồi học Toán, Bờm cảm thấy đau đầu nên ngồi thư giản bằng cách cứ nhớ đến số nguyên tố nào thì Bờm ghi số đó ra giấy. Một lúc sau, khi nhìn lại thì Bờm đã ghi ra một dãy gồm N số A1, A2, …, An. Bờm chợt nghỉ ra một bài toán mới đó là Bờm tính số M bằng tích các số trong dãy A, sau đó Bờm lại tính tích của các ước của M.

Bạn hãy giúp Bờm giải bài tập này.

Input

• Dòng đầu ghi số nguyên dương N (1≤N≤2.10^5)

• Dòng tiếp theo ghi N số A1, A2, …, An (2≤Ai≤2.10^5)

Output

• Gồm một dòng ghi một số là tích của các ước của M. Vì tích này có thể rất lớn nên chỉ cần ghi ra phần dư của tích khi chia cho 10^9+7

Sample Input

2
2 3

Sample Output

36