3 4
4 19
5 61
6 157
7 353
8 717
9 1355
10 2412
11 4094
12 6676
13 10524
14 16108
15 24036
16 35063
17 50135
18 70409
19 97295
20 132485
21 178011
22 236268
23 310086
24 402768
25 518158
26 660692
27 835486
28 1048379
29 1306039
30 1616025
31 1986887
32 2428245
33 2950913
34 3566968
35 4289896
36 5134684
37 6117958
38 7258096
39 8575394
40 10092167
41 11832941
42 13824581
43 16096473
44 18680677
45 21612141
46 24928840
47 28672020
48 32886368
49 37620244
50 42925880
51 48859648
52 55482243
53 62858985
54 71060037
55 80160693
56 90241629
57 101389231
58 113695828
59 127260058
60 142187140
61 158589224
62 176585700
63 196303592
64 217877847
65 241451771
66 267177361
67 295215723
68 325737445
69 358923063
70 394963412
71 434060138
72 476426096
73 522285842
74 571876076
75 625446186
76 683258667
77 745589715
78 812729697
79 884983723
80 962672165
81 1046131285
82 1135713728
83 1231789204
84 1334745036
85 1444986818
86 1562939016
87 1689045686
88 1823771047
89 1967600257
90 2121040045
91 2284619461
92 2458890565
93 2644429241
94 2841835856
95 3051736136
96 3274781888
97 3511651848
98 3763052464
99 4029718812
100 4312415347
101 4611936885
102 4929109421
103 5264791081
104 5619873005
105 5995280371
106 6391973244
107 6810947670
108 7253236596
109 7719910932
110 8212080540
111 8730895372
112 9277546423
113 9853266943
114 10459333465
115 11097066983
116 11767834053
117 12473048051
118 13214170236
119 13992711086
120 14810231440
121 15668343798
122 16568713540
123 17513060310
124 18503159195
125 19540842191
126 20627999465
127 21766580783
128 22958596853
129 24206120841
130 25511289672
131 26876305632
132 28303437756
133 29795023390
134 31353469664
135 32981255146
136 34680931271
137 36455124085
138 38306535765
139 40237946321
140 42252215205
141 44352283109
142 46541173528
143 48821994652
144 51197941024
145 53672295388
146 56248430440
147 58929810776
148 61719994595
149 64622635745
150 67641485525
151 70780394685
152 74043315325
153 77434302999
154 80957518564
155 84617230386
156 88417816292
157 92363765728
158 96459681812
159 100710283600
160 105120408087
161 109695012579
162 114439176801
163 119358105219
164 124457129253
165 129741709711
166 135217438948
167 140890043410
168 146765385904
169 152849468090
170 159148432860
171 165668566946
172 172416303243
173 179398223531
174 186621060913
175 194091702483
176 201817191877
177 209804732061
178 218061687824
179 226595588684
180 235414131500
181 244525183322
182 253936784120
183 263657149758
184 273694674663
185 284057934921
186 294755691069
187 305796891133
188 317190673541
189 328946370289
190 341073509792
191 353581820176
192 366481232256
193 379781882768
194 393494117472
195 407628494516
196 422195787475
197 437206988845
198 452673313213
199 468606200689
200 485017320205
201 501918573083
202 519322096268
203 537240266030
204 555685701332
205 574671267468
206 594210079564
207 614315506356
208 635001173623
209 656280968103
210 678169041065
211 700679812159
212 723827973125
213 747628491787
214 772096615692
215 797247876246
216 823098092496
217 849663375198
218 876960130740
219 905005065358
220 933815188987
221 963407819623
222 993800587321
223 1025011438487
224 1057058640021
225 1089960783761
226 1123736790552
227 1158405914840
228 1193987748892
229 1230502227318
230 1267969631440
231 1306410593970
232 1345846103303
233 1386297508349
234 1427786522981
235 1470335230793
236 1513966089701
237 1558701936861
238 1604565993192
239 1651581868452
240 1699773565920
241 1749165487396
242 1799782438040
243 1851649631536
244 1904792694851
245 1959237673561
246 2015011036773
247 2072139682373
248 2130650942109
249 2190572587007
250 2251932832372
251 2314760343370
252 2379084240196
253 2444934103576
254 2512339980100
255 2581332387896
256 2651942321879
257 2724201259595
258 2798141166641
259 2873794502427
260 2951194225765
261 3030373800807
262 3111367202548
263 3194208922938
264 3278933976560
265 3365577906658
266 3454176790988
267 3544767248026
268 3637386442731
269 3732072092931
270 3828862475265
271 3927796431483
272 4028913374565
273 4132253295205
274 4237856767840
275 4345764957316
276 4456019625100
277 4568663135858
278 4683738463848
279 4801289199686
280 4921359556647
281 5043994377617
282 5169239141581
283 5297139970485
284 5427743635909
285 5561097566121
286 5697249852656
287 5836249257560
288 5978145220160
289 6122987864216
290 6270828004880
291 6421717156044
292 6575707537203
293 6732852080997
294 6893204440269
295 7056818995513
296 7223750862125
297 7394055898051
298 7567790710940
299 7745012665990
300 7925779893300
301 8110151295620
302 8298186555900
303 8489946145244
304 8685491330359
305 8884884181711
306 9088187581177
307 9295465230103
308 9506781657157
309 9722202226595
310 9941793146012
311 10165621474814
312 10393755132176
313 10626262905414
314 10863214458148
315 11104680338886
316 11350731989083
317 11601441751935
318 11856882880649
319 12117129547135
320 12382256850485
321 12652340825881
322 12927458452968
323 13207687664976
324 13493107357308
325 13783797396558
326 14079838629312
327 14381312891386
328 14688303016519
329 15000892845829
330 15319167236725
331 15643212072257
332 15973114270245
333 16308961792853
334 16650843655608
335 16998849937196
336 17353071788704
337 17713601443308
338 18080532225736
339 18453958562184
340 18833975989667
341 19220681166161
342 19614171880181
343 20014547060813
344 20421906787517
345 20836352300391
346 21257986009860
347 21686911507170
348 22123233574308
349 22567058194384
350 23018492561780
351 23477645092768
352 23944625435543
353 24419544481075
354 24902514373377
355 25393648520243
356 25893061603749
357 26400869591231
358 26917189745668
359 27442140636898
360 27975842152240
361 28518415507594
362 29069983258300
363 29630669310482
364 30200598931787
365 30779898762971
366 31368696828881
367 31967122549923
368 32575306753285
369 33193381684653
370 33821481019312
371 34459739874108
372 35108294818796
373 35767283887882
374 36436846592216
375 37117123931086
376 37808258403687
377 38510394021465
378 39223676319837
379 39948252370413
380 40684270792965
381 41431881767905
382 42191237048128
383 42962489971744
384 43745795474176
385 44541310100768
386 45349192019136
387 46169601032036
388 47002698589587
389 47848647802397
390 48707613454045
391 49579762014081
392 50465261650765
393 51364282244331
394 52276995399596
395 53203574459486
396 54144194517908
397 55099032433148
398 56068266841004
399 57052078168452
400 58050648646647
401 59064162324855
402 60092805083721
403 61136764649071
404 62196230605445
405 63271394410171
406 64362449406764
407 65469590839270
408 66593015865936
409 67732923573422
410 68889514990740
411 70062993103742
412 71253562868923
413 72461431228183
414 73686807122905
415 74929901508583
416 76190927369173
417 77470099732001
418 78767635681976
419 80083754376776
420 81418677061340
421 82772627082918
422 84145829905840
423 85538513126850
424 86950906489735
425 88383241900941
426 89835753444485
427 91308677397433
428 92802252245093
429 94316718696781
430 95852319700872
431 97409300460852
432 98987908450656
433 100588393430580
434 102211007462904
435 103856004928096
436 105523642540291
437 107214179363785
438 108927876828805
439 110664998747861
440 112425811331805
441 114210583206479
442 116019585428628
443 117853091502842
444 119711377397764
445 121594721562888
446 123503404945060
447 125437711005576
448 127397925736535
449 129384337678235
450 131397237935825
451 133436920196555
452 135503680746725
453 137597818489239
454 139719634960404
455 141869434347786
456 144047523507312
457 146254211980978
458 148489812014252
459 150754638574090
460 153049009366187
461 155373244853299
462 157727668272801
463 160112605654859
464 162528385840293
465 164975340499061
466 167453804147968
467 169964114169460
468 172506610829644
469 175081637296930
470 177689539660360
471 180330666948566
472 183005371147943
473 185714007221921
474 188456933129453
475 191234509844133
476 194047101372997
477 196895074775961
478 199778800184464
479 202698650821224
480 205655003019200
481 208648236241192
482 211678733099120
483 214746879373948
484 217853064034803
485 220997679259221
486 224181120452589
487 227403786268233
488 230666078627181
489 233968402738579
490 237311167119292
491 240694783614646
492 244119667418356
493 247586237093108
494 251094914590812
495 254646125273516
496 258240297933495
497 261877864814495
498 265559261632153
499 269284927595079
500 273055305425605
501 276870841381203
502 280731985275068
503 284639190497870
504 288592914038672
505 292593616506518
506 296641762151684
507 300737818887606
508 304882258311963
509 309075555728943
510 313318190170665
511 317610644419279
512 321953405028725
513 326346962347177
514 330791810538632
515 335288447605696
516 339837375411516
517 344439099702398
518 349094130130080
519 353802980274698
520 358566167666887
521 363384213811093
522 368257644208021
523 373186988377777
524 378172779882661
525 383215556350661
526 388315859498072
527 393474235153340
528 398691233280032
529 403967408000508
530 409303317619240
531 414699524646840
532 420156595823203
533 425675102141889
534 431255618873621
535 436898725590493
536 442605006189821
537 448375048918711
538 454209446397732
539 460108795645842
540 466073698104420
541 472104759662016
542 478202590678740
543 484367806011376
544 490601025037591
545 496902871681411
546 503273974437793
547 509714966397923
548 516226485274149
549 522809173425647
550 529463677883172
551 536190650375090
552 542990747352496
553 549864630015066
554 556812964336540
555 563836421090946
556 570935675877899
557 578111409149195
558 585364306234481
559 592695057367667
560 600104357712965
561 607592907391677
562 615161411508048
563 622810580176428
564 630541128547500
565 638353776835258
566 646249250343608
567 654228279493726
568 662291599850471
569 670439952150121
570 678674082327165
571 686994741541853
572 695402686207365
573 703898678017745
574 712483483974880
575 721157876416816
576 729922633045120
577 738778536953008
578 747726376653088
579 756766946105876
580 765901044747347
581 775129477517837
582 784453054889981
583 793872592897425
584 803388913163149
585 813002842928571
586 822715215081676
587 832526868186510
588 842438646511700
589 852451400059756
590 862565984595980
591 872783261678164
592 883104098685303
593 893529368847687
594 904059951276009
595 914696730991263
596 925440598954245
597 936292452095851
598 947253193346380
599 958323731666230
600 969504982075600
601 980797865684990
602 992203309725300
603 1003722247578734
604 1015355618808699
605 1027104369191111
606 1038969450744697
607 1050951821762103
608 1063052446840597
609 1075272296913585
610 1087612349281112
611 1100073587641784
612 1112657002123676
613 1125363589316054
614 1138194352300688
615 1151150300683986
616 1164232450628103
617 1177441824883485
618 1190779452820389
619 1204246370461225
620 1217843620512485
621 1231572252397501
622 1245433322288168
623 1259427893138116
624 1273557034714848
625 1287821823632708
626 1302223343385432
627 1316762684379536
628 1331440943966659
629 1346259226477369
630 1361218643253925
631 1376320312683877
632 1391565360233245
633 1406954918480543
634 1422490127149748
635 1438172133144746
636 1454002090582724
637 1469981160828408
638 1486110512527876
639 1502391321643224
640 1518824771486167
641 1535412052753131
642 1552154363559281
643 1569052909473403
644 1586108903552357
645 1603323566376391
646 1620698126083380
647 1638233818404570
648 1655931886699248
649 1673793581990274
650 1691820162999180
651 1710012896182138
652 1728373055764843
653 1746901923778915
654 1765600790097217
655 1784470952470043
656 1803513716560869
657 1822730395982981
658 1842122312335008
659 1861690795237988
660 1881437182371340
661 1901362819509714
662 1921469060559400
663 1941757267595622
664 1962228810898727
665 1982885068991921
666 2003727428677901
667 2024757285076373
668 2045976041661125
669 2067385110297993
670 2088985911281712
671 2110779873374328
672 2132768433842496
673 2154953038495672
674 2177335141723856
675 2199916206536236
676 2222697704598707
677 2245681116272965
678 2268867930654477
679 2292259645611353
680 2315857767822765
681 2339663812818275
682 2363679305016028
683 2387905777762534
684 2412344773371316
685 2436997843162468
686 2461866547501756
687 2486952455840636
688 2512257146755127
689 2537782207986287
690 2563529236479545
691 2589499838424951
692 2615695629296965
693 2642118233895171
694 2668769286383836
695 2695650430333086
696 2722763318758928
697 2750109614164198
698 2777690988579044
699 2805509123602342
700 2833565710441947
701 2861862449956575
702 2890401052696521
703 2919183238945311
704 2948210738760885
705 2977485292017721
706 3007008648447784
707 3036782567683120
708 3066808819297276
709 3097089182847662
710 3127625447917440
711 3158419414158362
712 3189472891332423
713 3220787699355173
714 3252365668337845
715 3284208638630433
716 3316318460864293
717 3348696995995701
718 3381346115348216
719 3414267700656716
720 3447463644110240
721 3480935848395788
722 3514686226741640
723 3548716702961640
724 3583029211498275
725 3617625697467441
726 3652508116702005
727 3687678435796333
728 3723138632150333
729 3758890694014471
730 3794936620533572
731 3831278421792322
732 3867918118859556
733 3904857743833520
734 3942099339886644
735 3979644961311296
736 4017496673564311
737 4055656553313235
738 4094126688481345
739 4132909178293651
740 4172006133322405
741 4211419675533599
742 4251151938332228
743 4291205066609282
744 4331581216787504
745 4372282556868138
746 4413311266477180
747 4454669536912626
748 4496359571190475
749 4538383584092475
750 4580743802212625
751 4623442464004675
752 4666481819829125
753 4709864132001229
754 4753591674837744
755 4797666734705436
756 4842091610068332
757 4886868611535978
758 4932000061911192
759 4977488296238830
760 5023335661853287
761 5069544518427769
762 5116117238022301
763 5163056205132749
764 5210363816739333
765 5258042482356161
766 5306094624079488
767 5354522676637760
768 5403329087440384
769 5452516316627520
770 5502086837119360
771 5552043134666436
772 5602387707898643
773 5653123068376061
774 5704251740638493
775 5755776262256033
776 5807699183879117
777 5860023069289611
778 5912750495450604
779 5965884052558014
780 6019426344090900
781 6073379986862812
782 6127747611072620
783 6182531860356388
784 6237735391837943
785 6293360876181271
786 6349410997641609
787 6405888454117583
788 6462795957202821
789 6520136232238619
790 6577912018365292
791 6636126068575366
792 6694781149765456
793 6753880042789198
794 6813425542509652
795 6873420457852766
796 6933867611859515
797 6994769841739895
798 7056129998925593
799 7117950949123719
800 7180235572370005
801 7242986763083073
802 7306207430117368
803 7369900496817960
804 7434068901074012
805 7498715595373318
806 7563843546856304
807 7629455737371106
808 7695555163527303
809 7762144836751533
810 7829227783341765
811 7896807044522649
812 7964885676500325
813 8033466750518317
814 8102553352912072
815 8172148585165396
816 8242255563965536
817 8312877421259348
818 8384017304308920
819 8455678375748288
820 8527863813638787
821 8600576811526313
822 8673820578497221
823 8747598339235317
824 8821913334078301
825 8896768819075311
826 8972168066043092
827 9048114362624090
828 9124611012343172
829 9201661334665448
830 9279268665053540
831 9357436355025960
832 9436167772214103
833 9515466300421179
834 9595335339679761
835 9675778306310443
836 9756798632979941
837 9838399768760311
838 9920585179186772
839 10003358346317482
840 10086722768791920
841 10170681961890386
842 10255239457592940
843 10340398804639466
844 10426163568588331
845 10512537331877011
846 10599523693881313
847 10687126270975723
848 10775348696593189
849 10864194621286037
850 10953667712785472
851 11043771656063060
852 11134510153390796
853 11225886924402306
854 11317905706153480
855 11410570253184246
856 11503884337578919
857 11597851749028545
858 11692476294891821
859 11787761800257157
860 11883712108004165
861 11980331078866297
862 12077622591492048
863 12175590542508168
864 12274238846581440
865 12373571436481608
866 12473592263143728
867 12574305295731676
868 12675714521700211
869 12777823946859061
870 12880637595435565
871 12984159510138473
872 13088393752221165
873 13193344401546035
874 13299015556647420
875 13405411334796566
876 13512535872065140
877 13620393323389908
878 13728987862636828
879 13838323682666316
880 13948404995397047
881 14059236031871807
882 14170821042321881
883 14283164296232615
884 14396270082408389
885 14510142709038771
886 14624786503763196
887 14740205813737710
888 14856405005700240
889 14973388466037046
890 15091160600848580
891 15209725836016534
892 15329088617269403
893 15449253410250127
894 15570224700582249
895 15692006993937263
896 15814604816101365
897 15938022713043401
898 16062265250981320
899 16187337016450720
900 16313242616371900
901 16439986678118110
902 16567573849583200
903 16696008799250474
904 16825296216260039
905 16955440810478261
906 17086447312565717
907 17218320474046353
908 17351065067376037
909 17484685886012325
910 17619187744482712
911 17754575478455004
912 17890853944806176
913 18028028021692444
914 18166102608618728
915 18305082626509336
916 18444973017777123
917 18585778746394785
918 18727504797964629
919 18870156179789565
920 19013737920943485
921 19158255072342871
922 19303712706816868
923 19450115919179506
924 19597469826300388
925 19745779567176608
926 19895050303004052
927 20045287217249936
928 20196495515723799
929 20348680426650659
930 20501847200742625
931 20656001111271747
932 20811147454142245
933 20967291547963983
934 21124438734124388
935 21282594376862546
936 21441763863341744
937 21601952603723258
938 21763166031239516
939 21925409602268514
940 22088688796406667
941 22253009116543851
942 22418376088936881
943 22584795263284243
944 22752272212800197
945 22920812534290141
946 23090421848224400
947 23261105798814220
948 23432870054086188
949 23605720305957914
950 23779662270313080
951 23954701687077758
952 24130844320295143
953 24308095958202505
954 24486462413306557
955 24665949522460093
956 24846563146937989
957 25028309172514481
958 25211193509538848
959 25395222093013328
960 25580400882669440
961 25766735863045584
962 25954233043564000
963 26142898458609012
964 26332738167603667
965 26523758255088621
966 26715964830799421
967 26909364029745073
968 27103962012285965
969 27299764964213083
970 27496779096825612
971 27695010647010798
972 27894465877322196
973 28095151076059212
974 28297072557345996
975 28500236661211636
976 28704649753668727
977 28910318226794215
978 29117248498808617
979 29325447014156543
980 29534920243586565
981 29745674684232395
982 29957716859692428
983 30171053320111574
984 30385690642261456
985 30601635429621918
986 30818894312461876
987 31037473947921486
988 31257381020092667
989 31478622240101927
990 31701204346191545
991 31925134103802071
992 32150418305654165
993 32377063771831761
994 32605077349863576
995 32834465914806936
996 33065236369329948
997 33297395643794998
998 33530950696341584
999 33765908512970482
1000 34002276107626247