0 0
1 1
2 2
3 6
4 6
5 11
6 16
7 35
8 36
9 46
10 50
11 84
12 94
13 130
14 158
15 285
16 338
17 424
18 460
19 616
20 672
21 810
22 816
23 1162
24 1346
25 1680
26 1754
27 2308
28 2562
29 3164
30 3288
31 4486
32 5306
33 6838
34 7522
35 9627
36 11006
37 13496
38 14200
39 17462
40 19682
41 24036
42 25650
43 30842
44 33884
45 40302
46 41644
47 48896
48 53292
49 64006
50 67750
51 80329
52 87938
53 105238
54 110118
55 128026
56 138180
57 164551
58 173724
59 202406
60 218106
61 258218
62 269658
63 308972
64 328128
65 386488
66 407022
67 470854
68 505536
69 600626
70 636652
71 733622
72 784448
73 925922
74 988004
75 1142718
76 1229270
77 1450583
78 1551162
79 1777476
80 1895156
81 2205858
82 2352272
83 2687564
84 2870490
85 3340156
86 3574158
87 4069468
88 4329668
89 4990550
90 5328866
91 6048930
92 6438196
93 7407726
94 7920538
95 8954146
96 9483642
97 10797472
98 11475676
99 12894778
100 13612566
101 15455802
102 16432660
103 18438060
104 19423606
105 21927982
106 23239184
107 26001254
108 27362564
109 30869120
110 32775708
111 36687756
112 38597802
113 43354318
114 45884584
115 51165204
116 53691840
117 60163409
118 63679162
119 71001458
120 74499406
121 83224192
122 87889224
123 97738082
124 102382870
125 114185662
126 120647582
127 134242230
128 140731622
129 156621838
130 165159914
131 183217848
132 191584854
133 212568150
134 223855116
135 248119750
136 259358442
137 287138110
138 301743394
139 333598986
140 347916570
141 384274742
142 403416154
143 445993566
144 465404994
145 513684977
146 538791288
147 594763422
148 619677384
149 682527638
150 715014020
151 788951162
152 822232672
153 905051844
154 947426510
155 1044166503
156 1086976946
157 1194502858
158 1249368970
159 1376843632
160 1434607554
161 1576855880
162 1649721310
163 1817299046
164 1892978672
165 2077922560
166 2172316034
167 2391616612
168 2492518378
169 2735207364
170 2859269116
171 3145281446
172 3276328508
173 3589656492
174 3748772880
175 4119993300
176 4293212106
177 4702719434
178 4912308416
179 5396093328
180 5622883550
181 6151826722
182 6421360044
183 7046580862
184 7344335232
185 8031565236
186 8384160266
187 9194058211
188 9581576628
189 10464840944
190 10915609186
191 11955659128
192 12460554994
193 13603087136
194 14192550354
195 15537845820
196 16198630986
197 17668724786
198 18426970068
199 20151997276
200 21011623826
201 22906188994
202 23893491174
203 26113580472
204 27231506246
205 29656762226
206 30917680058
207 33744530914
208 35181797804
209 38284059172
210 39910813748
211 43527863662
212 45387162698
213 49345270106
214 51419527026
215 56008050454
216 58385870392
217 63423299238
218 66081244616
219 71918570734
220 74970326488
221 81361840762
222 84726142616
223 92083870790
224 95946027820
225 104022398904
226 108292370624
227 117595673258
228 122520328068
229 132729210564
230 138124356528
231 149818152216
232 156034965988
233 168893346408
234 175720473764
235 190452354388
236 198348063814
237 214544417530
238 223141628970
239 241582959250
240 251488364632
241 271779342884
242 282578753570
243 305685041558
244 318181240920
245 343631036340
246 357184417658
247 386016365163
248 401641554028
249 433416739082
250 450382116876
251 486374589662
252 506001724358
253 545711803696
254 566928910220
255 611674583198
256 636087789344
257 685434750066
258 711819891706
259 767394958366
260 797855094310
261 859251195516
262 892111799956
263 960979769142
264 998750044414
265 1074819058662
266 1115580454838
267 1200871629652
268 1247867166200
269 1342258412864
270 1392939608860
271 1498382879612
272 1556512741862
273 1673103217806
274 1735738453110
275 1865848727088
276 1937831091156
277 2081966469302
278 2159565593688
279 2319947456774
280 2408729681856
281 2586265549126
282 2681923521570
283 2879278008624
284 2988890683920
285 3207755348156
286 3325993208036
287 3568665487205
288 3703501740286
289 3972279356366
290 4117495020298
291 4415043552640
292 4580680713278
293 4910711930224
294 5089365754222
295 5453981744432
296 5656924280990
297 6060901461630
298 6279541175890
299 6725238344336
300 6973643131080
301 7468183186033
302 7736394934990
303 8281184444278
304 8584771397428
305 9188522755474
306 9515809160836
307 10179780334258
308 10549909443610
309 11286488779152
310 11686363580700
311 12495445399946
312 12946196253114
313 13842769717688
314 14329149898530
315 15312467152726
316 15860202792176
317 16950889631970
318 17543416933992
319 18738710264410
320 19404124108558
321 20728468027176
322 21447289814890
323 22896146314240
324 23701914862092
325 25307905248980
326 26180158538120
327 27935967846298
328 28911233041470
329 30855419557254
330 31909898338502
331 34032117339502
332 35208965446922
333 37559757330960
334 38835194187130
335 41400562272388
336 42821312829176
337 45660500568116
338 47198790671374
339 50292430864208
340 52002166643252
341 55426102029228
342 57280940232006
343 61010962108786
344 63069023439588
345 67193907735613
346 69424945135568
347 73912506121584
348 76382584450698
349 81344945226284
350 84028211579822
351 89427327155256
352 92394725692088
353 98361340793996
354 101583395896756
355 108067208807678
356 111621984805144
357 118784827291800
358 122650890715060
359 130434869190232
360 134695294893722
361 143288745527200
362 147920255037130
363 157248309456052
364 162340007793356
365 172633220743376
366 178176765404440
367 189351997734328
368 195441981527714
369 207767413339316
370 214397184737756
371 227766198797248
372 235032423330262
373 249767982390330
374 257687358134280
375 273672877196724
376 282346334844098
377 299956702529610
378 309409062320772
379 328497144440590
380 338825855092668
381 359838655210910
382 371106124084416
383 393887417372816
384 406194687341138
385 431263694661520
386 444692615569124
387 471854327772954
388 486491902972376
389 516356744175274
390 532339536357600
391 564702922648686
392 582116573006498
393 617685374026582
394 636702233616926
395 675224239853480
396 695900751984160
397 738198925863780
398 760788881963000
399 806606322807854
400 831160538022732
401 881451383503638
402 908287188137576
403 962740326352372
404 991857133106054
405 1051570791301998
406 1083400707548274
407 1148064112194044
408 1182588948894626
409 1253471534923596
410 1291224225112922
411 1367955547728804
412 1408834919384596
413 1492862805764418
414 1537565096124042
415 1628534839817602
416 1676929504580704
417 1776516845966506
418 1829460795697300
419 1937256157791864
420 1994495006622312
421 2112391791763784
422 2175007291650272
423 2302631226805602
424 2370314245225088
425 2509848966345173
426 2583917873846218
427 2734944030145618
428 2814906776940530
429 2979868580372034
430 3067351279214440
431 3245901926532646
432 3340329572465738
433 3535289198468884
434 3638640460812372
435 3849653810398800
436 3961101652122024
437 4191301338264108
438 4313240795518734
439 4562397539164428
440 4693870865167894
441 4965586021277096
442 5109485975974162
443 5403576082035358
444 5558595274106808
445 5879025087957564
446 6048611994442984
447 6395409455964486
448 6578070435848140
449 6955792538238140
450 7155685739752786
451 7564519263557674
452 7779696944425058
453 8224629194772730
454 8459991779777140
455 8941547899203218
456 9194880059045842
457 9718770534811382
458 9995943046043330
459 10563007719796662
460 10861203941841160
461 11477637008358588
462 11803695095598152
463 12470854578313812
464 12821587861731690
465 13546552596876900
466 13930129628403372
467 14714839133379992
468 15127325672474268
469 15979420922724360
470 16430258338433646
471 17352468143634548
472 17837222641394792
473 18838243669161062
474 19368129097912706
475 20451636445086074
476 21021274904199174
477 22196577774118307
478 22818813560117036
479 24090743735036288
480 24759534418101676
481 26138653181682696
482 26869201749686532
483 28361855296255342
484 29147005183069632
485 30764461655440904
486 31621538629731326
487 33371855515357338
488 34292861492906860
489 36188772241756788
490 37194111553698006
491 39245958554604804
492 40326305983590524
493 42547576145222386
494 43726016563332332
495 46129487032450913
496 47395618345713230
497 49996450582216404
498 51377338943851620
499 54191705744353496
500 55675475810226980
501 58719400689753412
502 60336558543218426
503 63629717994994936
504 65367102671312488
505 68927431134870304
506 70820637179413130
507 74672705678685828
508 76706957208198284
509 80869612064711128
510 83084792082774096
511 87587486346764746
512 89967259773875202
513 94830938260700376
514 97421605134327770
515 102682680012949202
516 105466308449442876
517 111146790361644452
518 114175119301340068
519 120318306327867068
520 123571706916960576
521 130201963062421880
522 133740232207821284
523 140910596546176286
524 144712669152748734
525 152448690119119992
526 156581081884440570
527 164945249558500746
528 169385024965758768
529 178405370353699338
530 183228963210380274
531 192981389588283910
532 198164894662539012
533 208678883135987560
534 214307126621718036
535 225671643506911196
536 231719001971361538
537 243966261243998956
538 250529760698863038
539 263767045907117452
540 270820976009184000
541 285082263721638650
542 292733901165269578
543 308144148504997932
544 316366309582521228
545 332962267754412258
546 341876874516813994
547 359808113736432634
548 369389367827564570
549 388694966564587676
550 399077402476760504
551 419930952508006919
552 431088269378307084
553 453531948675554112
554 465616347868985534
555 489856744982719518
556 502845775700180460
557 528928280512823696
558 542989436661136618
559 571152793131783036
560 586264557820314956
561 616557356927149314
562 632907935286705760
563 665612445040813604
564 683187715158386182
565 718357061410171292
566 737363751907246096
567 775323239800494274
568 795750990171751702
569 836557600857620372
570 858637557585403626
571 902673979951906826
572 926408678039866722
573 973738595183078932
574 999381415001386268
575 1050444482026804598
576 1078005777522961658
577 1132870106279750740
578 1162631107745511280
579 1221810854455759904
580 1253802249890593464
581 1317375238816874778
582 1351904729610384718
583 1420460304883556270
584 1457573051791088146
585 1531195214428983504
586 1571230940260984222
587 1650605919935816420
588 1693641254582669740
589 1778867783463603490
590 1825274012397251296
591 1917136945154889830
592 1967014692380147532
593 2065621311291803794
594 2119377413146854196
595 2225636868580542428
596 2283418046640170608
597 2397459112049857156
598 2459709231210030230
599 2582569682976241240
600 2649473570373461808
601 2781295440582447092
602 2853336645126621034
603 2995317382697384604
604 3072747862057033440
605 3225061772078807160
606 3308408854977779492
607 3472420491647080992
608 3561994047559097072
609 3737897881100007190
610 3834267787523937074
611 4023630998534456212
612 4127201305636531754
613 4330264872943604438
614 4441655927435047690
615 4660202440176080532
616 4779903852026087038
617 5014205946030662098
618 5142883722887603416
619 5394981435296327070
620 5533257204284645354
621 5803491696827863150
622 5952090746996009928
623 6242779478652310444
624 6402447504967841172
625 6713980691826824368
626 6885490075701245292
627 7220509212708277442
628 7404786045377523344
629 7763779017242857306
630 7961663252545958834
631 8347625755912037484
632 8560219310882488362
633 8973714620825133864
634 9201905592900865822
635 9646337354867110022
636 9891473879996131158
637 10367546341864579014
638 10630595594368577306
639 11142164722947909826
640 11424721571880578918
641 11972606190042453704
642 12275684952194967340
643 12864250772283292754
644 13189776011951842116
645 13820039876340919796
646 14169115160637196390
647 14846014927388130866
648 15220904046042678904
649 15945627043750781422
650 16347478285398364944
651 17125598767171460655
652 17557116528619143258
653 18390101944253172886
654 18852538992708217748
655 19746688367030196102
656 20243213554803844382
657 21200246893052206628
658 21732154259064704512
659 22759161572700851608
660 23330201325088184774
661 24429291536097976766
662 25040876254587708014
663 26220049414612507580
664 26876554340111590890
665 28138285423927719670
666 28841159075053836176
667 30194429614322224060
668 30948811920144929414
669 32396638083904783290
670 33204118299749437588
671 34756626299909220506
672 35623183539342424132
673 37283918410374006192
674 38211174481409646192
675 39991477421715172624
676 40986408011524649680
677 42890566587773710118
678 43954956301917453904
679 45995739228727683752
680 47137672902101525478
681 49320115836554029962
682 50541405356403213396
683 52879776527283376704
684 54189799281638217010
685 56690151498435749732
686 58090917154603158936
687 60769301836122357154
688 62271651643173604948
689 65135177768994688162
690 66741153118365396938
691 69807723096748059110
692 71529832230265989648
693 74807935758552085488
694 76648458341863277892
695 80158209758839002046
696 82131561085223977120
697 85882915359874425030
698 87991414031840518576
699 92006762741019577960
700 94266962175276650916
701 98558127811371738818
702 100972648009020193104
703 105564770006410815626
704 108152645566916926014
705 113059575399081116542
706 115823498546306331444
707 121073183032937549896
708 124034921257813784776
709 129643721879658303808
710 132806350129977404330
711 138805607558672328058
712 142194084922031259278
713 148602927907578036900
714 152220448815659675396
715 159073664727984394569
716 162948657950978686494
717 170268730279222904840
718 174404892886551782562
719 182230803777657332750
720 186660662135683193114
721 195018660351533457058
722 199746135120681125704
723 208679449830706938758
724 213741465329482624512
725 223280811629158744798
726 228681958088503820984
727 238875730310252714608
728 244658145250015309748
729 255542120847116697254
730 261710766304218706848
731 273338553703111202156
732 279941104420452172306
733 292354392004972893478
734 299396718897541417144
735 312655478590556409478
736 320191874554309959722
737 334344583505241212879
738 342381555296558951424
739 357494618669891557180
740 366093428589100710152
741 382223127302455942522
742 391391534482155618588
743 408612098376738698188
744 418419704830094653422
745 436796429882578802232
746 447251998725914758558
747 466867024365841740320
748 478048867121258191628
749 498977724044658820980
750 510896330552633311554
751 533230776895867027976
752 545974934817053975508
753 569802432530996107818
754 583384219245784908888
755 608806303379025044754
756 623325393320956748314
757 650442926622133404928
758 665913807462844791028
759 694840148880249421624
760 711375580584142156144
761 742227263084787949376
762 759844127569872759494
763 792746564691701271102
764 811571139646047601508
765 846658300321690065338
766 866710806747489086344
767 904122634198438297500
768 925545637866379095772
769 965436608936252310490
770 988253925008348716388
771 1030778931103739148916
772 1055149923445271188782
773 1100486103128208222354
774 1126439255957878593936
775 1174759388270989302388
776 1202474256358014391328
777 1253982157327821281268
778 1283492458977699706586
779 1338379412338760871944
780 1369885444277427013378
781 1428384538571100036272
782 1461926462748785126944
783 1524250984893830123782
784 1560054019768641159442
785 1626471618800255934406
786 1664583481168565744816
787 1735330466358315141852
788 1776002001011437141680
789 1851383790682949037124
790 1894671655967995191286
791 1974951710656590452886
792 2021137423295684169288
793 2106665722987125776462
794 2155816635640651811056
795 2246885265120257968840
796 2299314379641921168942
797 2396321780886893261860
798 2452108694157982209240
799 2555380433352346698056
800 2614875728637651275954
801 2724867467888570933804
802 2788165745338704015910
803 2905238802028131945692
804 2972729353962965924196
805 3097401510039497697527
806 3169195763988612666256
807 3301869809251777119340
808 3378403033857610197168
809 3519669963591065318824
810 3601074370152241084540
811 3751381643538449158832
812 3838139871516492522476
813 3998157715071953821314
814 4090424811306453296832
815 4260652020308285100264
816 4358966604247950495312
817 4540166678675533428330
818 4644712310210241394234
819 4837440041231721867016
820 4948813316614286686996
821 5153933126426943971602
822 5272348624166436193810
823 5490479157652537244660
824 5616601584657784286298
825 5848725757962929070612
826 5982808468655752074098
827 6229615193380965110498
828 6372393593184137269068
829 6634993779197802438360
830 6786762897049763387374
831 7065924844940282114100
832 7227502574718835730002
833 7524487099805763498468
834 7696220725569019522706
835 8011884509768853208446
836 8194678129096215423154
837 8530444083220856079814
838 8724700958084075789288
839 9081524974070142865284
840 9288249135095808850128
841 9667743370195034396652
842 9887408090904294346426
843 10290639790581567889566
844 10524353957502197443252
845 10953139811873360662340
846 11201451201656476354192
847 11656982407143900732780
848 11921120448017465699808
849 12405451637388756889708
850 12686057087645468198934
851 13200519907199447828612
852 13498949653378875556792
853 14045856358074154557942
854 14362850132793283764242
855 14943687926517848014904
856 15280748129649490099466
857 15898127908977412227842
858 16256117212666964578136
859 16911703638325721414100
860 17292279146798055900236
861 17989006591131833331584
862 18393161449968552997816
863 19132889767221107289664
864 19562456059494760168660
865 20348493016407691208222
866 20804625133613965298096
867 21639054835152014510794
868 22123772457598011631826
869 23010308050136223355778
870 23524937123697812681842
871 24465908587368313150272
872 25012679516212364923260
873 26012266222849704707238
874 26592715771718292359774
875 27653531623742281948004
876 28270117635721492757554
877 29396848759706982277844
878 30051332196806546922584
879 31246902226879179895514
880 31941993941178767488956
881 33211669123088979664954
882 33949403711030692491820
883 35296466922579795111794
884 36079830640317667143756
885 37510180261388646108078
886 38341499716816788638562
887 39858809879588632796718
888 40741375642005870572782
889 42352265680457691039352
890 43288758555030351950436
891 44997357859885469785064
892 45991402112364225208972
893 47805116910639724929820
894 48859771754614963590534
895 50783225655827371728244
896 51902480586555112130060
897 53943972993808901422830
898 55131342711015558260834
899 57296073454918133072318
900 58555951235227792831068
901 60853197087641964996324
902 62189586177062120161732
903 64625172365115919847146
904 66042905324080433264600
905 68627214014257895263728
906 70130878513209762663742
907 72870465246997690624662
908 74465383259194474557644
909 77371842233388235397148
910 79063229668227814127412
911 82143907860538321415624
912 83937614570568232297748
913 87205470576460438046236
914 89107458081372078498704
915 92570763050815676484442
916 94587473666580586903304
917 98260685862207679111662
918 100398885778278134611346
919 104291278670669276648212
920 106558045983631746791958
921 110685760244990940674732
922 113088810317266005817990
923 117462289910747793981248
924 120009419665793770879192
925 124646658418209592950499
926 127346610392149989097642
927 132259321480169119794020
928 135120658399434056200976
929 140328905431799458487310
930 143361572050746599606392
931 148878547933684693137536
932 152091978090369601017442
933 157940031268144414711872
934 161345475549115864327298
935 167539405900876135876982
936 171147222692489613414166
937 177711922595386536176922
938 181534882021576423593354
939 188487022899160442922186
940 192536542016873437906214
941 199903830595013607931602
942 204194335111570851708268
943 211995477070873268821500
944 216539501735632990816002
945 224805324854659697879270
946 229619207812100586270708
947 238370780513507703024688
948 243468342139916207026924
949 252739951497464991171162
950 258139620526450918686812
951 267954908072521153448728
952 273671859147344262529096
953 284068937527026840860772
954 290124001212751612463830
955 301129494860387382687604
956 307539411840189622582196
957 319195682151901497359926
958 325983916629661498511268
959 338320841498294291526548
960 345505778599690977829534
961 358570401791612334162478
962 366178511005132235553128
963 380004469136547730225146
964 388056042226318999774940
965 402695587083587040486720
966 411220398205896681016882
967 426711274534243247970746
968 435731616314765704057590
969 452131801742825961261498
970 461681200591109332480262
971 479033174439965150134338
972 489136251667299608900620
973 507504371768433009285668
974 518198792086473421891372
975 537630722612599209385252
976 548943549065102096184696
977 569510642692445700979970
978 581484210569635609176316
979 603240084882499854602610
980 615904301458237004674750
981 638928111846345939242804
982 652330475621214957695916
983 676682372606962110090202
984 690855776105975328550344
985 716623452903009278531454
986 731621195740598789813820
987 758872283643185887135498
988 774730742817152634156066
989 803562473182429505198648
990 820341378465166794257140
991 850829608750836520473358
992 868568998795851938825604
993 900821374448265904719158
994 919588165551344263184940
995 953689928249979837325556
996 973528429123428904313440
997 1009598866072028091589044
998 1030583973106756788589892
999 1068718664293210551125026
1000 1090899183652944759783818