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_{1}}^{k_1} {p_{2}}^{k_2}~ ...~{p_{n}}^{k_n}~ với ~p_{1}~, ~p_{2}~, ..., ~p_{n}~ là các số nguyên tố phân biệt thì các giá trị ~p_{1}~, ~p_{2}~, ..., ~p_{n}~ và ~k_{1}~, ~k_{2}~, ..., ~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^{9}~ + ~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 \leq N \leq 16~
• ~1 \leq p_{i}~, ~k_{i} \leq 10^{9}~
• Dữ liệu đảm bảo ~p_{i}~ là các số nguyên tố phân biệt.
• Subtask ~1~ (30%): ~S \leq 10^{12}~
• Subtask ~2~ (30%): ~S \leq 10^{18}~
• Subtask ~3~ (40%): Không có giới hạn về giá trị của ~S~.

Sample Input

2
2 2
3 1

Sample Output

50

Note

S = ~2^{2} \times 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~).