Cho đồ thị vô hướng và số nguyên tố ~p~, mỗi đỉnh có trọng số ~x_i~ ~(0 \leqslant x_i < p)~. Mỗi đỉnh ~u~ sẽ có một số nguyên ~b_u~ ~(0 \leqslant b_u < p)~ thỏa mãn ~b_u = \Sigma x_v (mod~ ~p)~ với tất cả các đỉnh ~v~ có cạnh nối trực tiếp với ~u~.

Yêu cầu: Cho đồ thị và mảng ~b~ ~(0 \leqslant b_i < p)~, hãy đếm số lượng mảng ~a~ thỏa mãn. Dữ liệu đảm bảo tồn tại ít nhất ~1~ nghiệm thỏa mãn.

INPUT

• Dòng đầu chứa 3 số nguyên ~n~, ~m~, ~p~ ~(1 \leqslant n \leqslant 100,~ ~1 \leqslant m \leqslant 200,~ ~p \leqslant 10 ^ 9)~ lần lượt là số đỉnh, số cạnh và số nguyên tố ~p~.
• Dòng tiếp theo là ~n~ số nguyên của mảng ~b~, mỗi số cách nhau ~1~ dấu cách.
• ~m~ dòng sau, mỗi dòng là ~2~ số ~u~, ~v~ cho biết có cạnh nối giữa ~u~ và ~v~.

OUTPUT

• Một số nguyên duy nhất là số lượng mảng ~a~ thỏa mãn lấy dư cho ~10^9+7~.

SAMPLE TEST

Input:

5 5 13
5 20 0 23 5 
1 4
2 1
2 4
4 5
5 2

Output:

2197