City Influence

A new city is being built. Seen from above the city is a plane, and that plane is cut into $10^9 \times 10^9$ cells of equal size. The top left cell is $(1, 1)$ and the bottom right cell is $(10^9, 10^9)$. Every cell carries a number that records the influence on that cell, and every number starts at $0$.

The city will contain many public facilities, so before construction the planners estimated the influence each facility spreads around it. One estimate has this form.

• Add $p$ to every cell $(x, y)$ with $a \le x \le c$ and $b \le y \le d$.

After all estimates are applied, the influence of one cell is the square of the number written on it, and the influence of the city is the sum of the influence of all cells.

Suppose there are these two estimates.

• Add $1$ to every cell $(x, y)$ with $1 \le x \le 2$ and $1 \le y \le 3$.
• Add $2$ to every cell $(x, y)$ with $1 \le x \le 3$ and $2 \le y \le 3$.

Cells $(1, 1)$ and $(2, 1)$ then hold $1$, cells $(1, 2)$, $(1, 3)$, $(2, 2)$, $(2, 3)$ hold $3$, cells $(3, 2)$ and $(3, 3)$ hold $2$, and every other cell holds $0$. The influence of the city is $1^2 \times 2 + 3^2 \times 4 + 2^2 \times 2 = 46$.

Given $N$ estimates, write a program that computes the influence of the city after all of them are applied.

The first line contains the number of estimates $N$ ($1 \le N \le 10^5$).

Each of the next $N$ lines contains $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$) separated by spaces. Each line is one estimate as described above.

Print the influence of the city after all estimates are applied. The answer can be very large, so print it modulo 1,000,000,007.