1 0
2 1
3 1025
4 8801
5 41569
6 100618
7 200618
8 449450
9 987274
10 1746649
11 2795225
12 4684793
13 7884793
14 11968894
15 17122526
16 25085150
17 34850775
18 46732151
19 61081058
20 78291426
21 102591426
22 136145858
23 175281251
24 220716675
25 273238550
26 333704726
27 412939894
28 503164093
29 605564093
30 736255325
31 901171549
32 1085699674
33 1291662650
34 1546466618
35 1828941867
36 2141441867
37 2486467118
38 2866671150
39 3325836174
40 3829120549
41 4379852325
42 4981544382
43 5637901150
44 6415501150
45 7331633982
46 8324070525
47 9397812349
48 10558102974
49 11810435550
50 13264369118
51 14828400467
52 16509100467
53 18444018099
54 20663024723
55 23036071598
56 25571596974
57 28278381131
58 31165555499
59 34442355499
60 37929139900
61 41636538332
62 45818657756
63 50255710881
64 54959981057
65 59944190264
66 65221509432
67 71126409432
68 77366730883
69 83957546115
70 90914429808
71 98253470032
72 105991279407
73 114145006383
74 123184214351
75 132694114850
76 142694114850
77 153734922882
78 165901451906
79 178664267531
80 192046523307
81 206739804075
82 222844904075
83 239695485626
84 257318902458
85 276573048282
86 296686620157
87 317690036733
88 339614517090
89 362492094658
90 386355631257
91 411238831257
92 437176255858
93 464203337490
94 492356394333
95 521672644957
96 552190223082
97 583948192458
98 618307930826
99 654030982475
100 691160282475
101 731234924907
102 772850720800
103 816054724224
104 860895058599
105 907420932775
106 957469935943
107 1011252335943
108 1066983172644
109 1124718511876
110 1184515620819
111 1246432985043
112 1310530325668
113 1376868616644
114 1445510102151
115 1516518314119
116 1592455814119
117 1673592626151
118 1757433762144
119 1844050855168
120 1933516952043
121 2025906531819
122 2124372336587
123 2225993841386
124 2330851441386
125 2439027058187
126 2550604159019
127 2669240908843
128 2791539011968
129 2917588312544
130 3051416134112
131 3189274625961
132 3331260325961
133 3477471495812
134 3628008141444
135 3787502836068
136 3951633695443
137 4120507908819
138 4294234513476
139 4472924415844
140 4661881215844
141 4861571502276
142 5066808403419
143 5277714490843
144 5494414356468
145 5717034634644
146 5945704024351
147 6180553311519
148 6421715391468
149 6669325291468
150 6930244554700
151 7205039442924
152 7486990064799
153 7776244719775
154 8080561535743
155 8400561535743
156 8728641936744
157 9064965152776
158 9409696034019
159 9763001891043
160 10125052519168
161 10496020222944
162 10876079840751
163 11265408769519
164 11664186989568
165 12072597089568
166 12500829274400
167 12939257006693
168 13388073560517
169 13847474944892
170 14317659929468
171 14798830070325
172 15291189735893
173 15794946132992
174 16310309332992
175 16837492298093
176 17376710907725
177 17940660246349
178 18517310636974
179 19106889894350
180 19723022560718
181 20366656860718
182 21024405410869
183 21696514741301
184 22398098112725
185 23114801259600
186 23846883741776
187 24594608446733
188 25358241617901
189 26154504017901
190 26984501605133
191 27831790214576
192 28696656826800
193 29579391979925
194 30480289798901
195 31399648024908
196 32337768044876
197 33294954921125
198 34271517421125
199 35287772441157
200 36324351917650
201 37381579738674
202 38459783648049
203 39559295275825
204 40702432928593
205 41867896813892
206 43056034413892
207 44267197251193
208 45501740920025
209 46784129477849
210 48090990393474
211 49422695862050
212 50779622308157
213 52162150417725
214 53597041117725
215 55085869091357
216 56602267203950
217 58146642386574
218 59719406058449
219 61320974159825
220 62981417190193
221 64671939927592
222 66392976727592
223 68176363502024
224 70023894357448
225 71904182035573
226 73817689521749
227 75764884691956
228 77746240347124
229 79762234247573
230 81813349147573
231 83900072830024
232 86022898141256
233 88219425677480
234 90453564111855
235 92725826894831
236 95036732716088
237 97386805540056
238 99776574641555
239 102206574641555
240 104677345543056
241 107189432767088
242 109743387188831
243 112339765173855
244 114979128614480
245 117662044966256
246 120433791943024
247 123250827943573
248 126113743043573
249 129070209596405
250 132122657358229
251 135224021555104
252 138374927307680
253 141626815461248
254 144930156518847
255 148285599718847
256 151693800424448
257 155155420162080
258 158671126659923
259 162241593886547
260 165867502089672
261 169549537835048
262 173288394045455
263 177084770039823
264 180939371572472
265 184852910872472
266 188886488490904
267 192981179807797
268 197137723347221
269 201356864306596
270 205639354596772
271 210050826335940
272 214527943821639
273 219071486221639
274 223682239619340
275 228360997054572
276 233108558564515
277 237925731224739
278 242813329190364
279 247772173737340
280 252876003965308
281 258128191465308
282 263455840192059
283 268859815020091
284 274419066369115
285 280057283090990
286 285775359966766
287 291574199360323
288 297454711261091
289 303501328861091
290 309632395118892
291 315848850955724
292 322151645133767
293 328541734299591
294 335020083027716
295 341587663864292
296 348336658661860
297 355177851474709
298 362112247174709
299 369140858825560
300 376264707727192
301 383582128197816
302 390997899682191
303 398513076871567
304 406128722917224
305 413845909475592
306 421769426275592
307 429797750041493
308 437931986903925
309 446281403327349
310 454740103817974
311 463309229712150
312 471989931262857
313 480783367686025
314 489805787586025
315 498944474248976
316 508200623208208
317 517575439193401
318 527070136177625
319 536685937424500
320 546424075535476
321 556410622767444
322 566523261169443
323 576763261169443
324 587261834001475
325 597891637363718
326 608653980276742
327 619550181529867
328 630581569729643
329 641749483348450
330 653055270773218
331 664640890873218
332 676368489916269
333 688239456437101
334 700255189130394
335 712417096900218
336 724726598909593
337 737185124630169
338 749794113892026
339 762555016933594
340 775624140133594
341 789007410599226
342 802550003917569
343 816253433832193
344 830119224847818
345 844148912281194
346 858344042312101
347 872706172034469
348 887236869507618
349 901937713807618
350 916983633314050
351 932381077821474
352 947956731593349
353 963712240891525
354 979649263357482
355 995769468064650
356 1012261090464650
357 1028940971442851
358 1045810826326083
359 1063065821834307
360 1080516007612432
361 1098163146087408
362 1116009011594415
363 1134055390430383
364 1152508202930383
365 1171166959957634
366 1190033496193666
367 1209109658551159
368 1228397306228183
369 1247898310762558
370 1267614556086334
371 1287766984635102
372 1308140380681401
373 1328736678281401
374 1349784631886233
375 1371292130460057
376 1393032392000682
377 1415007427405258
378 1437458095290826
379 1460149647964175
380 1483084148664175
381 1506263673855526
382 1529690313285158
383 1553366170038751
384 1577293360597375
385 1601474014894250
386 1625910276371626
387 1650604302037783
388 1675558262524151
389 1701038659324151
390 1726785585150552
391 1752801265700984
392 1779087940583627
393 1805647863375051
394 1832483301678176
395 1859596537180352
396 1887272268771520
397 1915232727712969
398 1943480252612969
399 1972308982820201
400 2001431881305894
401 2030851344538118
402 2060569783597493
403 2090589624236469
404 2120913306938726
405 2151543286978694
406 2182793286978694
407 2214357039481195
408 2246237059521227
409 2278757220162251
410 2311601284227876
411 2344771827475652
412 2378271440994959
413 2412102731267727
414 2446605256367727
415 2481447370631278
416 2516631742720110
417 2552161056993903
418 2588038013571727
419 2624265328393602
420 2660845733282178
421 2697781976004535
422 2735076820334103
423 2772733046112702
424 2810753449312702
425 2849510660106334
426 2889016057508958
427 2928899856337083
428 2969164950658459
429 3009814251109866
430 3050850684960234
431 3092277196173883
432 3134096745473883
433 3176312310405534
434 3218926885399966
435 3261943481837859
436 3305365128113283
437 3349194869697658
438 3393435769203834
439 3438090906450291
440 3483163378525459
441 3528656299852158
442 3574572802252158
443 3621345932183390
444 3668552143694333
445 3716194638850557
446 3764276637441182
447 3812801377044158
448 3862221382888126
449 3912093949865875
450 3962422387365875
451 4013210022893626
452 4064460202137658
453 4116176289035651
454 4168361665840675
455 4221019733187550
456 4274153910159326
457 4328250637756094
458 4382833843582893
459 4437907021182893
460 4493473682881694
461 4549537359854526
462 4606605736636350
463 4664181835989475
464 4722269265162051
465 4780871650589658
466 4839992637963226
467 4900161843663226
468 4961394083220858
469 5023163444394951
470 5085473689841575
471 5148328601950950
472 5211731982916326
473 5276243787730694
474 5341315587489593
475 5406951264289593
476 5473154720376494
477 5539929878214926
478 5607280680558069
479 5675211090517493
480 5743725091633118
481 5812826687943294
482 5883115569102462
483 5954004181264411
484 6025496611164411
485 6097596966388362
486 6170309375443594
487 6244258361723818
488 6318831913595693
489 6394034243962669
490 6469869587005426
491 6546342198253394
492 6624102198253394
493 6703166867101426
494 6782890404544669
495 6863277195713693
496 6944331647591818
497 7026058189087594
498 7109142284608362
499 7192911888750411
500 7277371518850411
501 7362525714534462
502 7448379037791294
503 7535644391977118
504 7623622694611493
505 7712318597868069
506 7802463749885637
507 7894077033085637
508 7986431520212738
509 8079532000934370
510 8173383288093713
511 8267990217784337
512 8363357649424962
513 8459490465834338
514 8556393573306245
515 8654071901684613
516 8752530404438762
517 8851774058738762
518 8952603042821194
519 9054232252919587
520 9156666761763011
521 9259911666159886
522 9363972087074062
523 9468853169701019
524 9574560083544187
525 9681098022491386
526 9788472204891386
527 9897534627470618
528 10008306459074842
529 10119940995477967
530 10232443603408943
531 10346698554660911
532 10461837827939160
533 10577866890439160
534 10694791234667411
535 10812616378519443
536 10932259777252467
537 11052820682411842
538 11174304714231618
539 11296717518726675
540 11420064767771443
541 11545298025371443
542 11672440291312275
543 11800545751831818
544 11929620235621642
545 12059669597787267
546 12190699719927843
547 12322716510215950
548 12455725903477518
549 12589733861271867
550 12724746371971867
551 12860769450844218
552 12997809140129850
553 13136900285264474
554 13277026330186349
555 13418193425839725
556 13561461185382093
557 13705788613081492
558 13851181969881492
559 13997647544428893
560 14145191653155325
561 14294911891082749
562 14445729780010874
563 14597651748329050
564 14750684252621257
565 14904833777748425
566 15060106836930874
567 15216509971830874
568 15375192997334106
569 15535025895020799
570 15696015321149023
571 15858167960833398
572 16021490528128374
573 16185989766111631
574 16351672446967599
575 16518545372071098
576 16686615372071098
577 16857100131327130
578 17028802633910873
579 17201729828407897
580 17375888693098522
581 17551286236042298
582 17727929495162605
583 17905825538331373
584 18086248473431373
585 18267945576735924
586 18450924036760756
587 18635191072395549
588 18820753932989373
589 19007619898436248
590 19195796279260824
591 19385290416704181
592 19576109682809749
593 19769601446009749
594 19964440639677350
595 20160634759926982
596 20358191334106825
597 20557117920885449
598 20757422110338574
599 20959111524035950
600 21163594377342318
601 21369485509436967
602 21576792668736967
603 21785523635589618
604 21995686222360050
605 22208735614571474
606 22423240256780849
607 22639208090303025
608 22856647088910482
609 23075565258921650
610 23297465921321650
611 23520869970241351
612 23745785543068583
613 23973748707920807
614 24203248007136432
615 24434291710595408
616 24666888121523915
617 24901045576583883
618 25136772445962632
619 25374077133462632
620 25614562803522664
621 25856651705701657
622 26100352379162681
623 26345673397134556
624 26592623367002332
625 26842857199895100
626 27094746012682899
627 27348298550282899
628 27605204910791731
629 27863801438891774
630 28124097018489598
631 28386100568467723
632 28649821042776299
633 28915267430524906
634 29182448756074474
635 29453127171774474
636 29725567810787325
637 29999779839400957
638 30277562289023581
639 30557143841757956
640 30838533807299332
641 31121741531426989
642 31406776396097357
643 31693647819537256
644 31982365256337256
645 32272938197545157
646 32565376170759589
647 32859688740223732
648 33155885506919156
649 33453976108659781
650 33753970220185957
651 34057800523681125
652 34363563583684074
653 34671269223584074
654 34980927304169025
655 35292547723720257
656 35606140418107450
657 35921715360883674
658 36239282563380549
659 36558852074803525
660 36882456503667493
661 37208093617271492
662 37535773617271492
663 37865506743675493
664 38197303274939525
665 38531173528063768
666 38867127858688792
667 39205176661191917
668 39545330368783693
669 39887599453604500
670 40231994426821268
671 40580672866921268
672 40933677289314100
673 41288860744729393
674 41646233980531217
675 42005807783790592
676 42367592981383168
677 42731600440087025
678 43097841066680593
679 43466325808040692
680 43837065651240692
681 44212348820618324
682 44592219749284948
683 44974401321550573
684 45358904767735949
685 45748085816370317
686 46141989880670317
687 46538272585783468
688 46936945408841900
689 47338019868461293
690 47741507524840717
691 48147419979862592
692 48555768877192768
693 48966565902380725
694 49379822782959893
695 49798034725359893
696 50218741958660094
697 50641956379335326
698 51067689926347769
699 51495954581247993
700 51926762368276118
701 52360125354463094
702 52796055649732101
703 53234565407000069
704 53675666822279318
705 54119372134779318
706 54565693627008569
707 55014643624876601
708 55468887785865625
709 55925797691650000
710 56385385842765776
711 56850368161906544
712 57320795179506544
713 57793963605866845
714 58269886206543677
715 58751355630749501
716 59235617793540126
717 59722685639216702
718 60212572157025809
719 60705290381263377
720 61200853391378726
721 61699274312078726
722 62200566313432077
723 62704742610973709
724 63211816465809302
725 63721801184719926
726 64234710120266801
727 64750556670896177
728 65272318831094545
729 65797059078074944
730 66324790994874944
731 66858547186177376
732 67398382542440800
733 67941278181993925
734 68487247967928101
735 69039407824191269
736 69594683698814718
737 70153089643714718
738 70714639758280169
739 71279348189479401
740 71847229131967094
741 72418296828191318
742 72992565568500693
743 73570049691251669
744 74150763582915926
745 74734721678187894
746 75321938460092393
747 75912428460092393
748 76506206258196894
749 77103286483068926
750 77703683812133669
751 78307412971686693
752 78914488737002318
753 79524925932442094
754 80142130658106862
755 80762741582590411
756 81386773727690411
757 82017693578051243
758 82652080012647036
759 83289948252456860
760 83931313568528735
761 84576191282089311
762 85224596764653668
763 85876545438135236
764 86535626961335236
765 87198298244683837
766 87864574912789469
767 88534472641210312
768 89208007156564936
769 89885194236643061
770 90566049710516437
771 91250589458649844
772 91938829413012212
773 92634517782312212
774 93333954463885863
775 94037155596832295
776 94744137372312188
777 95454916033659612
778 96169507876493987
779 96887929248832163
780 97614058934379331
781 98344067508988030
782 99077971531388030
783 99819716337511262
784 100565406585824205
785 101315059047572429
786 102068690547413054
787 102826317963528030
788 103591988061403998
789 104361705032383747
790 105135485969883747
791 105913348021413498
792 106695308388689530
793 107485517210006554
794 108279876278603429
795 109078403014167205
796 109881114891163762
797 110688029438952530
798 111499164241901329
799 112314536939501329
800 113134165226482130
801 113958066852926962
802 114786259624388005
803 115618761402001829
804 116455590102604954
805 117296763698849530
806 118146681228175098
807 119000997907150947
808 119859731932850947
809 120727355468920579
810 121599451281776672
811 122476037794775296
812 123357133488134671
813 124242756899052047
814 125137491585178415
815 126036809943499314
816 126940730740299314
817 127849272799428215
818 128762455002418647
819 129684974369050071
820 130612190871415696
821 131544123622957872
822 132480791795391579
823 133422214618822747
824 134368411381866696
825 135319401431766696
826 136280036332213928
827 137245522914202121
828 138215880760674345
829 139191129513796220
830 140171288875075196
831 141161328795155164
832 142156338785160163
833 143156338785160163
834 144161348795165164
835 145171388875245196
836 146186479145650439
837 147206639786931463
838 148231891040059588
839 149262253206547364
840 150297746648569171
841 151338391789081939
842 152389401839181939
843 153445625222547990
844 154507082606476822
845 155579070239094646
846 156656354242979021
847 157738955531707597
848 158826895080732454
849 159920193927502022
850 161024274730702022
851 162139222387135654
852 163259635462776997
853 164385535369619621
854 165516943582510246
855 166653881639271622
856 167796371140825529
857 168944433751315897
858 170098091198232046
859 171257365272532046
860 172427938228966478
861 173609897996081902
862 174797584301728777
863 175991019320274953
864 177190225290423910
865 178395224515339078
866 179611877417739078
867 180834390872400279
868 182062787441571511
869 183297089752584954
870 184537320497981178
871 185783502435634303
872 187035658388877279
873 188293811246627286
874 189557983963511254
875 190834265526011254
876 192122748544295286
877 193417367184895779
878 194718144799340803
879 196025104805750178
880 197338270688961954
881 198657666000659011
882 199983314359495779
883 201315239451225078
884 202653465028825078
885 204004363106637910
886 205368029506459734
887 206738116169875359
888 208114647255887935
889 209497646991618042
890 210887139672431610
891 212289691403131610
892 213698809375765961
893 215114518159963593
894 216536842394240186
895 217965806786126810
896 219401436112298685
897 220843755218704061
898 222292789020693218
899 223748562503147586
900 225211100720608985
901 226680428797408985
902 228156571927798386
903 229639555376076818
904 231129404476722461
905 232626144634521885
906 234129801324700010
907 235640400093050186
908 237164959938049354
909 238696538923313803
910 240235162878213803
911 241787954545509035
912 243355018099029259
913 244929256839963634
914 246510697026970610
915 248106619170258578
916 249709821968164077
917 251320331968164077
918 252938175790269578
919 254563380127157610
920 256203385862966634
921 257850832628907259
922 259505747409643035
923 261168157263165342
924 262838089320926110
925 264523147476026110
926 266215809671812661
927 267916103334909493
928 269624055966066286
929 271339695140292110
930 273063048506988985
931 274794143790085561
932 276540806376543129
933 278295294499684728
934 280057636182884728
935 281827859524714329
936 283605992699075961
937 285400030362206585
938 287202062832909710
939 289012118587759086
940 290830226179333493
941 292656414236351861
942 294498849415651861
943 296349451404746512
944 298208249138268944
945 300075271627669837
946 301950547961353261
947 303834107304812636
948 305725978900766812
949 307626192069296269
950 309534776207979437
951 311451760792029136
952 313377175374429136
953 315311049586070837
954 317253413135890069
955 319204295811004012
956 321163727476848236
957 323131738077313861
958 325108357634884837
959 327093616250775344
960 329087544105067312
961 331090171456848061
962 333101528644348061
963 335130436835240093
964 337177018335613117
965 339232482554834992
966 341296860308894768
967 343370182493892325
968 345452480086177093
969 347543784142486892
970 349644125800086892
971 351753536276908693
972 353872046871689525
973 356008851922519349
974 358154851473747474
975 360310077148728050
976 362474560652318657
977 364648333771020225
978 366831428373117074
979 369023876408817074
980 371235127490742706
981 373455828349839799
982 375686011265414423
983 377925708599398798
984 380174952796492174
985 382433776384301831
986 384702211973484199
987 386980292257886098
988 389268050014686098
989 391575261381852530
990 393892249054358673
991 396219046144126097
992 398555685847116722
993 400902201443474898
994 403268569004442066
995 405644912805727015
996 408031266465627015
997 410427663687333966
998 412834138259077198
999 415260869236445422
1000 417697779440192297