1 1
2 2
3 5
4 10
5 20
6 36
7 63
8 104
9 169
10 264
11 405
12 604
13 888
14 1278
15 1815
16 2536
17 3502
18 4772
19 6437
20 8586
21 11352
22 14866
23 19315
24 24890
25 31851
26 40466
27 51089
28 64092
29 79952
30 99172
31 122386
32 150264
33 183639
34 223394
35 270605
36 326422
37 392225
38 469490
39 559970
40 665542
41 788412
42 930942
43 1095885
44 1286190
45 1505265
46 1756762
47 2044865
48 2374064
49 2749469
50 3176554
51 3661517
52 4210994
53 4832457
54 5533902
55 6324284
56 7213182
57 8211274
58 9329974
59 10581949
60 11980730
61 13541278
62 15279552
63 17213140
64 19360790
65 21743087
66 24381958
67 27301400
68 30526954
69 34086494
70 38009654
71 42328687
72 47077854
73 52294352
74 58017652
75 64290504
76 71158238
77 78669831
78 86877174
79 95836214
80 105606170
81 116250769
82 127837400
83 140438444
84 154130384
85 168995216
86 185119508
87 202595909
88 221522162
89 242002702
90 264147614
91 288074343
92 313906586
93 341776124
94 371821644
95 404190680
96 439038394
97 476529620
98 516837584
99 560146079
100 606648116
101 656548229
102 710061056
103 767413787
104 828844672
105 894605609
106 964960584
107 1040188394
108 1120581038
109 1206446578
110 1298107444
111 1395903474
112 1500190134
113 1611341722
114 1729749512
115 1855825121
116 1989998584
117 2132721891
118 2284466984
119 2445729469
120 2617026540
121 2798900880
122 2991918482
123 3196672769
124 3413782324
125 3643895196
126 3887686560
127 4145863219
128 4419161186
129 4708350401
130 5014232208
131 5337644304
132 5679458128
133 6040584041
134 6421968606
135 6824600014
136 7249505280
137 7697755891
138 8170464924
139 8668792939
140 9193944992
141 9747176806
142 10329791662
143 10943146849
144 11588650464
145 12267768121
146 12982019650
147 13732986094
148 14522306316
149 15351684271
150 16222885508
151 17137744755
152 18098162300
153 19106111906
154 20163637066
155 21272859229
156 22435973976
157 23655259549
158 24933072918
159 26271858658
160 27674144896
161 29142552536
162 30679791086
163 32288668252
164 33972085642
165 35733048726
166 37574662426
167 39500141436
168 41512805728
169 43616091238
170 45813545234
171 48108837431
172 50505755224
173 53008215211
174 55620258306
175 58346061670
176 61189933716
177 64156326460
178 67249830406
179 70475187326
180 73837285034
181 77341170617
182 80992045056
183 84795276953
184 88756397018
185 92881112246
186 97175300302
187 101645024164
188 106296526396
189 111136244286
190 116170803970
191 121407036091
192 126851969800
193 132512848936
194 138397125876
195 144512478259
196 150866802722
197 157468232136
198 164325129238
199 171446104413
200 178840009186
201 186515954598
202 194483304536
203 202751694706
204 211331025846
205 220231483270
206 229463529952
207 239037926683
208 248965725040
209 259258288140
210 269927283478
211 280984704332
212 292442862450
213 304314410131
214 316612332756
215 329349971521
216 342541015878
217 356199526911
218 370339929648
219 384977037143
220 400126042646
221 415802544393
222 432022537636
223 448802440171
224 466159084226
225 484109742725
226 502672121048
227 521864384025
228 541705147610
229 562213506615
230 583409026228
231 605311770573
232 627942294078
233 651321670835
234 675471485840
235 700413865155
236 726171467038
237 752767512925
238 780225778436
239 808570625191
240 837826991706
241 868020426074
242 899177076698
243 931323725898
244 964487780508
245 998697306351
246 1033981018744
247 1070368317864
248 1107889279150
249 1146574689600
250 1186456038024
251 1227565552308
252 1269936189554
253 1313601674313
254 1358596488578
255 1404955911018
256 1452716006874
257 1501913668155
258 1552586603452
259 1604773379142
260 1658513409076
261 1713846996855
262 1770815325366
263 1829460500136
264 1889825538776
265 1951954415382
266 2015892049874
267 2081684353500
268 2149378218090
269 2219021562645
270 2290663322488
271 2364353497009
272 2440143138690
273 2518084402040
274 2598230532490
275 2680635916490
276 2765356070360
277 2852447691540
278 2941968647350
279 3033978027475
280 3128536132620
281 3225704528235
282 3325546033070
283 3428124774180
284 3533506175380
285 3641757013530
286 3752945406910
287 3867140872780
288 3984414315730
289 4104838086530
290 4228485970370
291 4355433247110
292 4485756679420
293 4619534574400
294 4756846771650
295 4897774706265
296 5042401396860
297 5190811509965
298 5343091347990
299 5499328915040
300 5659613904840
301 5824037768011
302 5992693699892
303 6165676709355
304 6343083606560
305 6525013073240
306 6711565650446
307 6902843810333
308 7098951943884
309 7299996434249
310 7506085644394
311 7717329992040
312 7933841937284
313 8155736059143
314 8383129043108
315 8616139759335
316 8854889250196
317 9099500810072
318 9350099972922
319 9606814593737
320 9869774836076
321 10139113255262
322 10414964785856
323 10697466826605
324 10986759227930
325 11282984378591
326 11586287193176
327 11896815200554
328 12214718531392
329 12540150008377
330 12873265133742
331 13214222181346
332 13563182184184
333 13920309028369
334 14285769440624
335 14659733084135
336 15042372546132
337 15433863435605
338 15834384370920
339 16244117079500
340 16663246385462
341 17091960311272
342 17530450065412
343 17978910146060
344 18437538328790
345 18906535772280
346 19386107006072
347 19876460038305
348 20377806343604
349 20890360972859
350 21414342541144
351 21949973339677
352 22497479323784
353 23057090227007
354 23629039549152
355 24213564672554
356 24810906850242
357 25421311324394
358 26045027314604
359 26682308138554
360 27333411200410
361 27998598113763
362 28678134690082
363 29372291064020
364 30081341681970
365 30805565429657
366 31545245620868
367 32300670127370
368 33072131367804
369 33859926439994
370 34664357109944
371 35485729946597
372 36324356310994
373 37180552493492
374 38054639703042
375 38946944206919
376 39857797320198
377 40787535547946
378 41736500574924
379 42705039410314
380 43693504377590
381 44702253261879
382 45731649299970
383 46782061330324
384 47853863783314
385 48947436833846
386 50063166391818
387 51201444257439
388 52362668111942
389 53547241675582
390 54755574698584
391 55988083121928
392 57245189068506
393 58527321006749
394 59834913741994
395 61168408582920
396 62528253333254
397 63914902461010
398 65328817090474
399 66770465174369
400 68240321486106
401 69738867794889
402 71266592858246
403 72823992600137
404 74411570103772
405 76029835792729
406 77679307424094
407 79360510272589
408 81073977124118
409 82820248462933
410 84599872465474
411 86413405190734
412 88261410574414
413 90144460622452
414 92063135405542
415 94018023255841
416 96009720761894
417 98038832968561
418 100105973372334
419 102211764124519
420 104356836026980
421 106541828738640
422 108767390771572
423 111034179700934
424 113342862161464
425 115694114060761
426 118088620576270
427 120527076371959
428 123010185595786
429 125538662099851
430 128113229438278
431 130734621090914
432 133403580461698
433 136120861105921
434 138887226729036
435 141703451417544
436 144570319638340
437 147488626473171
438 150459177618554
439 153482789623894
440 156560289891912
441 159692516920541
442 162880320303832
443 166124560977649
444 169426111221164
445 172785854906311
446 176204687499860
447 179683516316734
448 183223260522706
449 186824851391561
450 190489232308398
451 194217359030765
452 198010199692540
453 201868735069106
454 205793958581816
455 209786876567174
456 213848508282036
457 217979886176794
458 222182055901248
459 226456076581938
460 230803020828676
461 235223975016046
462 239720039290616
463 244292327856682
464 248941968984172
465 253670105298646
466 258477893789936
467 263366506106406
468 268337128564428
469 273390962446938
470 278529224013624
471 283753144803966
472 289063971648164
473 294462966974626
474 299951408821696
475 305530591149610
476 311201823853076
477 316966433077750
478 322825761233656
479 328781167316226
480 334834026920604
481 340985732567327
482 347237693717426
483 353591337102883
484 360048106742598
485 366609464277526
486 373276888987612
487 380051878131669
488 386935946965276
489 393930629085491
490 401037476449640
491 408258059724951
492 415593968308320
493 423046810680886
494 430618214428726
495 438309826602449
496 446123313738932
497 454060362225876
498 462122678324628
499 470311988539803
500 478630039643126
501 487078599048258
502 495659454835626
503 504374416132481
504 513225313138846
505 522213997512765
506 531342342397362
507 540612242811403
508 550025615677520
509 559584400218070
510 569290557984508
511 579146073258692
512 589152953083380
513 599313227669061
514 609628950425586
515 620102198374491
516 630735072181938
517 641529696576531
518 652488220383498
519 663612816948168
520 674905684171386
521 686369044938678
522 698005147156926
523 709816264189311
524 721804694893266
525 733972764061215
526 746322822459858
527 758857247276715
528 771578442160860
529 784488837675315
530 797590891339098
531 810887088085683
532 824379940306398
533 838071988314915
534 851965800392070
535 866063973256410
536 880369132110498
537 894883931117580
538 909611053449366
539 924553211768871
540 939713148279726
541 955093635215284
542 970697474889368
543 986527500191798
544 1002586574640658
545 1018877592884141
546 1035403480754454
547 1052167195776054
548 1069171727221190
549 1086420096624640
550 1103915357840814
551 1121660597565093
552 1139658935392594
553 1157913524346138
554 1176427550936628
555 1195204235697738
556 1214246833248034
557 1233558632832325
558 1253142958385582
559 1273003169081072
560 1293142659396006
561 1313564859666615
562 1334273236155496
563 1355271291613666
564 1376562565349756
565 1398150633799002
566 1420039110594284
567 1442231647142195
568 1464731932695990
569 1487543694938720
570 1510670700058078
571 1534116753336769
572 1557885699229230
573 1581981421959330
574 1606407845598980
575 1631168934673130
576 1656268694240470
577 1681711170505730
578 1707500450902400
579 1733640664712525
580 1760135983151440
581 1786990619995095
582 1814208831666840
583 1841794917872385
584 1869753221688660
585 1898088130206435
586 1926804074621320
587 1955905530884060
588 1985397019793810
589 2015283107656160
590 2045568406378540
591 2076257574136220
592 2107355315469890
593 2138866381959600
594 2170795572324600
595 2203147733105255
596 2235927758765220
597 2269140592381405
598 2302791225748480
599 2336884700076955
600 2371426106100080
601 2406420584780146
602 2441873327417682
603 2477789576366155
604 2514174625143560
605 2551033819155410
606 2588372555808856
607 2626196285244053
608 2664510510450814
609 2703320788008479
610 2742632728205024
611 2782451995785550
612 2822784310073964
613 2863635445730123
614 2905011232874038
615 2946917557851780
616 2989360363362356
617 3032345649232317
618 3075879472545372
619 3119967948425837
620 3164617250170916
621 3209833610043172
622 3255623319405446
623 3301992729522395
624 3348948251698220
625 3396496358087231
626 3444643581834386
627 3493396517895044
628 3542761823178392
629 3592746217376377
630 3643356483110012
631 3694599466767681
632 3746482078654304
633 3799011293839124
634 3852194152307754
635 3906037759819415
636 3960549288062092
637 4015735975519235
638 4071605127627950
639 4128164117655380
640 4185420386859932
641 4243381445377382
642 4302054872385182
643 4361448316998410
644 4421569498437190
645 4482426206932520
646 4544026303896882
647 4606377722839970
648 4669488469542644
649 4733366622982624
650 4798020335511634
651 4863457833791337
652 4929687418973724
653 4996717467647257
654 5064556432020602
655 5133212840879024
656 5202695299771552
657 5273012491977714
658 5344173178698134
659 5416186200031684
660 5489060475169590
661 5562805003383123
662 5637428864221112
663 5712941218508375
664 5789351308546750
665 5866668459124152
666 5944902077719278
667 6024061655521390
668 6104156767638704
669 6185197074129044
670 6267192320211834
671 6350152337309757
672 6434087043264484
673 6519006443389382
674 6604920630688932
675 6691839786922609
676 6779774182828158
677 6868734179196586
678 6958730227099374
679 7049772868974739
680 7141872738858710
681 7235040563482864
682 7329287162509240
683 7424623449639604
684 7521060432854394
685 7618609215533476
686 7717280996699128
687 7817087072148469
688 7918038834700572
689 8020147775340562
690 8123425483470854
691 8227883648067138
692 8333534057933726
693 8440388602871549
694 8548459273937644
695 8657758164625135
696 8768297471127114
697 8880089493528625
698 8993146636074864
699 9107481408375409
700 9223106425676746
701 9340034410078799
702 9458278190811836
703 9577850705465437
704 9698765000269822
705 9821034231337299
706 9944671664948104
707 10069690678804359
708 10196104762320598
709 10323927517890313
710 10453172661181004
711 10583854022413619
712 10715985546662194
713 10849581295146157
714 10984655445534672
715 11121222293251861
716 11259296251785954
717 11398891854007531
718 11540023752483484
719 11682706720808369
720 11826955653923270
721 11972785569460400
722 12120211608066762
723 12269249034762224
724 12419913239268104
725 12572219737378601
726 12726184171294480
727 12881822311007974
728 13039150054641586
729 13198183429846626
730 13358938594147048
731 13521431836351774
732 13685679576903718
733 13851698369305951
734 14019504900475866
735 14189115992185324
736 14360548601420150
737 14533819821834201
738 14708946884114284
739 14885947157448324
740 15064838149895632
741 15245637509869401
742 15428363026512302
743 15613032631193374
744 15799664397889164
745 15988276544694976
746 16178887434211570
747 16371515575070974
748 16566179622328846
749 16762898379004851
750 16961690796480688
751 17162575976055275
752 17365573169348430
753 17570701779871006
754 17777981363434266
755 17987431629734944
756 18199072442770596
757 18412923822439614
758 18629005944962478
759 18847339144496993
760 19067943913565456
761 19290840904685181
762 19516050930801646
763 19743594966934462
764 19973494150616552
765 20205769783555616
766 20440443332079446
767 20677536428812926
768 20917070873129678
769 21159068632844688
770 21403551844672114
771 21650542815933876
772 21900064025023704
773 22152138123131666
774 22406787934714586
775 22664036459236575
776 22923906871645936
777 23186422524131815
778 23451606946607606
779 23719483848483826
780 23990077119158124
781 24263410829804537
782 24539509233869996
783 24818396768880213
784 25100098056942828
785 25384637906569806
786 25672041313187422
787 25962333460975299
788 26255539723383256
789 26551685664987171
790 26850797042012610
791 27152899804207686
792 27458020095373640
793 27766184255254761
794 28077418820075876
795 28391750524449489
796 28709206301920392
797 29029813286889966
798 29353598815168018
799 29680590425914443
800 30010815862198216
801 30344303072956668
802 30681080213561616
803 31021175647796331
804 31364617948429046
805 31711435899207585
806 32061658495440272
807 32415314946008448
808 32772434673954900
809 33133047318514275
810 33497182735709038
811 33864871000398052
812 34236142406880060
813 34611027470960591
814 34989556930563016
815 35371761747813761
816 35757673109661248
817 36147322429979451
818 36540741350194648
819 36937961741407618
820 37339015705028226
821 37743935574916338
822 38152753918024316
823 38565503536556826
824 38982217468621306
825 39402928990406730
826 39827671616842168
827 40256479103794555
828 40689385448735560
829 41126424892958465
830 41567631922253168
831 42013041269142543
832 42462687913565668
833 42916607085133645
834 43374834263821200
835 43837405182242040
836 44304355826348958
837 44775722437728860
838 45251541514311396
839 45731849812683776
840 46216684348808046
841 46706082400355869
842 47200081507434338
843 47698719474940998
844 48202034373298358
845 48710064540829031
846 49222848584499164
847 49740425382313844
848 50262834084069480
849 50790114113769680
850 51322305170386504
851 51859447230297003
852 52401580548053534
853 52948745658841038
854 53500983379256378
855 54058334809786533
856 54620841335597194
857 55188544629031820
858 55761486650409612
859 56339709650545652
860 56923256171558186
861 57512169049410125
862 58106491414725626
863 58706266695353046
864 59311538617191086
865 59922351206773172
866 60538748792103194
867 61160776005261565
868 61788477783250690
869 62421899370622720
870 63061086320334768
871 63706084496398654
872 64356940074745870
873 65013699545899495
874 65676409715848970
875 66345117708744170
876 67019870967780330
877 67700717257914320
878 68387704666759650
879 69080881607325275
880 69780296818920710
881 70485999369917455
882 71198038658664310
883 71916464416271615
884 72641326707536840
885 73372675933751715
886 74110562833638230
887 74855038486178715
888 75606154311562490
889 76363962074039015
890 77128513882875010
891 77899862195231080
892 78678059817129410
893 79463159906353850
894 80255215973428350
895 81054281884540595
896 81860411862531330
897 82673660489841695
898 83494082709513470
899 84321733828160245
900 85156669516978720
901 85998945814743906
902 86848619128831372
903 87705746238236780
904 88570384294609260
905 89442590825295155
906 90322423734382766
907 91209941305770473
908 92105202204222894
909 93008265478463609
910 93919190562242654
911 94838037277454060
912 95764865835214894
913 96699736839007703
914 97642711285771068
915 98593850569067150
916 99553216480184016
917 100520871211328237
918 101496877356739122
919 102481297915906612
920 103474196294697356
921 104475636308598207
922 105485682183854136
923 106504398560737435
924 107531850494697760
925 108568103459657021
926 109613223349171596
927 110667276479753184
928 111730329592043342
929 112802449854160327
930 113883704862885982
931 114974162647038891
932 116073891668673624
933 117182960826480404
934 118301439456996784
935 119429397338033820
936 120566904689900552
937 121714032178856740
938 122870850918350080
939 124037432472495860
940 125213848857326952
941 126400172544300492
942 127596476461560752
943 128802833997473060
944 130019319001899640
945 131246005789760860
946 132482969142324192
947 133730284310792860
948 134988027017608184
949 136256273460065764
950 137535100311631024
951 138824584725583372
952 140124804336345064
953 141435837263153332
954 142757762111402752
955 144090657976345444
956 145434604444447112
957 146789681597115484
958 148155970012070064
959 149533550767098964
960 150922505441442520
961 152322916119578733
962 153734865392620642
963 155158436362130705
964 156593712641532130
965 158040778359952072
966 159499718163647188
967 160970617219875835
968 162453561218337904
969 163948636375076269
970 165455929433930824
971 166975527670469417
972 168507518893456324
973 170051991448812772
974 171609034221099822
975 173178736637508699
976 174761188669358368
977 176356480836115626
978 177964704206907524
979 179585950404571489
980 181220311607182530
981 182867880552133724
982 184528750537678210
983 186203015427040159
984 187890769649971874
985 189592108206895231
986 191307126670473938
987 193035921189785749
988 194778588491910052
989 196535225886130892
990 198305931265539924
991 200090803111270598
992 201889940494116496
993 203703443078796899
994 205531411125590594
995 207373945494632825
996 209231147647564974
997 211103119651862965
998 212989964182502754
999 214891784526320574
1000 216808684583694286