Evaluation Batch Compilation commands

새로운 도시를 지으려고 한다. 도시는 위에서 내려다 봤을 때 평면으로 나타낼 수 있는데, 도시의 구획을 $10^9 \times 10^9$개의 균등한 크기의 칸으로 나누어 가장 왼쪽 위에 있는 칸을 $(1,1)$, 가장 오른쪽 아래에 있는 칸을 $(10^{9},10^{9})$이라고 하자. 모든 칸에는 그 칸의 영향력을 나타내기 위해 숫자를 매길 것이다. 이 숫자들은 처음에 모두 0 으로 초기화되어 있다.

도시에는 여러 가지 편의 시설이 들어서므로, 도시를 짓기 전에 편의시설들이 주변에 미치게 되는 영향을 예상해 보았다. 각 예상은 다음과 같은 형태이다.

$a \le x \le c, b \le y \le d$를 만족하는 칸 $(x, y)$에 $p$를 더한다.

그리고 최종적으로 각 칸들이 미치는 영향력의 크기는 각 칸에 써진 숫자의 제곱이 되며, 이 도시의 영향력은 모든 칸의 영향력을 더한 값이 된다.

예를 들어 다음과 같은 두 가지 예상이 있다고 해보자.

$1 \le x \le 2, 1 \le y \le 3$을 만족하는 칸 $(x, y)$에 $1$을 더한다. $1 \le x \le 3, 2 \le y \le 3$을 만족하는 칸 $(x, y)$에 $1$을 더한다.

그러면 칸에 있는 숫자들은 다음과 같이 될 것이며, 도시의 총 영향력은 $1^2 \times 2 + 3^2 \times 4 + 2^2 \times 2 = 46$이 된다.

$N$개의 예상이 주어지면, 모든 예상을 적용 하였을 때 도시의 영향력을 구하는 프로그램을 작성하라.

입력 형식

첫 번째 줄에는 예상의 개수 $N$ $(1 \le N \le 10^{5})$가 주어진다.

다음 $N$개의 줄에는 각 줄마다 $a, b, c, d, p$ $(1 \le a \le c \le 10^{9}, 1 \le b \le d \le 10^{9}, 1 \le p \le 100)$가 공백으로 구분되어 주어진다. 이는 위에서 설명한 하나의 예상을 의미한다.

출력 형식

주어진 예상을 모두 적용하였을 때 도시의 영향력을 출력한다. 답이 매우 커질 수 있으므로 답을 $1,000,000,007$로 나눈 나머지를 출력한다.

입력

2
1 1 2 3 1
1 2 3 3 2

출력

46