Чамд $a_{1}, a_{2}, ... a_{n}$ гэсэн бүхэл тоонуудын үржвэр болох $m$ өгөгджээ. $(m = \prod\limits_{i=1}^{n} a_{i})$

Чиний даалгавар бол $m$ тоог $n$ ширхэг эрэмбэлэгдсэн (өсөхөөр эсвэл буурахаар) бүхэл тоонуудын үржвэрт хэдэн янзаар задалж болохыг олох юм.

Өгөгдөлд буй $n$ ширхэг тоонуудаар үүссэн задрал нь мөн тоологдоно. Хариу хэт том тоо байж болох тул $1000000007$ $(10^{9} + 7)$ тоонд хуваан үлдэгдлийг нь олно уу.

Оролт

Эхний мөрөнд $n$ ($1 ≤ n ≤ 500$) гэсэн бүхэл тоо байна. Хоёрдахь мөрөнд $a_{1}, a_{2}, ..., a_{n}$ ($1 ≤ a_{i} ≤ 10^{9}$) бүхэл тоонууд зайгаар тусгаарлагдан байна.

Гаралт

$m$ тоог эрэмбэлэгдсэн $n$ бүхэл тооны үржвэр хэлбэр задлах боломжийн тоог $1000000007$ $(10^{9} + 7)$ тоонд хуваан үлдэгдлийг хэвлэ.

Хоёр дахь жишээнд $2$ гэсэн тоог үржвэрт задлахад аль нэг үржвэр нь $2$-той тэнцүү, үлдсэн хоёр нь $1$-тэй тэнцүү байна.

Гурав дахь жишээний боломжит задаргаа нь $(7, 5), (5, 7), (1,35), (35, 1)$ юм.

$m$ тооны $n$ эрэмбэлэгдсэн үржвэрийн задаргаа гэдэг нь $(m = \prod\limits_{i=1}^{n} a_{i})$ нөхцлийг хангах $b = {b_{1}, b_{2}, ... b_{n}}$ дарааллыг хэлэх юм. Хэрэв $b_{i} ≠ c_{i}$ байх $i$ дугаар олддог бол $b$ болон $c$ задаргааг ялгаатай гэж үзнэ.