holdmesoclose cho CaiWinDao biết một số nguyên dương \(t\) và nhờ cậu ấy tính số lượng ước số, tổng các ước số và tích các ước số của số \(t\) này. Ví dụ, với \(t=12\) thì:

• Số lượng ước số của \(t\) là \(6\) (\(1\), \(2\), \(3\), \(4\), \(6\), \(12\)).
• Tổng các ước số của \(t\) là \(1+2+3+4+6+12=28\).
• Tích các ước số của \(t\) là \(1.2.3.4.6.12=1728\).

Vì input có thể rất lớn nên holdmesoclose chỉ cho CaiWinDao biết số \(t\) dưới dạng tích của các thừa số nguyên tố.

Input

Dòng đầu chứa số nguyên dương \(n\): số lượng thừa số nguyên tố của \(t\).

Mỗi dòng trong \(n\) dòng tiếp theo chứa hai số nguyên dương \(x\) và \(k\) lần lượt mô tả một thừa số của \(t\) và bậc tương ứng của nó.

Output

Gồm ba kết quả cần tìm sau khi chia lấy dư cho \(10^9+7\).

Ví dụ

Input

2
2 2
3 1

Output

6 28 1728

Ràng buộc

• \(1\leq n\leq 10^5\).
• \(2\leq x\leq 10^6\) và \(x\) là số nguyên tố.
• \(1\leq k\leq 10^9\).