C. Зоосны бэрхшээл

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

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

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

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

Гюрнсейн аралд $n$ төрлийн зоос байдаг. $i$-р $(1 ≤ i ≤ n)$ төрлийн зоос нь $a_{i}$ центийн үнэтэй бөгөөд ямар нэг $i$ ба $j$ ($i ≠ j$)-н хувьд $a_{i} = a_{j}$ байж болно.

Бессид нийт $t$ центийн зооснуудын зарим нэг багц байлаа. Тэр Жессид $b_i$ төрлийн зооснуудын тоо нь $c_i$ төрлийн зооснуудаас их байх $q$ ширхэг $(c_i,\ b_i)$ хос тоонуудыг хэлэв. Энд бүх $b_{i}$ ялгаатай, мөн бүх $c_{i}$ ялгаатай гэдэг нь мэдэгдэж байгаа.

Бессид байгаа зооснуудын боломжит хослолуудын тоог олоход Жессид тусал. Бессид байгаа $i$ төрлийн зоосны тоо нь хоёр хослолд ялгаатай байх ямар нэг $i$ $(1 ≤ i ≤ n)$ байдаг бол хослолуудыг ялгаатай гэж үзнэ.

Хариулт нь хэтэрхий том байж болох тул хариуг $1000000007$ $(10^{9} + 7)$-д хуваагаад гарсан үлдэгдлийг хэвлэнэ. Хэрвээ Бессигийн нөхцлийг хангах нийт $t$ центийн боломжит зоосны хослол байхгүй бол гаралт $0$ байна.

Оролт

Эхний мөр нь зайгаар тусгаарлагдсан $n, q$, $t$ $(1 ≤ n ≤ 300; 0 ≤ q ≤ n; 1 ≤ t ≤ 10^{5})$ гурван бүхэл тоог агуулна. Хоёр дахь мөр нь зайгаар тусгаарлагдсан $n$ ширхэг $a_{1}, a_{2}, ..., a_{n}$ $(1 ≤ a_{i} ≤ 10^{5})$ бүхэл тоонуудыг агуулна. Дараагийн $q$ мөр бүр нь зайгаар тусгаарлагдсан $b_{i}$, $c_{i}$ $(1 ≤ b_{i}, c_{i} ≤ n; b_{i} ≠ c_{i})$ ялгаатай бүхэл тоонуудыг агуулна.

Бүх $b_{i}$ ялгаатай ба бүх $c_{i}$ ялгаатай байх ёстой.

Гаралт

Нэг бүхэл тоо хэвлэнэ. Энэ нь Бессид байж болох зөв зоосны хослолуудын тоог $1000000007$ $(10^{9} + 7)$-д хуваагаад гарсан үлдэгдэл юм.

Орчуулсан: Даариймаа

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

Оролт
4 2 17
3 1 2 5
4 2
3 4
Гаралт
3
Оролт
3 2 6
3 1 1
1 2
2 3
Гаралт
0
Оролт
3 2 10
1 2 3
1 2
2 1
Гаралт
0

Тэмдэглэл

Эхний жишээнд өгөгдсөн нөхцлийг хангах нийт $17$ центийн дараах $3$ хослолыг өгнө: $(1$-р төрлийн $0$, $2$-р төрлийн $1$, $3$-р төрлийн $3$, $4$-р төрлийн $2)$, $(0, 0, 6, 1)$, $(2, 0, 3, 1)$.

Өөр ямар ч хослол байхгүй. $b_{i}$, $c_{i}$ хоёуланд нь $4$ гарч ирэх хэдий ч бүх $b_{i}$ ялгаатай ба бүх $c_{i}$ ялгаатай байх бодлогын нөхцлүүдийг хангах учиртайг анхаарна уу.

Сэтгэгдлүүдийг ачааллаж байна...