0 1
1 1
2 2
3 3
4 4
5 6
6 10
7 13
8 17
9 24
10 33
11 43
12 58
13 75
14 98
15 127
16 161
17 205
18 262
19 328
20 414
21 517
22 641
23 794
24 982
25 1205
26 1475
27 1803
28 2197
29 2664
30 3230
31 3896
32 4693
33 5640
34 6754
35 8077
36 9647
37 11479
38 13637
39 16178
40 19152
41 22624
42 26695
43 31426
44 36948
45 43372
46 50819
47 59463
48 69490
49 81068
50 94458
51 109918
52 127730
53 148236
54 171848
55 198947
56 230072
57 265760
58 306622
59 353387
60 406878
61 467932
62 537626
63 617092
64 707583
65 810585
66 927754
67 1060818
68 1211913
69 1383339
70 1577635
71 1797688
72 2046807
73 2328479
74 2646862
75 3006450
76 3412214
77 3869867
78 4385739
79 4966656
80 5620584
81 6356201
82 7183103
83 8112093
84 9155233
85 10325661
86 11638321
87 13109589
88 14757598
89 16602642
90 18667293
91 20976026
92 23556638
93 26439649
94 29658607
95 33250928
96 37258053
97 41725302
98 46703409
99 52248019
100 58420467
101 65288816
102 72928151
103 81420586
104 90857627
105 101339605
106 112976811
107 125891166
108 140216931
109 156101037
110 173706249
111 193210800
112 214810560
113 238721229
114 265179816
115 294445544
116 326804362
117 362569443
118 402083897
119 445724790
120 493905617
121 547078123
122 605739239
123 670432221
124 741751514
125 820348882
126 906937468
127 1002295927
128 1107278200
129 1222816619
130 1349929953
131 1489732543
132 1643441945
133 1812385689
134 1998016270
135 2201917791
136 2425818048
137 2671603568
138 2941332185
139 3237245292
140 3561789739
141 3917630255
142 4307669676
143 4735072002
144 5203282877
145 5716050514
146 6277459437
147 6891952484
148 7564361979
149 8299946524
150 9104424922
151 9984010766
152 10945463415
153 11996125229
154 13143972435
155 14397671949
156 15766635682
157 17261077370
158 18892091155
159 20671713774
160 22613003284
161 24730128376
162 27038456493
163 29554645213
164 32296760963
165 35284381365
166 38538719910
167 42082765064
168 45941417922
169 50141638808
170 54712630767
171 59686002941
172 65095964846
173 70979541544
174 77376792489
175 84331042724
176 91889160838
177 100101820819
178 109023804336
179 118714333050
180 129237408609
181 140662174550
182 153063344624
183 166521611299
184 181124113170
185 196964945921
186 214145690763
187 232775978576
188 252974137708
189 274867834030
190 298594789770
191 324303565027
192 352154372508
193 382319946843
194 414986531618
195 450354867788
196 488641291594
197 530078927705
198 574918937931
199 623431854286
200 675909072426
201 732664369305
202 794035576527
203 860386389767
204 932108271149
205 1009622481542
206 1093382335693
207 1183875516672
208 1281626609506
209 1387199837015
210 1501201943400
211 1624285273997
212 1757151168404
213 1900553467296
214 2055302334979
215 2222268374745
216 2402386977573
217 2596662969816
218 2806175691588
219 3032084288032
220 3275633447046
221 3538159564314
222 3821097272748
223 4125986412042
224 4454479614481
225 4808350240475
226 5189500949601
227 5599972904651
228 6041955525338
229 6517796898225
230 7030015056290
231 7581309820220
232 8174575563385
233 8812914886095
234 9499653118508
235 10238353801841
236 11032835401863
237 11887188904772
238 12805796728043
239 13793352962151
240 14854884861710
241 15995775756615
242 17221789722091
243 18539097605553
244 19954304951185
245 21474481846135
246 23107194609144
247 24860539577950
248 26743179394657
249 28764381347533
250 30934058421295
251 33262813142875
252 35761984154731
253 38443695818831
254 41320911391752
255 44407489275042
256 47718243164182
257 51269006222158
258 55076699224820
259 59159403139392
260 63536436784736
261 68228439037279
262 73257456619217
263 78647037679658
264 84422331190493
265 90610192721565
266 97239297442829
267 104340259837497
268 111945761390750
269 120090686587506
270 128812267326318
271 138150236534703
272 148146992098192
273 158847770533906
274 170300832052925
275 182557657541954
276 195673157689198
277 209705895314726
278 224718322325869
279 240777030840729
280 257953020541642
281 276321983019507
282 295964603572873
283 316966881907360
284 339420473607099
285 363423052010943
286 389078693144173
287 416498284882574
288 445799961100215
289 477109562758046
290 510561128395670
291 546297413930959
292 584470445181887
293 625242104759458
294 668784754605899
295 715281896845734
296 764928876215419
297 817933624356422
298 874517450374335
299 934915880142142
300 999379546255731
301 1068175132273264
302 1141586375630472
303 1219915130113610
304 1303482493686363
305 1392630005146536
306 1487720912535943
307 1589141518310830
308 1697302607095670
309 1812640957877402
310 1935620948232235
311 2066736255552690
312 2206511659636909
313 2355504953424208
314 2514308969757191
315 2683553727451718
316 2863908706661733
317 3056085260608257
318 3260839169992548
319 3478973349455585
320 3711340716664178
321 3958847229378478
322 4222455103790971
323 4503186224016754
324 4802125751947960
325 5120425950233446
326 5459310232717535
327 5820077450706032
328 6204106432676996
329 6612860791385126
330 7047894011484164
331 7510854835148976
332 8003492965124187
333 8527665097816268
334 9085341310042229
335 9678611818807823
336 10309694132774679
337 10980940619415371
338 11694846514132768
339 12454058390025062
340 13261383119885648
341 14119797357443833
342 15032457564213010
343 16002710614594326
344 17034105015032354
345 18130402764393505
346 19295591897968472
347 20533899752506017
348 21849806989152924
349 23248062419149479
350 24733698680751363
351 26312048806344791
352 27988763736827356
353 29769830834940705
354 31661593449126655
355 33670771588889510
356 35804483777577646
357 38070270138123946
358 40476116788440429
359 43030481617684552
360 45742321514930568
361 48621121133627634
362 51676923281333063
363 54920361012669063
364 58362691529064240
365 62015831983189661
366 65892397287023091
367 70005740036980616
368 74369992677476846
369 79000112012328565
370 83911926203464438
371 89122184390901219
372 94648609070498554
373 100509951383883926
374 106726049485176174
375 113317890136373086
376 120307673719497967
377 127718882848981628
378 135576354771558370
379 143906357763282828
380 152736671746769603
381 162096673338942842
382 172017425582952105
383 182531772614013380
384 193674439515882845
385 205482137652505282
386 217993675776694496
387 231250077205260779
388 245294703402294082
389 260173384311069911
390 275934555784769847
391 292629404501187257
392 310312020769710820
393 329039559627661403
394 348872410686385370
395 369874377188824329
396 392112864755696464
397 415659080341631499
398 440588241952217852
399 466979799664575771
400 494917668570939329
401 524490474271437079
402 555791811564131584
403 588920517035637479
404 623980956295889590
405 661083326596249898
406 700343975663861510
407 741885737598926347
408 785838286712849222
409 832338510256345873
410 881530901038532047
411 933567970940455946
412 988610686442300780
413 1046828927307141918
414 1108401969608427385
415 1173518994378327959
416 1242379623223345551
417 1315194482266744730
418 1392185795919190017
419 1473588012017206036
420 1559648459931156917
421 1650628043359697113
422 1746801969618948436
423 1848460517262205586
424 1955909844042869544
425 2069472837291371463
426 2189490008862251018
427 2316320436955454077
428 2450342757236640811
429 2591956205731100775
430 2741581716185063316
431 2899663074674028097
432 3066668134355493402
433 3243090093453462782
434 3429448839722016837
435 3626292364714383805
436 3834198251459316026
437 4053775239270025862
438 4285664869570778104
439 4530543216872042097
440 4789122709235892908
441 5062154042695004490
442 5350428194434406160
443 5654778539718847082
444 5976083077767214954
445 6315266772092048011
446 6673304011100835261
447 7051221194935518552
448 7450099454962145422
449 7871077512566494697
450 8315354684205507934
451 8784194040074353579
452 9278925724117984445
453 9800950443372859948
454 10351743135177747221
455 10932856821128103561
456 11545926657044404827
457 12192674188756949834
458 12874911823995205281
459 13594547531034256076
460 14353589775453126542
461 15154152706819122757
462 15998461607643663648
463 16888858617644733093
464 17827808746992790962
465 18817906192722878888
466 19861880973392205369
467 20962605897686842151
468 22123103883390067046
469 23346555644021793999
470 24636307761302754527
471 25995881162295825689
472 27428980021222108871
473 28939501106791767680
474 30531543596835910604
475 32209419383190494003
476 33977663890895050520
477 35841047436722077226
478 37804587153520690209
479 39873559507992232874
480 42053513440770040682
481 44350284159190607121
482 46770007614606377619
483 49319135697381504512
484 52004452184597752606
485 54833089477012066475
486 57812546163471794415
487 60950705452965755602
488 64255854516407669017
489 67736704781989175475
490 71402413230365172527
491 75262604737953388831
492 79327395518830164927
493 83607417718266668183
494 88113845213470867912
495 92858420679432713006
496 97853483980892337839
497 103112001954132416506
498 108647599645197997072
499 114474593074483554883
500 120608023600927048222
501 127063693962160983331
502 133858206070999745382
503 141009000652191233468
504 148534398807181638212
505 156453645598977674665
506 164786955753513959201
507 173555561578067585363
508 182781763202457453000
509 192488981253451189311
510 202701812077823974408
511 213446085635152635368
512 224748926187078022554
513 236638815915239960049
514 249145661606802984713
515 262300864552660161590
516 276137393809986339537
517 290689862988138329171
518 305994610724279138165
519 322089785022330873745
520 339015431637526103107
521 356813586696931663348
522 375528373754944584473
523 395206105492273587473
524 415895390276546087776
525 437647243812188272978
526 460515206118426512224
527 484555464084885419512
528 509826979865525805736
529 536391625384016657124
530 564314323236178227527
531 593663194287621035041
532 624509712279171873938
533 656928865766576296634
534 690999327735682911221
535 726803633250333498436
536 764428365506503199714
537 803964350682591275423
538 845506861994452184255
539 889155833381913502554
540 935016083272696014206
541 983197548890413096648
542 1033815531594546753305
543 1086990953761677902501
544 1142850627741382497836
545 1201527537443869024455
546 1263161133141385059850
547 1327897640092313150512
548 1395890381624419999482
549 1467300117341615636815
550 1542295397149738450844
551 1621052931827685018616
552 1703757980902623306506
553 1790604758622823184783
554 1881796858857370713143
555 1977547699788352141273
556 2078080989301296503146
557 2183631212019691933007
558 2294444138971464927811
559 2410777360920310644244
560 2532900846441039929333
561 2661097525865320412303
562 2795663902276046865207
563 2936910690780509631064
564 3085163487347058829765
565 3240763468548086664004
566 3404068123612041537108
567 3575452020248462541251
568 3755307605776853083296
569 3944046045157506637225
570 4142098097592978089797
571 4349915033443923209046
572 4567969593280435189146
573 4796756990969398508860
574 5036795962784478496438
575 5288629864612433681599
576 5552827819420678782799
577 5829985917247778489286
578 6120728470078494889349
579 6425709324067743759671
580 6745613231688627488257
581 7081157286492225038318
582 7433092423284635347905
583 7802204986651420620302
584 8189318370888495345593
585 8595294734531234522112
586 9021036792816116607685
587 9467489691554424601483
588 9935642966049459663732
589 10426532588849175688142
590 10941243110292205972726
591 11480909895976518951652
592 12046721465463140817880
593 12639921936714542988987
594 13261813580963019143023
595 13913759492910710690531
596 14597186381376654025211
597 15313587485726925461045
598 16064525623659229939008
599 16851636376154244143599
600 17676631415657856931765
601 18541301983823544850879
602 19447522525418879395983
603 20397254485284207538271
604 21392550275533448815163
605 22435557420496805181298
606 23528522887228862591167
607 24673797609745831302125
608 25873841215508527225135
609 27131226963032842365523
610 28448646899896514227859
611 29828917250809003547537
612 31274984045826859994543
613 32789928999233296314572
614 34376975650053399641523
615 36039495775645233038234
616 37781016090302920747316
617 39605225241318459977245
618 41515981115481968960360
619 43517318469559110914729
620 45613456898864639166202
621 47808809158652288419368
622 50107989853675870616374
623 52515824511930891523245
624 55037359059268842633935
625 57677869712291848188614
626 60442873307678226264467
627 63338138086859812845537
628 66369694955783462975872
629 69543849240327055127759
630 72867192958814235039570
631 76346617633987123726634
632 79989327667746445536853
633 83802854302954260147850
634 87795070197631421864857
635 91974204637953517397100
636 96348859417566385327430
637 100928025411911301458328
638 105721099877464146946126
639 110737904507052983130490
640 115988704273742182791712
641 121484227097140440388236
642 127235684367417140329006
643 133254792363803630804585
644 139553794605906091564574
645 146145485177765860125691
646 153043233066291424639903
647 160261007557433844908866
648 167813404735298450501092
649 175715675131288421188926
650 183983752572352875388399
651 192634284279464953180681
652 201684662269606920256325
653 211153056116767634632510
654 221058447129779210286664
655 231420664007243930214841
656 242260420032321609747962
657 253599351872763904954841
658 265460060054321414379095
659 277866151178488018322378
660 290842281958503482201042
661 304414205150621216399592
662 318608817460854969292333
663 333454209510749290549495
664 348979717949203430037926
665 365215979800990883838442
666 382194989146378652950116
667 399950156230174819061327
668 418516369102611694553878
669 437930057898708928916092
670 458229261867190153767579
671 479453699264619952052086
672 501644840235210018393443
673 524845982801730100066448
674 549102332098141978523839
675 574461082979959212305695
676 600971506153960115379631
677 628685037974716151783205
678 657655374061471249163049
679 687938566895238359229111
680 719593127562559228643369
681 752680131819209555053088
682 787263330654268498570361
683 823409265542376464585411
684 861187388579711476313547
685 900670187707244655994550
686 941933317233180997276667
687 985055733875163008537943
688 1030119838551862475334664
689 1077211624162975010773864
690 1126420829606401799765265
691 1177841100291579869968022
692 1231570155418498729516846
693 1287709962302930598437494
694 1346366918039861867266308
695 1407652038809008465577747
696 1471681157138672611748202
697 1538575127457084962291541
698 1608460040273768069645185
699 1681467445347371718848525
700 1757734584210935128972616
701 1837404632440587264568896
702 1920626952069357206122124
703 2007557354564070210032655
704 2098358374800247455979893
705 2193199556487530679514910
706 2292257749516494470349405
707 2395717419716750071819194
708 2503770971536046748070518
709 2616619084170686580903900
710 2734471061698984273764717
711 2857545197791753858428281
712 2986069155596979059477699
713 3120280363419884029652234
714 3260426426844638896474653
715 3406765557969965976908993
716 3559567022457960208762753
717 3719111605123537738529385
718 3885692094821184191013684
719 4059613789416050334305793
720 4241195021658023332951577
721 4430767706810254120602296
722 4628677912917753705875476
723 4835286454637129881348114
724 5050969511585442930553873
725 5276119272204477585183596
726 5511144604176560183675801
727 5756471752469476660207435
728 6012545066131084324601328
729 6279827754998917208113907
730 6558802677536603708296892
731 6849973161057213389973525
732 7153863855643847637332801
733 7471021623129985663150233
734 7802016462556318962069146
735 8147442473577128010952177
736 8507918859347842586596771
737 8884090970486254279032826
738 9276631391763060155195916
739 9686241073243131045335846
740 10113650507667155479448470
741 10559620955934204790138335
742 11024945722619493606608573
743 11510451483538154851443497
744 12016999667445381130758600
745 12545487894045951950596279
746 13096851470572024862590334
747 13672064949277236671303454
748 14272143748287871261046240
749 14898145838348098404261698
750 15551173498096278486828775
751 16232375140613240916183483
752 16942947214091357801768989
753 17684136179585297662188361
754 18457240568921832617362436
755 19263613125966999717671246
756 20104663034574529699930064
757 20981858236669973483763495
758 21896727844060485576372212
759 22850864647700950664330526
760 23845927728293393020987200
761 24883645172248425431945221
762 25965816897195172407351411
763 27094317591389909222666856
764 28271099771543738361637388
765 29498196963766211355320325
766 30777727012505287712928462
767 32111895522554473949581035
768 33502999439395763342698352
769 34953430773352428700638397
770 36465680473238997393861812
771 38042342455417152110868567
772 39686117794396319149023196
773 41399819081356441906332120
774 43186374957218324626111376
775 45048834827144371568716069
776 46990373763619790875334107
777 49014297605541744808362038
778 51124048261032067945886919
779 53323209221988212335345350
780 55615511298697539132241386
781 58004838583162451991987453
782 60495234650118484932758691
783 63090909005074771131153962
784 65796243789067000735940698
785 68615800750187267864349300
786 71554328492343747815064236
787 74616770012106538799901654
788 77808270534914669632997381
789 81134185662353782575072819
790 84600089842665156614795970
791 88211785177114877558377849
792 91975310575337863265740771
793 95896951273275856025279249
794 99983248727851940753610395
795 104241010903067342511688378
796 108677322962770174001686687
797 113299558385930899570705556
798 118115390520866501356554513
799 123132804595485585658365661
800 128360110201280644237650475
801 133805954269472263258540185
802 139479334558414428910929803
803 145389613672100821842913626
804 151546533630370274004106464
805 157960231012196499145548465
806 164641252694263680866072113
807 171600572207876599326411063
808 178849606738133123808787551
809 186400234790198894694714725
810 194264814548470270223427285
811 202456202955393494527341027
812 210987775537726666754743401
813 219873447009087809174625028
814 229127692678728871908932931
815 238765570697612917288697138
816 248802745174051714378243183
817 259255510192385232720729518
818 270140814769454458834084419
819 281476288784936247117467950
820 293280269922975654184097576
821 305571831663968742374293999
822 318370812366819272653380369
823 331697845483518115100656859
824 345574390949476355441717851
825 360022767794684047323266242
826 375066188022468900044970099
827 390728791804394632902553534
828 407035684041669836699885347
829 424012972345337513295588289
830 441687806489485235361562765
831 460088419393758654997545159
832 479244169693579991171413366
833 499185585958670353845915609
834 519944412622753459242356489
835 541553657689681593694856958
836 564047642283675373830301658
837 587462052113910113670553346
838 611833990926317220158505400
839 637202036018201806788167705
840 663606295894111487055530585
841 691088470144329944011585453
842 719691911630415844955626209
843 749461691065366918794041965
844 780444664079265140443639274
845 812689540864655524718213927
846 846246958499432734282547949
847 881169556048661295024262045
848 917512052550541022658532029
849 955331327995654162677836522
850 994686507412700346142175494
851 1035639048178144243519291485
852 1078252830671574531511251144
853 1122594252403107303348133697
854 1168732325743867750544146200
855 1216738779395456829982438923
856 1266688163739361557658378218
857 1318657960212504163815577064
858 1372728694860553679425239831
859 1428984056226250764967412083
860 1487511017735829450296215694
861 1548399964752665341471634109
862 1611744826473547136157899361
863 1677643212849464017470895552
864 1746196556719534339263168452
865 1817510261353679775700708083
866 1891693853606882116846757399
867 1968861142895356287987063833
868 2049130386212743177746676166
869 2132624459412478281277902298
870 2219471034990837628618253068
871 2309802766613811786012818952
872 2403757480639922217882284984
873 2501478374900383240113479077
874 2603114225007639677320657128
875 2708819598473286129063788727
876 2818755076926711479520057232
877 2933087486736525228449252581
878 3051990138347923166240215776
879 3175643074660652728841463040
880 3304233328784158321745828926
881 3437955191518837647699669153
882 3577010488925137574969335636
883 3721608870355478638526100519
884 3871968107337736689144000674
885 4028314403713245559952188626
886 4190882717447034578599739944
887 4359917094543296266937154971
888 4535671015514912200083681658
889 4718407754872268744164830383
890 4908400754113588789965261827
891 5105934008716611635639544001
892 5311302469649693672670855162
893 5524812459939298511603585855
894 5746782106850420614234789092
895 5977541790256765910455588483
896 6217434607798520373601676592
897 6466816857447298905584567480
898 6726058538120410051412281928
899 6995543869009923035974530629
900 7275671828316211747956318133
901 7566856712100705674283175663
902 7869528713998530125543607925
903 8184134526558599076307855919
904 8511137965006567694956805657
905 8851020614254890311658497572
906 9204282500014099118247737964
907 9571442784890356189592426196
908 9953040490386373052932345597
909 10349635245755976915353815685
910 10761808064696972500043273310
911 11190162150902542935025087808
912 11635323733528296290551231504
913 12097942933670241363990031740
914 12578694662988512188137338740
915 13078279555652603222976601159
916 13597424934826277263934240515
917 14136885814954214707155298474
918 14697445941157939813195112380
919 15279918867095642354238559480
920 15885149072689266865842406457
921 16514013123172725188984508758
922 17167420870967363384760755949
923 17846316701944941711406742349
924 18551680827694432066364967492
925 19284530625466968878716529268
926 20045922027533374882047032901
927 20836950961750894242834103388
928 21658754845200178285404621010
929 22512514132820257705725112017
930 23399453923038280293905519667
931 24320845622462277715734987676
932 25278008671779232290205221021
933 26272312335077332815492326626
934 27305177554890630324533925390
935 28378078875346421342209265580
936 29492546435880696300501249295
937 30650168038074995684723377949
938 31852591288259118587626054221
939 33101525818618435212908556861
940 34398745589642180042756006763
941 35746091276850157792402941563
942 37145472744839900337200660816
943 38598871611804593538295926440
944 40108343907784173757762522138
945 41676022830028006463565488623
946 43304121598967642302163336061
947 44994936418422436673435906626
948 46750849543789464288067214523
949 48574332462102311997792099080
950 50467949187981144999848421537
951 52434359679639074283939507400
952 54476323379257476091180723247
953 56596702882195695505719551597
954 58798467739658685747804118618
955 61084698399609777437674170973
956 63458590290885126088474364479
957 65923458055641648086038928902
958 68482739935451631825602361854
959 71140002316544907652409431255
960 73898944439893697079038817312
961 76763403282036264507067425370
962 79737358612743493346894141754
963 82824938235847743314406480929
964 86030423419776068514653262659
965 89358254524560338998359901334
966 92813036832335279359039154929
967 96399546588582192540048536794
968 100122737261631456447680038540
969 103987746028201058618299549258
970 107999900493021776955801745164
971 112164725650882430986471512201
972 116487951099721244495211424764
973 120975518513692113388987378645
974 125633589385447805561796512198
975 130468553047206190436662434205
976 135487034980500878741078484779
977 140695905424864524998386712075
978 146102288296051904006974822074
979 151713570424781128624287012631
980 157537411127355448663987232675
981 163581752119925396322686333533
982 169854827788562077897352386867
983 176365175827737615117508574617
984 183121648260248596965013601732
985 190133422852073414543978181039
986 197410014936125028831298185929
987 204961289659347596294067088451
988 212797474668109005225476584446
989 220929173247362318208971937996
990 229367377929587963824130097278
991 238123484590085882828902213047
992 247209307045763334204897710666
993 256637092175160353203503644297
994 266419535578071602232088733802
995 276569797793761251480487251431
996 287101521097427288474889029008
997 298028846895254026100289784522
998 309366433739097317013446898136
999 321129475982576878597597177196
1000 333333723101105008407527179898