Дэвү өөрийн цэцэрлэгийг цэцэгнүүдээр чимэглэхийг хүсжээ. Тэр $i$-р хайрцаг нь $f_{i}$ цэцэг агуулдаг $n$ хайрцаг худалдаж авсан байна. Нэг хайрцаг дахь бүх цэцэгнүүд ижил өнгөтэй (иймээс тэднийг ялгах боломжгүй). Мөн ямар ч хоёр хайрцаг ижил өнгийн цэцэгнүүдтэй байж болохгүй.

Одоо Дэвү хайрцагнуудаас цэцэрлэгээ чимэглэх яг $s$ цэцэг сонгохыг хүсэж байгаа ба ингэж цэцэг сонгох нийтдээ хэдэн янзын боломж байгааг мэдэхийг хүсэж байна. Түүний чамаас асуусан тоо хэтэрхий том байж болох тул $(10^{9} + 7)$-д хуваасан үлдэгдлийг олоход болно.

Хэрвээ нэг хайрцгаас ялгаатай тооны цэцэгнүүдийг хоёр аргаар сонгодог бол ялгаатай хоёр арга гэж үзнэ.

Оролт

Оролтын эхний мөр нь зайгаар тусгаарлагдсан $n$, $s$ ($1 ≤ n ≤ 20$, $0 ≤ s ≤ 10^{14}$) бүхэл тоонуудыг агуулна.

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

Гаралт

Нэг бүхэл тоо гарна. Энэ бол Дэвүгийн цэцэгнүүдийг сонгож чадах боломжит нийт аргыг $(10^{9} + 7)$-д хуваасан үлдэгдэл.

Жишээ 1. $3$ цэцэг сонгох хоёр боломж байна: $(1, 2)$ ба $(0, 3)$.

Жишээ 2. $4$ цэцэг сонгох нэг л боломж байна: $(2, 2)$.

Жишээ 3. $5$ цэцэг сонгох гурван боломж байна: $(1, 2, 2)$, $(0, 3, 2)$, ба $(1, 3, 1)$.