0 1
1 1
2 2
3 3
4 5
5 8
6 12
7 17
8 25
9 35
10 49
11 66
12 90
13 119
14 158
15 206
16 267
17 342
18 437
19 551
20 694
21 865
22 1074
23 1324
24 1627
25 1985
26 2414
27 2919
28 3518
29 4219
30 5045
31 6003
32 7125
33 8422
34 9927
35 11660
36 13660
37 15949
38 18578
39 21575
40 24998
41 28884
42 33303
43 38298
44 43955
45 50329
46 57513
47 65581
48 74645
49 84786
50 96141
51 108807
52 122939
53 138660
54 156148
55 175544
56 197059
57 220861
58 247187
59 276240
60 308295
61 343579
62 382415
63 425071
64 471906
65 523239
66 579478
67 640984
68 708232
69 781635
70 861723
71 948977
72 1044000
73 1147332
74 1259660
75 1381603
76 1513922
77 1657331
78 1812687
79 1980785
80 2162600
81 2359027
82 2571146
83 2799979
84 3046732
85 3312541
86 3598759
87 3906663
88 4237748
89 4593451
90 4975435
91 5385287
92 5824867
93 6295945
94 6800561
95 7340699
96 7918613
97 8536488
98 9196828
99 9902051
100 10654902
101 11458065
102 12314562
103 13227340
104 14199733
105 15234989
106 16336743
107 17508587
108 18754508
109 20078426
110 21484722
111 22977693
112 24562109
113 26242694
114 28024650
115 29913124
116 31913803
117 34032309
118 36274812
119 38647460
120 41156967
121 43810000
122 46613874
123 49575845
124 52703823
125 56005714
126 59490087
127 63165499
128 67041254
129 71126623
130 75431644
131 79966376
132 84741669
133 89768377
134 95058231
135 100622963
136 106475193
137 112627610
138 119093814
139 125887455
140 133023203
141 140515758
142 148380868
143 156634386
144 165293232
145 174374422
146 183896145
147 193876687
148 204335532
149 215292332
150 226767974
151 238783498
152 251361310
153 264523959
154 278295384
155 292699765
156 307762701
157 323510028
158 339969136
159 357167644
160 375134768
161 393900041
162 413494642
163 433950064
164 455299587
165 477576809
166 500817149
167 525056463
168 550332476
169 576683337
170 604149234
171 632770777
172 662590671
173 693652160
174 726000630
175 759682019
176 794744575
177 831237110
178 869210803
179 908717523
180 949811577
181 992547957
182 1036984293
183 1083178916
184 1131192851
185 1181087973
186 1232928914
187 1286781180
188 1342713242
189 1400794452
190 1461097208
191 1523694942
192 1588664222
193 1656082664
194 1726031238
195 1798591998
196 1873850427
197 1951893270
198 2032810792
199 2116694540
200 2203639834
201 2293743296
202 2387105424
203 2483828210
204 2584017615
205 2687781133
206 2795230482
207 2906478966
208 3021644219
209 3140845653
210 3264207135
211 3391854345
212 3523917713
213 3660529528
214 3801826938
215 3947949187
216 4099040496
217 4255247239
218 4416721075
219 4583615870
220 4756090917
221 4934307945
222 5118434262
223 5308639678
224 5505099904
225 5707993229
226 5917503981
227 6133819343
228 6357132695
229 6587640332
230 6825545112
231 7071052885
232 7324376238
233 7585731031
234 7855340026
235 8133429358
236 8420232437
237 8715986149
238 9020934836
239 9335326618
240 9659417274
241 9993466447
242 10337741861
243 10692515219
244 11058066494
245 11434679978
246 11822648434
247 12222269075
248 12633848026
249 13057695973
250 13494132746
251 13943483088
252 14406081130
253 14882266044
254 15372386851
255 15876797773
256 16395863111
257 16929952761
258 17479446953
259 18044731656
260 18626203689
261 19224265757
262 19839331691
263 20471821629
264 21122167103
265 21790806128
266 22478188642
267 23184771264
268 23911022826
269 24657419273
270 25424449078
271 26212608011
272 27022404958
273 27854356302
274 28708991846
275 29586849387
276 30488480461
277 31414444819
278 32365316566
279 33341678242
280 34344127097
281 35373269314
282 36429726159
283 37514128073
284 38627121223
285 39769361211
286 40941519726
287 42144278462
288 43378335590
289 44644399532
290 45943195898
291 47275460820
292 48641948036
293 50043422392
294 51480666750
295 52954475389
296 54465661334
297 56015049342
298 57603483355
299 59231819671
300 60900934243
301 62611715683
302 64365073060
303 66161928445
304 68003224828
305 69889918883
306 71822988684
307 73803426359
308 75832246275
309 77910477205
310 80039170686
311 82219393373
312 84452235230
313 86738801720
314 89080222492
315 91477643117
316 93932233890
317 96445181804
318 99017699149
319 101651015326
320 104346385991
321 107105084332
322 109928410401
323 112817682604
324 115774246813
325 118799467722
326 121894738477
327 125061471546
328 128301108487
329 131615111030
330 135004970670
331 138472199565
332 142018340712
333 145644958286
334 149353647972
335 153146027577
336 157023747113
337 160988479264
338 165041930041
339 169185828682
340 173421938501
341 177752047001
342 182177976534
343 186701574234
344 191324723255
345 196049332152
346 200877346272
347 205810737425
348 210851515025
349 216001715563
350 221263414402
351 226638714631
352 232129759067
353 237738719352
354 243467807709
355 249319265891
356 255295377540
357 261398456547
358 267630859590
359 273994974758
360 280493233868
361 287128100863
362 293902084827
363 300817727739
364 307877617662
365 315084376803
366 322440674424
367 329949214746
368 337612750518
369 345434070246
370 353416012001
371 361561450913
372 369873312744
373 378354561160
374 387008211996
375 395837319892
376 404844992729
377 414034378589
378 423408679914
379 432971140249
380 442725059151
381 452673778200
382 462820696160
383 473169255290
384 483722956205
385 494485344002
386 505460023840
387 516650646390
388 528060923614
389 539694614510
390 551555540646
391 563647571660
392 575974641589
393 588540733609
394 601349896584
395 614406230172
396 627713901041
397 641277127779
398 655100197889
399 669187451933
400 683543300788
401 698172210087
402 713078717215
403 728267415509
404 743742972044
405 759510111081
406 775573632068
407 791938393476
408 808609330467
409 825591438469
410 842889791722
411 860509526024
412 878455857555
413 896734065956
414 915349512823
415 934307624586
416 953613911821
417 973273951334
418 993293405720
419 1013678005802
420 1034433569892
421 1055565985939
422 1077081231716
423 1098985356112
424 1121284499558
425 1143984875725
426 1167092791586
427 1190614628901
428 1214556865162
429 1238926054185
430 1263728847370
431 1288971974651
432 1314662265441
433 1340806629294
434 1367412077773
435 1394485704263
436 1422034706075
437 1450066364687
438 1478588067482
439 1507607287711
440 1537131607217
441 1567168695439
442 1597726332468
443 1628812388448
444 1660434846244
445 1692601780597
446 1725321381745
447 1758601933684
448 1792451838059
449 1826879592817
450 1861893815772
451 1897503222945
452 1933716653168
453 1970543045436
454 2007991463801
455 2046071075201
456 2084791173926
457 2124161159190
458 2164190560620
459 2204889014828
460 2246266291243
461 2288332269078
462 2331096962818
463 2374570498879
464 2418763142130
465 2463685271571
466 2509347407144
467 2555760185910
468 2602934388432
469 2650880914623
470 2699610811262
471 2749135246775
472 2799465539110
473 2850613130954
474 2902589617187
475 2955406719836
476 3009076316596
477 3063610414754
478 3119021180034
479 3175320910985
480 3232522067438
481 3290637244529
482 3349679202346
483 3409660838852
484 3470595219849
485 3532495552421
486 3595375214435
487 3659247727709
488 3724126788654
489 3790026240300
490 3856960103341
491 3924942548626
492 3993987927798
493 4064110745426
494 4135325690827
495 4207647609109
496 4281091533305
497 4355672655961
498 4431406360808
499 4508308193998
500 4586393897035
501 4665679376795
502 4746180738879
503 4827914258143
504 4910896411562
505 4995143848447
506 5080673424530
507 5167502171039
508 5255647329133
509 5345126319484
510 5435956776291
511 5528156516476
512 5621743575014
513 5716736172880
514 5813152752756
515 5911011947576
516 6010332615702
517 6111133809142
518 6213434810025
519 6317255097559
520 6422614384940
521 6529532586818
522 6638029855767
523 6748126549369
524 6859843267995
525 6973200820651
526 7088220263130
527 7204922864485
528 7323330144648
529 7443463840496
530 7565345944895
531 7688998671427
532 7814444493888
533 7941706111570
534 8070806488233
535 8201768817056
536 8334616560957
537 8469373416250
538 8606063353379
539 8744710581160
540 8885339587027
541 9027975100829
542 9172642136562
543 9319365954794
544 9468172104802
545 9619086387645
546 9772134897731
547 9927343985544
548 10084740300643
549 10244350752970
550 10406202556349
551 10570323190384
552 10736740443449
553 10905482374146
554 11076577355776
555 11250054036435
556 11425941383887
557 11604268646336
558 11785065396728
559 11968361493093
560 12154187124411
561 12342572769452
562 12533549243165
563 12727147656156
564 12923399460476
565 13122336408714
566 13323990601304
567 13528394444200
568 13735580696626
569 13945582429385
570 14158433072087
571 14374166370986
572 14592816437838
573 14814417706199
574 15039004980756
575 15266613394362
576 15497278456719
577 15731036011011
578 15967922284196
579 16207973842089
580 16451227640189
581 16697720979400
582 16947491556312
583 17200577418460
584 17457017016227
585 17716849156575
586 17980113055418
587 18246848292119
588 18517094861216
589 18790893126427
590 19068283874124
591 19349308265702
592 19634007891611
593 19922424724414
594 20214601172178
595 20510580031125
596 20810404540687
597 21114118334570
598 21421765496322
599 21733390511120
600 22049038320740
601 22368754274810
602 22692584187598
603 23020574287589
604 23352771274779
605 23689222271045
606 24029974876748
607 24375077120681
608 24724577518428
609 25078525020586
610 25436969071736
611 25799959559391
612 26167546872346
613 26539781849099
614 26916715838012
615 27298400644070
616 27684888589543
617 28076232461568
618 28472485572122
619 28873701705088
620 29279935178130
621 29691240787943
622 30107673872762
623 30529290258395
624 30956146320009
625 31388298927695
626 31825805510110
627 32268723998315
628 32717112889967
629 33171031193933
630 33630538493845
631 34095694892154
632 34566561075660
633 35043198257709
634 35525668244303
635 36014033377188
636 36508356599189
637 37008701396815
638 37515131867545
639 38027712660564
640 38546509044699
641 39071586849935
642 39603012534692
643 40140853126787
644 40685176292680
645 41236050276591
646 41793543970323
647 42357726853303
648 42928669061630
649 43506441327534
650 44091115050530
651 44682762234913
652 45281455561586
653 45887268326394
654 46500274511185
655 47120548721655
656 47748166260423
657 48383203062964
658 49025735771312
659 49675841670867
660 50333598763380
661 50999085703131
662 51672381872095
663 52353567314115
664 53042722810685
665 53739929816075
666 54445270532294
667 55158827843708
668 55880685394119
669 56610927519321
670 57349639324912
671 58096906619730
672 58852815992921
673 59617454746754
674 60390910975865
675 61173273498079
676 61964631934267
677 62765076640155
678 63574698785361
679 64393590284596
680 65221843878976
681 66059553065062
682 66906812176933
683 67763716316165
684 68630361433050
685 69506844256019
686 70393262375085
687 71289714169205
688 72196298890388
689 73113116591992
690 74040268212071
691 74977855501016
692 75925981107256
693 76884748502695
694 77854262069112
695 78834627024659
696 79825949509350
697 80828336510984
698 81841895952966
699 82866736618010
700 83902968236738
701 84950701412322
702 86010047708296
703 87081119572551
704 88164030427494
705 89258894591853
706 90365827371532
707 91484944982512
708 92616364640795
709 93760204484626
710 94916583666934
711 96085622275233
712 97267441424867
713 98462163179913
714 99669910645526
715 100890807888261
716 102124980030817
717 103372553170096
718 104633654472698
719 105908412094024
720 107196955272920
721 108499414250050
722 109815920365121
723 111146605972890
724 112491604541130
725 113851050567764
726 115225079677871
727 116613828540223
728 118017434966800
729 119436037826899
730 120869777147518
731 122318794028513
732 123783230742105
733 125263230647316
734 126758938292049
735 128270499325174
736 129798060599345
737 131341770084250
738 132901776968470
739 134478231572020
740 136071285450892
741 137681091307062
742 139307803093929
743 140951575927437
744 142612566190517
745 144290931443559
746 145986830531481
747 147700423491775
748 149431871662370
749 151181337590788
750 152948985141111
751 154734979402378
752 156539486798321
753 158362674993180
754 160204713002273
755 162065771099054
756 163946020924626
757 165845635394129
758 167764788808996
759 169703656760746
760 171662416244154
761 173641245562159
762 175640324438111
763 177659833919930
764 179699956495114
765 181760875992333
766 183842777697265
767 185945848255474
768 188070275787190
769 190216249789401
770 192383961253559
771 194573602564964
772 196785367621416
773 199019451733782
774 201276051743600
775 203555365922972
776 205857594094984
777 208182937530956
778 210531599071750
779 212903783026247
780 215299695291664
781 217719543251193
782 220163535897332
783 222631883726769
784 225124798864591
785 227642494960485
786 230185187311839
787 232753092759247
788 235346429812547
789 237965418543506
790 240610280712872
791 243281239664293
792 245978520450348
793 248702349725638
794 251452955875825
795 254230568907984
796 257035420580516
797 259867744294858
798 262727775224288
799 265615750204822
800 268531907867144
801 271476488524567
802 274449734306009
803 277451889045259
804 280483198412804
805 283543909804344
806 286634272475683
807 289754537428426
808 292904957545806
809 296085787479679
810 299297283785313
811 302539704807513
812 305813310818629
813 309118363901695
814 312455128089413
815 315823869248738
816 319224855218647
817 322658355693953
818 326124642366264
819 329623988804795
820 333156670598393
821 336722965237655
822 340323152255884
823 343957513110349
824 347626331326452
825 351329892376018
826 355068483822437
827 358842395200440
828 362651918160029
829 366497346345358
830 370378975542048
831 374297103552949
832 378252030346552
833 382244057934131
834 386273490516953
835 390340634362643
836 394445797955664
837 398589291870629
838 402771428923819
839 406992524047922
840 411252894442410
841 415552859447324
842 419892740697135
843 424272861991356
844 428693549449430
845 433155131382867
846 437657938448862
847 442202303521635
848 446788561849448
849 451417050922703
850 456088110632133
851 460802083138333
852 465559313028779
853 470360147186418
854 475204934950162
855 480094027980324
856 485027780420135
857 490006548762748
858 495030692011489
859 500100571545935
860 505216551285767
861 510378997553483
862 515588279239458
863 520844767666169
864 526148836751944
865 531500862874328
866 536901225037371
867 542350304731753
868 547848486103162
869 553396155813924
870 558993703210188
871 564641520182573
872 570340001337054
873 576089543852190
874 581890547651144
875 587743415260573
876 593648551981268
877 599606365746164
878 605617267294652
879 611681670027153
880 617799990180661
881 623972646684828
882 630200061336284
883 636482658653749
884 642820866056048
885 649215113713823
886 655665834728677
887 662173464986595
888 668738443335709
889 675361211438708
890 682042213954485
891 688781898386984
892 695580715268112
893 702439118008178
894 709357563077439
895 716336509855653
896 723376420817384
897 730477761378064
898 737641000080500
899 744866608442578
900 752155061142468
901 759506835865256
902 766922413492134
903 774402277943416
904 781946916368915
905 789556818992707
906 797232479302071
907 804974393891345
908 812783062654764
909 820658988626623
910 828602678175461
911 836614640845875
912 844695389551370
913 852845440415112
914 861065312966757
915 869355529979606
916 877716617668619
917 886149105529365
918 894653526534600
919 903230416972175
920 911880316645728
921 920603768708768
922 929401319866750
923 938273520212892
924 947220923428769
925 956244086619159
926 965343570516682
927 974519939312957
928 983773760864497
929 993105606525594
930 1002516051352859
931 1012005673937001
932 1021575056611588
933 1031224785280946
934 1040955449630224
935 1050767642955188
936 1060661962370731
937 1070639008639672
938 1080699386385457
939 1090843703917059
940 1101072573443086
941 1111386610898417
942 1121786436156920
943 1132272672856998
944 1142845948618519
945 1153506894864502
946 1164256147039348
947 1175094344432470
948 1186022130394972
949 1197040152162144
950 1208149061074555
951 1219349512396515
952 1230642165538613
953 1242027683877999
954 1253506734979383
955 1265079990414317
956 1276748125986476
957 1288511821546986
958 1300371761221079
959 1312328633225298
960 1324383130092680
961 1336535948488763
962 1348787789441294
963 1361139358152144
964 1373591364228380
965 1386144521496167
966 1398799548230225
967 1411557166966708
968 1424418104737092
969 1437383092876883
970 1450452867261037
971 1463628168114552
972 1476909740246382
973 1490298332858845
974 1503794699786053
975 1517399599299252
976 1531113794346611
977 1544938052360599
978 1558873145496163
979 1572919850436938
980 1587078948638087
981 1601351226128201
982 1615737473753709
983 1630238486982752
984 1644855066147931
985 1659588016249091
986 1674438147200658
987 1689406273630256
988 1704493215127481
989 1719699796044485
990 1735026845743222
991 1750475198394800
992 1766045693231503
993 1781739174341773
994 1797556490923720
995 1813498497082248
996 1829566052080826
997 1845760020137501
998 1862081270681410
999 1878530678144406
1000 1895109122219166