Cho một số nguyên dương ~m~, nhiệm vụ của bạn là tìm số lượng ước, tổng các ước và tích các ước của nó.

Vì ~m~ có thể rất lớn nên nó được cho dưới dạng phân tích thừa số nguyên tố:

~m = p_1^{x_1} \cdot p_2^{x_2} \cdot \ldots \cdot p_n^{x_n}~

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên dương ~n~.
• ~n~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~p~ và ~x~ — một số nguyên tố và số mũ của nó. Các số nguyên tố ~p~ đôi một khác nhau.

Kết quả

In ra ba số nguyên đã chia dư cho ~10^9 + 7~: số lượng ước, tổng các ước và tích các ước của ~m~.

Ví dụ

Đầu vào:

2
2 1
3 2

Đầu ra:

6 39 5832

Giải thích: Test mẫu chính là phân tích của ~m = 2^1 \cdot 3^2 = 18~.

• Các ước của ~18~ là ~1, 2, 3, 6, 9, 18~ — có ~6~ ước.
• Tổng các ước là ~1 + 2 + 3 + 6 + 9 + 18 = 39~.
• Tích các ước là ~1 \cdot 2 \cdot 3 \cdot 6 \cdot 9 \cdot 18 = 5832~.

Giới hạn

• ~1 \le n \le 10^5~
• ~2 \le p \le 10^6~, các ~p~ đôi một khác nhau
• ~1 \le x \le 10^9~