Count the permutation
Problem
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 109+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
Time Limit: 1
Memory Limit: 256
Source Limit:
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.
