Có \(n\) khủng long đang đứng ngoài sân, số con của mỗi loài rất nhiều. Mỗi loài có thể ghét một số loài khác. Người quản thú đang có \(k\) cái kẹo và sẽ tổ chức một hoạt đọng cho các con khủng long này. Anh ta chuẩn bị một cái chuống dài và hẹp, sau đó sẽ gọi các con khủng long đi vào chuồng hoặc đi ra khỏi chuồng. Vì không thích ở trong chuồng, anh ta phải cho khủng long một viên kẹo mỗi làn gọi vào, còn gọi ra thì không mất kẹo. Anh ta có thể gọi bất cứ con khủng long của loài nào ngoài sân đi vào chuồng, miễn là trong chuồng không có con khủng long nào thuộc loài mà nó ghét. Còn lúc gọi ra, vì chuồng hẹp, nên còn khủng long vào sao cùng sẽ ra trước.

Yêu cầu: Tính số cách khác nhau mà anh ta có thể tổ chức hoạt động trên, sao cho tất cả kẹo đều được dùng hết và sau cùng chuồng rỗng. Lưu ý, các con của cùng một loài là giống nhau và không phân biệt được.

Input

• Dòng đầu chứa ba số nguyên \(n,m,k\) là số loài khủng long, số kẹo và số thông tin mà khủng long ghét nhau \(1 ≤ n ≤ 10, 1 ≤ k ≤ 100, 0 ≤ m ≤ n(n-1)\).

• Mỗi dòng trong số \(m\) dòng tiếp theo chứa hai số \(u,v\) cho biết loài \(u\) ghét loài \(v\). Lưu ý việc ghét là một chiều.

Output

Ghi một số nguyên là số cách tổ chức hoạt động sau khi chia lấy dư cho \(10^9+7\).

Sample Input

2 2 1
1 2

Sample Output

7