Hard Divide and Conquer > Dynamic Programming

The laboratory of Microbiology department has been attacked by several robbers recently. They robbed and stole many valuable samples of viruses, bacteria, microorganisms. While being in hurry, they broke a tube. The tube contained sample of one of the most dangerous germs called Dangerm. The tube contained exactly one sample of each of the three species (namely Clu, Tron, Flynn) of Dangerm. During the research and test on the day before robbery, our students managed to discover that everyday each Clu turns into 12 Dangerms (3 Clus, 4 Trons and 5 Flynns), each Tron turns into 21 Dangerms (6 Clus, 7 Trons and 8 Flynns) and each Flynn turns into 30 Dangerms (9 Clus, 10 Trons and 11 Flynns). As Dangerm is very dangerous, scientists have set out a meeting and are planning to invent something called Dangkill to destroy all the Dangerms. They are expecting that the invention of Dangkill will take n days and for every thousand Dangerms, one Dangkill is needed. So to know how many Dangkills need to be prepared, scientists need to know how many Dangerms there will be on the nth day. Can you help them? Input: ------ Input starts with an integer T (T ≤ 1000) denoting the number of test cases. Each case contains a single integer n (1 ≤ n ≤ 1 000 000 000). Output: ------- For each case, print the number of Dangerms that will exist on the nth day modulo 1 000 000 009. Sample Input ------------ 4 1 2 3 1000 Sample Output ------------- 3 63 1377 358121526

Ariful Hoque Maruf