Дано ціле число, ваше завдання — знайти число, суму та добуток його дільників. Для прикладу розглянемо число 12:

• кількість дільників 6 (вони 1, 2, 3, 4, 6, 12)
• сума дільників 1+2+3+4+6+12=28
• добуток дільників дорівнює 1⋅2⋅3⋅4⋅6⋅12=1728

Оскільки введене число може бути великим, воно подано як розклад на прості множники.

Вхідні дані

У першому рядку міститься ціле число \(n\) : кількість частин у розкладі на прості множники.

Після цього є \(n\) рядків, які описують факторізацію. У кожному рядку є два числа \(x\) і \(k\), де \(x\) — просте число, а \(k\) — його степінь.

Вихідні дані

Вивести три цілі числа за модулем \(10^9+7\) : число, суму та добуток дільників.

Обмеження

• \(1≤n≤10^5\)
• \(2≤x≤10^6\)
• кожен \(x\) є окремим простим числом
• \(1≤k≤10^9\)

Приклад вхідних даних

2
2 2
3 1

Приклад вихідних даних

6 28 1728