UOJ Logo

NOI.AC

1S 512MB
Statistics

战棋游戏

时间限制 : 3 s

空间限制 : 1 gigabyte

题目

Z最近得到一副十分奇特的棋盘。

这副棋盘的玩法十分高级,只需要使用者在开始的时候给每个棋子划分阵营,然后这个棋盘就会开始自动生成各种战争行为。

在尝试了很多次之后,Z发现了一个规律:如果一对存在着敌对关系的棋子在一个阵营,那么整个游戏都会因为这对棋子的敌对而导致阵营之间的不平衡,从而使游戏很快结束。

假设有n个棋子,他们的编号是1..n,这些敌对关系是这样的

  • 对于i=1..n,棋子i和棋子imod之间存在着敌对关系。

  • 图中存在着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\sim1.inchess0\sim1.ans

点此下载

数据范围

对于所有测试数据,m\le\frac{k(k-1)}{2}

不保证没有重复的敌对关系,但保证没有骑士与自己是敌对的。

保证给出的骑士编号中没有重复的。

保证c10^9+7互质。

img