0 1
1 1
2 2
3 3
4 4
5 6
6 9
7 12
8 17
9 23
10 30
11 40
12 53
13 68
14 88
15 113
16 143
17 181
18 228
19 284
20 354
21 439
22 541
23 665
24 815
25 993
26 1208
27 1465
28 1769
29 2132
30 2563
31 3070
32 3671
33 4379
34 5209
35 6185
36 7329
37 8663
38 10223
39 12041
40 14153
41 16609
42 19459
43 22755
44 26571
45 30979
46 36059
47 41915
48 48654
49 56392
50 65279
51 75468
52 87131
53 100477
54 115729
55 133133
56 152986
57 175604
58 201339
59 230607
60 263858
61 301588
62 344381
63 392866
64 447744
65 509824
66 579988
67 659212
68 748618
69 849428
70 963000
71 1090876
72 1234747
73 1396482
74 1578200
75 1782220
76 2011110
77 2267760
78 2555341
79 2877356
80 3237737
81 3640793
82 4091288
83 4594539
84 5156385
85 5783265
86 6482351
87 7261511
88 8129419
89 9095703
90 10170931
91 11366731
92 12695989
93 14172831
94 15812797
95 17633059
96 19652442
97 21891624
98 24373417
99 27122808
100 30167224
101 33536858
102 37264772
103 41387206
104 45944006
105 50978759
106 56539208
107 62677756
108 69451695
109 76923710
110 85162522
111 94243193
112 104247789
113 115266145
114 127396331
115 140745453
116 155430631
117 171579611
118 189331795
119 208839439
120 230268498
121 253799898
122 279631055
123 307976966
124 339071846
125 373170982
126 410552204
127 451517912
128 496397413
129 545548815
130 599361600
131 658259502
132 722702999
133 793192497
134 870271963
135 954532087
136 1046614312
137 1147215321
138 1257091119
139 1377062049
140 1508018406
141 1650925604
142 1806830486
143 1976868262
144 2162269119
145 2364366047
146 2584603508
147 2824545753
148 3085886615
149 3370460243
150 3680251621
151 4017408715
152 4384255842
153 4783306830
154 5217280183
155 5689115592
156 6201990479
157 6759338774
158 7364871408
159 8022596947
160 8736844915
161 9512291093
162 10353983301
163 11267370211
164 12258332679
165 13333215746
166 14498864324
167 15762661812
168 17132569867
169 18617172427
170 20225723362
171 21968195687
172 23855335913
173 25898722649
174 28110827533
175 30505082089
176 33095949870
177 35899001599
178 38930997456
179 42209975648
180 45755345053
181 49587986225
182 53730360145
183 58206622100
184 63042745690
185 68266656010
186 73908369604
187 80000146324
188 86576652423
189 93675132133
190 101335593559
191 109601008011
192 118517520201
193 128134675350
194 138505662727
195 149687572591
196 161741673521
197 174733709411
198 188734213329
199 203818845597
200 220068755742
201 237570965189
202 256418779104
203 276712226809
204 298558528044
205 322072593847
206 347377562095
207 374605364626
208 403897335953
209 435404863557
210 469290077053
211 505726586927
212 544900273524
213 587010123306
214 632269124666
215 680905223902
216 733162339064
217 789301444796
218 849601729691
219 914361823816
220 983901111319
221 1058561129893
222 1138707055619
223 1224729289241
224 1317045146965
225 1416100654311
226 1522372461466
227 1636369883697
228 1758637066532
229 1889755295866
230 2030345458100
231 2181070650553
232 2342638965182
233 2515806451606
234 2701380261446
235 2900221999146
236 3113251287595
237 3341449551480
238 3585864047211
239 3847612149324
240 4127885898580
241 4427956843736
242 4749181189939
243 5093005260577
244 5460971309429
245 5854723698307
246 6276015450482
247 6726715220896
248 7208814702492
249 7724436481766
250 8275842390587
251 8865442377324
252 9495803915048
253 10169661999558
254 10889929766099
255 11659709746595
256 12482305828348
257 13361235948360
258 14300245551614
259 15303321882239
260 16374709149430
261 17518924602855
262 18740775597122
263 20045377694845
264 21438173852289
265 22924954777779
266 24511880523326
267 26205503362616
268 28012792059675
269 29941157599823
270 31998480448594
271 34193139457774
272 36534042504960
273 39030658945513
274 41693054015106
275 44531925284719
276 47558641264675
277 50785282315979
278 54224683991091
279 57890482919722
280 61797165423044
281 65960119000542
282 70395686829338
283 75121225486747
284 80155166068296
285 85517078867407
286 91227741861645
287 97309213208318
288 103784907949029
289 110679679205585
290 118019904107986
291 125833574691356
292 134150394089909
293 143001878311019
294 152421463872366
295 162444621680877
296 173108977488775
297 184454439261200
298 196523331895601
299 209360539686910
300 223013656935641
301 237533147208403
302 252972511715757
303 269388467275669
304 286841134455134
305 305394236435037
306 325115309152645
307 346075923407976
308 368351919575646
309 392023655574539
310 417176268893035
311 443899953421520
312 472290251861605
313 502448364636633
314 534481476186603
315 568503099550447
316 604633440310913
317 642999780935037
318 683736886572210
319 726987433556967
320 772902461826964
321 821641852500785
322 873374832065114
323 928280504585426
324 986548413400811
325 1048379133983899
326 1113984899620697
327 1183590261618715
328 1257432785996513
329 1335763788585858
330 1418849110546384
331 1506969936558366
332 1600423657949248
333 1699524783089401
334 1804605897688635
335 1916018677622011
336 2034134957014471
337 2159347854635767
338 2292072961671220
339 2432749594051511
340 2581842112883131
341 2739841316548482
342 2907265908188957
343 3084664042676514
344 3272614957230575
345 3471730690004051
346 3682657891401332
347 3906079732961760
348 4142717918844606
349 4393334805434652
350 4658735634689806
351 4939770887087939
352 5237338760570806
353 5552387782014519
354 5885919558039085
355 6238991672565995
356 6612720738709164
357 7008285612912196
358 7426930779914592
359 7869969917348522
360 8338789649156514
361 8834853497764075
362 9359706045219428
363 9914977313962808
364 10502387378724864
365 11123751221390701
366 11780983841198661
367 12476105633574710
368 13211248051320548
369 13988659562490172
370 14810711920339125
371 15679906761231590
372 16598882547114036
373 17570421870337253
374 18597459139217773
375 19683088663564991
376 20830573160726120
377 22043352703423491
378 23325054131635476
379 24679500952259516
380 26110723751161228
381 27622971143342194
382 29220721288640750
383 30908694001400149
384 32691863483853892
385 34575471714868143
386 36565042526893963
387 38666396405498385
388 40885666047984542
389 43229312719033187
390 45704143443057997
391 48317329075381871
392 51076423296017574
393 53989382571863748
394 57064587135866796
395 60310863033654117
396 63737505290494354
397 67354302254534055
398 71171561174552138
399 75200135073178786
400 79451450980036858
401 83937539591930308
402 88671066430330351
403 93665364570383380
404 98934469018776714
405 104493152821391299
406 110356964986186610
407 116542270310370287
408 123066291205050171
409 129947151615684346
410 137203923140836764
411 144856673456508563
412 152926517159133569
413 161435669145174391
414 170407500650741075
415 179866598081253090
416 189838824766784483
417 200351385785026018
418 211432896001304818
419 223113451481586670
420 235424704441622406
421 248399941903923744
422 262074168241747195
423 276484191797561038
424 291668715773170927
425 307668433597308297
426 324526128986014387
427 342286780922172042
428 360997673790486406
429 380708512915131583
430 401471545759820424
431 423341689061495304
432 446376662181356235
433 470637126971195181
434 496186834466171264
435 523092778729487822
436 551425358190656562
437 581258544834147721
438 612670061611637240
439 645741568469507577
440 680558857400618262
441 717212056948132844
442 755795846610182320
443 796409681614047121
444 839158028550021118
445 884150612378989172
446 931502675350577594
447 981335248393282046
448 1033775435565140406
449 1088956712179657627
450 1147019237249748651
451 1208110180923352508
452 1272384067614307568
453 1340003135564115508
454 1411137713605366496
455 1485966615931835319
456 1564677555716852591
457 1647467578461511238
458 1734543515993431527
459 1826122462078560410
460 1922432270653929836
461 2023712077734044503
462 2130212848091214539
463 2242197947861812062
464 2359943744281555993
465 2483740233807246576
466 2613891699941123071
467 2750717402132369271
468 2894552297192224259
469 3045747794725926354
470 3204672548151314191
471 3371713282944468568
472 3547275663828678951
473 3731785202698957809
474 3925688209154715382
475 4129452785599437074
476 4343569868952794470
477 4568554321112139129
478 4804946070398311383
479 5053311306319347703
480 5314243730089853693
481 5588365863455094451
482 5876330418481231101
483 6178821731091658749
484 6496557261255801762
485 6830289162864643173
486 7180805926462100571
487 7548934098144860471
488 7935540078088877658
489 8341532002314041956
490 8767861711461428738
491 9215526810523156237
492 9685572823639132235
493 10179095448259850113
494 10697242913162727282
495 11241218445007461025
496 11812282848325674128
497 12411757204054173679
498 13041025691946049241
499 13701538542431814556
500 14394815123746026601
501 15122447170390176484
502 15886102159272565489
503 16687526840142123439
504 17528550927223016460
505 18411090959262920075
506 19337154335521505848
507 20308843535554623250
508 21328360530996592291
509 22398011397899019856
510 23520211138557714088
511 24697488722152437765
512 25932492353928176606
513 27227994983069757277
514 28586900059867145236
515 30012247553226873555
516 31507220240064810779
517 33075150278620085492
518 34719526078249438367
519 36443999478804977423
520 38252393253269785324
521 40148708947914580532
522 42137135074854668927
523 44222055672533407426
524 46408059250325530295
525 48699948134151410421
526 51102748230725672694
527 53621719228819213273
528 56262365256703739583
529 59030446015776644071
530 61931988411219692733
531 64973298701439312577
532 68160975188973802078
533 71501921476521373573
534 75003360312754992050
535 78672848053650320971
536 82518289766149210846
537 86547955002126080523
538 90770494271823535387
539 95194956247163584432
540 99830805726635716446
541 104687942394818462191
542 109776720410993501715
543 115107968862775428791
544 120693013122212083760
545 126543697143395947826
546 132672406742281993325
547 139092093901138069176
548 145816302141846091241
549 152859193014142339911
550 160235573746840123501
551 167960926112103134380
552 176051436554950425396
553 184524027642381596130
554 193396390888798390394
555 202687021016784807010
556 212415251714800296481
557 222601292955923995980
558 233266269944481846329
559 244432263760201664736
560 256122353772457881790
561 268360661900208392807
562 281172398796400502063
563 294583912038914828648
564 308622736413547435286
565 323317646378111684085
566 338698710800455801943
567 354797350067063246390
568 371646395662942088757
569 389280152327699717277
570 407734462897065246362
571 427046775943676349543
572 447256216335672613385
573 468403658836560480735
574 490531804874948893773
575 513685262618082288535
576 537910630488647112074
577 563256584270114039146
578 589773967951882991112
579 617515888471752149286
580 646537814519751377298
581 676897679574147034938
582 708655989347471535191
583 741875933827774447271
584 776623504107914849661
585 812967614203651522884
586 850980228069557514494
587 890736492030370885002
588 932314872854331208016
589 975797301704362339081
590 1021269324212628717083
591 1068820256934054684799
592 1118543350444876817219
593 1170535959363180829224
594 1224899719579700028529
595 1281740732998946282407
596 1341169760102990552918
597 1403302420662953905433
598 1468259402936538911007
599 1536166681703709483212
600 1607155745506963697658
601 1681363833477568949841
602 1758934182144626851669
603 1840016282639959406513
604 1924766148728591299560
605 2013346596112031381884
606 2105927533469686781344
607 2202686265722611667381
608 2303807810023386831373
609 2409485224996307369317
610 2519919953773263816362
611 2635322181392725797547
612 2755911207152143153124
613 2881915832527911362238
614 3013574765301796756785
615 3151137040558454158448
616 3294862459245443689188
617 3445022045014957466882
618 3601898520095378485852
619 3765786800970866450833
620 3936994514678394437030
621 4115842536564130032830
622 4302665550374824044133
623 4497812631594937598442
624 4701647854976695938498
625 4914550927248169171042
626 5136917846023849365319
627 5369161585983118560037
628 5611712813424555307210
629 5865020630348215017635
630 6129553349263949232786
631 6405799299971580232761
632 6694267669608331900207
633 6995489377310452341073
634 7310017984889536233126
635 7638430644979682442691
636 7981329088169432603981
637 8339340650692525928153
638 8713119344313898495085
639 9103346970112190320342
640 9510734277927407981120
641 9936022173312355747546
642 10379982973899145441619
643 10843421717167643257205
644 11327177521681150514584
645 11832125003936109803978
646 12359175753057309858523
647 12909279865657981164253
648 13483427543275510352816
649 14082650754888400370420
650 14708024967118625918055
651 15360670944825876918157
652 16041756624906508289107
653 16752499066220394966392
654 17494166478683543006171
655 18268080334683409397166
656 19075617566097522226477
657 19918212850324405420907
658 20797360988869196786714
659 21714619382164807521380
660 22671610604453265078251
661 23670025082701228871635
662 24711623883678691163535
663 25798241613490857669595
664 26931789434020387849816
665 28114258200910704869032
666 29347721727901271993388
667 30634340182512845839232
668 31976363618274922039783
669 33376135648889228024831
670 34836097269932490653686
671 36358790833919003523968
672 37946864184769116553993
673 39603074957964001308639
674 41330295052910128952464
675 43131515284289247419134
676 45009850219431629585971
677 46968543209022236525471
678 49010971618731654839431
679 51140652269656633946161
680 53361247095759056405448
681 55676569026807723023473
682 58090588105654879077069
683 60607437849019277516222
684 63231421861300321638357
685 65967020711313957417096
686 68818899082220869631487
687 71791913205311784079367
688 74891118588723850157664
689 78121778052586600060811
690 81489370082536523171532
691 84999597513996477664462
692 88658396560090469715381
693 92471946196556502779229
694 96446677917530924525495
695 100589285876607524661017
696 104906737428124378366746
697 109406284084201851996386
698 114095472903646909531034
699 118982158329452779227042
700 124074514492260008873528
701 129381047997805654143036
702 134910611217072800492157
703 140672416098563756666002
704 146676048522857865755551
705 152931483220380053546467
706 159449099274100019180482
707 166239696229705257559476
708 173314510836645096844572
709 180685234444328797671307
710 188364031078679492244972
711 196363556225198677823102
712 204696976345684407695755
713 213377989156771365655224
714 222420844699524144206835
715 231840367230417700450926
716 241651977965182396790001
717 251871718708176878045975
718 262516276401181877232741
719 273603008626783291906750
720 285149970102835335540993
721 297175940205866001797958
722 309700451562709067576418
723 322743819751121396709754
724 336327174151673341109651
725 350472489994785342663170
726 365202621648427621737764
727 380541337193704260249196
728 396513354337310032959652
729 413144377711680446815382
730 430461137615555015027074
731 448491430249643038147938
732 467264159504122783726502
733 486809380356821610877368
734 507158343943118755178064
735 528343544360887152520145
736 550398767276148790383840
737 573359140397562398941497
738 597261185890396128697089
739 622142874803264479394722
740 648043683583631235913321
741 675004652760902176042706
742 703068447878856472394039
743 732279422762197461521317
744 762683685205145830191578
745 794329165173255295388211
746 827265685613006372817095
747 861545035967232298204497
748 897221048498057047724510
749 934349677522782978739415
750 972989081672059813498073
751 1013199709283702460783470
752 1055044387049707281677529
753 1098588412038350312593074
754 1143899647217742141871384
755 1191048620611867902981657
756 1240108628224963234772839
757 1291155840875074139641292
758 1344269415082826350908360
759 1399531608166794778395060
760 1457027897702422565095357
761 1516847105507198828181635
762 1579081526320771660929464
763 1643827061354855892777379
764 1711183356894200749105584
765 1781253948136519090030852
766 1854146408466155596867272
767 1929972504363394236450091
768 2008848356158684604278472
769 2090894604848711473600538
770 2176236585199151082965775
771 2265004505367161373923364
772 2357333633285151673277247
773 2453364490056180223217258
774 2553243050620446552252703
775 2657120951961791166329589
776 2765155709132898552812481
777 2877510939388033254653796
778 2994356594722635207240562
779 3115869203129971990107303
780 3242232118896305649232787
781 3373635782267694040692266
782 3510277988833624943160218
783 3652364168985190433754746
784 3800107677818464436973742
785 3953730095867163148906341
786 4113461541062562738233028
787 4279540992333038173074742
788 4452216625270488087242677
789 4631746160306341555597224
790 4818397223855822133286257
791 5012447722905691230267832
792 5214186233537827044879443
793 5423912403898737488353614
794 5641937372143476528414896
795 5868584199901455497935329
796 6104188321831336966795799
797 6349098011852591735792737
798 6603674866662414067917292
799 6868294307168551657547376
800 7143346098491240506256623
801 7429234889210868109651946
802 7726380770562249070921189
803 8035219856301513636755722
804 8356204883997611854319456
805 8689805838527354934342920
806 9036510598580782196797274
807 9396825607012489992288941
808 9771276565904422356956625
809 10160409157236536436241806
810 10564789790093755720797945
811 10985006375370748598343079
812 11421669128970356898415628
813 11875411404526989667859586
814 12346890556723033061555651
815 12836788836304350303842004
816 13345814317940301105887716
817 13874701862114443797036100
818 14424214112274242587888487
819 14995142528511736462091756
820 15588308459092286119066361
821 16204564251195252977238973
822 16844794402278834314366261
823 17509916753531337436233647
824 18200883726922980633525451
825 18918683607425920144384809
826 19664341872025682550493418
827 20438922567204594360047757
828 21243529736637211816440590
829 22079308900899232880960185
830 22947448591054989919477503
831 23849181938054449677363120
832 24785788319938762490466786
833 25758595068923882774396172
834 26768979240504709132640722
835 27818369446797648670486503
836 28908247756417581853701251
837 30040151663265981438618024
838 31215676126690514089704752
839 32436475685562920820051167
840 33704266648911431595170370
841 35020829365836522410753158
842 36388010577534574313221622
843 37807725854353052710893814
844 39281962120903304602914716
845 40812780272363086362283388
846 42402317885210606310566482
847 44052792025745318875205789
848 45766502159868067981656910
849 47545833167714579846145682
850 49393258466861886735750714
851 51311343247957164159884627
852 53302747826752831451110472
853 55370231116670751203126465
854 57516654226162121777229443
855 59744984185278351317578832
856 62058297806021998480221911
857 64459785681205935692520326
858 66952756326713414164080719
859 69540640472221870332947715
860 72226995505629299997324398
861 75015510076604036382825462
862 77910008864867005058254957
863 80914457519010200517398703
864 84032967771856453967887786
865 87269802738573763523330142
866 90629382403972766676545920
867 94116289305638590509681516
868 97735274419778564681796674
869 101491263256905379612951725
870 105389362174721481872214330
871 109434864915825093003467987
872 113633259378121496764220124
873 117990234626095454443563094
874 122511688151382078868095445
875 127203733391364533495912925
876 132072707514827844815861148
877 137125179484009255091394752
878 142367958402707238530890346
879 147808102160443911135312438
880 153452926383019447514587917
881 159310013700152651887681557
882 165387223341269405212891232
883 171692701070880727831670810
884 178234889475385070459193835
885 185022538613535605368716210
886 192064717043233176973246154
887 199370823237739642149019492
888 206950597404855058718997508
889 214814133723066053269975502
890 222971893009152218714411671
891 231434715832233078828237508
892 240213836089750548617365452
893 249320895061411468580586479
894 258767955957662271588831917
895 268567518979833744813491962
896 278732536909678784790222638
897 289276431246630643140505027
898 300213108911734075146431276
899 311556979537847703842746496
900 323322973366383494170472450
901 335526559771539212267832366
902 348183766433692862537517737
903 361311199184365115452564716
904 374926062545917451712750464
905 389046180989940966282594212
906 403690020939104341834971509
907 418876713538070284259440048
908 434626078219958608084445532
909 450958647095732094424502919
910 467895690194809174852321321
911 485459241586166406416199654
912 503672126410184616494961699
913 522557988852516563793336826
914 542141321092312067549201256
915 562447493258229923873466402
916 583502784426795714089328717
917 605334414698832007796805803
918 627970578390893708491349597
919 651440478379887655867044397
920 675774361640343398793939005
921 701003556015132645190178861
922 727160508261809680939426452
923 754278823418165473311291235
924 782393305532055729487698230
925 811539999802079409011187095
926 841756236177250678181532055
927 873080674465425688071598563
928 905553351001917550801304539
929 939215726931460227352935827
930 974110738158466531576073404
931 1010282847022368962741638163
932 1047778095756736523392464347
933 1086644161792828046989434578
934 1126930414970274899873194608
935 1168687976719685345706006775
936 1211969781284131551749998280
937 1256830639048720427392168405
938 1303327302049763537322622160
939 1351518531737451625149411453
940 1401465169068408293603775115
941 1453230207007047666150592347
942 1506878865517295039870145447
943 1562478669128950351619878251
944 1620099527165784522707648676
945 1679813816725361320539325424
946 1741696468503575268629050524
947 1805825055559992430282881289
948 1872279885123278771346741614
949 1941144093539303558495461647
950 2012503744467916257244271275
951 2086447930437918157408762551
952 2163068877873388081832562098
953 2242462055708278746338613957
954 2324726287710080478825822562
955 2409963868637356037230936627
956 2498280684360088275495383121
957 2589786336076055615477349644
958 2684594268760863044679571802
959 2782821903993813162304258718
960 2884590777306507275843090116
961 2990026680205925488383908354
962 3099259807028752041337024321
963 3212424906788892979375059801
964 3329661440185482734071703021
965 3451113741944199891568132055
966 3576931188670415807213755063
967 3707268372398588620618888922
968 3842285280028395549412554718
969 3982147478844374235529221838
970 4127026308322325711796382052
971 4277099078432423771471946109
972 4432549274655884894854149044
973 4593566769939186360813166423
974 4760348043817184906546848169
975 4933096408944091688719981739
976 5112022245279108966407919674
977 5297343242181637728598529978
978 5489284648679331539227363955
979 5688079532180908536219002688
980 5893969045914549420686450384
981 6107202705381913310343529263
982 6328038674127304686301567841
983 6556744059131332796258970083
984 6793595216148529556552359341
985 7038878065318843291133228193
986 7292888417393713937686077436
987 7555932310928571354327410691
988 7828326360805093121945379951
989 8110398118458423144460706304
990 8402486444196799154807953783
991 8704941892013678055701551522
992 9018127107305495351406841760
993 9342417237921661649743159997
994 9678200358987298622081654719
995 10025877911953562601437194955
996 10385865158345210310525380182
997 10758591648690342616453818672
998 11144501707133033728027243562
999 11544054932245830385349222671
1000 11957726714575904319187358315