题目描述

rsw因为迟到次数太多被列入黑名单，于是被派去参加陕西妇女儿童技能大赛，大赛中共安排了$m$个比赛项目，算上rsw在内，共有$n$位选手报名参加本次比赛。（如rsw，zrx，kh，ljm，cky，大耳朵图图，大头儿子等）

经过$m$场比赛，组委会发现，每个项目，有且仅有两个人实力超群。（比如穿针引线项目，rsw，ljm独领风骚，健美操项目，cky，cjy风姿绰约）。

现在，组委会要推选一些人去参加全国比赛，因为每个项目都必须有人擅长，所以推选的这些人，对于每一个项目，至少要有一个人擅长。

已知，选中每个人参加比赛是有一个费用$a[i]$，比如选中了$1,3,5$三个人参加比赛，就要支付$a[1]\times a[3]\times a[5]$的费用。

现在的问题是：组委会所有可行选人方案的费用总和是多少？

输入格式

第一行$n,m,q$。

接下来$1$行$n$个数字$a[1]$~$a[n]$。

接下来$m$行，每行$2$个数字$u,v$，代表$u$和$v$两个人共同擅长第$i$个项目。

输出格式

一行，$1$个数字，表示最后的结果$mod$ $q$。

样例输入1

3 2 998244353
1 1 1
1 2
2 3

样例输出1

5

样例解释

合法情况有：$[1,2],[1,3],[1,2,3],[2],[2,3]$五种，每种的费用都是$1$，所以结果是$1+1+1+1+1=5$。

大样例在此

数据分布

对于30%的数据，$n\leq 20$

对于70%的数据，$n\leq 28$

对于100%的数据，$n\leq 36,0\leq m\leq n\times n,q\leq 10^9$