0 1
1 1
2 1
3 2
4 1
5 3
6 3
7 3
8 6
9 5
10 7
11 9
12 9
13 12
14 15
15 16
16 21
17 24
18 26
19 33
20 37
21 42
22 51
23 57
24 65
25 78
26 86
27 99
28 115
29 128
30 146
31 168
32 187
33 213
34 243
35 269
36 306
37 345
38 383
39 433
40 487
41 539
42 607
43 678
44 749
45 842
46 935
47 1033
48 1157
49 1279
50 1413
51 1575
52 1736
53 1916
54 2127
55 2339
56 2579
57 2853
58 3131
59 3446
60 3801
61 4164
62 4575
63 5033
64 5504
65 6040
66 6625
67 7235
68 7925
69 8674
70 9460
71 10345
72 11300
73 12307
74 13437
75 14649
76 15935
77 17372
78 18905
79 20540
80 22359
81 24292
82 26364
83 28655
84 31087
85 33703
86 36578
87 39629
88 42918
89 46515
90 50332
91 54450
92 58937
93 63699
94 68839
95 74419
96 80345
97 86739
98 93660
99 101010
100 108942
101 117505
102 126597
103 136409
104 146972
105 158195
106 170297
107 183295
108 197113
109 212000
110 227960
111 244929
112 263199
113 282748
114 303540
115 325904
116 349796
117 375217
118 402527
119 431667
120 462680
121 495957
122 531423
123 569172
124 609632
125 652717
126 698568
127 747663
128 799896
129 855481
130 914934
131 978136
132 1045391
133 1117249
134 1193586
135 1274805
136 1361495
137 1453534
138 1551436
139 1655829
140 1766607
141 1884411
142 2009903
143 2143010
144 2284516
145 2435121
146 2594795
147 2764481
148 2944929
149 3136166
150 3339315
151 3555173
152 3783856
153 4026681
154 4284500
155 4557542
156 4847344
157 5154823
158 5480342
159 5825688
160 6191857
161 6579380
162 6990314
163 7425750
164 7886431
165 8374721
166 8891808
167 9438701
168 10018104
169 10631323
170 11279692
171 11966269
172 12692536
173 13460196
174 14272703
175 15131752
176 16039476
177 16999781
178 18014604
179 19086593
180 20220161
181 21417535
182 22681961
183 24018408
184 25429473
185 26919090
186 28492842
187 30153775
188 31906621
189 33757657
190 35710456
191 37770668
192 39945360
193 42238728
194 44657479
195 47209557
196 49899919
197 52736483
198 55728161
199 58880833
200 62203788
201 65707047
202 69397562
203 73286187
204 77384213
205 81699857
206 86245739
207 91034588
208 96076123
209 101384962
210 106975473
211 112859118
212 119052800
213 125572754
214 132432460
215 139651426
216 147248004
217 155238042
218 163643970
219 172486565
220 181784443
221 191563327
222 201846762
223 212656563
224 224022189
225 235970357
226 248526551
227 261724459
228 275594440
229 290166211
230 305478223
231 321564990
232 338461126
233 356210445
234 374852220
235 394426677
236 414983695
237 436568008
238 459226236
239 483015122
240 507985660
241 534191774
242 561697955
243 590562333
244 620847217
245 652625829
246 685964442
247 720934934
248 757620378
249 796096380
250 836445679
251 878762470
252 923133043
253 969652481
254 1018427517
255 1069556639
256 1123148959
257 1179325370
258 1238198250
259 1299892631
260 1364545414
261 1432284802
262 1503253849
263 1577607519
264 1655492075
265 1737070968
266 1822519531
267 1912004567
268 2005712638
269 2103842064
270 2206582984
271 2314148080
272 2426761628
273 2544640296
274 2668026232
275 2797173011
276 2932327438
277 3073764923
278 3221772074
279 3376629871
280 3538651289
281 3708160164
282 3885476222
283 4070954753
284 4264961631
285 4467860474
286 4680054176
287 4901956058
288 5133979395
289 5376580717
290 5630226793
291 5895387037
292 6172578397
293 6462327861
294 6765168260
295 7081684505
296 7412471450
297 7758133554
298 8119332084
299 8496738356
300 8891037690
301 9302977147
302 9733314130
303 10182825099
304 10652353561
305 11142753811
306 11654904965
307 12189758836
308 12748278773
309 13331459519
310 13940374384
311 14576109413
312 15239789481
313 15932624236
314 16655837657
315 17410700945
316 18198576727
317 19020844011
318 19878938415
319 20774394100
320 21708764304
321 22683669312
322 23700835513
323 24762011813
324 25869025864
325 27023819452
326 28228361072
327 29484711057
328 30795052490
329 32161600294
330 33586675680
331 35072731895
332 36622260353
333 38237874643
334 39922330372
335 41678428963
336 43509111569
337 45417472149
338 47406659504
339 49479981539
340 51640910793
341 53892985174
342 56239923001
343 58685620154
344 61234050293
345 63889390881
346 66656010928
347 69538371866
348 72541164568
349 75669286811
350 78927745676
351 82321805810
352 85856955812
353 89538812918
354 93373282768
355 97366513757
356 101524805250
357 105854778703
358 110363319016
359 115057487789
360 119944705551
361 125032679189
362 130329321592
363 135842944860
364 141582173097
365 147555869586
366 153773340766
367 160244233775
368 166978472558
369 173986472243
370 181279020511
371 188867224502
372 196762735117
373 204977611273
374 213524279426
375 222415767248
376 231665550222
377 241287525356
378 251296253590
379 261706788288
380 272534665057
381 283796151878
382 295508058992
383 307687747074
384 320353384006
385 333523735743
386 347218194778
387 361457042756
388 376261222049
389 391652386416
390 407653168342
391 424286931258
392 441577844778
393 459551155064
394 478232917854
395 497650100683
396 517830854781
397 538804228995
398 560600301195
399 583250450450
400 606787052123
401 631243640624
402 656655180232
403 683057742027
404 710488700537
405 738987001041
406 768592819062
407 799347793795
408 831295289667
409 864480039374
410 898948416472
411 934748689246
412 971930648795
413 1010545922736
414 1050648219425
415 1092292942714
416 1135537549258
417 1180441780656
418 1227067266470
419 1275477928135
420 1325740196364
421 1377922604420
422 1432096241061
423 1488334950936
424 1546714920649
425 1607315182752
426 1670217796662
427 1735507430545
428 1803271918742
429 1873602420300
430 1946592999765
431 2022341240707
432 2100948379191
433 2182518886664
434 2267161141908
435 2354987536954
436 2446114066081
437 2540661057996
438 2638753251475
439 2740519395272
440 2846093042387
441 2955612592615
442 3069220908041
443 3187066171730
444 3309301894599
445 3436086551339
446 3567584505337
447 3703965977764
448 3845406709627
449 3992088954164
450 4144201405936
451 4301938895304
452 4465503450124
453 4635104182033
454 4810957020105
455 4993285843711
456 5182322323707
457 5378305702459
458 5581483998764
459 5792113802764
460 6010460110050
461 6236797599098
462 6471410378744
463 6714591884787
464 6966646231032
465 7227887907632
466 7498641749015
467 7779244359865
468 8070043763319
469 8371399449481
470 8683683876647
471 9007282069586
472 9342591758787
473 9690024956602
474 10050007506071
475 10422979321829
476 10809396041418
477 11209728525050
478 11624463209232
479 12054103834104
480 12499170895210
481 12960202121494
482 13437754278556
483 13932402574860
484 14444741277100
485 14975385588148
486 15524971010938
487 16094154114947
488 16683614488403
489 17294054063261
490 17926198046614
491 18580796947384
492 19258625867116
493 19960485610501
494 20687204786013
495 21439639068970
496 22218672506532
497 23025219691277
498 23860225003473
499 24724664127366
500 25619546297259
501 26545913526451
502 27504842352025
503 28497446153507
504 29524874378156
505 30588314531385
506 31688994567674
507 32828182124079
508 34007186774841
509 35227362493837
510 36490106909006
511 37796863841285
512 39149125838898
513 40548433466416
514 41996378148354
515 43494604776714
516 45044811050789
517 46648750646253
518 48308235896821
519 50025137203997
520 51801386553918
521 53638980273796
522 55539978532599
523 57506509229096
524 59540770825997
525 61645031963260
526 63821635741598
527 66073002638807
528 68401630260354
529 70810098043585
530 73301070260071
531 75877295932350
532 78541613985660
533 81296956340498
534 84146348026727
535 87092912811245
536 90139876387645
537 93290566720757
538 96548420179196
539 99916984831716
540 103399921058956
541 107001008220659
542 110724148069025
543 114573365668849
544 118552816631921
545 122666790658251
546 126919712809019
547 131316151342939
548 135860821399753
549 140558586673325
550 145414467885266
551 150433646629128
552 155621467495647
553 160983447220416
554 166525278708693
555 172252833670447
556 178172172482025
557 184289548413464
558 190611410835051
559 197144415835996
560 203895430681083
561 210871537654075
562 218080045478174
563 225528494033779
564 233224658910686
565 241176563676674
566 249392484891199
567 257880957445785
568 266650787730654
569 275711058983518
570 285071137501910
571 294740686762576
572 304729673151296
573 315048373135693
574 325707388395187
575 336717651984358
576 348090436563274
577 359837370598576
578 371970445017881
579 384502022603819
580 397444855332129
581 410812091580443
582 424617286799061
583 438874422057755
584 453597911882054
585 468802616320199
586 484503860774551
587 500717444548705
588 517459654439859
589 534747285936062
590 552597652564389
591 571028601149747
592 590058534466854
593 609706421488251
594 629991814459931
595 650934873104648
596 672556375882104
597 694877739040341
598 717921042473826
599 741709042121866
600 766265191167319
601 791613667660699
602 817779388193726
603 844788031431549
604 872666067625189
605 901440773709284
606 931140259366097
607 961793498560623
608 993430346228794
609 1026081567084237
610 1059778869319767
611 1094554923071205
612 1130443392194640
613 1167478970289005
614 1205697401137117
615 1245135513699035
616 1285831260626590
617 1327823740900548
618 1371153238301760
619 1415861262605521
620 1461990574656829
621 1509585228597810
622 1558690615944735
623 1609353493368294
624 1661622028977727
625 1715545849500083
626 1771176071054424
627 1828565349817747
628 1887767932547569
629 1948839690663859
630 2011838175643107
631 2076822673149061
632 2143854240767837
633 2212995768498495
634 2284312036779760
635 2357869758256036
636 2433737643762446
637 2511986464559628
638 2592689098538919
639 2675920602132394
640 2761758277097542
641 2850281721604346
642 2941572908529707
643 3035716257167332
644 3132798689681315
645 3232909716274612
646 3336141512232103
647 3442588980269267
648 3552349843103008
649 3665524726271412
650 3782217226947456
651 3902534014483247
652 4026584919492832
653 4154483009746325
654 4286344699299445
655 4422289844371241
656 4562441826989865
657 4706927673361715
658 4855878157121493
659 5009427891460224
660 5167715457439265
661 5330883515240708
662 5499078905564938
663 5672452788651613
664 5851160764217879
665 6035362982974319
666 6225224297170366
667 6420914389971795
668 6622607898017364
669 6830484574364683
670 7044729428122781
671 7265532859049740
672 7493090833845223
673 7727605036923629
674 7969283018130667
675 8218338383404431
676 8474990957656513
677 8739466946769190
678 9011999143721998
679 9292827104637342
680 9582197326316019
681 9880363469007907
682 10187586546767847
683 10504135121891096
684 10830285545601744
685 11166322163961114
686 11512537530669401
687 11869232667048069
688 12236717284854849
689 12615310019030604
690 13005338708455044
691 13407140637143332
692 13821062788646337
693 14247462149169822
694 14686705968752211
695 15139172039163576
696 15605249021106852
697 16085336727110900
698 16579846424912676
699 17089201190599515
700 17613836215102501
701 18154199135197965
702 18710750414592154
703 19283963676063469
704 19874326062391816
705 20482338647538410
706 21108516796656252
707 21753390559438806
708 22417505113721715
709 23101421155764899
710 23805715328699007
711 24530980701065529
712 25277827189979347
713 26046882027554559
714 26838790277094219
715 27654215291963744
716 28493839223106023
717 29358363575801146
718 30248509707312348
719 31165019378844993
720 32108655356031708
721 33080201948662928
722 34080465610696302
723 35110275587878296
724 36170484503150139
725 37261969008584988
726 38385630483823924
727 39542395671046863
728 40733217383018479
729 41959075256302876
730 43220976440001666
731 44519956364415573
732 45857079553321327
733 47233440371017264
734 48650163856446065
735 50108406599163132
736 51609357549603729
737 53154238923877642
738 54744307148419587
739 56380853738794981
740 58065206280780829
741 59798729449078078
742 61582825960396902
743 63418937636870638
744 65308546504643681
745 67253175827431220
746 69254391258767534
747 71313802026750409
748 73433062054770781
749 75613871209586722
750 77857976578995065
751 80167173686966694
752 82543307845075734
753 84988275530397991
754 87504025702856563
755 90092561268113177
756 92755940563577062
757 95496278786377057
758 98315749576430091
759 101216586619074457
760 104201085192753846
761 107271603881633298
762 110430566304035691
763 113680462789642963
764 117023852231749676
765 120463363951395038
766 124001699514649776
767 127641634735368515
768 131386021685694472
769 135237790664821238
770 139199952363917364
771 143275600034529487
772 147467911621101558
773 151780152100621638
774 156215675821346595
775 160777928812320925
776 165470451311254911
777 170296880286957905
778 175260951940117700
779 180366504433948389
780 185617480614773002
781 191017930719419415
782 196572015324265517
783 202284008279548052
784 208158299639922736
785 214199398848705323
786 220411937902689805
787 226800674523699809
788 233370495596100971
789 240126420580208897
790 247073604944016197
791 254217343873423926
792 261563075953732042
793 269116386882185889
794 276883013471830441
795 284868847622095801
796 293079940334391549
797 301522506032052337
798 310202926842648325
799 319127756940556331
800 328303727207166232
801 337737749849284042
802 347436923094417524
803 357408536217239347
804 367660074520339167
805 378199224409902293
806 389033878816368254
807 400172142565820043
808 411622337865835686
809 423393010150371400
810 435492933872236041
811 447931118431153616
812 460716814475165090
813 473859520146957113
814 487368987488579221
815 501255229234086913
816 515528525545012851
817 530199430928761210
818 545278781559803648
819 560777702542288162
820 576707615381919466
821 593080245875803064
822 609907631943069967
823 627202131693043891
824 644976431926840607
825 663243556579981305
826 682016875432837100
827 701310113270322744
828 721137358983819713
829 741513074973310971
830 762452107014952314
831 783969694073224387
832 806081478447862995
833 828803516402792230
834 852152288743262447
835 876144711764640259
836 900798148700188227
837 926130421122061666
838 952159820753248277
839 978905121795970483
840 1006385593219857736
841 1034621011502858884
842 1063631673906620780
843 1093438411719925651
844 1124062603999283760
845 1155526191862556586
846 1187851692760842386
847 1221062215294694402
848 1255181474602559728
849 1290233807739759926
850 1326244189651869165
851 1363238249740228923
852 1401242288432560578
853 1440283294401030428
854 1480388962393176256
855 1521587711085005434
856 1563908701637728130
857 1607381856888949665
858 1652037880585853356
859 1697908277381502630
860 1745025373488173509
861 1793422337395456172
862 1843133201414413006
863 1894192883902456063
864 1946637211578990058
865 2000502942733629732
866 2055827791140071554
867 2112650450090252535
868 2171010617391345246
869 2230949021094702122
870 2292507445378422639
871 2355728757466970284
872 2420656935310554085
873 2487337095455554358
874 2555815522030355758
875 2626139696520481665
876 2698358327776610272
877 2772521383220662548
878 2848680120872639131
879 2926887121656979617
880 3007196322994164450
881 3089663053246608821
882 3174344066495886891
883 3261297578697130858
884 3350583304723596370
885 3442262495799879534
886 3536397978409245590
887 3633054194129614084
888 3732297239921444199
889 3834194909991887055
890 3938816738628973769
891 4046234043557359900
892 4156519970977969768
893 4269749541622213203
894 4385999697404286286
895 4505349349870798107
896 4627879429713000729
897 4753672936960947497
898 4882814993094500130
899 5015392894268865075
900 5151496165313731645
901 5291216615775164805
902 5434648397128236283
903 5581888060863351930
904 5733034618747962891
905 5888189604319890826
906 6047457135363447036
907 6210943978700692848
908 6378759616280322062
909 6551016312368003546
910 6727829183199146067
911 6909316268000968403
912 7095598601244911467
913 7286800287516653868
914 7483048577833332005
915 7684473947330930394
916 7891210175732804339
917 8103394429350065481
918 8321167344603634027
919 8544673114499831148
920 8774059576729881036
921 9009478303454963969
922 9251084694226616552
923 9499038070631203179
924 9753501772797024598
925 10014643259228481537
926 10282634208473326092
927 10557650622843743650
928 10839872935666691643
929 11129486120485944764
930 11426679802524172543
931 11731648373887664805
932 12044591110851836151
933 12365712293628877336
934 12695221330103329012
935 13033332881788923946
936 13380266992506621182
937 13736249221268407443
938 14101510777535254946
939 14476288659453381710
940 14860825796547479227
941 15255371194954393515
942 15660180085911420256
943 16075514078967028692
944 16501641317912887768
945 16938836640267154753
946 17387381741760844641
947 17847565343742171627
948 18319683364450412557
949 18804039095589626305
950 19300943382034134473
951 19810714805744812668
952 20333679875299187474
953 20870173218785548428
954 21420537781273616371
955 21985125028231339573
956 22564295152557926921
957 23158417286585085484
958 23767869720376313011
959 24393040123916281573
960 25034325774687576430
961 25692133791918281505
962 26366881375016853289
963 27058996047842771841
964 27768915910043109336
965 28497089892898693043
966 29243978021485546162
967 30010051684321181176
968 30795793907869864927
969 31601699637875582810
970 32428276028624290176
971 33276042737443749663
972 34145532226578432041
973 35037290073465329984
974 35951875286657443686
975 36889860629706858976
976 37851832953949441632
977 38838393537381078895
978 39850158432117487161
979 40887758821287518700
980 41951841382498226990
981 43043068660549260762
982 44162119450146005364
983 45309689185703815059
984 46486490341111701366
985 47693252840095639456
986 48930724474234319407
987 50199671331691656336
988 51500878237187912128
989 52835149200229659723
990 54203307874863873304
991 55606198031350526874
992 57044684036748768374
993 58519651347887644459
994 60032007016979032855
995 61582680206850800035
996 63172622719481270784
997 64802809537946418885
998 66474239378749589966
999 68187935258429199576
1000 69944945074399793582