One day, Touma Kazusa encountered a easy math problem. Given n and k, she need to calculate the following sum modulo $1e9+7$. $$∑_{i=1}^n∑^n_{j=1}gcd(i,j)^klcm(i,j)[gcd(i,j)∈prime]%(1e9+7) $$ However, as a poor student, Kazusa obviously did not, so Touma Kazusa went to ask Kitahara Haruki. But Kitahara Haruki is too busy, in order to prove that he is a skilled man, so he threw this problem to you. Can you answer this easy math problem quickly?
input
There are multiple test cases.$（T=5）$ The first line of the input contains an integer$T$, indicating the number of test cases. For each test case: There are only two positive integers n and k which are separated by spaces. $1≤n≤1e10$ $1≤k≤100$
###descirption You are given an array $a_1,a_2,…,a_n(∀i∈[1,n],1≤a_i≤n)$. Initially, each element of the array is unique.
Moreover, there are m instructions.
Each instruction is in one of the following two formats:
(1,pos),indicating to change the value of $a_{pos}$ to $a_{pos}+10,000,000$;
(2,r,k),indicating to ask the minimum value which is not equal to any $a_i$ ( 1≤i≤r ) and not less than k.
Please print all results of the instructions in format 2.
###input The first line of the input contains an integer T(1≤T≤10), denoting the number of test cases.
In each test case, there are two integers n(1≤n≤100,000),m(1≤m≤100,000) in the first line, denoting the size of array a and the number of instructions.
In the second line, there are n distinct integers $a_1,a_2,…,a_n (∀i∈[1,n],1≤a_i≤n)$,denoting the array. For the following m lines, each line is of format $(1,t_1) or (2,t_2,t_3)$. The parameters of each instruction are generated by such way :
For instructions in format 1 , we defined $pos=t_1⊕LastAns$ . (It is promised that 1≤pos≤n)
For instructions in format 2 , we defined $r=t_2⊕LastAns,k=t_3⊕LastAns$. (It is promised that 1≤r≤n,1≤k≤n )
(Note that ⊕ means the bitwise XOR operator. )
Before the first instruction of each test case, LastAns is equal to 0 .After each instruction in format 2, LastAns will be changed to the result of that instruction.
(∑n≤510,000,∑m≤510,000 )
###output For each instruction in format 2, output the answer in one line.
###hint note: After the generation procedure ,the instructions of the first test case are : 2 1 1, in format 2 and r=1 , k=1 2 3 3, in format 2 and r=3 , k=3 2 3 2, in format 2 and r=3 , k=2 2 3 1, in format 2 and r=3 , k=1 2 4 1, in format 2 and r=4 , k=1 2 5 1, in format 2 and r=5 , k=1 1 3 , in format 1 and pos=3 2 5 1, in format 2 and r=5 , k=1 2 5 2, in format 2 and r=5 , k=2
the instructions of the second test case are : 2 7 2, in format 2 and r=7 , k=2 1 5 , in format 1 and pos=5 2 7 2, in format 2 and r=7 , k=2 2 8 9, in format 2 and r=8 , k=9 1 8 , in format 1 and pos=8 2 8 9, in format 2 and r=8 , k=9
the instructions of the third test case are : 1 10 , in format 1 and pos=10 2 8 9 , in format 2 and r=8 , k=9 1 7 , in format 1 and pos=7 2 4 4 , in format 2 and r=4 , k=4 1 8 , in format 1 and pos=8 2 5 7 , in format 2 and r=5 , k=7 1 1 , in format 1 and pos=1 1 4 , in format 1 and pos=4 2 10 10, in format 2 and r=10 , k=10 1 2 , in format 1 and pos=2
###descirption Tom has a string containing only lowercase letters. He wants to choose a subsequence of the string whose length is k and lexicographical order is the smallest. It’s simple and he solved it with ease. But Jerry, who likes to play with Tom, tells him that if he is able to find a lexicographically smallest subsequence satisfying following 26 constraints, he will not cause Tom trouble any more. The constraints are: the number of occurrences of the ith letter from a to z (indexed from 1 to 26) must in $[L_i,R_i]$. Tom gets dizzy, so he asks you for help.
###input The input contains multiple test cases. Process until the end of file. Each test case starts with a single line containing a string $S(|S|≤10^5)$and an integer k(1≤k≤|S|). Then 26 lines follow, each line two numbers$ L_i,R_i(0≤L_i≤R_i≤|S|)$. It’s guaranteed that S consists of only lowercase letters, and $∑|S|≤3×10^5$.
###output Output the answer string. If it doesn’t exist, output −1.
###descirption hough time passes, there is always someone we will never forget. “The probability of being hit by a meteor is one in a billion, but it is much more miraculous, to meet you in my life.” said Tom to Jerry with affection. “One in a billion? I may not agree with you.” answered Jerry proudly, “Let’s do the math.” … Thinking of the days they have happily spent together, Tom can’t help bursting into tears. Though Jerry has been gone for a long time, Tom still misses him every day. He remembers it was a sunny afternoon when Jerry and him were lying in the yard, working on the probability of a man being hit by a meteor. Unlike Jerry, he was always slow. Jerry got the answer soon, but Tom was stuck as usual. In the end, Tom lost patience and asked Jerry to tell him the answer. “I can’t be so straightforward,” snickered Jerry, “the only thing I will tell you is that the answer is $\frac{p}{q}$, where p,q≤n,gcd(p,q)=1.” “Is it $\frac{1}{n}$?” “Is it $\frac{1}{n-1}$?” … If answered “No” , he would try the minimum larger number that satisfies the requirement. Tom only remembered n given by Jerry, and k, the times that he tried, but forgot what matters the most: Jerry’s answer. Now, he wants you to help him find it.
###input The first line contains an integer $T(T≤10^2)$, the number of test cases. The next T lines, each line contains two number$s, n,k(2≤n≤10^6)$, indicating a query. The answer is guaranteed to be in (0,1].
###output T lines, each line contains a fraction in term of p/q ,where gcd(p,q)=1.