题目描述

在“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

1	6

样例1解释

4 1 3
3
1
2
1
4 3

1	4

样例2解释

tree3.ans
tree3.in

数据范围

对于所有测试数据有：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 。保证不会有重复确认同一个帮派的旗帜种类。