A kód

Miután sikeresen meghatároztuk, hogy a zár feltörhető, itt az idő, hogy bejussunk az épületbe. Ehhez azonban be is kell írnunk a kódot a számzáras ajtóba!

Input

A bemenet egyetlen, sor vége jellel lezárt sor, mely egyetlen pozitív egész n számot tartalmaz, mely legfeljebb 4000.

Output

A kimenet n! (n faktoriális) prímtényezős felbontása prímek szerinti növekvő sorrendben az alábbiak szerint:

• Amennyiben egy prím a nulladik hatványon szerepel úgy azt nem írjuk ki.
• Ha egy prím az első hatványon szerepel akkor a prímet egyszerűen számként írjuk ki.
• Ha egy prím legalább második hatványon szerepel akkor azt p^k alakban szerepeltetjük, ahol p a prím, k pedig, hogy hanyadik hatványon szerepel.
• Az egyes tagok között egy szóköz, majd egy szorzásjel, majd egy újabb szóköz szerepel.

Példa