C. ГУЙХ

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Бидний мэдэж байгаачлан Барни-ийн хийдэг ажил нь "ГУЙХ" бөгөөд тэрээр ажил дээрээ нэг их зүйл хийдэггүй ажээ. Иймд тэрээр "аяганууд болон түлхүүр" гэх нэгэн тоглоомыг тоглож эхэлжээ. Уг тоглоомд зүүнээс баруун хүртэл нэг шулуун дээр байрласан 3 ширхэг ижилхэн аяга байх юм. Анхандаа Барни-ийн зүрхний түлхүүр нь голд байрлах аяганы доор байв.

Дараа нь ээлж болгонд Барни голд байрлах аягыг бусад 2 аяганы аль нэгтэй нь дурын байдлаар солих (тэрээр эдгээр 2 аяганаас тэнцүү магадлалтайгаар 1-ийг нь сонгоно) бөгөөд сонгогдсон аяга нь голд байрлах шинэ аяга болох юм. Тоглоом $n$ ширхэг ээлжийн турш үргэлжлэх бөгөөд Барни ямар нэгэн зүйлтэй хамааралгүйгээр ээлж болгон дээр голд байрлах аягатай солих нэгэн аягыг сонгосоор байна. Түүнчлэн түлхүүр нь тоглоом эхлэхэд байсан аяган доороо үргэлж байсаар байх юм.

$n$-р ээлжийн дараа Барни нэгэн охиноос аль аяганы доор түлхүүр агуулагдаж байгааг асуух ажээ. Охин голд байрлах аяга уруу заах боловч эдгээр олон тооны ээлжийн туршид Барни-ийн анхаарал бага зэрэг сарнисан учраас голд байрлах аяганы доор түлхүүр байгаа эсэхийг мэдэхгүй байв. Иймд тэрээр танаас охин зөв аяга сонгосон байх магадлалыг хэлж өгөхийг хүсжээ.

Тоглоомын ээлжийн тоог илэрхийлэх $n$ тоо нь маш том тоо байж болох учраас Барни танд уг тоог өгөхгүй байх юм. Оронд нь тэрээр танд $a_{1}, a_{2}, ..., a_{k}$ гэсэн нэгэн цувааг өгөх бөгөөд энэ нь дараах илэрхийллийн үржигдэхүүнүүд байх юм.

Өөрөөр хэлбэл $n$ тоо нь өгөгдсөн цувааны бүх элементийн үржвэртэй тэнцүү байна.

Хариултыг яг баттай мэдэхийн тулд Барни таныг түүнд бодлогын хариултыг үл хураагдах бутархай хэлбэртэйгээр хэлж өгөхийг хүсжээ. Өөрөөр хэлбэл байх $p / q$ гэсэн энгийн бутархайг олох хэрэгтэй бөгөөд энд -аар 2 тооны хамгийн их ерөнхий хуваагчийг илэрхийлнэ. $p$ болон $q$ тоонууд нь маш том байж болох учраас та зөвхөн эдгээр тоо тус бүрийг $10^{9} + 7$-д хуваагаад гарах үлдэгдлүүдийг олох хэрэгтэй юм.

Бид $p$ болон $q$-ын нь $1$-тэй тэнцүү байхыг хүсэж байгаа бөгөөд эдгээрийг $10^{9} + 7$-д хуваагаад гарах үлдэгдлүүдийн нь $1$-тэй тэнцүү байх албагүй болохыг анхаарна уу.

Оролт

Оролтын эхний мөрөнд бүхэл тоо $k$ ($1 ≤ k ≤ 10^{5}$) өгөгдөх бөгөөд энэ нь Барни-ийн танд өгөх цувааны элементийн тоог илэрхийлнэ.

2-дахь мөрөнд $k$ ширхэг бүхэл тоо $a_{1}, a_{2}, ..., a_{k}$ ($1 ≤ a_{i} ≤ 10^{18}$)-ууд өгөгдөх ба эдгээр нь цувааны элементүүдийг илэрхийлнэ.

Гаралт

Гаралтын ганц мөрөнд $x / y$ гэсэн нэгэн тэмдэгт мөрийг хэвлэх бөгөөд энд $x$ нь $p$-г $10^{9} + 7$-д хуваагаад гарах үлдэгдлийг, $y$ нь $q$-г $10^{9} + 7$-д хуваагаад гарах үлдэгдлийг тус тус илэрхийлнэ.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
1
2
Гаралт
1/2
Оролт
3
1 1 1
Гаралт
0/1
Сэтгэгдлүүдийг ачааллаж байна...