In another test the terrorists have occupied CodeVillage. The village consists of N buildings. Each building is connected to every other building with a road. Each terrorist has been told to cover a single strip of K buildings along any path. A path is a set of roads connecting a particular set of buildings in which the buildings will not be repeated and every adjacent pair of roads share a common building.

Each terrorist will be given a distinct path. Two paths are different if at least one building is different or the order of visiting the buildings is different. For example a path from building numbers 1 → 2 → 3 is different from a path from building numbers 1 → 3 → 2.

Now so as to improve coordination between the terrorists, they had decided that every terrorist should meet all other terrorists along the path. Thus there should be at least one common building in every pair of paths.

Digo must take enough artillery to kill all the terrorists but not much more due to the ongoing recession problems. So help him calculate the maximum number of terrorists that may be present in the village. Give your answer modulo 10^9 + 7.

Input

The first line contains a single integer T denoting the number of test cases. T lines follow each containing two space separated integers N and K.

Output

For each test case output the maximum possible number of terrorists modulo 10^9 + 7.

Constraints

1 <= T <= 100000

1 <= K <= N <= 1000000

Sample

Input
2
3 2
5 3

Output
6
60