Ноён Санта дэлхийн бүх шилдэг програмистуудаас нэгэн улиг болсон бодлогыг асуужээ.Санта тэдэнд $m$ бүхэл тоог өгөх ба тэднээс $n$-ын факториал нь яг $m$ ширхэг тэгээр төгссөн байх нийт хэчнээн ширхэг эерэг бүхэл $n$ тоо байгааг асуух юм.Та тэдгээр програмистуудын дунд байгаа бөгөөд тус бодлогыг та бодож чадах уу?

Оролт

Ганц мөрөнд факториалын төгсгөлд байх тэгийн тоог илэрхийлэх бүхэл тоо $m$ ($1 ≤ m ≤ 100 000$) өгөгдөнө.

Гаралт

Эхний мөрөнд $n$-ын факториал нь яг $m$ ширхэг тэгээр төгссөн байх $n$-үүдийн утгуудын тоог илэрхийлэх $k$ тоог хэвлэнэ.Дараа нь эдгээр $k$ утгуудыг өсөх дарааллаар хэвлэнэ.

$n$-ын факториал гэдэг нь $1$-ээс $n$ хүртэлх бүх бүхэл тоонуудын үржвэртэй тэнцүү бөгөөд өөрөөр хэлбэл $n! = 1*2*3*...*n$ байна.

Эхний жишээнд, $5! = 120$, $6! = 720$, $7! = 5040$, $8! = 40320$ мөн $9! = 362880$ байна.