This year the students of MSIT worked really hard in order to make the college fest possible and managed everything in a really short amount of time.

The College thought of rewarding them by giving each and every student who contributed in the fest work, a T-Shirt with their name written on the back of the T-Shirt

So every T-Shirt will belong to exactly one person in the team (assume that all members of the team have distinct name)

The Responsibility of managing this was given to Utkarsh. Utkarsh asked Mayank to distribute the T-shirt to each member of the team with every person getting his own T-shirt. Unfortunately , Mayank is a really careless guy, he forgot that each T-shirt belongs to some particular person and he distributed random T-shirt to the team members.

After realizing his mistake, he went to every member personally to check whether they got their T-Shirt or not. So far he has checked K members out of N and found that none of the K members have received right T-shirt.

Utkarsh got very angry with this. In order to lower his anger he asked Mayank the following Question. "In how many different ways could the T-shirt have been distributed such that a wrong T-shirt went to each of the K team members that have been checked by you so far ?"

Two ways are considered different if at least one student gets a different T-shirt.

Help Mayank to answer the Question
Since the answer can be very large, return the answer modulo 1,000,000,007.

Constraint
1<=T<=100
1<=K<=N<=1000
1<=K<=12

Input
Input contains T , number of test cases, each test case contains two space separated number N and K

Output
Output a single number denoting the answer in every line