All Tracks Math Combinatorics Problem

Killjee And Sequence
Tag(s):

Medium-Hard

Problem
Editorial
Analytics

Killjee is very weak in mathematics and everyone is sure that he will fail in mathematics this year like previous years. Somehow killjee found the question of final exams and now he is asking for your help to solve the question.

$$$ S_{k} = \prod_{i = 0}^{r - 1} \binom{k - \frac{i \cdot (i +1)}{2}}{i + 1} $$$

$$$ SS = \sum_{k = \frac{r \cdot (r + 1)}{2}}^{n} \binom{n}{k} \cdot S_{k} $$$

Compute $$SS$$.

Input:

First line of input contains a single integer $$T$$ denoting the number of test cases. Each of the next $$T$$ lines contains $$2$$ integers, $$n$$ and $$r$$, as described in the problem statement.

Output:

Print the answer to each query modulo $$10^{10}+19$$.

Constraints:

$$1 \le T \le 10$$

$$1 \le n \le 10^{18}$$

$$1 \le r \le 2000$$

SAMPLE INPUT
2
8 3
9 3
SAMPLE OUTPUT
6720
40320
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++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

Notifications
View All Notifications