Playing with Combinatorics
All submissions for this problem are available.
John likes playing with combinatorics. One day he comes across a strange formula. He defines a sum as :
Help John to find the value of this sum, for a given value of N. Since, the sum can be large, print its value modulo 109
Note : "nCk" is the number of combinations of k elements in n elements.
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first and only line of each test case contains a single integer N.
For each test case, output a single line containing (sum % 109), the required answer to the problem.
1 ≤ T ≤ 100
1 ≤ N ≤ 10100000
Input: 3 3 5 97 Output: 8 24 110338050
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.