CF809C.Find a car

After a wonderful evening in the restaurant the time to go home came. Leha as a true gentlemen suggested Noora to give her a lift. Certainly the girl agreed with pleasure. Suddenly one problem appeared: Leha cannot find his car on a huge parking near the restaurant. So he decided to turn to the watchman for help.

Formally the parking can be represented as a matrix 109 × 109. There is exactly one car in every cell of the matrix. All cars have their own machine numbers represented as a positive integer. Let's index the columns of the matrix by integers from 1 to 109 from left to right and the rows by integers from 1 to 109 from top to bottom. By coincidence it turned out, that for every cell (x, y) the number of the car, which stands in this cell, is equal to the minimum positive integer, which can't be found in the cells (i, y) and (x, j), 1 ≤ i < x, 1 ≤ j < y.

The upper left fragment 5 × 5 of the parking

Leha wants to ask the watchman q requests, which can help him to find his car. Every request is represented as five integers _x_1, _y_1, _x_2, _y_2, k. The watchman have to consider all cells (x, y) of the matrix, such that _x_1 ≤ x ≤ _x_2 and _y_1 ≤ y ≤ _y_2, and if the number of the car in cell (x, y) does not exceed k, increase the answer to the request by the number of the car in cell (x, y). For each request Leha asks the watchman to tell him the resulting sum. Due to the fact that the sum can turn out to be quite large, hacker asks to calculate it modulo 109 + 7.

However the requests seem to be impracticable for the watchman. Help the watchman to answer all Leha's requests.

在餐厅度过了一个美妙的夜晚后，到了回家的时间。Leha 作为一名真正的绅士，主动提出送 Noora 回家。女孩当然欣然同意。突然出现了一个问题：Leha 在餐厅附近巨大的停车场里找不到自己的车。于是他决定向看守员求助。

形式化地，该停车场可表示为一个 $10^9 \times 10^9$ 的矩阵。矩阵中每个格子恰好停有一辆车。每辆车都有一个用正整数表示的车牌号。我们从左到右将矩阵的列编号为 $1$ 到 $10^9$，从上到下将行编号为 $1$ 到 $10^9$。巧合的是，对任意格子 $(x, y)$，其中停放的车辆的车牌号等于最小的正整数，该整数不出现在所有格子 $(i, y)$（其中 $1 \le i < x$）和 $(x, j)$（其中 $1 \le j < y$）的车牌号中。

停车场左上角 $5 \times 5$ 区域

Leha 想向看守员提出 $q$ 个查询请求，以帮助他找到自己的车。每个请求由五个整数 $x_1,\ y_1,\ x_2,\ y_2,\ k$ 表示。看守员需考察矩阵中所有满足 $x_1 \le x \le x_2$ 且 $y_1 \le y \le y_2$ 的格子 $(x, y)$；若格子 $(x, y)$ 中车辆的车牌号不超过 $k$，则将该车牌号加到该查询的答案中。对每个请求，Leha 要求看守员返回最终的总和。由于总和可能非常大，黑客要求将结果对 $10^9 + 7$ 取模。

然而，这些查询对看守员而言似乎难以直接完成。请帮助看守员回答 Leha 的所有查询。

The first line contains one integer q (1 ≤ q ≤ 104) — the number of Leha's requests.

The next q lines contain five integers _x_1, _y_1, _x_2, _y_2, k (1 ≤ _x_1 ≤ _x_2 ≤ 109, 1 ≤ _y_1 ≤ _y_2 ≤ 109, 1 ≤ k ≤ 2·109) — parameters of Leha's requests.

第一行包含一个整数 $q$（$1 \le q \le 10^4$）—— 表示 Leha 的请求次数。

接下来的 $q$ 行每行包含五个整数 $x_1,\ y_1,\ x_2,\ y_2,\ k$（$1 \le x_1 \le x_2 \le 10^9$，$1 \le y_1 \le y_2 \le 10^9$，$1 \le k \le 2 \cdot 10^9$）—— 表示 Leha 请求的参数。

Print exactly q lines — in the first line print the answer to the first request, in the second — the answer to the second request and so on.

精确输出 q 行——第一行输出第一个查询的答案，第二行输出第二个查询的答案，依此类推。

Let's analyze all the requests. In each case the requested submatrix is highlighted in blue.

In the first request (k = 1) Leha asks only about the upper left parking cell. In this cell the car's number is 1. Consequentally the answer is 1.

In the second request (k = 5) suitable numbers are 4, 1, 2, 3, 2, 1. Consequentally the answer is 4 + 1 + 2 + 3 + 2 + 1 = 13.

In the third request (k = 10000) Leha asks about the upper left frament 5 × 5 of the parking. Since k is big enough, the answer is equal to 93.

In the last request (k = 2) none of the cur's numbers are suitable, so the answer is 0.

我们来分析所有请求。在每种情况下，所请求的子矩阵均以蓝色高亮显示。

在第一个请求（$k = 1$）中，Leha 仅询问左上角的停车位。该车位中的汽车编号为 1，因此答案为 1。

在第二个请求（$k = 5$）中，满足条件的数字为 $4,\,1,\,2,\,3,\,2,\,1$，因此答案为 $4 + 1 + 2 + 3 + 2 + 1 = 13$。

在第三个请求（$k = 10000$）中，Leha 询问的是停车场左上角 $5 \times 5$ 的区域。由于 $k$ 足够大，答案为 93。

在最后一个请求（$k = 2$）中，没有任何汽车编号满足条件，因此答案为 0。