0 1
1 1
2 2
3 5
4 14
5 30
6 72
7 195
8 485
9 1059
10 2065
11 3682
12 6120
13 9620
14 14454
15 20925
16 29367
17 40145
18 53655
19 70324
20 90610
21 115002
22 144020
23 178215
24 218169
25 264495
26 317837
27 378870
28 448300
29 526864
30 615330
31 714497
32 825195
33 948285
34 1084659
35 1235240
36 1400982
37 1582870
38 1781920
39 1999179
40 2235725
41 2492667
42 2771145
43 3072330
44 3397424
45 3747660
46 4124302
47 4528645
48 4962015
49 5425769
50 5921295
51 6450012
52 7013370
53 7612850
54 8249964
55 8926255
56 9643297
57 10402695
58 11206085
59 12055134
60 12951540
61 13897032
62 14893370
63 15942345
64 17045779
65 18205525
66 19423467
67 20701520
68 22041630
69 23445774
70 24915960
71 26454227
72 28062645
73 29743315
74 31498369
75 33329970
76 35240312
77 37231620
78 39306150
79 41466189
80 43714055
81 46052097
82 48482695
83 51008260
84 53631234
85 56354090
86 59179332
87 62109495
88 65147145
89 68294879
90 71555325
91 74931142
92 78425020
93 82039680
94 85777874
95 89642385
96 93636027
97 97761645
98 102022115
99 106420344
100 110959270
101 115641862
102 120471120
103 125450075
104 130581789
105 135869355
106 141315897
107 146924570
108 152698560
109 158641084
110 164755390
111 171044757
112 177512495
113 184161945
114 190996479
115 198019500
116 205234442
117 212644770
118 220253980
119 228065599
120 236083185
121 244310327
122 252750645
123 261407790
124 270285444
125 279387320
126 288717162
127 298278745
128 308075875
129 318112389
130 328392155
131 338919072
132 349697070
133 360730110
134 372022184
135 383577315
136 395399557
137 407492995
138 419861745
139 432509954
140 445441800
141 458661492
142 472173270
143 485981405
144 500090199
145 514503985
146 529227127
147 544264020
148 559619090
149 575296794
150 591301620
151 607638087
152 624310745
153 641324175
154 658682989
155 676391830
156 694455372
157 712878320
158 731665410
159 750821409
160 770351115
161 790259357
162 810550995
163 831230920
164 852304054
165 873775350
166 895649792
167 917932395
168 940628205
169 963742299
170 987279785
171 1011245802
172 1035645520
173 1060484140
174 1085766894
175 1111499045
176 1137685887
177 1164332745
178 1191444975
179 1219027964
180 1247087130
181 1275627922
182 1304655820
183 1334176335
184 1364195009
185 1394717415
186 1425749157
187 1457295870
188 1489363220
189 1521956904
190 1555082650
191 1588746217
192 1622953395
193 1657710005
194 1693021899
195 1728894960
196 1765335102
197 1802348270
198 1839940440
199 1878117619
200 1916885845
201 1956251187
202 1996219745
203 2036797650
204 2077991064
205 2119806180
206 2162249222
207 2205326445
208 2249044135
209 2293408609
210 2338426215
211 2384103332
212 2430446370
213 2477461770
214 2525156004
215 2573535575
216 2622607017
217 2672376895
218 2722851805
219 2774038374
220 2825943260
221 2878573152
222 2931934770
223 2986034865
224 3040880219
225 3096477645
226 3152833987
227 3209956120
228 3267850950
229 3326525414
230 3385986480
231 3446241147
232 3507296445
233 3569159435
234 3631837209
235 3695336890
236 3759665632
237 3824830620
238 3890839070
239 3957698229
240 4025415375
241 4093997817
242 4163452895
243 4233787980
244 4305010474
245 4377127810
246 4450147452
247 4524076895
248 4598923665
249 4674695319
250 4751399445
251 4829043662
252 4907635620
253 4987183000
254 5067693514
255 5149174905
256 5231634947
257 5315081445
258 5399522235
259 5484965184
260 5571418190
261 5658889182
262 5747386120
263 5836916995
264 5927489829
265 6019112675
266 6111793617
267 6205540770
268 6300362280
269 6396266324
270 6493261110
271 6591354877
272 6690555895
273 6790872465
274 6892312919
275 6994885620
276 7098598962
277 7203461370
278 7309481300
279 7416667239
280 7525027705
281 7634571247
282 7745306445
283 7857241910
284 7970386284
285 8084748240
286 8200336482
287 8317159745
288 8435226795
289 8554546429
290 8675127475
291 8796978792
292 8920109270
293 9044527830
294 9170243424
295 9297265035
296 9425601677
297 9555262395
298 9686256265
299 9818592394
300 9952279920
301 10087328012
302 10223745870
303 10361542725
304 10500727839
305 10641310505
306 10783300047
307 10926705820
308 11071537210
309 11217803634
310 11365514540
311 11514679407
312 11665307745
313 11817409095
314 11970993029
315 12126069150
316 12282647092
317 12440736520
318 12600347130
319 12761488649
320 12924170835
321 13088403477
322 13254196395
323 13421559440
324 13590502494
325 13761035470
326 13933168312
327 14106910995
328 14282273525
329 14459265939
330 14637898305
331 14818180722
332 15000123320
333 15183736260
334 15369029734
335 15556013965
336 15744699207
337 15935095745
338 16127213895
339 16321064004
340 16516656450
341 16714001642
342 16913110020
343 17113992055
344 17316658249
345 17521119135
346 17727385277
347 17935467270
348 18145375740
349 18357121344
350 18570714770
351 18786166737
352 19003487995
353 19222689325
354 19443781539
355 19666775480
356 19891682022
357 20118512070
358 20347276560
359 20577986459
360 20810652765
361 21045286507
362 21281898745
363 21520500570
364 21761103104
365 22003717500
366 22248354942
367 22495026645
368 22743743855
369 22994517849
370 23247359935
371 23502281452
372 23759293770
373 24018408290
374 24279636444
375 24542989695
376 24808479537
377 25076117495
378 25345915125
379 25617884014
380 25892035780
381 26168382072
382 26446934570
383 26727704985
384 27010705059
385 27295946565
386 27583441307
387 27873201120
388 28165237870
389 28459563454
390 28756189800
391 29055128867
392 29356392645
393 29659993155
394 29965942449
395 30274252610
396 30584935752
397 30898004020
398 31213469590
399 31531344669
400 31851641495
401 32174372337
402 32499549495
403 32827185300
404 33157292114
405 33489882330
406 33824968372
407 34162562695
408 34502677785
409 34845326159
410 35190520365
411 35538272982
412 35888596620
413 36241503920
414 36597007554
415 36955120225
416 37315854667
417 37679223645
418 38045239955
419 38413916424
420 38785265910
421 39159301302
422 39536035520
423 39915481515
424 40297652269
425 40682560795
426 41070220137
427 41460643370
428 41853843600
429 42249833964
430 42648627630
431 43050237797
432 43454677695
433 43861960585
434 44272099759
435 44685108540
436 45101000282
437 45519788370
438 45941486220
439 46366107279
440 46793665025
441 47224172967
442 47657644645
443 48094093630
444 48533533524
445 48975977960
446 49421440602
447 49869935145
448 50321475315
449 50776074869
450 51233747595
451 51694507312
452 52158367870
453 52625343150
454 53095447064
455 53568693555
456 54045096597
457 54524670195
458 55007428385
459 55493385234
460 55982554840
461 56474951332
462 56970588870
463 57469481645
464 57971643879
465 58477089825
466 58985833767
467 59497890020
468 60013272930
469 60531996874
470 61054076260
471 61579525527
472 62108359145
473 62640591615
474 63176237469
475 63715311270
476 64257827612
477 64803801120
478 65353246450
479 65906178289
480 66462611355
481 67022560397
482 67586040195
483 68153065560
484 68723651334
485 69297812390
486 69875563632
487 70456919995
488 71041896445
489 71630507979
490 72222769625
491 72818696442
492 73418303520
493 74021605980
494 74628618974
495 75239357685
496 75853837327
497 76472073145
498 77094080415
499 77719874444
500 78349470570
501 78982884162
502 79620130620
503 80261225375
504 80906183889
505 81555021655
506 82207754197
507 82864397070
508 83524965860
509 84189476184
510 84857943690
511 85530384057
512 86206812995
513 86887246245
514 87571699579
515 88260188800
516 88952729742
517 89649338270
518 90350030280
519 91054821699
520 91763728485
521 92476766627
522 93193952145
523 93915301090
524 94640829544
525 95370553620
526 96104489462
527 96842653245
528 97585061175
529 98331729489
530 99082674455
531 99837912372
532 100597459570
533 101361332410
534 102129547284
535 102902120615
536 103679068857
537 104460408495
538 105246156045
539 106036328054
540 106830941100
541 107630011792
542 108433556770
543 109241592705
544 110054136299
545 110871204285
546 111692813427
547 112518980520
548 113349722390
549 114185055894
550 115024997920
551 115869565387
552 116718775245
553 117572644475
554 118431190089
555 119294429130
556 120162378672
557 121035055820
558 121912477710
559 122794661509
560 123681624415
561 124573383657
562 125469956495
563 126371360220
564 127277612154
565 128188729650
566 129104730092
567 130025630895
568 130951449505
569 131882203399
570 132817910085
571 133758587102
572 134704252020
573 135654922440
574 136610615994
575 137571350345
576 138537143187
577 139508012245
578 140483975275
579 141465050064
580 142451254430
581 143442606222
582 144439123320
583 145440823635
584 146447725109
585 147459845715
586 148477203457
587 149499816370
588 150527702520
589 151560880004
590 152599366950
591 153643181517
592 154692341895
593 155746866305
594 156806772999
595 157872080260
596 158942806402
597 160018969770
598 161100588740
599 162187681719
600 163280267145
601 164378363487
602 165481989245
603 166591162950
604 167705903164
605 168826228480
606 169952157522
607 171083708945
608 172220901435
609 173363753709
610 174512284515
611 175666512632
612 176826456870
613 177992136070
614 179163569104
615 180340774875
616 181523772317
617 182712580395
618 183907218105
619 185107704474
620 186314058560
621 187526299452
622 188744446270
623 189968518165
624 191198534319
625 192434513945
626 193676476287
627 194924440620
628 196178426250
629 197438452514
630 198704538780
631 199976704447
632 201254968945
633 202539351735
634 203829872309
635 205126550190
636 206429404932
637 207738456120
638 209053723370
639 210375226329
640 211702984675
641 213037018117
642 214377346395
643 215723989280
644 217076966574
645 218436298110
646 219802003752
647 221174103395
648 222552616965
649 223937564419
650 225328965745
651 226726840962
652 228131210120
653 229542093300
654 230959510614
655 232383482205
656 233814028247
657 235251168945
658 236694924535
659 238145315284
660 239602361490
661 241066083482
662 242536501620
663 244013636295
664 245497507929
665 246988136975
666 248485543917
667 249989749270
668 251500773580
669 253018637424
670 254543361410
671 256074966177
672 257613472395
673 259158900765
674 260711272019
675 262270606920
676 263836926262
677 265410250870
678 266990601600
679 268577999339
680 270172465005
681 271774019547
682 273382683945
683 274998479210
684 276621426384
685 278251546540
686 279888860782
687 281533390245
688 283185156095
689 284844179529
690 286510481775
691 288184084092
692 289865007770
693 291553274130
694 293248904524
695 294951920335
696 296662342977
697 298380193895
698 300105494565
699 301838266494
700 303578531220
701 305326310312
702 307081625370
703 308844498025
704 310614949939
705 312393002805
706 314178678347
707 315971998320
708 317772984510
709 319581658734
710 321398042840
711 323222158707
712 325054028245
713 326893673395
714 328741116129
715 330596378450
716 332459482392
717 334330450020
718 336209303430
719 338096064749
720 339990756135
721 341893399777
722 343804017895
723 345722632740
724 347649266594
725 349583941770
726 351526680612
727 353477505495
728 355436438825
729 357403503039
730 359378720605
731 361362114022
732 363353705820
733 365353518560
734 367361574834
735 369377897265
736 371402508507
737 373435431245
738 375476688195
739 377526302104
740 379584295750
741 381650691942
742 383725513520
743 385808783355
744 387900524349
745 390000759435
746 392109511577
747 394226803770
748 396352659040
749 398487100444
750 400630151070
751 402781834037
752 404942172495
753 407111189625
754 409288908639
755 411475352780
756 413670545322
757 415874509570
758 418087268860
759 420308846559
760 422539266065
761 424778550807
762 427026724245
763 429283809870
764 431549831204
765 433824811800
766 436108775242
767 438401745145
768 440703745155
769 443014798949
770 445334930235
771 447664162752
772 450002520270
773 452350026590
774 454706705544
775 457072580995
776 459447676837
777 461832016995
778 464225625425
779 466628526114
780 469040743080
781 471462300372
782 473893222070
783 476333532285
784 478783255159
785 481242414865
786 483711035607
787 486189141620
788 488676757170
789 491173906554
790 493680614100
791 496196904167
792 498722801145
793 501258329455
794 503803513549
795 506358377910
796 508922947052
797 511497245520
798 514081297890
799 516675128769
800 519278762795
801 521892224637
802 524515538995
803 527148730600
804 529791824214
805 532444844630
806 535107816672
807 537780765195
808 540463715085
809 543156691259
810 545859718665
811 548572822282
812 551296027120
813 554029358220
814 556772840654
815 559526499525
816 562290359967
817 565064447145
818 567848786255
819 570643402524
820 573448321210
821 576263567602
822 579089167020
823 581925144815
824 584771526369
825 587628337095
826 590495602437
827 593373347870
828 596261598900
829 599160381064
830 602069719930
831 604989641097
832 607920170195
833 610861332885
834 613813154859
835 616775661840
836 619748879582
837 622732833870
838 625727550520
839 628733055379
840 631749374325
841 634776533267
842 637814558145
843 640863474930
844 643923309624
845 646994088260
846 650075836902
847 653168581645
848 656272348615
849 659387163969
850 662513053895
851 665650044612
852 668798162370
853 671957433450
854 675127884164
855 678309540855
856 681502429897
857 684706577695
858 687922010685
859 691148755334
860 694386838140
861 697636285632
862 700897124370
863 704169380945
864 707453081979
865 710748254125
866 714054924067
867 717373118520
868 720702864230
869 724044187974
870 727397116560
871 730761676827
872 734137895645
873 737525799915
874 740925416569
875 744336772570
876 747759894912
877 751194810620
878 754641546750
879 758100130389
880 761570588655
881 765052948697
882 768547237695
883 772053482860
884 775571711434
885 779101950690
886 782644227932
887 786198570495
888 789765005745
889 793343561079
890 796934263925
891 800537141742
892 804152222020
893 807779532280
894 811419100074
895 815070952985
896 818735118627
897 822411624645
898 826100498715
899 829801768544
900 833515461870
901 837241606462
902 840980230120
903 844731360675
904 848495025989
905 852271253955
906 856060072497
907 859861509570
908 863675593160
909 867502351284
910 871341811990
911 875194003357
912 879058953495
913 882936690545
914 886827242679
915 890730638100
916 894646905042
917 898576071770
918 902518166580
919 906473217799
920 910441253785
921 914422302927
922 918416393645
923 922423554390
924 926443813644
925 930477199920
926 934523741762
927 938583467745
928 942656406475
929 946742586589
930 950842036755
931 954954785672
932 959080862070
933 963220294710
934 967373112384
935 971539343915
936 975719018157
937 979912163995
938 984118810345
939 988338986154
940 992572720400
941 996820042092
942 1001080980270
943 1005355564005
944 1009643822399
945 1013945784585
946 1018261479727
947 1022590937020
948 1026934185690
949 1031291254994
950 1035662174220
951 1040046972687
952 1044445679745
953 1048858324775
954 1053284937189
955 1057725546430
956 1062180181972
957 1066648873320
958 1071131650010
959 1075628541609
960 1080139577715
961 1084664787957
962 1089204201995
963 1093757849520
964 1098325760254
965 1102907963950
966 1107504490392
967 1112115369395
968 1116740630805
969 1121380304499
970 1126034420385
971 1130703008402
972 1135386098520
973 1140083720740
974 1144795905094
975 1149522681645
976 1154264080487
977 1159020131745
978 1163790865575
979 1168576312164
980 1173376501730
981 1178191464522
982 1183021230820
983 1187865830935
984 1192725295209
985 1197599654015
986 1202488937757
987 1207393176870
988 1212312401820
989 1217246643104
990 1222195931250
991 1227160296817
992 1232139770395
993 1237134382605
994 1242144164099
995 1247169145560
996 1252209357702
997 1257264831270
998 1262335597040
999 1267421685819
1000 1272523128445