Công ty của Alice có ~n~ nhân viên được tổ chức vào ~m~ phòng ban. Nhân viên ~i~ (~1 ≤ i ≤ n~) đang thuộc phòng ban ~d_i~, mỗi phòng ban có ít nhất ~2~ người.

Có ~s~ sự phản đối, sự phản đối thứ ~k~ là ~i_k, j_k~ cho biết nhân viên ~i_k~ phản đổi nhân viên ~j_k~. Một lần sắp xếp lại nhân sự, lãnh đạo công ty sẽ chọn từ mỗi phòng ban một nhân viên và chuyển nhân viên đó sang phòng ban khác, mỗi phòng ban sau khi chuyển một nhân viên đi sẽ chỉ nhận lại một nhân viên. Nhân viên ~i~ có thể xếp vào phòng ban ~d~, nếu những người ở lại phòng ban ~d~ phản đối nhân viên ~i~ không quá bán (cụ thể, nếu còn lại ~x~ người thì số người phản đối nhỏ hơn hoặc bằng ~\frac {x}{2}~).

Yêu cầu: Đếm số lượng cách sắp xếp nhân sự.

INPUT

Dòng đầu chứa ba số nguyên không âm ~n~, ~m~, ~s~ (~1 \le n \le 200~, ~1 \le m \le 10~, ~s \le \frac {n \times (n - 1)}{2}~).

Dòng thứ hai gồm ~n~ số nguyên ~d_1, d_2, ..., d_n~ (~1 \le d_i \le m~).

Dòng thứ ~k~ (~1 ≤ k ≤ s~) trong ~s~ dòng sau chứa hai số nguyên ~i_k, j_k~.

OUTPUT

Số cách sắp xếp, chia dư cho ~10^9 + 7~.

SAMPLE INPUT 1

4 2 0
1 1 2 2

SAMPLE OUTPUT 1

4

SAMPLE INPUT 2

4 2 1
1 1 2 2
3 1

SAMPLE OUTPUT 2

3

SUBTASKS