시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
8 초 (추가 시간 없음) 1024 MB 38 25 20 66.667%

문제

종영이는 애완 트리를 키우고 있다. 이 트리는 $N$개의 정점이 있으며 $i$번째 간선은 두 정점 $u_i$와 $v_i$를 잇는다.

요즘 트리에게도 사춘기가 와서, 변덕이 심해 간선들의 길이가 매일 바뀐다. $i$번째 간선의 길이는 $\left[L_i, R_i\right]$ 범위의 자연수의 값들 중 하나를 가질 수 있다.

트리의 변덕에 짜증이 난 종영이는 참을성이 부족해 트리를 팔아버리기로 했다. 트리는 지름이 $S$ 이상 $E$ 이하이면 크기가 적절한 좋은 트리라 생각되어 비싸게 취급된다. 트리의 지름은 트리 상에서 임의의 두 정점 사이의 거리 중 최댓값을 뜻한다.

간선들의 가능한 길이들의 조합은 총 $\prod_{i=1}^{N-1} \left(R_i-L_i+1\right)$가지임을 알 수 있다. 종영이가 트리를 비싸게 팔아치우는 것을 도와주기 위해 가능한 모든 조합에 대해 트리의 지름이 $S$ 이상 $E$ 이하인 경우의 수를 구하여라.

입력

첫 줄에 $N$, $S$, $E$가 주어진다. ($2 \leq N \leq 400$, $1 \leq S \leq E \leq 10^9$)

그 후 $N-1$개의 줄에 걸쳐 트리의 간선들의 정보가 주어진다. 정보는 $u_i$, $v_i$, $L_i$, $R_i$ 순서로 주어진다. ($1 \leq u_i$, $v_i \leq N$, $1 \leq L_i \leq R_i \leq 400$)

출력

트리의 지름이 $S$ 이상 $E$ 이하인 경우의 수를 $10^9+7$로 나눈 나머지를 출력한다.

예제 입력 1

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

예제 출력 1

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

예제 출력 2

159