All Submissions


This BITOTSAV the core committee plans on arranging for crackers for the PRO Night. There are two types of crackers:FLASH crackers and ROCKETS.The flash crackers are instant, meaning each of these happen instantly at some moment in time.The rockets on the other hand take any positive amount of time.Different rockets take different amounts of time but none of the rockets are instant.
Now the core wants to fix an order for burning these crackers.They are not really interested in the exact times but the relative order instead.For example given a Rocket A and a Flash Cracker B the possible orderings are :
Order 1
i.Rocket A is ignited.
ii.Cracker B flashes.
iii.Rocket A burns off.

Order 2
i.A is ignited.
ii.B flashes and simultaneously A burns off.

Order 3
i.B flashes, simultaneously A is ignited.
ii.A burns off.

Order 4
i.B flashes.
ii.A is ignited.
iii.A burns off.

Order 5
i.A is ignited.
ii.A burns off.
iii.B flashes.

Given the number of Rockets and Flash crackers bought by core you need to calculate the number of orderings of these that are possible.The answer should be modulo 1,000,000,009.


Input Specifications
The input file consists of multiple test cases.Each test case consists of two numbers X and Y. X represents the number of Rockets and Y represents the number of Flash Crackers.Take the input till EOF.

Output Specifications
For Each test case print the number of orderings possible modulo 1,000,000,009 on a separate line.

Constraints
No. of test cases <= 30
Both X and Y will be between 0 to 1000(inclusive).
Both X and Y will never be 0 simultaneously.

Sample Input
0 2
1 1


Sample Output
3
5


Sample Explanation
Case 1:Let the Flash Crackers be A and B.
A before B.
A and b simultaneously.
A after B.

Case 2:explained above.

Problem Setter : Shradha Chhaparia

Languages: AWK,Bash,Brain,C,C++,Java,C#,JavaScript,Pascal,Perl,PHP,Python,Python3,Ruby,Text

Time Limit: 5 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0