题目描述

众所周知，CN－001 是神一般的存在。 CN－001给了你一个 $n$ 阶排列 $\left\{a_{i}\right\}$ ，并向你提出了 $q$ 次询问。每次询问 CN－001 会给出四个参数 $l_{1}, r_{1}, l_{2}, r_{2}\left(1 \leq l_{1} \leq r_{1}<l_{2} \leq r_{2} \leq n\right)$ ，且 $r_{1}-l_{1}=r_{2}-l_{2}$ 。记 $m=r_{1}-l_{1}+1$ ，你需要构造一个 $m$ 阶排列 $\left\{b_{j}\right\}$ 并满足：$\forall j \in[1, m], a_{j+l_{1}-1}<a_{b_{j}+l_{2}-1 \text { 。 }}$ $\mathrm{CN}-001$ 并不满足于让你构造出一个 $\left\{b_{j}\right\}, \mathrm{Ta}$ 想让你算一下满足条件的的 $\left\{b_{j}\right\}$ 的数量。 由于 CN－001 崇尚秩序， Ta 对＂逆序对＂这类事物不感兴趣，因此排列 $\left\{a_{i}\right\}$ 中的逆序对数不会太多，具体来说，就是满足 $1 \leq x<y \leq n$ 且 $a_{x}>a_{y}$ 的二元组 $(x, y)$ 的数量不会超过 $10^{5}$ 。

由于答案可能很大，CN－001 不想太为难你，于是 Ta 只要你输出答案对 $10^{9}+7$ 取模的结果。

输入格式

单个测试点中包含多组测试数据。输人的第一行包含一个整数 $T$ ，表示测试数据的组数。

对于每组数据，第一行包含两个整数 $n$ 和 $q$ 。 第二行包含 $n$ 个整数，表示排列 $\left\{a_{i}\right\}$ 。 接下来 $q$ 行，每行包含 4 个整数 $l_{1}, r_{1}, l_{2}, r_{2}$ ，表示一次询问。

输出格式

共 $q$ 行，每行一个数，表示一次询问的答案对 $10^{9}+7$ 取模后的结果。

输入样例1

3
4 1
1 2 3 4
1 2 3 4
4 2
1 3 2 4
1 1 2 2
1 2 3 4
10 1
1 4 3 2 9 5 6 7 10 8
1 5 6 10

输出样例1

2
1
1
24

样例 2

见选手目录下的 god2．in 和 god2．ans。

数据范围

记 $\sum n, \sum q$ 分别表示单个测试点中各组测试数据的 $n, q$ 之和。 对于 $20 \%$ 的数据，$n \leq 10$ 。 对于 $50 \%$ 的数据，$n \leq 1000$ 。 对于 $100 \%$ 的数据， $1 \leq T \leq 10,1 \leq \sum n, \sum q \leq 10^{5}$ ，排列 $\left\{a_{i}\right\}$ 的逆序对数不超过 $10^{5}$ 。 数据很弱，欢迎水过。