Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Counting Subsets

By timelord · Limits 1s, 512 MB

Mr. Meseeks has just turned evil and is on his way to destroy the universe. To stop him Rick and Morty need to buy some time and keep him busy. So, Morty gives Mr. Meseeks a set A with n elements and tells him to make k non-empty sets B1, B2, ... Bk - 1, Bk such that Bk ⊆ Bk - 1⊆ Bk - 2 ⊆...B1⊆ A.


Rick wonders in how many ways Mr. Meseeks can make the sets. Now, Given n and k, your task is to help Rick determine that.

Input

Input starts with an integer T, denoting the number of test cases. Each of the next T lines contain two integers n and k as stated in description.

Constraints

1 <= T <= 100000

1 <= n <= 2000000000

1 <= k <= 2000000000

Output

For each case, you have to print the number of ways Mr. Meseeks can make the sets modulo 1000000007.

Sample

InputOutput
2
3 1
2 3
7
7

Explanation of Case 2.


Let A = {a, b}


Then the possible ways are -


{a} ⊆ {a} ⊆ {a} ⊆ {a, b}

{a} ⊆ {a} ⊆ {a, b} ⊆ {a, b}

{a} ⊆ {a, b} ⊆ {a, b} ⊆ {a, b}

{b} ⊆ {b} ⊆ {b} ⊆ {a, b}

{b} ⊆ {b} ⊆ {a, b} ⊆ {a, b}

{b} ⊆ {a, b} ⊆ {a, b} ⊆ {a, b}

{a, b} ⊆ {a, b} ⊆ {a, b} ⊆ {a,b}

Discussion

Statistics


67% Solution Ratio

fsshakkhorEarliest, Apr '20

curly_bracesFastest, 0.0s

fsshakkhorLightest, 1.0 MB

bokaifShortest, 95B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.