함수와 최소 스패닝 트리

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

각 간선의 가중치는 시간 $t$에 따라 변화하는 이차함수 $at^2+b\_it+c\_i$ 꼴이다. 모든 간선에 대해 $a$는 동일하다.

이때 함수 $f(t)$를 시간 $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}$임을 이용할 수 있다.