Four-tuples

题号：NC15932
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 64 M，其他语言128 M
64bit IO Format: %lld

题目描述

Given $l_{1},r_{1},l_{2},r_{2},l_{3},r_{3},l_{4},r_{4}$ ,please count the number of four-tuples $(x_{1},x_{2},x_{3},x_{4})$ such that $l_{i} \leq x_{i} \leq r_{i}$ and $x_{1} \ne x_{2},x_{2}\ne x_{3},x_{3}\ne x_{4},x_{4}\ne x_{1}$

The answer should modulo10⁹+7 before output.

输入描述:

The input consists of several test cases. The first
line gives the number of test cases,T(1≤T≤10⁶).

For each test case, the input contains one line
with 8 integers,.

输出描述:

For each test case, output one line containing one
integer, representing the answer.

示例1

输入

复制

1
1 1 2 2 3 3 4 4

输出

复制