The outbreak of the COVID-19 has infected more than 50,000 people in Wuhan and nearly 70,000 people in Hubei province, which brings on great pressure on the local hospital and medical workers. To help the people in Hubei defeating the virus and returning to normal life as soon as possible, many other province deployed their medical teams to Hubei and offered lots of help.
Now it's the time for a hospital in Bitland to choose who will be sent to join this great mission. There are 
medical workers in the hospital ready to deploy and you can send arbitrary numbers of persons to the team. Also, a medical team need a captain in charge of all the work, so once we confirm the people in the team, we need to set one of them as captain too. However, being a captain needs a lot experience, so there are only 
people capable with the responsibility of a captain. Therefore, A team cannot be made up of people without someone that can be the captain.
And here's the question: How many ways are there to pick up a medical team with a captain? Notice that two teams are consider different as long as they have different participants or have different captain.
Also, due to the large memory of Bitland, the number of workers in hospital can be as large as 
! And that means your answer can be very large, so please output the result of the answer modulo 
.
输入描述:
The input consists of multiple test cases. The first line of the input contains an integer 
--- the number of the test cases.
For each test cases, there will be two integers , separated by space in one line, which means the number of workers in hospital and the numbers of people who can be the captain. Here 
.
输出描述:
For each test case, output a single integer 
in a line, denoting the answer modulo .