1 2
2 8
3 31
4 66
5 154
6 220
7 443
8 518
9 991
10 1004
11 1910
12 1738
13 3315
14 2746
15 5359
16 4102
17 8185
18 5842
19 11963
20 8014
21 16858
22 10666
23 23112
24 13846
25 30899
26 17576
27 40447
28 21954
29 52029
30 27004
31 65880
32 32774
33 82276
34 39312
35 101509
36 46666
37 123887
38 54884
39 149695
40 64014
41 179308
42 74104
43 213082
44 85202
45 251344
46 97356
47 294476
48 110614
49 342876
50 125024
51 396958
52 140634
53 457099
54 157492
55 523849
56 175646
57 597562
58 195144
59 678769
60 216034
61 767842
62 238364
63 865405
64 262182
65 971919
66 287536
67 1087920
68 314474
69 1213960
70 343044
71 1350607
72 373294
73 1498372
74 405272
75 1657849
76 439026
77 1829725
78 474604
79 2014553
80 512054
81 2212975
82 551424
83 2425649
84 592762
85 2653249
86 636116
87 2896465
88 681534
89 3155914
90 729064
91 3432312
92 778754
93 3726484
94 830652
95 4039089
96 884806
97 4370891
98 941264
99 4722670
100 1000074
101 5095222
102 1061284
103 5489256
104 1124942
105 5905699
106 1191096
107 6345395
108 1259794
109 6809095
110 1331084
111 7297669
112 1405014
113 7812003
114 1481632
115 8352999
116 1560986
117 8921575
118 1643124
119 9518546
120 1728094
121 10144977
122 1815944
123 10801834
124 1906722
125 11489974
126 2000476
127 12210389
128 2097254
129 12964087
130 2197104
131 13752092
132 2300074
133 14575444
134 2406212
135 15435064
136 2515566
137 16332155
138 2628184
139 17267805
140 2744114
141 18242977
142 2863404
143 19258785
144 2986102
145 20316359
146 3112256
147 21416845
148 3241914
149 22561256
150 3375124
151 23751066
152 3511934
153 24987169
154 3652392
155 26270924
156 3796546
157 27603243
158 3944444
159 28985674
160 4096134
161 30419314
162 4251664
163 31905431
164 4411082
165 33445309
166 4574436
167 35040248
168 4741774
169 36691395
170 4913144
171 38400076
172 5088594
173 40167806
174 5268172
175 41995774
176 5451926
177 43885354
178 5639904
179 45837936
180 5832154
181 47854926
182 6028724
183 49937746
184 6229662
185 52087649
186 6435016
187 54306083
188 6644834
189 56594701
190 6859164
191 58954798
192 7078054
193 61387870
194 7301552
195 63895429
196 7529706
197 66479003
198 7762564
199 69140136
200 8000174
201 71880187
202 8242584
203 74700726
204 8489842
205 77603544
206 8741996
207 80590042
208 8999094
209 83661838
210 9261184
211 86820566
212 9528314
213 90067876
214 9800532
215 93405219
216 10077886
217 96834488
218 10360424
219 100357381
220 10648194
221 103975391
222 10941244
223 107690242
224 11239622
225 111503674
226 11543376
227 115417443
228 11852554
229 119433321
230 12167204
231 123552865
232 12487374
233 127778106
234 12813112
235 132110864
236 13144466
237 136552738
238 13481484
239 141105574
240 13824214
241 145771234
242 14172704
243 150551596
244 14527002
245 155448554
246 14887156
247 160463771
248 15253214
249 165599416
250 15625224
251 170857431
252 16003234
253 176239521
254 16387292
255 181747654
256 16777446
257 187383814
258 17173744
259 193150001
260 17576234
261 199047970
262 17984964
263 205080273
264 18399982
265 211248434
266 18821336
267 217554778
268 19249074
269 224000847
270 19683244
271 230589267
272 20123894
273 237322150
274 20571072
275 244201074
276 21024826
277 251228171
278 21485204
279 258406147
280 21952254
281 265736616
282 22426024
283 273221758
284 22906562
285 280864054
286 23393916
287 288665435
288 23888134
289 296628129
290 24389264
291 304754380
292 24897354
293 313046448
294 25412452
295 321506609
296 25934606
297 330136858
298 26463864
299 338939497
300 27000274
301 347917145
302 27543884
303 357071839
304 28094742
305 366405929
306 28652896
307 375921781
308 29218394
309 385621777
310 29791284
311 395508315
312 30371614
313 405583496
314 30959432
315 415849744
316 31554786
317 426309816
318 32157724
319 436965855
320 32768294
321 447820333
322 33386544
323 458875738
324 34012522
325 470134574
326 34646276
327 481599034
328 35287854
329 493272306
330 35937304
331 505155955
332 36594674
333 517253203
334 37260012
335 529566299
336 37933366
337 542097837
338 38614784
339 554850427
340 39304314
341 567826695
342 40002004
343 581028940
344 40707902
345 594460159
346 41422056
347 608123026
348 42144514
349 622019882
350 42875324
351 636153427
352 43614534
353 650526377
354 44362192
355 665141464
356 45118346
357 680001436
358 45883044
359 695108698
360 46656334
361 710466385
362 47438264
363 726077293
364 48228882
365 741943869
366 49028236
367 758068935
368 49836374
369 774455329
370 50653344
371 791105905
372 51479194
373 808023533
374 52313972
375 825210724
376 53157726
377 842670751
378 54010504
379 860406532
380 54872354
381 878420620
382 55743324
383 896715959
384 56623462
385 915295509
386 57512816
387 934162246
388 58411434
389 953318773
390 59319364
391 972768874
392 60236654
393 992514793
394 61163352
395 1012559959
396 62099506
397 1032906634
398 63045164
399 1053558676
400 64000374
401 1074518772
402 64965184
403 1095790020
404 65939642
405 1117375534
406 66923796
407 1139278444
408 67917694
409 1161501487
410 68921384
411 1184047819
412 69934914
413 1206921025
414 70958332
415 1230123884
416 71991686
417 1253659600
418 73035024
419 1277531393
420 74088394
421 1301742499
422 75151844
423 1326296170
424 76225422
425 1351195249
426 77309176
427 1376443014
428 78403154
429 1402043188
430 79507404
431 1427998656
432 80621974
433 1454312744
434 81746912
435 1480988794
436 82882266
437 1508030164
438 84028084
439 1535440228
440 85184414
441 1563221935
442 86351304
443 1591378685
444 87528802
445 1619914339
446 88716956
447 1648831888
448 89915814
449 1678134780
450 91125424
451 1707826479
452 92345834
453 1737910465
454 93577092
455 1768389779
456 94819246
457 1799268841
458 96072344
459 1830549808
460 97336434
461 1862237134
462 98611564
463 1894333916
464 99897782
465 1926843724
466 101195136
467 1959770144
468 102503674
469 1993116778
470 103823444
471 2026886773
472 105154494
473 2061084230
474 106496872
475 2095712799
476 107850626
477 2130775669
478 109215804
479 2166276516
480 110592454
481 2202219032
482 111980624
483 2238606925
484 113380362
485 2275443919
486 114791716
487 2312733267
488 116214734
489 2350479208
490 117649464
491 2388685514
492 119095954
493 2427355480
494 120554252
495 2466492904
496 122024406
497 2506101600
498 123506464
499 2546185398
500 125000474
501 2586748144
502 126506484
503 2627793197
504 128024542
505 2669324934
506 129554696
507 2711347249
508 131096994
509 2753863034
510 132651484
511 2796877736
512 134218214
513 2840393764
514 135797232
515 2884415579
516 137388586
517 2928946632
518 138992324
519 2973991939
520 140608494
521 3019554464
522 142237144
523 3065638740
524 143878322
525 3112247749
526 145532076
527 3159386581
528 147198454
529 3207058771
530 148877504
531 3255268393
532 150569274
533 3304019537
534 152273812
535 3353316309
536 153991166
537 3403162294
538 155721384
539 3453561624
540 157464514
541 3504518988
542 159220604
543 3556038013
544 160989702
545 3608122879
546 162771856
547 3660777782
548 164567114
549 3714006934
550 166375524
551 3767814563
552 168197134
553 3822204360
554 170031992
555 3877180579
556 171880146
557 3932748047
558 173741644
559 3988910497
560 175616534
561 4045672231
562 177504864
563 4103037567
564 179406682
565 4161010839
566 181322036
567 4219596397
568 183250974
569 4278798038
570 185193544
571 4338620138
572 187149794
573 4399067662
574 189119772
575 4460144449
576 191103526
577 4521854923
578 193101104
579 4584203524
580 195112554
581 4647194708
582 197137924
583 4710832364
584 199177262
585 4775122144
586 201230616
587 4840066797
588 203298034
589 4905672009
590 205379564
591 4971941725
592 207475254
593 5038880491
594 209585152
595 5106492869
596 211709306
597 5174783437
598 213847764
599 5243756190
600 216000574
601 5313416333
602 218167784
603 5383768492
604 220349442
605 5454816704
606 222545596
607 5526565621
608 224756294
609 5599019911
610 226981584
611 5672184258
612 229221514
613 5746063362
614 231476132
615 5820661324
616 233745486
617 5895983487
618 236029624
619 5972034599
620 238328594
621 6048818803
622 240642444
623 6126340873
624 242971222
625 6204605599
626 245314976
627 6283617787
628 247673754
629 6363382259
630 250047604
631 6443903222
632 252436574
633 6525186157
634 254840712
635 6607235934
636 257260066
637 6690056165
638 259694684
639 6773653657
640 262144614
641 6858031411
642 264609904
643 6943194992
644 267090602
645 7029148699
646 269586756
647 7115898780
648 272098414
649 7203448919
650 274625624
651 7291804753
652 277168434
653 7380969984
654 279726892
655 7470950934
656 282301046
657 7561751986
658 284890944
659 7653378190
660 287496634
661 7745834612
662 290118164
663 7839126334
664 292755582
665 7933257789
666 295408936
667 8028234085
668 298078274
669 8124061015
670 300763644
671 8220743054
672 303465094
673 8318285358
674 306182672
675 8416693099
676 308916426
677 8515971465
678 311666404
679 8616125660
680 314432654
681 8717160223
682 317215224
683 8819080384
684 320014162
685 8921892074
686 322829516
687 9025599874
688 325661334
689 9130209062
690 328509664
691 9235724932
692 331374554
693 9342152794
694 334256052
695 9449497974
696 337154206
697 9557765117
698 340069064
699 9666959575
700 343000674
701 9777087417
702 345949084
703 9888153330
704 348914342
705 10000162714
706 351896496
707 10113120985
708 354895594
709 10227033575
710 357911684
711 10341905221
712 360944814
713 10457742807
714 363995032
715 10574549674
716 367062386
717 10692332740
718 370146924
719 10811096798
720 373248694
721 10930847370
722 376367744
723 11051589994
724 379504122
725 11173330224
726 382657876
727 11296072903
728 385829054
729 11419824340
730 389017704
731 11544590137
732 392223874
733 11670375179
734 395447612
735 11797185094
736 398688966
737 11925025526
738 401947984
739 12053902135
740 405224714
741 12183820597
742 408519204
743 12314785861
744 411831502
745 12446804374
746 415161656
747 12579881860
748 418509714
749 12714023310
750 421875724
751 12849234474
752 425259734
753 12985521118
754 428661792
755 13122889024
756 432081946
757 13261343990
758 435520244
759 13400891071
760 438976734
761 13541536852
762 442451464
763 13683287179
764 445944482
765 13826146384
766 449455836
767 13970121867
768 452985574
769 14115219522
770 456533744
771 14261443717
772 460100394
773 14408800366
774 463685572
775 14557296949
776 467289326
777 14706937870
778 470911704
779 14857729870
780 474552754
781 15009677371
782 478212524
783 15162787927
784 481891062
785 15317066769
786 485588416
787 15472519923
788 489304634
789 15629153431
790 493039764
791 15786973351
792 496793854
793 15945984964
794 500566952
795 16106194354
796 504359106
797 16267608418
798 508170364
799 16430232479
800 512000774
801 16594072669
802 515850384
803 16759135136
804 519719242
805 16925426044
806 523607396
807 17092951573
808 527514894
809 17261717110
810 531441784
811 17431728861
812 535388114
813 17602993861
814 539353932
815 17775517539
816 543339286
817 17949306149
818 547344224
819 18124365961
820 551368794
821 18300703261
822 555413044
823 18478324351
824 559477022
825 18657234724
826 563560776
827 18837440708
828 567664354
829 19018949476
830 571787804
831 19201766563
832 575931174
833 19385898345
834 580094512
835 19571351214
836 584277866
837 19758131578
838 588481284
839 19946245022
840 592704814
841 20135699662
842 596948504
843 20326499431
844 601212402
845 20518652479
846 605496556
847 20712164447
848 609801014
849 20907041833
850 614125824
851 21103291151
852 618471034
853 21300918931
854 622836692
855 21499930864
856 627222846
857 21700334363
858 631629544
859 21902136006
860 636056834
861 22105341526
862 640504764
863 22309957527
864 644973382
865 22515990629
866 649462736
867 22723447468
868 653972874
869 22932334696
870 658503844
871 23142658110
872 663055694
873 23354425261
874 667628472
875 23567642849
876 672222226
877 23782316713
878 676837004
879 23998453579
880 681472854
881 24216060189
882 686129824
883 24435143301
884 690807962
885 24655709689
886 695507316
887 24877765256
888 700227934
889 25101317691
890 704969864
891 25326373816
892 709733154
893 25552938683
894 714517852
895 25781020924
896 719324006
897 26010627409
898 724151664
899 26241763226
900 729000874
901 26474435265
902 733871684
903 26708652238
904 738764142
905 26944419269
906 743678296
907 27181744203
908 748614194
909 27420632182
910 753571884
911 27661091992
912 758551414
913 27903129712
914 763552832
915 28146752344
916 768576186
917 28391966906
918 773621524
919 28638780432
920 778688894
921 28887199051
922 783778344
923 29137229823
924 788889922
925 29388880749
926 794023676
927 29642158000
928 799179654
929 29897068684
930 804357904
931 30153619925
932 809558474
933 30411818863
934 814781412
935 30671672654
936 820026766
937 30933187533
938 825294584
939 31196370682
940 830584914
941 31461230240
942 835897804
943 31727772484
944 841233302
945 31996004644
946 846591456
947 32265933966
948 851972314
949 32537567712
950 857375924
951 32810913160
952 862802334
953 33085976651
954 868251592
955 33362765489
956 873723746
957 33641287951
958 879218844
959 33921550420
960 884736934
961 34203560248
962 890278064
963 34487324803
964 895842282
965 34772851469
966 901429636
967 35060146679
968 907040174
969 35349219781
970 912673944
971 35640075300
972 918330994
973 35932722618
974 924011372
975 36227168224
976 929715126
977 36523419592
978 935442304
979 36821484212
980 941192954
981 37121369590
982 946967124
983 37423082265
984 952764862
985 37726630754
986 958586216
987 38032022611
988 964431234
989 38339264417
990 970299964
991 38648363752
992 976192454
993 38959328212
994 982108752
995 39272165409
996 988048906
997 39586882971
998 994012964
999 39903487543
1000 1000000974