Напишете програма која од стандарден влез ќе прочита еден природен број N, и на стандарден излез ќе ја испечати факторизацијата на тој број.

Под факторизација на природен број се подразбира неговото претставување како производ од прости фактори (прост број на степен). Прост број е природен број кој има точно два делители (1 и самиот тој број). Првите неколку прости броеви се 2, 3, 5, 7, 11, 13, 17, итн...

Влез

Од стандарден влез се чита еден цел број N (2 <= N <= 100000).

Излез

На стандарден излез отпечатете ја факторизацијата на бројот N. Простите фактори се печатат во загради како број на (^) степен, а се одделени со знакот за множење (*).

Факторите треба да се подредени од оној фактор со најмала основа, кон оние со поголема основа. Не смее да има знак * на крајот на излезот. Видете го тест-случајот даден подолу за конкретен пример...

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
1176

излез
(2^3)*(3^1)*(7^2)