在“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取模的结果即可。

【样例1解释】 一共有3个帮派，旗帜种类一共有3种，1号帮派的敌对帮派是2号帮派，2号帮派的敌对帮派是3号帮派，3号帮派的敌对帮派是1号，没有已经确定旗帜种类的帮派。有6种方案满足条件。

【样例2解释】

一共有3个帮派，旗帜种类一共有3种，1号帮派的敌对帮派是3号帮派，2号帮派的敌对帮派是1号帮派，3号帮派的敌对帮派是2号，4号帮派的敌对帮派是1号，另外已经确定了4号帮派的旗帜是第3种。一共有4种方案满足条件。

对于所有测试数据有：2≤n≤2×10^5,0≤m≤ min(n,10^4),2≤k≤20,1≤d_i≤n,d_i≠i,1≤c_i≤k 。保证不会有重复确认同一个帮派的旗帜种类。

云南编程挑战赛