Compute's Matrix
题号：NC221056
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

Compute 有一个大小为 的特殊矩阵。使用 (i,j) 表示矩阵中的第 i 行第 j 列的位置，则在这个特殊矩阵中，每个位置 (i,j) 对应的元素值恰为 。

现在，Compute 给你若干个符合上述规定的特殊矩阵，以及坐标 (x_1,y_1) 和 (x_2,y_2)。 你需要帮他计算一下，以上述坐标作为左上角和右下角的子矩阵中，所有元素的和为多少。

由于和可能非常的大，你只需要输出它对 取余后的结果即可。

输入描述:

第一行是一个整数 T ，代表有 T 组测试数据。

接下来 T 行，每行有 5 个整数，n,x_1,y_1,x_2,y_2 ，, ，分别表示特殊矩阵的大小，子矩阵的左上角坐标 (x_1,y_1) 和右下角坐标 (x_2,y_2) 。

输出描述:

输出 T 行，每行输出一个整数代表子矩阵的和对  取余后的结果。
示例1

输入

复制 
2
2 1 2 2 2
500 1 1 500 500

输出

复制 
6
687562395