更好的阅读体验：
黑谷山女是生活在洞穴里的蜘蛛妖怪。尽管如此，作为拥有蜘蛛能力的土蜘蛛，山女常常通过建筑巨大的蜘蛛网完成一些土木工程上的工作，是一个非常忙碌的打工人。

当然，山女除了会建造蜘蛛网，同样会拆除蜘蛛网。对于形如脚手架一般的蜘蛛网，在建筑完工后当然就要拆除了。但在拆除过程中，山女遇到了一点小麻烦。

不同的蜘蛛丝会在一些地点打结，这些网结直接影响了拆除与之相连的边所花费的时间。然而山女太忙碌了来不及计算出一个最优方案，只能每次等概率地选取一条剩下的边进行拆除。山女选择了一些边作为采样点，来估算拆除整张网的总时间。但由于网太复杂，所花费的时间难以计算，因此她来求助了。




整张蜘蛛网可以认为是一个 个节点、 条边的无向图，每个节点的粘度就是与它相连的边的数目。

山女每次随机选取一条剩余的边进行拆除，花费的时间就是两端节点的粘度之和。当拆除这条边后，两端节点的粘度分别会下降。我们计删除第 条边花费的时间为 。此外，蜘蛛网上有 条特殊的边，分别为 。山女想知道删除这些边时花费时间的和的期望。即：



由于这个结果很大，山女只要你将结果对 (一个质数，等于 ) 取模就行了。

第一行有三个正整数  ，含义如题面所示。
接下来  行，每行有两个正整数  ，表示一条连接着网结  和网结  的蜘蛛丝。山女可能会用若干条蜘蛛丝连接相同的两个网结以加强强度，但保证  。
接下来一行，共有  个正整数  ，表示山女选中的边。

共一个整数，表示删除那  条边时花费的总时间的期望对  取模后的结果。

2 1 1
1 2
1

2

图上有且仅有一条边，连接着网结  和网结  ，因此山女只能删除它。在删除前两个网结的粘度都是  ，因此总时间的期望为  。

3 2 1
1 2
2 3
1

499122179

图上有两条边  和  。山女有两种删除顺序：

- 首先删除  ，再删除  ，这样的概率为  。由于第一条边端点粘度分别为  和  ，因此删除第一条边用时为  。
- 首先删除  ，再删除  ，这样的概率为  。删除第二条边后，第一条边端点的粘度都变成了  ，因此删除第一条边用时为  。


删除第一条边的总期望为  。在模意义下，  。

    由于本题读入量较大，现提供快速输入模板（C++）：

    通过调用 qread(a) 以读入一个整数 a 。