描述
在“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解释】
一共有4个帮派，旗帜种类一共有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 $。保证不会有重复确认同一个帮派的旗帜种类。
关注我们
