0 0
1 1
2 462
3 7941
4 48838
5 185193
6 530526
7 1265677
8 2654646
9 5060433
10 8960878
11 14964501
12 23826342
13 36463801
14 53972478
15 77642013
16 108971926
17 149687457
18 201755406
19 267399973
20 349118598
21 449697801
22 572229022
23 720124461
24 897132918
25 1107355633
26 1355262126
27 1645706037
28 1983940966
29 2375636313
30 2826893118
31 3344259901
32 3934748502
33 4605849921
34 5365550158
35 6222346053
36 7185261126
37 8263861417
38 9468271326
39 10809189453
40 12297904438
41 13946310801
42 15766924782
43 17772900181
44 19978044198
45 22396833273
46 25044428926
47 27936693597
48 31090206486
49 34522279393
50 38250972558
51 42295110501
52 46674297862
53 51408935241
54 56520235038
55 62030237293
56 67961825526
57 74338742577
58 81185606446
59 88527926133
60 96392117478
61 104805519001
62 113796407742
63 123394015101
64 133628542678
65 144531178113
66 156134110926
67 168470548357
68 181574731206
69 195481949673
70 210228559198
71 225851996301
72 242390794422
73 259884599761
74 278374187118
75 297901475733
76 318509545126
77 340242650937
78 363146240766
79 387266970013
80 412652717718
81 439352602401
82 467416997902
83 496897549221
84 527847188358
85 560320150153
86 594371988126
87 630059590317
88 667441195126
89 706576407153
90 747526213038
91 790352997301
92 835120558182
93 881894123481
94 930740366398
95 981727421373
96 1034924899926
97 1090403906497
98 1148237054286
99 1208498481093
100 1271263865158
101 1336610441001
102 1404617015262
103 1475363982541
104 1548933341238
105 1625408709393
106 1704875340526
107 1787420139477
108 1873131678246
109 1962100211833
110 2054417694078
111 2150177793501
112 2249475909142
113 2352409186401
114 2459076532878
115 2569578634213
116 2684017969926
117 2802498829257
118 2925127327006
119 3052011419373
120 3183260919798
121 3318987514801
122 3459304779822
123 3604328195061
124 3754175161318
125 3908965015833
126 4068819048126
127 4233860515837
128 4404214660566
129 4580008723713
130 4761371962318
131 4948435664901
132 5141333167302
133 5340199868521
134 5545173246558
135 5756392874253
136 5974000435126
137 6198139739217
138 6428956738926
139 6666599544853
140 6911218441638
141 7162965903801
142 7421996611582
143 7688467466781
144 7962537608598
145 8244368429473
146 8534123590926
147 8831969039397
148 9138073022086
149 9452606102793
150 9775741177758
151 10107653491501
152 10448520652662
153 10798522649841
154 11157841867438
155 11526663101493
156 11905173575526
157 12293562956377
158 12692023370046
159 13100749417533
160 13519938190678
161 13949789288001
162 14390504830542
163 14842289477701
164 15305350443078
165 15779897510313
166 16266143048926
167 16764302030157
168 17274592042806
169 17797233309073
170 18332448700398
171 18880463753301
172 19441506685222
173 20015808410361
174 20603602555518
175 21205125475933
176 21820616271126
177 22450316800737
178 23094471700366
179 23753328397413
180 24427137126918
181 25116150947401
182 25820625756702
183 26540820307821
184 27276996224758
185 28029418018353
186 28798353102126
187 29584071808117
188 30386847402726
189 31206956102553
190 32044677090238
191 32900292530301
192 33774087584982
193 34666350430081
194 35577372270798
195 36507447357573
196 37456873001926
197 38425949592297
198 39414980609886
199 40424272644493
200 41454135410358
201 42504881762001
202 43576827710062
203 44670292437141
204 45785598313638
205 46923070913593
206 48083039030526
207 49265834693277
208 50471793181846
209 51701253043233
210 52954556107278
211 54232047502501
212 55534075671942
213 56860992389001
214 58213152773278
215 59590915306413
216 60994641847926
217 62424697651057
218 63881451378606
219 65365275118773
220 66876544400998
221 68415638211801
222 69982939010622
223 71578832745661
224 73203708869718
225 74857960356033
226 76541983714126
227 78256179005637
228 80000949860166
229 81776703491113
230 83583850711518
231 85422805949901
232 87293987266102
233 89197816367121
234 91134718622958
235 93105123082453
236 95109462489126
237 97148173297017
238 99221695686526
239 101330473580253
240 103474954658838
241 105655590376801
242 107872835978382
243 110127150513381
244 112418996852998
245 114748841705673
246 117117155632926
247 119524413065197
248 121971092317686
249 124457675606193
250 126984649062958
251 129552502752501
252 132161730687462
253 134812830844441
254 137506305179838
255 140242659645693
256 143022404205526
257 145846052850177
258 148714123613646
259 151627138588933
260 154585623943878
261 157590109937001
262 160641130933342
263 163739225420301
264 166884936023478
265 170078809522513
266 173321396866926
267 176613253191957
268 179954937834406
269 183347014348473
270 186790050521598
271 190284618390301
272 193831294256022
273 197430658700961
274 201083296603918
275 204789797156133
276 208550753877126
277 212366764630537
278 216238431639966
279 220166361504813
280 224151165216118
281 228193458172401
282 232293860195502
283 236452995546421
284 240671492941158
285 244949985566553
286 249289111096126
287 253689511705917
288 258151834090326
289 262676729477953
290 267264853647438
291 271916866943301
292 276633434291782
293 281415225216681
294 286262913855198
295 291177178973773
296 296158703983926
297 301208176958097
298 306326290645486
299 311513742487893
300 316771234635558
301 322099473963001
302 327499172084862
303 332971045371741
304 338515814966038
305 344134206797793
306 349826951600526
307 355594784927077
308 361438447165446
309 367358683554633
310 373356244200478
311 379431884091501
312 385586363114742
313 391820446071601
314 398134902693678
315 404530507658613
316 411008040605926
317 417568286152857
318 424212033910206
319 430940078498173
320 437753219562198
321 444652261788801
322 451638014921422
323 458711293776261
324 465872918258118
325 473123713376233
326 480464509260126
327 487896141175437
328 495419449539766
329 503035279938513
330 510744483140718
331 518547915114901
332 526446437044902
333 534440915345721
334 542532221679358
335 550721232970653
336 559008831423126
337 567395904534817
338 575883345114126
339 584472051295653
340 593162926556038
341 601956879729801
342 610854825025182
343 619857682039981
344 628966375777398
345 638181836661873
346 647505000554926
347 656936808770997
348 666478208093286
349 676130150789593
350 685893594628158
351 695769502893501
352 705758844402262
353 715862593519041
354 726081730172238
355 736417239869893
356 746870113715526
357 757441348423977
358 768131946337246
359 778942915440333
360 789875269377078
361 800930027466001
362 812108214716142
363 823410861842901
364 834839005283878
365 846393687214713
366 858075955564926
367 869886864033757
368 881827472106006
369 893898845067873
370 906102054022798
371 918438175907301
372 930908293506822
373 943513495471561
374 956254876332318
375 969133536516333
376 982150582363126
377 995307126140337
378 1008604286059566
379 1022043186292213
380 1035624956985318
381 1049350734277401
382 1063221660314302
383 1077238883265021
384 1091403557337558
385 1105716842794753
386 1120179905970126
387 1134793919283717
388 1149560061257926
389 1164479516533353
390 1179553475884638
391 1194783136236301
392 1210169700678582
393 1225714378483281
394 1241418385119598
395 1257282942269973
396 1273309277845926
397 1289498626003897
398 1305852227161086
399 1322371328011293
400 1339057181540758
401 1355911047044001
402 1372934190139662
403 1390127882786341
404 1407493403298438
405 1425032036361993
406 1442745073050526
407 1460633810840877
408 1478699553629046
409 1496943611746033
410 1515367301973678
411 1533971947560501
412 1552758878237542
413 1571729430234201
414 1590884946294078
415 1610226775690813
416 1629756274243926
417 1649474804334657
418 1669383734921806
419 1689484441557573
420 1709778306403398
421 1730266718245801
422 1750951072512222
423 1771832771286861
424 1792913223326518
425 1814193844076433
426 1835676055686126
427 1857361287025237
428 1879250973699366
429 1901346558065913
430 1923649489249918
431 1946161223159901
432 1968883222503702
433 1991816956804321
434 2014963902415758
435 2038325542538853
436 2061903367237126
437 2085698873452617
438 2109713565021726
439 2133948952691053
440 2158406554133238
441 2183087893962801
442 2207994503751982
443 2233127922046581
444 2258489694381798
445 2284081373298073
446 2309904518356926
447 2335960696156797
448 2362251480348886
449 2388778451652993
450 2415543197873358
451 2442547313914501
452 2469792401797062
453 2497280070673641
454 2525011936844638
455 2552989623774093
456 2581214762105526
457 2609688989677777
458 2638413951540846
459 2667391299971733
460 2696622694490278
461 2726109801875001
462 2755854296178942
463 2785857858745501
464 2816122178224278
465 2846648950586913
466 2877439879142926
467 2908496674555557
468 2939821054857606
469 2971414745467273
470 3003279479203998
471 3035416996304301
472 3067829044437622
473 3100517378722161
474 3133483761740718
475 3166729963556533
476 3200257761729126
477 3234068941330137
478 3268165294959166
479 3302548622759613
480 3337220732434518
481 3372183439262401
482 3407438566113102
483 3442987943463621
484 3478833409413958
485 3514976809702953
486 3551419997724126
487 3588164834541517
488 3625213188905526
489 3662566937268753
490 3700227963801838
491 3738198160409301
492 3776479426745382
493 3815073670229881
494 3853982806063998
495 3893208757246173
496 3932753454587926
497 3972618836729697
498 4012806850156686
499 4053319449214693
500 4094158596125958
501 4135326261005001
502 4176824421874462
503 4218655064680941
504 4260820183310838
505 4303321779606193
506 4346161863380526
507 4389342452434677
508 4432865572572646
509 4476733257617433
510 4520947549426878
511 4565510497909501
512 4610424161040342
513 4655690604876801
514 4701311903574478
515 4747290139403013
516 4793627402761926
517 4840325792196457
518 4887387414413406
519 4934814384296973
520 4982608824924598
521 5030772867582801
522 5079308651783022
523 5128218325277461
524 5177504044074918
525 5227167972456633
526 5277212282992126
527 5327639156555037
528 5378450782338966
529 5429649357873313
530 5481237089039118
531 5533216190084901
532 5585588883642502
533 5638357400742921
534 5691523980832158
535 5745090871787053
536 5799060329931126
537 5853434620050417
538 5908216015409326
539 5963406797766453
540 6019009257390438
541 6075025693075801
542 6131458412158782
543 6188309730533181
544 6245581972666198
545 6303277471614273
546 6361398569038926
547 6419947615222597
548 6478926969084486
549 6538338998196393
550 6598186078798558
551 6658470595815501
552 6719194942871862
553 6780361522308241
554 6841972745197038
555 6904031031358293
556 6966538809375526
557 7029498516611577
558 7092912599224446
559 7156783512183133
560 7221113719283478
561 7285905693164001
562 7351161915321742
563 7416884876128101
564 7483077074844678
565 7549741019639113
566 7616879227600926
567 7684494224757357
568 7752588546089206
569 7821164735546673
570 7890225346065198
571 7959772939581301
572 8029810087048422
573 8100339368452761
574 8171363372829118
575 8242884698276733
576 8314905951975126
577 8387429750199937
578 8460458718338766
579 8533995490907013
580 8608042711563718
581 8682603033127401
582 8757679117591902
583 8833273636142221
584 8909389269170358
585 8986028706291153
586 9063194646358126
587 9140889797479317
588 9219116877033126
589 9297878611684153
590 9377177737399038
591 9457016999462301
592 9537399152492182
593 9618326960456481
594 9699803196688398
595 9781830643902373
596 9864412094209926
597 9947550349135497
598 10031248219632286
599 10115508526098093
600 10200334098391158
601 10285727775846001
602 10371692407289262
603 10458230851055541
604 10545345975003238
605 10633040656530393
606 10721317782590526
607 10810180249708477
608 10899630963996246
609 10989672841168833
610 11080308806560078
611 11171541795138501
612 11263374751523142
613 11355810629999401
614 11448852394534878
615 11542503018795213
616 11636765486159926
617 11731642789738257
618 11827137932385006
619 11923253926716373
620 12019993795125798
621 12117360569799801
622 12215357292733822
623 12313987015748061
624 12413252800503318
625 12513157718516833
626 12613704851178126
627 12714897289764837
628 12816738135458566
629 12919230499360713
630 13022377502508318
631 13126182275889901
632 13230647960461302
633 13335777707161521
634 13441574676928558
635 13548042040715253
636 13655182979505126
637 13763000684328217
638 13871498356276926
639 13980679206521853
640 14090546456327638
641 14201103337068801
642 14312353090245582
643 14424298967499781
644 14536944230630598
645 14650292151610473
646 14764346012600926
647 14879109105968397
648 14994584734300086
649 15110776210419793
650 15227686857403758
651 15345320008596501
652 15463679007626662
653 15582767208422841
654 15702587975229438
655 15823144682622493
656 15944440715525526
657 16066479469225377
658 16189264349388046
659 16312798772074533
660 16437086163756678
661 16562129961333001
662 16687933612144542
663 16814500573990701
664 16941834315145078
665 17069938314371313
666 17198816060938926
667 17328471054639157
668 17458906805800806
669 17590126835306073
670 17722134674606398
671 17854933865738301
672 17988527961339222
673 18122920524663361
674 18258115129597518
675 18394115360676933
676 18530924813101126
677 18668547092749737
678 18806985816198366
679 18946244610734413
680 19086327114372918
681 19227236975872401
682 19368977854750702
683 19511553421300821
684 19654967356606758
685 19799223352559353
686 19944325111872126
687 20090276348097117
688 20237080785640726
689 20384742159779553
690 20533264216676238
691 20682650713395301
692 20832905417918982
693 20984032109163081
694 21136034576992798
695 21288916622238573
696 21442682056711926
697 21597334703221297
698 21752878395587886
699 21909316978661493
700 22066654308336358
701 22224894251567001
702 22384040686384062
703 22544097501910141
704 22705068598375638
705 22866957887134593
706 23029769290680526
707 23193506742662277
708 23358174187899846
709 23523775582400233
710 23690314893373278
711 23857796099247501
712 24026223189685942
713 24195600165602001
714 24365931039175278
715 24537219833867413
716 24709470584437926
717 24882687336960057
718 25056874148836606
719 25232035088815773
720 25408174237006998
721 25585295684896801
722 25763403535364622
723 25942501902698661
724 26122594912611718
725 26303686702257033
726 26485781420244126
727 26668883226654637
728 26852996293058166
729 27038124802528113
730 27224272949657518
731 27411444940574901
732 27599644992960102
733 27788877336060121
734 27979146210704958
735 28170455869323453
736 28362810575959126
737 28556214606286017
738 28750672247624526
739 28946187798957253
740 29142765570944838
741 29340409885941801
742 29539125078012382
743 29738915492946381
744 29939785488274998
745 30141739433286673
746 30344781709042926
747 30548916708394197
748 30754148835995686
749 30960482508323193
750 31167922153688958
751 31376472212257501
752 31586137136061462
753 31796921389017441
754 32008829446941838
755 32221865797566693
756 32436034940555526
757 32651341387519177
758 32867789662031646
759 33085384299645933
760 33304129847909878
761 33524030866382001
762 33745091926647342
763 33967317612333301
764 34190712519125478
765 34415281254783513
766 34641028439156926
767 34867958704200957
768 35096076693992406
769 35325387064745473
770 35555894484827598
771 35787603634775301
772 36020519207310022
773 36254645907353961
774 36489988452045918
775 36726551570757133
776 36964340005107126
777 37203358508979537
778 37443611848537966
779 37685104802241813
780 37927842160862118
781 38171828727497401
782 38417069317589502
783 38663568758939421
784 38911331891723158
785 39160363568507553
786 39410668654266126
787 39662252026394917
788 39915118574728326
789 40169273201554953
790 40424720821633438
791 40681466362208301
792 40939514763025782
793 41198870976349681
794 41459539966977198
795 41721526712254773
796 41984836202093926
797 42249473438987097
798 42515443438023486
799 42782751226904893
800 43051401845961558
801 43321400348168001
802 43592751799158862
803 43865461277244741
804 44139533873428038
805 44414974691418793
806 44691788847650526
807 44969981471296077
808 45249557704283446
809 45530522701311633
810 45812881629866478
811 46096639670236501
812 46381802015528742
813 46668373871684601
814 46956360457495678
815 47245767004619613
816 47536598757595926
817 47828860973861857
818 48122558923768206
819 48417697890595173
820 48714283170568198
821 49012320072873801
822 49311813919675422
823 49612770046129261
824 49915193800400118
825 50219090543677233
826 50524465650190126
827 50831324507224437
828 51139672515137766
829 51449515087375513
830 51760857650486718
831 52073705644139901
832 52388064521138902
833 52703939747438721
834 53021336802161358
835 53340261177611653
836 53660718379293126
837 53982713925923817
838 54306253349452126
839 54631342195072653
840 54957986021242038
841 55286190399694801
842 55615960915459182
843 55947303166872981
844 56280222765599398
845 56614725336642873
846 56950816518364926
847 57288501962499997
848 57627787334171286
849 57968678311906593
850 58311180587654158
851 58655299866798501
852 59001041868176262
853 59348412324092041
854 59697416980334238
855 60048061596190893
856 60400351944465526
857 60754293811492977
858 61109892997155246
859 61467155314897333
860 61826086591743078
861 62186692668311001
862 62548979398830142
863 62912952651155901
864 63278618306785878
865 63645982260875713
866 64015050422254926
867 64385828713442757
868 64758323070664006
869 65132539443864873
870 65508483796728798
871 65886162106692301
872 66265580364960822
873 66646744576524561
874 67029660760174318
875 67414334948517333
876 67800773187993126
877 68188981538889337
878 68578966075357566
879 68970732885429213
880 69364288071031318
881 69759637748002401
882 70156788046108302
883 70555745109058021
884 70956515094519558
885 71359104174135753
886 71763518533540126
887 72169764372372717
888 72577847904295926
889 72987775357010353
890 73399552972270638
891 73813187005901301
892 74228683727812582
893 74646049422016281
894 75065290386641598
895 75486412933950973
896 75909423390355926
897 76334328096432897
898 76761133406939086
899 77189845690828293
900 77620471331266758
901 78053016725649001
902 78487488285613662
903 78923892437059341
904 79362235620160438
905 79802524289382993
906 80244764913500526
907 80688963975609877
908 81135127973147046
909 81583263417903033
910 82033376836039678
911 82485474768105501
912 82939563769051542
913 83395650408247201
914 83853741269496078
915 84313842951051813
916 84775962065633926
917 85240105240443657
918 85706279117179806
919 86174490352054573
920 86644745615809398
921 87117051593730801
922 87591414985666222
923 88067842506039861
924 88546340883868518
925 89026916862777433
926 89509577201016126
927 89994328671474237
928 90481178061697366
929 90970132173902913
930 91461197824995918
931 91954381846584901
932 92449691084997702
933 92947132401297321
934 93446712671297758
935 93948438785579853
936 94452317649507126
937 94958356183241617
938 95466561321759726
939 95976940014868053
940 96489499227219238
941 97004245938327801
942 97521187142585982
943 98040329849279581
944 98561681082603798
945 99085247881679073
946 99611037300566926
947 100139056408285797
948 100669312288826886
949 101201812041169993
950 101736562779299358
951 102273571632219501
952 102812845743971062
953 103354392273646641
954 103898218395406638
955 104444331298495093
956 104992738187255526
957 105543446281146777
958 106096462814758846
959 106651795037828733
960 107209450215256278
961 107769435627120001
962 108331758568692942
963 108896426350458501
964 109463446298126278
965 110032825752647913
966 110604572070232926
967 111178692622364557
968 111755194795815606
969 112334085992664273
970 112915373630309998
971 113499065141489301
972 114085167974291622
973 114673689592175161
974 115264637473982718
975 115858019113957533
976 116453842021759126
977 117052113722479137
978 117652841756657166
979 118256033680296613
980 118861697064880518
981 119469839497387401
982 120080468580307102
983 120693591931656621
984 121309217184995958
985 121927351989443953
986 122548004009694126
987 123171180926030517
988 123796890434343526
989 124425140246145753
990 125055938088587838
991 125689291704474301
992 126325208852279382
993 126963697306162881
994 127604764855985998
995 128248419307327173
996 128894668481497926
997 129543520215558697
998 130194982362334686
999 130849062790431693
1000 131505769384251958