#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
vector < pair <unsigned, unsigned> > dividers(unsigned n)
{
vector < pair <unsigned, unsigned> > res;
if (n <= 1)
res.push_back(make_pair(n, 1));
for (unsigned q=2; q*q<=n; ++q)
{
if (n % q == 0)
{
unsigned d;
for (d=0; !(n%q); ++d) n/=q;
res.push_back(make_pair(q, d));
}
}
if (n > 1)
res.push_back(make_pair(n, 1));
return res;
}
string fragment(const pair <unsigned, unsigned> &p)
{
char res[256];
sprintf(res, p.second==1 ? "%d" : "%d^%d", p.first, p.second);
return res;
}
void print(const vector < pair <unsigned, unsigned> > &v)
{
transform(v.begin(), --v.end(), ostream_iterator<string>(cout, " * "), fragment);
cout << fragment(*v.rbegin()) << endl;
}
int main()
{
print(dividers(126));
print(dividers(1));
print(dividers(17));
print(dividers(128));
print(dividers(0));
print(dividers(121));
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8aXRlcmF0b3I+CiNpbmNsdWRlIDx2ZWN0b3I+CiNpbmNsdWRlIDxhbGdvcml0aG0+CiNpbmNsdWRlIDxzdHJpbmc+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKdmVjdG9yIDwgcGFpciA8dW5zaWduZWQsIHVuc2lnbmVkPiA+IGRpdmlkZXJzKHVuc2lnbmVkIG4pCnsKICB2ZWN0b3IgPCBwYWlyIDx1bnNpZ25lZCwgdW5zaWduZWQ+ID4gcmVzOwogIAogIGlmIChuIDw9IDEpCiAgICByZXMucHVzaF9iYWNrKG1ha2VfcGFpcihuLCAxKSk7CiAgCiAgZm9yICh1bnNpZ25lZCBxPTI7IHEqcTw9bjsgKytxKQogIHsKICAgIGlmIChuICUgcSA9PSAwKQogICAgewogICAgICB1bnNpZ25lZCBkOwogICAgICBmb3IgKGQ9MDsgIShuJXEpOyArK2QpIG4vPXE7CiAgICAgIHJlcy5wdXNoX2JhY2sobWFrZV9wYWlyKHEsIGQpKTsKICAgIH0KICB9CiAgCiAgaWYgKG4gPiAxKQogICAgcmVzLnB1c2hfYmFjayhtYWtlX3BhaXIobiwgMSkpOwoJCiAgcmV0dXJuIHJlczsKfQoKc3RyaW5nIGZyYWdtZW50KGNvbnN0IHBhaXIgPHVuc2lnbmVkLCB1bnNpZ25lZD4gJnApCnsKICBjaGFyIHJlc1syNTZdOwogIHNwcmludGYocmVzLCBwLnNlY29uZD09MSA/ICIlZCIgOiAiJWReJWQiLCBwLmZpcnN0LCBwLnNlY29uZCk7CiAgcmV0dXJuIHJlczsKfQoKdm9pZCBwcmludChjb25zdCB2ZWN0b3IgPCBwYWlyIDx1bnNpZ25lZCwgdW5zaWduZWQ+ID4gJnYpCnsKICB0cmFuc2Zvcm0odi5iZWdpbigpLCAtLXYuZW5kKCksIG9zdHJlYW1faXRlcmF0b3I8c3RyaW5nPihjb3V0LCAiICogIiksIGZyYWdtZW50KTsKICBjb3V0IDw8IGZyYWdtZW50KCp2LnJiZWdpbigpKSA8PCBlbmRsOwp9CgppbnQgbWFpbigpCnsKICBwcmludChkaXZpZGVycygxMjYpKTsKICBwcmludChkaXZpZGVycygxKSk7CiAgcHJpbnQoZGl2aWRlcnMoMTcpKTsKICBwcmludChkaXZpZGVycygxMjgpKTsKICBwcmludChkaXZpZGVycygwKSk7CiAgcHJpbnQoZGl2aWRlcnMoMTIxKSk7CiAgCiAgcmV0dXJuIDA7Cn0=