随机化游戏时间？
题号：NC277688
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

\,\,\,\,\,\,\,\,\,注：本题和 \sf hard 版本的区别在于排列已知，询问概率。
\,\,\,\,\,\,\,\,\,\,小 \mathcal L 有一个 1\sim n 的排列，她从中选择了一个数字作为自己的幸运数。
\,\,\,\,\,\,\,\,\,\,小 \mathcal H 每次会询问小 \mathcal L 一个区间 [l,r] ，随后小 \mathcal L 会告诉他这个区间里有多少个数小于等于她的幸运数。
\,\,\,\,\,\,\,\,\,\,直到 m 次询问全部完成，如果小 \mathcal H 依旧无法唯一确定幸运数是什么，他会在全部可能的数字里等概率随机挑选一个。
\,\,\,\,\,\,\,\,\,\,你需要直接输出 m 次询问后他猜对数字的概率，保证数据有解。

\,\,\,\,\,\,\,\,\,\,长度为 n 的排列是由 1 \sim n 这 n 个整数、按任意顺序组成的数组，每个整数恰好出现一次。例如，[2,3,1,5,4] 是一个排列，但 [1,2,2] 不是一个排列（数组中的 2 出现了两次），[1,3,4] 也不是一个排列（长度为 3 但数组中有 4）。

输入描述:

\,\,\,\,\,\,\,\,\,\,每个测试文件均包含多组测试数据。第一行输入一个整数 T\left(1\le T\le 200\right) 代表数据组数，每组测试数据描述如下：

\,\,\,\,\,\,\,\,\,\,第一行输入两个整数 n,m\left( 1\le n,m \le 10^5\right) 代表小 \mathcal L 的排列长度和最多询问次数。
\,\,\,\,\,\,\,\,\,\,第二行输入 n 个整数 a_1,a_2,\dots,a_n \left( 1\le a_i \le n\right) 代表排列元素，保证数字两两不同。
\,\,\,\,\,\,\,\,\,\,随后 m 行，每行输入三个整数 l,r,k\left(1\le l \le r \le n;\ 0 \le k \le r - l + 1 \right) 代表询问区间、区间内小于等于幸运数的数字个数。

\,\,\,\,\,\,\,\,\,\,除此之外，保证所有的 n 之和不超过 2\times 10^5 ，所有的 m 之和不超过 2\times 10^5 。
\,\,\,\,\,\,\,\,\,\,本题数据保证有解。

输出描述:

\,\,\,\,\,\,\,\,\,\,对于每一组测试数据，在一行上输出一个整数，代表小 \mathcal H 猜中幸运数的概率。特别的，如果概率为 100\% ，则需要在同一行上额外输出一个整数，代表小 \mathcal L 的幸运数。

\,\,\,\,\,\,\,\,\,\,可以证明答案可以表示为一个不可约分数 \frac{p}{q} ，为了避免精度问题，请直接输出整数 \left(p \cdot q^{-1} \bmod M\right) 作为答案，其中 M = (10^9+7) ，q^{-1} 是满足 q\times q^{-1} \equiv 1 \pmod{M} 的整数。
示例1

输入

复制 
2
6 2
5 6 4 3 2 1
5 6 2
1 2 0
5 3
5 4 2 1 3
1 3 1
5 5 1
3 5 3

输出

复制 
333333336
1 3

说明

\,\,\,\,\,\,\,\,\,\,对于第一组测试数据，初始时，幸运数的范围为 [1,6] 。
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,● [5,6] 区间有两个数字小于等于幸运数，可以将范围缩小至 [2,6] ；
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,● [1,2] 区间中没有数字小于等幸运数，可以将范围缩小至 [2,4] ；
\,\,\,\,\,\,\,\,\,\,综上，幸运数只有可能是 2 、3 或者 4 ，小 \mathcal H 会从这三个数字中随机挑选一个猜测，猜中的概率即为 \frac{1}{3} \bmod M 。

\,\,\,\,\,\,\,\,\,\,对于第二组测试数据，初始时，幸运数的范围为 [1,5] 。
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,● [1,3] 区间有一个数字小于等于幸运数，可以将范围缩小至 [2,3] ；
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,● [5,5] 区间有一个数字小于等于幸运数，可以唯一确定幸运数为 3 。