题目描述

钟英养了一棵宠物树。这棵树共有 $N$ 个顶点，第 $i$ 条边连接顶点 $u_i$ 和 $v_i$。

树的边长每天都会变化。第 $i$ 条边的长度可以取区间

内的任意正整数。

若一棵树的直径不小于 $S$ 且不大于 $E$，则称这组边长对应的树为一棵好树。

树的直径是树上任意两个顶点之间距离的最大值。

所有边长方案的总数为

请计算其中有多少种方案使树的直径位于区间 $[S,E]$ 内。

输入格式

第一行包含三个整数 $N,S,E$。

接下来 $N-1$ 行，每行包含四个整数

表示一条连接 $u_i$ 与 $v_i$ 的边，其长度可以取 $[L_i,R_i]$ 内的任意整数。

输入保证这些边构成一棵树。

输出格式

输出满足条件的边长方案数对

取模后的结果。

样例 1

输入

4 3 14
1 2 1 10
1 3 1 10
1 4 1 10

输出

573

样例 2

输入

8 17 31
3 4 5 5
1 8 8 8
8 2 8 10
6 7 8 10
6 3 9 10
8 6 7 10
7 5 1 10

输出

159