输入描述:

第一行输入一个正整数 ，表示房间个数。
第二行输入  个整数 。令 ，则 。
第三行输入  个整数 。
接下来  行，每行输入两个整数 ，表示第  条通道连接房间  和房间 。
保证输入的图是一棵树。

输出描述:

显然，最后答案一定可以表示成  的形式。
请输出这个分数对  取模后的结果。

备注:

，，。