F: A Fibonacci Family Formula Source file name: family.c, family.cpp, family.java, or family.py Author: Rafael García Everybody knows about Leonardo Fibonacci, the inventor of the famous sequence where the first two terms are 1 and from then on every term is calculated as the sum of the previous two terms. There is a tradition in the Fibonacci family since the 12th century: when a member is about to become 21 years of age, the family formulates a new sequence in which an extra summation term is added to the last version of the sequence. Then, during the birthday party, everybody has fun asking the new adult random terms in the newly designed sequence. Of course, the sequence that started this tradition is 1, 1, 1, 1, 1, 1, . . . . The second sequence, and most fa- mous one, is 1,1,2,3,5,8,.... The third formulated sequence is 1,1,2,4,7,13,.... And the fourth one is 1,1,2,4,8,15,.... Your friend Leonardo is 20 and will be the kth family member to celebrate a birthday under this tradition. He is very stressed because he has not found enough time to study the sequence that will be designed for his birthday. However, he has found a paper in his father’s office with the following equation: (k) 0 fn =1 f(k) + f(k) +···+ f(k) n−1 n−2 n−k , if n < 0 ,ifn=0 ,ifn≥1. Leonardo is certain that this equation describes the nth term in the kth sequence of the tradition, but he is not sure how to quickly calculate such terms. Your task is to help Leonardo by writing a program he can use during his birthday party: when asked for a term, he wishes to answer swiftly. Input The input consists of several test cases. A case consists of a line containing two blank-separated integers k and n with 1 ≤ k ≤ 100 and 0 ≤ n ≤ 1015. The input ends with two blank-separated zeroes. The input must be read from standard input. Output For each test case, output one line with the nth term in the kth sequence, namely, with the value of f (k). Since the terms can become very big, your program should calculate the results modulo 1 000 000 009. The output must be written to standard output. n
2018 ACIS REDIS - XXXII Colombian Programming Contest - ACM ICPC 11 Sample Input 55 34 23 70 00 Sample Output 16 7 3 1