0 1
1 1
2 2
3 3
4 5
5 7
6 10
7 14
8 20
9 27
10 37
11 49
12 66
13 86
14 113
15 146
16 189
17 241
18 308
19 389
20 492
21 615
22 770
23 956
24 1187
25 1463
26 1802
27 2207
28 2701
29 3288
30 3999
31 4842
32 5857
33 7056
34 8491
35 10183
36 12197
37 14564
38 17369
39 20658
40 24539
41 29075
42 34408
43 40627
44 47912
45 56385
46 66277
47 77757
48 91119
49 106588
50 124542
51 145282
52 169290
53 196963
54 228915
55 265672
56 308011
57 356619
58 412484
59 476501
60 549919
61 633893
62 730005
63 839746
64 965107
65 1107999
66 1270929
67 1456344
68 1667390
69 1907178
70 2179656
71 2488772
72 2839466
73 3236726
74 3686724
75 4195752
76 4771499
77 5421872
78 6156442
79 6985121
80 7919795
81 8972847
82 10159021
83 11493760
84 12995307
85 14682866
86 16578979
87 18707484
88 21096180
89 23774574
90 26776903
91 30139625
92 33904826
93 38117451
94 42829156
95 48095253
96 53979031
97 60548418
98 67880851
99 76059604
100 85179268
101 95341734
102 106662387
103 119265700
104 133292194
105 148893660
106 166240998
107 185519029
108 206935292
109 230714445
110 257108188
111 286389201
112 318862310
113 354857972
114 394744866
115 438922909
116 487837403
117 541971621
118 601862742
119 668093976
120 741312498
121 822221150
122 911598683
123 1010291026
124 1119234082
125 1239444671
126 1372046240
127 1518259519
128 1679431479
129 1857025821
130 2052655682
131 2268074020
132 2505210527
133 2766162101
134 3053234561
135 3368933388
136 3716010811
137 4097457120
138 4516553901
139 4976866162
140 5482302523
141 6037108560
142 6645934967
143 7313832519
144 8046329211
145 8849427482
146 9729691608
147 10694247810
148 11750883242
149 12908049832
150 14174976574
151 15561677980
152 17079081462
153 18739041597
154 20554484761
155 22539430533
156 24709155888
157 27080225438
158 29670678000
159 32500067490
160 35589674965
161 38962562461
162 42643814204
163 46660605941
164 51042479322
165 55821429939
166 61032219638
167 66712486822
168 72903101961
169 79648304454
170 86996107624
171 94998466955
172 103711741507
173 113196899367
174 123520043592
175 134752661518
176 146972224256
177 160262487756
178 174714176448
179 190425344945
180 207502157738
181 226059322069
182 246220977507
183 268121211960
184 291905076610
185 317729199224
186 345762942390
187 376189130179
188 409205369913
189 445024910916
190 483878153269
191 526013659964
192 571699879068
193 621226334138
194 674905590205
195 733074650832
196 796097202255
197 864365249979
198 938301680612
199 1018362175400
200 1105038134540
201 1198858910907
202 1300395148214
203 1410261384222
204 1529119860810
205 1657683553613
206 1796720520515
207 1947057422501
208 2109584485928
209 2285259589047
210 2475113924343
211 2680256735460
212 2901881777292
213 3141272800620
214 3399810921427
215 3678980964068
216 3980379866071
217 4305724006718
218 4656858791386
219 5035767109737
220 5444580262878
221 5885587716026
222 6361249554406
223 6874207717815
224 7427300195727
225 8023573957815
226 8666301127717
227 9358993852568
228 10105422726585
229 10909633876566
230 11775969943583
231 12709089698772
232 13713991931997
233 14796037955774
234 15960978796887
235 17214980994425
236 18564657542340
237 20017097443062
238 21579900909170
239 23261213195480
240 25069764634651
241 27014909341474
242 29106670733696
243 31355785780985
244 33773756747022
245 36372901746036
246 39166413539460
247 42168417263320
248 45394037220931
249 48859462759146
250 52582024122246
251 56580267583030
252 60874041560481
253 65484582257648
254 70434611402202
255 75748433806047
256 81452048262449
257 87573258627359
258 94141799605316
259 101189463159079
260 108750241138057
261 116860469057397
262 125558987773681
263 134887306936794
264 144889788197790
265 155613830933872
266 167110079790564
267 179432635611838
268 192639290473188
269 206791767123888
270 221955985068176
271 238202332245990
272 255605966166812
273 274247122028655
274 294211453413754
275 315590381575133
276 338481480767428
277 362988874026869
278 389223668846195
279 417304405440900
280 447357549187765
281 479517998121171
282 513929639354007
283 550745923387680
284 590130492627268
285 632257831033266
286 677313973846867
287 725497242166899
288 777019044123163
289 832104705147357
290 890994372092403
291 953943951291162
292 1021226128526948
293 1093131428460732
294 1169969364936546
295 1252069637019436
296 1339783425882718
297 1433484744561171
298 1533571899643369
299 1640469013924676
300 1754627673334746
301 1876528644004886
302 2006683727331535
303 2145637695574444
304 2293970380714813
305 2452298855612814
306 2621279785404980
307 2801611884499571
308 2994038562701357
309 3199350691957719
310 3418389583249190
311 3652050101054440
312 3901284011339011
313 4167103486239239
314 4450584868279126
315 4752872612827751
316 5075183519023456
317 5418811163203290
318 5785130652986271
319 6175603611165164
320 6591783516057261
321 7035321302370582
322 7507971358357338
323 8011597817991199
324 8548181293732121
325 9119825943078188
326 9728767024976200
327 10377378833530962
328 11068183176369602
329 11803858279124295
330 12587248295507278
331 13421373298243759
332 14309439943357417
333 15254852676665481
334 16261225688966617
335 17332395482161061
336 18472434267822780
337 19685664053651772
338 20976671655488705
339 22350324483319572
340 23811787356337382
341 25366540188318944
342 27020396817082903
343 28779524811960868
344 30650466553171905
345 32640161409580035
346 34755969330381380
347 37005695669643232
348 39397617582561811
349 41940511804737116
350 44643684178445813
351 47517000729550119
352 50570920686086119
353 53816531234525724
354 57265584433918704
355 60930536076328644
356 64824586945212339
357 68961726252709128
358 73356777741395628
359 78025448224219770
360 82984379084753529
361 88251200504508566
362 93844588978933438
363 99784327882235325
364 106091371685270665
365 112787913580532015
366 119897457164504218
367 127444891925900327
368 135456573239781098
369 143960406611296770
370 152985936922797150
371 162564442424167485
372 172729034278243887
373 183514761398362968
374 194958721452738328
375 207100177771186128
376 219980683096879847
377 233644209918631043
378 248137288399950788
379 263509151642112172
380 279811889377130101
381 297100609831645707
382 315433610943903230
383 334872560680926829
384 355482687731557290
385 377332982331301823
386 400496408595951603
387 425050128131881925
388 451075736409811876
389 478659511685475657
390 507892678073080218
391 538871682574600884
392 571698487800001931
393 606480880205668716
394 643332795726355123
395 682374662657415670
396 723733763814844076
397 767544617865326816
398 813949382019119484
399 863098276020107016
400 915150029805403277
401 970272354818587700
402 1028642441544019274
403 1090447483304586637
404 1155885229102376129
405 1225164565612478961
406 1298506131339939794
407 1376142963128692092
408 1458321178283179392
409 1545300692582210826
410 1637355977718450163
411 1734776858547293098
412 1837869353975261875
413 1946956561990998330
414 2062379592991924695
415 2184498552045854601
416 2313693574592190830
417 2450365916377044264
418 2594939102509717778
419 2747860136610935851
420 2909600775357204214
421 3080658869591127881
422 3261559777756271809
423 3452857853051864700
424 3655138010560841124
425 3869017376000958000
426 4095147022891838751
427 4334213800074278700
428 4586942256962599163
429 4854096668788711530
430 5136483169859666004
431 5434951997449293729
432 5750399855044691012
433 6083772397974058699
434 6436066850898956184
435 6808334760652078554
436 7201684894735155583
437 7617286289466626702
438 8056371459000861766
439 8520239769776815560
440 9010260992607737367
441 9527879037604109742
442 10074615885221627413
443 10652075719333685558
444 11261949276799131876
445 11906018420212761782
446 12586160949596159729
447 13304355660593507440
448 14062687666334775459
449 14863353991506494272
450 15708669457326247899
451 16601072867045260445
452 17543133512349874755
453 18537558011490297783
454 19587197501336074622
455 20695055195522777044
456 21864294332886384523
457 23098246529831599703
458 24400420563011574942
459 25774511597607485511
460 27224410889967548203
461 28754215981712848416
462 30368241416671487571
463 32071029999761894818
464 33867364632028973089
465 35762280743181572568
466 37761079358939649066
467 39869340827002853673
468 42092939242340544613
469 44438057598337391253
470 46911203708199750917
471 49519226926164337752
472 52269335716962241067
473 55169116106400391523
474 58226551065935840230
475 61450040867769692766
476 64848424468167539730
477 68431001959576091097
478 72207558154521372241
479 76188387346316275257
480 80384319315329809596
481 84806746630759851674
482 89467653322962348712
483 94379644981693174388
484 99555980362199198599
485 105010604560478317867
486 110758183847165424944
487 116814142227930021226
488 123194699828058506296
489 129916913176333558386
490 136998717494859463604
491 144458971077896990069
492 152317501876162322622
493 160595156378399091004
494 169313850917389862202
495 178496625501832020923
496 188167700312945870238
497 198352534977809611443
498 209077890771071018433
499 220371895868645073574
500 232264113819009162323
501 244785615368464145988
502 257969053821222676188
503 271848744084705253792
504 286460745597561232809
505 301842949306179421443
506 318035168905396062396
507 335079236526050626584
508 353019103104962952896
509 371900943638511281136
510 391773267577078632632
511 412687034581874111654
512 434695775925085581721
513 457855721777164100751
514 482225934688062467113
515 507868449530673044380
516 534848420241528303207
517 563234273653806118612
518 593097870788535532687
519 624514675928413267020
520 657563933873785653099
521 692328855737385236367
522 728896813714118839340
523 767359545217746974129
524 807813366860856206087
525 850359398708571365379
526 895103799326181111564
527 942158012093397417073
528 991639023353193161951
529 1043669632914217157850
530 1098378737526861391181
531 1155901627902632381428
532 1216380299953785350923
533 1279963780878301560414
534 1346808470829232933512
535 1417078500854136640348
536 1490946107911337072556
537 1568592027715071413340
538 1650205906290124988400
539 1735986731060557218965
540 1826143282433701208405
541 1920894606783359918624
542 2020470511881268238872
543 2125112085767460300066
544 2235072240204461599438
545 2350616279800727731399
546 2472022498052775641572
547 2599582801495008936061
548 2733603363320660572911
549 2874405307776027741180
550 3022325426815693649588
551 3177716930444544358014
552 3340950232369757847537
553 3512413772523610126070
554 3692514878227966418830
555 3881680665708768529630
556 4080358983892370447106
557 4289019402353046051098
558 4508154245518977645643
559 4738279675181823246223
560 4979936823608383253640
561 5233692979491321474363
562 5500142829245822522432
563 5779909756098517825120
564 6073647199702588987161
565 6382040078953841469881
566 6705806280988996775877
567 7045698219290239851504
568 7402504464146712709783
569 7777051448668865748960
570 8170205253899849662413
571 8582873476516373834594
572 9016007182982869475356
573 9470602953974720994234
574 9947705023282519646972
575 10448407515365636565908
576 10973856786146140928474
577 11525253871595668684219
578 12103857049119005736935
579 12710984516705875564707
580 13348017195304043857334
581 14016401659841734830731
582 14717653204841628043572
583 15453359050551861351592
584 16225181696068744426981
585 17034862425918556993659
586 17884224977152620411109
587 18775179374013382612098
588 19709725937856330149925
589 20689959480028485516222
590 21718073686074511544352
591 22796365699671449298052
592 23927240915409723896376
593 25113217989583954746531
594 26356934078923454402454
595 27661150317256122609893
596 29028757540919185144273
597 30462782273814195105951
598 31966392983880788476862
599 33542906622870245651528
600 35195795462238554568781
601 36928694238110509582345
602 38745407619271158654617
603 40649918012300977501439
604 42646393719046979433227
605 44739197461813497756615
606 46932895292808555993891
607 49232265904608276860172
608 51642310359636014321579
609 54168262256918320232442
610 56815598355702293925275
611 59590049675827433939730
612 62497613096162377305896
613 65544563472773279007908
614 68737466300009819961513
615 72083190938104083859302
616 75588924432506444154023
617 79262185950650301336848
618 83110841863584371285680
619 87143121500443447972267
620 91367633605602325501913
621 95793383528960946641937
622 100429791181819146278910
623 105286709791481143681936
624 110374445489887169886114
625 115703777772337708655114
626 121285980864691196293868
627 127132846038279044285530
628 133256704914267429839481
629 139670453800162642177137
630 146387579103825592849616
631 153422183871443006490304
632 160789015498768913964383
633 168503494666157700346299
634 176581745550988496891272
635 185040627372426209242950
636 193897767326771776288326
637 203171594973150857237853
638 212881378132843827467112
639 223047260367222062343645
640 233690300103074550618259
641 244832511475952134762140
642 256496906966261607420321
643 268707541904883340015474
644 281489560929499020871786
645 294869246475074239331892
646 308874069386685359361684
647 323532741745375129936424
648 338875272002823702389253
649 354933022523375451249524
650 371738769637449464748536
651 389326766313397788200580
652 407732807560778131814960
653 426994298681352277360946
654 447150326490471468711102
655 468241733635190931378785
656 490311196142287940477536
657 513403304333405484319965
658 537564647251895606815933
659 562843900750383934233111
660 589291919395989180315060
661 616961832355014477405854
662 645909143427443596819086
663 676191835406932683250224
664 707870478951155380576184
665 741008346153233461275470
666 775671529014854174544525
667 811929063028112158968425
668 849853056083739527630724
669 889518822930436329693651
670 931005025421455130169002
671 974393818792307740172736
672 1019771004225783206341144
673 1067226187968904379399519
674 1116852947279719769002374
675 1168749003491052611809548
676 1223016402492620952167611
677 1279761702943023105463200
678 1339096172538477230091651
679 1401135992676213676233912
680 1466002471867001897580871
681 1533822268263313182425670
682 1604727621687485388564054
683 1678856595557371650333512
684 1756353329126202111463224
685 1837368300467693781732313
686 1922058600658181072255177
687 2010588219623137550701845
688 2103128344137803981928732
689 2199857668488637683395775
690 2300962718326375652725054
691 2406638188260024921707437
692 2517087293767039612852310
693 2632522138015114999763037
694 2753164094218989796049725
695 2879244204177607860668136
696 3011003593667124084925767
697 3148693905389138987283086
698 3292577750206022856734682
699 3442929177421192753921984
700 3600034164897208103874897
701 3764191129832831920082552
702 3935711461057930924580128
703 4114920073735838367377452
704 4302155987403466491721344
705 4497772928312881150273047
706 4702139957081880875903702
707 4915642122697445681233181
708 5138681143963164958435222
709 5371676119521214536484800
710 5615064267630378279440577
711 5869301696924467632492132
712 6134864209430386785367177
713 6412248137171626940364678
714 6701971213742146455732969
715 7004573482286110171410648
716 7320618241382747714702135
717 7650693030390414987147480
718 7995410655872702873019516
719 8355410260788922746471002
720 8731358438205419636513503
721 9123950391348691997950269
722 9533911141901197953547035
723 9961996788510710280283626
724 10408995817570213566368392
725 10875730468401218165448568
726 11363058155066212458724798
727 11871872947118234648707700
728 12403107111695630984176655
729 12957732719459223244593030
730 13536763316976996280542402
731 14141255668258027176417496
732 14772311568253674897542400
733 15431079731248717608137054
734 16118757757190485362075966
735 16836594179117411954471346
736 17585890594983557784126932
737 18368003887298440789429614
738 19184348534147166733003964
739 20036399015288800911752374
740 20925692317187920750894297
741 21853830540978220929498882
742 22822483617526263110812310
743 23833392133919255621097070
744 24888370275883139401873788
745 25989308890805859404148671
746 27138178676237282411806861
747 28337033498919657259417614
748 29588013849614384642432769
749 30893350439188233128928099
750 32255367941650481431612599
751 33676488890045958973493290
752 35159237731355045856433533
753 36706245046782588393860298
754 38320251944082891937881187
755 40004114628817630800413176
756 41760809161729312822658759
757 43593436409682884170093796
758 45505227197936038299700224
759 47499547671790613090675448
760 49579904876009328786269120
761 51749952560697537404682656
762 54013497222707253267056948
763 56374504391961609482891107
764 58837105172483194795743411
765 61405603048278060151472865
766 64084480964642335455423217
767 66878408695856348513146549
768 69792250510678423821974031
769 72831073147480429650615534
770 76000154111349029328466247
771 79304990305940923741832614
772 82751307013399515855564456
773 86345067236141892363993275
774 90092481414884273563053572
775 94000017537815579220554182
776 98074411656431198577531492
777 102322678824123702688428339
778 106752124474276166774162362
779 111370356255234933178182760
780 116185296340237618744917282
781 121205194231053462002259930
782 126438640074845945723924251
783 131894578514502942026132658
784 137582323093490446081118215
785 143511571237079483687893800
786 149692419832668997418090895
787 156135381432783748692924996
788 162851401105266648100706908
789 169851873956108720395361082
790 177148663351372553829716875
791 184754119865661654744438312
792 192681100985678537015080867
793 200942991598489335028756478
794 209553725295286813145624022
795 218527806522603026558266368
796 227880333614187002000505083
797 237627022738013102662640668
798 247784232794246714452021596
799 258368991301342081478406960
800 269399021308912292214020220
801 280892769377465010400571943
802 292869434666674810011903338
803 305348999175430040271802989
804 318352259178589984374065946
805 331900857907077295460129638
806 346017319519758217553367576
807 360725084417383803252024924
808 376048545950832344688379185
809 392013088577855453494353414
810 408645127524647234841162572
811 425972150010670517501437397
812 444022758097452423535642924
813 462826713224339965208237442
814 482414982496658139590418448
815 502819786794167738249585706
816 524074650770358385211290493
817 546214454815756792108669871
818 569275489061269048898101814
819 593295509500424357204172987
820 618313796312442037181167006
821 644371214471111796139075563
822 671510276727763442021223915
823 699775209059906556646582144
824 729212018680655983635441967
825 759868564707617332262140806
826 791794631593709842679088192
827 825042005426235483300181613
828 859664553204594137109210488
829 895718305211170023762437109
830 933261540594314848636970391
831 972354876286794335490828954
832 1013061359387797605072427383
833 1055446563141389649639132884
834 1099578686649377225358116922
835 1145528658461704396143492920
836 1193370244192967931243723887
837 1243180158319181179083028941
838 1295038180314801493636950181
839 1349027275295996622652270080
840 1405233719342455093842360495
841 1463747229676459451437475054
842 1524661099884746935130840011
843 1588072340375583386490185314
844 1654081824270793374839588598
845 1722794438939914489417369551
846 1794319243391510362357490342
847 1868769631744664760277688754
848 1946263503012135830337213197
849 2026923437435242099711917132
850 2110876879619642401559914948
851 2198256328730414146469651352
852 2289199536014605644856479625
853 2383849709929378450603425325
854 2482355729164358001586442896
855 2584872363857500932887486592
856 2691560505315074735380190887
857 2802587404557840968722155639
858 2918126920027663428351308733
859 3038359774801123295994083626
860 3163473823669758501054055828
861 3293664330459834248975669304
862 3429134255978558504836121772
863 3570094556987943713060471049
864 3716764496622565964257953339
865 3869371966682831735692198946
866 4028153822251532006298389984
867 4193356229097972895949462205
868 4365235024351343596909974209
869 4544056090942726892133653571
870 4730095746333819266415787814
871 4923641146069498209740710732
872 5124990702711420640150322280
873 5334454520730330504733521180
874 5552354847956285914003790801
875 5779026544208038357595501726
876 6014817567745923481390832745
877 6260089480216285238238336206
878 6515217970780293294075531833
879 6780593400145436212951388934
880 7056621365244647045489260992
881 7343723285335329734549272212
882 7642337010319198766000393012
883 7952917452113183550520766202
884 8275937239932406456642010769
885 8611887400377757805447623911
886 8961278063253615806226310598
887 9324639194075107845139046704
888 9702521354259766294041560384
889 10095496490034784593351354654
890 10504158751129144873509669049
891 10929125340358927439480186519
892 11371037395254976031217371138
893 11830560902924013695868467088
894 12308387649378168642120763884
895 12805236204612881616318494858
896 13321852944760249190562549697
897 13859013112693185132910812384
898 14417521918506316089338397953
899 14998215681351411598732439408
900 15601963014159383239681583034
901 16229666052836585078034593217
902 16882261731581350373147483827
903 17560723106026486389805507110
904 18266060725975906290821425186
905 18999324059567749098039670379
906 19761602970763356874346913184
907 20554029252130352065638226507
908 21377778214959965639925322693
909 22234070338832681391958001991
910 23124172982823410835837118393
911 24049402160616732054715308012
912 25011124381885493067925015389
913 26010758562371192495000280074
914 27049778005193339109861629248
915 28129712456006314017103974226
916 29252150234717501674009491853
917 30418740446578434204894263970
918 31631195275562852243374370168
919 32891292363050697588469241628
920 34200877274946623361686094751
921 35561866060474364753461425243
922 36976247906005825749233772984
923 38446087887404687635263443507
924 39973529824490366983185742006
925 41560799241357880537842345029
926 43210206436424313634372309751
927 44924149666211725456117531245
928 46705118447021231443572724807
929 48555696978802218663701793927
930 50478567695676020998749570126
931 52476514947733394457672682032
932 54552428818891713200786120492
933 56709309085769387945002736772
934 58950269322713595451694403486
935 61278541158301380255863039386
936 63697478688825637031582616470
937 66210563054474727373421223103
938 68821407184119705479904886635
939 71533760714834588884448429397
940 74351515092495081771005861576
941 77278708860027845760184338344
942 80319533140118180705613688230
943 83478337319426971120921252391
944 86759634941620436426917661908
945 90168109816776677563323871053
946 93708622355003806758510294037
947 97386216132383599122716145304
948 101206124697644790913186013157
949 105173778628269321208181267708
950 109294812845045761329371805235
951 113575074194404782944645057352
952 118020629308204689655061498247
953 122637772750978591376215751694
954 127433035465011767725911908343
955 132413193523985887546388902361
956 137585277206309187283693945914
957 142956580399646129275550501235
958 148534670348569757314296424022
959 154327397757682533811337330096
960 160342907262990316287041587701
961 166589648284766826165808460410
962 173076386275616062536112407624
963 179812214377925053983508381061
964 186806565505402858686046600594
965 194069224863921172108120733469
966 201610342927411178840266859355
967 209440448885127663102766611248
968 217570464577168934454892692765
969 226011718935737019474022616730
970 234775962950241054681446072904
971 243875385174984992599438709977
972 253322627798843022277122991528
973 263130803297009521622333009336
974 273313511685619513070485976464
975 283884858400767410378173013733
976 294859472824211133829895336525
977 306252527478832266239845483700
978 318079757917735842586227206184
979 330357483331712351125111813734
980 343102627900654811246367943069
981 356332742915422027613348719845
982 370066029697570767163151500801
983 384321363345341213551202252880
984 399118317335277326980134949332
985 414477189009893126605524038964
986 430419025982863371680489478263
987 446965653494318997831326179136
988 464139702749970181108833592342
989 481964640278959306046063444025
990 500464798346568892642855307552
991 519665406459171840958978488573
992 539592624000119954275862963613
993 560273574036617650230834630960
994 581736378339028136355024812464
995 604010193655505056560802285528
996 627125249286341093679902816455
997 651112886003972080850614928309
998 676005596366178544344382564876
999 701837066471682008736271859670
1000 728642219209048898115569281081