SOLVE

LATER

Killjee And Sequence

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$$

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,
Visual Basic

Initializing Code Editor...

{"a4d814a": "/pagelets/problem-author-tester/algorithm/killjee-and-sequence/", "139bdc1": "/pagelets/suggested-problems/algorithm/killjee-and-sequence/", "d290d37": "/pagelets/problems-hint/algorithm/killjee-and-sequence/", "4c3535d": "/pagelets/recommended-problems/algorithm/killjee-and-sequence/", "7be7ce5": "/pagelets/show-submission/algorithm/killjee-and-sequence/"}

realtime.hackerearth.com

80

7c0d7a680b77cff2420459e09024ff970571c264

58a29e5cae2309f04b28

/realtime/pusher/auth/