자동차 찾기

레스토랑에서 멋진 저녁을 보낸 뒤 집에 갈 시간이 되었다. 진정한 신사인 Leha는 Noora를 차로 데려다주겠다고 제안했다. 물론 소녀는 기쁘게 동의했다. 그런데 갑자기 한 가지 문제가 생겼다. Leha는 레스토랑 근처의 거대한 주차장에서 자신의 자동차를 찾을 수 없었다. 그래서 경비원에게 도움을 청하기로 했다.

형식적으로 주차장은 109 × 109 행렬로 나타낼 수 있다. 행렬의 모든 칸에는 정확히 하나의 자동차가 있다. 모든 자동차에는 양의 정수로 표현되는 고유한 차량 번호가 있다. 행렬의 열은 왼쪽에서 오른쪽으로 1부터 109까지의 정수로, 행은 위에서 아래로 1부터 109까지의 정수로 번호를 매기자. 우연히도 모든 칸 (x, y)에 대해, 이 칸에 있는 자동차의 번호는 칸 (i, y)과 (x, j)에서 찾을 수 없는 최소 양의 정수와 같다. 여기서 1 ≤ i < x, 1 ≤ j < y이다.

주차장의 왼쪽 위 5 × 5 부분

Leha는 자신의 자동차를 찾는 데 도움이 될 수 있는 q개의 요청을 경비원에게 하려고 한다. 각 요청은 다섯 정수 x1, y1, x2, y2, k로 표현된다. 경비원은 x1 ≤ x ≤ x2이고 y1 ≤ y ≤ y2인 행렬의 모든 칸 (x, y)을 살펴보고, 칸 (x, y)에 있는 자동차의 번호가 k를 초과하지 않으면 요청의 답에 칸 (x, y)에 있는 자동차의 번호를 더해야 한다. 각 요청마다 Leha는 경비원에게 이렇게 얻은 합을 알려 달라고 한다. 합이 상당히 커질 수 있으므로, 해커는 이를 109 + 7로 나눈 나머지를 계산해 달라고 한다.

하지만 이 요청들은 경비원이 처리하기에는 불가능해 보인다. 경비원이 Leha의 모든 요청에 답하도록 도와주자.

첫 번째 줄에 Leha의 요청 수인 정수 하나 q (1 ≤ q ≤ 104)가 주어진다.

다음 q개의 줄에는 Leha의 요청을 나타내는 매개변수인 다섯 정수 x1, y1, x2, y2, k (1 ≤ x1 ≤ x2 ≤ 109, 1 ≤ y1 ≤ y2 ≤ 109, 1 ≤ k ≤ 2·109)가 주어진다.

정확히 q개의 줄을 출력한다. 첫 번째 줄에는 첫 번째 요청의 답을, 두 번째 줄에는 두 번째 요청의 답을 출력하는 식으로 계속한다.

모든 요청을 분석해 보자. 각 경우에 요청된 부분 행렬은 파란색으로 강조되어 있다.

첫 번째 요청 (k = 1)에서 Leha는 주차장의 왼쪽 위 칸 하나만 묻는다. 이 칸에 있는 자동차의 번호는 1이다. 따라서 답은 1이다.

두 번째 요청 (k = 5)에서 조건에 맞는 번호는 4, 1, 2, 3, 2, 1이다. 따라서 답은 4 + 1 + 2 + 3 + 2 + 1 = 13이다.

세 번째 요청 (k = 10000)에서 Leha는 주차장의 왼쪽 위 5 × 5 부분을 묻는다. k가 충분히 크므로 답은 93이다.

마지막 요청 (k = 2)에서는 cur의 번호 중 어느 것도 조건에 맞지 않으므로 답은 0이다.