1 1
2 3
3 28
4 85
5 151
6 302
7 864
8 3197
9 4780
10 5438
11 5815
12 6413
13 7769
14 7985
15 11062
16 16672
17 24805
18 27379
19 35435
20 41718
21 45047
22 58383
23 69835
24 70235
25 76305
26 91178
27 95963
28 97763
29 103173
30 111375
31 118498
32 138405
33 158200
34 170333
35 184132
36 191707
37 201693
38 254666
39 296977
40 332866
41 346216
42 360305
43 376632
44 395601
45 421816
46 470195
47 475108
48 515167
49 543903
50 628710
51 674234
52 726489
53 728426
54 817945
55 835160
56 909482
57 970177
58 1024865
59 1100641
60 1132655
61 1236631
62 1338936
63 1377535
64 1385142
65 1435174
66 1453716
67 1463303
68 1511103
69 1520477
70 1809301
71 1851232
72 1884199
73 1894253
74 1895096
75 1960007
76 2075903
77 2078224
78 2110493
79 2133886
80 2203634
81 2288987
82 2475496
83 2511182
84 2907689
85 2921800
86 2922859
87 2989956
88 3015293
89 3283750
90 3285896
91 3489808
92 3583033
93 3616032
94 3655836
95 3672234
96 3895740
97 3925093
98 4036849
99 4113803
100 4233955
101 4345861
102 4813108
103 4827029
104 4862641
105 4935115
106 5239310
107 5259609
108 5330389
109 5401108
110 5590591
111 6216873
112 6311307
113 6319300
114 6356723
115 6357421
116 6391527
117 7078480
118 7128401
119 7495879
120 7535227
121 7803701
122 7806038
123 8005155
124 8043178
125 8466115
126 8508610
127 8584866
128 8792926
129 8936385
130 8957910
131 9051423
132 9274862
133 9294378
134 9315760
135 9371841
136 9445966
137 9709740
138 9987676
139 10114236
140 10424186
141 10526914
142 10818297
143 10996131
144 11265424
145 11867963
146 11984729
147 12060665
148 12139493
149 12199615
150 12507632
151 12626553
152 12683402
153 13200154
154 13318182
155 13438036
156 13547891
157 13551101
158 13820895
159 13907359
160 13966580
161 14112773
162 14260860
163 14261351
164 14355492
165 14363848
166 14845224
167 14845959
168 15007025
169 15122155
170 15527702
171 15660720
172 15951327
173 16099144
174 16354790
175 18119178
176 18425564
177 18570348
178 18714153
179 18847106
180 19085427
181 19094837
182 19219460
183 20035349
184 20143680
185 20214286
186 20332626
187 20409399
188 20556740
189 21493418
190 21536021
191 21792867
192 22175041
193 22330192
194 22554937
195 22583297
196 22903648
197 22975711
198 23275432
199 23356757
200 23480161
201 23988005
202 24028234
203 24721251
204 24970351
205 25281442
206 26092923
207 26263790
208 26349152
209 26356282
210 26891856
211 27478457
212 27603196
213 28065966
214 28365645
215 29264311
216 29302024
217 29335836
218 29385191
219 30224876
220 30315104
221 30486937
222 31586269
223 31695614
224 31823884
225 32630797
226 32730085
227 32735910
228 33180687
229 33462027
230 33706424
231 33735875
232 34063891
233 36939641
234 37086557
235 37517141
236 37655512
237 38047552
238 38414133
239 38843157
240 39060952
241 39310084
242 40409972
243 40933761
244 41035089
245 41133210
246 41138804
247 41344161
248 41442611
249 41846862
250 41859275
251 44254964
252 45007214
253 45009813
254 45019988
255 45163021
256 45814949
257 46097017
258 46295600
259 46860874
260 46861828
261 47018614
262 47286205
263 47445352
264 47615686
265 47632922
266 47842054
267 48006067
268 48628946
269 48743923
270 48888474
271 49067894
272 49169556
273 50091653
274 50718570
275 51579127
276 51670399
277 52016962
278 52192364
279 52360192
280 52965196
281 53007138
282 53190586
283 53244160
284 53290164
285 53292869
286 53761429
287 53778789
288 55318463
289 55664032
290 55977284
291 56265107
292 57405658
293 57467038
294 57528341
295 57827119
296 58093094
297 58619403
298 59915788
299 60360370
300 60411329
301 60552042
302 60979991
303 60987124
304 61103978
305 61798616
306 61905793
307 61997083
308 63449976
309 64714450
310 64992686
311 65183893
312 65617802
313 65769551
314 66019010
315 66150268
316 66226045
317 66521521
318 66656093
319 66860350
320 67205900
321 67782588
322 67787516
323 67992024
324 68254027
325 68850456
326 68890385
327 68978165
328 69097438
329 69432682
330 69903089
331 69976199
332 70188583
333 72322820
334 73768043
335 74664253
336 75494131
337 75844382
338 75929670
339 75973464
340 76184192
341 76319600
342 76609428
343 76695983
344 78724225
345 79305337
346 79502618
347 79588479
348 79781828
349 80501290
350 80875827
351 81962958
352 82035532
353 82742660
354 83210871
355 83417156
356 84284987
357 84720703
358 84968121
359 85609956
360 85620335
361 86286777
362 86653031
363 87264383
364 87850024
365 87936375
366 89139661
367 90207863
368 91197611
369 91886984
370 92019844
371 92274033
372 92730367
373 93726330
374 93816818
375 94792264
376 96286778
377 96514500
378 96850845
379 98747533
380 98886900
381 99704720
382 100663562
383 100899992
384 100907421
385 101063960
386 101789191
387 102047230
388 104290519
389 104534669
390 105050307
391 105597855
392 106023281
393 106607696
394 107012665
395 107785672
396 107830785
397 107995332
398 108526658
399 109281961
400 109760233
401 110858320
402 111435375
403 111806742
404 112878500
405 113756876
406 113811547
407 115451208
408 117272098
409 118315688
410 118817166
411 120478550
412 122431832
413 122947697
414 124118854
415 124127074
416 124213972
417 125116035
418 125369074
419 125654679
420 125895425
421 126275504
422 127072286
423 127512263
424 128079575
425 130873971
426 130904735
427 131273489
428 131742155
429 132078552
430 135334136
431 135398439
432 135519880
433 135787431
434 135993827
435 137077808
436 137378026
437 137388013
438 137667081
439 138327638
440 138604850
441 138785095
442 140306727
443 141463052
444 142129831
445 142285173
446 142417344
447 143075355
448 144403113
449 148548353
450 150120372
451 150407649
452 150815988
453 151896075
454 152903416
455 154078935
456 154597666
457 154882927
458 155387977
459 155574512
460 155595004
461 155953588
462 156171019
463 156861621
464 160522389
465 161021042
466 164045259
467 164163534
468 167479372
469 170487048
470 171507945
471 172031501
472 172470352
473 172793779
474 173294640
475 173525107
476 173537483
477 174395380
478 175196252
479 176188922
480 176369734
481 176398696
482 177031484
483 178722497
484 179360409
485 181067760
486 181724374
487 181957281
488 182065820
489 182387246
490 182584108
491 182682282
492 182711747
493 183985033
494 184215365
495 186490913
496 187066745
497 187472318
498 187633318
499 189680610
500 190223020
501 190909151
502 191139619
503 192003872
504 193242803
505 193583530
506 194435559
507 195368489
508 196817392
509 196929651
510 197799132
511 199184258
512 199271448
513 199867218
514 202331219
515 204850661
516 205887074
517 207016663
518 209577080
519 211095736
520 212390931
521 215434385
522 215522884
523 215621850
524 216810078
525 218352097
526 218928694
527 219567321
528 219633487
529 220271462
530 220622385
531 222037109
532 224655117
533 225134847
534 226465008
535 228857105
536 230800510
537 233280595
538 234752816
539 234870873
540 235200242
541 235741133
542 239895041
543 240289025
544 241005183
545 245781369
546 246000584
547 246903216
548 246993606
549 247508936
550 247874651
551 248300138
552 250047514
553 250696602
554 251709801
555 251933177
556 252947016
557 253360534
558 255671365
559 257941201
560 260170520
561 260384673
562 260561755
563 260923412
564 262330455
565 262996562
566 266368913
567 266741056
568 266764212
569 267520045
570 267954531
571 268060709
572 272795257
573 273463160
574 273720736
575 276284990
576 277333225
577 277562469
578 281320144
579 281327445
580 283918972
581 284137663
582 284184348
583 285096180
584 285885331
585 286037501
586 288649480
587 290407254
588 290424014
589 290650396
590 291793561
591 292601681
592 294503443
593 295901896
594 296306392
595 297000638
596 297419111
597 299015230
598 300706232
599 301931027
600 304166661
601 305457224
602 305860816
603 305999082
604 306177602
605 306586358
606 308673697
607 309106665
608 309780610
609 311741923
610 311905679
611 312904928
612 313896942
613 314195284
614 314461272
615 314470991
616 314919002
617 316858761
618 317889848
619 319447355
620 320269938
621 321620884
622 323743109
623 324581036
624 324882126
625 325594636
626 325880498
627 325904036
628 326026429
629 328114712
630 329978997
631 332595158
632 332893527
633 333143751
634 335537293
635 335790330
636 336685156
637 337095283
638 339019607
639 344047883
640 345110639
641 349754954
642 350315461
643 350954746
644 351400826
645 352708824
646 357576409
647 360905482
648 363034519
649 363813275
650 366826495
651 368646733
652 368827239
653 369324949
654 370184764
655 371107978
656 371146104
657 371477625
658 371573210
659 373909014
660 375807455
661 377509928
662 377669591
663 378406891
664 379183445
665 380262061
666 389370485
667 391005989
668 393815572
669 394903783
670 397764671
671 402276805
672 406824909
673 407719659
674 412271994
675 413793251
676 414228187
677 417160146
678 417533782
679 417639003
680 418999526
681 419978662
682 420495745
683 421445854
684 424386202
685 425529884
686 425849164
687 425889547
688 427697358
689 429849701
690 430390800
691 430844411
692 431722265
693 432832000
694 433546404
695 435313367
696 435868337
697 436174188
698 436655672
699 436987023
700 439557400
701 442395456
702 442595484
703 447940097
704 451825932
705 453768888
706 454445478
707 454914279
708 455464302
709 455593826
710 456958615
711 457447780
712 459547908
713 461791672
714 461796287
715 464746004
716 465245583
717 467337435
718 468535371
719 469721006
720 475417007
721 475939889
722 476866000
723 476993467
724 478077988
725 481052114
726 482114017
727 482501696
728 487396573
729 488291535
730 488825559
731 489144571
732 489895865
733 490392116
734 490442135
735 491273596
736 498035572
737 498908732
738 501843504
739 502914781
740 504514090
741 506858414
742 508108944
743 508135095
744 510076236
745 510774209
746 510995311
747 510997529
748 511362064
749 513121497
750 513131015
751 517858920
752 518408879
753 521869829
754 524608248
755 526062099
756 526618652
757 527727175
758 529959095
759 532132643
760 532142216
761 532515756
762 532906092
763 533253520
764 535109370
765 537543597
766 540661919
767 541301399
768 544012049
769 545321690
770 545728053
771 545924171
772 547776062
773 552698517
774 553005967
775 554186194
776 557930290
777 562702436
778 566121423
779 567392970
780 568754245
781 572589802
782 576647352
783 579676725
784 579854217
785 580644909
786 581233534
787 581398598
788 584381084
789 584515350
790 584541666
791 586072682
792 586682329
793 587400323
794 587837070
795 588254603
796 590334729
797 592453918
798 592648409
799 593887818
800 595625804
801 596400406
802 599472061
803 599875659
804 601064462
805 601430491
806 603464293
807 604044638
808 604437208
809 605999487
810 607368585
811 609315385
812 610916432
813 610946072
814 611479646
815 611744703
816 612273520
817 612488760
818 613870621
819 615074234
820 617465930
821 622233755
822 622679131
823 623691050
824 623698773
825 624449296
826 625206576
827 625262391
828 629695632
829 631496803
830 631861828
831 643768161
832 645632933
833 648450324
834 649710665
835 656859080
836 657436422
837 659499445
838 659757466
839 661334898
840 661373420
841 662578278
842 664070673
843 664086742
844 664299052
845 664455833
846 667309253
847 672887678
848 677555803
849 680216125
850 685187407
851 691714564
852 694272015
853 695350143
854 696604808
855 697062923
856 699096816
857 699930572
858 702955727
859 705027247
860 705231611
861 705482566
862 708261578
863 708658756
864 709910183
865 710550233
866 711240961
867 711442030
868 713114655
869 714242392
870 717840878
871 718690259
872 725400633
873 725550983
874 728408471
875 731855735
876 733830650
877 734516166
878 734850419
879 736197132
880 742503096
881 742752690
882 743361909
883 745149654
884 755416208
885 755607099
886 756561538
887 759436841
888 761403139
889 766275574
890 772005152
891 773363149
892 774711724
893 775312539
894 777783536
895 780648388
896 781549253
897 783171303
898 783803438
899 784723111
900 785157266
901 785840286
902 789863801
903 790067136
904 795490239
905 795534922
906 796418682
907 796655938
908 797360561
909 801356496
910 802965635
911 804074109
912 805485333
913 808026912
914 810082520
915 811840179
916 812557947
917 814850963
918 816831201
919 817046355
920 817373695
921 818964845
922 820776322
923 823515376
924 825379415
925 827480569
926 827841931
927 830652634
928 834123653
929 834150224
930 840076325
931 841093378
932 846598081
933 846895128
934 848759727
935 849221337
936 849936738
937 850095309
938 857577566
939 857803252
940 858985745
941 872430866
942 875280560
943 879114185
944 880727467
945 884294608
946 885901455
947 886936450
948 890539124
949 892609978
950 893884453
951 899369864
952 903895334
953 904862233
954 911168213
955 912391927
956 914515772
957 921303377
958 922083216
959 923786151
960 924243271
961 927833045
962 929874119
963 932759838
964 934423473
965 934464748
966 936145059
967 936172732
968 936677518
969 938166196
970 939360520
971 941265896
972 942246982
973 942356953
974 944002830
975 945224167
976 946490507
977 947181087
978 947256914
979 954621626
980 956047906
981 957780812
982 957833996
983 960529574
984 960834028
985 963339473
986 964302613
987 965328390
988 966484987
989 971724887
990 975030198
991 978263241
992 984255329
993 984728718
994 985745222
995 986259818
996 986833093
997 989733559
998 989777979
999 989784275
1000 996345017