Сонья муужгайд $n$ ширхэг эерэг бүхэл тоонуудаас тогтох цуваа байжээ.Уг цуваанд нийт $2^{n}$ ширхэг боломжит дэд дараалал байх юм.Дэд дараалал бүрийн хувьд тэрээр уг дэд дарааллын бүх элементүүдийг тэнцүү болгох хамгийн бага үйлдлийн тоог тоолох юм.

Үйлдэл бүр нь доорх 2-ын нэг нь байна:

• Дэд дарааллын ямар нэг элементийг сонгон ямар нэгэн анхны тоогоор үржүүлнэ.
• Дэд дарааллын ямар нэг элементийг сонгон ямар нэгэн анхны тоонд хуваана.Сонгогдсон элемент нь сонгогдсон анхны тоондоо заавал хуваагдаж байх ёстой.

Бүх боломжит $2^{n}$ дэд дарааллуудын хамгийн бага үйлдлийн тоонуудын нийлбэр хэд вэ? Уг нийлбэрийг олон $10^{9} + 7$ модулаар бодож хэвлэнэ үү.

Оролт

Эхний мөрөнд цувааны хэмжээг илэрхийлэх ганц бүхэл тоо $n$ ($1 ≤ n ≤ 300 000$) өгөгдөнө.

2-дахь мөрөнд цувааны элементүүд болох $n$ ширхэг бүхэл тоо $t_{1}, t_{2}, ..., t_{n}$ ($1 ≤ t_{i} ≤ 300 000$)-ууд өгөгдөнө.

Гаралт

Өгөгдсөн цувааны бүх боломжит дэд дарааллуудын хамгийн бага үйлдлийн тоонуудын нийлбэрийг $10^{9} + 7$ модулаар бодож хэвлэнэ.

Эхний жишээнд, $8$-н боломжит дэд дараалал байна: $(60, 60, 40)$, $(60, 60)$, $(60, 40)$, $(60, 40)$, $(60)$, $(60)$, $(40)$ болон $()$ (хоосон дэд дараалал).

Дэд дараалал $(60, 60, 40)$-ын хувьд бид бүх элементийг 2 үйлдлээр тэнцүү болгож чадна -- $40$-ыг $2$-т хувааж $20$-ыг гаргана, дараа нь $20$-ын $3$-аар үржүүлж $60$-ыг гаргана.Үүнээс бага үйлдлээр зорилгодоо хүрэх боломжгүй ба иймд бид хариулт дээр $2$-ыг нэмэх юм.

$(60, 40)$-тай адил 2 дэд дараалал байх ба тус бүр нь мөн дор хаяж $2$ үйлдлээр ижил элементүүдтэй болох юм.

Бусад дэд дараалал бүрийн хувьд бүх тоонууд нь аль хэдийн тэнцүү байна, иймд бид тус бүрийнх нь хувьд $0$ үйлдэл хийх хэрэгтэй.Ингэснээр нийлбэр нь $2 + 2 + 2 = 6$-тай тэнцүү байх юм.