e-olymp
Змагання

Azerbaijan Programming Olympiad - 2nd Stage preparation

Урок математики

На початку кожного уроку вчителька математики Гузель Закіївна пише на дошці натуральне число n. Доки йде урок школярі намагаються знайти якомога більше простих дільників цього числа. В кінці уроку щедра Гузель Закіївна роздає цукерку всім тим, хто знайшов максимальну кількусть простих дільників. Школяр Вася обожнює солодке і просить вас забезпечити йому цукерку від Гузель Закіївни сьогодні. За заданим числом n потрібно вивести всі його прості дільники в степені, у якому вони зустрічаються у заданому числі.

Вхідні дані

Єдине натуральне число n109.

Вихідні дані

Виведіть усі прості дільники числа у порядку зростання і вкажіть для кожного дільника степінь, у якій він зустрічається в числі n, якщо його степінь більше одиниці. Формат виведення повинен відповідати прикладу.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
3240
Вихідні дані #1
2^3*3^4*5
Джерело ЛКШ 2009