0 1
1 1
2 1
3 1
4 2
5 3
6 3
7 3
8 5
9 7
10 9
11 9
12 11
13 15
14 19
15 21
16 25
17 31
18 39
19 45
20 53
21 63
22 75
23 87
24 103
25 121
26 143
27 165
28 193
29 225
30 263
31 301
32 347
33 401
34 467
35 535
36 613
37 701
38 807
39 921
40 1053
41 1197
42 1365
43 1551
44 1767
45 2003
46 2269
47 2563
48 2905
49 3281
50 3705
51 4167
52 4697
53 5285
54 5947
55 6669
56 7485
57 8387
58 9401
59 10511
60 11761
61 13137
62 14669
63 16349
64 18237
65 20313
66 22613
67 25127
68 27941
69 31039
70 34465
71 38199
72 42349
73 46915
74 51963
75 57467
76 63547
77 70217
78 77579
79 85607
80 94455
81 104131
82 114775
83 126381
84 139141
85 153079
86 168365
87 185009
88 203271
89 223191
90 244999
91 268715
92 294657
93 322915
94 353801
95 387367
96 424005
97 463837
98 507289
99 554477
100 605899
101 661719
102 722479
103 788389
104 860115
105 937889
106 1022393
107 1113937
108 1213399
109 1321137
110 1438027
111 1564497
112 1701675
113 1850101
114 2010923
115 2184755
116 2373019
117 2576473
118 2796615
119 3034319
120 3291431
121 3568977
122 3868887
123 4192387
124 4541857
125 4918735
126 5325475
127 5763741
128 6236599
129 6746037
130 7295251
131 7886453
132 8523531
133 9209209
134 9947635
135 10741803
136 11596641
137 12515765
138 13504559
139 14567053
140 15709537
141 16936791
142 18255699
143 19671667
144 21192733
145 22825209
146 24577901
147 26457939
148 28475579
149 30639135
150 32959891
151 35447193
152 38114059
153 40971373
154 44033569
155 47312915
156 50825913
157 54586693
158 58613651
159 62922793
160 67535109
161 72468859
162 77747377
163 83391455
164 89427735
165 95879827
166 102777265
167 110146847
168 118022333
169 126434157
170 135419717
171 145013411
172 155257859
173 166192139
174 177863553
175 190316169
176 203603707
177 217776111
178 232893083
179 249010899
180 266197221
181 284515659
182 304041367
183 324846007
184 347014639
185 370628153
186 395780983
187 422564003
188 451083967
189 481443409
190 513760907
191 548151375
192 584748459
193 623681787
194 665099971
195 709148091
196 755993173
197 805798541
198 858750085
199 915030531
200 974848413
201 1038408931
202 1105944121
203 1177683567
204 1253887229
205 1334812457
206 1420748311
207 1511982435
208 1608838379
209 1711638177
210 1820741473
211 1936507793
212 2059339047
213 2189637389
214 2327849481
215 2474423845
216 2629858977
217 2794655815
218 2969368215
219 3154554567
220 3350832307
221 3558824167
222 3779215585
223 4012700339
224 4260042029
225 4522013443
226 4799461541
227 5093246383
228 5404310819
229 5733612079
230 6082195289
231 6451124537
232 6841562031
233 7254691277
234 7691799989
235 8154202501
236 8643329173
237 9160640443
238 9707720469
239 10286189869
240 10897806633
241 11544369663
242 12227824719
243 12950166593
244 13713552873
245 14520195817
246 15372481789
247 16272861819
248 17223979977
249 18228552417
250 19289501955
251 20409835195
252 21592787579
253 22841688523
254 24160112751
255 25551742909
256 27020532507
257 28570555931
258 30206179143
259 31931905757
260 33752560553
261 35673121871
262 37698914241
263 39835437057
264 42088570347
265 44464388307
266 46969375819
267 49610237821
268 52394130875
269 55328455501
270 58421099561
271 61680226031
272 65114533387
273 68733025203
274 72545283491
275 76561232617
276 80791431611
277 85246818849
278 89939019119
279 94880081767
280 100082808497
281 105560470083
282 111327151623
283 117397462537
284 123786904219
285 130511556317
286 137588463777
287 145035316329
288 152870861179
289 161114555961
290 169787002865
291 178909593757
292 188504973483
293 198596657353
294 209209517263
295 220369389917
296 232103595789
297 244440517989
298 257410147519
299 271043650867
300 285373951679
301 300435266571
302 316263716859
303 332896852759
304 350374304605
305 368737272627
306 388029211897
307 408295309799
308 429583215531
309 451942479925
310 475425322709
311 500086058323
312 525981913309
313 553172412843
314 581720239819
315 611690605249
316 643152163077
317 676176339235
318 710838294189
319 747216233929
320 785392433625
321 825452504201
322 867486470689
323 911588020219
324 957855647405
325 1006391854123
326 1057304356327
327 1110705265085
328 1166712368803
329 1225448261521
330 1287041694073
331 1351626682007
332 1419343941803
333 1490339944079
334 1564768425195
335 1642789418971
336 1724570863231
337 1810287573881
338 1900122937589
339 1994267861747
340 2092922572943
341 2196295506033
342 2304605199665
343 2418079161779
344 2536955881965
345 2661483632077
346 2791922587827
347 2928543605717
348 3071630476059
349 3221478631683
350 3378397522367
351 3542709298733
352 3714751335443
353 3894874845113
354 4083447536733
355 4280852203349
356 4487489546447
357 4703776693179
358 4930150173703
359 5167064410793
360 5414994882065
361 5674436536813
362 5945907132119
363 6229945624421
364 6527115709481
365 6838004139383
366 7163224458835
367 7503415299193
368 7859244344207
369 8231406546991
370 8620628316489
371 9027665713485
372 9453308894961
373 9898380235125
374 10363739016129
375 10850279531115
376 11358936063299
377 11890680916767
378 12446529674537
379 13027539214823
380 13634813291717
381 14269500480271
382 14932800073617
383 15625960022751
384 16350283192533
385 17107125233211
386 17897901192667
387 18724083393257
388 19587208448955
389 20488875077815
390 21430751518845
391 22414573361053
392 23442151416569
393 24515369496407
394 25636192731423
395 26806665376313
396 28028919644345
397 29305173471381
398 30637739856529
399 32029024670239
400 33481536570579
401 34997884786323
402 36580789606151
403 38233080228649
404 39957705896089
405 41757733738063
406 43636360550699
407 45596910735125
408 47642848803705
409 49777777334443
410 52005450205437
411 54329770672943
412 56754805426237
413 59284782715803
414 61924107226555
415 64677358366309
416 67549306061077
417 70544909133445
418 73669332025417
419 76927943379729
420 80326333798587
421 83870314559121
422 87565936423707
423 91419488615601
424 95437518792121
425 99626832206975
426 103994512872007
427 108547923047355
428 113294725715041
429 118242884319103
430 123400686581335
431 128776744645071
432 134380020372365
433 140219825819755
434 146305850048099
435 152648160092085
436 159257229440957
437 166143939434183
438 173319609456259
439 180795998930989
440 188585339399749
441 196700337051191
442 205154206739433
443 213960675244037
444 223134017410107
445 232689060071283
446 242641220383639
447 253006510630349
448 263801578953597
449 275043714974585
450 286750893004653
451 298941778717459
452 311635775073965
453 324853029994143
454 338614485082067
455 352941884550585
456 367857827009829
457 383385775609449
458 399550112997713
459 416376152948165
460 433890198779867
461 452119556447155
462 471092596552271
463 490838769199313
464 511388669911365
465 532774056235697
466 555027917728047
467 578184494642341
468 602279352332303
469 627349402026171
470 653432979829885
471 680569869956399
472 708801388723879
473 738170410267253
474 768721455742329
475 800500721916439
476 833556176019759
477 867937587276155
478 903696627652763
479 940886906763083
480 979564078999397
481 1019785881898063
482 1061612249957345
483 1105105356953393
484 1150329736969409
485 1197352330779805
486 1246242614446801
487 1297072650323379
488 1349917223810503
489 1404853899123621
490 1461963164617443
491 1521328493930909
492 1583036500549829
493 1647177004529569
494 1713843196751105
495 1783131711897385
496 1855142803159773
497 1929980421728363
498 2007752402477927
499 2088570550717743
500 2172550839697213
501 2259813504938679
502 2350483254180847
503 2444689370136647
504 2542565933801801
505 2644251936024675
506 2749891514896209
507 2859634077079121
508 2973634550325957
509 3092053515028497
510 3215057472675485
511 3342818988682799
512 3475516977971961
513 3613336859653513
514 3756470860640619
515 3905118183354649
516 4059485328709249
517 4219786277531755
518 4386242833971123
519 4559084821935047
520 4738550450405607
521 4924886525716939
522 5118348839998945
523 5319202400762155
524 5527721844116427
525 5744191682623397
526 5968906744690861
527 6202172442354733
528 6444305238698649
529 6695632936678945
530 6956495176166151
531 7227243745673201
532 7508243111107831
533 7799870751723783
534 8102517722382437
535 8416589015807973
536 8742504160708383
537 9080697611880613
538 9431619386253601
539 9795735483167969
540 10173528560968575
541 10565498389256545
542 10972162568386619
543 11394057016327367
544 11831736733996909
545 12285776328789405
546 12756770828441151
547 13245336244201107
548 13752110436531833
549 14277753720291491
550 14822949785310359
551 15388406346937009
552 15974856125221299
553 16583057543570787
554 17213795769970407
555 17867883467506231
556 18546161901822577
557 19249501746689453
558 19978804261598971
559 20735002156586695
560 21519060844680221
561 22331979369621857
562 23174791737608841
563 24048567912677677
564 24954415233005651
565 25893479478124527
566 26866946374826359
567 27876042741576891
568 28922038089958003
569 30006245851041747
570 31130025078066089
571 32294781760814281
572 33501970636208889
573 34753096596158087
574 36049716612496903
575 37393441245086523
576 38785936688622405
577 40228926387241647
578 41724193210481347
579 43273581182021175
580 44878997793227981
581 46542415853158663
582 48265875947951619
583 50051488420707293
584 51901435986168297
585 53817975848572859
586 55803442480977415
587 57860249890799947
588 59990894574410629
589 62197957939550255
590 64484109445741389
591 66852109194529311
592 69304811267665065
593 71845166495636253
594 74476226005504733
595 77201144180028269
596 80023182428602307
597 82945712348871985
598 85972219734193425
599 89106307951571127
600 92351702200733675
601 95712253121889059
602 99191941321573689
603 102794881225821583
604 106525325889711697
605 110387671111222667
606 114386460541578001
607 118526390077363659
608 122812313290691629
609 127249246116854201
610 131842372623565365
611 136597050013921939
612 141518814756105685
613 146613387921239017
614 151886681695203713
615 157344805073598067
616 162994070779704343
617 168841001338722579
618 174892336426289771
619 181155039346939503
620 187636304840125147
621 194343565987976335
622 201284502506323425
623 208467048109831385
624 215899399318235901
625 223590023307142943
626 231547667260438851
627 239781366738349471
628 248300455609933403
629 257114574970302839
630 266233683688019641
631 275668067906978631
632 285428352246777315
633 295525509925288605
634 305970874651105615
635 316776151406672171
636 327953429075521619
637 339515191926602943
638 351474333020292367
639 363844166438670939
640 376638441518189871
641 389871355871690511
642 403557570497167969
643 417712223641839855
644 432350946840651285
645 447489879673913429
646 463145686791114595
647 479335573618646129
648 496077304429061733
649 513389219056865135
650 531290252075570537
651 549799950584986023
652 568938494563533913
653 588726715792284375
654 609186119452464707
655 630338904257395767
656 652207985370798175
657 674817015820050065
658 698190410813769193
659 722353370516170679
660 747331905848618369
661 773152862707594987
662 799843949338276793
663 827433762085651117
664 855951814434899741
665 885428564388337029
666 915895445271367045
667 947384894835642313
668 979930387936763751
669 1013566467467702051
670 1048328779018913967
671 1084254103754559133
672 1121380395173922919
673 1159746814047277089
674 1199393767402571607
675 1240362945646978673
676 1282697363911944121
677 1326441401491576329
678 1371640845684931189
679 1418342933692411683
680 1466596399104173453
681 1516451516401633749
682 1567960150247574381
683 1621175802750901189
684 1676153665724929297
685 1732950670880270961
686 1791625545225502693
687 1852238864365278061
688 1914853111229590557
689 1979532732661851051
690 2046344201671676469
691 2115356077511153155
692 2186639071659397013
693 2260266111594025443
694 2336312410725513377
695 2414855536085624207
696 2495975482444381145
697 2579754744147334417
698 2666278393659024039
699 2755634157797107081
700 2847912500962475309
701 2943206706029804065
702 3041612962537069045
703 3143230452509948551
704 3248161443901333617
705 3356511381640016035
706 3468388986625081467
707 3583906352309100957
708 3703179049572045023
709 3826326229163817127
710 3953470732798371329
711 4084739201802297011
712 4220262194791727651
713 4360174302890325901
714 4504614274369477569
715 4653725136823018153
716 4807654329175580861
717 4966553831220290789
718 5130580303420241721
719 5299895224241797669
720 5474665038201043087
721 5655061301446685897
722 5841260838526032799
723 6033445896700678809
724 6231804311936144839
725 6436529672457480487
726 6647821494492308627
727 6865885395605830447
728 7090933280759699633
729 7323183525992770241
730 7562861175386906739
731 7810198135695562579
732 8065433384843893221
733 8328813178137546519
734 8600591268956386953
735 8881029127215263691
736 9170396172950922527
737 9468970007740609887
738 9777036661917531339
739 10094890839696558777
740 10422836180798072869
741 10761185520068335013
742 11110261164331681101
743 11470395167341228415
744 11841929622728415619
745 12225216955162436771
746 12620620230311188639
747 13028513463141154137
748 13449281945858018731
749 13883322574326448497
750 14331044195008922811
751 14792867950543862797
752 15269227646761357715
753 15760570118511559579
754 16267355617891923609
755 16790058201482917213
756 17329166140988108815
757 17885182333094139723
758 18458624733787383185
759 19050026792127026145
760 19659937909575820711
761 20288923899042074077
762 20937567470631695913
763 21606468717394560121
764 22296245628986522193
765 23007534605630155221
766 23740991001253293029
767 24497289667262392701
768 25277125526814309945
769 26081214150083582885
770 26910292361410796401
771 27765118847842765565
772 28646474801000769311
773 29555164560765302429
774 30492016293803736717
775 31457882674379172741
776 32453641601587855963
777 33480196919375133159
778 34538479174640076019
779 35629446378660693181
780 36754084808345732623
781 37913409811386564063
782 39108466653055489767
783 40340331367533656225
784 41610111652790467939
785 42918947770665025863
786 44268013492494202147
787 45658517050671185751
788 47091702137839432059
789 48568848912794286873
790 50091275056207733557
791 51660336833900736539
792 53277430212229416501
793 54943991981914223727
794 56661500936382057919
795 58431479059516962259
796 60255492770436279903
797 62135154178703859669
798 64072122399200301731
799 66068104878537084301
800 68124858783883888249
801 70244192404517928065
802 72427966618673598647
803 74678096374379771063
804 76996552238621166625
805 79385361961833683517
806 81846612113891606193
807 84382449736872819273
808 86995084072633843785
809 89686788308697826233
810 92459901402428620401
811 95316829925161826509
812 98260049988263416059
813 101292109190891780709
814 104415628653502445513
815 107633305074924450561
816 110947912879176290131
817 114362306387837048611
818 117879422086344698359
819 121502280917968758725
820 125233990676097603257
821 129077748426448906725
822 133036843032191966627
823 137114657711393068101
824 141314672702189383749
825 145640467962831374901
826 150095725984501111253
827 154684234641712883191
828 159409890160778220125
829 164276700128730152753
830 169288786625853960399
831 174450389401741476769
832 179765869180759237601
833 185239711014287283431
834 190876527768457478711
835 196681063662118195421
836 202658197946675995993
837 208812948639823934427
838 215150476407830245811
839 221676088505605702427
840 228395242872335607093
841 235313552289011245393
842 242436788698866562843
843 249770887594092893605
844 257321952573151767577
845 265096259968999971237
846 273100263655975537933
847 281340599932516611265
848 289824092590991251419
849 298557758068565923461
850 307548810794041598443
851 316804668621252575151
852 326332958467715405409
853 336141522045682539607
854 346238421808175206667
855 356631946993616470011
856 367330619895640903631
857 378343202238054342129
858 389678701785658367503
859 401346379067166971165
860 413355754345190846941
861 425716614705650619943
862 438439021406000248865
863 451533317350651250043
864 465010134837514974441
865 478880403439957010099
866 493155358172770840235
867 507846547802257459311
868 522965843453846828371
869 538525447373007627993
870 554537901997873505289
871 571016099194875000013
872 587973289820945755945
873 605423093458994829987
874 623379508495527158607
875 641856922382383599857
876 660870122256954145155
877 680434305757967376043
878 700565092216864922471
879 721278534056865678911
880 742591128585552361783
881 764519830007931064131
882 787082061851815414689
883 810295729627194319585
884 834179233917633148379
885 858751483719912528301
886 884031910236360073179
887 910040480930478905553
888 936797714056924691497
889 964324693470663023973
890 992643083933175498397
891 1021775146714620702675
892 1051743755716838819919
893 1082572413909999607413
894 1114285270315036039951
895 1146907137318395602655
896 1180463508558722463995
897 1214980577165544145111
898 1250485254597294392221
899 1287005189852117546517
900 1324568789306736157481
901 1363205236949998597301
902 1402944515274601619207
903 1443817426586596541867
904 1485855615004633461493
905 1529091588901334407029
906 1573558744067488935281
907 1619291387344055939955
908 1666324761011666385309
909 1714695067674983299043
910 1764439495940912311037
911 1815596246620192039823
912 1868204559760935834047
913 1922304742235595573943
914 1977938196199812208269
915 2035147448136356226409
916 2093976178812813867185
917 2154469253857711195897
918 2216672755294257633513
919 2280634013727670009625
920 2346401641536102282049
921 2414025566752155395215
922 2483557067996191627429
923 2555048810139209802493
924 2628554881068042845245
925 2704130829221148663477
926 2781833702279671091199
927 2861722086672312812283
928 2943856148290972026845
929 3028297674065675703137
930 3115110114808437922129
931 3204358628964311181741
932 3296110127692319778889
933 3390433320903984052821
934 3487398764695611561341
935 3587078909791237211921
936 3689548151446284375503
937 3794882880417693920675
938 3903161535464942019685
939 4014464656976277634705
940 4128874942199385489693
941 4246477301659066545577
942 4367358917256408372711
943 4491609301620003676847
944 4619320359219419666747
945 4750586448799106129597
946 4885504447659187347599
947 5024173817328645562631
948 5166696671174077808833
949 5313177843476501506351
950 5463724960536671893849
951 5618448513328030045427
952 5777461932275552785283
953 5940881663665898039591
954 6108827248285503394031
955 6281421401777967852891
956 6458790097336322624237
957 6641062650207071956863
958 6828371804641172487683
959 7020853822754029390703
960 7218648575949839119091
961 7421899638357151611279
962 7630754382951797408981
963 7845364079798476788167
964 8065883997108609052579
965 8292473504529744535175
966 8525296179386286144735
967 8764519915270441035949
968 9010317033725976833135
969 9262864398406884348737
970 9522343532477089256855
971 9788940738616091843309
972 10062847222420969254513
973 10344259218551941105749
974 10633378120437011637845
975 10930410612864790624045
976 11235568808306857163395
977 11549070386280194856547
978 11871138736617750345677
979 12202003105938632305911
980 12541898748213513900637
981 12891067078697250082469
982 13249755832152674988137
983 13618219224617628776501
984 13996718119668458028433
985 14385520198411564726443
986 14784900134186475167353
987 15195139771191054447409
988 15616528308043499620653
989 16049362485470255568521
990 16493946779166658489223
991 16950593596997475451529
992 17419623481617313844915
993 17901365317655540932641
994 18396156544579930198655
995 18904343374360635390571
996 19426281015084015283085
997 19962333899614297088081
998 20512875920489051290573
999 21078290670122323072223
1000 21658971687538977113769