Sometimes, going shopping with grandma can be a very exciting and fun adventure! Eloi is going shopping with grandma this evening because of the holidays; just perfect for his saying: “Sewing, baking, and shopping with grandma, it all goes together... a grandmother, at holiday time, is worth gold.” They also are stopping at the pharmacy: granny is losing her memory and her bottle of memory pills is running low ... how sad! The memory pills come in two sizes: large and small. The dose in each large pill is equivalent to that in two small ones. Eloi observes granny picks a pill at random from the bottle every day: if it’s a small one, she takes it; otherwise, she splits it and takes a half, replacing the other which is from then on considered a small pill. Given a certain bottle with l large pills and s small pills, we say that the pair (l,s) is the bottle configuration. Eloi is interested in the pill tree associated with bottle config- uration (l,s), in which left or right branching represents a large or small pill being picked, respectively. Formally it’s the labeled binary tree with root (l, s) in which a node (u,v) has a left child (u−1,v+1) if u > 0 and a right child (u, v − 1) if v > 0. For example, the pill tree associated with bottle config- uration (2, 1) (2 large, 1 small) is depicted on the right: Eloi then asks himself: how many nodes does the pill tree associated with bottle configuration (l, s) have? Input The input consists of several test cases. Each test case consists of a line with two blank-separated integers l and s (0 ≤ l ≤ 1000 and 0 ≤ s ≤ 1000). The end of the input is given by l = s = 0, which should not be processed as a test case. Output For each l and s, output a line with the number of nodes in the pill tree associated to (l, s). Since this number can be very large, print it modulo 9 999 959 999. Sample Input 21 65 100 2 19 78 1000 1000 00
2/2 Sample Output 21 31654 5306431377 1942584859 4124225148