All Tracks Algorithms Dynamic Programming 2 Dimensional Problem

Count the permutation
/

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

Best Submission

Similar Problems

Contributors

Initializing Code Editor...
Notifications
View All Notifications

?