Given an integer, your task is to find the number, sum and product of its divisors. As an example, let us consider the number 12:

• the number of divisors is 6 (they are 1, 2, 3, 4, 6, 12)
• the sum of divisors is 1+2+3+4+6+12=28
• the product of divisors is 1 \cdot 2 \cdot 3 \cdot 4 \cdot 6 \cdot 12 = 1728

Since the input number may be large, it is given as a prime factorization.

Input

The first line has an integer n: the number of parts in the prime factorization.

After this, there are n lines that describe the factorization. Each line has two numbers x and k where x is a prime and k is its power.

Output

Print three integers modulo 10^9+7: the number, sum and product of the divisors.

Constraints

• 1 \le n \le 10^5
• 2 \le x \le 10^6
• each x is a distinct prime
• 1 \le k \le 10^9

Example

Input:

2
2 2
3 1

Output:

6 28 1728