败北

Problem Description

给定一张 $n$ 个点 $m$ 条边的 DAG。 $q$ 组询问，每次给出集合 $S$ 和 $k$，你要求出对 $S$ 内所有点赋 $[1,k]$ 内的权值，记点 $p$ 的权值是 $a_p$，使得所有满足 $u,v \in S$ 的边 $u \to v$ 满足 $a_u > a_v$ 的方案数，答案模 $10^9+7$。 注意保证无自环但可能有重边，如果 $S$ 为空集答案为 $1$。

Input

本题有多组数据。第一行一个正整数 $T$（$1\le T\le 5$），表示测试数据组数。 对于每组数据，第一行三个整数 $n,m,q$（$1 \le n \le 20,0 \le m \le \dfrac{n(n-1)}{2},1 \le q \le 10^5$）。 接下来 $m$ 行每行两个整数 $u,v$ （$1 \le u,v \le n$）描述图的一条有向边 $u \to v$。 接下来 $q$ 行，每行先是一个正整数 $k$（$1 \le k \le 10^9$），接下来是一个长度为 $n$ 的 $01$ 串 $s$，$s_i=1$ 代表 $i \in S$，否则 $i \notin S$。 保证图无环。

Output

对于每组数据，输出 $q$ 行，每行一个整数，表示赋权值方案数对 $10^9+7$ 取模后的结果。

Sample Input

3
3 2 5
2 3
2 3
2 101
6 001
9 101
5 001
7 001
5 1 5
3 2
2 00110
6 00111
2 10100
2 11001
3 01101
5 8 5
2 1
2 5
2 5
2 4
3 4
4 1
3 5
3 2
10 00101
4 01111
10 00001
3 01110
1 10100

Sample Output

4
6
81
5
7
4
216
4
8
9
45
6
10
1
1

Source

2024“钉耙编程”中国大学生算法设计超级联赛（10）