Raju and Tushar are two best friends. They are fond of weird things, so they decided that they will go to visit the weird land called BruteForce Land every year once. When they went there they saw a lot of strange things but the strangest of all of them was this : The BruteForce Land has a language which has a total of n distinct letters and the value of n is huge compared to the number of letters we use(only 26)! And all the words are of length n having distinct letters. So, they went to the library for a part time job and discovered there a more stranger thing. There was a book which contains all possible words that can be made by the letters in BruteForce Land following the rules of word making described above . So, that book was humongous in size obviously. So, the two friends understood that there are so many unnecessary words there which are not used by the people of BruteForce Land. They decided to divide the words of that big book so that some unused words get deleted from there. The friends now decide to work like this : On their k th visit, Tushar takes 1 / k portion of the book containing both used and unused words and then Raju will take that 1 / k part of the book and take 1 / (k + 1) part of it and save those words in their database. So, at their first visit k was equal to 1, in the second visit k was 2 and so on. When the government notices this each year they replace all the letters with completely new n letters. Another thing that the two friends decided is they will visit the land strictly less than n times. Your task is to calculate the total number of words after m visits, saved in the database of Raju and Tushar. As it can be a huge number output your answer modulo 1000000007.

Input:
Input starts with an integer t (1 <= t <= 100000), denoting the number of test cases. Each case contains an integer n (2 ≤ n ≤ 100000) and an integer m (1 <= m < n) denoting the number of distinct letters BruteForce Land had.

Output:
For example, For each case of input, output the total number of words in the database of Raju and Tushar after their m th visit.