战棋游戏
时间限制 : 3 s
空间限制 : 1 gigabyte
题目
Z最近得到一副十分奇特的棋盘。
这副棋盘的玩法十分高级，只需要使用者在开始的时候给每个棋子划分阵营，然后这个棋盘就会开始自动生成各种战争行为。
在尝试了很多次之后，Z发现了一个规律：如果一对存在着敌对关系的棋子在一个阵营，那么整个游戏都会因为这对棋子的敌对而导致阵营之间的不平衡，从而使游戏很快结束。
假设有$n$个棋子，他们的编号是$1..n$，这些敌对关系是这样的
对于$i=1..n$，棋子$i$和棋子$i\bmod n+1$之间存在着敌对关系。
图中存在着$k$个十分强的棋子（称其为“骑士”），在这些棋子之间可能存在着别的敌对关系。
注意，敌对关系是双向的。
现在一共有$c$种阵营，这些阵营按照$1..c$编号，**Z}想知道有多少种划分阵营的方式，使得没有一个阵营内存在着一对存在敌对关系的棋子，答案对$10^9+7$取模。
两种划分方式不同，当且仅当存在一个棋子，他在两种方案里面所属的阵营编号不同。
注意，每个棋子只能属于恰好一个阵营，一个阵营可能没有棋子。
输入
第一行四个整数$n,k,m,c$，分别表示棋子数，骑士数，骑士之间的敌对关系数，阵营数。
第二行$k$个整数$a_{1..k}$，表示$k$个骑士的编号。
接下来$m$行，每行两个整数$u,v(u\neq v,1\le u,v\le k)$，表示第$u$个骑士，与第$v$个骑士之间存在着敌对关系，即棋子$a_u$与棋子$a_v$之间存在着额外的敌对关系。
输出
一行一个整数，表示有多少种划分阵营的方式，使得没有一个阵营内存在着一对存在敌对关系的棋子，答案对$10^9+7$取模。
样例输入&样例输出
见下发文件中的$chess0$\sim$1.in$和$chess0$\sim$1.ans$。
数据范围
对于所有测试数据，$m\le\frac{k(k-1)}{2}$。
不保证没有重复的敌对关系，但保证没有骑士与自己是敌对的。
保证给出的骑士编号中没有重复的。
保证$c$与$10^9+7$互质。
