0 1
1 0
2 1
3 1
4 1
5 2
6 3
7 3
8 5
9 5
10 8
11 9
12 13
13 15
14 20
15 24
16 30
17 37
18 47
19 55
20 71
21 83
22 103
23 123
24 151
25 178
26 218
27 257
28 310
29 366
30 440
31 515
32 617
33 722
34 857
35 1003
36 1184
37 1380
38 1625
39 1889
40 2214
41 2570
42 3000
43 3472
44 4042
45 4669
46 5414
47 6244
48 7221
49 8303
50 9583
51 10998
52 12655
53 14502
54 16646
55 19035
56 21805
57 24890
58 28448
59 32420
60 36982
61 42068
62 47902
63 54404
64 61827
65 70120
66 79550
67 90073
68 102031
69 115356
70 130457
71 147298
72 166328
73 187535
74 211467
75 238115
76 268118
77 301530
78 339073
79 380840
80 427724
81 479832
82 538220
83 603107
84 675680
85 756275
86 846316
87 946222
88 1057683
89 1181299
90 1319023
91 1471644
92 1641515
93 1829613
94 2038708
95 2270130
96 2527070
97 2811235
98 3126452
99 3474794
100 3860804
101 4287132
102 4759071
103 5279940
104 5856041
105 6491420
106 7193520
107 7967409
108 8821787
109 9762883
110 10801059
111 11943822
112 13203426
113 14589119
114 16115232
115 17793046
116 19639548
117 21668288
118 23899334
119 26349148
120 29041276
121 31995577
122 35239920
123 38798051
124 42702818
125 46982865
126 51676696
127 56818666
128 62454240
129 68624287
130 75382379
131 82777399
132 90872167
133 99724987
134 109409821
135 119995840
136 131569976
137 144214540
138 158031395
139 173118199
140 189594692
141 207576259
142 227203427
143 248612856
144 271968978
145 297433342
146 325198751
147 355455513
148 388429485
149 424345098
150 463466360
151 506057522
152 552427551
153 602886831
154 657796541
155 717521519
156 782483235
157 853109907
158 929893786
159 1013336400
160 1104012185
161 1202508701
162 1309495253
163 1425659456
164 1551781392
165 1688664427
166 1837217052
167 1998377844
168 2173203549
169 2362789555
170 2568365249
171 2791207190
172 3032744534
173 3294464823
174 3578027534
175 3885164542
176 4217802668
177 4577955732
178 4967859523
179 5389854990
180 5846533955
181 6340615438
182 6875103364
183 7453152615
184 8078242448
185 8754032188
186 9484548167
187 10274031608
188 11127140707
189 12048786434
190 13044354788
191 14119529912
192 15280534368
193 16533942788
194 17886941674
195 19347129309
196 20922800673
197 22622733109
198 24456494278
199 26434216932
200 28566932483
201 30866329528
202 33345120000
203 36016781116
204 38895951535
205 41998161423
206 45340261265
207 48940134386
208 52817166999
209 56991942328
210 61486750187
211 66325267723
212 71533112191
213 77137502339
214 83167864223
215 89655473223
216 96634110887
217 104139694068
218 112210987760
219 120889214258
220 130218834924
221 140247139049
222 151025093338
223 162606918754
224 175051013537
225 188419511433
226 202779293386
227 218201527657
228 234762770292
229 252544496701
230 271634299590
231 292125404712
232 314117985341
233 337718663927
234 363041944088
235 390209711399
236 419352793550
237 450610453707
238 484132102980
239 520076788844
240 558615064341
241 599928487610
242 644211662595
243 691671744561
244 742530681735
245 797024732867
246 855406916991
247 917946564334
248 984931994536
249 1056670097111
250 1133489276695
251 1215739071944
252 1303793380796
253 1398050146108
254 1498934887497
255 1606900455027
256 1722430915684
257 1846041390100
258 1978282314789
259 2119739398290
260 2271038297096
261 2432844697506
262 2605869467725
263 2790868889287
264 2988650316302
265 3200072606935
266 3426052340340
267 3667564464391
268 3925649151893
269 4201412699444
270 4496035071192
271 4810771115364
272 5146958865708
273 5506021106624
274 5889474537458
275 6298931740565
276 6736111277468
277 7202840150906
278 7701064929862
279 8232854756093
280 8800413638535
281 9406084082616
282 10052360654631
283 10741894358524
284 11477507602180
285 12262199404467
286 13099161947669
287 13991786729933
288 14943682848229
289 15958684265067
290 17040870006047
291 18194572665759
292 19424400766029
293 20735248667857
294 22132321293279
295 23621145677395
296 25207598305225
297 26897918491676
298 28698738663069
299 30617099802050
300 32660484962295
301 34836837097543
302 37154596156585
303 39622719572809
304 42250723379723
305 45048705701081
306 48027392288585
307 51198163452276
308 54573104498732
309 58165036499342
310 61987572224451
311 66055151227653
312 70383101837024
313 74987681160499
314 79886143789137
315 85096787295932
316 90639028451636
317 96533454890468
318 102801909618363
319 109467549674428
320 116554939834152
321 124090119075284
322 132100704559053
323 140615966843622
324 149666945219370
325 159286532811586
326 169509604504230
327 180373113071671
328 191916231156948
329 204180459743457
330 217209785675607
331 231050804032886
332 245752892884576
333 261368351161914
334 277952592628127
335 295564301071803
336 314265645534766
337 334122454968463
338 355204457033548
339 377585474436348
340 401343689987549
341 426561867135204
342 453327644085452
343 481733781463097
344 511878488649287
345 543865701645261
346 577805445261777
347 613814144655221
348 652015027204736
349 692538471719885
350 735522454310567
351 781112939504347
352 829464375030965
353 880740129615937
354 935113041911675
355 992765910425537
356 1053892102451213
357 1118696101957821
358 1187394185181163
359 1260215032998076
360 1337400480309204
361 1419206200323673
362 1505902535687579
363 1597775262661492
364 1695126512992789
365 1798275626903136
366 1907560175392915
367 2023336912130518
368 2145982906978323
369 2275896607680008
370 2413499096766805
371 2559235275186322
372 2713575255733227
373 2877015682310358
374 3050081274487882
375 3233326297241678
376 3427336273039290
377 3632729618562203
378 3850159542115725
379 4080315865868019
380 4323927128332188
381 4581762612279087
382 4854634674392867
383 5143401001241482
384 5448967190149913
385 5772289258286404
386 6114376501397787
387 6476294283325561
388 6859167202352618
389 7264182191427702
390 7692592024564224
391 8145718761577281
392 8624957630435769
393 9131780853437517
394 9667741945497924
395 10234479962650545
396 10833724259946609
397 11467299207816582
398 12137129457873582
399 12845245176936794
400 13593787874421883
401 14385016209108551
402 15221312436826775
403 16105188851199260
404 17039294916470163
405 18026424409266436
406 19069523308527861
407 20171697712360562
408 21336222563851639
409 22566550425199633
410 23866321126367843
411 25239371486548786
412 26689745981991477
413 28221707514221401
414 29839749202576826
415 31548606309328927
416 33353269273318226
417 35258996912728040
418 37271330828605768
419 39396110018477016
420 41639486790914127
421 44007942937339893
422 46508307313207800
423 49147773729606831
424 51933920372960087
425 54874729594556784
426 57978609357259859
427 61254415119780602
428 64711473517992382
429 68359606559844039
430 72209157770442936
431 76271018935397410
432 80556658960977962
433 85078153428352644
434 89848216445421702
435 94880233299887819
436 100188295607790477
437 105787237382334502
438 111692673813666663
439 117921041102905023
440 124489639241152773
441 131416675992086114
442 138721314075648931
443 146423719720894607
444 154545114699012989
445 163107829910977310
446 172135362758740019
447 181652436277264070
448 191685062382039515
449 202260607105688745
450 213407860311950869
451 225157107653463971
452 237540207400643368
453 250590669796920137
454 264343741715786848
455 278836494156528512
456 294107915511500888
457 310199008019571556
458 327152890502495258
459 345014904672167132
460 363832728280188102
461 383656492262951271
462 404538905339317466
463 426535383075036238
464 449704185064482578
465 474106557100024465
466 499806882185659025
467 526872837112564687
468 555375558672208540
469 585389816067240102
470 616994193824417816
471 650271281607134702
472 685307875475236361
473 722195186817367721
474 761029063762272390
475 801910221116872733
476 844944483907892833
477 890243040391892345
478 937922709898296680
479 988106221176844311
480 1040922506920034520
481 1096507009933098385
482 1155002006942255002
483 1216556945309043161
484 1281328798982330911
485 1349482438739883427
486 1421191023413455129
487 1496636406927792040
488 1576009568227118736
489 1659511058692029424
490 1747351474524534679
491 1839751948464839301
492 1936944668747483323
493 2039173419415467911
494 2146694150350886827
495 2259775570889924454
496 2378699775860775391
497 2503762897649335327
498 2635275793641919325
499 2773564762381490129
500 2918972298323077948
501 3071857878251050053
502 3232598789815186723
503 3401590994961988539
504 3579250039326144235
505 3766012000067739166
506 3962334483859479356
507 4168697667214166387
508 4385605391537725095
509 4613586304790551150
510 4853195062867649437
511 5105013582269405831
512 5369652357937151134
513 5647751837511437866
514 5939983866700897376
515 6247053196694575581
516 6569699069172379469
517 6908696869520153492
518 7264859864718021001
519 7639041016181513344
520 8032134884998462835
521 8445079619504828145
522 8878859043680937641
523 9334504835976665457
524 9813098818143583052
525 10315775343351012920
526 10843723804333386912
527 11398191250508039677
528 11980485136057886297
529 12591976187586511967
530 13234101414658757040
531 13908367251510882569
532 14616352854650391608
533 15359713544304632066
534 16140184415939593188
535 16959584109495790156
536 17819818764152189378
537 18722886145968421318
538 19670879977913180514
539 20665994459337819312
540 21710529006215026692
541 22806893198931961782
542 23957611970878859422
543 25165331024378534541
544 26432822509249904377
545 27762990950322447859
546 29158879461387243942
547 30623676231707058935
548 32160721324898725144
549 33773513776155340270
550 35465719030109473668
551 37241176705179127665
552 39103908729357734775
553 41058127833214937940
554 43108246447897012986
555 45258885993876999146
556 47514886611267533073
557 49881317317478052501
558 52363486646264901417
559 54966953754060861581
560 57697540051076346522
561 60561341343246835594
562 63564740546204401276
563 66714420957609947572
564 70017380152969892627
565 73480944491639339553
566 77112784302340146946
567 80920929735377904158
568 84913787355389151771
569 89100157462393278025
570 93489252219804720157
571 98090714577913266229
572 102914638076634921275
573 107971587516934808901
574 113272620590239995416
575 118829310456291871845
576 124653769364668714068
577 130758673311671540857
578 137157287834118883853
579 143863494933204843115
580 150891821236737735443
581 158257467394589858978
582 165976338822939962492
583 174065077794078747828
584 182541096995125566139
585 191422614554659469701
586 200728690668945937915
587 210479265829289820067
588 220695200791140533247
589 231398318289360167589
590 242611446649853350774
591 254358465305240172445
592 266664352375048419280
593 279555234321775359398
594 293058437854333289855
595 307202544094366631497
596 322017445188778450798
597 337534403388609070244
598 353786112790305588616
599 370806763764713019981
600 388632110283474349168
601 407299540173976379397
602 426848148527161296732
603 447318814295827844526
604 468754280323468511901
605 491199236848461749958
606 514700408740573648400
607 539306646522594634676
608 565069021452206912263
609 592040924725806256086
610 620278171098881007104
611 649839106994503371654
612 680784723415518575287
613 713178773742878250996
614 747087896758232692083
615 782581744985282064825
616 819733118712237028566
617 858618105803166458056
618 899316227686662785499
619 941910591644258749733
620 986488049815046387662
621 1033139365055097360210
622 1081959384098290966816
623 1133047218174910557597
624 1186506431567077233369
625 1242445238276929988219
626 1300976707321518536706
627 1362218976851819697438
628 1426295477647413738739
629 1493335166207806419218
630 1563472768032391559575
631 1636849031335922704330
632 1713610991835004121027
633 1793912248880872243085
634 1877913253620841073028
635 1965781609494767815320
636 2057692385799392910845
637 2153828444660968988341
638 2254380782203352013996
639 2359548884289268860328
640 2469541097680449450053
641 2584575017035096425253
642 2704877888651428650273
643 2830687031420349523636
644 2962250275963844884751
645 3099826422470899335295
646 3243685718280663854381
647 3394110355777849044178
648 3551394991728887436146
649 3715847288681919375962
650 3887788479644010479281
651 4067553956722060742071
652 4255493885032273472652
653 4451973842633752856773
654 4657375487889683120550
655 4872097255087026332448
656 5096555079824379052174
657 5331183155081097120058
658 5576434719591787714595
659 5832782879528745777306
660 6100721465239827268285
661 6380765924141792137233
662 6673454251649549647197
663 6979347961347470530953
664 7299033096426513135651
665 7633121283708772288894
666 7982250832437716152833
667 8347087879281339724723
668 8728327581893004420784
669 9126695362613855089248
670 9542948204841099792148
671 9977876003794569221382
672 10432302974399406522837
673 10907089118178769394104
674 11403131752083006053372
675 11921367101324684495451
676 12462771959370864616493
677 13028365417352574718095
678 13619210666285425858940
679 14236416874568335177623
680 14881141144415716734599
681 15554590549914923676262
682 16258024260646185367212
683 16992755753800783892392
684 17760155119038682583523
685 18561651459286136457272
686 19398735392042152936463
687 20272961654681672963684
688 21185951818677645037618
689 22139397116541470024770
690 23135061386784972932700
691 24174784141041348069901
692 25260483759058923558006
693 26394160816071694726180
694 27577901548703306115449
695 28813881464305645889635
696 30104369100366248353712
697 31451729939316207485300
698 32858430485887553423762
699 34327042512818386709799
700 35860247482609750900760
701 37460841151637940997669
702 39131738364924700779517
703 40875978048416483445110
704 42696728407720367189023
705 44597292340740773363904
706 46581113073860154570652
707 48651780029749757305260
708 50813034937203600470345
709 53068778191776788350968
710 55423075478429725823983
711 57880164665711712955816
712 60444462983557057195408
713 63120574495041284842420
714 65913297875110248437037
715 68827634507510646515639
716 71868796913947591236525
717 75042217527650873692357
718 78353557826467418809196
719 81808717838692455156795
720 85413846037933935188305
721 89175349641337691724626
722 93099905328736485778663
723 97194470398256193539729
724 101466294377309744056848
725 105922931105815591226397
726 110572251312045318872165
727 115422455699346382900308
728 120482088565733113099299
729 125760051976115278749945
730 131265620510869433631380
731 137008456612168478939738
732 142998626553619912586330
733 149246617056407034691444
734 155763352579472009647344
735 162560213308857069996812
736 169649053875885606507551
737 177042222831375606574481
738 184752582907876390576588
739 192793532099363736027514
740 201179025592872433203543
741 209923598583923529334584
742 219042390012906254664724
743 228551167256887341578009
744 238466351816896413446886
745 248805046037984203022608
746 259585060905214340510669
747 270824944955934438434263
748 282544014354840018028952
749 294762384175468083989590
750 307501000938245955267726
751 320781676452284406528383
752 334627123014931573118778
753 349060990020110434823823
754 364107902033647529562100
755 379793498390752467853120
756 396144474378370482392540
757 413188624062031043527505
758 430954884824777083513496
759 449473383682613360256017
760 468775485449295331223665
761 488893842820091417014743
762 509862448452980004050681
763 531716689122516747816698
764 554493402030906972918438
765 578230933357561276831714
766 602969199138209314015735
767 628749748561365699919248
768 655615829780265499258313
769 683612458335089000862626
770 712786488291175770370906
771 743186686195622585879202
772 774863807966129097115525
773 807870678822651486966054
774 842262276384517319129100
775 878095817052363811335317
776 915430845807014474939812
777 954329329554143334799094
778 994855754157027051100331
779 1037077225296457948805038
780 1081063573311082099573555
781 1126887462168252572954006
782 1174624502730462567918083
783 1224353370479319484998762
784 1276155927874825450196612
785 1330117351524714534258175
786 1386326264355281202350941
787 1444874872972227760441156
788 1505859110417674968573420
789 1569378784526704545841999
790 1635537732105406664182777
791 1704443979149785557725266
792 1776209907344528841671020
793 1850952427078208430713708
794 1928793157232244527046492
795 2009858611998738827596839
796 2094280395004225127065375
797 2182195401014404528586277
798 2273746025518125383965290
799 2369080382487166744186350
800 2468352530632903973440903
801 2571722708479552810138033
802 2679357578599616283431790
803 2791430481356137368294720
804 2908121698523784035697243
805 3029618727160178661756769
806 3156116564127895143009241
807 3287818001667390206416082
808 3424933934451832657417325
809 3567683678555149654261032
810 3716295302797097812257945
811 3871005972930093985891268
812 4032062309166932049105210
813 4199720757550076394376485
814 4374247975699636021330708
815 4555921233479394933471003
816 4745028829158837113896047
817 4941870521652160120286327
818 5146757979456118131451641
819 5360015246912459012501414
820 5581979228463995079814452
821 5813000191578228757272295
822 6053442289058312433152236
823 6303684101467058858931379
824 6564119200438323074911365
825 6835156733657176456122092
826 7117222032341819377371921
827 7410757242068555671820193
828 7716221977835786740994492
829 8034094004272761258341914
830 8364869941956758356876109
831 8709066000813697466627128
832 9067218741638629288198969
833 9439885866785560152361860
834 9827647041141270242724646
835 10231104744512623930917826
836 10650885156626066722092428
837 11087639075954852674445145
838 11542042873662988096288478
839 12014799483973921966101240
840 12506639432349977475262771
841 13018321902889957833018964
842 13550635846435138554023012
843 14104401130897907395138769
844 14680469735415220559171473
845 15279726989955934354676348
846 15903092862104443134778098
847 16551523292773036690633108
848 17226011582694582628978769
849 17927589831580484790528862
850 18657330431934262879142048
851 19416347619548097847566356
852 20205799082821691836668433
853 21026887633083758528736493
854 21880862938215508086982861
855 22769023321920765536320746
856 23692717631113917560322094
857 24653347173946829117958094
858 25652367731130432104253686
859 26691291643261699184907456
860 27771689977009809804246384
861 28895194773075815516826097
862 30063501378992303383538823
863 31278370869896000597929964
864 32541632560568157698295325
865 33855186612110426745595163
866 35221006736796191198027360
867 36641143004717147489400234
868 38117724756028212642234204
869 39652963622681207159662845
870 41249156663732807359275182
871 42908689618407778749005812
872 44634040281306101713992250
873 46427782004246919885995316
874 48292587329463234050236793
875 50231231758975091294550772
876 52246597665204301743164579
877 54341678348017809468979157
878 56519582243637372660280451
879 58783537290988388603223405
880 61136895461327494755946356
881 63583137457135720990812149
882 66125877586548124436205541
883 68768868819750888461191518
884 71516008034079549314452702
885 74371341454725985899999726
886 77339070298284260780368151
887 80423556626554382020496644
888 83629329418366611293572016
889 86961090867394103459962802
890 90423722914287742111838805
891 94022294021689631242241603
892 97762066201071823782321702
893 101648502300588246091478101
894 105687273563543563609407451
895 109884267467344340218964843
896 114245595853241027182446371
897 118777603357452709046236468
898 123486876154738964940615439
899 128380251025790044691907958
900 133464824760310217825365178
901 138747963908001231391420633
902 144237314890189810206293453
903 149940814485202368488861211
904 155866700701162694738383581
905 162023524050276820950135456
906 168420159239279888863866213
907 175065817291139695164699057
908 181970058113762782192300848
909 189142803531902599062428206
910 196594350799163776542067786
911 204335386607486542573199174
912 212377001612236099658521794
913 220730705491550813712684654
914 229408442559393272755360723
915 238422607952319266057031568
916 247786064410822711079384016
917 257512159676730635809005304
918 267614744529021654931162568
919 278108191481105895496323994
920 289007414163563838875175792
921 300327887417058092548492701
922 312085668121155884640439412
923 324297416785572494865656537
924 336980419931438253966616361
925 350152613291024157973107901
926 363832605855526864889697888
927 378039704801410666303215962
928 392793941327048033052524626
929 408116097432366295611228389
930 424027733675535638349911615
931 440551217941773747242032218
932 457709755260759364931296499
933 475527418710266792041519835
934 494029181445145655673485355
935 513240949891975479597736157
936 533189598151338730474216350
937 553903003650952871546115825
938 575410084094624878801118605
939 597740835753386833659993720
940 620926373147010311522417847
941 644998970165597867958645484
942 669992102682913117633410189
943 695940492714724530131343506
944 722880154177533785748163429
945 750848440304794374098965351
946 779884092779963374685549342
947 810027292647594139319659317
948 841319713066066019515777577
949 873804573967551346313768483
950 907526698693369736816389381
951 942532572675033151566506114
952 978870404234007412345368503
953 1016590187575529218914576110
954 1055743768054724132876723963
955 1096384909795755745326883897
956 1138569365747839332271301519
957 1182354950264621713533654781
958 1227801614296742138281571654
959 1274971523290254183352439634
960 1323929137887126052230105213
961 1374741297527112575218778755
962 1427477307054069140219421143
963 1482209026433079422326133074
964 1539010963688801501228457907
965 1597960371178980326746994976
966 1659137345321380377366241791
967 1722624929896194575767207928
968 1788509223050583111667379846
969 1856879488136075194943562333
970 1927828268514475841617595746
971 2001451506472295882577440094
972 2077848666388965093442282148
973 2157122862308782056937699183
974 2239380990072151259905895414
975 2324733864166691624925997723
976 2413296359464776825131778483
977 2505187558019465301846025803
978 2600530901097159018036360877
979 2699454346631116955598539049
980 2802090532286762872174934901
981 2908576944335930503764032558
982 3019056092544464579060598535
983 3133675691284245530313191654
984 3252588847088473894014080942
985 3375954252876176911989597164
986 3503936389080194229870854797
987 3636705731920536395505269868
988 3774438969073866115979221927
989 3917319222998034879688154490
990 4065536282180063668046468307
991 4219286840584722952753445427
992 4378774745590963686923473641
993 4544211254712841873775893734
994 4715815301412359456040414414
995 4893813770321702881345106687
996 5078441782203870668760787638
997 5269942988991453931910827139
998 5468569879255622839654139951
999 5674584094468908080583213439
1000 5888256756438487023186845558