# 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 Protap_Ghose Cpp14 0.00s
03 nmunim Cpp14 0.00s
04 Robbinb1993 Cpp14 0.00s
05 MazedRupok Cpp14 0.01s
06 tariqiitju Cpp14 0.01s
07 eltonrawn Cpp14 0.01s
08 Reayz Cpp14 0.01s
09 SKL12 Cpp14 0.01s
10 feodorv Cpp14 0.01s
11 Dariwala Cpp14 0.01s
12 Sopto Cpp14 0.01s
13 Masum_ice Cpp14 0.01s
14 Knight_King Cpp14 0.01s
15 saiful130104 Cpp14 0.01s
16 CLown1331 Cpp14 0.01s
17 shaft Cpp14 0.01s
18 Double_O Cpp14 0.01s
20 ksohan Cpp14 0.01s
21 mamun4122 Cpp14 0.01s
22 sahedsohel Cpp14 0.01s
23 Tanmoy1228 Cpp14 0.01s
24 alhelal_cse Cpp14 0.01s
25 dmehrab06 Cpp14 0.02s
26 BishalG Cpp14 0.02s
27 Zeronfinity Cpp14 0.02s
29 PKP_007 Cpp14 0.02s
30 ssavi Cpp14 0.02s
31 AlirezaNa Cpp14 0.03s
32 n999 Cpp14 0.03s
33 Rajib_119 Cpp14 0.03s
34 Tanmoy_Datta Cpp14 0.04s