Tích các ước

Xem PDF
Tác giả:
PhanDinhKhoi
Dạng bài
Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 1023M Input: bàn phím Output: màn hình

Cho 1 số nguyên dương \(n\) là tích của \(m\) số nguyên tố (\(m\) số nguyên tố này không nhất thiết phải khác nhau). Ta có \(n=p_1 \times p_2 \times ... \times p_m\).

Yêu cầu: Hãy tìm tích các ước của n.

Input

  • Dòng đầu tiên chứa số nguyên dương \(m\) \((m \leq 200000)\).
  • Dòng tiếp theo gồm \(m\) số nguyên tố \((2 \leq p_i \leq 200000, ∀ i:1 \leq i \leq m)\).

Output

  • Phần dư của tích các ước của số \(n\) khi chia cho \(10^9+7\).

Example

Test 1

Input 
2
2 3
Output 
36
Note
  • \(n = 2 \times 3 = 6\). Các ước của n là \(1, 2, 3, 6\). Tích của của chúng là \(1 \times 2 \times 3 \times 6=36\).

Test 2

Input 
3
2 3 2
Output 
1728
Note
  • \(n = 2 \times 3 \times 2 = 12\). Các ước của n là \(1, 2, 3, 4, 6, 12\). Tích của chúng là \(1 \times 2 \times 3 \times 4 \times 6 \times 12=1728\).

Bình luận