#5349. Divisors (Mã bài: DIVISORS)

Cho số nguyên . Mỗi số được đảm bảo có từ 3 đến 5 ước số.

Xét tích . Hãy tìm số lượng ước của . Vì kết quả có thể rất lớn, hãy in ra theo modulo .

Dữ liệu:

• Dòng đầu tiên chứa một số nguyên () — là số lượng các số.
• dòng tiếp theo, mỗi dòng chứa một số nguyên (). Đề bài đảm bảo rằng số ước của mỗi là từ 3 đến 5.

Kết quả: In ra một số nguyên duy nhất — là số lượng ước của tích theo modulo .

Ví dụ:

Dữ liệu:

3
9
15
143

Kết quả:

32

Dữ liệu:

1
7400840699802997

Kết quả:

4

Dữ liệu:

8
4606061759128693
4606066102679989
4606069767552943
4606063116488033
4606063930903637
4606064745319241
4606063930904021
460606559735517

Kết quả:

1920

Dữ liệu:

3
4
8
16

Kết quả:

10

Giải thích:

• Trường hợp 1: , các số là .

  • Tích .
  • Số lượng ước là .

• Trường hợp 2: , số là . Số này có 4 ước. Điều này gợi ý nó là tích của hai số nguyên tố khác nhau () hoặc là lập phương của một số nguyên tố (). Trong trường hợp này, nó có 4 ước là , , , và chính nó.

• Trường hợp 4: , các số là .

  • Tích .
  • Số lượng ước của là .

Giới hạn: