0 1
1 2
2 3
3 4
4 5
5 8
6 11
7 16
8 21
9 26
10 34
11 44
12 58
13 74
14 93
15 116
16 143
17 178
18 221
19 272
20 332
21 402
22 487
23 588
24 710
25 854
26 1021
27 1216
28 1444
29 1714
30 2031
31 2400
32 2826
33 3318
34 3888
35 4552
36 5322
37 6208
38 7224
39 8388
40 9726
41 11264
42 13028
43 15044
44 17339
45 19952
46 22930
47 26324
48 30186
49 34568
50 39530
51 45144
52 51498
53 58690
54 66818
55 75988
56 86315
57 97938
58 111019
59 125736
60 142280
61 160846
62 181657
63 204968
64 231074
65 260302
66 292994
67 329520
68 370287
69 415760
70 466470
71 522992
72 585950
73 656008
74 733902
75 820464
76 916619
77 1023390
78 1141867
79 1273236
80 1418797
81 1579998
82 1758457
83 1955932
84 2174331
85 2415710
86 2682324
87 2976676
88 3301522
89 3659880
90 4055006
91 4490424
92 4969989
93 5497942
94 6078953
95 6718104
96 7420892
97 8193266
98 9041713
99 9973348
100 10995960
101 12118020
102 13348684
103 14697864
104 16176340
105 17795896
106 19569383
107 21510752
108 23635086
109 25958690
110 28499277
111 31276128
112 34310227
113 37624312
114 41242940
115 45192660
116 49502227
117 54202886
118 59328543
119 64915880
120 71004502
121 77637144
122 84860056
123 92723348
124 101281288
125 110592518
126 120720253
127 131732680
128 143703439
129 156712176
130 170844986
131 186194736
132 202861482
133 220952994
134 240585517
135 261884540
136 284985457
137 310034160
138 337187626
139 366614792
140 398497609
141 433032166
142 470429726
143 510917604
144 554740178
145 602160132
146 653460017
147 708943908
148 768938906
149 833796576
150 903894454
151 979637944
152 1061462577
153 1149836398
154 1245262262
155 1348279976
156 1459468651
157 1579449502
158 1708889131
159 1848503008
160 1999058840
161 2161379862
162 2336348365
163 2524909844
164 2728077755
165 2946938560
166 3182656695
167 3436479500
168 3709742526
169 4003875592
170 4320409695
171 4660984280
172 5027354555
173 5421398816
174 5845126283
175 6300686016
176 6790376799
177 7316657714
178 7882158767
179 8489691688
180 9142261515
181 9843079438
182 10595577171
183 11403422056
184 12270532533
185 13201093982
186 14199575532
187 15270748816
188 16419708421
189 17651893684
190 18973111012
191 20389556820
192 21907842126
193 23535019352
194 25278611757
195 27146644508
196 29147676759
197 31290834946
198 33585848080
199 36043086392
200 38673603151
201 41489178996
202 44502367943
203 47726545088
204 51175957472
205 54865779094
206 58812170430
207 63032341444
208 67544617083
209 72368505642
210 77524771287
211 83035512384
212 88924245797
213 95215996080
214 101937388557
215 109116746532
216 116784194487
217 124971769016
218 133713537849
219 143045725764
220 153006846203
221 163637839044
222 174982216691
223 187086220660
224 199998989055
225 213772733720
226 228462925661
227 244128489484
228 260832009378
229 278639949240
230 297622887693
231 317855766376
232 339418150357
233 362394501382
234 386874467112
235 412953189656
236 440731634029
237 470316935352
238 501822763087
239 535369703600
240 571085664954
241 609106307534
242 649575502114
243 692645813428
244 738479008083
245 787246588328
246 839130356152
247 894323012912
248 953028795587
249 1015464148624
250 1081858429753
251 1152454651868
252 1227510267075
253 1307297998168
254 1392106720392
255 1482242391672
256 1578029030267
257 1679809742976
258 1787947810486
259 1902827837636
260 2024856971118
261 2154466183894
262 2292111625499
263 2438276041816
264 2593470273619
265 2758234842184
266 2933141626608
267 3118795632108
268 3315836848961
269 3524942207702
270 3746827640961
271 3982250263460
272 4232010675586
273 4496955390890
274 4777979388293
275 5076028795868
276 5392103720026
277 5727261233714
278 6082618531463
279 6459356252768
280 6858721975865
281 7282033891420
282 7730684673140
283 8206145562696
284 8709970679214
285 9243801556904
286 9809371914707
287 10408512670912
288 11043157223981
289 11715347021416
290 12427237430872
291 13181103919136
292 13979348546466
293 14824506792888
294 15719254743564
295 16666416661104
296 17668972963026
297 18730068614904
298 19853021949559
299 21041333935284
300 22298697927373
301 23629009937602
302 25036379447514
303 26525140779688
304 28099865044271
305 29765372690592
306 31526746707091
307 33389346515080
308 35358822588800
309 37441131824824
310 39642553684667
311 41969707150388
312 44429568549357
313 47029490304338
314 49777220654390
315 52680924377904
316 55749204552671
317 58991125406256
318 62416236326793
319 66034597108368
320 69856804489188
321 73894020028332
322 78157999369945
323 82661122964156
324 87416428336527
325 92437643998960
326 97739225081054
327 103336390744808
328 109245163450096
329 115482410163666
330 122065885627619
331 129014277808668
332 136347255631340
333 144085519082122
334 152250851777601
335 160866176117544
336 169955611173497
337 179544533467688
338 189659640779144
339 200329019095552
340 211582212836991
341 223450298511374
342 235965961994512
343 249163579635000
344 263079303363498
345 277751149967358
346 293219094700654
347 309525169439448
348 326713565630995
349 344830742294392
350 363925539309597
351 384049296210048
352 405255976708327
353 427602299228880
354 451147873768489
355 475955345417396
356 502090544850198
357 529622646076514
358 558624331755410
359 589171966433392
360 621345778119387
361 655230048624770
362 690913313075784
363 728488568980960
364 768053495259952
365 809710681702390
366 853567869389217
367 899738202631380
368 948340492954243
369 999499495638386
370 1053346199351719
371 1110018129484376
372 1169659665874747
373 1232422375638816
374 1298465361796246
375 1367955628363228
376 1441068462618938
377 1517987835342088
378 1598906819902041
379 1684028031127000
380 1773564084847992
381 1867738079002462
382 1966784097225074
383 2070947735959088
384 2180486656231381
385 2295671161276322
386 2416784801179807
387 2544125005700264
388 2678003746480594
389 2818748229993938
390 2966701622692340
391 3122223809888348
392 3285692189887237
393 3457502504882008
394 3638069710197124
395 3827828883618648
396 4027236176703905
397 4236769810038632
398 4456931114408637
399 4688245619856512
400 4931264194688064
401 5186564236677112
402 5454750918902613
403 5736458492750504
404 6032351650623471
405 6343126950921110
406 6669514307972132
407 7012278549823084
408 7372221047011693
409 7750181415579140
410 8147039297606553
411 8563716222597448
412 9001177553184000
413 9460434518901280
414 9942546342046266
415 10448622459802096
416 10979824846860615
417 11537370442845680
418 12122533689032214
419 12736649179184372
420 13381114429666197
421 14057392774185332
422 14767016388623885
423 15511589451508128
424 16292791445923276
425 17112380609074070
426 17972197536094403
427 18874168944980964
428 19820311609655653
429 20812736468319114
430 21853652914572264
431 22945373279268436
432 24090317511553927
433 25291018067893016
434 26550125018076056
435 27870411377420196
436 29254778674781378
437 30706262766589378
438 32228039907718502
439 33823433090451092
440 35495918663061163
441 37249133239852026
442 39086880914995502
443 41013140793246604
444 43032074851354445
445 45148036144544528
446 47365577372833828
447 49689459822349324
448 52124662697475866
449 54676392860556280
450 57350094996777488
451 60151462222594160
452 63086447156555070
453 66161273471954728
454 69382447951563717
455 72756773065792208
456 76291360096772125
457 79993642831748898
458 83871391849867952
459 87932729427180864
460 92186145085748984
461 96640511814083636
462 101305102987556498
463 106189610018567424
464 111304160767174540
465 116659338743871214
466 122266203137524856
467 128136309703177412
468 134281732546132019
469 140715086840213464
470 147449552519299885
471 154498898982502040
472 161877510855055433
473 169600414849069554
474 177683307770419755
475 186142585719921520
476 194995374538501328
477 204259561547754082
478 213953828639398520
479 224097686769728044
480 234711511917806602
481 245816582568501780
482 257435118783502972
483 269590322925626992
484 282306422104405751
485 295608712414148712
486 309523605038966151
487 324078674302208832
488 339302707740418178
489 355225758284678512
490 371879198635640623
491 389295777922462584
492 407509680740010077
493 426556588662390638
494 446473744334311625
495 467300018245322896
496 489075978296271463
497 511843962272233054
498 535648153341266234
499 560534658703059128
500 586551591515892336
501 613749156234928442
502 642179737500196731
503 671897992718773124
504 702960948491987362
505 735428101044416904
506 769361520817006892
507 804825961392490356
508 841888972928018919
509 880621020277543032
510 921095605994340450
511 963389398411564132
512 1007582365005768025
513 1053757911255796864
514 1102003025217881713
515 1152408428047259284
516 1205068730706421399
517 1260082597109474048
518 1317552913961093114
519 1377586967557977272
520 1440296627831303033
521 1505798539920471960
522 1574214323580608027
523 1645670780738030800
524 1720300111519329993
525 1798240139091581480
526 1879634543664525879
527 1964633106020184248
528 2053391960950517583
529 2146073860998482592
530 2242848450912245991
531 2343892553237349896
532 2449390465488254111
533 2559534269358884800
534 2674524152450639917
535 2794568743014765540
536 2919885458224173735
537 3050700866508725070
538 3187251064508776333
539 3329782069224431560
540 3478550225961323604
541 3633822632696839312
542 3795877581513566321
543 3965005017770544468
544 4141507017708884559
545 4325698285216423570
546 4517906668505152072
547 4718473697484005940
548 4927755142638306403
549 5146121596257045856
550 5373959076881610790
551 5611669657884451032
552 5859672121122315354
553 6118402636644664518
554 6388315469473884351
555 6669883714511375120
556 6963600060664003630
557 7269977585328745584
558 7589550580418164387
559 7922875411154277924
560 8270531408903412945
561 8633121799371541210
562 9011274667529911702
563 9405643960694564572
564 9816910531238953116
565 10245783220474801752
566 10692999985292672955
567 11159329069212287424
568 11645570219555266379
569 12152555952519661568
570 12681152868004625454
571 13232263016103165144
572 13806825317251235661
573 14405817038094522114
574 15030255325212122371
575 15681198798918998056
576 16359749209454595970
577 17067053157951538094
578 17804303884665944868
579 18572743127042033368
580 19373663050280348562
581 20208408253181384104
582 21078377852142302357
583 21985027646291903944
584 22929872366858135356
585 23914488013975781408
586 24940514284262014114
587 26009657092614243280
588 27123691191815890834
589 28284462893669026994
590 29493892895508531180
591 30753979216093337488
592 32066800245019167392
593 33434517909953986034
594 34859380966159726543
595 36343728412929110244
596 37889993041734949422
597 39500705121064290802
598 41178496223094124262
599 42926103197559319496
600 44746372298364132112
601 46642263468693333748
602 48616854790588173620
603 50673347105169349580
604 52815068809917414212
605 55045480839660651192
606 57368181838168419881
607 59786913527501330828
608 62305566282528773200
609 64928184918293181376
610 67658974698182668882
611 70502307571169544008
612 73462728646678408380
613 76544962915960775134
614 79753922229174036104
615 83094712537695320524
616 86572641411549587450
617 90193225842196393042
618 93962200341297556038
619 97885525346474960984
620 101969395945464543071
621 106220250930483922988
622 110644782195061784362
623 115249944486027278856
624 120042965523823598850
625 125031356504787518120
626 130222922999527011951
627 135625776262037234216
628 141248344964726374890
629 147099387375077676170
630 153188003990247860734
631 159523650646491372620
632 166116152120905001997
633 172975716243614592306
634 180112948539180358559
635 187538867416680430136
636 195264919928638991304
637 203302998119691361490
638 211665455986624667724
639 220365127072205947788
640 229415342716016036038
641 238829950986348120518
642 248623336318099452319
643 258810439882478576408
644 269406780715269941301
645 280428477631350174702
646 291892271954142843601
647 303815551089732060628
648 316216372976424487933
649 329113491441649030712
650 342526382499215386775
651 356475271621124778332
652 370981162019346718339
653 386065863974245599182
654 401752025247654569061
655 418063162619946094812
656 435023694591840676872
657 452658975293136591518
658 470995329642043180259
659 490060089800359560608
660 509881632971353524139
661 530489420588856018944
662 551914038947797306597
663 574187241328181784848
664 597341991666339758161
665 621412509829207732664
666 646434318549367675852
667 672444292080613976892
668 699480706635917217478
669 727583292671827932302
670 756793289085622449441
671 787153499393838887496
672 818708349963277557505
673 851503950368039843226
674 885588155948756518006
675 921010632652823142304
676 957822924237229477207
677 996078521918444316766
678 1035832936556789565174
679 1077143773465801077712
680 1120070809940232561148
681 1164676075599627322752
682 1211023935647775014799
683 1259181177151890048760
684 1309217098448987562333
685 1361203601790684593254
686 1415215289341523320589
687 1471329562649916073316
688 1529626725714964410518
689 1590190091776710961230
690 1653106093961835043543
691 1718464399921394241156
692 1786358030601949710811
693 1856883483296311500870
694 1930140859125219662744
695 2006233995106542383808
696 2085270600974015832503
697 2167362400913164518168
698 2252625280387832655444
699 2341179438236747013724
700 2433149544225740550763
701 2528664902247699839502
702 2627859619368949853180
703 2730872780927649797516
704 2837848631896851604171
705 2948936764732191972822
706 3064292313931772634720
707 3184076157543639305720
708 3308455125864389575439
709 3437602217580816643934
710 3571696823615139311392
711 3710924958943305549916
712 3855479502665113763984
713 4005560446614481489480
714 4161375152808098137687
715 4323138620040919665356
716 4491073759947510669281
717 4665411682859143719608
718 4846391993797856577218
719 5034263098960356560192
720 5229282523056740367783
721 5431717237881461030652
722 5641844002506835768152
723 5859949715502683695112
724 6086331779599444842330
725 6321298479226375250030
726 6565169371371130567108
727 6818275690222237461280
728 7080960766071625375028
729 7353580458970590218904
730 7636503607649325232894
731 7930112494227499161204
732 8234803325261282692145
733 8550986729690716885158
734 8879088274270402998270
735 9219548997086216391404
736 9572825959781152789034
737 9939392819134523149994
738 10319740418660519990820
739 10714377400914681358420
740 11123830841220003532210
741 11548646903548451538050
742 11989391519318438624815
743 12446651089894516497228
744 12921033213602035874229
745 13413167438096902151976
746 13923706038958793822172
747 14453324825405390588588
748 15002723974055332652037
749 15572628891698832071386
750 16163791108067082811073
751 16776989199624871874732
752 17413029745445115746700
753 18072748316259502080952
754 18757010497816073722610
755 19466712949712486702280
756 20202784500912811138960
757 20966187283196131793400
758 21757917903826886791258
759 22579008658779936745296
760 23430528787897860159587
761 24313585773403968172402
762 25229326683242032587573
763 26178939560762738972224
764 27163654862327463422511
765 28184746944452217533912
766 29243535602168601201903
767 30341387660334399948684
768 31479718619684078951732
769 32659994359468879807138
770 33883732898597580886971
771 35152506217252342000616
772 36467942141019523434445
773 37831726289643011941792
774 39245604092577426440261
775 40711382873590642398736
776 42230934006739441228737
777 43806195146118880229232
778 45439172531865310633404
779 47131943374974923315424
780 48886658323584307949252
781 50705544013446810870038
782 52590905705428559829270
783 54545130012941030059736
784 56570687722323096581144
785 58670136709284745190912
786 60846124954627045975006
787 63101393662558680530984
788 65438780485038365391485
789 67861222855685092475894
790 70371761436914376307904
791 72973543684078769538012
792 75669827530514844993064
793 78463985197526712169528
794 81359507133468068774017
795 84360006086220972868176
796 87469221313510149764208
797 90691022935636854910848
798 94029416435366180566535
799 97488547309856308376540
800 101072705879677727283968
801 104786332260135077991816
802 108634021500274274372398
803 112620528895133051468628
804 116750775476974203290360
805 121029853691427613741158
806 125463033264659937390575
807 130055767267889711534104
808 134813698385771038237396
809 139742665395380960408776
810 144848709862764401836620
811 150138083064216189984936
812 155617253139712455245657
813 161292912486143903704858
814 167171985398251397925502
815 173261635965420186887400
816 179569276232753169351356
817 186102574635115932847096
818 192869464713127250769195
819 199878154120358596620280
820 207137133931305405841880
821 214655188260001564341540
822 222441404199467138105961
823 230505182092507902675336
824 238856246144724104808257
825 247504655390935506644600
826 256460815026590545898317
827 265735488116099733238928
828 275339807690417460487387
829 285285289246592486402994
830 295583843662415883751138
831 306247790539716659353220
832 317289871990290092819527
833 328723266878892486178296
834 340561605538198798325749
835 352818984971096895373036
836 365509984556184338655588
837 378649682272841329495936
838 392253671462777215448289
839 406338078145488324648128
840 420919578905622230239695
841 436015419370818273925006
842 451643433299186844417637
843 467822062296201186575996
844 484570376181406095914817
845 501908094025998314915728
846 519855605883004280077502
847 538433995232472584143620
848 557665062164811770781666
849 577571347326139663060718
850 598176156650269149411373
851 619503586902737911230132
852 641578552063096571499679
853 664426810572501798711688
854 688074993474518797442608
855 712550633477922290515976
856 737882194971197500438617
857 764099105019383606545062
858 791231785374872416685259
859 819311685534775309594312
860 848371316878502809667308
861 878444287920264552442652
862 909565340712294009845001
863 941770388435733170372732
864 975096554217278296045785
865 1009582211210889828740336
866 1045267023985108608523309
867 1082191991257798095715292
868 1120399490021449583298438
869 1159933321103545643422928
870 1200838756207877344719174
871 1243162586484154225612984
872 1286953172674733942291709
873 1332260496888832463485610
874 1379136216056157224291528
875 1427633717113536207169488
876 1477808173979796789949375
877 1529716606375880741462562
878 1583417940548967541222128
879 1638973071961219062688820
880 1696444930005656441271530
881 1755898544813636354663838
882 1817401116220410544889802
883 1881022084957330841946412
884 1946833206141404098361737
885 2014908625135109453490694
886 2085324955851666403722125
887 2158161361583288296224212
888 2233499638432373983322535
889 2311424301428082440041182
890 2392022673413303411011254
891 2475384976789684144706996
892 2561604428211100579832996
893 2650777336318773398525620
894 2743003202614127434651677
895 2838384825568479389991056
896 2937028408071716348738008
897 3039043668325299182267438
898 3144543954288193659977522
899 3253646361787700822947272
900 3366471856410629676537176
901 3483145399293832359550416
902 3603796076936807844600400
903 3728557235162878451740356
904 3857566617359357633691853
905 3990966507131161063592112
906 4128903875506469316940679
907 4271530532837332799684992
908 4419003285542521833459653
909 4571484097844471147666792
910 4729140258656852725146614
911 4892144553784138109618680
912 5060675443599484855360668
913 5234917246372405869780272
914 5415060327422959487675871
915 5601301294284637164429916
916 5793843198063729747137977
917 5992895741188727263301618
918 6198675491749255782550673
919 6411406104630183050065512
920 6631318549652837633499181
921 6858651346941790114562176
922 7093650809742345380146058
923 7336571294920798137922408
924 7587675461386615051780652
925 7847234536683032211078570
926 8115528592000102400555381
927 8392846825871999737402724
928 8679487856828396773079887
929 8975760025277978029688714
930 9281981704910650910068545
931 9598481623913766972585592
932 9925599196306681280523980
933 10263684863707263097747280
934 10613100447853535986794696
935 10974219514213477583877984
936 11347427747026157043149860
937 11733123336127839694462838
938 12131717375927452851226988
939 12543634276906893605228380
940 12969312190033078765677640
941 13409203444480398593067858
942 13863774999074349264493816
943 14333508907879594022308324
944 14818902800368550391410035
945 15320470376619832133506254
946 15838741918009501462142468
947 16374264813872121048923856
948 16927604104623047972570445
949 17499343041848294834221394
950 18090083665883609465881204
951 18700447401420207509027556
952 19331075671690845500479320
953 19982630531806659711760920
954 20655795321832431496199390
955 21351275340205687392024712
956 22069798538123316747421635
957 22812116235538207152210072
958 23579003859427774870763988
959 24371261705016220069028812
960 25189715720652881153767993
961 26035218317070215748944332
962 26908649201766715547609240
963 27810916239282487381241168
964 28742956338158322719325761
965 29705736365392851769561184
966 30700254089236855699668568
967 31727539151189011157391996
968 32788654068083286344912800
969 33884695265184919724781400
970 35016794141239413896702729
971 36186118166447291183535400
972 37393872014366506935644101
973 38641298728774425153080408
974 39929680926552153748662525
975 41260342037685839997881568
976 42634647583512267505897676
977 44054006494369801485536808
978 45519872467850426511312191
979 47033745368884338260390388
980 48597172672925317682692201
981 50211750953542963706331654
982 51879127415766820950488820
983 53601001476567544092852720
984 55379126393901522826642931
985 57215310945787884031952040
986 59111421160930525919665187
987 61069382102442859266293196
988 63091179706279271204851356
989 65178862676025025366967656
990 67334544435745406784845887
991 69560405142645450319453672
992 71858693761343598931685897
993 74231730201616166287334824
994 76681907521524571570708084
995 79211694197894017922745676
996 81823636466170645000930797
997 84520360731744247526648830
998 87304576054885464350069413
999 90179076711509957788204060
1000 93146744832047573412294580