Calculate the number of ways that k things can be 'chosen' from a set of n things.

Input

The first line of input is the number of tests t <= 100000. Next t lines contains two integers each n and k, separated with a single space. 0 <= k <= n <= 100000.

Output

For each test output the number of ways that k things can be 'chosen' from a set of n things modulo 1000000007.

Example

Input:
3
9876 5432
100 50
100000 50000

Output:
266875274
538992043
149033233