Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

VMGCDSUM - Tổng ước chung lớn nhất 2

Bé năm nay 16 tuổi, học hết lớp 10, giải toán bây giờ đã trở thành một phần không thể thiếu trong cuộc sống của Bé. Hàng ngày, Bé luôn mơ ước được ngắm nhìn những bài toán hóc búa, quyến rũ. Biết Bé đam mê giải toán, cô giáo vui lắm. Hôm nay cô cho Bé một bài toán:

Cho một số nguyên dương S. Bé cần tìm tất cả các cặp số (x, y) thỏa mãn bội chung nhỏ nhất của x và y là S. Do giá trị của S có thể rất lớn:

  • Số S sẽ được cho dưới dạng tích các thừa số nguyên tố và số mũ. Cụ thể hơn, nếu S = p1k1p2k2...pnkn với p1, p2, ..., pn là các số nguyên tố phân biệt thì các giá trị p1, p2, ..., pn và k1, k2, ..., kn sẽ được cho trước.
  • Thay vì liệt kê ra tất cả các cặp số (x, y) thỏa mãn, Bé chỉ cần tính tổng ước chung lớn nhất của các cặp số đó theo module 109 + 7. Lưu ý nếu x khác y, (x, y) và (y, x) là 2 cặp số khác nhau.

Input

  • Dòng 1 chứa số nguyên N là số lượng thừa số nguyên tố phân biệt của S.
  • Dòng thứ i trong số N dòng tiếp theo chứa 2 số nguyên pi ki, tương ứng với một thừa số nguyên tố và số mũ của nó.

Output

  • Một số nguyên duy nhất là kết quả của bài toán.

Giới hạn

  • 1 ≤ N ≤ 16
  • 1 ≤ pi, ki ≤ 109
  • Dữ liệu đảm bảo pi là các số nguyên tố phân biệt.
  • Subtask 1 (30%): S ≤ 1012
  • Subtask 2 (30%): S ≤ 1018
  • Subtask 3 (40%): Không có giới hạn về giá trị của S.
  • Thời gian chạy cho subtask 1 và 2 là 2s, subtask 3 là 4s.

Chấm bài

Bài của bạn sẽ được chấm trên thang điểm 100. Điểm mà bạn nhận được sẽ tương ứng với % test mà bạn giải đúng.

Trong quá trình thi, bài của bạn sẽ chỉ được chấm với 1 test ví dụ.

Khi vòng thi kết thúc, bài của bạn sẽ được chấm với bộ test đầy đủ.

Example

Input:

2
2 2
3 1

Output:

50

Giải thích

S = 22 x 3 = 12. Các cặp (x, y) thỏa mãn là (1, 12), (2, 12), (3, 4), (3, 12), (4, 3), (4, 6), (4, 12), (6, 4), (6, 12), (12, 1), (12, 2), (12, 3), (12, 4), (12, 6), (12, 12).


Được gửi lên bởi:VOJ Team
Ngày:2014-07-23
Thời gian chạy:2s-4s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:VM14

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.