0 1
1 1
2 2
3 2
4 3
5 3
6 5
7 5
8 8
9 9
10 13
11 15
12 22
13 25
14 35
15 42
16 56
17 67
18 89
19 106
20 138
21 166
22 211
23 254
24 321
25 384
26 479
27 575
28 709
29 848
30 1040
31 1239
32 1508
33 1795
34 2168
35 2574
36 3095
37 3661
38 4379
39 5171
40 6154
41 7246
42 8592
43 10088
44 11915
45 13960
46 16425
47 19197
48 22520
49 26253
50 30702
51 35718
52 41647
53 48343
54 56225
55 65122
56 75548
57 87332
58 101067
59 116601
60 134648
61 155039
62 178652
63 205344
64 236132
65 270929
66 310963
67 356170
68 408047
69 466611
70 533624
71 609238
72 695579
73 792907
74 903812
75 1028765
76 1170828
77 1330773
78 1512302
79 1716487
80 1947827
81 2207852
82 2501929
83 2832215
84 3205192
85 3623698
86 4095606
87 4624712
88 5220437
89 5887817
90 6638249
91 7478187
92 8421449
93 9476371
94 10659544
95 11981700
96 13462886
97 15116627
98 16967207
99 19031740
100 21339418
101 23911835
102 26784254
103 29983572
104 33552416
105 37524345
106 41950628
107 46873054
108 52353456
109 58443397
110 65217507
111 72739458
112 81098954
113 90374473
114 100674038
115 112093787
116 124763798
117 138801829
118 154364068
119 171594523
120 190680896
121 211798492
122 235172862
123 261017330
124 289602260
125 321186853
126 356095341
127 394641604
128 437214306
129 484193271
130 536043531
131 593224105
132 656291386
133 725798624
134 802411184
135 886795382
136 979745605
137 1082063337
138 1194696816
139 1318608065
140 1454928241
141 1604811074
142 1769604113
143 1950689438
144 2149671689
145 2368203565
146 2608194591
147 2871619380
148 3160747520
149 3477935704
150 3825880114
151 4207389270
152 4625663840
153 5084047904
154 5586336957
155 6136508818
156 6739061663
157 7398721011
158 8120814034
159 8910949754
160 9775430912
161 10720908962
162 11754836211
163 12885091294
164 14120479366
165 15470324961
166 16945022325
167 18555597524
168 20314312650
169 22234192365
170 24329692016
171 26616184919
172 29110697566
173 31831360283
174 34798214856
175 38032623081
176 41558159461
177 45399973906
178 49585774461
179 54145147466
180 59110637817
181 64517020846
182 70402496543
183 76807909205
184 83778062904
185 91360893908
186 99608918037
187 108578349896
188 118330703304
189 128931854055
190 140453804469
191 152973696560
192 166575755712
193 181350249107
194 197395636377
195 214817471129
196 233730774619
197 254258890940
198 276536105169
199 300706448428
200 326926597264
201 355364629260
202 386203227437
203 419638401891
204 455883029523
205 495165541766
206 537733848781
207 583853998451
208 633814519648
209 687925076239
210 746521272981
211 809963310413
212 878641319493
213 952974031020
214 1033414689618
215 1120449773393
216 1214605549195
217 1316446859434
218 1426584408758
219 1545673644475
220 1674422848223
221 1813592164483
222 1964002586263
223 2126535165505
224 2302141016136
225 2491840754408
226 2696735626363
227 2918007260052
228 3156930044793
229 3414871256894
230 3693304861666
231 3993812092793
232 4318096832236
233 4667986767383
234 5045450531947
235 5452599544645
236 5891707148594
237 6365211262360
238 6875735742947
239 7426094034769
240 8019313019149
241 8658637830306
242 9347558524222
243 10089816267630
244 10889433151558
245 11750720031502
246 12678309863609
247 13677167462473
248 14752626827647
249 15910403138954
250 17156634544057
251 18497896803879
252 19941250084021
253 21494256663534
254 23165033390554
255 24962272942016
256 26895302622103
257 28974109784576
258 31209407754000
259 33612666039320
260 36196184312172
261 38973128147764
262 41957612038560
263 45164741562448
264 48610706550556
265 52312830630203
266 56289675871796
267 60561100804648
268 65148377949547
269 70074261628266
270 75363119986493
271 81041014007490
272 87135845905728
273 93677450971883
274 100697764357236
275 108230927677726
276 116313476485997
277 124984463720099
278 134285670534316
279 144261748983492
280 154960459107442
281 166432833655196
282 178733444707988
283 191920593501838
284 206056610382021
285 221208073219443
286 237446144837777
287 254846824084281
288 273491325418370
289 293466367097674
290 314864598313792
291 337784929571199
292 362333013281589
293 388621622196934
294 416771190144911
295 446910244983574
296 479176017116744
297 513714934314754
298 550683306432457
299 590247890521986
300 632586661258578
301 677889455679900
302 726358840145339
303 778210845273266
304 833675941407362
305 892999875828240
306 956444770222302
307 1024290073577190
308 1096833796972470
309 1174393597317633
310 1257308166453070
311 1345938462976582
312 1440669274775947
313 1541910618134447
314 1650099495343154
315 1765701482735837
316 1889212707429678
317 2021161648846962
318 2162111361623691
319 2312661517974177
320 2473450907307248
321 2645159750251915
322 2828512508954706
323 3024280507623333
324 3233285091659848
325 3456400593590767
326 3694557884045649
327 3948747726792256
328 4220024769448007
329 4509511336959301
330 4818401915776490
331 5147967440816277
332 5499560333558505
333 5874619344324505
334 6274675211653138
335 6701356129532566
336 7156394103557448
337 7641631120821201
338 8159026287682384
339 8710662789505166
340 9298755904572313
341 9925660851702199
342 10593881786185015
343 11306080644661710
344 12065087241870228
345 12873909235390180
346 13735743455603141
347 14653987127930852
348 15632250584165257
349 16674369895761720
350 17784421132558028
351 18966734579055925
352 20225910725571009
353 21566836260248345
354 22994701999532578
355 24515020870919219
356 26133648014313140
357 27856800996016076
358 29691082339040344
359 31643502237601241
360 33721503804691102
361 35932988587346439
362 38286344853846543
363 40790476245322859
364 43454833461739082
365 46289446425135645
366 49304959765329636
367 52512668913117109
368 55924559833559923
369 59553349516249697
370 63412530455007318
371 67516416057054421
372 71880190425563069
373 76519959269162236
374 81452805608348416
375 86696846834010555
376 92271297029097028
377 98196530900175711
378 104494153485056735
379 111187071763659426
380 118299572610992863
381 125857402986167994
382 133887857087131327
383 142419866120127206
384 151484095721525845
385 161113046423345522
386 171341162529179092
387 182204944518509403
388 193743070697080633
389 205996522924627450
390 219008722509444149
391 232825670799824764
392 247496100959165606
393 263071635135689324
394 279606953937339402
395 297159972088568141
396 315792027628783509
397 335568078178429326
398 356556912112470110
399 378831367796419729
400 402468569236747602
401 427550170912900396
402 454162620685936949
403 482397433144586313
404 512351482864189480
405 544127309510462543
406 577833444882904128
407 613584753381925513
408 651502796651979754
409 691716213416390787
410 734361125958872603
411 779581563774245321
412 827529916593411643
413 878367406791101625
414 932264594178238803
415 989401902651047775
416 1049970182550640461
417 1114171297641788554
418 1182218751474269103
419 1254338341449702662
420 1330768856324388940
421 1411762804861338703
422 1497587192396350886
423 1588524332392706894
424 1684872710854376412
425 1786947890010252950
426 1895083470315181091
427 2009632096493343746
428 2130966527927951376
429 2259480758405732357
430 2395591206865098714
431 2539737963415758157
432 2692386113711151458
433 2854027125175882725
434 3025180319703089891
435 3206394415528046052
436 3398249164533331990
437 3601357066873460571
438 3816365190923218153
439 4043957079595838144
440 4284854772908750724
441 4539820926972516008
442 4809661061286097542
443 5095225913624145887
444 5397413936539826154
445 5717173913859375785
446 6055507733486270978
447 6413473293956984774
448 6792187583524102601
449 7192829908261212047
450 7616645310591505841
451 8064948153774480390
452 8539125916569909450
453 9040643172636401908
454 9571045801904325381
455 10131965407500226634
456 10725123988693663437
457 11352338842462757596
458 12015527747618380504
459 12716714403098276434
460 13458034178093846517
461 14241740144649007895
462 15070209454380794497
463 15945950029006991817
464 16871607630614650319
465 17849973280416653940
466 18883991096532142006
467 19976766518637444065
468 21131574994957721865
469 22351871098590876684
470 23641298153940938258
471 25003698339443686448
472 26443123353068015730
473 27963845606040513966
474 29570370037402632568
475 31267446514198337551
476 33060082916496253252
477 34953558871485175658
478 36953440242944778650
479 39065594339896430774
480 41296205958364887587
481 43651794219765106590
482 46139230328065417276
483 48765756209104438840
484 51539004163069609762
485 54467017493575712958
486 57558272253881935502
487 60821700073971137736
488 64266712219309318399
489 67903224845537117020
490 71741685610997313559
491 75793101612177583717
492 80069068815916136194
493 84581802954613853042
494 89344172071194632588
495 94369730681588542428
496 99672755755398910280
497 105268284484498172542
498 111172154055226837557
499 117401043396402560063
500 123972517135036533403
501 130905071734963332850
502 138218184067810961406
503 145932362395147023940
504 154069200030155348826
505 162651431662012470698
506 171702992631788937271
507 181249081148147774330
508 191316223753804809331
509 201932344037016883440
510 213126834922992581191
511 224930634546475980183
512 237376306066300848897
513 250498121431234894685
514 264332149485950477714
515 278916348435752474202
516 294290663089235142158
517 310497126908187724908
518 327579969316783146961
519 345585728311567980116
520 364563368859889597534
521 384564407142190991699
522 405643041164360955208
523 427856287811379791594
524 451264126910242612005
525 475929652391289179052
526 501919231161234106338
527 529302669797260085049
528 558153389724574914146
529 588548611009620090850
530 620569545484605304831
531 654301599361221387243
532 689834586107002808657
533 727262949771042722705
534 766685999595215897464
535 808208156129977836485
536 851939209758940424845
537 897994591887509226797
538 946495659773650714436
539 997569995296593049077
540 1051351718721696782112
541 1107981817802557304378
542 1167608493365647594896
543 1230387521769013972863
544 1296482635474909008066
545 1366065922184103821735
546 1439318243874466417534
547 1516429676254136989155
548 1597599970083488727036
549 1683039034945758959025
550 1772967447041816882261
551 1867616981666234185593
552 1967231172071892108803
553 2072065895466067349569
554 2182389987988476285479
555 2298485889509297136532
556 2420650320253380031208
557 2549194990194034717039
558 2684447343391880870032
559 2826751338338824088549
560 2976468266666730334053
561 3133977611409907268490
562 3299677947381168061959
563 3473987884993292791721
564 3657347060303360031397
565 3850217172769459240068
566 4053083073734075077963
567 4266453907297749480723
568 4490864306854937978933
569 4726875649147836206328
570 4975077369390317124809
571 5236088339529739680059
572 5510558313503681963592
573 5799169441793015702455
574 6102637859460155578635
575 6421715350231402325177
576 6757191091173187035173
577 7109893480804759149086
578 7480692055589977451058
579 7870499497962927250446
580 8280273741257570136181
581 8711020175039708511009
582 9163793956676727824640
583 9639702433021305606391
584 10139907678550966053899
585 10665629154255111579955
586 11218146494162623874503
587 11798802424258299911291
588 12409005821281130467938
589 13050234916654380851853
590 13724040653693530940933
591 14432050203892949768331
592 15175970651148243056812
593 15957592850320020579025
594 16778795469769782950129
595 17641549224937532997253
596 18547921313434150151244
597 19500080059446398447615
598 20500299778844581820984
599 21550965873589515291974
600 22654580167826960283623
601 23813766495142054370118
602 25031276550448498558134
603 26309996016945004797116
604 27652950982796672070434
605 29063314659025794114445
606 30544414414557381843489
607 32099739141056397749813
608 33732946964903714823314
609 35447873320209930499004
610 37248539401739951726242
611 39139161013029476901047
612 41124157830227225054029
613 43208163098456853493381
614 45396033783040457295621
615 47692861194033075075710
616 50103982108378193527791
617 52634990409945014021496
618 55291749273899614431874
619 58080403917652128003484
620 61007394947163759530765
621 64079472323022463479653
622 67303709977608988638319
623 70687521110131156582798
624 74238674193610159921700
625 77965309723186414064997
626 81875957742834920388359
627 85979556182687757141261
628 90285470047325316118548
629 94803511490326281892960
630 99543960818998263859985
631 104517588467957327832946
632 109735677989352773718713
633 115210050102095052654847
634 120953087852099225346554
635 126977762929931043136541
636 133297663202455459176047
637 139927021509273732907894
638 146880745785540388559461
639 154174450566748045386267
640 161824489942502132436280
641 169847992020114299022856
642 178262894970944742800524
643 187087984726041035160538
644 196342934400431213788177
645 206048345518857761619839
646 216225791129302318967351
647 226897860883893486782648
648 238088208181153104563600
649 249821599456595947293157
650 262123965723910831623396
651 275022456461831852416486
652 288545495957925302619962
653 302722842213225510799389
654 317585648528730355410722
655 333166527887309292400228
656 349499620262676082708263
657 366620662979463487470146
658 384567064267623853374774
659 403377980146618413887894
660 423094394795201515278748
661 443759204554711769967821
662 465417305735356845618076
663 488115686386966086797085
664 511903522218571136526620
665 536832276843061637869645
666 562955806547445223176547
667 590330469781048077872571
668 619015241579761887478329
669 649071833136193460225778
670 680564816752928062173259
671 713561756407838477862571
672 748133344189415820988786
673 784353542851820676716399
674 822299734770198282674330
675 862052877568560178373637
676 903697666725300981204201
677 947322705453253462701449
678 993020682186000220977242
679 1040888555994115459417756
680 1091027750292011808658523
681 1143544355188192749292200
682 1198549338871046409016892
683 1256158768414668820290474
684 1316494040431031010071556
685 1379682121987446507979902
686 1445855802252782375415075
687 1515153955328858686384264
688 1587721814770809786368763
689 1663711260293620355951276
690 1743281117212413525040489
691 1826597469158033155858149
692 1913833984663071104270086
693 2005172258208076311699380
694 2100802166374759891056656
695 2200922239748324652489820
696 2305740051271833029922895
697 2415472621751688713596368
698 2530346843278058822060543
699 2650599921321202209499929
700 2776479836333664119809660
701 2908245825686558229956852
702 3046168886841691278995185
703 3190532302660828251171627
704 3341632189831788848817506
705 3499778071392065753562530
706 3665293474414249600591221
707 3838516553920195800699025
708 4019800744180031800307586
709 4209515438556617130822663
710 4408046699151196571097090
711 4615797997512597010529737
712 4833190987773836435859528
713 5060666313588976823411094
714 5298684450351416293333516
715 5547726584186414214776338
716 5808295529326343127780380
717 6080916685491702347340765
718 6366139037024492976678968
719 6664536195538375712813254
720 6976707487982028774833089
721 7303279092033596041128170
722 7644905220885152486904356
723 8002269359501641737442451
724 8376085554589475020744309
725 8767099760540006103563507
726 9176091243774233213461935
727 9603874047950085988939178
728 10051298522665952664986910
729 10519252918334618749297745
730 11008665050086063109050373
731 11520504033604159155076009
732 12055782095999458055374353
733 12615556464873548193898008
734 13200931338941413729288787
735 13813059943638933110453758
736 14453146675368403628577147
737 15122449338103844989545523
738 15822281476319489561076558
739 16554014808282698624242424
740 17319081764011285463193301
741 18118978132282909431082685
742 18955265821361301267194423
743 19829575738202581830086382
744 20743610791201749885123419
745 21699149021649788150188017
746 22698046869389835829276460
747 23742242578284264911104877
748 24833759747445263280687008
749 25974711034319177730845238
750 27167302016080102655531935
751 28413835215941466168785568
752 29716714301385896950836525
753 31078448461484007582928888
754 32501656970892533680082444
755 33989073948311306609052144
756 35543553317628735385293579
757 37168073980194936140548423
758 38865745207144526449943286
759 40639812260922874328892278
760 42493662255687614995738146
761 44430830266513379396025841
762 46455005697883496329689968
763 48570038922235143714080867
764 50779948199920892655057608
765 53088926892261295640789633
766 55501350980003364891712159
767 58021786899843106066814403
768 60654999712357504188554834
769 63405961615069129183910781
770 66279860815104364187802562
771 69282110776321558151287297
772 72418359856577686917004873
773 75694501351258270334041719
774 79116683960046158352299039
775 82691322694405445335877731
776 86425110244170676579127621
777 90325028822180557460779637
778 94398362506877120862630858
779 98652710103393001118281513
780 103095998544704216315135962
781 107736496855084799736943705
782 112582830699232951692199193
783 117643997541159546580835512
784 122929382438147736292445698
785 128448774495881171807248223
786 134212384012147304748314212
787 140230860337384467248870296
788 146515310481748360155479312
789 153077318499315587736672992
790 159928965681554296199297501
791 167082851593220589980329188
792 174552115985465376078017247
793 182350461622058910312626838
794 190492178056388547179701981
795 198992166398109824913714337
796 207865965110210862235085558
797 217129776878585334266309500
798 226800496598230840155518581
799 236895740521644787585596229
800 247433876617164027386927930
801 258434056186579922358807559
802 269916246793698906264789951
803 281901266557245117824776052
804 294410819864016927549808848
805 307467534560088608252009221
806 321095000680554064506700892
807 335317810780354649735195948
808 350161601931643811573473125
809 365653099455365909049283999
810 381820162457858040398160398
811 398691831245702733881350757
812 416298376695428582011499548
813 434671351657285437685225600
814 453843644475946005675600292
815 473849534713843134167547910
816 494724751166752964670250616
817 516506532264338305600771029
818 539233688952564252399580995
819 562946670158269317917125330
820 587687630940692590597345653
821 613500503438417632529641268
822 640431070725055215488235776
823 668527043690959806783110340
824 697838141073506657619618688
825 728416172762767318597445272
826 760315126515052353440482959
827 793591258211466720488238142
828 828303185804683868788449555
829 864511987102216773146882552
830 902281301540987316525039779
831 941677436113495182196051311
832 982769475612908711813739810
833 1025629397370362150704631801
834 1070332190665301318403263504
835 1116955980996181284077711265
836 1165582159406954707058413798
837 1216295517071790918114200498
838 1269184385349222649735104098
839 1324340781524502080053409671
840 1381860560468374104210912851
841 1441843572448689722421485854
842 1504393827341429408875028963
843 1569619665496602061214081156
844 1637633935525408057987278701
845 1708554179284685945280627055
846 1782502824346420585051491776
847 1859607384250515605129786500
848 1940000666851690651885615135
849 2023820991082646295329227269
850 2111212412469265288023058676
851 2202324957745826832836083313
852 2297314868932878629010255837
853 2396344857253618597719203983
854 2499584367280428278425236301
855 2607209851717485472926832608
856 2719405057242381555143865556
857 2836361321845118332242909265
858 2958277884121157216845476566
859 3085362204991898864633408225
860 3217830302345668632836791958
861 3355907099110343688587341929
862 3499826785289960954100449245
863 3649833194517167442817525139
864 3806180195696198973584898509
865 3969132100332172565625163516
866 4138964086167046955802737808
867 4315962637765405848797638160
868 4500426004719665348455076020
869 4692664678168941483465099941
870 4893001886354281319413485305
871 5101774109959573606257837214
872 5319331618018097092996894224
873 5546039025193409799458329042
874 5782275871276264809800391685
875 6028437223770282582903361852
876 6284934304474610108255383073
877 6552195141005320261356890074
878 6830665244235514502448174342
879 7120808312670286698796323504
880 7423106964813830922966819001
881 7738063500625050086756066881
882 8066200693202283938135151442
883 8408062611879951931880597661
884 8764215477967542723352555625
885 9135248554406902615044868942
886 9521775070675041968845405872
887 9924433184308801707242169105
888 10343886980482894238145306314
889 10780827511125837389044510422
890 11235973875117673420529566243
891 11710074341170550320033090587
892 12203907515057135268254879409
893 12718283552913518650597981499
894 13254045422412020634642453847
895 13812070213665851052494950632
896 14393270501801555288394201105
897 14998595763206940934302572426
898 15629033847541785102506502365
899 16285612507676008992993324702
900 16969400989805658964859847531
901 17681511686080476303114890048
902 18423101852168994126793746249
903 19195375392277063158027796275
904 19999584714234858060811292802
905 20837032657364398713622321509
906 21709074495946291177910747148
907 22617120021208931747003904554
908 23562635704878174207648853293
909 24547146947438131910940917456
910 25572240414377237440390919053
911 26639566463815107146412592979
912 27750841669038556773551728229
913 28907851439605958572277550739
914 30112452744821978920353991815
915 31366576943525715891840667335
916 32672232724288908580976117777
917 34031509160272776821439644794
918 35446578883157316056606310104
919 36919701380720493092566709180
920 38453226422822538425183181059
921 40049597620726775430036164117
922 41711356124879595090138499919
923 43441144466462008965640474691
924 45241710548230803679207311244
925 47115911790371750656822039754
926 49066719437308415646304260876
927 51097223031630252830103428494
928 53210635061541417066559758911
929 55410295788468763332106233765
930 57699678261723152290851908464
931 60082393527363385137220159771
932 62562196038686976805442974672
933 65142989276046717402799430782
934 67828831583987527159390206406
935 70623942233993856725981503578
936 73532707721455648538664114296
937 76559688305779205274994363324
938 79709624802910936024562680742
939 82987445639884559517302285560
940 86398274181369602845196475293
941 89947436338567741097069767398
942 93640468471198321008432261715
943 97483125593711171130880541340
944 101481389897289181212160767539
945 105641479599630043487677578877
946 109969858134952705135966350099
947 114473243697133394504720188984
948 119158619149366371260959736341
949 124033242314238685810347338519
950 129104656658635178961845806257
951 134380702388421506069315268358
952 139869527968419285606189282684
953 145579602083759230339866895645
954 151519726059306715338283505846
955 157699046754469191551047223385
956 164127069951348852970035330497
957 170813674254865326720434561415
958 177769125524175908679494979974
959 185004091855432081025989543809
960 192529659136666150452635755304
961 200357347196366609704901213151
962 208499126568112133586985824143
963 216967435894456402466743809878
964 225775199994127598802671680169
965 234935848617490479597440576045
966 244463335916155362989096339101
967 254372160653568768128025261904
968 264677387184426427026563163506
969 275394667231771032439166704609
970 286540262491717716771816726520
971 298131068096848404496138591749
972 310184636970476940544917939243
973 322719205105167186809795718920
974 335753717800133042682997959413
975 349307856893417827214188040333
976 363402069026089528363063065335
977 378057594977051587450208213838
978 393296500108507015055741307494
979 409141705963578437851335537990
980 425617023059131108916589965144
981 442747184918419821774014920530
982 460557883389839174434897224610
983 479075805299747646032922463037
984 498328670489116856411572174639
985 518345271285574086950683194319
986 539155513464318379882694897545
987 560790458753342136040830682677
988 583282368940443274032805489790
989 606664751641609378817725466884
990 630972407792559576890425266128
991 656241480927481581743688590451
992 682509508311367829031052861546
993 709815473994773010216746269094
994 738199863862355746807958809876
995 767704722749164377436321076447
996 798373713701353858670601361586
997 830252179460809883789314200709
998 863387206256083492268834110827
999 897827689985034388054702726696
1000 933624404877723008811705095742