Cho một số nguyên, nhiệm vụ của bạn là tìm số lượng, tổng và tích của các ước số của nó. Ví dụ, chúng ta hãy xem xét số \(12\):

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

Vì số đầu vào có thể rất lớn, nó sẽ được cho dưới dạng phân tích thừa số nguyên tố.

Input

• Dòng đầu tiên có một số nguyên \(n\): số phần trong dạng phân tích thừa số nguyên tố
• Sau đó, gồm \(n\) dòng mô tả dạng phân tích. Mỗi dòng có hai số \(x\) và \(k\), trong đó \(x\) là số nguyên tố và \(k\) là lũy thừa của nó

Constraints

• \(1 \leq n \leq 10^5\)
• \(2 \leq x \leq 10^6\)
• Mỗi \(x\) là một số nguyên tố riêng biệt
• \(1 \leq k \leq 10^9\)

Output

• In ba số nguyên chia lấy dư cho \(10^9 + 7\): số lượng, tổng và tích của các ước số

Example

2
2 2
3 1

6 28 1728