0 1
1 1
2 2
3 3
4 5
5 7
6 12
7 16
8 24
9 33
10 47
11 63
12 88
13 115
14 155
15 202
16 266
17 341
18 443
19 560
20 715
21 897
22 1129
23 1401
24 1746
25 2146
26 2645
27 3228
28 3941
29 4771
30 5781
31 6948
32 8353
33 9979
34 11913
35 14144
36 16785
37 19814
38 23374
39 27454
40 32211
41 37645
42 43954
43 51130
44 59417
45 68827
46 79631
47 91863
48 105857
49 121645
50 139632
51 159885
52 182857
53 208655
54 237827
55 270492
56 307304
57 348441
58 394639
59 446144
60 503833
61 567987
62 639641
63 719174
64 807751
65 905862
66 1014878
67 1135364
68 1268922
69 1416271
70 1579215
71 1758647
72 1956668
73 2174308
74 2414000
75 2677011
76 2966076
77 3282728
78 3630125
79 4010029
80 4426069
81 4880359
82 5376971
83 5918417
84 6509361
85 7152676
86 7853684
87 8615773
88 9444901
89 10345033
90 11322948
91 12383157
92 13533346
93 14778764
94 16127992
95 17587102
96 19165796
97 20870946
98 22713492
99 24701343
100 26846677
101 29158553
102 31650665
103 34333216
104 37221567
105 40327354
106 43667625
107 47255600
108 51110354
109 55246704
110 59685948
111 64444853
112 69546986
113 75011263
114 80863932
115 87126101
116 93826948
117 100990200
118 108648051
119 116827104
120 125563065
121 134885493
122 144833922
123 155441388
124 166751385
125 178800751
126 191637538
127 205302517
128 219848696
129 235321405
130 251778801
131 269271184
132 287862575
133 307608441
134 328579163
135 350836127
136 374456341
137 399507622
138 426074463
139 454231391
140 484070995
141 515675408
142 549145677
143 584572181
144 622065443
145 661724465
146 703669997
147 748010732
148 794878125
149 844391345
150 896693760
151 951915515
152 1010212804
153 1071728017
154 1136630792
155 1205076723
156 1277250317
157 1353321019
158 1433489315
159 1517940001
160 1606890326
161 1700541598
162 1799129507
163 1902872703
164 2012026651
165 2126829107
166 2247556295
167 2374466478
168 2507858610
169 2648012500
170 2795251430
171 2949878827
172 3112243518
173 3282674229
174 3461547638
175 3649219060
176 3846094925
177 4052559558
178 4269050640
179 4495983511
180 4733829788
181 4983037407
182 5244114176
183 5517543455
184 5803871063
185 6103618159
186 6417371694
187 6745692551
188 7089211475
189 7448532357
190 7824331933
191 8217259905
192 8628042614
193 9057377898
194 9506044830
195 9974793190
196 10464457412
197 10975842508
198 11509842454
199 12067320279
200 12649233156
201 13256506525
202 13890163885
203 14551196942
204 15240700334
205 15959735343
206 16709472006
207 17491046243
208 18305707193
209 19154669902
210 20039268141
211 20960799997
212 21920688815
213 22920321539
214 23961215445
215 25044851543
216 26172847373
217 27346782612
218 28568380785
219 29839326899
220 31161455561
221 32536563127
222 33966602524
223 35453486847
224 36999293933
225 38606061224
226 40275997406
227 42011271205
228 43814230408
229 45687181297
230 47632618332
231 49652994021
232 51750956382
233 53929112118
234 56190272189
235 58537204764
236 60972892413
237 63500274623
238 66122513534
239 68842729074
240 71664273594
241 74590455854
242 77624828314
243 80770899744
244 84032431869
245 87413143878
246 90917018804
247 94547995906
248 98310290797
249 102208075447
250 106245808548
251 110427906628
252 114759085053
253 119244015970
254 123887684218
255 128695031832
256 133671325118
257 138821789440
258 144151987895
259 149667441809
260 155374025560
261 161277572502
262 167384281957
263 173700314528
264 180232211706
265 186986475719
266 193970006596
267 201189666247
268 208652728756
269 216366432896
270 224338446134
271 232576400421
272 241088375049
273 249882415401
274 258967030164
275 268350697505
276 278042377145
277 288050998493
278 298385993045
279 309056764122
280 320073234831
281 331445304146
282 343183410970
283 355297970768
284 367799961500
285 380700340442
286 394010646953
287 407742404496
288 421907740810
289 436518768995
290 451588231207
291 467128858416
292 483154032291
293 499677128945
294 516712199604
295 534273291853
296 552375155554
297 571032541183
298 590260925372
299 610075791937
300 630493377671
301 651529929216
302 673202475943
303 695528062235
304 718524541497
305 742209789774
306 766602521557
307 791721477507
308 817586269271
309 844216540845
310 871632836132
311 899855740186
312 928906770206
313 958807489055
314 989580427286
315 1021248168444
316 1053834295514
317 1087362454590
318 1121857326487
319 1157343660746
320 1193847280413
321 1231394085866
322 1270011085809
323 1309725377853
324 1350565206485
325 1392558911966
326 1435736023702
327 1480126176911
328 1525760234086
329 1572669176714
330 1620885255641
331 1670440848968
332 1721369650173
333 1773705491619
334 1827483562741
335 1882739206824
336 1939509170099
337 1997830362472
338 2057741146846
339 2119280063186
340 2182487149991
341 2247402639743
342 2314068313420
343 2382526157549
344 2452819761519
345 2524992935604
346 2599091142610
347 2675160085307
348 2753247173343
349 2833400069820
350 2915668203725
351 3000101274976
352 3086750803490
353 3175668601561
354 3266908360531
355 3360524079745
356 3456571701561
357 3555107496181
358 3656189735711
359 3759877044131
360 3866230111418
361 3975309997396
362 4087179897174
363 4201903398143
364 4319546286980
365 4440174769506
366 4563857320322
367 4690662853737
368 4820662627815
369 4953928365595
370 5090534203364
371 5230554772327
372 5374067192212
373 5521149101074
374 5671880706542
375 5826342762942
376 5984618669534
377 6146792405581
378 6312950676743
379 6483180795199
380 6657572887067
381 6836217716731
382 7019208944165
383 7206640904571
384 7398610916801
385 7595217004855
386 7796560270849
387 8002742557481
388 8213868873933
389 8430045010891
390 8651380020643
391 8877983770605
392 9109969491647
393 9347451269207
394 9590546647718
395 9839374071404
396 10094055546115
397 10354714015157
398 10621476093191
399 10894469376113
400 11173825234371
401 11459676069517
402 11752158168310
403 12051408890670
404 12357569599823
405 12670782780646
406 12991195032681
407 13318954132020
408 13654212088614
409 13997122135777
410 14347841867703
411 14706530155526
412 15073350351318
413 15448467144419
414 15832049833387
415 16224269106021
416 16625300395830
417 17035320584646
418 17454511429337
419 17883056201265
420 18321143184774
421 18768962236246
422 19226708371616
423 19694578243879
424 20172773804752
425 20661498715483
426 21160962084259
427 21671374792368
428 22192953325302
429 22725916013067
430 23270486939523
431 23826892112280
432 24395363451930
433 24976134872882
434 25569446371139
435 26175540014820
436 26794664114406
437 27427069139006
438 28073011970806
439 28732751727675
440 29406554121206
441 30094687184365
442 30797425716430
443 31515046932371
444 32247834996457
445 32996076573230
446 33760065469930
447 34540098087705
448 35336478155521
449 36149512098927
450 36979513867304
451 37826800199271
452 38691695564186
453 39574527322800
454 40475630765007
455 41395344183725
456 42334014010811
457 43291989782474
458 44269629395075
459 45267293960598
460 46285353163659
461 47324180025698
462 48384156365191
463 49465667448060
464 50569107573593
465 51694874609559
466 52843375684475
467 54015021626776
468 55210232765496
469 56429433250149
470 57673056983178
471 58941541818968
472 60235335607987
473 61554890295008
474 62900668077069
475 64273135376716
476 65672769137978
477 67100050672999
478 68555472075247
479 70039529960311
480 71552731998547
481 73095590524991
482 74668629216518
483 76272376569181
484 77907372698330
485 79574162704916
486 81273303600859
487 83005357538369
488 84770898886533
489 86570507321890
490 88404775033942
491 90274299699275
492 92179691818354
493 94121567546351
494 96100556188093
495 98117292883773
496 100172426238971
497 102266610888328
498 104400515263098
499 106574814004986
500 108790195899037
501 111047356135756
502 113347004385468
503 115689856932600
504 118076644894022
505 120508106196758
506 122984993969079
507 125508068359686
508 128078105076877
509 130695887073886
510 133362213238736
511 136077889916019
512 138843739777175
513 141660593176707
514 144529297177363
515 147450706766307
516 150425694037893
517 153455139239090
518 156539940140606
519 159681002909461
520 162879251642092
521 166135619090454
522 169451056359892
523 172826523457054
524 176262999184277
525 179761471507155
526 183322947618210
527 186948444151358
528 190638997417743
529 194395653434331
530 198219478364718
531 202111548359614
532 206072960174498
533 210104820850147
534 214208258510094
535 218384411847371
536 222634441135639
537 226959517519841
538 231360834211991
539 235839595614771
540 240397028705029
541 245034371955414
542 249752886940551
543 254553847054334
544 259438549308809
545 264408302877109
546 269464441088198
547 274608309759426
548 279841279423216
549 285164733446768
550 290580080459795
551 296088742292299
552 301692166606599
553 307391814616046
554 313189173958544
555 319085746193659
556 325083059885765
557 331182657911446
558 337386110755631
559 343695003590969
560 350110949825316
561 356635577950465
562 363270545308142
563 370017524740983
564 376878218580469
565 383854345060673
566 390947652567691
567 398159905813448
568 405492900312779
569 412948448351182
570 420528393693103
571 428234597302947
572 436068952325322
573 444033369556534
574 452129792661905
575 460360183432671
576 468726537244024
577 477230868055508
578 485875224151792
579 494661672883671
580 503592316655642
581 512669277443488
582 521894713032424
583 531270801268112
584 540799756588605
585 550483814005834
586 560325245894366
587 570326345740402
588 580489445191228
589 590816897527282
590 601311095016829
591 611974452108038
592 622809423050801
593 633818484846973
594 645004155143310
595 656368974894133
596 667915526571212
597 679646416535714
598 691564293525866
599 703671830777419
600 715971744793182
601 728466777164947
602 741159713672062
603 754053365801587
604 767150590135574
605 780454269609844
606 793967333194191
607 807692736841365
608 821633483508728
609 835792603794101
610 850173176257413
611 864778307784949
612 879611154215316
613 894674900382324
614 909972781095164
615 925508060856486
616 941284055154148
617 957304109897215
618 973571623023747
619 990090023603515
620 1006862793813131
621 1023893447701958
622 1041185553490758
623 1058742712044722
624 1076568579500190
625 1094666845392193
626 1113041255661993
627 1131695590435503
628 1150633687366609
629 1169859419111602
630 1189376717012984
631 1209189548215837
632 1229301939746315
633 1249717955266237
634 1270441719499970
635 1291477394673630
636 1312829205295174
637 1334501414222664
638 1356498347853281
639 1378824371816798
640 1401483916525964
641 1424481452542847
642 1447821516495545
643 1471508686060352
644 1495547606301985
645 1519942964267636
646 1544699515701892
647 1569822059301613
648 1595315463810636
649 1621184641876882
650 1647434577585599
651 1674070299914643
652 1701096910656119
653 1728519557520114
654 1756343462449945
655 1784573894314188
656 1813216197675847
657 1842275765068525
658 1871758066168067
659 1901668619704451
660 1932013023041253
661 1962796923661523
662 1994026049216995
663 2025706178583685
664 2057843172328007
665 2090442943385057
666 2123511487947132
667 2157054855701338
668 2191079181204063
669 2225590653673515
670 2260595548795959
671 2296100198127522
672 2332111021337821
673 2368634495156054
674 2405677186117206
675 2443245719047919
676 2481346810259675
677 2519987235630202
678 2559173864249429
679 2598913626029735
680 2639213545871548
681 2680080710797823
682 2721522304582272
683 2763545574465263
684 2806157866250582
685 2849366590534385
686 2893179258339085
687 2937603446850612
688 2982646835530968
689 3028317171422426
690 3074622305744827
691 3121570158696610
692 3169168756607172
693 3217426196229888
694 3266350682389586
695 3315950491827674
696 3366234011350944
697 3417209701156948
698 3468886133556248
699 3521271955773037
700 3574375929179392
701 3628206891632774
702 3682773797228664
703 3738085678101299
704 3794151684768565
705 3850981047390865
706 3908583116645317
707 3966967324505908
708 4026143225653533
709 4086120457701960
710 4146908783219438
711 4208518049395227
712 4270958230608267
713 4334239387599010
714 4398371710591825
715 4463365477894814
716 4529231099653527
717 4595979075873398
718 4663620040738717
719 4732164720123962
720 4801623976484869
721 4872008765779476
722 4943330183010764
723 5015599418551922
724 5088827804272866
725 5163026769337635
726 5238207886921805
727 5314382829400913
728 5391563415740161
729 5469761566068224
730 5548989349669955
731 5629258939015110
732 5710582658361224
733 5792972937154240
734 5876442359324882
735 5961003616055410
736 6046669555698542
737 6133453135981539
738 6221367474555041
739 6310425800549460
740 6400641505839039
741 6492028095944647
742 6584599241940453
743 6678368730776015
744 6773350517833062
745 6869558676579885
746 6967007451865558
747 7065711208900573
748 7165684487214195
749 7266941949035926
750 7369498433923689
751 7473368906457087
752 7578568511625777
753 7685112521828351
754 7793016392944850
755 7902295710717594
756 8012966247515695
757 8125043908006753
758 8238544786704832
759 8353485112926660
760 8469881309045268
761 8587749934808799
762 8707107746307861
763 8827971639563773
764 8950358710303157
765 9074286196809141
766 9199771540423623
767 9326832327741315
768 9455486351847916
769 9585751553761682
770 9717646084503199
771 9851188245777836
772 9986396552795734
773 10123289674276874
774 10261886496029682
775 10402206060181246
776 10544267629612387
777 10688090626406241
778 10833694697056607
779 10981099650218430
780 11130325522698016
781 11281392516405774
782 11434321065228364
783 11589131771176764
784 11745845472055256
785 11904483176890256
786 12065066134404933
787 12227615767626927
788 12392153743270904
789 12558701905518053
790 12727282346219624
791 12897917337935530
792 13070629404967844
793 13245441255554407
794 13422375853836836
795 13601456351201874
796 13782706159095026
797 13966148879598922
798 14151808379101782
799 14339708718006360
800 14529874225360097
801 14722329427687233
802 14917099124489834
803 15114208316294307
804 15313682281032653
805 15515546501194664
806 15719826741198610
807 15926548973641527
808 16135739457566558
809 16347424663904533
810 16561631354647547
811 16778386507370746
812 16997717395423706
813 17219651511524698
814 17444216648875068
815 17671440823921201
816 17901352358401677
817 18133979801163475
818 18369352011255901
819 18607498078793092
820 18848447408997890
821 19092229642207924
822 19338874738879427
823 19588412898621019
824 19840874646273854
825 20096290749965024
826 20354692308165166
827 20616110666860826
828 20880577507599737
829 21148124763663790
830 21418784709220874
831 21692589874490187
832 21969573135899669
833 22249767630345126
834 22533206846363658
835 22819924537365760
836 23109954813946129
837 23403332056080312
838 23700091006469840
839 24000266681806981
840 24303894467164822
841 24611010026206781
842 24921649396745578
843 25235848899888902
844 25553645236662025
845 25875075396195376
846 26200176753421653
847 26528986976179385
848 26861544124111064
849 27197886554673891
850 27538053023131539
851 27882082587580012
852 28230014710044104
853 28581889160389891
854 28937746118654998
855 29297626077838741
856 29661569947356597
857 30029618954818161
858 30401814750617140
859 30778199308565968
860 31158815031753089
861 31543704652025075
862 31932911336999373
863 32326478588506349
864 32724450350768999
865 33126870907671128
866 33533784992238490
867 33945237682723746
868 34361274513274947
869 34781941368951956
870 35207284597594038
871 35637350903631241
872 36072187461288265
873 36511841807181287
874 36956361954741708
875 37405796285715426
876 37860193665818444
877 38319603334999365
878 38784075024466823
879 39253658845705441
880 39728405408756365
881 40208365710106047
882 40693591252232118
883 41184133930223002
884 41680046152731832
885 42181380727316975
886 42688190982682930
887 43200530652863487
888 43718454000762089
889 44242015701032800
890 44771270965065698
891 45306275422555521
892 45847085247808629
893 46393757040123492
894 46946347951431925
895 47504915565343750
896 48069518026270727
897 48640213917125072
898 49217062389800238
899 49800123041649842
900 50389456047338250
901 50985122033949377
902 51587182214358421
903 52195698260960018
904 52810732440432779
905 53432347486215858
906 54060606734679510
907 54695573996196603
908 55337313692873489
909 55985890728205714
910 56641370626238410
911 57303819399937748
912 57973303691794310
913 58649890640753892
914 59333648024421105
915 60024644124538580
916 60722947870657480
917 61428628704299200
918 62141756724106541
919 62862402548528465
920 63590637462612204
921 64326533279199925
922 65070162487225928
923 65821598111561887
924 66580913862833094
925 67348183995749837
926 68123483460606038
927 68906887760085394
928 69698473102303990
929 70498316256230448
930 71306494706286770
931 72123086506216969
932 72948170435412572
933 73781825851218178
934 74624132846840571
935 75475172102233086
936 76335025043602840
937 77203773692705286
938 78081500828119162
939 78968289832939405
940 79864224857676133
941 80769390666490481
942 81683872801732409
943 82607757428547697
944 83541131501227300
945 84484082606173487
946 85436699129914400
947 86399070100576584
948 87371285357579821
949 88353435391441077
950 89345611515325581
951 90347905703169935
952 91360410762940375
953 92383220173225057
954 93416428258214825
955 94460130022586478
956 95514421328385253
957 96579398728186608
958 97655159643728653
959 98741802197505174
960 99839425393163622
961 100948128945347932
962 102068013462044589
963 103199180272662552
964 104341731612172801
965 105495770447580928
966 106661400663876075
967 107838726888711424
968 109027854680348385
969 110228890350532038
970 111441941154273205
971 112667115111077225
972 113904521196580091
973 115154269161942482
974 116416469727529174
975 117691234400455151
976 118978675670148070
977 120278906824207715
978 121592042145868024
979 122918196727978371
980 124257486672557782
981 125610028902884645
982 126975941364980039
983 128355342837970042
984 129748353137514920
985 131155092924249129
986 132575683909352463
987 134010248661054094
988 135458910812179699
989 136921794864886622
990 138399026400204062
991 139890731880800969
992 141397038862718876
993 142918075796158666
994 144453972239237099
995 146004858656962513
996 147570866637032414
997 149152128686796232
998 150748778451297132
999 152360950508207659
1000 153988780587943850