Counting stars
Tag(s):

## Combinatorics, Easy-Medium, Math, approved

Problem
Editorial
Analytics

There are N stars in the sky. A manual attempt at counting yielded K stars. It is possible that the same star may have been counted more than once. You need to determine the probability that any star may have been counted more than once. Probability can be represented as a rational number $\frac{\textstyle P}{\textstyle Q}$. If Q is not divisible by $10^9 + 7$ there is a unique integer $x \mid 0 \leq x \lt 10^9 +7$ where $P \equiv Qx$ $\%$ $(10^9 +7)$. Calculate value of this integer x.

Input Format:
First line of input consists of a single integer T denoting number of test cases.
Following T lines contain two space separated integers denoting N and K.

Output Format:
Print the answer to each test case in a new line.

Input Constraints:
$1 \le T \le 10$
$1 \le N, K \le 100000$

SAMPLE INPUT
1
3 3

SAMPLE OUTPUT
300000003

Explanation

There are 3 stars in the sky. Let's call them A, B and C.
Following are the different ways that Micro could have counted the stars.
$(A, A, A)$
$(B, B, B)$
$(C, C, C)$
$(A, A, B)$
$(A, B, B)$
$(A, A, C)$
$(A, C, C)$
$(B, B, C)$
$(B, C, C)$
$(A, B, C)$
So, clearly there are 9 out of $10$ ways, in which Micro counted any star more than once. So, probability is $\frac{9}{10}$, and $9 \equiv (10 \times 300000003) \% 10^9+7$. So $x = 300000003$.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

Darwinbox Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
• Data Structures > Arrays