Time Limit: 1000 MS    Memory Limit: 65536 K 


Description

One day, Huang Yaoshi, Zhou Botong and Li Qiushui meet in SCU again. No contact for so many years, they all have a great progress in Kung Fu, and still can not differentiate who is the best in the world. So they ask the famous Lord Windy to decide. But in fact, it is also difficut for Lord Windy to know who is the best in the three young man in Kung Fu, so he make an ACM problem to differentiate who is clever for them, and the one who first solve it is the best in the world. The problem is this£º This year there are K students to participate in ACM competition. After the competion, every one of the K participants can get a rank between 1 and K, and there are no two students whose ranks are the same. To enable all the K students to have a harvest, the organizers decide to distribute apples to the K participants according to their ranks. At first the organizers buy N apples which are the same, and then distribute the N apples with the rules of this£º the number of apples each student gets can not be less than K+1-(his or her rank) and at last there is no apple left. For example: if N=4 and K=2, there are two different ways to distribute the apples, the first way is£º the one ranking 1 gets 3 apples and the one ranking 2 gets 1 apples, another is£º the one ranking 1 gets 2 apples, and so is the one ranking 2 get 2 apples. Now give the N and K, you just tell me after the competition, how many different ways to distribute the N apples to the K participants. Because the result may be very large, we make the result module 10009 for the output¡£ Huang Yaoshi, Zhou Botong ahd Li Qiushui can not solve the problem, they ask you to help them.

Input

The input contains many test cases ended with EOF. For each test case, the input contains only one line with two integers: N( 1 <= N <= 10^9 ) and K( 1 <= K <= 10^9 ), indicate the number of apples and the number of students.

Output

For each test case output the answer in a single line.

Sample Input

1 1 1 3 10 3 732239332 21023

Sample Output

1 0 15 2677

Source

8th SCUPC

Author

H×´Ôª