Once upon a time in a boring class of electronic systems, $$$\textit{Kifah}$$$ and $$$\textit{Ali}$$$ were sitting there talking about the problem set of Al-Baath contest. Kindhearted $$$\textit{Ali}$$$ came up with a cute probability problem and told $$$\textit{Kifah}$$$ about it. Since $$$\textit{Kifah}$$$ doesn't like cute problems, he couldn't prevent himself from making some changes to make it a little bit harder. And here is the problem.
In this problem, you will be given an array $$$a_1,a_2,...,a_n$$$. Imagine an array $$$b_1,b_2,...,b_n$$$ where $$$b_i \in [1, a_i]$$$ with a uniform distribution. A subarray of $$$b$$$ is one of its contiguous subsequences (i.e. an array $$$[b_l,b_{l+1},...,b_r]$$$ for some integers $$$l$$$ and $$$r$$$ such that $$$1 \le l \le r \le n$$$).
We define the function $$$f(l, r, x)$$$ of the subarray $$$[b_l,b_{l+1},...,b_r]$$$ as the probability of $$$max([b_l,b_{l+1},...,b_r]) \le x$$$.
You will be asked two types of queries:
It can be shown that this answer can always be expressed as a fraction $$$P/Q$$$ where $$$P, Q$$$ are coprime integers and $$$Q \neq 0 \bmod 10^9+7$$$. Output the value of $$$(P \cdot Q^{-1})$$$ modulo $$$10^9+7$$$.
The first line contains a single integer $$$Tc$$$ $$$(1 \le Tc \le 10^5)$$$ — the number of test cases.
The first line of each test case contains a single integer $$$n$$$ $$$(1 \le n \le 10^5)$$$ — the size of the array $$$a$$$.
The second line contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$ $$$(1 \le a_i \le 10^5)$$$.
The third line of each test case contains a single integer $$$q$$$ $$$(1 \le q \le 10^5)$$$ — the number of queries.
Each of the following $$$q$$$ lines has one of two types:
It is guaranteed that the sum of $$$n$$$ and $$$q$$$ over all test cases doesn't exceed $$$10^5$$$.
For each query of the type $$$2$$$, print $$$f(l, r, x)$$$.
131 2 321 2 62 1 3 3
500000004
1532 45 12 43 3652 1 5 172 2 4 131 3 10002 1 4 402 2 5 55
242668409 929198973 340051682 135000001
