Иахуб найз охин Иахубинатайгаа уулзахыг хүсжээ. Тэр хоёр хоёулаа $Ox$ тэнхлэг (хэвтээ тэнхлэг) дээр, Иахуб $0$ цэг дээр харин Иахубина $d$ цэг дээр байрлаж байлаа.

Иахубт $a_{1}$, $a_{2}$, ..., $a_{n}$ гэсэн $n$ эерэг бүхэл тоо бий. Эдгээрийн нийлбэр нь $d$. $p_{1}$, $p_{2}$, ..., $p_{n}$ нь ${1, 2, ..., n}$-ийн ямар нэгэн сэлгэмэл ба $b_{1} = a_{p_{1}}$, $b_{2} = a_{p_{2}}$ ... байг. Энэхүү $b$ дарааллыг "зам" гэж нэрлэе. Тэгэхээр сэлгэмэл бүрт нэг зам харгалзах ба нийт $n!$ ширхэг ялгаатай зам байж болно.

Иахубын аяллын хуваарь нь: эхлээд $Ox$ тэнхлэг дээгүүр $b_{1}$ алхам яван $b_{1}$ цэг дээр амарна. Тэгээд дахин $Ox$ тэнхлэг дээгүүр $b_{2}$ алхам яван $b_{1} + b_{2}$ цэг дээр амарна. Мөн адилаар $j$ $(1 ≤ j ≤ n)$ дэх удаа алхахдаа $b_{j}$ алхам яван $b_{1} + b_{2} + ... + b_{j}$ цэг дээр амарна.

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

Оролт

Эхний мөрөнд бүхэл тоо $n$ ($1 ≤ n ≤ 24$) байна. Дараагийн мөрөнд $n$ ширхэг бүхэл тоо байна: $a_{1}, a_{2}, ..., a_{n}$ ($1 ≤ a_{i} ≤ 10^{9}$).

Гурав дахь мөрөнд бүхэл тоо $k$ ($0 ≤ k ≤ 2$) байна. Дөрөв дэх мөрөнд Иахубийн $k$ ширхэг азгүй тоонууд байна. Эдгээр тоонууд нь $10^{9}$-аас хэтрэхгүй.

Гаралт

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

Эхний жишээн дээрх зургаан боломжит дарааллыг сонирхъё:

• $[2, 3, 5]$. Иахуб $2$, $5$, $10$ цэгүүд дээр амарна. Харин $5$ азгүй тоо юм.
• $[2, 5, 3]$. Иахуб $2$, $7$ ба $10$ цэгүүд дээр амарна. Харин $7$ азгүй тоо юм.
• $[3, 2, 5]$. Ахиад л азгүй $5$ дээр зогсож таарах нь.
• $[3, 5, 2]$. Энэ сайн дараалал юм.
• $[5, 2, 3]$. $5$ ба $7$ гэсэн хоёр ч азгүй тоон дээр зогсоно.
• $[5, 3, 2]$. Шууд л $5$ гэсэн азгүй тоон дээр очно.

Хоёр дахь жишээн дээр ялгаатай хоёр замын зогсох цэгүүд ижил байж болохыг анхаарна уу. Үнэндээ боломжит бүх замууд ижил зогсох газруудтай юм: $[2, 4, 6]$. Энд азгүй тоо байхгүй байна.