0 1
1 1
2 5
3 23
4 101
5 377
6 1226
7 3507
8 9027
9 21224
10 46262
11 94512
12 182702
13 336666
14 595085
15 1014091
16 1673243
17 2682685
18 4192118
19 6401314
20 9572962
21 14047457
22 20260601
23 28763703
24 40247228
25 55567352
26 75776769
27 102158957
28 136267461
29 179969238
30 235493851
31 305487369
32 393073019
33 501917234
34 636303413
35 801211827
36 1002408254
37 1246539556
38 1541239073
39 1895239796
40 2318498512
41 2822328615
42 3419545106
43 4124619192
44 4953846357
45 5925525016
46 7060149981
47 8380617549
48 9912446804
49 11684013621
50 13726802362
51 16075671395
52 18769137845
53 21849677344
54 25364044610
55 29363610252
56 33904720067
57 39049071836
58 44864116337
59 51423477180
60 58807396651
61 67103201742
62 76405798053
63 86818185290
64 98452002555
65 111428096702
66 125877122462
67 141940167150
68 159769409189
69 179528802773
70 201394798462
71 225557091523
72 252219408380
73 281600322463
74 313934110409
75 349471639366
76 388481296949
77 431249954058
78 478083972710
79 529310248533
80 585277300712
81 646356398438
82 712942737309
83 785456654130
84 864344894222
85 950081919077
86 1043171269145
87 1144146968960
88 1253574990083
89 1372054758427
90 1500220722151
91 1638743966020
92 1788333889157
93 1949739931391
94 2123753365877
95 2311209142502
96 2512987800500
97 2730017434089
98 2963275730325
99 3213792062255
100 3482649657362
101 3770987823636
102 4080004254074
103 4410957391179
104 4765168873091
105 5144026042141
106 5548984538297
107 5981570957512
108 6443385598286
109 6936105275650
110 7461486226762
111 8021367086486
112 8617671958043
113 9252413556261
114 9927696449414
115 10645720376327
116 11408783665653
117 12219286733129
118 13079735684649
119 13992746000079
120 14961046326601
121 15987482355603
122 17075020812881
123 18226753535237
124 19445901664229
125 20735819929227
126 22100001051518
127 23542080240673
128 25065839815931
129 26675213922842
130 28374293378962
131 30167330617854
132 32058744766238
133 34053126822540
134 36155244972753
135 38370050010841
136 40702680900675
137 43158470445711
138 45742951104482
139 48461860917072
140 51321149581762
141 54326984645939
142 57485757851597
143 60804091598437
144 64288845566036
145 67947123457002
146 71786279903741
147 75813927499643
148 80037943998485
149 84466479641736
150 89107964658751
151 93971116898391
152 99064949638275
153 104398779529028
154 109982234720961
155 115825263129377
156 121938140887166
157 128331480939702
158 135016241831957
159 142003736641634
160 149305642109512
161 156934007919577
162 164901266181422
163 173220241066246
164 181904158650245
165 190966656915466
166 200421795963233
167 210284068388955
168 220568409874748
169 231290209947399
170 242465322959462
171 254110079239697
172 266241296472021
173 278876291247858
174 292032890852438
175 305729445228602
176 319984839180059
177 334818504756302
178 350250433882541
179 366301191175498
180 382991927009851
181 400344390774784
182 418380944386889
183 437124575997464
184 456598913961923
185 476828241007952
186 497837508671594
187 519652351936476
188 542299104146853
189 565804812128231
190 590197251587762
191 615504942726705
192 641757166138676
193 668983978924497
194 697216231098917
195 726485582218516
196 756824518307621
197 788266369010044
198 820845325045034
199 854596455893731
200 889555727796112
201 925760021983160
202 963247153225865
203 1002055888624224
204 1042225966719470
205 1083798116851127
206 1126814078843757
207 1171316622943406
208 1217349570090267
209 1264957812445965
210 1314187334263651
211 1365085233017682
212 1417699740882773
213 1472080246477745
214 1528277316965465
215 1586342720422452
216 1646329448571452
217 1708291739788795
218 1772285102481569
219 1838366338744733
220 1906593568394962
221 1977026253289638
222 2049725222029550
223 2124752694951993
224 2202172309514619
225 2282049145974991
226 2364449753467989
227 2449442176384278
228 2537095981153790
229 2627482283335668
230 2720673775120462
231 2816744753144228
232 2915771146722179
233 3017830546399735
234 3123002232930482
235 3231367206577077
236 3343008216846485
237 3458009792553755
238 3576458272327613
239 3698441835450237
240 3824050533146401
241 3953376320212485
242 4086513087102477
243 4223556692359571
244 4364604995512437
245 4509757890322877
246 4659117338505890
247 4812787403806959
248 4970874286559555
249 5133486358605740
250 5300734198704862
251 5472730628311276
252 5649590747848094
253 5831431973355934
254 6018374073645701
255 6210539207832391
256 6408051963380987
257 6611039394539457
258 6819631061291966
259 7033959068705310
260 7254158106803762
261 7480365490843301
262 7712721202122513
263 7951367929199091
264 8196451109651324
265 8448118972251452
266 8706522579692393
267 8971815871732649
268 9244155708903029
269 9523701916637914
270 9810617329976851
271 10105067838697093
272 10407222433025051
273 10717253249785142
274 11035335619136189
275 11361648111751727
276 11696372586596558
277 12039694239153768
278 12391801650256761
279 12752886835378352
280 13123145294533712
281 13502776062647019
282 13891981760540858
283 14290968646396020
284 14699946667843013
285 15119129514530716
286 15548734671335765
287 15988983472055881
288 16440101153753012
289 16902316911587257
290 17375863954309762
291 17860979560253279
292 18357905133990917
293 18866886263499492
294 19388172778000346
295 19922018806311752
296 20468682835888131
297 21028427772377888
298 21601520999877465
299 22188234441711096
300 22788844621916251
301 23403632727261906
302 24032884669982045
303 24676891151049158
304 25335947724172571
305 26010354860344002
306 26700418013117606
307 27406447684444522
308 28128759491251637
309 28867674232582169
310 29623517957490262
311 30396622033504767
312 31187323215856892
313 31995963717284451
314 32822891278609905
315 33668459239902466
316 34533026612423973
317 35416958151166350
318 36320624428182878
319 37244401906518609
320 38188673014944712
321 39153826223299562
322 40140256118643941
323 41148363482030638
324 42178555366098398
325 43231245173287977
326 44306852734892849
327 45405804390739772
328 46528533069714371
329 47675478370924383
330 48847086645718351
331 50043811080349824
332 51266111779507509
333 52514455850498819
334 53789317488309933
335 55091178061327202
336 56420526197945684
337 57777857873847021
338 59163676500175133
339 60578493012389291
340 62022825960025762
341 63497201597144920
342 65002153973697746
343 66538225027585927
344 68105964677652227
345 69705930917372641
346 71338689909489761
347 73004816081356164
348 74704892221230014
349 76439509575288966
350 78209267945607362
351 80014775788860050
352 81856650316000635
353 83735517592674729
354 85652012640618830
355 87606779539802627
356 89600471531568197
357 91633751122521101
358 93707290189429697
359 95821770084884875
360 97977881743979401
361 100176325791756247
362 102417812651687993
363 104703062654933825
364 107032806150639125
365 109407783617021327
366 111828745773509942
367 114296453693681565
368 116811678919260699
369 119375203574924318
370 121987820484183962
371 124650333286080378
372 127363556552967470
373 130128315909117648
374 132945448150428329
375 135815801364958741
376 138740235054579779
377 141719620257463123
378 144754839671695370
379 147846787779740428
380 150996370974038962
381 154204507683465143
382 157472128500932549
383 160800176311866465
384 164189606423837492
385 167641386697070702
386 171156497676128325
387 174735932722477175
388 178380698148241893
389 182091813350852172
390 185870310948888151
391 189717236918829075
392 193633650733012547
393 197620625498506376
394 201679248097203497
395 205810619326838877
396 210015854043242030
397 214296081303520954
398 218652444510494285
399 223086101558064350
400 227598224977851112
401 232190002086776541
402 236862635135922614
403 241617341460349314
404 246455353630199061
405 251377919602770766
406 256386302875893177
407 261481782642277527
408 266665653945182396
409 271939227835067595
410 277303831527573262
411 282760808562497741
412 288311518964113733
413 293957339402493046
414 299699663356182734
415 305539901275899702
416 311479480749589883
417 317519846668515794
418 323662461394721909
419 329908804929538374
420 336260375083475851
421 342718687647168708
422 349285276563722721
423 355961694102121172
424 362749511032048899
425 369650316799784852
426 376665719705526098
427 383797347081790488
428 391046845473264341
429 398415880817738987
430 405906138628505962
431 413519324177851309
432 421257162682022228
433 429121399487303125
434 437113800257577773
435 445236151163011216
436 453490259070231605
437 461877951733642176
438 470401077988247042
439 479061507943617567
440 487861133179386512
441 496801866941893244
442 505885644342370737
443 515114422556294172
444 524490181024285406
445 534014921654189627
446 543690669024722021
447 553519470590297258
448 563503396887443195
449 573644541742408081
450 583945022480366251
451 594406980135828046
452 605032579664662565
453 615824010157335413
454 626783485053773681
455 637913242359456752
456 649215544863148796
457 660692680355867967
458 672346961851511817
459 684180727808730329
460 696196342354469762
461 708396195508775082
462 720782703411277862
463 733358308548953781
464 746125479985580315
465 759086713592475091
466 772244532280949213
467 785601486236052370
468 799160153152047758
469 812923138469189944
470 826893075612247462
471 841072626230339552
472 855464480438532611
473 870071357060762043
474 884896003874528858
475 899941197856932977
476 915209745432496389
477 930704482722334367
478 946428275795131701
479 962384020919478393
480 978574644818025601
481 995003104923012489
482 1011672389633628629
483 1028585518574758799
484 1045745542857578693
485 1063155545341544577
486 1080818640898249274
487 1098737976676683691
488 1116916732370380163
489 1135358120485972976
490 1154065386613656262
491 1173041809699070760
492 1192290702317103566
493 1211815410947128482
494 1231619316250175037
495 1251705833347549891
496 1272078412101402651
497 1292740537396755909
498 1313695729425495494
499 1334947543971836826
500 1356499572699767362
501 1378355443441977065
502 1400518820490780905
503 1422993404890541359
504 1445782934732098940
505 1468891185448714752
506 1492321970114037137
507 1516079139741592421
508 1540166583586315877
509 1564588229447618910
510 1589348043974512651
511 1614450032972279937
512 1639898241711219963
513 1665696755236953530
514 1691849698682817285
515 1718361237583830827
516 1745235578192769182
517 1772476967797820460
518 1800089695042365329
519 1828078090246354028
520 1856446525729821712
521 1885199416138013743
522 1914341218768665890
523 1943876433900906928
524 1973809605126332789
525 2004145319681715616
526 2034888208783901069
527 2066042947966353093
528 2097614257417903700
529 2129606902323162813
530 2162025693205149962
531 2194875486269598683
532 2228161183751499669
533 2261887734263329320
534 2296060133145534002
535 2330683422818712452
536 2365762693138070915
537 2401303081749589220
538 2437309774448476673
539 2473788005539351732
540 2510743058198728651
541 2548180264839240790
542 2586105007476188117
543 2624522718095834306
544 2663438879026045307
545 2702859023308690502
546 2742788735074402670
547 2783233649919113574
548 2824199455282965765
549 2865691890831013085
550 2907716748836314862
551 2950279874564831931
552 2993387166662733884
553 3037044577545521319
554 3081258113789576921
555 3126033836525544766
556 3171377861834156117
557 3217296361143896722
558 3263795561631138326
559 3310881746622125005
560 3358561255997441512
561 3406840486598349806
562 3455725892635625453
563 3505223986100275626
564 3555341337176774894
565 3606084574658196077
566 3657460386363876873
567 3709475519558995064
568 3762136781376697539
569 3815451039242151459
570 3869425221299167351
571 3924066316838757948
572 3979381376730287141
573 4035377513854568327
574 4092061903539571109
575 4149441783998091102
576 4207524456768046388
577 4266317287154750833
578 4325827704675832421
579 4386063203508142247
580 4447031342937326962
581 4508739747809405724
582 4571196108985029098
583 4634408183795756355
584 4698383796503033283
585 4763130838759202341
586 4828657270071231945
587 4894971118266492096
588 4962080479961267822
589 5029993521031333002
590 5098718477085280762
591 5168263653939928334
592 5238637428098497307
593 5309848247230882477
594 5381904630656714966
595 5454815169830528127
596 5528588528829736661
597 5603233444844732753
598 5678758728671814425
599 5755173265208245191
600 5832486013950165001
601 5910706009492646811
602 5989842362032623585
603 6069904257873975293
604 6150900959935505541
605 6232841808261092627
606 6315736220532749486
607 6399593692585872537
608 6484423798927418747
609 6570236193256286114
610 6657040608986641762
611 6744846859773468022
612 6833664840041075582
613 6923504525513849236
614 7014375973749980225
615 7106289324677445841
616 7199254801132995203
617 7293282709403397015
618 7388383439769713138
619 7484567467053848904
620 7581845351168148962
621 7680227737667284667
622 7779725358303206781
623 7880349031582404573
624 7982109663326250068
625 8085018247233663602
626 8189085865446884429
627 8294323689119577587
628 8400742978988065781
629 8508355085944912528
630 8617171451615650351
631 8727203608937875279
632 8838463182743506499
633 8950961890343427404
634 9064711542115311953
635 9179724042093847577
636 9296011388564163614
637 9413585674657671486
638 9532459088951130693
639 9652643916068141786
640 9774152537283885512
641 9896997431132304225
642 10021191174016549886
643 10146746440821889662
644 10273676005531898597
645 10401992741847125266
646 10531709623807065041
647 10662839726414621779
648 10795396226263897724
649 10929392402170487311
650 11064841635805119862
651 11201757412329821705
652 11340153321037447925
653 11480043055993749114
654 11621440416682828550
655 11764359308655150002
656 11908813744178956827
657 12054817842894257366
658 12202385832470242557
659 12351532049265285570
660 12502270938990394651
661 12654617057375263752
662 12808585070837797433
663 12964189757156249360
664 13121446006144856195
665 13280368820332100952
666 13440973315642492922
667 13603274722080992980
668 13767288384420976709
669 13933029762894858863
670 14100514433888276962
671 14269758090636952233
672 14440776543927131060
673 14613585722798719833
674 14788201675252021749
675 14964640568957183116
676 15142918691967263109
677 15323052453434029188
678 15505058384327397530
679 15688953138157615323
680 15874753491701109712
681 16062476345729094848
682 16252138725739867289
683 16443757782693875800
684 16637350793752501262
685 16832935163019627327
686 17030528422286943005
687 17230148231782052390
688 17431812380920338203
689 17635538789059648917
690 17841345506258761651
691 18049250714038685130
692 18259272726147760437
693 18471429989329618361
694 18685741084094956617
695 18902224725496190252
696 19120899763905944060
697 19341785185798434819
698 19564900114534717745
699 19790263811150839445
700 20017895675149877362
701 20247815245296902446
702 20480042200417850654
703 20714596360201334449
704 20951497686004385531
705 21190766281661154391
706 21432422394295563557
707 21676486415136934542
708 21922978880339591006
709 22171920471805452540
710 22423332018010627262
711 22677234494835011996
712 22933649026395913923
713 23192596885884696831
714 23454099496407471554
715 23718178431828828077
716 23984855417619634613
717 24254152331707895459
718 24526091205333698669
719 24800694223907239669
720 25077983727870957601
721 25357982213564764813
722 25640712334095412061
723 25926196900208964107
724 26214458881167434069
725 26505521405628545477
726 26799407762529676178
727 27096141401974947303
728 27395745936126517251
729 27698245140099038132
730 28003662952858340462
731 28312023478123297764
732 28623350985271942718
733 28937669910250780710
734 29255004856488378293
735 29575380595812166591
736 29898822069369543035
737 30225354388552205641
738 30555002835924809102
739 30887792866156871062
740 31223750106959023762
741 31562900360022533549
742 31905269601963189377
743 32250883985268476907
744 32599769839249145276
745 32951953670994077252
746 33307462166329575801
747 33666322190781971873
748 34028560790544672405
749 34394205193448547426
750 34763282809936781251
751 35135821234043080701
752 35511848244374371355
753 35891391805096868798
754 36274480066926661901
755 36661141368123689127
756 37051404235490250926
757 37445297385372933232
758 37842849724669091177
759 38244090351836762024
760 38649048557909162512
761 39057753827512633587
762 39470235839889193802
763 39886524469922558316
764 40306649789168790885
765 40730642066890439716
766 41158531771095330693
767 41590349569578862785
768 42026126330970985268
769 42465893125786695489
770 42909681227481242962
771 43357522113508872407
772 43809447466386297701
773 44265489174759733228
774 44725679334476680778
775 45190050249661292352
776 45658634433794513219
777 46131464610797819432
778 46608573716121760361
779 47089994897838114288
780 47575761517736873851
781 48065907152426863194
782 48560465594441209869
783 49059470853346467134
784 49562957156856615963
785 50070958951950736202
786 50583510905995582454
787 51100647907871847906
788 51622405069105357973
789 52148817725001970721
790 52679921435787432262
791 53215751987750957815
792 53756345394393792956
793 54301737897581519467
794 54851965968701366657
795 55407066309823286266
796 55967075854866058181
797 56532031770767178774
798 57101971458657805454
799 57676932555041502921
800 58256952932978071112
801 58842070703271193970
802 59432324215661195445
803 60027752060021635494
804 60628393067561038910
805 61234286312028483377
806 61845471110924346017
807 62461987026714928436
808 63083873868052265987
809 63711171690997834855
810 64343920800251469151
811 64982161750384195192
812 65625935347076301653
813 66275282648359346315
814 66930244965863424605
815 67590863866068394202
816 68257181171560387412
817 68929238962292299125
818 69607079576849588589
819 70290745613720076323
820 70980279932569080962
821 71675725655518570848
822 72377126168431681730
823 73084525122201268863
824 73797966434043851459
825 74517494288797611241
826 75243153140225809649
827 75974987712324278908
828 76713043000634358110
829 77457364273559922958
830 78207997073689886962
831 78964987219124816138
832 79728380804809041659
833 80498224203866905905
834 81274564068944533022
835 82057447333555752827
836 82846921213433575845
837 83643033207885841685
838 84445831101156445233
839 85255362963790756227
840 86071677154006643401
841 86894822319069712095
842 87724847396674173257
843 88561801616327946041
844 89405734500743418677
845 90256695867232463127
846 91114735829107134950
847 91979904797084647189
848 92852253480698056475
849 93731832889711243430
850 94618694335539632362
851 95512889432675225586
852 96414470100117404174
853 97323488562808063704
854 98239997353072543641
855 99164049312064912141
856 100095697591219071747
857 101034995653704240987
858 101981997275886284186
859 102936756548793437700
860 103899327879587911762
861 104869765993041909311
862 105848125933019547893
863 106834463063963219161
864 107828833072385878964
865 108831291968367795702
866 109841896087059256853
867 110860702090187754479
868 111887766967571156549
869 112923148038635378004
870 113966902953938065351
871 115019089696696801803
872 116079766584323353731
873 117148992269962458512
874 118226825744036681529
875 119313326335795835477
876 120408553714872496718
877 121512567892842104898
878 122625429224789187581
879 123747198410878189142
880 124877936497930452712
881 126017704881005827429
882 127166565304990456838
883 128324579866189213690
884 129491811013924344053
885 130668321552138778966
886 131854174641005683625
887 133049433798542695311
888 134254162902232427132
889 135468426190647681747
890 136692288265082959262
891 137925814091190696389
892 139169069000623828197
893 140422118692683102462
894 141685029235970745086
895 142957867070048899502
896 144240699007104445691
897 145533592233618614618
898 146836614312043010885
899 148149833182480452286
900 149473317164372246251
901 150807134958190304716
902 152151355647135724625
903 153506048698842228428
904 154871283967086099011
905 156247131693500996252
906 157633662509299296866
907 159030947436998337552
908 160439057892153210357
909 161858065685094483059
910 163288043022672500762
911 164729062510006634277
912 166181197152241138772
913 167644520356305981021
914 169119105932684306045
915 170605028097184894216
916 172102361472721286933
917 173611181091095924680
918 175131562394790982898
919 176663581238764242199
920 178207313892251685712
921 179762837040575152772
922 181330227786956749121
923 182909563654338335508
924 184500922587207802238
925 186104382953430444227
926 187720023546087151509
927 189347923585317722402
928 190988162720171021691
929 192640821030460283673
930 194305979028625289851
931 195983717661599713734
932 197674118312685369989
933 199377262803431652989
934 201093233395521909473
935 202822112792665022952
936 204563984142493962044
937 206318931038469562951
938 208087037521791305753
939 209868388083313347281
940 211663067665467577762
941 213471161664191956530
942 215292755930865901526
943 217127936774250980397
944 218976790962438685467
945 220839405724803532891
946 222715868753963275821
947 224606268207744464394
948 226510692711155149934
949 228429231358362958656
950 230361973714680339862
951 232309009818555206360
952 234270430183568779715
953 236246325800438850499
954 238236788139030273770
955 240241909150370902377
956 242261781268674785957
957 244296497413370830631
958 246346150991138754917
959 248410835897950529265
960 250490646521119142401
961 252585677741352874257
962 254696024934816926373
963 256821783975200581895
964 258963051235791753765
965 261119923591557085577
966 263292498421229471402
967 265480873609401151395
968 267685147548624257219
969 269905419141516956408
970 272141787802877077462
971 274394353461801357088
972 276663216563812199150
973 278948478072990079018
974 281250239474113490669
975 283568602774804562491
976 285903670507682246939
977 288255545732521202253
978 290624332038418279190
979 293010133545964723218
980 295413054909426012962
981 297833201318927437553
982 300270678502647341529
983 302725592729016132135
984 305198050808922985532
985 307688160097928338952
986 310196028498484113185
987 312721764462159744605
988 315265476991875979013
989 317827275644144498662
990 320407270531315342651
991 323005572323830184185
992 325622292252483432827
993 328257542110689217346
994 330911434256756225237
995 333584081616168446627
996 336275597683873806590
997 338986096526578725684
998 341715692785050600705
999 344464501676426237540
1000 347232638996528236112