1 1
2 4
3 14
4 39
5 96
6 213
7 437
8 837
9 1520
10 2632
11 4380
12 7040
13 10979
14 16668
15 24716
16 35879
17 51104
18 71549
19 98625
20 134025
21 179782
22 238292
23 312386
24 405368
25 521083
26 663968
27 839140
28 1052439
29 1310534
30 1620985
31 1992343
32 2434229
33 2957458
34 3574108
35 4297666
36 5143120
37 6127097
38 7267976
39 8586054
40 10103647
41 11845282
42 13837825
43 16110663
44 18695857
45 21628356
46 24946136
47 28690444
48 32905968
49 37641069
50 42947980
51 48883074
52 55507047
53 62885220
54 71087757
55 80189953
56 90272485
57 101421740
58 113730048
59 127296048
60 142224960
61 158628935
62 176627364
63 196347272
64 217923607
65 241499676
66 267227477
67 295268117
68 325792185
69 358980218
70 395023052
71 434122334
72 476490920
73 522353367
74 571946376
75 625519336
76 683334743
77 745668794
78 812811857
79 885069043
80 962760725
81 1046223166
82 1135809012
83 1231887974
84 1334847376
85 1445092813
86 1563048752
87 1689159250
88 1823888527
89 1967721742
90 2121165625
91 2284749227
92 2459024609
93 2644567656
94 2841978736
95 3051883576
96 3274933984
97 3511808697
98 3763214164
99 4029885462
100 4312587047
101 4612113736
102 4929291525
103 5264978541
104 5620065925
105 5995478856
106 6392177400
107 6811157604
108 7253452416
109 7720132747
110 8212308460
111 8731129508
112 9277786887
113 9853513848
114 10459586925
115 11097327113
116 11768100969
117 12473321870
118 13214451076
119 13992999066
120 14810526680
121 15668646419
122 16569023664
123 17513378060
124 18503484695
125 19541175566
126 20628340841
127 21766930287
128 22958954613
129 24206486986
130 25511664332
131 26876688938
132 28303829840
133 29795424385
134 31353879704
135 32981674366
136 34681359807
137 36455562074
138 38306983345
139 40238403631
140 42252682385
141 44352760300
142 46541660872
143 48822492292
144 51198449104
145 53672814053
146 56248959836
147 58930351050
148 61720545895
149 64623198220
150 67642059325
151 70780979961
152 74043912229
153 77434911684
154 80958139184
155 84617863096
156 88418461248
157 92364423087
158 96460351732
159 100710966240
160 105121103607
161 109695721140
162 114439898565
163 119358840349
164 124457877913
165 129742472066
166 135218215164
167 140890833654
168 146766190344
169 152850286895
170 159149266200
171 165669414992
172 172417166167
173 179399101506
174 186621954113
175 194092611083
176 201818116053
177 209805671990
178 218062643684
179 226596560654
180 235415119760
181 244526188053
182 253937805504
183 263658187978
184 273695729903
185 284059007366
186 294756780905
187 305797998547
188 317191798721
189 328947513424
190 341074671072
191 353582999792
192 366482430400
193 379783099633
194 393495353252
195 407629749406
196 422197061671
197 437208282544
198 452674626613
199 468607533989
200 485018673605
201 501919946784
202 519323490472
203 537241680940
204 555687137152
205 574672724403
206 594211557820
207 614317006140
208 635002695143
209 656282511568
210 678170606685
211 700681400145
212 723829583689
213 747630125142
214 772098272052
215 797249555826
216 823099795512
217 849665101867
218 876961881280
219 905006839988
220 933816987927
221 963409643094
222 993802435545
223 1025013311687
224 1057060538421
225 1089962707586
226 1123738740028
227 1158407890194
228 1193989750352
229 1230504255113
230 1267971685800
231 1306412675126
232 1345848211487
233 1386299643794
234 1427788685921
235 1470337421463
236 1513968308337
237 1558704183700
238 1604568268472
239 1651584172412
240 1699775898800
241 1749167849437
242 1799784829484
243 1851652052626
244 1904795145831
245 1959240154676
246 2015013548269
247 2072142224497
248 2130653515109
249 2190575191132
250 2251935467872
251 2314763010496
252 2379086939200
253 2444936834711
254 2512342743620
255 2581335184056
256 2651945150935
257 2724204121804
258 2798144062261
259 2873797431717
260 2951197188985
261 3030376798218
262 3111370234412
263 3194211989518
264 3278937078120
265 3365581043463
266 3454179963304
267 3544770456120
268 3637389686871
269 3732075373386
270 3828865792305
271 3927799785379
272 4028916765589
273 4132256723630
274 4237860233940
275 4345768461366
276 4456023167376
277 4568666716637
278 4683742083408
279 4801292858306
280 4921363254607
281 5043998115198
282 5169242919065
283 5297143788155
284 5427747494049
285 5561101465016
286 5697253792592
287 5836253238824
288 5978149243040
289 6122991929001
290 6270832111860
291 6421721305510
292 6575711729447
293 6732856316312
294 6893208718949
295 7056823317853
296 7223755228421
297 7394060308600
298 7567795166040
299 7745017165940
300 7925784438400
301 8110155886171
302 8298191192204
303 8489950827604
304 8685496059079
305 8884888957096
306 9088192403533
307 9295470099737
308 9506786574377
309 9722207191710
310 9941798159332
311 10165626536650
312 10393760242840
313 10626268065219
314 10863219667408
315 11104685597916
316 11350737298199
317 11601447111454
318 11856888290889
319 12117135008415
320 12382262363125
321 12652346390202
322 12927464069292
323 13207693333626
324 13493113078608
325 13783803170833
326 14079844456888
327 14381318772590
328 14688308951679
329 15000898835274
330 15319173280785
331 15643218171263
332 15973120424529
333 16308968002748
334 16650849921448
335 16998856259316
336 17353078167440
337 17713607878997
338 18080538718716
339 18453965112794
340 18833982598247
341 19220687833052
342 19614178605725
343 20014553845353
344 20421913631397
345 20836359203956
346 21257992973456
347 21686918531144
348 22123240659008
349 22567065340159
350 23018499768980
351 23477652361744
352 23944632766647
353 24419551874660
354 24902521829797
355 25393656039853
356 25893069186905
357 26400877238290
358 26917197456988
359 27442148412838
360 27975849993160
361 28518423413855
362 29069991230264
363 29630677348512
364 30200607036247
365 30779906934226
366 31368705067297
367 31967130855867
368 32575315127125
369 33193390126758
370 33821489530052
371 34459748453854
372 35108303467920
373 35767292606757
374 36436855381216
375 37117132790586
376 37808267334063
377 38510403023094
378 39223685393097
379 39948261515683
380 40684280010625
381 41431891058336
382 42191246411712
383 42962499408864
384 43745804985216
385 44541319686113
386 45349201679172
387 46169610767150
388 47002708400167
389 47848657688832
390 48707623416725
391 49579772053397
392 50465271767109
393 51364292438096
394 52277005671176
395 53203584809276
396 54144204946304
397 55099042940547
398 56068277427804
399 57052088835052
400 58050659393447
401 59064173152256
402 60092815992125
403 61136775638881
404 62196241677065
405 63271405564006
406 64362460643220
407 65469602158754
408 66593027268856
409 67732935060187
410 68889526561760
411 70063004759428
412 71253574609687
413 72461443054438
414 73686819035065
415 74929913507063
416 76190939454389
417 77470111904370
418 78767647941916
419 80083766724706
420 81418689497680
421 82772639608089
422 84145842520264
423 85538525830950
424 86950919283935
425 88383254785666
426 89835766420161
427 91308690464487
428 92802265403953
429 94316731947876
430 95852333044632
431 97409313897708
432 98987921981040
433 100588407054925
434 102211021181644
435 103856018741666
436 105523656449127
437 107214193368324
438 108927890929485
439 110665012945121
440 112425825626085
441 114210597598220
442 116019599918272
443 117853106090832
444 119711392084544
445 121594736348903
446 123503419830756
447 125437725991400
448 127397940822935
449 129384352865660
450 131397253224725
451 133436935587381
452 135503696239929
453 137597834085274
454 139719650659724
455 141869450150846
456 144047539414568
457 146254227992887
458 148489828131272
459 150754654796680
460 153049025694807
461 155373261288410
462 157727684814865
463 160112622304339
464 162528402597653
465 164975357364766
466 167453821122484
467 169964131253254
468 172506628023184
469 175081654600685
470 177689557074800
471 180330684474162
472 183005388785167
473 185714024971246
474 188456950991353
475 191234527819083
476 194047119461473
477 196895092978440
478 199778818501424
479 202698669253144
480 205655021566560
481 208648254904473
482 211678751878804
483 214746898270518
484 217853083048743
485 220997698391016
486 224181139702725
487 227403805637197
488 230666098115461
489 233968422346664
490 237311186847672
491 240694803463812
492 244119687388800
493 247586257185323
494 251094934805292
495 254646145610756
496 258240318393991
497 261877885398744
498 265559282340653
499 269284948428329
500 273055326384105
501 276870862465454
502 280732006485572
503 284639211835130
504 288592935503192
505 292593638098803
506 296641783872240
507 300737840736940
508 304882280290583
509 309075577837358
510 313318212409385
511 317610666788815
512 321953427529589
513 326346984979882
514 330791833303692
515 335288470503626
516 339837398442832
517 344439122867617
518 349094153429720
519 353803003709278
520 358566191236927
521 363384237517114
522 368257668050545
523 373187012357327
524 378172803999761
525 383215580605836
526 388315883891848
527 393474259686244
528 398691257952592
529 403967432813253
530 409303342572700
531 414699549741546
532 420156621059687
533 425675127520684
534 431255644395261
535 436898751255513
536 442605031998757
537 448375074872100
538 454209472496112
539 460108821889752
540 466073724494400
541 472104786198607
542 478202617362484
543 484367832842816
544 490601052017271
545 496902898809876
546 503274001715589
547 509714993825597
548 516226512852249
549 522809201154722
550 529463705763772
551 536190678407766
552 542990775537800
553 549864658353551
554 556812992828760
555 563836449737456
556 570935704679255
557 578111438105954
558 585364335347201
559 592695086636907
560 600104387139285
561 607592936975638
562 615161441250212
563 622810610077358
564 630541158607760
565 638353807055413
566 646249280724224
567 654228310035370
568 662291630553711
569 670439983015526
570 678674113355305
571 686994772733299
572 695402717562689
573 703898709537520
574 712483515659680
575 721157908267216
576 729922665061696
577 738778569136337
578 747726409003748
579 756766978624446
580 765901077434407
581 775129510373968
582 784453087915765
583 793872626093445
584 803388946529989
585 813002876466816
586 822715248791912
587 832526902069324
588 842438680567680
589 852451434289491
590 862566019000060
591 872783296257180
592 883104133439847
593 893529403778352
594 904059986383389
595 914696766275953
596 925440634416841
597 936292487736950
598 947253229166580
599 958323767666130
600 969505018255800
601 980797902046091
602 992203346267904
603 1003722284303444
604 1015355655716119
605 1027104406281846
606 1038969488019353
607 1050951859221287
608 1063052484484917
609 1075272334743650
610 1087612387297532
611 1100073625845170
612 1112657040514640
613 1125363627895209
614 1138194391068648
615 1151150339641366
616 1164232489775519
617 1177441864221554
618 1190779492349729
619 1204246410182455
620 1217843660426225
621 1231572292504372
622 1245433362588792
623 1259427933633116
624 1273557075404848
625 1287821864518333
626 1302223384467308
627 1316762725658290
628 1331440985442919
629 1346259268151764
630 1361218685127085
631 1376320354756433
632 1391565402505829
633 1406954960953788
634 1422490169824288
635 1438172176021216
636 1454002133661760
637 1469981204110647
638 1486110556013956
639 1502391365333784
640 1518824815381847
641 1535412096854572
642 1552154407867125
643 1569052953988293
644 1586108948274937
645 1603323611307306
646 1620698171223276
647 1638233863754094
648 1655931932259048
649 1673793627760999
650 1691820208981480
651 1710012942376664
652 1728373102172247
653 1746901970399850
654 1765600836932337
655 1784470999520003
656 1803513763826325
657 1822730443464590
658 1842122360033428
659 1861690843153878
660 1881437230505360
661 1901362867862525
662 1921469109131664
663 1941757316388002
664 1962228859911887
665 1982885118226526
666 2003727478134617
667 2024757334755867
668 2045976091564065
669 2067385160425048
670 2088985961633552
671 2110779923951624
672 2132768484645920
673 2154953089525897
674 2177335192981556
675 2199916258022086
676 2222697756313383
677 2245681168217144
678 2268867982828837
679 2292259698016573
680 2315857820459525
681 2339663865687256
682 2363679358117912
683 2387905831098004
684 2412344826941056
685 2436997896967163
686 2461866601542092
687 2486952510117300
688 2512257201268807
689 2537782262737672
690 2563529291469325
691 2589499893653817
692 2615695684765609
693 2642118289604286
694 2668769342334116
695 2695650486525226
696 2722763375193624
697 2750109670842147
698 2777691045500944
699 2805509180768892
700 2833565767853847
701 2861862507614526
702 2890401110601225
703 2919183297097471
704 2948210797161205
705 2977485350666906
706 3007008707346540
707 3036782626832154
708 3066808878697296
709 3097089242499377
710 3127625507821560
711 3158419474315598
712 3189472951743487
713 3220787760020778
714 3252365729258705
715 3284208699807263
716 3316318522297809
717 3348697057686620
718 3381346177297256
719 3414267762864596
720 3447463706577680
721 3480935911123509
722 3514686289730364
723 3548716766212090
724 3583029275011175
725 3617625761243516
726 3652508180741981
727 3687678500100937
728 3723138696720293
729 3758890758850516
730 3794936685636432
731 3831278487162728
732 3867918184498240
733 3904857809741215
734 3942099406064084
735 3979645027759216
736 4017496740283447
737 4055656620304324
738 4094126755745125
739 4132909245830861
740 4172006201133785
741 4211419743619890
742 4251152006694172
743 4291205135247622
744 4331581285702984
745 4372282626061503
746 4413311335949176
747 4454669606664000
748 4496359641221975
749 4538383654404850
750 4580743872806625
751 4623442534881051
752 4666481890988629
753 4709864203444614
754 4753591746565764
755 4797666806718846
756 4842091682367888
757 4886868684122437
758 4932000134785312
759 4977488369401370
760 5023335735305007
761 5069544592169430
762 5116117312054665
763 5163056279456579
764 5210363891355393
765 5258042557265216
766 5306094699282304
767 5354522752135104
768 5403329163233024
769 5452516392716225
770 5502086913504900
771 5552043211349582
772 5602387784880167
773 5653123145656736
774 5704251818219093
775 5755776340137333
776 5807699262061893
777 5860023147774640
778 5912750574238664
779 5965884131649884
780 6019426423487360
781 6073380066564643
782 6127747691080604
783 6182531940671308
784 6237735472460583
785 6293360957112416
786 6349411078882045
787 6405888535668097
788 6462796039064201
789 6520136314411654
790 6577912100850772
791 6636126151374082
792 6694781232878200
793 6753880126216763
794 6813425626252832
795 6873420541912356
796 6933867696236311
797 6994769926434694
798 7056130083939193
799 7117951034456919
800 7180235658023605
801 7242986849057874
802 7306207516414172
803 7369900583437570
804 7434068988017232
805 7498715682640953
806 7563843634449160
807 7629455825289990
808 7695555251773023
809 7762144925324898
810 7829227872243585
811 7896807133753735
812 7964885766061489
813 8033466840410372
814 8102553443135832
815 8172148675721676
816 8242255654855152
817 8312877512483117
818 8384017395867660
819 8455678467642818
820 8527863905869927
821 8600576904094884
822 8673820671404045
823 8747598432481217
824 8821913427664101
825 8896768913001836
826 8972168160311168
827 9048114457234544
828 9124611107296832
829 9201661429963143
830 9279268760696100
831 9357436451014216
832 9436167868548887
833 9515466397103324
834 9595335436710101
835 9675778403689813
836 9756798730709177
837 9838399866840250
838 9920585277618252
839 10003358445101342
840 10086722867929000
841 10170682061381527
842 10255239557438984
843 10340398904841256
844 10426163669146711
845 10512537432792826
846 10599523795155409
847 10687126372608947
848 10775348798586389
849 10864194723640062
850 10953667815501172
851 11043771759141286
852 11134510256832400
853 11225887028208141
854 11317905810324400
855 11410570357721106
856 11503884442482575
857 11597851854299854
858 11692476400531641
859 11787761906266347
860 11883712214383585
861 11980331185616808
862 12077622698614512
863 12175590650003448
864 12274238954450400
865 12373571544725113
866 12473592371762644
867 12574305404726870
868 12675714631072551
869 12777824056609416
870 12880637705564805
871 12984159620647469
872 13088393863110789
873 13193344512817160
874 13299015668300920
875 13405411446833316
876 13512535984486016
877 13620393436195787
878 13728987975828588
879 13838323796244836
880 13948405109363207
881 14059236146226488
882 14170821157065965
883 14283164411366985
884 14396270197933929
885 14510142824956366
886 14624786620073732
887 14740205930442074
888 14856405122799320
889 14973388583531731
890 15091160718739760
891 15209725954305100
892 15329088735956247
893 15449253529336142
894 15570224820068329
895 15692007113824303
896 15814604936390261
897 15938022833735050
898 16062265372076620
899 16187337137950570
900 16313242738277200
901 16439986800429761
902 16567573972302104
903 16696008922377534
904 16825296339796159
905 16955440934424346
906 17086447436922673
907 17218320598815087
908 17351065192557457
909 17484686011607340
910 17619187870492232
911 17754575604879940
912 17890854071647440
913 18028028148950949
914 18166102736295388
915 18305082754605066
916 18444973146292839
917 18585778875331404
918 18727504927323069
919 18870156309570745
920 19013738051148325
921 19158255202972292
922 19303712837871792
923 19450116050660856
924 19597469958209088
925 19745779699513583
926 19895050435770228
927 20045287350446240
928 20196495649351159
929 20348680560710004
930 20501847335234885
931 20656001246197853
932 20811147589503129
933 20967291683760578
934 21124438870357628
935 21282594513533366
936 21441764000451080
937 21601952741272047
938 21763166169228696
939 21925409740699024
940 22088688935279447
941 22253009255859842
942 22418376228697025
943 22584795403489483
944 22752272353451477
945 22920812675388406
946 23090421989770596
947 23261105940809294
948 23432870196531088
949 23605720448853589
950 23779662413660480
951 23954701830877834
952 24130844464548847
953 24308096102910790
954 24486462558470377
955 24665949668080403
956 24846563293015745
957 25028309319050640
958 25211193656534368
959 25395222240469168
960 25580401030586560
961 25766736011424945
962 25954233192406564
963 26142898607915742
964 26332738317375527
965 26523758405326576
966 26715964981504437
967 26909364180918117
968 27103962163928005
969 27299765116325088
970 27496779249408552
971 27695010800065644
972 27894466030849920
973 28095151230060787
974 28297072711822396
975 28500236816163836
976 28704649909097703
977 28910318382700944
978 29117248655194077
979 29325447171021713
980 29534920400932425
981 29745674842059926
982 29957717018002612
983 30171053478905394
984 30385690801539896
985 30601635589385963
986 30818894472712512
987 31037474108659700
988 31257381181319447
989 31478622401818262
990 31701204508398425
991 31925134266500487
992 32150418468845109
993 32377063935516226
994 32605077514042556
995 32834466079481426
996 33065236534500944
997 33297395809463497
998 33530950862508584
999 33765908679636982
1000 34002276274793247