题目描述

布拉格国家剧院于 1881 年 6 月开始运营，却在同年 8 月、尚未完全竣工时遭遇火灾。建筑本身和其中极具艺术价值的独特装饰都被烧毁了。

艺术家们随后开始为修复后的剧院重新设计绘画和壁画。那时出现了一段被称为“编号绘画”的过渡时期，它后来成为立体主义、立体未来主义等艺术风格的先驱。

编号绘画的制作过程如下：

1. 艺术家先绘制一张大型草图，重点勾勒人物和周围景物的轮廓；
2. 助手制作许多大小完全相同的草图副本；
3. 每张副本中的各个封闭区域都用自然数编号，并且同一区域在所有副本中的编号相同；
4. 助手使用同一个调色板，为每张草图中的每个区域选择一种颜色。

不同草图的着色方案必须互不相同，即任意两张草图至少有一个区域颜色不同。

为了形成强烈的对比效果，艺术家还会给出若干对“禁止同色”的区域。每一对中的两个区域必须使用不同颜色。

助手必须制作出所有满足这些限制的不同着色方案。

现在，我们找到了某幅作品完整的禁止同色区域列表。对于若干种不同大小的调色板，请计算分别需要制作多少张不同的草图。

形式化地说，把每个区域看作一个顶点，把每一对禁止同色区域看作一条边。对每个给定的颜色数量 $k$，需要计算使用这 $k$ 种可用颜色对所有顶点进行合法染色的方案数。颜色不要求全部被使用。

输入格式

第一行包含三个整数 $N,M,T$（$1\le N\le 21$，$0\le M\le 21$，$1\le T\le 10^5$），分别表示区域数、禁止同色的区域对数量以及调色板数量。

第二行包含 $T$ 个整数 $A_i$（$1\le A_i<10^6$），第 $i$ 个数表示第 $i$ 个调色板中可用颜色的数量。

区域编号为 $0,1,\ldots,N-1$。

接下来 $M$ 行，每行包含两个整数 $u,v$（$0\le u,v<N$），表示区域 $u$ 和区域 $v$ 不能使用相同颜色。

保证：

• $u\ne v$；
• 所有给出的无序点对互不重复。

输出格式

按输入顺序输出 $T$ 个答案，每个答案占一行。

第 $i$ 个答案表示使用恰好 $A_i$ 种可用颜色时的合法着色方案数。答案对

取模。

样例 1

输入

4 4 3
1 2 3
0 1
1 2
0 2
0 3

输出

0
0
12

样例 2

输入

4 4 4
1 2 3 4
0 1
1 2
2 3
0 3

输出

0
2
18
84