布拉格国家剧院于 1881 年 6 月开始活动，但不久之后——同年 8 月——在完工前被烧毁。伴随着建筑的毁灭，具有极高艺术价值的独特装饰也一同化为灰烬。

因此，艺术家们开始为重建建筑中的未来绘画和壁画准备新的设计。在此期间，开始了一个过渡时期，被称为“编号绘画”时代，它后来成为了立体主义、立体未来主义以及新古典 Pissoffism 等更著名风格的先驱。

编号绘画的工作原理如下：艺术家准备一张预期作品的大草图，主要强调人物和周围风景的轮廓。然后，助手们制作了许多张同样大小的草图副本。在每个副本中，由轮廓包围的各个区域都用不同的自然数进行标记。在所有副本中，相同的区域都标记有相同的数字。

因此，艺术家获得了许多带有编号区域的相同草图。为了评估成品画作的整体视觉效果，艺术家指示助手们为每张草图填上颜色。每个封闭区域都涂上单一的颜色，并且为了使过程尽可能简单，没有添加任何额外的细节。

不同的草图以不同的方式着色，且没有两张草图的着色方式完全相同，这意味着它们在至少一个区域的颜色上有所不同。需要注意的是，助手们只有一盒可用颜色的调色板。

着色后的草图随后被临时放置在光线和氛围与画作预期最终位置相似的各个地点。艺术家会选择最令他满意的着色草图，并将其作为完成作品的样板。

草图中区域的编号有一个特定的目的。艺术家们关注他们所谓的“对比区域”。为了达到强烈的对比效果，某些彼此接近的区域不允许涂上相同的颜色。

为了强制执行这一点，艺术家给助手们提供了一份禁止区域对的清单，表示为与草图中的编号相对应的数字对。禁止对中的区域必须涂上不同的颜色。

在重建的国家剧院进行装饰工作的艺术家们是真正的激进分子，他们总是要求助手们准备好涵盖所有符合给定限制的可能颜色组合的草图。这是一个相当大的数量——在今天很难估计，因为在最终作品完成后，大多数草图都被销毁了。令现代艺术史学家大失所望的是，只有极少数幸存了下来。

最近，人们发现了几份完整的禁止对清单，这些清单与剧院内的一些著名画作有关。现在人们相信，从每个这样的禁止对清单中，可以推断出在创作相应画作时必须使用过的草图数量。请尝试针对不同大小的颜色调色板确定这个数量。

输入格式

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

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

我们假设区域用数字 $0, 1, \dots, N - 1$ 标记。

接下来 $M$ 行，每行包含一对整数 $u, v$（$0 \le u, v < N$），表示一对禁止的区域。保证 $u \neq v$，且所有 $u, v$ 对都是唯一的。

输出格式

输出 $T$ 个数字，其中第 $i$ 个数字表示如果调色板恰好包含 $A_i$ 种不同的颜色，则会创建的草图总数。输出结果模 $1000000007$。

样例

输入样例 1

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

输出样例 1

0
0
12

输入样例 2

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

输出样例 2

0
2
18
84