5495: 旗帜（flag）

在“xx 西游”网游中，每个帮派都可以设置自己旗帜，编号为1～k的k种旗帜。另外每个帮派均会设置一个自己的敌对帮派。

假设，这个网游内有n个帮派并编号从1～n，其中在有m种帮派旗帜已经确定的情况下，有多少种设计方案，使得每个帮派的旗帜，都和自己的敌对帮派的旗帜不同。

方案数可能很大，你只需要输出对10^9+7取模的结果即可。

从文件 flag.in 中读入数据。

输入的第一行包含三个正整数 n,m,k，分别表示帮派的个数、确定的帮派个数和旗帜的种类数。

接下来 n 行，第 i 行仅一个整数 d_i，表示第 i 个帮派的敌对帮派编号为 d_i。

接下来 m 行，每行两个整数 i,c_i。表示第 i 个帮派的旗帜必须是第 c_i种。

输出到文件 flag.out 中。

输出仅一个数字，即设置旗帜的方案数，结果可能很大，你只需要输出对 10^9+7 取模的结果即可。

3 0 3
2
3
1

6