0 1
1 1
2 2
3 3
4 4
5 7
6 10
7 14
8 19
9 27
10 37
11 50
12 67
13 88
14 115
15 153
16 196
17 253
18 324
19 412
20 524
21 661
22 828
23 1036
24 1290
25 1603
26 1980
27 2443
28 2997
29 3671
30 4487
31 5460
32 6631
33 8034
34 9703
35 11703
36 14075
37 16890
38 20226
39 24175
40 28838
41 34332
42 40801
43 48394
44 57307
45 67765
46 79974
47 94249
48 110901
49 130292
50 152876
51 179109
52 209550
53 244844
54 285721
55 333001
56 387618
57 450665
58 523329
59 607030
60 703363
61 814041
62 941161
63 1086997
64 1254130
65 1445561
66 1664560
67 1914888
68 2200819
69 2527132
70 2899230
71 3323157
72 3805823
73 4354842
74 4978967
75 5687947
76 6492595
77 7405299
78 8439811
79 9611501
80 10937822
81 12438005
82 14133773
83 16049413
84 18212085
85 20652059
86 23403197
87 26503350
88 29994600
89 33924084
90 38344353
91 43313518
92 48896948
93 55166950
94 62204076
95 70098144
96 78948612
97 88866149
98 99973859
99 112408192
100 126320648
101 141879120
102 159270122
103 178699808
104 200397248
105 224615794
106 251635457
107 281766918
108 315353373
109 352774088
110 394449086
111 440841360
112 492462952
113 549879155
114 613713885
115 684655226
116 763462260
117 850972075
118 948106711
119 1055882808
120 1175420001
121 1307949780
122 1454829621
123 1617551809
124 1797758048
125 1997254439
126 2218025132
127 2462251098
128 2732328936
129 3030890141
130 3360824050
131 3725301770
132 4127803794
133 4572146548
134 5062517232
135 5603505611
136 6200140603
137 6857935240
138 7582926878
139 8381726750
140 9261575068
141 10230393446
142 11296851486
143 12470433385
144 13761511176
145 15181424639
146 16742569360
147 18458491918
148 20343990332
149 22415230217
150 24689863287
151 27187156739
152 29928144782
153 32935775941
154 36235085040
155 39853379345
156 43820430350
157 48168695064
158 52933549023
159 58153537414
160 63870650487
161 70130621494
162 76983250813
163 84482750030
164 92688128419
165 101663596590
166 111479006744
167 122210345541
168 133940240847
169 146758528687
170 160762866951
171 176059381682
172 192763388257
173 211000159687
174 230905754795
175 252627918465
176 276327053979
177 302177275276
178 330367532702
179 361102851316
180 394605643602
181 431117133067
182 470898916155
183 514234606749
184 561431638963
185 612823215305
186 668770377544
187 729664279229
188 795928614850
189 868022239103
190 946441994608
191 1031725764516
192 1124455759244
193 1225262047065
194 1334826387643
195 1453886328898
196 1583239623482
197 1723749031617
198 1876347419805
199 2042043302616
200 2221926804596
201 2417176037371
202 2629064013383
203 2858966062228
204 3108367796765
205 3378873701160
206 3672216361313
207 3990266399036
208 4335043121629
209 4708726032592
210 5113667136319
211 5552404185927
212 6027674974186
213 6542432593043
214 7099861889963
215 7703397159021
216 8356741058913
217 9063885028972
218 9829131153964
219 10657115640458
220 11552834023177
221 12521668235866
222 13569415646755
223 14702320195182
224 15927105862912
225 17251012505484
226 18681834289942
227 20227961035346
228 21898422362699
229 23702935164478
230 25651954481511
231 27756727949638
232 30029354271677
233 32482845834122
234 35131195765338
235 37989449834011
236 41073783456019
237 44401584198681
238 47991540071238
239 51863734222275
240 56039746173853
241 60542760267866
242 65397681883591
243 70631261616597
244 76272228327125
245 82351431560248
246 88901993741695
247 95959473249168
248 103562038733196
249 111750655584943
250 120569285386223
251 130065099248265
252 140288705892441
253 151294395472526
254 163140400388136
255 175889173905457
256 189607687974766
257 204367751777207
258 220246351715473
259 237326014989205
260 255695198005723
261 275448701094904
262 296688111753765
263 319522277948447
264 344067813477063
265 370449637723183
266 398801551925556
267 429266854429892
268 461998997313250
269 497162287575355
270 534932635135452
271 575498351200468
272 619061000456737
273 665836309813819
274 716055138229065
275 769964511335078
276 827828724581694
277 889930520283177
278 956572342589290
279 1028077675673582
280 1104792470594052
281 1187086666580143
282 1275355812659466
283 1370022796086558
284 1471539684877182
285 1580389691011041
286 1697089262518910
287 1822190313185750
288 1956282597237922
289 2099996239768270
290 2254004432174779
291 2419026302636847
292 2595829973856812
293 2785235819096036
294 2988119929129151
295 3205417803870284
296 3438128282607728
297 3687317727927454
298 3954124479025213
299 4239763592285455
300 4545531885748402
301 4872813307544938
302 5223084648982873
303 5597921622063518
304 5999005326079969
305 6428129126925447
306 6887205973810749
307 7378276182519514
308 7903515712640242
309 8465244969791761
310 9065938165666536
311 9708233270333488
312 10394942593094873
313 11129064030605617
314 11913793024384283
315 12752535269605446
316 13648920222506210
317 14606815456276845
318 15630341914535392
319 16723890120358001
320 17892137398028485
321 19140066168142770
322 20472983383974357
323 21896541176640747
324 23416758782777036
325 25040045833318394
326 26773227085535248
327 28623568685532545
328 30598806053422003
329 32707173490879468
330 34957435612164965
331 37358920710409463
332 39921556176557879
333 42655906090382500
334 45573211118025880
335 48685430852761374
336 52005288743260255
337 55546319767817974
338 59322921015501142
339 63350405348001518
340 67645058326551558
341 72224198597689634
342 77106241942866178
343 82310769208933491
344 87858598351740738
345 93771860832308859
346 100074082625546452
347 106790270115215618
348 113947001157536260
349 121572521623721841
350 129696847741402409
351 138351874572785795
352 147571490994938632
353 157391701558957113
354 167850755631202831
355 178989284243536263
356 190850445102077207
357 203480076229412456
358 216926858742781081
359 231242489302718155
360 246481862788569086
361 262703265798028143
362 279968581600270544
363 298343507197430102
364 317897783203245271
365 338705437275617602
366 360845041881295126
367 384399987225722269
368 409458770215216589
369 436115300373412900
370 464469223687694344
371 494626265412624210
372 526698592915527535
373 560805199710068325
374 597072311893480303
375 635633818257961819
376 676631725431946855
377 720216639479042265
378 766548275448698362
379 815795996478253411
380 868139384119443705
381 923768841653401806
382 982886232273284259
383 1045705554097876688
384 1112453654098438699
385 1183370983137039318
386 1258712394433181893
387 1338747987901732176
388 1423764002942240425
389 1514063762407076957
390 1609968670610024697
391 1711819268411548047
392 1819976348581286868
393 1934822134792251077
394 2056761527819376105
395 2186223422685586583
396 2323662100703555394
397 2469558700597568090
398 2624422773093850487
399 2788793923617050011
400 2963243547988266082
401 3148376666277878921
402 3344833860248033535
403 3553293320113780141
404 3774473006673813136
405 4009132935162696344
406 4258077587549008704
407 4522158460358715555
408 4802276755460226404
409 5099386221691184761
410 5414496155602049490
411 5748674570031544213
412 6103051539732120301
413 6478822733718663142
414 6877253144552654663
415 7299681025322402287
416 7747522045650750945
417 8222273678662942568
418 8725519831491066685
419 9258935732570859913
420 9824293089663691786
421 10423465533311294038
422 11058434361208998981
423 11731294599763758543
424 12444261400034068403
425 13199676786111790487
426 14000016774964018691
427 14847898887798930853
428 15746090074034524890
429 16697515070080607664
430 17705265216328318577
431 18772607756957338515
432 19902995648470614388
433 21100077904228477921
434 22367710503709028304
435 23709967896678349677
436 25131155134094192722
437 26635820659216751579
438 28228769794106015400
439 29915078958605807430
440 31700110660797629188
441 33589529299931298575
442 35589317825044879457
443 37705795294661313002
444 39945635385349195438
445 42315885899423162511
446 44823989324660748197
447 47477804501646916913
448 50285629457254694591
449 53256225465814675907
450 56398842402655961440
451 59723245458107475420
452 63239743283556607865
453 66959217644776311734
454 70893154661736356776
455 75053677718100979924
456 79453582127898101932
457 84106371651416871487
458 89026296957031358675
459 94228396130642168976
460 99728537339664359779
461 105543463763932386443
462 111690840911647651493
463 118189306444532628270
464 125058522642734390832
465 132319231646584628773
466 139993313619418774619
467 148103847982966628810
468 156675177884448242300
469 165732978062749758762
470 175304326289449446206
471 185417778569361880557
472 196103448294754817630
473 207393089557084823695
474 219320184830479860170
475 231920037252036594748
476 245229867735346123400
477 259288917165573711459
478 274138553936965109541
479 289822387106817006629
480 306386385453635924076
481 323879002741795827285
482 342351309510171347226
483 361857131718011609183
484 382453196598265594535
485 404199286085944947790
486 427158398207510121157
487 451396916836710846752
488 476984790242407415754
489 503995718875202949546
490 532507352862048932027
491 562601499701305370060
492 594364342675263798998
493 627886670522868059515
494 663264118942406775381
495 700597424522072895814
496 739992691726145633718
497 781561673595608500427
498 825422066854484000763
499 871697822147657994057
500 920519470171654709177
501 972024464497405079056
502 1026357541923717377637
503 1083671101241265252952
504 1144125601330375120406
505 1207889979561375210402
506 1275142091513872932920
507 1346069173081247969845
508 1420868326079057237005
509 1499747028530979390012
510 1582923670863262934208
511 1670628119299158825499
512 1763102307807974306847
513 1860600860029361710231
514 1963391742663280303617
515 2071756951888517692482
516 2185993234448873938345
517 2306412845126253790002
518 2433344342403319508197
519 2567133424206167637400
520 2708143805709465518162
521 2856758141282659578187
522 3013378992756737566388
523 3178429846296731885561
524 3352356180275961862695
525 3535626586663690925411
526 3728733948559703117333
527 3932196676636466055960
528 4146560007382546969721
529 4372397366181082179929
530 4610311798402986022877
531 4860937471847688346043
532 5124941254024994373108
533 5403024367939214886495
534 5695924130212824254277
535 6004415775571200477355
536 6329314371902820274074
537 6671476830311243620559
538 7031804014786823091276
539 7411242956347630536914
540 7810789176730616460359
541 8231489126957200586204
542 8674442746351565809478
543 9140806147855567753661
544 9631794435763452575535
545 10148684662290657754257
546 10692818929696171311859
547 11265607644997924130270
548 11868532934654582799377
549 12503152226937356463095
550 13171102010081939787124
551 13874101774693986611618
552 14613958149282789732198
553 15392569238217895094521
554 16211929171843035591942
555 17074132878941178419465
556 17981381092226346861519
557 18935985598041313601131
558 19940374741966654325152
559 20997099202598932819316
560 22108838046332010086501
561 23278405076578927182913
562 24508755491503941846221
563 25802992864994137993585
564 27164376466291402073530
565 28596328934428655004806
566 30102444324370274000770
567 31686496542547636030243
568 33352448190308307806931
569 35104459834663060802345
570 36946899726619478570186
571 38884353988338474675277
572 40921637291340057319742
573 43063804049019510052220
574 45316160147819439694657
575 47684275242534833601683
576 50173995642412535815842
577 52791457815945932025500
578 55543102543559679598164
579 58435689748733800998043
580 61476314039532540464738
581 64672420993983444128408
582 68031824224299791160259
583 71562723256557831519374
584 75273722264132210633172
585 79173849694960628623351
586 83272578834558618555400
587 87579849348637724703076
588 92106089851199626801155
589 96862241546092185218426
590 101859782992219541395998
591 107110756044905426951455
592 112627793028321441718517
593 118424145196411073871032
594 124513712542374747406079
595 130911075019534322006085
596 137631525239271925885128
597 144691102714744304418395
598 152106629722215768790163
599 159895748855136050229521
600 168076962349518614041275
601 176669673262760805754477
602 185694228591792066372507
603 195171964420348338901947
604 205125253189261448005063
605 215577553187922249633391
606 226553460369538753012260
607 238078762597474164626682
608 250180496434818458228891
609 262887006594435568505573
610 276228008172043507215452
611 290234651790435956079266
612 304939591788752765744044
613 320377057596764388284017
614 336582928440462253536354
615 353594811531853534354742
616 371452123902761946850291
617 390196178049643595672699
618 409870271563952666086698
619 430519780930455960641975
620 452192259684102696187332
621 474937541124628687320745
622 498807845797028230153773
623 523857893955372692836891
624 550145023237216409230833
625 577729311786022857609564
626 606673707069684688067796
627 637044160654321494492049
628 668909769204139546910243
629 702342921990248810901427
630 737419455203973877287862
631 774218813383397079215685
632 812824218275650403305313
633 853322845471854665679334
634 895806009166623220072483
635 940369355409718303076224
636 987113064233807776452427
637 1036142061059349278283025
638 1087566237795449275412414
639 1141500684074148523725331
640 1198065929075001820954685
641 1257388194417082614008101
642 1319599658616690323509448
643 1384838733631108870472351
644 1453250354031796903577954
645 1524986279374422283247751
646 1600205410358236818208587
647 1679074119393457668562545
648 1761766596222627322425916
649 1848465209270423750958179
650 1939360883426120029248478
651 2034653494993913223025124
652 2134552284578711184284155
653 2239276288708729471795927
654 2349054791031480735701263
655 2464127793956492992767067
656 2584746511656433474283365
657 2711173885378312559290863
658 2843685122058167816676548
659 2982568257276154019092917
660 3128124743634362934528733
661 3280670065687058686035472
662 3440534382602409937649741
663 3608063199786318955971356
664 3783618070752691829402608
665 3967577330580537102343333
666 4160336862356733527032114
667 4362310898064275593409172
668 4573932855439377918276589
669 4795656212387124288416886
670 5027955420614491111673527
671 5271326860211676195877554
672 5526289836987850012613145
673 5793387624445849359259702
674 6073188552362084807954144
675 6366287144023170479298899
676 6673305304259668108921750
677 6994893560510004317398393
678 7331732359244231904834994
679 7684533420178046424067487
680 8054041150812481840825985
681 8441034123944193950664418
682 8846326620905385074468564
683 9270770243411404648799530
684 9715255597018100590469309
685 10180714049320299069208000
686 10668119566157570274593184
687 11178490629233930537800117
688 11712892238704574386914747
689 12272438004435370336724328
690 12858292329799941894764673
691 13471672692044980029330332
692 14113852023427251786870414
693 14786161197505879276649467
694 15489991625161187118334316
695 16226797965107035854667641
696 16998100953867425719590124
697 17805490360400615555856584
698 18650628070775384108624422
699 19535251308534765234078098
700 20461175996622986888607143
701 21430300267001833981161987
702 22444608124343660188092042
703 23506173270460231112492062
704 24617163096409937129076928
705 25779842849521133471214657
706 26996579982876960435256828
707 28269848695127451391053190
708 29602234668828585065547599
709 30996440015855763093607812
710 32455288438801519692835444
711 33981730617644729535158002
712 35578849831371795282951903
713 37249867824639883539116521
714 38998150929998943765945424
715 40827216456633676684075858
716 42740739357049536096733306
717 44742559183609020609477934
718 46836687347326726971323243
719 49027314691854711990604528
720 51318819396134486121847759
721 53715775219759361304065297
722 56222960105681782838257456
723 58845365155515661286601205
724 61588203993324618136918065
725 64456922534454450219728871
726 67457209176663122903634730
727 70595005431525352507328079
728 73876517014842457973868705
729 77308225415572916178536633
730 80896899963616187896527269
731 84649610417633202036700918
732 88573740094972772263277497
733 92676999566695600999833171
734 96967440941647870916312946
735 101453472764536263313574105
736 106143875553997215601594457
737 111047818007736956936725736
738 116174873902947080761259106
739 121535039721374975003229847
740 127138753029651126349564683
741 132996911646748147874347522
742 139120893631771375700202955
743 145522578126660092472642460
744 152214367089814107276549428
745 159209207958154807745305429
746 166520617276685249985448970
747 174162705336232844325404848
748 182150201861743285788566524
749 190498482795248219226245274
750 199223598219454464301273775
751 208342301469802384599519907
752 217872079484818089730917820
753 227831184446641731748396958
754 238238666765755480044062686
755 249114409466163091308069814
756 260479164029591885503704690
757 272354587759701031400745039
758 284763282729791028127518633
759 297728836380122138933714449
760 311275863833668326013148255
761 325430052001962169330550267
762 340218205555629741843825286
763 355668294837277036668059076
764 371809505797576030554545582
765 388672292038713743892763980
766 406288429052816914076138794
767 424691070746553393966943160
768 443914808346844674857952941
769 463995731786507851604261662
770 484971493672685747862020298
771 506881375945127112369779769
772 529766359335751249038833139
773 553669195745479780617374895
774 578634483659049536637072229
775 604708746723442016349695635
776 631940515620684011424972907
777 660380413371098638789602179
778 690081244208624362295600904
779 721098086175580007376340127
780 753488387590245043215050174
781 787312067546855732586768430
782 822631620614098498047306275
783 859512225904921895581810659
784 898021860697498238943501022
785 938231418794455643808475015
786 980214833815082202777812401
787 1024049207623087640873758585
788 1069814944100705920569401859
789 1117595888488447364287138479
790 1167479472518673735346886410
791 1219556865580387687997941534
792 1273923132162212955491072969
793 1330677395830508003483009881
794 1389923010009918560107202108
795 1451767735844448952915462340
796 1516323927428334774955195965
797 1583708724707646700202400174
798 1654044254365664700778314486
799 1727457839017651686972738494
800 1804082215053744252945590365
801 1884055759482285409654620502
802 1967522726140070177118356723
803 2054633491650680568700457927
804 2145544811527373815194753549
805 2240420086832879262265849031
806 2339429641824978729491986651
807 2442751013033916740042297249
808 2550569250235536304793038535
809 2663077229802589205019438325
810 2780475980935954289369474741
811 2902975025297541747233375424
812 3030792730587494976358285285
813 3164156678629955209091704346
814 3303304048554159455722144004
815 3448482015681032329478220785
816 3599948166749741398839427470
817 3757970932143949491608715537
818 3922830035803752607225384602
819 4094816963536577350862623088
820 4274235450468666830171778710
821 4461401988408250054897806377
822 4656646353922110024071650563
823 4860312157959084448971844666
824 5072757417887096644628993519
825 5294355152844670499144040928
826 5525494003343582606224537846
827 5766578876096398146804757752
828 6018031615081178670950816882
829 6280291699895695497120188933
830 6553816972495089516655912833
831 6839084393450147046868318521
832 7136590828908274354617711554
833 7446853869485915011732059623
834 7770412682369631719858450283
835 8107828897953437232361661755
836 8459687532392279735224479081
837 8826597947505941643279823264
838 9209194849524075103788324820
839 9608139328221753336774468825
840 10024119938055848080626491916
841 10457853822975837108861539903
842 10910087886648392072927057612
843 11381600009903389590525118583
844 11873200317279925024262833595
845 12385732494624589262206919002
846 12920075159770799009792817197
847 13477143288407459310627931560
848 14057889697327795636926258165
849 14663306587334939215305757284
850 15294427148169904506305778137
851 15952327227920087761668528785
852 16638127069462471062577356674
853 17352993116595472749531688096
854 18098139892616983218914711330
855 18874831954213710493834041674
856 19684385923638684394814383188
857 20528172602269788203873626878
858 21407619168762665389826726890
859 22324211465136455525837866653
860 23279496374260722714517614835
861 24275084292346833842861337826
862 25312651700187111473031604516
863 26393943837030522392905749025
864 27520777481134671154040284058
865 28695043841190658680139814852
866 29918711562980157476321775273
867 31193829855793073720250090911
868 32522531743309647511817529245
869 33907037443833029359077017722
870 35349657884947516212572938418
871 36852798357873996497017978380
872 38418962316998012036793791765
873 40050755330257477581208342137
874 41750889186296798601059994937
875 43522186164522197714198361832
876 45367583474429814462395225971
877 47290137870823908408106653371
878 49293030451797609366375739634
879 51379571646613472294450175871
880 53553206400895971463763563483
881 55817519566833386065516341523
882 58176241506382678623160713799
883 60633253915778354106623355383
884 63192595879965331879645671763
885 65858470165907000526713430207
886 68635249764063309805665651873
887 71527484687690452735498224936
888 74539909039983890407606906379
889 77677448359470677016577263673
890 80945227254455774557630874447
891 84348577337740848032901686325
892 87893045473263464665123603971
893 91584402346750266293373751912
894 95428651372940147271627146430
895 99432037952413376551589656138
896 103601059091560600984812146183
897 107942473399742430198998337627
898 112463311478226529197527773678
899 117170886716045555955977134298
900 122072806508496627145994949233
901 127176983914602053243364499123
902 132491649770472659406700471288
903 138025365276159935717301221741
904 143787035074252405711549598058
905 149785920839165861592312579952
906 156031655396797418677803401196
907 162534257394960654435881601396
908 169304146545794417061385021250
909 176352159462142251240946584055
910 183689566110733867447777799071
911 191328086905865787905173493324
912 199279910468176390380487966925
913 207557712074042235128606947204
914 216174672822089038739110796888
915 225144499544313234599443129731
916 234481445490350063971904114441
917 244200331814502951842683285273
918 254316569896267966498084539621
919 264846184526247922385239153990
920 275805837990554695004576291165
921 287212855088047165082298770111
922 299085249116047544674298653236
923 311441748861522366308738634480
924 324301826636107907850277285049
925 337685727394805113187732302071
926 351614498979668051264344200952
927 366110023531364601864574795377
928 381195050113100405395194331120
929 396893228593069278425344722704
930 413229144833327466232838566290
931 430228357234787547400799522040
932 447917434689892872913107479844
933 466323995996467548663115382854
934 485476750788242679820487138152
935 505405542039639500309371555078
936 526141390204546820067218186059
937 547716539051066742573961843156
938 570164503256521740782097680486
939 593520117829420943543678981069
940 617819589427576996049990961442
941 643100549644150347935387963801
942 669402110336078639787007513325
943 696764921072128470966369832656
944 725231228780688831094795297327
945 754844939680413585477742470069
946 785651683579918477205507483058
947 817698880635950137370455312050
948 851035810662774716393654989680
949 885713685088986249395714098155
950 921785721661514182492175584209
951 959307222000320212808053874288
952 998335652111121494058647279990
953 1038930725967465261253238548027
954 1081154492277614141450027035541
955 1125071424555987131738487341271
956 1170748514623343918935170872969
957 1218255369664505562497472737057
958 1267664312977178439638051591449
959 1319050488550396845156384596491
960 1372491969616229050868815766678
961 1428069871323708489587402328297
962 1485868467689462794629511744262
963 1545975312985225698806279577569
964 1608481367728337527894072028459
965 1673481129447476717370504302061
966 1741072768402225213778110178013
967 1811358268441662844052140651634
968 1884443573194018081830837694446
969 1960438737786483743263417631404
970 2039458086301644943943277966594
971 2121620375184572398015742545780
972 2207048962822516424425161809114
973 2295871985527305766828816297974
974 2388222540159020806846955816193
975 2484238873638283592841417410466
976 2584064579603598334718035240843
977 2687848802479597031270192280596
978 2795746449231807508339955515900
979 2907918409093677579994722920922
980 3024531781562071954095319521053
981 3145760112968320993517727500814
982 3271783641943156080917535295971
983 3402789554105529159895701078294
984 3538972246317398580663888370530
985 3680533600859084714699884048161
986 3827683269892772501700433728278
987 3980638970595180284833826864746
988 4139626791354341675638844866403
989 4304881509439877053021739199852
990 4476646920571081535200306400226
991 4655176180822645394024134989242
992 4840732161323870078856269725332
993 5033587816223868129826500435465
994 5234026564412458833954615653748
995 5442342685504314772738101323420
996 5658841730612399439705008570686
997 5883840948455885653579892431121
998 6117669727367582134564042817401
999 6360670053786445757286520270372
1000 6613196987842044904360019879485