26519번 - 함수와 최소 스패닝 트리

문제

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}$임을 이용할 수 있다.