0 1
1 1
2 1
3 1
4 1
5 2
6 2
7 3
8 4
9 5
10 6
11 8
12 10
13 12
14 16
15 19
16 24
17 31
18 37
19 46
20 58
21 70
22 86
23 104
24 127
25 156
26 185
27 222
28 273
29 326
30 392
31 463
32 556
33 669
34 792
35 939
36 1109
37 1317
38 1564
39 1838
40 2156
41 2535
42 2986
43 3514
44 4100
45 4777
46 5577
47 6526
48 7621
49 8847
50 10251
51 11869
52 13807
53 16032
54 18529
55 21370
56 24540
57 28394
58 32812
59 37772
60 43398
61 49690
62 56917
63 65498
64 75141
65 86047
66 98247
67 111973
68 127809
69 146173
70 166883
71 190065
72 216100
73 245128
74 278550
75 317155
76 360357
77 408796
78 462821
79 523184
80 591523
81 670592
82 759131
83 857865
84 968062
85 1090584
86 1226909
87 1385670
88 1563071
89 1760893
90 1980803
91 2225330
92 2496457
93 2802946
94 3152524
95 3540976
96 3972627
97 4451171
98 4981619
99 5568331
100 6236997
101 6987728
102 7819706
103 8741480
104 9760873
105 10887843
106 12131588
107 13548969
108 15128377
109 16874497
110 18804118
111 20933402
112 23281905
113 25868599
114 28797300
115 32057600
116 35654166
117 39619734
118 43986856
119 48793685
120 54078363
121 59993066
122 66605410
123 73885291
124 81895826
125 90701365
126 100375531
127 110993566
128 122694082
129 135885738
130 150382626
131 166305348
132 183778746
133 202943414
134 223945182
135 246947651
136 272572793
137 301002948
138 332176966
139 366333437
140 403737728
141 444668156
142 489433388
143 538357101
144 593133375
145 653301741
146 719130146
147 791114143
148 869777069
149 955694902
150 1049475849
151 1151787826
152 1266338770
153 1391519107
154 1528220656
155 1677414799
156 1840164057
157 2017596318
158 2210943127
159 2421511569
160 2656328863
161 2912680265
162 3192119918
163 3496586967
164 3828146634
165 4189045081
166 4581673874
167 5008629611
168 5481241660
169 5998434722
170 6561315431
171 7173621848
172 7839406358
173 8562994094
174 9349067342
175 10202621554
176 11137891247
177 12166847407
178 13284999195
179 14499583216
180 15818334428
181 17249608887
182 18802334238
183 20486144135
184 22311325673
185 24328355612
186 26520624313
187 28898684875
188 31477299711
189 34272257325
190 37300567094
191 40580410509
192 44131356558
193 47995463099
194 52240500895
195 56839493338
196 61820082751
197 67212012386
198 73047093565
199 79359525970
200 86185868030
201 93565389010
202 101612746335
203 110403083629
204 119911719805
205 130193785084
206 141308490213
207 153319153262
208 166293725778
209 180304835293
210 195430365454
211 211910420750
212 229863295276
213 249255526764
214 270195779076
215 292800582228
216 317194504616
217 343511040285
218 371892816569
219 402492577978
220 435718478749
221 471909543523
222 510950411795
223 553052877116
224 598443769505
225 647365454607
226 700077343555
227 756856475639
228 817999190875
229 884016396279
230 956078677957
231 1033719198098
232 1117346354177
233 1207397052446
234 1304337871682
235 1408667673844
236 1520918945362
237 1641660695150
238 1771499990949
239 1912865906138
240 2065482541814
241 2229679188126
242 2406288906469
243 2596200837183
244 2800364733910
245 3019793812950
246 3255569801157
247 3508846175973
248 3781917826870
249 4078607936337
250 4397466476595
251 4740066513729
252 5108086010312
253 5503315788129
254 5927665242752
255 6383171208177
256 6872004428925
257 7396479424995
258 7963892515409
259 8576621166031
260 9234312361499
261 9940103240419
262 10697339299017
263 11509585510270
264 12380641905552
265 13314556114062
266 14315640724874
267 15388487411422
268 16550470339642
269 17800492970878
270 19140678112124
271 20577220016844
272 22116715503614
273 23766191442804
274 25533128399701
275 27425491262260
276 29451755824000
277 31620942895280
278 33968215755736
279 36488904938289
280 39188451257503
281 42078957278214
282 45173306032364
283 48485204857614
284 52029239298220
285 55820922282044
286 59876754182257
287 64214277935158
288 68895247853655
289 73922331031505
290 79300564200050
291 85053372904381
292 91205668053823
293 97783940669274
294 104816351393758
295 112332836063212
296 120365205905198
297 128947265101182
298 138169301147087
299 148089721133351
300 158692773076659
301 170023369897074
302 182129245968481
303 195061118159470
304 208872870577678
305 223621734595499
306 239368494599156
307 256177689091046
308 274138123745931
309 293518632139378
310 314213644502703
311 336308517791181
312 359893896442445
313 385066034493869
314 411927115347060
315 440585610415101
316 471156636004953
317 503762352418393
318 538532361960829
319 575859174650826
320 615865590831982
321 658541169618001
322 704056588729647
323 752592953257934
324 804342417500140
325 859508812510415
326 918308337944623
327 980970261367182
328 1047737687527975
329 1118868337159999
330 1195445249464979
331 1277119720278959
332 1364158177448949
333 1456898609218752
334 1555699379441618
335 1660940420857661
336 1773024452890141
337 1892378308102259
338 2019454287425964
339 2154731633917171
340 2298962325829252
341 2453904551814181
342 2618894264915324
343 2794557211761983
344 2981556500599562
345 3180594705630406
346 3392416141089515
347 3617809201563629
348 3857608887721072
349 4112699407627984
350 4384016980559573
351 4673286089490350
352 4983414070071704
353 5313361293462063
354 5664345363648453
355 6037655670275623
356 6434657399731900
357 6856795840079390
358 7305600836795897
359 7782691570048308
360 8289781501765131
361 8828683674408969
362 9402438021987335
363 10017185382581378
364 10670671221665008
365 11365244427935418
366 12103390697845466
367 12887740116016043
368 13721075247754102
369 14606339550864823
370 15546646348354716
371 16545288158061508
372 17605746636654679
373 18731809434284121
374 19939098827102126
375 21221443293776040
376 22583336558100411
377 24029531025928881
378 25565051993399838
379 27195212756462507
380 28925630361515176
381 30762242344167688
382 32711324181512387
383 34779507827443322
384 36973801041218701
385 39317283060636648
386 41811361392485674
387 44458161276945970
388 47266696530593219
389 50246492814573478
390 53407615651968920
391 56760699695805611
392 60316979741942412
393 64088323128953087
394 68087264051799537
395 72327039412805380
396 76832285383348691
397 81641798268449226
398 86742143385518693
399 92150285737571954
400 97884143319944648
401 103962638727329204
402 110405753138761265
403 117234583395762703
404 124471401711543082
405 132139718774149411
406 140264349758802680
407 148871484062976958
408 158045053927368827
409 167793062618676861
410 178122286933572201
411 189066181537823577
412 200660057283425318
413 212941180086857395
414 225948875287744005
415 239724636919644153
416 254312242994864731
417 269757876210949776
418 286110251255136591
419 303420748089615628
420 321901410237066766
421 341474803963591712
422 362199493107639003
423 384140899650378256
424 407368031598054913
425 431953672565894465
426 457974580396324348
427 485511696433139626
428 514650364753064402
429 545480563087235307
430 578097144711914526
431 612643035562304473
432 649452785794458599
433 688403358221975822
434 729615125025187190
435 773214992295505258
436 819336742277139593
437 868121392046354722
438 919717571019612618
439 974281916555883997
440 1031979490212585613
441 1092984213911110325
442 1157479328750661901
443 1225763195293143926
444 1298434137176242134
445 1375278067443071047
446 1456526807647973888
447 1542424621802107670
448 1633228860015191334
449 1729210635327802796
450 1830655533087912131
451 1937864356726321400
452 2051153909304976837
453 2170857814970446034
454 2297327379713912859
455 2431039531914385732
456 2573316194384866538
457 2723662745997740019
458 2882522289357056881
459 3050361449322495542
460 3227671579253990572
461 3414970025311637458
462 3612801454652303755
463 3821739247384246027
464 4042386958553469119
465 4275379850124556534
466 4521386499694205592
467 4781110486018142124
468 5057199129920915464
469 5349006603196166921
470 5657141675669029551
471 5982489295175074982
472 6325980812213827212
473 6688596331715108036
474 7071367177544389744
475 7475378479450006171
476 7901771883681993603
477 8351748397722167167
478 8826571370631205130
479 9327569620245019774
480 9858344366310538935
481 10420350224044857168
482 11013441702108484356
483 11639285317080775026
484 12299634079280552980
485 12996331831345055239
486 13731317799930051760
487 14506631364455813171
488 15324417059195437834
489 16186929813208929169
490 17096540445687543918
491 18055741421852041182
492 19067764132847758779
493 20142103826766055825
494 21275205861246818125
495 22470187265055072222
496 23730325235163357218
497 25059065101392244000
498 26460028669466668423
499 27937022968316930093
500 29494049411795287200
501 31135313402686507223
502 32865234390417214507
503 34688456412557063883
504 36609859132872268847
505 38641767271140298561
506 40791034257999227420
507 43056409304670407086
508 45443978780043698748
509 47960138302018948044
510 50611607952294036574
511 53405448208967119709
512 56349076641482337263
513 59450285390968531217
514 62717259484100512698
515 66158596006040817452
516 69783324184485184149
517 73600926413114984046
518 77643396366467429045
519 81908239678464442216
520 86400726864295434012
521 91132654728352497076
522 96116412970415505815
523 101365013055949582436
524 106892118438193650315
525 112712076209803322399
526 118839950232304180785
527 125291555827496574492
528 132083496083985795398
529 139233199869877838039
530 146758961610184148392
531 154731145995472090547
532 163127770493377566455
533 171967385875735518930
534 181272694151760767028
535 191067526298245799230
536 201376896685452042806
537 212227060031640449266
538 223645571022824514563
539 235661346694691787499
540 248304731724603146075
541 261607566740051340260
542 275603259803744851093
543 290326861191977747258
544 305916768950119083580
545 322323136806667222712
546 339585333100293635901
547 357746744566249331997
548 376852893485668454135
549 396951539641031072413
550 418092786970953108628
551 440329195165903493301
552 463715896393375120226
553 488310717414289053517
554 514174307296917414412
555 541370271011946017728
556 569965309134279915067
557 600205419222833107602
558 632028059475734355421
559 665492548774425510310
560 700681250789518211503
561 737680542900440001863
562 776581006015552271522
563 817477623071958758406
564 860469986643294080093
565 905662516014813305442
566 953164684190017603046
567 1003091255221131611381
568 1055562532366572192470
569 1110704617503573168562
570 1168904986677954378551
571 1230193560675539976075
572 1294610590200427977284
573 1362311417139679535090
574 1433458880134163130726
575 1508223665875679014018
576 1586784676339692608438
577 1669329412714897832564
578 1756054376702407179698
579 1847165490009806453905
580 1942878532773444225961
581 2043419601803476778384
582 2149025589450781336414
583 2260196568603731372828
584 2377426881419741903257
585 2500579179542026198085
586 2629944601043074839879
587 2765828201707165526910
588 2908549601394245119100
589 3058443659493223461125
590 3215861180816946473855
591 3381169653183197813622
592 3554754018147764199304
593 3737017476244113452431
594 3928382328318829319553
595 4129290854436852110137
596 4340206232078847107671
597 4562847915990563965841
598 4796732332022739464114
599 5042297658081891705275
600 5300111888515182962286
601 5570769886571762260972
602 5854894619749495090967
603 6153138450347323585881
604 6466184483498520418320
605 6794747975287940165710
606 7139577803427299620437
607 7501458003309865999438
608 7881209372133970244456
609 8279691144152805474283
610 8698671823606406857374
611 9140002022654975209846
612 9603157358686018947076
613 10089189130941092689689
614 10599197925597554940939
615 11134335862681902557160
616 11695808942573060599865
617 12284879496219771510076
618 12902868743683569210222
619 13551159465487498515198
620 14231198791767814976167
621 14944501114094336955381
622 15692651125373801848251
623 16477306993119282764256
624 17303365290063416243605
625 18171483298862449720513
626 19082070665252630785533
627 20037151923428845429724
628 21038845579665189620387
629 22089368355943167662405
630 23191039619732474509072
631 24346286008075578728159
632 25557646254022976237876
633 26827776224249873151516
634 28159454176586571631451
635 29555586247027895191187
636 31019212175695544663211
637 32553511282112640454809
638 34169609647054216950499
639 35865332538131809691399
640 37643143449287079455006
641 39506916102106802462559
642 41460702285530773281167
643 43508739822791794214838
644 45655460885133950360461
645 47905500666664806563394
646 50263706435895474047689
647 52735146979535668311561
648 55325122455386433438679
649 58039174671207744602497
650 60883097807796073661213
651 63862949604565536971471
652 67001156392494299315359
653 70291083962310576874945
654 73738648137245368541083
655 77351214680354273756522
656 81136484754482822296875
657 85102509793824496631582
658 89257707016798633091536
659 93610875607555974393543
660 98171213593684676257825
661 102948335449677016482328
662 107952290456030909217193
663 113193581845979339797167
664 118683186772208622795631
665 124432577128185905554923
666 130482659821718474717233
667 136823726104844993670296
668 143465601293852171403260
669 150422206387211732278125
670 157708090451177171572887
671 165338458223669803723128
672 173329198899320281481054
673 181696916144226668343976
674 190458959392114789081325
675 199633456474483654891178
676 209239347640655362334799
677 219296421024656056908300
678 229825349619417810069747
679 240847729819918783654285
680 252430434561979542283087
681 264574585514722144044917
682 277289241416485283658442
683 290600557565887006597609
684 304535858715531174798058
685 319123690030517342537757
686 334393870208815527132031
687 350377546853544891297729
688 367107254189203967540996
689 384616973219229801179238
690 402942194424483310189837
691 422119983107957488662949
692 442189047493454876403991
693 463189809692075582696137
694 485215253401610643882680
695 508329564003752481345169
696 532519443010849624905187
697 557833750635449201591529
698 584323512588387804218913
699 612042013649663217034490
700 641044895178694150767985
701 671390256724294023046073
702 703138761903261737289304
703 736353748720975730393701
704 771101344516560194103664
705 807450585720100901132058
706 845473542619219528804440
707 885245449337684899827616
708 926855386097522483259828
709 970585400160779620619240
710 1016331447211644890108361
711 1064184293370124173906465
712 1114238693096758098824808
713 1166593560119813795680231
714 1221352145501023666969497
715 1278622223131704100818647
716 1338516282959631919413903
717 1401151732262000341238148
718 1466651105289087112160815
719 1535142281619282401140746
720 1606758713576263609193682
721 1681639663076266811423463
722 1759930448284440174483483
723 1842000869598896018835640
724 1928008329037457719554216
725 2017941046082799101415823
726 2111974025964899322152932
727 2210289891674124563218145
728 2313079207491225667574842
729 2420540815913035529503661
730 2532882188516307541478892
731 2650319791319267938075083
732 2773079465226662819849034
733 2901396822162678160317769
734 3035517657524218642638590
735 3175698379607211288769626
736 3322206456688744157650259
737 3475320882469738355764462
738 3636039235958537013084173
739 3804099096012594215503592
740 3979753767471751821704484
741 4163338647723795289838481
742 4355203599965252226854886
743 4555713562167011828881784
744 4765249181042358615477273
745 4984207472020812857318829
746 5213002506264460965050198
747 5452066125809751231759664
748 5701848687953777282217591
749 5962819840053744949325480
750 6235469325947335963296726
751 6520307825254981311682983
752 6818099340508800861208628
753 7130427794330446123340651
754 7456749096990556278014920
755 7797676059350246523644928
756 8153847712194029608185031
757 8525930401588148402430862
758 8914618928889682448442419
759 9320637737177105166379695
760 9744742145949363904572931
761 10187719636003987360089445
762 10650391186486733869146248
763 11133612666173844581405045
764 11638276281135995519107444
765 12165312081007103708651098
766 12715689526175629800662981
767 13291232646869286373906446
768 13894207311197467727418710
769 14523943090268310290820309
770 15181601343300938034722426
771 15868392684768885175179280
772 16585579024756334717710685
773 17334475691815504307664439
774 18116453641573486739904635
775 18932941754472569506388214
776 19785429226146903039517421
777 20675468054084103583320819
778 21604675624348622894178110
779 22574737402300157884504005
780 23587409731378731530933491
781 24644522744196019198051854
782 25749641290167913474971116
783 26906783349066095607116274
784 28114811049603773739043357
785 29375913106372154159143721
786 30692370266601698482040521
787 32066559091152536876825188
788 33500955887181650046865279
789 34998140798416365537832060
790 36560802059204905777907270
791 38191740418734779105061501
792 39893873742068783756929433
793 41670241794885571796423127
794 43524011219089774555277550
795 45458480706712270765670318
796 47477086379819689298495661
797 49585666953417698472020777
798 51793392789227898391538393
799 54097334302194882640467471
800 56501594067771306067716334
801 59010445725093910369069401
802 61628340948216456105070331
803 64359916694838880029271336
804 67210002743304403241100746
805 70183629529065068785686025
806 73286036292219303325809689
807 76522679548185445044016769
808 79899241894009240347693908
809 83421641163297537436608021
810 87096039943237699528053154
811 90928855467692808073637713
812 94927403847506534369420183
813 99115742708321452703549427
814 103485015231600318330219894
815 108042870836967319646686225
816 112797275285618731258685486
817 117756523470317317411855310
818 122929252710655593364154323
819 128324456573064503670022990
820 133951499235805163608326379
821 139820130419913756747992810
822 145940500907886748641303897
823 152323178672681589357047344
824 158979165640485156664795046
825 165919915111549844666577167
826 173157349864338610438704847
827 180703880969131947589515003
828 188596823736608404944175404
829 196837330343234068995522131
830 205430462134539789937146734
831 214390990527599089903710111
832 223734292382931123210067526
833 233476374272965535369956346
834 243633897701281301115503921
835 254224205309023459130198845
836 265265348106222332509236144
837 276776113767187743543802325
838 288776056030570572088907232
839 301285525246237960685576488
840 314325700112634691288561697
841 327918620649970843916891381
842 342087222456216171490084329
843 356873401586395089774528985
844 372331883411865989457212933
845 388446313130202008799219311
846 405243945146831756891077522
847 422753142195185346953600267
848 441003419427275639421754875
849 460025490219134233296960403
850 479851313756300063910192502
851 500514144466924790904474475
852 522048583372618534667100730
853 544490631429701895106543338
854 567877744936276325494846152
855 592248893083256067608431685
856 617644617730451081626027187
857 644107095491723893646042086
858 671680202216403851971296446
859 700498491963990231295609874
860 730559883822754672098189174
861 761885336349342758159645575
862 794526909492031691180825838
863 828538762242982766995274370
864 863977235453286639650999054
865 900900937843504211447980529
866 939370835330184094363130099
867 979450343793350034791470272
868 1021205425414477083651638978
869 1064704688719315672108653658
870 1110019492464781366883412686
871 1157224053514319680707077789
872 1206395558851370989161947416
873 1257614281886128334829646950
874 1310983210757948700738555594
875 1366777467288945401370652239
876 1424898976135382677349003698
877 1485442838104586138330330014
878 1548507959597725324253026379
879 1614197201666904925023793247
880 1682617534783791575662125559
881 1753880199533707513072376584
882 1828100873457053798034462539
883 1905399844267939160768059555
884 1985902189688395790416134382
885 2069737964145162284358021329
886 2157042392585133646767519318
887 2247956071674804278649468573
888 2342625178658807348964737670
889 2441201688162551639962430675
890 2543975682064845889262942402
891 2651280612471882379763365451
892 2763022549257237040670099202
893 2879381277606623121983245936
894 3000543718251898480746456522
895 3126704204745904727659000278
896 3258064771280811917394263963
897 3394835451442155000491106924
898 3537234588304866890296026007
899 3685489156292511816817022606
900 3839835095236065575734632688
901 4000517657084559283908200174
902 4167791765736142837197171311
903 4341922390475240693146213876
904 4523184933518886153206859937
905 4711865632193663562626435621
906 4908602922183598947865727450
907 5113841953252910145984614833
908 5327495426041211657660556881
909 5549901474126962303030821551
910 5781411543906933342633887866
911 6022390907902453983777127336
912 6273219197438721368741267236
913 6534290955412406396489097558
914 6806016209888797665804788416
915 7088821069296272197859651115
916 7383148340013753524046654973
917 7689458167175273676145823692
918 8008228699545618610720777500
919 8339956779351535973016940564
920 8685158657984977111327847117
921 9044370738527531026442908545
922 9418800389820803342023792766
923 9809255070546731467580931762
924 10215584479116158307470988080
925 10638421378834295611239145707
926 11078423250338753503813251618
927 11536273237398656866961620640
928 12012681128148394307195044997
929 12508384373055303397217297245
930 13024149140966928023597094673
931 13560771414631965645391803908
932 14119078127138665978189279154
933 14699928340766370626326540294
934 15304214469799069236901698398
935 15932863548905461093719262574
936 16586838548746985910218577249
937 17267139740534841776538370595
938 17975740928428535791335741205
939 18714681219450131434810865412
940 19483419541898131561121730143
941 20283134219030218243536778497
942 21115049248276796799789739657
943 21980436035936565639293439536
944 22880615196396540385623561083
945 23816958418225755528713994267
946 24790890399575908041366137355
947 25803890855408458789656039982
948 26857496599157692059642259499
949 27953303701531601838370063639
950 29092969729248811977783348070
951 30278216066608645833377694768
952 31510830322894591838759841479
953 32792668828717311870264213005
954 34126332863027830078285399837
955 35517666351381703761533381230
956 36964657047596055957406871645
957 38469488723355187400978648067
958 40034429158988734183873137580
959 41661833310805216620520189522
960 43354146595408803685380376032
961 45113908295230161142466015165
962 46943755089651503756260461363
963 48846424716261372336444235864
964 50824759766934431202965732037
965 52881711623597899317770782392
966 55020344538717249869773244485
967 57243839865711797589110693257
968 59555500444693834070846371121
969 61958755149115422480911311971
970 64457163599102848050971514352
971 67062140212014260355921907837
972 69772285078103076352719763839
973 72589914725254072444024041559
974 75519211227007136631357981636
975 78564516232351337960487094933
976 81730336934662596123423987044
977 85021352259415926753086269846
978 88442419278526086943353583940
979 91998579859445761554999441518
980 95695067557436570422561939883
981 99537314759722762085470299090
982 103530960090543569490862490525
983 107681856086435375203069493907
984 111996077151402276081457926601
985 116479927801970801027237390105
986 121139951212474763529948718255
987 125989534390886815501858205085
988 131040905530067261020894760393
989 136291074753761294858491581471
990 141747719174847919471757405179
991 147418806716829724838510817805
992 153312606915252668747537413698
993 159437702112338902345740954237
994 165802999058855597955800414218
995 172417740937733352052581233287
996 179291519824453269562266293935
997 186434289599746518962796619301
998 193856379330690814714088459390
999 201568507136849347094305716477
1000 209581794558675865935581028281