ztm 的火星探索

题目描述

ztm 所在的国家决定去火星建立观测基地！为了建立观测基地， ztm 选拔了 $n$ 个各行各业的人才，编号分别为 $1 \sim n$

但是建立观测基地对于各个领域的专业人员要求很高，有非常多的技术都需要有人懂，才能把这个任务完成

而现在 ztm 统计了可能发生的事件，一共有 $m$ 件，其中包含（工程建造，水循环利用，空气循环......等等相关需求）

现在 ztm 已经统计完了每个人擅长的领域，对于每个事件罗列出了两位擅长并且一定能解决该需求的人才

现在 ztm 需要选一些人去建立观测基地，并且要保证他挑选的人在遇到这 $m$ 种事件一定有人擅长并且能站出来解决问题

ztm 想知道一共有哪些选人方案，但是方案数可能很大，所以 ztm 会给第 $i$ 位人才设定一个系数 $a_i$，对于选拔的几位人才以后，这一组方案可以用 $a$ 的乘积来表示

例如选了 $1,2,7$ 三位人才，那么这一组方案可以用 $a_1 * a_2 * a_7$ 来表示

为了方便输出，请输出可行的方案总和并对 $mod$ 取模

输入格式

输入第一行包含三个整数 $n,m,mod$ 表示有 $n$ 个人才，$m$ 个事件 输入第二行包含 $n$ 个整数，分别表示每个人才的系数 $a_i$ 接下来 $m$ 行，每行包含两个整数 $x,y$ 表示第 $i$ 个事件有 $x,y$ 这两位人才可以解决

输出格式

输出一个数字表示最终结果

数据范围

数据点

$n,m$

$1 \sim 3$

$n\leq 20, m \leq 100$

$4 \sim 7$

$n\leq 28,m \leq 100$

$8 \sim 10$

$n\leq 36,m \leq 1000$

对于所有数据保证 $mod \leq 10^9$

样例输入

3 2 10
1 1 1
1 2
2 3

样例输出

5

样例解释

可以选择的方案有五种 $(1,2),(1,3),(1,2,3),(2),(2,3)$ 每一种的方案值都是 $1$,总和为 $5$