#include <iostream>
using namespace std;
#define mod 1000000009
unsigned long long dp[1000001]={0};
int main() {
dp[0]=1;
dp[1]=0;
dp[2]=1;
dp[3]=1;
for(int i=4;i<1000001;i++){
dp[i]=dp[i-2]+dp[i-3];
dp[i]%=mod;
}
int t;
cin>>t;
while(t--){
int n;
cin>>n;
cout<<dp[n]<<endl;
}
}
I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwojZGVmaW5lIG1vZCAxMDAwMDAwMDA5CnVuc2lnbmVkIGxvbmcgbG9uZyBkcFsxMDAwMDAxXT17MH07CmludCBtYWluKCkgewoJZHBbMF09MTsKICAgZHBbMV09MDsKICBkcFsyXT0xOwpkcFszXT0xOwpmb3IoaW50IGk9NDtpPDEwMDAwMDE7aSsrKXsKZHBbaV09ZHBbaS0yXStkcFtpLTNdOwpkcFtpXSU9bW9kOwp9CmludCB0OwpjaW4+PnQ7CndoaWxlKHQtLSl7CmludCBuOwpjaW4+Pm47CmNvdXQ8PGRwW25dPDxlbmRsOwp9Cn0=
MTAwMAoyCjkKMTEyCjk4OQo3NjMKNjk1CjI4OAo2ODMKNjE4CjIzNgozNDcKOTY0CjE2MQo5MzIKMzM0CjkyOAo2NzAKMjAKODA5CjYzNgo5OAo1NDIKODAzCjE0Mwo5NjcKNTI1CjY1OAo2ODkKNTM4CjE5Mgo3NTIKNDU1CjMKNTM1CjU3NAoyMzEKOTgxCjgyOAo1OTEKMjUwCjk1NgoxMzAKNjgwCjI3MAozMjUKNzQ2CjU0NwoxNjYKNzQ3CjQ4Mwo3NTAKNzA2CjE0Ngo3NTMKOTUxCjczNAoxMjcKMjA3CjUxNwoyNDkKNzcxCjExMQo3OTYKODc4CjMyNgo4MjcKMjY5CjQxNwozNzIKMzM5Cjk4MQo5MDMKNzQ3CjIzCjM3MAoyNzcKNjg5CjY4Ngo5NzUKODYyCjEyNQoyMzAKODA5CjM1CjcwMAoxMjQKMTc2CjQ2Mwo1MTkKOTA0CjI3OAoyMzMKOTU0CjY4OQozNTIKMzQ1CjM5CjE1Nwo4NDYKMTkxCjIxMAo3MDQKNTk5CjcKMjU1CjU0Nwo4NDEKNjUyCjQ5CjQ1OQo2MAo3ODgKMzg2CjI3Mgo4MzAKNzEyCjQKOTY3Cjk1NQozNjMKNjE0CjI4Mgo0MjUKMjIyCjI4Mwo1MzkKNzg4CjM0Nwo2OQo0NzkKOTU2CjYwMQoxMzEKMjM3Cjc4Nwo1MjAKNDI4CjEzNAo0MDMKMzA3CjEzOQo0ODgKODQ4CjI5OQo1MDAKMjQ1CjM4NAo1NDkKODkxCjQxNAozMjkKNDU0CjY4NAoyNDAKNzcxCjU0OAo4MjUKMTcxCjk4MQo2OTYKMzI3CjQzMgo0Cjk5Mgo2NjcKMjMwCjUzMwozNDgKOTg2CjM1NQo0NzYKNDQ2CjU1Mwo3ODMKNzY5Cjk5MQo3NjUKODE3CjMxNgo1NDUKODIzCjM0NQozNzQKNjgyCjc4Mwo2MTUKNDYyCjYzCjc5CjQ2MQo1MzMKMgo3MzgKNzA2CjU3NQo1NjIKOTQxCjM0NQo4MDEKNTc1CjI0MwozNAo4MzAKOTU3Cjk2MAo3ODAKNTk0Cjg1NwoyOAozMTIKNzc3CjQzOQo4NzAKMzA4Cjc5MgoxMTYKODI0CjUwNQo1NTMKMjA2CjM4OQo1OTcKOTY3CjE3NAo3MzcKMTI3CjcyOQo5OTUKNjQxCjc4OAo2NDUKMzYKNDMKMzQxCjI5MwoxNTAKMjY4CjExMAo4MzcKNDEwCjI5CjQ2NAoxMDUKNjUyCjYyOQoyMjgKMTY5CjMwNAo5MzMKOTU3CjY4Mgo4ODMKOTUyCjk0Nwo5MTQKNjE0CjkzMQoyMgo4MzYKOTA4CjQ1NAozMzkKNzA0CjMzNAo5MzUKNTc5CjY4NAo3MzgKNzg0CjU4MAo1MDMKNDA4CjkxNgo4ODUKOTc1CjgxNQo3NzYKMTU2CjcxMgo5OTUKNjE5CjUwMgo2NDcKMzM5CjI5OAoyMDEKMjA4CjY5MwozMjkKNDA5Cjg3Ngo0NAo0NDIKNTM2CjIyNAo2MAo2MzgKMTU4CjU3Ngo1MzQKODY4CjQyNQo0MTQKMAo1OTIKMzc3CjYwNwozMzEKOTQKOTg1CjMzNwoyNzUKNjA3CjYzNwo2Ngo1MTgKMTQ2CjIzNQo0ODIKNDkyCjQ2OQoyNjEKNDA2Cjg2Ngo0OTgKNzk1CjY5CjU3NgoyODEKOTQyCjg0NAo2NjUKODQxCjUyNAo5MTMKMzEKMTI2CjEyMAoxMTAKNTk5CjQ0MAoyNTIKOTk1CjI0NQo2MjAKNzQ5Cjg1NAo0MjYKNzg5CjIwMgo5MTAKNjgzCjY5NwoyMDEKOTM5Cjc1Mgo2NDkKMjU5CjIwNQoyMzQKOTYxCjIyNQo1ODQKNjYKMTA5CjE0CjM5MQoxNTQKMjM5CjUzNwo5MjMKMTQwCjY4MAo5NDcKNTQ3CjQxMAoyNAoyMTUKNDM4CjgyMQo5NQo4NDYKMzQ1CjgzOAo0OTEKNTIxCjkwOQo3MzIKMjUxCjgzOAo3MjAKMjE4CjQzNAo1MzAKNDcwCjU5Nwo4NzcKMTk0CjI3Nwo3NTcKMjM1CjU0NQo2NjYKNjgxCjY4CjExOAoxMjEKNzU4CjU1Nwo1NzEKOTUKMTk4CjY4NwoxNTQKMjc1CjMxOQozOQo3ODUKOTIwCjIyOAo2MjcKNDQxCjU5MAoyMjgKNzg2CjcwNAozNTUKMjc4CjI2MQoxOTYKODM5CjE5OAo0MzEKNjA5Cjg0MAoxMjgKMzU2Cjg0NQo4NTYKODc2CjMyMwo0MTIKMzY0Cjk1Cjk0NAo0NjgKNjgyCjY2Nwo2OTIKOTM0CjQ2NQo1NjMKNDIwCjMxNAo0NjcKNTY5CjYwOQo4NDIKMjgyCjYyNAozNDcKMjM1CjYyMAoxMzYKMzMxCjE5Ngo4MzkKNTI0CjExNwo0NDQKMjc1CjcwMgoxMTgKMzM5Cjg0Mgo0MjAKNjk3CjE4NwozNjAKNTEzCjg0MAo3MzcKMzQ4CjE2OAoyOTIKNzk0CjQwOAo1NjYKMTY4CjE4NAo1MDAKMjkKMzg4CjgKMzg2CjQ2Mgo0MQo1OTUKMjI2CjgyMgo5MTEKMzk5CjI4NQoxMTIKNDU4CjI2MAo0NDAKNjM1CjczMwoyODYKODkxCjk3MQo0Mwo3MjIKNTgyCjMyMgoyMzcKNTgKMTQ5CjU3OQo2MTYKMjA0CjQyCjk3MQo3NjMKNjM4CjQ1OQoxMDIKNzk2CjQ5Ngo0MzQKODczCjI2MgozOTYKMjAxCjUxMQoyOTcKMTA4CjIwMQo3CjkzNQoxNzUKMzM2CjQzOQo4NjkKNTYyCjUwOQoxMDgKODIyCjk4OQoxNDgKMzMKNDY3CjE3MQo5MDkKMTYzCjgyNgo5OTAKODAyCjMxMwo1NDMKMzMKMzE5CjUyMAo3NzcKOQo1Mgo0NzgKODE1CjMzMwo4NDIKMTEyCjI2MQo1NjYKNjg4CjYwNQo0NjkKMTY5Cjc3Mwo5MjkKNzY3CjE5MAo5Nwo1MAoyNjUKNzUwCjM4Mgo1NTQKODU2CjUzOAoyMzYKMTczCjg5Nwo1NDMKNDQ4CjI5Nwo0NDQKOTc2CjI5NQo1MzkKNTMxCjU0NQoyOTkKNzgxCjUzCjc5MAo2NzAKODU3CjEzNQo3OTUKNTc1Cjc3NgozMTEKMTQzCjg4OAoyMzAKNTczCjgxOAoyODUKMTU1Cjk0Nwo3MTMKNDk5CjQ0CjI3CjYyNAoyNTMKMjUKNjY3Cjg5OQo5NjAKMjU3CjM3NQo4NzIKNTY1CjEzNQo5MTcKOTg0CjQ5MQoyNQoxMTkKNzA4CjUyMgo5MTYKNzM2CjgKOTExCjQ4CjQyMgoyNTcKNTg1CjQ1NAo2OTYKNzY4Cjg3NAoxMDMKMjk2Cjk3MAo5NzgKMTI0CjIzMAo5NzcKMTk4CjkwOQo3OAozMzIKNDU2Cjc1OQo3MTkKNjAKMjMKMTk4CjYxMQoxNDQKNTI5CjQwNgo4NQo1NDAKMzgKOTgyCjI0NAo3MDUKNTM0CjE0Nwo2NTMKMzA5CjEyNAo4MQo1NDUKMTQKNDIzCjQ3Mwo2MDUKMzgKMjI5Cjc4Cjc3MwoxMDQKNTMzCjU3OQo1OTQKNjM5Cjc1OQoxODgKMTk4CjI5NQo2NDIKNTcKODY2CjMyOAo2NDgKOTYwCjkzMgozNzkKNjMyCjkzMQo1OTAKMTU1Cjc4NQozODMKODI5Cjg5OAo0MTYKNTM2CjM5Mgo5ODcKNTMxCjI4MAo3NTgKMjU1CjE0NAo3MzQKMTA1CjYzNwo2NTUKODE4Cjk0OQoyNjUKNTIKODQ4CjczNQo2OTgKNTMyCjUxMQo4MDgKODY0CjE5MwoyNjAKNDEwCjY0OQo3MjEKMTE2CjIzOAoyNgo0MDkKNjczCjUwMgo3NjkKNDQ1CjIwNgo4MDMKNzkyCjkzMgo3OTMKMTcwCjM4NgozMTAKMTU0Cjk3MAo4NzYKNTIzCjU0NQo0NDAKMzgyCjYwNwoyNDUKMTk1CjgzOQo2NDgKNjA3Cjg2MQo1NjIKODAwCjM5Mgo2ODkKNjE3CjUwOQo3Nwo4MjgKNzA5CjY5CjcyOAo5NTkKNTkxCjMwOAoyNzcKOTk1CjU0NwoxODkKMzI4CjcxNwo3OTEKNzY5CjQ4MQoyMTMKNDQ4CjcxMgo0NjkKODI0CjE3CjczNwoyNjEKOTg0CjIwNAoxMDAwCjk3Nwo1MTIKMTUzCjkwMQozNTIKMTEzCjE1NAo5ODQKNDEwCjE5NgoyOTUKMjg5CjM3NQo4MzIKMTQzCjc3MAo2MgoxNTIKMjY0CjIxOAozMjEKMTczCjQ3Mwo3MQo1MTYKMjgKNTAzCjc1NgoyNDQKOTM3CjgzCjI0Nwo2MAoxNjAKMTcxCjEzNQozMTgKMTU1CjI1NQo5OTYKNzg2CjkyOAo2ODQKNTcyCjIyMQo2NzYKNDczCjM2OQo1MTIKOTkyCjk0MAo3NzcKMjE3CjgxCjM2OQo5MAo5MzIKNgo0NDYKNjUzCjY3Mgo0OTIKNjk1CjQ1NQoyMzgKNTIyCjYxNwoxNDAKMjEyCjg3OQo1NjcKOTU4CjI4OAoyMzMKNDcKNTk0CjE5NgoyMjAKMzYzCjg0MAo3MjAKMjU5Cjc3MAozMzYKMjY3CjE5MgoxMzgKOTU2Cjc4MQo5NjkKOTI4Cjk1NQo3MDMKNTYwCjc5NAozNjAKMjQzCjYyMQo2NzYKOTY3CjcyCjI5CjM4NAoxMTIKOTQxCjQwOAo0MzMKNzI3CjY0NAo1NzMKNTc4CjI0NgozMjgKNDI1CjU4MQo0ODkKNjIwCjEyMgoxMzkKOTgzCjg0MQoxODIKNzYwCjk0OQo5ODEKMTczCjQxNAo2NTUKOTU0CjcxNgo2NTIKMzgzCjcwMwo3MjMKMTE4CjcxOAo3MTEKNTk2CjQ2NQo4NjAKMzI1CjU5Nwo4NTYKNDgyCjE1NQozMDEKMzA0CjM4Ngo0OTkKNTk3CjU0Ngo4NjgKOTIyCjYKNjYwCjkwMAo0OTAKMzQzCjgzNwo5NDkKNTI0CjQyMwo0MTgKMzc4CjU5Mgo0NjcKMjc4CjIyNQoyOTkKMzM0CjUwMQo5NTgKODg2CjUzMQo5MTAKMTc4CjQ4OAo2NTcKNDkzCjY1MAoxNjAKNjcxCjkwMAo3OTkKOTA4Cg==
1000
2
9
112
989
763
695
288
683
618
236
347
964
161
932
334
928
670
20
809
636
98
542
803
143
967
525
658
689
538
192
752
455
3
535
574
231
981
828
591
250
956
130
680
270
325
746
547
166
747
483
750
706
146
753
951
734
127
207
517
249
771
111
796
878
326
827
269
417
372
339
981
903
747
23
370
277
689
686
975
862
125
230
809
35
700
124
176
463
519
904
278
233
954
689
352
345
39
157
846
191
210
704
599
7
255
547
841
652
49
459
60
788
386
272
830
712
4
967
955
363
614
282
425
222
283
539
788
347
69
479
956
601
131
237
787
520
428
134
403
307
139
488
848
299
500
245
384
549
891
414
329
454
684
240
771
548
825
171
981
696
327
432
4
992
667
230
533
348
986
355
476
446
553
783
769
991
765
817
316
545
823
345
374
682
783
615
462
63
79
461
533
2
738
706
575
562
941
345
801
575
243
34
830
957
960
780
594
857
28
312
777
439
870
308
792
116
824
505
553
206
389
597
967
174
737
127
729
995
641
788
645
36
43
341
293
150
268
110
837
410
29
464
105
652
629
228
169
304
933
957
682
883
952
947
914
614
931
22
836
908
454
339
704
334
935
579
684
738
784
580
503
408
916
885
975
815
776
156
712
995
619
502
647
339
298
201
208
693
329
409
876
44
442
536
224
60
638
158
576
534
868
425
414
0
592
377
607
331
94
985
337
275
607
637
66
518
146
235
482
492
469
261
406
866
498
795
69
576
281
942
844
665
841
524
913
31
126
120
110
599
440
252
995
245
620
749
854
426
789
202
910
683
697
201
939
752
649
259
205
234
961
225
584
66
109
14
391
154
239
537
923
140
680
947
547
410
24
215
438
821
95
846
345
838
491
521
909
732
251
838
720
218
434
530
470
597
877
194
277
757
235
545
666
681
68
118
121
758
557
571
95
198
687
154
275
319
39
785
920
228
627
441
590
228
786
704
355
278
261
196
839
198
431
609
840
128
356
845
856
876
323
412
364
95
944
468
682
667
692
934
465
563
420
314
467
569
609
842
282
624
347
235
620
136
331
196
839
524
117
444
275
702
118
339
842
420
697
187
360
513
840
737
348
168
292
794
408
566
168
184
500
29
388
8
386
462
41
595
226
822
911
399
285
112
458
260
440
635
733
286
891
971
43
722
582
322
237
58
149
579
616
204
42
971
763
638
459
102
796
496
434
873
262
396
201
511
297
108
201
7
935
175
336
439
869
562
509
108
822
989
148
33
467
171
909
163
826
990
802
313
543
33
319
520
777
9
52
478
815
333
842
112
261
566
688
605
469
169
773
929
767
190
97
50
265
750
382
554
856
538
236
173
897
543
448
297
444
976
295
539
531
545
299
781
53
790
670
857
135
795
575
776
311
143
888
230
573
818
285
155
947
713
499
44
27
624
253
25
667
899
960
257
375
872
565
135
917
984
491
25
119
708
522
916
736
8
911
48
422
257
585
454
696
768
874
103
296
970
978
124
230
977
198
909
78
332
456
759
719
60
23
198
611
144
529
406
85
540
38
982
244
705
534
147
653
309
124
81
545
14
423
473
605
38
229
78
773
104
533
579
594
639
759
188
198
295
642
57
866
328
648
960
932
379
632
931
590
155
785
383
829
898
416
536
392
987
531
280
758
255
144
734
105
637
655
818
949
265
52
848
735
698
532
511
808
864
193
260
410
649
721
116
238
26
409
673
502
769
445
206
803
792
932
793
170
386
310
154
970
876
523
545
440
382
607
245
195
839
648
607
861
562
800
392
689
617
509
77
828
709
69
728
959
591
308
277
995
547
189
328
717
791
769
481
213
448
712
469
824
17
737
261
984
204
1000
977
512
153
901
352
113
154
984
410
196
295
289
375
832
143
770
62
152
264
218
321
173
473
71
516
28
503
756
244
937
83
247
60
160
171
135
318
155
255
996
786
928
684
572
221
676
473
369
512
992
940
777
217
81
369
90
932
6
446
653
672
492
695
455
238
522
617
140
212
879
567
958
288
233
47
594
196
220
363
840
720
259
770
336
267
192
138
956
781
969
928
955
703
560
794
360
243
621
676
967
72
29
384
112
941
408
433
727
644
573
578
246
328
425
581
489
620
122
139
983
841
182
760
949
981
173
414
655
954
716
652
383
703
723
118
718
711
596
465
860
325
597
856
482
155
301
304
386
499
597
546
868
922
6
660
900
490
343
837
949
524
423
418
378
592
467
278
225
299
334
501
958
886
531
910
178
488
657
493
650
160
671
900
799
908