祖先

题目描述

DD 学习了关于树上公共祖先的知识。 LCA（Lowest Common Ancestors），即最近公共祖先，是这样一个问题：在有根树中，找出某两个结点 u 和 v 最近的公共祖先（或者说，离树根最远的公共祖先）。 现在给定一棵树，给定树根，萨摩耶不断给出询问 ai,DD 需要回答出有多少点对 (x,y)（其中 x,y 可以相等）的 LCA 是 ai，答案对 10^9+7取模

输入

第一行三个整数，分别表示 n,m,root。接下来 n−1 行每行两个整数，表示边连接着 ui,vi。接下来一行 n 个整数，第 i 个表示 ai。 【数据范围】 对于 20% 的数据，1≤n,m≤500；对于 50% 的数据，1≤n,m≤104； 对于 100% 的数据， 1≤n,m≤106；

输出

对于每次询问回答有多少个点对的 LCA 符合条件。

样例输入

7 3 1
1 2
1 3
2 4
2 5
3 6
3 7
1 2 4

样例输出

31
7
1

来源：徐州工程学院编程竞赛OJ