Дано ціле число, ваше завдання — знайти число, суму та добуток його дільників. Для прикладу розглянемо число 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