万物因时潮涌 锚点又在何方 白垩色的王子给了你一张由 个点和 条无向边构成的联通图（结点编号从 至 ，保证不存在重边和自环），每条边的长度均为 ，同时，他又给了你一点 。 白垩色的王子告诉你图上存在 个锚点。记第 个锚点所在点的编号为 ，记点 到点 的最短距离为 。他又告诉你，这 个锚点的位置满足 ，且对于任意一个锚点 ，都有 。 同时，这个图还满足：记图中一点 到点 的距离为 ，保证 。 现在白垩色的王子想知道，这 个锚点的位置有多少种可能。具体地，我们记这 个锚点的位置组成了一个集合 ，对于两个集合，如果他们有任意一个元素不一样，我们就认为这两个集合是不一样的。也就是说，你只需要输出合法的不同集合数即可。 一共有 组询问，每组询问给出一个 ，你需要求出锚点数量为 时的可能位置方案数。 由于答案可能过大，你只需要输出它对 取模的结果。

输入描述:

第一行输入四个整数 ，意义如题面所示。接下来 行，每行包含两个整数 ，表示在 之间存在一条无向边。接下来 行，每行输入一个整数 ，表示锚点的数量。

输出描述:

输出 行，第 行输出一个整数表示对于第 组询问给出的 ，锚点位置的合法方案数，结果对 取模。