INV - Inversions

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

Added by:Spooky
Date:2009-04-13
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 DOC ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PDF PERL PHP PIKE PS PRLG-swi PYTHON RUBY SCM guile SCM qobi ST TEXT WHITESPACE

hide comments
2012-09-04 07:39:53 LE BEIER
can someone kindly explain to me is this problem about combination or is it about finding the inversion of the permutation?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.