0 1
1 1
2 2
3 3
4 4
5 6
6 7
7 10
8 12
9 16
10 19
11 24
12 28
13 36
14 43
15 51
16 62
17 74
18 87
19 104
20 122
21 143
22 169
23 195
24 227
25 260
26 302
27 346
28 397
29 455
30 521
31 599
32 686
33 780
34 889
35 1001
36 1138
37 1286
38 1454
39 1638
40 1846
41 2076
42 2330
43 2614
44 2929
45 3280
46 3666
47 4093
48 4565
49 5085
50 5667
51 6300
52 7002
53 7772
54 8623
55 9548
56 10569
57 11685
58 12905
59 14247
60 15703
61 17310
62 19054
63 20973
64 23045
65 25315
66 27792
67 30505
68 33456
69 36674
70 40172
71 43979
72 48111
73 52610
74 57501
75 62813
76 68554
77 74785
78 81536
79 88856
80 96789
81 105380
82 114637
83 124695
84 135522
85 147255
86 159901
87 173589
88 188322
89 204245
90 221412
91 239936
92 259907
93 281443
94 304597
95 329530
96 356360
97 385247
98 416303
99 449706
100 485580
101 524098
102 565491
103 609946
104 657655
105 708854
106 763754
107 822567
108 885685
109 953251
110 1025761
111 1103338
112 1186458
113 1275338
114 1370543
115 1472297
116 1581312
117 1697722
118 1822308
119 1955300
120 2097582
121 2249470
122 2411783
123 2585092
124 2770102
125 2967510
126 3178235
127 3402968
128 3642799
129 3898505
130 4171258
131 4461808
132 4771628
133 5101618
134 5453409
135 5827882
136 6226785
137 6651242
138 7103225
139 7584079
140 8095858
141 8640116
142 9219067
143 9834529
144 10488951
145 11184428
146 11923641
147 12709059
148 13543278
149 14429318
150 15370196
151 16369214
152 17429651
153 18555207
154 19749351
155 21016405
156 22360215
157 23785770
158 25297016
159 26899593
160 28597923
161 30398074
162 32305276
163 34326334
164 36466841
165 38734289
166 41134958
167 43677055
168 46367710
169 49215996
170 52230159
171 55419711
172 58793697
173 62362885
174 66137138
175 70129072
176 74349200
177 78811237
178 83526766
179 88511059
180 93777304
181 99342355
182 105220578
183 111430462
184 117988015
185 124913332
186 132224667
187 139944338
188 148092427
189 156692988
190 165768362
191 175345066
192 185447669
193 196105990
194 207347344
195 219203246
196 231704691
197 244885857
198 258781224
199 273428977
200 288866948
201 305136368
202 322279367
203 340340920
204 359367618
205 379409138
206 400517088
207 422745386
208 446150802
209 470792287
210 496732770
211 524037630
212 552775570
213 583017984
214 614840206
215 648320629
216 683542356
217 720592145
218 759560673
219 800542688
220 843637626
221 888949068
222 936587017
223 986665132
224 1039304809
225 1094628218
226 1152769587
227 1213862742
228 1278054136
229 1345491789
230 1416336323
231 1490748433
232 1568903675
233 1650977883
234 1737163964
235 1827654369
236 1922660726
237 2022392958
238 2127080657
239 2236955116
240 2352266811
241 2473269741
242 2600236789
243 2733445017
244 2873192507
245 3019781349
246 3173537713
247 3334793412
248 3503902706
249 3681227402
250 3867155493
251 4062079353
252 4266424444
253 4480619377
254 4705127473
255 4940416491
256 5186989943
257 5445358784
258 5716072042
259 5999688509
260 6296805427
261 6608030450
262 6934014385
263 7275419704
264 7632956257
265 8007345417
266 8399358861
267 8809783929
268 9239459037
269 9689241581
270 10160044609
271 10652801760
272 11168505952
273 11708173038
274 12272881944
275 12863736976
276 13481913322
277 14128614116
278 14805112305
279 15512718090
280 16252813634
281 17026822846
282 17836248741
283 18682640220
284 19567626497
285 20492891621
286 21460203330
287 22471391617
288 23528376325
289 24633144866
290 25787780215
291 26994439730
292 28255381959
293 29572948919
294 30949592284
295 32387854176
296 33890389386
297 35459960636
298 37099439349
299 38811825841
300 40600235436
301 42467920246
302 44418252890
303 46454761625
304 48581095606
305 50801084154
306 53118677854
307 55538029869
308 58063416134
309 60699335442
310 63450416053
311 66321531324
312 69317692872
313 72444178328
314 75706414949
315 79110109060
316 82661134251
317 86365667366
318 90230065455
319 94261011130
320 98465386272
321 102850410862
322 107423528817
323 112192553122
324 117165527533
325 122350906870
326 127757383642
327 133394099118
328 139270444404
329 145396302412
330 151781822967
331 158437685422
332 165374857953
333 172604877736
334 180139588601
335 187991453202
336 196173268696
337 204698488482
338 213580942997
339 222835140381
340 232476024382
341 242519245320
342 252980942964
343 263878005115
344 275227858999
345 287048713146
346 299359375589
347 312179488934
348 325529348894
349 339430138201
350 353903760100
351 368973046321
352 384661616354
353 400994092195
354 417995942778
355 435693703391
356 454114844927
357 473287957230
358 493242647005
359 514009723564
360 535621098749
361 558109963602
362 581510706814
363 605859072672
364 631192110107
365 657548308426
366 684967580351
367 713491368857
368 743162663653
369 774026066738
370 806127877127
371 839516094121
372 874240561118
373 910352946847
374 947906893678
375 986958001666
376 1027563986502
377 1069784669328
378 1113682145881
379 1159320769890
380 1206767345728
381 1256091085354
382 1307363824082
383 1360659995861
384 1416056842407
385 1473634402931
386 1533475724758
387 1595666849784
388 1660297043409
389 1727458782509
390 1797248017042
391 1869764127722
392 1945110223663
393 2023393094428
394 2104723512920
395 2189216202452
396 2276990165381
397 2368168633084
398 2462879438892
399 2561254911544
400 2663432336749
401 2769553809689
402 2879766721879
403 2994223661651
404 3113082864499
405 3236508106394
406 3364669247232
407 3497742059728
408 3635908833712
409 3779358213994
410 3928285823384
411 4082894050697
412 4243392779987
413 4409999144474
414 4582938265720
415 4762443080211
416 4948755048893
417 5142123980507
418 5342808824845
419 5551077435372
420 5767207483593
421 5991486167044
422 6224211168702
423 6465690369470
424 6716242856964
425 6976198621437
426 7245899663775
427 7525699636647
428 7815965050499
429 8117074833144
430 8429421700368
431 8753411620058
432 9089465301820
433 9438017658040
434 9799519352776
435 10174436178668
436 10563250820967
437 10966462093921
438 11384586870240
439 11818159296067
440 12267732807452
441 12733879278803
442 13217191147625
443 13718280624389
444 14237781821291
445 14776350048362
446 15334663991650
447 15913424940337
448 16513359134698
449 17135217003494
450 17779775561597
451 18447837748807
452 19140234807403
453 19857825709186
454 20601499581382
455 21372175191584
456 22170803459307
457 22998367068828
458 23855882848218
459 24744401690308
460 25665010762289
461 26618833696174
462 27607032748391
463 28630809213930
464 29691405472077
465 30790105660707
466 31928237607561
467 33107173778289
468 34328333204048
469 35593182577714
470 36903238231466
471 38260067380981
472 39665290024820
473 41120580554364
474 42627669598107
475 44188345781131
476 45804457698672
477 47477915882227
478 49210694516558
479 51004834072071
480 52862442700449
481 54785699344718
482 56776854964744
483 58838236124722
484 60972245903757
485 63181368103274
486 65468167997512
487 67835296941967
488 70285493004451
489 72821586051709
490 75446498242871
491 78163249517114
492 80974958236554
493 83884846769714
494 86896242477296
495 90012583312374
496 93237419206279
497 96574417651034
498 100027365618774
499 103600175017881
500 107296885237436
501 111121668458811
502 115078832737545
503 119172827228601
504 123408246108665
505 127789833365389
506 132322487676212
507 137011267011090
508 141861393923132
509 146878260443650
510 152067433961859
511 157434661962731
512 162985878694484
513 168727210024226
514 174664980360889
515 180805718016477
516 187156162624528
517 193723270589854
518 200514223185504
519 207536432320279
520 214797548861760
521 222305469095127
522 230068343366327
523 238094583047491
524 246392869748610
525 254972162541648
526 263841707816486
527 273011046959830
528 282490026792859
529 292288807805445
530 302417875227400
531 312888047673780
532 323710488878827
533 334896716944568
534 346458616773615
535 358408449846624
536 370758867487443
537 383522921417470
538 396714077194273
539 410346226138978
540 424433698970347
541 438991279163144
542 454034216509033
543 469578242578777
544 485639583403480
545 502234977448671
546 519381687779998
547 537097522530481
548 555400846107440
549 574310602892706
550 593846326907611
551 614028168864216
552 634876905044376
553 656413967045702
554 678661450325027
555 701642146470657
556 725379551533234
557 749897900808758
558 775222177264018
559 801378148702337
560 828392376721112
561 856292255811293
562 885106023093170
563 914862799393851
564 945592600177200
565 977326378240100
566 1010096036432656
567 1043934471771376
568 1078875589614225
569 1114954349859435
570 1152206782568918
571 1190670036237514
572 1230382395251370
573 1271383329925091
574 1313713516270815
575 1357414887235329
576 1402530655458836
577 1449105366384567
578 1497184922941775
579 1546816641423525
580 1598049278292298
581 1650933087715708
582 1705519852079274
583 1761862941170357
584 1820017346039826
585 1880039739932875
586 1941988516075816
587 2005923849763972
588 2071907740822593
589 2140004077504917
590 2210278683092984
591 2282799381542746
592 2357636049137823
593 2434860680984312
594 2514547449034672
595 2596772769376478
596 2681615366428177
597 2769156341850521
598 2859479244204746
599 2952670139897720
600 3048817689198432
601 3148013219203566
602 3250350806042868
603 3355927350865756
604 3464842667686217
605 3577199562143425
606 3693103926280736
607 3812664820948151
608 3935994576314940
609 4063208879082153
610 4194426878674782
611 4329771278803956
612 4469368450662847
613 4613348529701914
614 4761845535160966
615 4914997472214067
616 5072946459024765
617 5235838833172599
618 5403825287545728
619 5577060982452806
620 5755705689324394
621 5939923909243495
622 6129885024750541
623 6325763424265974
624 6527738664168608
625 6735995599275733
626 6950724554511777
627 7172121463587198
628 7400388048564798
629 7635731967393447
630 7878367004069533
631 8128513224213990
632 8386397175835629
633 8652252054870279
634 8926317915527521
635 9208841845498404
636 9500078189699568
637 9800288733790423
638 10109742941793192
639 10428718149339436
640 10757499814876682
641 11096381722619698
642 11445666249949263
643 11805664579975866
644 12176696986017078
645 12559093054355817
646 12953191985373000
647 13359342827993892
648 13777904798914641
649 14209247529099632
650 14653751402992579
651 15111807816362640
652 15583819535856212
653 16070200970031477
654 16571378550135355
655 17087791015883889
656 17619889818301240
657 18168139420827278
658 18733017723808899
659 19315016383113076
660 19914641257614692
661 20532412747254689
662 21168866263374132
663 21824552588229847
664 22500038367676847
665 23195906493755280
666 23912756621262769
667 24651205577138080
668 25411887899292844
669 26195456275081519
670 27002582103212421
671 27833955961990327
672 28690288196688743
673 29572309421370138
674 30480771130197393
675 31416446235102913
676 32380129702312847
677 33372639127651113
678 34394815399481638
679 35447523315562258
680 36531652273253485
681 37648116928608964
682 38797857915034896
683 39981842548755433
684 41201065574965572
685 42456549925594591
686 43749347493650717
687 45080539943854080
688 46451239517330942
689 47862589898330216
690 49315767050070821
691 50811980143600378
692 52352472425056640
693 53938522207756395
694 55571443773795639
695 57252588432514216
696 58983345457990069
697 60765143220791598
698 62599450161163928
699 64487775994092985
700 66431672725240949
701 68432735930717837
702 70492605816552307
703 72612968582760208
704 74795557526309276
705 77042154488308094
706 79354591009585525
707 81734749861304203
708 84184566257362792
709 86706029475009425
710 89301184127044665
711 91972131871509424
712 94721032751311694
713 97550106995846257
714 100461636433637603
715 103457966389105455
716 106541507177276384
717 109714736091800028
718 112980198989869487
719 116340512375663546
720 119798365083491221
721 123356520458002294
722 127017818146349816
723 130785176373290293
724 134661593847402407
725 138650152141379979
726 142754017715855143
727 146976444410093651
728 151320775596297218
729 155790446775410599
730 160388987870513434
731 165120025939641251
732 169987287609387077
733 174994601915188250
734 180145902887713679
735 185445232512379986
736 190896743482111002
737 196504702289325434
738 202273492145484776
739 208207616215627152
740 214311700722998642
741 220590498315174353
742 227048891368936962
743 233691895504004931
744 240524663087190723
745 247552486908471187
746 254780803901724915
747 262215198973691883
748 269861408958445847
749 277725326614911114
750 285813004817153095
751 294130660737784299
752 302684680288082214
753 311481622486269603
754 320528224159857702
755 329831404518827469
756 339398270122567266
757 349236119680198479
758 359352449295314315
759 369754957491447094
760 380451550754416216
761 391450348801395670
762 402759690424124350
763 414388139028749386
764 426344488793886864
765 438637770479530564
766 451277257923478588
767 464272474140311094
768 477633198159384370
769 491369471444571788
770 505491605092923208
771 520010186569576963
772 534936087297216195
773 550280469729080289
774 566054795332233370
775 582270832037061519
776 598940662630759640
777 616076692582878999
778 633691658883396730
779 651798638264598745
780 670411056494309640
781 689542697037071209
782 709207710815403132
783 729420625316361261
784 750196354862331881
785 771550210177743507
786 793497909188813466
787 816055587098911819
788 839239807727432799
789 863067574106368091
790 887556340407200960
791 912724023068032519
792 938589013338016386
793 965170188989863941
794 992486927489692495
795 1020559118315120380
796 1049407176800457554
797 1079052057075916248
798 1109515266625678142
799 1140818879899913896
800 1172985553602850861
801 1206038541005782635
802 1240001708009775435
803 1274899548187016143
804 1310757199661550123
805 1347600460932526691
806 1385455808595431741
807 1424350413984698553
808 1464312161780105920
809 1505369667502202749
810 1547552297058575242
811 1590890185146507387
812 1635414255764797336
813 1681156241579437259
814 1728148705437055880
815 1776425060740608292
816 1826019594025385739
817 1876967486405300465
818 1929304837247968051
819 1983068686746763295
820 2038297040740962736
821 2095028894472448993
822 2153304258612036061
823 2213164184277949486
824 2274650790303537123
825 2337807289586799481
826 2402678017652866225
827 2469308460395944171
828 2537745284017594304
829 2608036364234901078
830 2680230817647199063
831 2754379032494929020
832 2830532701492636718
833 2908744854235064070
834 2989069891578730761
835 3071563619775882053
836 3156283286472383161
837 3243287616664245693
838 3332636850358191546
839 3424392780453257053
840 3518618792171365445
841 3615379902947319592
842 3714742803703539850
843 3816775900874805486
844 3921549359563048036
845 4029135147820204737
846 4139607081817021355
847 4253040872454121154
848 4369514172661470936
849 4489106626457538538
850 4611899918435717455
851 4737977825414477286
852 4867426268246573294
853 5000333366157972994
854 5136789491014854125
855 5276887324474315919
856 5420721914787382207
857 5568390736920667268
858 5719993752054074332
859 5875633470778894354
860 6035415015452066939
861 6199446186612107299
862 6367837528273282575
863 6540702397754057639
864 6718157034081795909
865 6900320631355534075
866 7087315410457422300
867 7279266696096421771
868 7476302991943391716
869 7678556061560450169
870 7886161007161450411
871 8099256354575217736
872 8317984135836828058
873 8542489978367986650
874 8772923191545745838
875 9009436860302993659
876 9252187935932716167
877 9501337334263843566
878 9757050030946582385
879 10019495164402301031
880 10288846135771368563
881 10565280716867237865
882 10848981155073945135
883 11140134286489242436
884 11438931646055400605
885 11745569586107853017
886 12060249391962226750
887 12383177406130236477
888 12714565149680584908
889 13054629452346522404
890 13403592579975950000
891 13761682370790901387
892 14129132369165470192
893 14506181968357784680
894 14893076550964332409
895 15290067638387325181
896 15697413038323155651
897 16115377001266783558
898 16544230375310521748
899 16984250770055046998
900 17435722719098124117
901 17898937851686943056
902 18374195063274014825
903 18861800695265337632
904 19362068713984446013
905 19875320898905132225
906 20401887030479848785
907 20942105087233175361
908 21496321442884131320
909 22064891072706658448
910 22648177760347428432
911 23246554313895553598
912 23860402782899971097
913 24490114684600290302
914 25136091231626427305
915 25798743568852200887
916 26478493012250656186
917 27175771296860924217
918 27891020827386375018
919 28624694937793122633
920 29377258154183496743
921 30149186466590412903
922 30940967604630602132
923 31753101322084415101
924 32586099685986766437
925 33440487374586480371
926 34316801980478814250
927 35215594322611586758
928 36137428764007249294
929 37082883538513950145
930 38052551083858805622
931 39047038383827346845
932 40066967317327387421
933 41112975016764035774
934 42185714233767284770
935 43285853714523373302
936 44414078583037063136
937 45571090734179336059
938 46757609235292935984
939 47974370737795105226
940 49222129897911744421
941 50501659807682912826
942 51813752435821318881
943 53159219078988679247
944 54538890823718342905
945 55953619018890104435
946 57404275759645208643
947 58891754382023548706
948 60416969969989473773
949 61980859873242172531
950 63584384238409124378
951 65228526551112327263
952 66914294192365021943
953 68642719006020695588
954 70414857881622241931
955 72231793348416482738
956 74094634185824077488
957 76004516045297533993
958 77962602089583635739
959 79970083643692903241
960 82028180864396064538
961 84138143421659619839
962 86301251199692102094
963 88518815010310422565
964 90792177326895563698
965 93122713031113758349
966 95511830181429852556
967 97960970794735425689
968 100471611650919455011
969 103045265111053994847
970 105683479959616344453
971 108387842260835613229
972 111159976240442382283
973 114001545181937875401
974 116914252349609290800
975 119899841926570484309
976 122960099980889883780
977 126096855447236341804
978 129311981138228323988
979 132607394771713568971
980 135985060029322051063
981 139446987631476374164
982 142995236445264279816
983 146631914609293612265
984 150359180693228234410
985 154179244874866062816
986 158094370153540105857
987 162106873581864851997
988 166219127535366093096
989 170433561001345097599
990 174752660907383938544
991 179178973470054959562
992 183715105584774750763
993 188363726237176623623
994 193127567957027875836
995 198009428295016797103
996 203012171343754443142
997 208138729283097978519
998 213392103971053350972
999 218775368560812158554
1000 224291669164720910717