0 1
1 1
2 2
3 3
4 5
5 7
6 11
7 15
8 22
9 30
10 42
11 55
12 75
13 97
14 128
15 164
16 212
17 267
18 340
19 423
20 530
21 653
22 807
23 984
24 1204
25 1455
26 1761
27 2112
28 2534
29 3015
30 3590
31 4242
32 5013
33 5888
34 6912
35 8070
36 9418
37 10936
38 12690
39 14663
40 16928
41 19466
42 22367
43 25608
44 29292
45 33401
46 38047
47 43214
48 49037
49 55494
50 62740
51 70760
52 79725
53 89623
54 100654
55 112804
56 126299
57 141136
58 157564
59 175586
60 195491
61 217280
62 241279
63 267507
64 296320
65 327748
66 362198
67 399705
68 440725
69 485315
70 533975
71 586779
72 644295
73 706607
74 774345
75 847628
76 927143
77 1013036
78 1106080
79 1206440
80 1314972
81 1431884
82 1558110
83 1693899
84 1840292
85 1997569
86 2166875
87 2348553
88 2543849
89 2753159
90 2977866
91 3218412
92 3476314
93 3752096
94 4047402
95 4362833
96 4700201
97 5060174
98 5444732
99 5854649
100 6292069
101 6757864
102 7254388
103 7782608
104 8345084
105 8942920
106 9578879
107 10254199
108 10971900
109 11733342
110 12541802
111 13398814
112 14307910
113 15270794
114 16291308
115 17371322
116 18514989
117 19724399
118 21004018
119 22356152
120 23785645
121 25295011
122 26889475
123 28571827
124 30347671
125 32220069
126 34195076
127 36276024
128 38469427
129 40778952
130 43211575
131 45771300
132 48465645
133 51298950
134 54279279
135 57411388
136 60703893
137 64161965
138 67794864
139 71608176
140 75611815
141 79811865
142 84218903
143 88839522
144 93685056
145 98762607
146 104084280
147 109657784
148 115496010
149 121607276
150 128005367
151 134699218
152 141703526
153 149027949
154 156688108
155 164694398
156 173063483
157 181806502
158 190941187
159 200479536
160 210440370
161 220836558
162 231688140
163 243008877
164 254820051
165 267136439
166 279980591
167 293368323
168 307323599
169 321863286
170 337012795
171 352790186
172 369222348
173 386328561
174 404137344
175 422669224
176 441954389
177 462014762
178 482882242
179 504580179
180 527142353
181 550593568
182 574969531
183 600296674
184 626612672
185 653945620
186 682335346
187 711811649
188 742416568
189 774181780
190 807151588
191 841359596
192 876852573
193 913666096
194 951849458
195 991440410
196 1032490831
197 1075040697
198 1119144696
199 1164845082
200 1212199424
201 1261252465
202 1312064727
203 1364683514
204 1419172533
205 1475581709
206 1533978017
207 1594414239
208 1656960705
209 1721673120
210 1788625426
211 1857876328
212 1929503474
213 2003568823
214 2080153818
215 2159323761
216 2241164168
217 2325743765
218 2413152252
219 2503462052
220 2596767156
221 2693143777
222 2792690497
223 2895487426
224 3001637852
225 3111226073
226 3224360204
227 3341128846
228 3461645269
229 3586002480
230 3714319039
231 3846692681
232 3983247392
233 4124085762
234 4269337546
235 4419110319
236 4573539756
237 4732738757
238 4896849074
239 5065989072
240 5240306955
241 5419926691
242 5605003104
243 5795666145
244 5992077422
245 6194373023
246 6402721743
247 6617265971
248 6838181881
249 7065618551
250 7299759723
251 7540761345
252 7788815159
253 8044084163
254 8306768300
255 8577038050
256 8855101766
257 9141137602
258 9435362790
259 9737963356
260 10049165639
261 10369163991
262 10698194089
263 11036458839
264 11384203747
265 11741640489
266 12109024651
267 12486577175
268 12874563987
269 13273215526
270 13682808589
271 14103583360
272 14535827783
273 14979792315
274 15435776320
275 15904040798
276 16384897101
277 16878617036
278 17385524251
279 17905901922
280 18440086299
281 18988372213
282 19551109123
283 20128603822
284 20721219301
285 21329274912
286 21953147513
287 22593169339
288 23249731768
289 23923180231
290 24613920986
291 25322313307
292 26048778697
293 26793690624
294 27557486519
295 28340554403
296 29143348027
297 29966270645
298 30809792731
299 31674333152
300 32560379840
301 33468367656
302 34398802415
303 35352135714
304 36328891676
305 37329539043
306 38354621028
307 39404623944
308 40480110561
309 41581585529
310 42709631643
311 43864772345
312 45047611286
313 46258691159
314 47498636963
315 48768011474
316 50067461545
317 51397570518
318 52759007990
319 54152378363
320 55578374517
321 57037622787
322 58530839883
323 60058674614
324 61621868450
325 63221093205
326 64857115690
327 66530631663
328 68242433873
329 69993242580
330 71783877465
331 73615083875
332 75487709049
333 77402524413
334 79360405392
335 81362150112
336 83408663238
337 85500770215
338 87639405628
339 89825423290
340 92059788389
341 94343383763
342 96677206319
343 99062168606
344 101499299965
345 103989543763
346 106533962509
347 109133531106
348 111789346419
349 114502415598
350 117273870639
351 120104752122
352 122996227961
353 125949372933
354 128965392111
355 132045395252
356 135190625418
357 138402228586
358 141681486657
359 145029582647
360 148447838616
361 151937475445
362 155499856241
363 159136241082
364 162848035015
365 166636538187
366 170503198979
367 174449358505
368 178476509436
369 182586035231
370 186779473814
371 191058251934
372 195423954239
373 199878051724
374 204422176765
375 209057846078
376 213786740795
377 218610424350
378 223530628190
379 228548963484
380 233667213073
381 238887037405
382 244210271810
383 249638627100
384 255173992721
385 260818130929
386 266572986435
387 272440374580
388 278422296514
389 284520621789
390 290737409717
391 297074585225
392 303534267009
393 310118437095
394 316829274795
395 323668820455
396 330639315816
397 337742860770
398 344981760794
399 352358177138
400 359874480333
401 367532894271
402 375335856445
403 383285654715
404 391384794906
405 399635630748
406 408040737797
407 416602537031
408 425323675752
409 434206643563
410 443254160974
411 452468788227
412 461853320524
413 471410390204
414 481142869260
415 491053463612
416 501145123594
417 511420630810
418 521883015516
419 532535136542
420 543380106280
421 554420862345
422 565660600906
423 577102340596
424 588749363016
425 600604769445
426 612671929241
427 624954027995
428 637454524566
429 650176691169
430 663124077925
431 676300045410
432 689708237446
433 703352104728
434 717235386604
435 731361626338
436 745734660665
437 760358127241
438 775235962754
439 790371901107
440 805769980879
441 821434034774
442 837368205227
443 853576425694
444 870062945137
445 886831799718
446 903887346971
447 921233728457
448 938875412365
449 956816647680
450 975062016054
451 993615875974
452 1012482924711
453 1031667633071
454 1051174816121
455 1071009059147
456 1091175297952
457 1111678234479
458 1132522927549
459 1153714198707
460 1175257232096
461 1197156971126
462 1219418728339
463 1242047571330
464 1265048943423
465 1288428039475
466 1312190436018
467 1336341457571
468 1360886817102
469 1385831971200
470 1411182771787
471 1436944810757
472 1463124081539
473 1489726313852
474 1516757645987
475 1544223948049
476 1572131505839
477 1600486333215
478 1629294866182
479 1658563264998
480 1688298119389
481 1718505738690
482 1749192869131
483 1780365972670
484 1812031954851
485 1844197433032
486 1876869475745
487 1910054858578
488 1943760815984
489 1977994285449
490 2012762670309
491 2048073072881
492 2083933069220
493 2120349929442
494 2157331405378
495 2194884938800
496 2233018460424
497 2271739586741
498 2311056431366
499 2350976788620
500 2391508958235
501 2432660916371
502 2474441152138
503 2516857826777
504 2559919622942
505 2603634890212
506 2648012508159
507 2693061018901
508 2738789502356
509 2785206696542
510 2832321886079
511 2880144008317
512 2928682556113
513 2977946670524
514 3027946056214
515 3078690061497
516 3130188607385
517 3182451253029
518 3235488139501
519 3289309041345
520 3343924323443
521 3399343979433
522 3455578602738
523 3512638409868
524 3570534226650
525 3629276497208
526 3688876283697
527 3749344261747
528 3810691734780
529 3872929613846
530 3936069447687
531 4000122387730
532 4065100232141
533 4131014376790
534 4197876874387
535 4265699369369
536 4334494173227
537 4404273184109
538 4475048976589
539 4546833706773
540 4619640217658
541 4693480927602
542 4768368952453
543 4844316978205
544 4921338398029
545 4999446169987
546 5078653970129
547 5158975033091
548 5240423322438
549 5323012354941
550 5406756386362
551 5491669220255
552 5577765410358
553 5665059051708
554 5753565000835
555 5843297650073
556 5934272163632
557 6026503235978
558 6120006345020
559 6214796492258
560 6310889474338
561 6408300605820
562 6507046007187
563 6607141311136
564 6708602968218
565 6811446934376
566 6915689995484
567 7021348437013
568 7128439385490
569 7236979461167
570 7346986137711
571 7458476375502
572 7571468000825
573 7685978320709
574 7802025519589
575 7919627256651
576 8038802081217
577 8159568010186
578 8281943963487
579 8405948322500
580 8531600383538
581 8658918898183
582 8787923546126
583 8918633454973
584 9051068693727
585 9185248773037
586 9321194157235
587 9458924745993
588 9598461406243
589 9739824432700
590 9883035101087
591 10028114108467
592 10175083145618
593 10323963318171
594 10474776739478
595 10627544930038
596 10782290432220
597 10939035188952
598 11097802178151
599 11258613771642
600 11421493390702
601 11586463842590
602 11753548998646
603 11922772109438
604 12094157503137
605 12267728880343
606 12443511034158
607 12621528122035
608 12801805408990
609 12984367517449
610 13169240191393
611 13356448525233
612 13546018750311
613 13737976440109
614 13932348320563
615 14129160452677
616 14328440064310
617 14530213711257
618 14734509132013
619 14941353384525
620 15150774725453
621 15362800723633
622 15577460161505
623 15794781126382
624 16014792935484
625 16237524202242
626 16463004786477
627 16691263836810
628 16922331763585
629 17156238258449
630 17393014291603
631 17632690105677
632 17875297238850
633 18120866494124
634 18369429985854
635 18621019085585
636 18875666493512
637 19133404157965
638 19394265373421
639 19658282674710
640 19925489959114
641 20195920356423
642 20469608376727
643 20746587753366
644 21026893617970
645 21310560317477
646 21597623613900
647 21888118476576
648 22182081308264
649 22479547709564
650 22780554733053
651 23085138621013
652 23393337085010
653 23705187018130
654 24020726801621
655 24339993988602
656 24663027639410
657 24989865977954
658 25320548753182
659 25655114869246
660 25993604774778
661 26336058063721
662 26682515894141
663 27033018560933
664 27387607941439
665 27746325041297
666 28109212468573
667 28476311949567
668 28847666833186
669 29223319577882
670 29603314283615
671 29987694151157
672 30376504043354
673 30769787913568
674 31167591397983
675 31569959214464
676 31976937783110
677 32388572596801
678 32804910871793
679 33225998886613
680 33651884664512
681 34082615281952
682 34518239580132
683 34958805444372
684 35404362546437
685 35854959591507
686 36310647093133
687 36771474589073
688 37237493446016
689 37708754045555
690 38185308620564
691 38667208407883
692 39154506518183
693 39647255056679
694 40145508023557
695 40649318404095
696 41158741101467
697 41673829992801
698 42194640896287
699 42721228594453
700 43253649832643
701 43791960310855
702 44336217715495
703 44886478676264
704 45442801833041
705 46005244759210
706 46573867060677
707 47148727267017
708 47729885964531
709 48317402651585
710 48911338907724
711 49511755214556
712 50118714157850
713 50732277215382
714 51352507993941
715 51979468980537
716 52613224816261
717 53253839012246
718 53901377257316
719 54555904100083
720 55217486292383
721 55886189433789
722 56562081352875
723 57245228715574
724 57935700441047
725 58633564275381
726 59338890244082
727 60051747187348
728 60772206251226
729 61500337385852
730 62236212872137
731 62979903784431
732 63731483554757
733 64491024396090
734 65258600906197
735 66034286453037
736 66818156814914
737 67610286529493
738 68410752572380
739 69219630665823
740 70036998997855
741 70862934492148
742 71697516564436
743 72540823355057
744 73392935524694
745 74253932445704
746 75123896039333
747 76002906927339
748 76891048307313
749 77788402066094
750 78695052695407
751 79611083363045
752 80536579870982
753 81471626685867
754 82416310936179
755 83370718403647
756 84334937561581
757 85309055523147
758 86293162123129
759 87287345824567
760 88291697840507
761 89306308000578
762 90331268914964
763 91366671796801
764 92412610670547
765 93469178151826
766 94536469696687
767 95614579340510
768 96703603990389
769 97803639118854
770 98914783101733
771 100037132868277
772 101170788280906
773 102315847743393
774 103472412624746
775 104640582821239
776 105820461226707
777 107012149250050
778 108215751328357
779 109431370401501
780 110659112470425
781 111899082024486
782 113151386647282
783 114416132398412
784 115693428463090
785 116983382490060
786 118286105287353
787 119601706111965
788 120930297414135
789 122271990080416
790 123626898222812
791 124995134376940
792 126376814338383
793 127772052311503
794 129180965795409
795 130603670685172
796 132040286203576
797 133490929956475
798 134955722912785
799 136434784409413
800 137928237181972
801 139436202320991
802 140958804349534
803 142496166132474
804 144048414003391
805 145615672622372
806 147198070154692
807 148795733078892
808 150408791413332
809 152037373476288
810 153681611162941
811 155341634652821
812 157017577739737
813 158709572488363
814 160417754613125
815 162142258085797
816 163883220565826
817 165640777954216
818 167415069877901
819 169206234191670
820 171014412512596
821 172839744671829
822 174682374301668
823 176542443232448
824 178420097134782
825 180315479863422
826 182228739150608
827 184160020898772
828 186109474927581
829 188077249210576
830 190063495678626
831 192068364402341
832 194092009447780
833 196134583006550
834 198196241306377
835 200277138684017
836 202377433553323
837 204497282422849
838 206636845917269
839 208796282741545
840 210975755758393
841 213175425894001
842 215395458274286
843 217636016074087
844 219897266707885
845 222179375624474
846 224482512554861
847 226806845247349
848 229152545775361
849 231519784214818
850 233908735007659
851 236319570583472
852 238752467781430
853 241207601411057
854 243685150735344
855 246185292972665
856 248708209836663
857 251254080981318
858 253823090600432
859 256415420810591
860 259031258313102
861 261670787716820
862 264334198258140
863 267021677065737
864 269733415941353
865 272469604561226
866 275230437320551
867 278016106473613
868 280826809037425
869 283662739872571
870 286524098648962
871 289411082862022
872 292323894863441
873 295262734814765
874 298227807778573
875 301219316611611
876 304237469119246
877 307282470882723
878 310354532479887
879 313453862248580
880 316580673569050
881 319735177565582
882 322917590453561
883 326128126173862
884 329367003807468
885 332634440144773
886 335930657163095
887 339255874533034
888 342610317161847
889 345994207631240
890 349407773809712
891 352851241223889
892 356324840735078
893 359828800846331
894 363363355446199
895 366928736045941
896 370525179593495
897 374152920642986
898 377812199234169
899 381503252996379
900 385226325096527
901 388981656271761
902 392769492849148
903 396590078709247
904 400443663372536
905 404330493896180
906 408250823030310
907 412204901042197
908 416192983945517
909 420215325254087
910 424272184279281
911 428363817815565
912 432490488509173
913 436652456469595
914 440849987712670
915 445083345700325
916 449352799853054
917 453658617020192
918 458001070065005
919 462380429259505
920 466796970945403
921 471250968855714
922 475742702846558
923 480272450147887
924 484840494169264
925 489447115673756
926 494092601660968
927 498777236466399
928 503501310716610
929 508265112356330
930 513068935679103
931 517913072276033
932 522797820145189
933 527723474564336
934 532690337273894
935 537698707276085
936 542748890094698
937 547841188494483
938 552975911821121
939 558153366643165
940 563373866167001
941 568637720803719
942 573945247662437
943 579296761035877
944 584692581975354
945 590133028697501
946 595618426235629
947 601149096770033
948 606725369359095
949 612347570186790
950 618016032377054
951 623731086160886
952 629493068768580
953 635302314518904
954 641159164792593
955 647063958037263
956 653017039825590
957 659018752778406
958 665069446702175
959 671169468432705
960 677319172055417
961 683518908663173
962 689769036662888
963 696069911449969
964 702421895795675
965 708825349440750
966 715280639567052
967 721788130303820
968 728348193287123
969 734961197081208
970 741627517820287
971 748347528547500
972 755121609942562
973 761950139571722
974 768833502704845
975 775772081478965
976 782766265799111
977 789816442418037
978 796923005924441
979 804086347732093
980 811306867159122
981 818584960329090
982 825921031335672
983 833315481058311
984 840768718415838
985 848281149089969
986 855853186871568
987 863485242294584
988 871177734069170
989 878931077628647
990 886745696653253
991 894622011523232
992 902560450936919
993 910561440272603
994 918625413295073
995 926752800428995
996 934944040557594
997 943199569200582
998 951519830408807
999 959905264849333
1000 968356321790171