Giải bài trực tuyến

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 = p₁^k₁p₂^k₂...p_n^k_n với p₁, p₂, ..., p_n là các số nguyên tố phân biệt thì các giá trị p₁, p₂, ..., p_n và k₁, k₂, ..., k_n 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 10⁹ + 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 p_i và k_i, 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 ≤ p_i, k_i ≤ 10⁹
• Dữ liệu đảm bảo p_i là các số nguyên tố phân biệt.
• Subtask 1 (30%): S ≤ 10¹²
• Subtask 2 (30%): S ≤ 10¹⁸
• 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 = 2² 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).