0 6
1 7
2 14
3 33
4 70
5 131
6 222
7 349
8 518
9 735
10 1006
11 1337
12 1734
13 2203
14 2750
15 3381
16 4102
17 4919
18 5838
19 6865
20 8006
21 9267
22 10654
23 12173
24 13830
25 15631
26 17582
27 19689
28 21958
29 24395
30 27006
31 29797
32 32774
33 35943
34 39310
35 42881
36 46662
37 50659
38 54878
39 59325
40 64006
41 68927
42 74094
43 79513
44 85190
45 91131
46 97342
47 103829
48 110598
49 117655
50 125006
51 132657
52 140614
53 148883
54 157470
55 166381
56 175622
57 185199
58 195118
59 205385
60 216006
61 226987
62 238334
63 250053
64 262150
65 274631
66 287502
67 300769
68 314438
69 328515
70 343006
71 357917
72 373254
73 389023
74 405230
75 421881
76 438982
77 456539
78 474558
79 493045
80 512006
81 531447
82 551374
83 571793
84 592710
85 614131
86 636062
87 658509
88 681478
89 704975
90 729006
91 753577
92 778694
93 804363
94 830590
95 857381
96 884742
97 912679
98 941198
99 970305
100 1000006
101 1030307
102 1061214
103 1092733
104 1124870
105 1157631
106 1191022
107 1225049
108 1259718
109 1295035
110 1331006
111 1367637
112 1404934
113 1442903
114 1481550
115 1520881
116 1560902
117 1601619
118 1643038
119 1685165
120 1728006
121 1771567
122 1815854
123 1860873
124 1906630
125 1953131
126 2000382
127 2048389
128 2097158
129 2146695
130 2197006
131 2248097
132 2299974
133 2352643
134 2406110
135 2460381
136 2515462
137 2571359
138 2628078
139 2685625
140 2744006
141 2803227
142 2863294
143 2924213
144 2985990
145 3048631
146 3112142
147 3176529
148 3241798
149 3307955
150 3375006
151 3442957
152 3511814
153 3581583
154 3652270
155 3723881
156 3796422
157 3869899
158 3944318
159 4019685
160 4096006
161 4173287
162 4251534
163 4330753
164 4410950
165 4492131
166 4574302
167 4657469
168 4741638
169 4826815
170 4913006
171 5000217
172 5088454
173 5177723
174 5268030
175 5359381
176 5451782
177 5545239
178 5639758
179 5735345
180 5832006
181 5929747
182 6028574
183 6128493
184 6229510
185 6331631
186 6434862
187 6539209
188 6644678
189 6751275
190 6859006
191 6967877
192 7077894
193 7189063
194 7301390
195 7414881
196 7529542
197 7645379
198 7762398
199 7880605
200 8000006
201 8120607
202 8242414
203 8365433
204 8489670
205 8615131
206 8741822
207 8869749
208 8998918
209 9129335
210 9261006
211 9393937
212 9528134
213 9663603
214 9800350
215 9938381
216 10077702
217 10218319
218 10360238
219 10503465
220 10648006
221 10793867
222 10941054
223 11089573
224 11239430
225 11390631
226 11543182
227 11697089
228 11852358
229 12008995
230 12167006
231 12326397
232 12487174
233 12649343
234 12812910
235 12977881
236 13144262
237 13312059
238 13481278
239 13651925
240 13824006
241 13997527
242 14172494
243 14348913
244 14526790
245 14706131
246 14886942
247 15069229
248 15252998
249 15438255
250 15625006
251 15813257
252 16003014
253 16194283
254 16387070
255 16581381
256 16777222
257 16974599
258 17173518
259 17373985
260 17576006
261 17779587
262 17984734
263 18191453
264 18399750
265 18609631
266 18821102
267 19034169
268 19248838
269 19465115
270 19683006
271 19902517
272 20123654
273 20346423
274 20570830
275 20796881
276 21024582
277 21253939
278 21484958
279 21717645
280 21952006
281 22188047
282 22425774
283 22665193
284 22906310
285 23149131
286 23393662
287 23639909
288 23887878
289 24137575
290 24389006
291 24642177
292 24897094
293 25153763
294 25412190
295 25672381
296 25934342
297 26198079
298 26463598
299 26730905
300 27000006
301 27270907
302 27543614
303 27818133
304 28094470
305 28372631
306 28652622
307 28934449
308 29218118
309 29503635
310 29791006
311 30080237
312 30371334
313 30664303
314 30959150
315 31255881
316 31554502
317 31855019
318 32157438
319 32461765
320 32768006
321 33076167
322 33386254
323 33698273
324 34012230
325 34328131
326 34645982
327 34965789
328 35287558
329 35611295
330 35937006
331 36264697
332 36594374
333 36926043
334 37259710
335 37595381
336 37933062
337 38272759
338 38614478
339 38958225
340 39304006
341 39651827
342 40001694
343 40353613
344 40707590
345 41063631
346 41421742
347 41781929
348 42144198
349 42508555
350 42875006
351 43243557
352 43614214
353 43986983
354 44361870
355 44738881
356 45118022
357 45499299
358 45882718
359 46268285
360 46656006
361 47045887
362 47437934
363 47832153
364 48228550
365 48627131
366 49027902
367 49430869
368 49836038
369 50243415
370 50653006
371 51064817
372 51478854
373 51895123
374 52313630
375 52734381
376 53157382
377 53582639
378 54010158
379 54439945
380 54872006
381 55306347
382 55742974
383 56181893
384 56623110
385 57066631
386 57512462
387 57960609
388 58411078
389 58863875
390 59319006
391 59776477
392 60236294
393 60698463
394 61162990
395 61629881
396 62099142
397 62570779
398 63044798
399 63521205
400 64000006
401 64481207
402 64964814
403 65450833
404 65939270
405 66430131
406 66923422
407 67419149
408 67917318
409 68417935
410 68921006
411 69426537
412 69934534
413 70445003
414 70957950
415 71473381
416 71991302
417 72511719
418 73034638
419 73560065
420 74088006
421 74618467
422 75151454
423 75686973
424 76225030
425 76765631
426 77308782
427 77854489
428 78402758
429 78953595
430 79507006
431 80062997
432 80621574
433 81182743
434 81746510
435 82312881
436 82881862
437 83453459
438 84027678
439 84604525
440 85184006
441 85766127
442 86350894
443 86938313
444 87528390
445 88121131
446 88716542
447 89314629
448 89915398
449 90518855
450 91125006
451 91733857
452 92345414
453 92959683
454 93576670
455 94196381
456 94818822
457 95443999
458 96071918
459 96702585
460 97336006
461 97972187
462 98611134
463 99252853
464 99897350
465 100544631
466 101194702
467 101847569
468 102503238
469 103161715
470 103823006
471 104487117
472 105154054
473 105823823
474 106496430
475 107171881
476 107850182
477 108531339
478 109215358
479 109902245
480 110592006
481 111284647
482 111980174
483 112678593
484 113379910
485 114084131
486 114791262
487 115501309
488 116214278
489 116930175
490 117649006
491 118370777
492 119095494
493 119823163
494 120553790
495 121287381
496 122023942
497 122763479
498 123505998
499 124251505
500 125000006
501 125751507
502 126506014
503 127263533
504 128024070
505 128787631
506 129554222
507 130323849
508 131096518
509 131872235
510 132651006
511 133432837
512 134217734
513 135005703
514 135796750
515 136590881
516 137388102
517 138188419
518 138991838
519 139798365
520 140608006
521 141420767
522 142236654
523 143055673
524 143877830
525 144703131
526 145531582
527 146363189
528 147197958
529 148035895
530 148877006
531 149721297
532 150568774
533 151419443
534 152273310
535 153130381
536 153990662
537 154854159
538 155720878
539 156590825
540 157464006
541 158340427
542 159220094
543 160103013
544 160989190
545 161878631
546 162771342
547 163667329
548 164566598
549 165469155
550 166375006
551 167284157
552 168196614
553 169112383
554 170031470
555 170953881
556 171879622
557 172808699
558 173741118
559 174676885
560 175616006
561 176558487
562 177504334
563 178453553
564 179406150
565 180362131
566 181321502
567 182284269
568 183250438
569 184220015
570 185193006
571 186169417
572 187149254
573 188132523
574 189119230
575 190109381
576 191102982
577 192100039
578 193100558
579 194104545
580 195112006
581 196122947
582 197137374
583 198155293
584 199176710
585 200201631
586 201230062
587 202262009
588 203297478
589 204336475
590 205379006
591 206425077
592 207474694
593 208527863
594 209584590
595 210644881
596 211708742
597 212776179
598 213847198
599 214921805
600 216000006
601 217081807
602 218167214
603 219256233
604 220348870
605 221445131
606 222545022
607 223648549
608 224755718
609 225866535
610 226981006
611 228099137
612 229220934
613 230346403
614 231475550
615 232608381
616 233744902
617 234885119
618 236029038
619 237176665
620 238328006
621 239483067
622 240641854
623 241804373
624 242970630
625 244140631
626 245314382
627 246491889
628 247673158
629 248858195
630 250047006
631 251239597
632 252435974
633 253636143
634 254840110
635 256047881
636 257259462
637 258474859
638 259694078
639 260917125
640 262144006
641 263374727
642 264609294
643 265847713
644 267089990
645 268336131
646 269586142
647 270840029
648 272097798
649 273359455
650 274625006
651 275894457
652 277167814
653 278445083
654 279726270
655 281011381
656 282300422
657 283593399
658 284890318
659 286191185
660 287496006
661 288804787
662 290117534
663 291434253
664 292754950
665 294079631
666 295408302
667 296740969
668 298077638
669 299418315
670 300763006
671 302111717
672 303464454
673 304821223
674 306182030
675 307546881
676 308915782
677 310288739
678 311665758
679 313046845
680 314432006
681 315821247
682 317214574
683 318611993
684 320013510
685 321419131
686 322828862
687 324242709
688 325660678
689 327082775
690 328509006
691 329939377
692 331373894
693 332812563
694 334255390
695 335702381
696 337153542
697 338608879
698 340068398
699 341532105
700 343000006
701 344472107
702 345948414
703 347428933
704 348913670
705 350402631
706 351895822
707 353393249
708 354894918
709 356400835
710 357911006
711 359425437
712 360944134
713 362467103
714 363994350
715 365525881
716 367061702
717 368601819
718 370146238
719 371694965
720 373248006
721 374805367
722 376367054
723 377933073
724 379503430
725 381078131
726 382657182
727 384240589
728 385828358
729 387420495
730 389017006
731 390617897
732 392223174
733 393832843
734 395446910
735 397065381
736 398688262
737 400315559
738 401947278
739 403583425
740 405224006
741 406869027
742 408518494
743 410172413
744 411830790
745 413493631
746 415160942
747 416832729
748 418508998
749 420189755
750 421875006
751 423564757
752 425259014
753 426957783
754 428661070
755 430368881
756 432081222
757 433798099
758 435519518
759 437245485
760 438976006
761 440711087
762 442450734
763 444194953
764 445943750
765 447697131
766 449455102
767 451217669
768 452984838
769 454756615
770 456533006
771 458314017
772 460099654
773 461889923
774 463684830
775 465484381
776 467288582
777 469097439
778 470910958
779 472729145
780 474552006
781 476379547
782 478211774
783 480048693
784 481890310
785 483736631
786 485587662
787 487443409
788 489303878
789 491169075
790 493039006
791 494913677
792 496793094
793 498677263
794 500566190
795 502459881
796 504358342
797 506261579
798 508169598
799 510082405
800 512000006
801 513922407
802 515849614
803 517781633
804 519718470
805 521660131
806 523606622
807 525557949
808 527514118
809 529475135
810 531441006
811 533411737
812 535387334
813 537367803
814 539353150
815 541343381
816 543338502
817 545338519
818 547343438
819 549353265
820 551368006
821 553387667
822 555412254
823 557441773
824 559476230
825 561515631
826 563559982
827 565609289
828 567663558
829 569722795
830 571787006
831 573856197
832 575930374
833 578009543
834 580093710
835 582182881
836 584277062
837 586376259
838 588480478
839 590589725
840 592704006
841 594823327
842 596947694
843 599077113
844 601211590
845 603351131
846 605495742
847 607645429
848 609800198
849 611960055
850 614125006
851 616295057
852 618470214
853 620650483
854 622835870
855 625026381
856 627222022
857 629422799
858 631628718
859 633839785
860 636056006
861 638277387
862 640503934
863 642735653
864 644972550
865 647214631
866 649461902
867 651714369
868 653972038
869 656234915
870 658503006
871 660776317
872 663054854
873 665338623
874 667627630
875 669921881
876 672221382
877 674526139
878 676836158
879 679151445
880 681472006
881 683797847
882 686128974
883 688465393
884 690807110
885 693154131
886 695506462
887 697864109
888 700227078
889 702595375
890 704969006
891 707347977
892 709732294
893 712121963
894 714516990
895 716917381
896 719323142
897 721734279
898 724150798
899 726572705
900 729000006
901 731432707
902 733870814
903 736314333
904 738763270
905 741217631
906 743677422
907 746142649
908 748613318
909 751089435
910 753571006
911 756058037
912 758550534
913 761048503
914 763551950
915 766060881
916 768575302
917 771095219
918 773620638
919 776151565
920 778688006
921 781229967
922 783777454
923 786330473
924 788889030
925 791453131
926 794022782
927 796597989
928 799178758
929 801765095
930 804357006
931 806954497
932 809557574
933 812166243
934 814780510
935 817400381
936 820025862
937 822656959
938 825293678
939 827936025
940 830584006
941 833237627
942 835896894
943 838561813
944 841232390
945 843908631
946 846590542
947 849278129
948 851971398
949 854670355
950 857375006
951 860085357
952 862801414
953 865523183
954 868250670
955 870983881
956 873722822
957 876467499
958 879217918
959 881974085
960 884736006
961 887503687
962 890277134
963 893056353
964 895841350
965 898632131
966 901428702
967 904231069
968 907039238
969 909853215
970 912673006
971 915498617
972 918330054
973 921167323
974 924010430
975 926859381
976 929714182
977 932574839
978 935441358
979 938313745
980 941192006
981 944076147
982 946966174
983 949862093
984 952763910
985 955671631
986 958585262
987 961504809
988 964430278
989 967361675
990 970299006
991 973242277
992 976191494
993 979146663
994 982107790
995 985074881
996 988047942
997 991026979
998 994011998
999 997003005
1000 1000000006