도시의 영향력

시간 제한2초메모리 제한64 MB

요약

10억 by 10억 격자에 N개 직사각형 가중치를 더한 뒤 셀 값 제곱합을 1,000,000,007로 나눈 나머지를 구합니다.

난이도: 보통10점 중 7점
유형: 세그먼트 트리, 정렬, 누적 합
정답자: 아직 제출이 없습니다

문제

새 도시를 짓는다. 도시를 위에서 내려다보면 평면이고, 이 평면을 크기가 같은 $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)$ 에 $2$ 를 더한다.

그러면 칸 $(1, 1)$ 과 $(2, 1)$ 에는 $1$ , 칸 $(1, 2)$ , $(1, 3)$ , $(2, 2)$ , $(2, 3)$ 에는 $3$ , 칸 $(3, 2)$ 와 $(3, 3)$ 에는 $2$ 가 적히고 나머지 칸은 $0$ 이다. 따라서 도시의 영향력은 $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로 나눈 나머지를 출력한다.

예제7

예제 1
입력
```
2
1 1 2 3 1
1 2 3 3 2
```
예상 출력
```
46
```
예제 2
입력
```
1
1 1 1 1 1
```
예상 출력
```
1
```
예제 3
입력
```
1
7 9 7 9 100
```
예상 출력
```
10000
```
예제 4
입력
```
1
1 1 1000000000 1000000000 1
```
예상 출력
```
49
```
예제 5
입력
```
2
2 2 3 3 3
2 2 3 3 4
```
예상 출력
```
196
```
예제 6
입력
```
2
1 1 2 2 5
3 1 4 2 5
```
예상 출력
```
200
```
예제 7
입력
```
3
1 1 6 6 1
2 2 5 5 2
3 3 4 4 3
```
예상 출력
```
272
```