树

题号：NC19186
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

你有一棵 $n\$ 个节点的树，根节点为1，定义好的路径是连接祖先节点和其子孙节点的路径

如图，路径 $(1,5)\$ 是好的路径，因为节点 $1\$ 是节点 $5\$ 的祖先
路径 $(6,4)\$ 不是好的路径，因为节点 $6\$ 不是节点 $4\$ 的祖先，节点 $4\$ 也不是节点 $6\$ 的祖先

你希望知道有多少对路径 $\lbrace (a,b),(c,d) \rbrace$ 满足 $(a,b)\$ 和 $(c,d)\$ 的路径交是长度在 $\lbrack l,r \rbrack$ 之间的好的路径
下面是一些你可能会用到的定义:
路径交: $(a,b) , (c,d)\$ 的路径交定义为路径 $(a,b)\$ 和 $(c,d)\$ 路径所共同覆盖的点和边(可能为空）

不难看出一对路径的交还是一条路径

路径长度：路径上边的数量

路径 $(a,b)\$ 和 $(b,a)\$ 视为同一条
路径对 $\lbrace (a,b),(c,d)\rbrace$ 与 $\lbrace (c,d),(a,b) \rbrace$ 视为同一对
路径对 $\lbrace (a,b),(a,b) \rbrace$ 不计入答案

输入描述:

第一行三个数
接下来行，每行两个数，代表树上的一条边，保证给出的是一棵树

输出描述:

一个整数表示答案，对取模

示例1

输入

复制

输出

复制

备注:

对于所有数据满足 , 
对于的数据，满足 
对于的数据，满足 
对于另外的数据，满足树是一条链，并且节点1是一个端点