Rắc rối tiền xu

Có $n$ loại đồng xu. Đồng xu loại $i$ có mệnh giá $a_i$ xu (các $a_i$ có thể trùng nhau).

Bạn cần chọn một bộ đồng xu (mỗi loại có thể lấy $0$ hoặc nhiều đồng) sao cho tổng mệnh giá đúng bằng $t$ xu. Ngoài ra, bộ đồng xu phải thỏa mãn $q$ điều kiện: điều kiện thứ $i$ cho bởi cặp $(b_i,c_i)$, nghĩa là số đồng xu loại $b_i$ phải lớn hơn thực sự số đồng xu loại $c_i$.

Đảm bảo mọi $b_i$ đôi một khác nhau và mọi $c_i$ đôi một khác nhau (một chỉ số có thể vừa xuất hiện ở cột $b$ vừa xuất hiện ở cột $c$).

Hai bộ đồng xu được coi là khác nhau nếu tồn tại loại $i$ mà số đồng xu loại $i$ ở hai bộ khác nhau.

Hãy đếm số bộ đồng xu hợp lệ có tổng đúng $t$ xu, kết quả lấy theo modulo ${10}^9+7$. Nếu không có bộ nào, in ra $0$.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $q$, $t$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.
• $q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên phân biệt $b_i$ và $c_i$.

Dữ liệu ra

Một số nguyên duy nhất: số bộ đồng xu hợp lệ, lấy theo modulo ${10}^9+7$.

Ràng buộc

• $1\le n\le 300$; $0\le q\le n$; $1\le t\le {10}^5$.
• $1\le a_i\le {10}^5$.
• $1\le b_i,c_i\le n$; $b_i\ne c_i$.
• Mọi $b_i$ đôi một khác nhau; mọi $c_i$ đôi một khác nhau.

Ví dụ