# DCP-174: Troubles With Germs Back to All Problems

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

### Problem Limits

 Language Time Limit (seconds) C 1.00 C++ 1.00 C++14 1.00 C# 3.00 Go 3.00 Java 3.00 JavaScript 3.00 Objective-C 3.00 Perl 3.00 PHP 3.00 Python 3.00 Python3 3.00 Ruby 3.00 VB.Net 3.00

# 46/82

Solve/Submission

### Ranking

# User Language Timing
01 nasif2587 Cpp14 0.00s
02 nmunim Cpp14 0.00s
03 Protap_Ghose Cpp14 0.00s
04 Robbinb1993 Cpp14 0.00s
05 MazedRupok Cpp14 0.01s
06 eltonrawn Cpp14 0.01s
07 mamun4122 Cpp14 0.01s
08 Sopto Cpp14 0.01s
09 Masum_ice Cpp14 0.01s
10 Knight_King Cpp14 0.01s
11 Dariwala Cpp14 0.01s
12 shaft Cpp14 0.01s
13 ksohan Cpp14 0.01s
15 alhelal_cse Cpp14 0.01s
16 CLown1331 Cpp14 0.01s
17 sahedsohel Cpp14 0.01s
18 Tanmoy1228 Cpp14 0.01s
19 Reayz Cpp14 0.01s
20 tariqiitju Cpp14 0.01s
21 Double_O Cpp14 0.01s
22 SKL12 Cpp14 0.01s
23 saiful130104 Cpp14 0.01s
24 feodorv Cpp14 0.01s
25 ssavi Cpp14 0.02s
26 Zeronfinity Cpp14 0.02s
27 dmehrab06 Cpp14 0.02s
29 BishalG Cpp14 0.02s
30 PKP_007 Cpp14 0.02s
31 AlirezaNa Cpp14 0.03s
32 Rajib_119 Cpp14 0.03s
33 n999 Cpp14 0.03s