0 1
1 1
2 4
3 8
4 18
5 32
6 58
7 94
8 151
9 227
10 338
11 480
12 676
13 920
14 1242
15 1636
16 2137
17 2739
18 3486
19 4370
20 5444
21 6698
22 8196
23 9926
24 11963
25 14293
26 17002
27 20076
28 23612
29 27594
30 32134
31 37212
32 42955
33 49341
34 56512
35 64444
36 73294
37 83036
38 93844
39 105690
40 118765
41 133037
42 148718
43 165772
44 184430
45 204654
46 226694
47 250510
48 276373
49 304239
50 334402
51 366814
52 401792
53 439284
54 479632
55 522780
56 569093
57 618513
58 671430
59 727782
60 787986
61 851974
62 920192
63 992568
64 1069575
65 1151137
66 1237756
67 1329352
68 1426456
69 1528984
70 1637498
71 1751908
72 1872809
73 2000105
74 2134424
75 2275666
76 2424490
77 2580792
78 2745266
79 2917802
80 3099129
81 3289131
82 3488574
83 3697336
84 3916220
85 4145098
86 4384810
87 4635224
88 4897217
89 5170651
90 5456444
91 5754450
92 6065628
93 6389826
94 6728044
95 7080124
96 7447107
97 7828829
98 8226374
99 8639572
100 9069550
101 9516130
102 9980486
103 10462432
104 10963187
105 11482559
106 12021812
107 12580748
108 13160678
109 13761396
110 14384262
111 15029062
112 15697205
113 16388469
114 17104314
115 17844510
116 18610566
117 19402246
118 20221110
119 21066914
120 21941271
121 22843927
122 23776550
123 24738878
124 25732632
125 26757542
126 27815384
127 28905880
128 30030861
129 31190041
130 32385308
131 33616366
132 34885162
133 36191390
134 37537056
135 38921846
136 40347823
137 41814665
138 43324496
139 44876984
140 46474314
141 48116144
142 49804722
143 51539696
144 53323377
145 55155403
146 57038148
147 58971242
148 60957122
149 62995408
150 65088604
151 67236318
152 69441121
153 71702611
154 74023426
155 76403154
156 78844500
157 81347042
158 83913554
159 86543604
160 89240035
161 92002403
162 94833624
163 97733242
164 100704244
165 103746164
166 106862060
167 110051456
168 113317483
169 116659653
170 120081172
171 123581540
172 127164038
173 130828154
174 134577246
175 138410790
176 142332219
177 146340999
178 150440640
179 154630596
180 158914456
181 163291660
182 167765878
183 172336538
184 177007389
185 181777847
186 186651742
187 191628478
188 196711966
189 201901598
190 207201368
191 212610654
192 218133535
193 223769375
194 229522338
195 235391776
196 241381936
197 247492158
198 253726776
199 260085116
200 266571599
201 273185537
202 279931440
203 286808606
204 293821634
205 300969808
206 308257816
207 315684930
208 323255927
209 330970065
210 338832214
211 346841616
212 355003234
213 363316296
214 371785858
215 380411134
216 389197273
217 398143475
218 407254984
219 416530986
220 425976820
221 435591656
222 445380932
223 455343802
224 465485801
225 475806069
226 486310238
227 496997434
228 507873388
229 518937210
230 530194732
231 541645048
232 553294091
233 565140939
234 577191628
235 589445220
236 601907852
237 614578572
238 627463620
239 640562028
240 653880141
241 667416973
242 681178976
243 695165148
244 709382046
245 723828652
246 738511630
247 753429946
248 768590371
249 783991855
250 799641278
251 815537572
252 831687728
253 848090660
254 864753470
255 881675056
256 898862629
257 916315071
258 934039706
259 952035398
260 970309584
261 988861110
262 1007697528
263 1026817666
264 1046229191
265 1065930913
266 1085930614
267 1106227088
268 1126828232
269 1147732822
270 1168948874
271 1190475144
272 1212319767
273 1234481481
274 1256968540
275 1279779664
276 1302923226
277 1326397928
278 1350212264
279 1374364918
280 1398864505
281 1423709689
282 1448909210
283 1474461712
284 1500376058
285 1526650874
286 1553295146
287 1580307482
288 1607696993
289 1635462267
290 1663612542
291 1692146386
292 1721073164
293 1750391424
294 1780110660
295 1810229400
296 1840757265
297 1871692765
298 1903045650
299 1934814410
300 1967008926
301 1999627666
302 2032680644
303 2066166308
304 2100094803
305 2134464557
306 2169285848
307 2204557084
308 2240288676
309 2276479012
310 2313138638
311 2350265920
312 2387871541
313 2425953845
314 2464523652
315 2503579286
316 2543131702
317 2583179204
318 2623732886
319 2664791030
320 2706364869
321 2748452663
322 2791065786
323 2834202476
324 2877874248
325 2922079318
326 2966829342
327 3012122516
328 3057970637
329 3104371879
330 3151338184
331 3198867702
332 3246972520
333 3295650766
334 3344914672
335 3394762344
336 3445206159
337 3496244201
338 3547888994
339 3600138600
340 3653005690
341 3706488302
342 3760599258
343 3815336572
344 3870713215
345 3926727179
346 3983391584
347 4040704400
348 4098678898
349 4157313024
350 4216620202
351 4276598354
352 4337261057
353 4398606209
354 4460647542
355 4523382930
356 4586826258
357 4650975378
358 4715844330
359 4781430942
360 4847749411
361 4914797539
362 4982589682
363 5051123618
364 5120413860
365 5190458162
366 5261271196
367 5332850692
368 5405211481
369 5478351269
370 5552285048
371 5627010498
372 5702542774
373 5778879530
374 5856036084
375 5934010066
376 6012816955
377 6092454357
378 6172937916
379 6254265212
380 6336452054
381 6419495996
382 6503413014
383 6588200636
384 6673875005
385 6760433623
386 6847892800
387 6936250014
388 7025521742
389 7115705436
390 7206817744
391 7298856090
392 7391837293
393 7485758751
394 7580637454
395 7676470774
396 7773275872
397 7871050094
398 7969810774
399 8069555232
400 8170300975
401 8272045295
402 8374805876
403 8478579982
404 8583385472
405 8689219584
406 8796100352
407 8904024988
408 9013011703
409 9123057681
410 9234181312
411 9346379752
412 9459671570
413 9574053894
414 9689545474
415 9806143410
416 9923866631
417 10042712211
418 10162699260
419 10283824824
420 10406108196
421 10529546392
422 10654158890
423 10779942678
424 10906917417
425 11035080067
426 11164450474
427 11295025570
428 11426825386
429 11559846826
430 11694110108
431 11829612106
432 11966373227
433 12104390315
434 12243683966
435 12384250996
436 12526112188
437 12669264330
438 12813728396
439 12959501144
440 13106603739
441 13255032909
442 13404810012
443 13555931746
444 13708419662
445 13862270428
446 14017505788
447 14174122382
448 14332142147
449 14491561693
450 14652403154
451 14814663108
452 14978363886
453 15143502036
454 15310100086
455 15478154554
456 15647688165
457 15818697407
458 15991205204
459 16165208014
460 16340728960
461 16517764468
462 16696337864
463 16876445542
464 17058111029
465 17241330689
466 17426128250
467 17612500046
468 17800470008
469 17990034438
470 18181217472
471 18374015380
472 18568452503
473 18764525079
474 18962257656
475 19161646440
476 19362716184
477 19565463064
478 19769912040
479 19976059256
480 20183929881
481 20393520025
482 20604855068
483 20817931088
484 21032773674
485 21249378872
486 21467772482
487 21687950518
488 21909938991
489 22133733883
490 22359361418
491 22586817544
492 22816128700
493 23047290800
494 23280330498
495 23515243676
496 23752057201
497 23990766923
498 24231399926
499 24473952026
500 24718450524
501 24964891202
502 25213301580
503 25463677406
504 25716046419
505 25970404333
506 26226779106
507 26485166420
508 26745594452
509 27008058850
510 27272588014
511 27539177556
512 27807856099
513 28078619221
514 28351495768
515 28626481284
516 28903604838
517 29182861940
518 29464281884
519 29747860146
520 30033626245
521 30321575621
522 30611738022
523 30904108852
524 31198718086
525 31495561094
526 31794668078
527 32096034374
528 32399690413
529 32705631495
530 33013888282
531 33324456038
532 33637365656
533 33952612364
534 34270227288
535 34590205620
536 34912578717
537 35237341737
538 35564526270
539 35894127438
540 36226177066
541 36560670238
542 36897639016
543 37237078448
544 37579020831
545 37923461177
546 38270432020
547 38619928336
548 38971982896
549 39326590640
550 39683784578
551 40043559612
552 40405948993
553 40770947585
554 41138588880
555 41508867706
556 41881817794
557 42257433936
558 42635750106
559 43016761058
560 43400501009
561 43786964675
562 44176186518
563 44568161216
564 44962923476
565 45360467938
566 45760829554
567 46164002928
568 46570023257
569 46978885107
570 47390623924
571 47805234234
572 48222751732
573 48643170906
574 49066527700
575 49492816564
576 49922073691
577 50354293493
578 50789512414
579 51227724828
580 51668967430
581 52113234554
582 52560563150
583 53010947512
584 53464424843
585 53920989399
586 54380678636
587 54843486772
588 55309451518
589 55778567052
590 56250871342
591 56726358526
592 57205066829
593 57686990349
594 58172167570
595 58660592550
596 59152304030
597 59647296030
598 60145607550
599 60647232570
600 61152210351
601 61660534831
602 62172245534
603 62687336358
604 63205847088
605 63727771582
606 64253149888
607 64781975824
608 65314289701
609 65850085297
610 66389403188
611 66932237110
612 67478627906
613 68028569270
614 68582102312
615 69139220686
616 69699965767
617 70264331169
618 70832358536
619 71404041440
620 71979421794
621 72558493128
622 73141297626
623 73727828776
624 74318129033
625 74912191843
626 75510059932
627 76111726706
628 76717235162
629 77326578664
630 77939800484
631 78556893942
632 79177902585
633 79802819691
634 80431689082
635 81064503994
636 81701308524
637 82342095866
638 82986910394
639 83635745260
640 84288645115
641 84945603067
642 85606664048
643 86271821122
644 86941119500
645 87614552204
646 88292164724
647 88973950040
648 89659953923
649 90350169309
650 91044642252
651 91743365644
652 92446385822
653 93153695634
654 93865341702
655 94581316830
656 95301667923
657 96026387743
658 96755523480
659 97489067852
660 98227068336
661 98969517604
662 99716463422
663 100467898418
664 101223870645
665 101984372687
666 102749452886
667 103519103782
668 104293374006
669 105072256054
670 105855798848
671 106643994838
672 107436893239
673 108234486455
674 109036823994
675 109843898216
676 110655758920
677 111472398422
678 112293866816
679 113120156372
680 113951317479
681 114787342361
682 115628281704
683 116474127686
684 117324931290
685 118180684648
686 119041439040
687 119907186554
688 120777978767
689 121653807721
690 122534725294
691 123420723480
692 124311854458
693 125208110176
694 126109543114
695 127016145174
696 127927969137
697 128845006859
698 129767311424
699 130694874642
700 131627749900
701 132565928960
702 133509465516
703 134458351282
704 135412640257
705 136372324109
706 137337457142
707 138308030978
708 139284100228
709 140265656466
710 141252754612
711 142245386192
712 143243606435
713 144247406819
714 145256842884
715 146271906060
716 147292652196
717 148319072676
718 149351223660
719 150389096484
720 151432747621
721 152482168357
722 153537415480
723 154598480228
724 155665419702
725 156738225092
726 157816953814
727 158901597010
728 159992212411
729 161088791111
730 162191391158
731 163300003596
732 164414686792
733 165535431740
734 166662297126
735 167795273896
736 168934421053
737 170079729495
738 171231258546
739 172388999054
740 173553010664
741 174723284174
742 175899879552
743 177082787546
744 178272068447
745 179467712953
746 180669781678
747 181878265272
748 183093224672
749 184314650478
750 185542603954
751 186777075648
752 188018127151
753 189265748961
754 190520002996
755 191780879704
756 193048441330
757 194322678272
758 195603653104
759 196891356174
760 198185850385
761 199487126033
762 200795246354
763 202110201592
764 203432055314
765 204760797714
766 206096492690
767 207439130386
768 208788775033
769 210145416723
770 211509120022
771 212879874970
772 214257746468
773 215642724504
774 217034874316
775 218434185840
776 219840724649
777 221254480629
778 222675519690
779 224103831666
780 225539482806
781 226982462890
782 228432838508
783 229890599388
784 231355812459
785 232828467397
786 234308631472
787 235796294308
788 237291523516
789 238794308668
790 240304717718
791 241822740184
792 243348444365
793 244881819725
794 246422934908
795 247971779326
796 249528421966
797 251092852188
798 252665139326
799 254245272686
800 255833321949
801 257429276367
802 259033205970
803 260645099956
804 262265028704
805 263892981358
806 265529028646
807 267173159660
808 268825445477
809 270485875135
810 272154520064
811 273831369246
812 275516494464
813 277209884646
814 278911611928
815 280621665184
816 282340116903
817 284066955905
818 285802255034
819 287546003056
820 289298273170
821 291059054086
822 292828419362
823 294606357652
824 296392942871
825 298188163619
826 299992094168
827 301804723064
828 303626124938
829 305456288280
830 307295288082
831 309143112778
832 310999837721
833 312865451289
834 314740029198
835 316623559770
836 318516119082
837 320417695402
838 322328365170
839 324248116598
840 326177026491
841 328115083003
842 330062363306
843 332018855498
844 333984637116
845 335959696202
846 337944110660
847 339937868476
848 341941047921
849 343953636925
850 345975714128
851 348007267402
852 350048375758
853 352099027010
854 354159300540
855 356229184106
856 358308757459
857 360398008301
858 362497016756
859 364605770468
860 366724349934
861 368852742740
862 370991029758
863 373139198516
864 375297330261
865 377465412463
866 379643526744
867 381831660518
868 384029895782
869 386238219892
870 388456715224
871 390685369074
872 392924264197
873 395173387831
874 397432823110
875 399702557214
876 401982673656
877 404273159558
878 406574098814
879 408885478488
880 411207382855
881 413539798919
882 415882811340
883 418236407062
884 420600671128
885 422975590424
886 425361250376
887 427757637812
888 430164838543
889 432582839337
890 435011726392
891 437451486416
892 439902205994
893 442363871774
894 444836570730
895 447320289450
896 449815115295
897 452321034795
898 454838135700
899 457366404480
900 459905929276
901 462456696496
902 465018794674
903 467592210158
904 470177031873
905 472773246107
906 475380942178
907 478000106314
908 480630828226
909 483273094082
910 485926993988
911 488592514050
912 491269744771
913 493958672195
914 496659387222
915 499371875836
916 502096229332
917 504832433634
918 507580580436
919 510340655600
920 513112751219
921 515896853093
922 518693053716
923 521501338826
924 524321801318
925 527154426868
926 529999308772
927 532856432646
928 535725892187
929 538607672949
930 541501869034
931 544408465932
932 547327558150
933 550259131116
934 553203279742
935 556159989394
936 559129355389
937 562111363031
938 565106108044
939 568113575670
940 571133862040
941 574166952332
942 577212943088
943 580271819422
944 583343678285
945 586428504729
946 589526396114
947 592637337430
948 595761426448
949 598898648094
950 602049100552
951 605212768684
952 608389751087
953 611580032559
954 614783712112
955 618000774480
956 621231319088
957 624475330608
958 627732908880
959 631004038512
960 634288819761
961 637587237169
962 640899391412
963 644225266968
964 647564964930
965 650918469712
966 654285882826
967 657667188622
968 661062489031
969 664471768339
970 667895128898
971 671332554928
972 674784149204
973 678249895880
974 681729898154
975 685224140116
976 688732725385
977 692255637987
978 695792981966
979 699344741282
980 702911020404
981 706491803226
982 710087194644
983 713697178486
984 717321860075
985 720961223173
986 724615373530
987 728284294844
988 731968093292
989 735666752506
990 739380379094
991 743108956620
992 746852592123
993 750611269101
994 754385095024
995 758174053324
996 761978251902
997 765797674124
998 769632428324
999 773482497802
1000 777347991325