Đếm ước của một số nguyên dương

Mô tả

Cho phân tích thừa số nguyên tố của một số nguyên dương N, hãy đếm số lượng ước số của số nguyên dương đó.

Ví dụ: N = 60 = 2^2 3^1 5^1

Input Format

• Dòng đầu tiên là T : số lượng thừa số nguyên tố khác nhau của N
• T dòng tiếp theo, mỗi dòng gồm 2 số nguyên p và e:
  • p: thừa số nguyên tố
  • e: số mũ tương ứng

Constraints

• 1 ≤ T ≤ 100
• 2 ≤ p ≤ 100000
• 1 ≤ e ≤ 100000

Output Format

In ra số lượng ước số của N, vì kết quả quá lớn, hãy lấy dư với số 1000000007 (1e9 + 7)

Sample

Input

2
2 2
3 1

Output

6