함수와 최소 스패닝 트리

$1$부터 $V$까지 번호가 붙은 정점이 $V$개, 간선이 $E$개인 단순 연결그래프가 주어진다.

각 간선의 가중치는 시간 $t$에 따라 변하는 이차함수 $at^2+b_it+c_i$ 꼴이다. 모든 간선에 대해 $a$는 같다.

시간 $t$에서의 최소 스패닝 트리의 가중치 합을 $f(t)$라고 정의하자.

정수 $t_1$, $t_2$가 주어지면 $\int_{t_1}^{t_2}f(t)dt$의 값을 구하시오.

최소 스패닝 트리는 주어진 그래프의 모든 정점을 연결하는 부분 그래프 중에서 가중치의 합이 가장 작은 트리이다.

첫 번째 줄에 정수 $V$, $E$, $a$가 공백으로 구분되어 주어진다. ($1 \le V \le 100$, $1 \le E \le 250$, $-1\,000 \le a \le 1\,000$, $a \neq 0$)

다음 $E$개의 줄에는 간선의 정보를 나타내는 정수 네 개 $X$, $Y$, $b_i$, $c_i$가 공백으로 구분되어 주어진다. ($1 \le X, Y \le V$, $-1\,000 \le b_i, c_i \le 1\,000$)

이는 $X$번 정점과 $Y$번 정점을 잇는 간선의 가중치가 $at^2+b_it+c_i$라는 뜻이다.

마지막 줄에는 시간을 나타내는 정수 $t_1$과 $t_2$가 공백으로 구분되어 주어진다. ($-1\,000 \le t_1 \le t_2 \le 1\,000$)

$\int_{t_1}^{t_2}f(t)dt$의 값이 정수 $m$, 양의 정수 $n$에 대하여 기약분수 $\frac{m}{n}$이면, $m\times n^{-1}\bmod (10^9+7)$을 출력한다. $n^{-1}$은 $n$의 모듈러 곱셈에 대한 역원이다.

$10^9+7$의 배수가 아닌 $n$에 대해서는 답이 위와 같은 꼴로 표현됨을 증명할 수 있다.

필요하다면 $(ab^{-1})+(cd^{-1}) \equiv (ad+bc)\times(bd)^{-1} \pmod {10^9+7}$임을 이용할 수 있다.