All Tracks Algorithms Dynamic Programming 2 Dimensional Problem

Count the permutation
Tag(s):

Algorithms, Dynamic Programming, Easy-Medium, Two dimensional

Problem
Editorial
Analytics

You are given two numbers, namely A and S.

Write a program to find the number of ways in which the numbers that are greater than or equal to S can be added to get the sum A. Print the result as modulo \(10^9 + 9\).

Input format

  • First line: T (Number of test cases)
  • First line in each test case: Two space-separated integers A and S

Output format

For each test case, print the number of ways to acquire the sum A using the numbers that are greater than or equal to S.

Constraints

1 ≤ T ≤ 1000
1 ≤ A , S ≤ 1000

SAMPLE INPUT
4
2 1
3 1
4 5
750 466
SAMPLE OUTPUT
2
3
0
1
Explanation

In the first test case: <1, 1> and <2> are the 2 ways.

In the second test case: <1,1,1>, <1,2> and <3> are the three ways.

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: Bash, 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, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

Notifications
View All Notifications

?