0 1
1 1
2 2
3 2
4 3
5 3
6 5
7 5
8 8
9 8
10 12
11 12
12 18
13 17
14 26
15 25
16 36
17 36
18 50
19 50
20 69
21 69
22 93
23 95
24 123
25 129
26 164
27 171
28 215
29 229
30 278
31 300
32 365
33 387
34 468
35 507
36 595
37 652
38 760
39 830
40 966
41 1055
42 1214
43 1336
44 1530
45 1674
46 1910
47 2104
48 2380
49 2617
50 2953
51 3253
52 3656
53 4019
54 4504
55 4952
56 5539
57 6088
58 6776
59 7440
60 8299
61 9079
62 10082
63 11070
64 12251
65 13401
66 14862
67 16235
68 17929
69 19611
70 21607
71 23597
72 26042
73 28322
74 31191
75 34017
76 37351
77 40624
78 44690
79 48496
80 53186
81 57866
82 63317
83 68698
84 75291
85 81520
86 89163
87 96703
88 105519
89 114218
90 124797
91 134864
92 147020
93 159105
94 173181
95 187035
96 203754
97 219786
98 239009
99 258065
100 280119
101 302103
102 328196
103 353425
104 383208
105 413142
106 447498
107 481714
108 521827
109 561238
110 607272
111 653491
112 706062
113 759052
114 820483
115 881190
116 951096
117 1022106
118 1102175
119 1183173
120 1275881
121 1368785
122 1474477
123 1582163
124 1702507
125 1825699
126 1964767
127 2105154
128 2263054
129 2425585
130 2605618
131 2790285
132 2996935
133 3207836
134 3442653
135 3685038
136 3951341
137 4227023
138 4532614
139 4845741
140 5191557
141 5550967
142 5943237
143 6350551
144 6798036
145 7260724
146 7767236
147 8295118
148 8868074
149 9466266
150 10119021
151 10795508
152 11531993
153 12303142
154 13135733
155 14006853
156 14950967
157 15935578
158 17001274
159 18118405
160 19319896
161 20580066
162 21941072
163 23362040
164 24893601
165 26503664
166 28228139
167 30039701
168 31987322
169 34027911
170 36218880
171 38521599
172 40982992
173 43573069
174 46348050
175 49258448
176 52372423
177 55651486
178 59147926
179 62826612
180 66759300
181 70887425
182 75295490
183 79935919
184 84874906
185 90076170
186 95620524
187 101445253
188 107651925
189 114187046
190 121134033
191 128443657
192 136225326
193 144403772
194 153103626
195 162260440
196 171979269
197 182210068
198 193082914
199 204508529
200 216645400
201 229415326
202 242958486
203 257206342
204 272328297
205 288221024
206 305078701
207 322809803
208 341596453
209 361352424
210 382299839
211 404301809
212 427620421
213 452136270
214 478089168
215 505367722
216 534256505
217 564598932
218 596724480
219 630478563
220 666186476
221 703696366
222 743388744
223 785061880
224 829143564
225 875438988
226 924374608
227 975758137
228 1030082924
229 1087097331
230 1147359103
231 1210611449
232 1277426835
233 1347551886
234 1421629948
235 1499348327
236 1581419820
237 1667532684
238 1758431835
239 1853787850
240 1954443666
241 2059998673
242 2171390280
243 2288212322
244 2411442624
245 2540663086
246 2676951325
247 2819833565
248 2970502336
249 3128445681
250 3294944758
251 3469461114
252 3653397669
253 3846161825
254 4049277304
255 4262133168
256 4486349794
257 4721284839
258 4968721361
259 5227952452
260 5500909963
261 5786840922
262 6087843264
263 6403130792
264 6734952703
265 7082482114
266 7448158243
267 7831097108
268 8233947909
269 8655768952
270 9099417627
271 9563932893
272 10052362640
273 10563695739
274 11101251415
275 11663971047
276 12255396000
277 12874453881
278 13524967815
279 14205777428
280 14921053646
281 15669561291
282 16455756521
283 17278472024
284 18142422159
285 19046347784
286 19995425355
287 20988355880
288 22030601101
289 23120949507
290 24265239839
291 25462161443
292 26718099891
293 28031693539
294 29409699346
295 30850928992
296 32362529821
297 33943226989
298 35600887722
299 37334191669
300 39151418629
301 41051491864
302 43043191848
303 45125401878
304 47307731725
305 49589026232
306 51979420959
307 54478161119
308 57095944763
309 59831907354
310 62697869537
311 65693030399
312 68829712685
313 72107678853
314 75539969158
315 79126319101
316 82881048016
317 86803971058
318 90910150787
319 95200138674
320 99689794428
321 104379687777
322 109287319327
323 114413431480
324 119776324340
325 125377750362
326 131237012974
327 137355996457
328 143755938791
329 150439005855
330 157427423006
331 164724738200
332 172354351943
333 180320006135
334 188647532585
335 197341142879
336 206427848261
337 215913536404
338 225826779046
339 236173847322
340 246986167235
341 258270681147
342 270060351344
343 282364363971
344 295217364410
345 308629202057
346 322638153493
347 337254948288
348 352519685116
349 368445904783
350 385076018334
351 402424386807
352 420537756730
353 439431877253
354 459155694400
355 479728558723
356 501202166481
357 523597139934
358 546970500304
359 571344637079
360 596779421803
361 623301695347
362 650974803803
363 679827354280
364 709929155932
365 741311109081
366 774046728928
367 808172508042
368 843766166968
369 880866677308
370 919559607393
371 959887065618
372 1001939146159
373 1045764923293
374 1091459925050
375 1139076341463
376 1188719391282
377 1240445403993
378 1294365282155
379 1350543826596
380 1409098855787
381 1470099454955
382 1533675166622
383 1599900341210
384 1668911777522
385 1740794496186
386 1815693725592
387 1893700024759
388 1974973136375
389 2059610372365
390 2147780769099
391 2239594457726
392 2335231244440
393 2434808671626
394 2538524017684
395 2646503461777
396 2758956037956
397 2876023925449
398 2997929560527
399 3124824463877
400 3256952489424
401 3394476517066
402 3537655170760
403 3686670436494
404 3841798112292
405 4003232404870
406 4171275145206
407 4346134573268
408 4528131406214
409 4717497785545
410 4914575417403
411 5119611779296
412 5332980850393
413 5554948097548
414 5785910923354
415 6026163512680
416 6276130208949
417 6536125314084
418 6806611691340
419 7087926029396
420 7380561250612
421 7684889516599
422 8001437012436
423 8330600749935
424 8672954452168
425 9028924140273
426 9399120532148
427 9784012325007
428 10184252330814
429 10600341232393
430 11032989533987
431 11482733371605
432 11950330405159
433 12436369569998
434 12941660121807
435 13466830722777
436 14012761540694
437 14580126831080
438 15169864598393
439 15782712568083
440 16419673826486
441 17081537635878
442 17769391779439
443 18484081559209
444 19226768606023
445 19998376064502
446 20800145555924
447 21633063619634
448 22498476217761
449 23397441352598
450 24331394918599
451 25301489228959
452 26309260630111
453 27355941795850
454 28443194799088
455 29572340133791
456 30745152986143
457 31963070493850
458 33227989898674
459 34541447704723
460 35905495808714
461 37321781578992
462 38792495277982
463 40319424547618
464 41904912636523
465 43550873183984
466 45259834409390
467 47033846865331
468 48875611858481
469 50787352408302
470 52771956152070
471 54831801902956
472 56970003986029
473 59189112656609
474 61492453355233
475 63882785292810
476 66363665466205
477 68938048656614
478 71609763962350
479 74381977713498
480 77258781080664
481 80243597661347
482 83340800050760
483 86554051908478
484 89888059568091
485 93346750500604
486 96935150141803
487 100657497523706
488 104519165700426
489 108524695437062
490 112679859177787
491 116989522437513
492 121459852275060
493 126096096342878
494 130904844403139
495 135891714601881
496 141063784164669
497 146427075240660
498 151989143984669
499 157756476633902
500 163737149385763
501 169938109257347
502 176368018956581
503 183034320052709
504 189946265529705
505 197111865691145
506 204541004574755
507 212242258038768
508 220226222459524
509 228502087951449
510 237081165869315
511 245973337710737
512 255190687708805
513 264743796885758
514 274645607421267
515 284907451621160
516 295543149956611
517 306564878672336
518 317987393892522
519 329823731430921
520 342089687990056
521 354799226661285
522 367969206142253
523 381614614990122
524 395753456885171
525 410401777864401
526 425578834656649
527 441301805813836
528 457591245368939
529 474465585465910
530 491946763789484
531 510054507407331
532 528812270893500
533 548241172204756
534 568366238760598
535 589210108274939
536 610799494322046
537 633158622476337
538 656316032152991
539 680297648277178
540 705133921743587
541 730852631972478
542 757486267818244
543 785064544237223
544 813622162662897
545 843190915453404
546 873807816625504
547 905506907939732
548 938327676333135
549 972306533999023
550 1007485627214650
551 1043903902060819
552 1081606311112555
553 1120634531502608
554 1161036507920870
555 1202856800943559
556 1246146572491761
557 1290953467668563
558 1337332038755657
559 1385333246301226
560 1435015262196697
561 1486432566153226
562 1539647196759712
563 1594717382668305
564 1651709273532633
565 1710685116138779
566 1771715432074940
567 1834866738397859
568 1900214223796161
569 1967828968392195
570 2037791114578795
571 2110176613007008
572 2185070887178045
573 2262555072790452
574 2342720216482726
575 2425652984697147
576 2511450413191056
577 2600205058588722
578 2692020325418006
579 2786995064423460
580 2885239448107481
581 2986859034253145
582 3091971212803089
583 3200688663626647
584 3313136464912597
585 3429434915158347
586 3549717240419392
587 3674111851161192
588 3802760676541843
589 3935800741012928
590 4073383226991224
591 4215654379867570
592 4362775181638480
593 4514901684952891
594 4672205363110578
595 4834852656353313
596 5003026190646204
597 5176903541330034
598 5356679114839601
599 5542542344272241
600 5734700250938535
601 5933354808879863
602 6138726447469585
603 6351030581235485
604 6570501810959787
605 6797369843719643
606 7031884465779868
607 7274290488077977
608 7524853818568753
609 7783835481123665
610 8051518401112061
611 8328180839060187
612 8614123961781834
613 8909644208612419
614 9215062135538299
615 9530693707228362
616 9856879912109082
617 10193957454065444
618 10542289237408038
619 10902233858388372
620 11274177481132077
621 11658502199050952
622 12055618693711250
623 12465934012609657
624 12889885149772411
625 13327905444731628
626 13780459824129471
627 14248009869827521
628 14731049906768632
629 15230071509921483
630 15745600556717642
631 16278160228620293
632 16828309874134940
633 17396606578782854
634 17983644962475995
635 18590018117899866
636 19216358483109451
637 19863297054631612
638 20531506398182522
639 21221658225090704
640 21934467319310519
641 22670648584494067
642 23430962111039135
643 24216168267695986
644 25027075199299397
645 25864492053613130
646 26729277558743646
647 27622292629188936
648 28544450205345803
649 29496665680363189
650 30479909505316417
651 31495155548767181
652 32543434739176501
653 33625782911382505
654 34743295897129788
655 35897074764088926
656 37088284111783434
657 38318094941655632
658 39587744211773302
659 40898477130307948
660 42251608172230882
661 43648460583246394
662 45090431047539691
663 46578926472080924
664 48115430003919566
665 49701437211697552
666 51338523911084589
667 53028278979990724
668 54772376372001332
669 56572504938149680
670 58430441911322133
671 60347982132095919
672 62327013381046065
673 64369441935478888
674 66477272801492194
675 68652531630739261
676 70897346675971590
677 73213870050234373
678 75604361953826514
679 78071107608187108
680 80616506939608609
681 83242987595461250
682 85953096543773674
683 88749412339975313
684 91634639234498653
685 94611514496642239
686 97682909013222133
687 100851729908349098
688 104121023277651933
689 107493876121246094
690 110973521961139932
691 114563237095427130
692 118266453448378541
693 122086649624145412
694 126027466398415980
695 130092596687367484
696 134285904359277656
697 138611307756024518
698 143072907026594551
699 147674861495155038
700 152421519817199149
701 157317296408548843
702 162366805455294516
703 167574729808837091
704 172945964692971791
705 178485479585891422
706 184198465514899521
707 190090195475551552
708 196166176113174683
709 202431999782629743
710 208893507312922341
711 215556632001015954
712 222427566238076885
713 229512604059749496
714 236818313126485730
715 244351367205010267
716 252118730913251878
717 260127483059960489
718 268385006130886340
719 276898807672667558
720 285676715637777409
721 294726688728293368
722 304057026365301394
723 313676168319803846
724 323592910147927037
725 333816200552098698
726 344355363960205550
727 355219884866725055
728 366419647021047384
729 377964705794747778
730 389865533845075130
731 402132790575445207
732 414777575747225057
733 427811184489149022
734 441245380086809640
735 455092134828981460
736 469363910323731413
737 484073395002957742
738 499233794016260265
739 514858549931254666
740 530961654051010103
741 547557351530153214
742 564660461532091044
743 582286078055932386
744 600449901004700022
745 619167918004028177
746 638456760374194596
747 658333366602519003
748 678815348453324069
749 699920649746348086
750 721667925131961653
751 744076177143447336
752 767165162753671564
753 790955010083791996
754 815466637080366287
755 840721361990591982
756 866741336570563844
757 893549132204432609
758 921168204971199350
759 949622458289221859
760 978936721539551979
761 1009136305967522429
762 1040247500217970571
763 1072297098256117097
764 1105312930749441485
765 1139323366610685718
766 1174357860627405813
767 1210446446378213169
768 1247620303002026255
769 1285911217208591791
770 1325352190499099786
771 1365976871097945230
772 1407820179528849427
773 1450917730900849365
774 1495306482856116461
775 1541024122304299143
776 1588109758834822361
777 1636603277996697530
778 1686546056056027416
779 1737980301667413185
780 1790949795594442199
781 1845499193264784113
782 1901674815677088768
783 1959523913908916793
784 2019095484289016749
785 2080439519644447851
786 2143607853599994576
787 2208653367185458921
788 2275630890356159533
789 2344596366519498952
790 2415607781908017595
791 2488724314510937710
792 2564007295948130711
793 2641519311207884036
794 2721325224973791411
795 2803491233529780671
796 2888085922604508035
797 2975179301911737503
798 3064843900140580666
799 3157153744239176174
800 3252185525765316866
801 3350017527545863423
802 3450730826306518210
803 3554408198591981961
804 3661135365319113370
805 3770999836678688358
806 3884092236553669642
807 4000505088383753706
808 4120334180216937798
809 4243677327818550629
810 4370635786955460880
811 4501312948498570950
812 4635815839142908590
813 4774253751587318803
814 4916739791572922741
815 5063389481415630404
816 5214322360197678487
817 5369660512464758992
818 5529530266832133472
819 5694060652506669361
820 5863385149413614435
821 6037640115626777430
822 6216966597137054026
823 6401508672263234113
824 6591415370274480764
825 6786838936370660327
826 6987936808876465233
827 7194869850765031785
828 7407804393295852666
829 7626910377070513230
830 7852363515771965683
831 8084343349631444992
832 8323035474489812906
833 8568629558268737588
834 8821321644730563619
835 9081312069865461238
836 9348807898094310972
837 9624020743049992431
838 9907169276884310375
839 10198477009681989230
840 10498174881348379445
841 10806498932435203808
842 11123693041801564138
843 11450006492230035620
844 11785696789867715147
845 12131027184047006673
846 12486269578854132434
847 12851701934175704374
848 13227611336945221537
849 13614291288302620273
850 14012044865528366671
851 14421181958404271671
852 14842022533500588258
853 15274893741354027387
854 15720133356205689547
855 16178086758691652188
856 16649110476366185008
857 17133569111070266717
858 17631838992587272126
859 18144304965547157833
860 18671364235335120434
861 19213423020041330451
862 19770900508181446521
863 20344225449792300029
864 20933840239352446361
865 21540197355144653629
866 22163763651771921247
867 22805016653895849183
868 23464448972580581663
869 24142564532499676221
870 24839883126287346130
871 25556936478241444607
872 26294273027702907136
873 27052453834985348584
874 27832057502053126381
875 28633676005951960776
876 29457919771858471246
877 30305413330687643624
878 31176800640841334978
879 32072740576875769628
880 32993912402873270063
881 33941011182136438267
882 34914753418590749281
883 35915872277357074060
884 36945123497651023115
885 38003280431488989069
886 39091140123524396237
887 40209518265123651214
888 41359255458863993229
889 42541211970414082823
890 43756274287222408301
891 45005349676231233498
892 46289372927580060694
893 47609300820167296415
894 48966119067970979148
895 50360836570228646779
896 51794492678125994797
897 53268151236985853043
898 54782908055788380979
899 56339884851261890459
900 57940236941363772080
901 59585146958566081313
902 61275832890163939024
903 63013541571176100732
904 64799556949370133935
905 66635193471546125114
906 68521804593390049363
907 70460775922652559931
908 72453534105481190179
909 74501539734357047650
910 76606296480908643533
911 78769343891047546422
912 80992266788664267079
913 83276687811193954155
914 85624277219963366050
915 88036745188269947863
916 90515851884898595876
917 93063399640338242036
918 95681243325872802802
919 98371282247641285914
920 101135470968161683373
921 103975810936439768863
922 106894361609464270153
923 109893231954215013291
924 112974591896037625571
925 116140663532070098693
926 119393733056115335902
927 122736141696822076564
928 126170297975777983515
929 129698668505884031408
930 133323790608342007340
931 137048262809042289378
932 140874757975091552579
933 144806013518480814290
934 148844844897592636487
935 152994135676683477928
936 157256851423791029543
937 161636029451692671411
938 166134793275110166083
939 170756342048070914996
940 175503965428344752464
941 180381032856606855213
942 185391008856912167868
943 190537441985256959094
944 195823980739612646384
945 201254362186748013236
946 206832428320148547531
947 212562114523636909498
948 218447466412814765313
949 224492627950357081840
950 230701858944759214764
951 237079522834530692516
952 243630104687681144495
953 250358198806774323115
954 257268527259932079182
955 264365927128693928401
956 271655369756241594849
957 279141947645290111167
958 286830894258152712372
959 294727570730002201996
960 302837486262546747012
961 311166284459249756460
962 319719764496319174065
963 328503867098966067557
964 337524696330644279176
965 346788505367657359829
966 356301718941519960686
967 366070918730319711324
968 376102866649774401523
969 386404489865925446013
970 396982904772249578590
971 407845401792316405398
972 418999470090299462836
973 430452781969553806598
974 442213218502543985856
975 454288853546792464366
976 466687980143844868702
977 479419094306301624946
978 492490922226922601983
979 505912403655594935483
980 519692720121337169102
981 533841277903267847410
982 548367737109080244714
983 563281994409249461342
984 578594213025277648378
985 594314805035637432825
986 610454462463662364630
987 627024139175812526801
988 644035082935780432226
989 661498817038402374070
990 679427173376409079641
991 697832273644599825830
992 716726563618573243944
993 736122793929582607855
994 756034055420951997270
995 776473759652010201824
996 797455675393174170469
997 818993908682309465103
998 841102940643922516589
999 863797607114104911284
1000 887093137682175108843