1 1
2 2
3 8
4 25
5 65
6 146
7 292
8 533
9 905
10 1450
11 2216
12 3257
13 4633
14 6410
15 8660
16 11461
17 14897
18 19058
19 24040
20 29945
21 36881
22 44962
23 54308
24 65045
25 77305
26 91226
27 106952
28 124633
29 144425
30 166490
31 190996
32 218117
33 248033
34 280930
35 317000
36 356441
37 399457
38 446258
39 497060
40 552085
41 611561
42 675722
43 744808
44 819065
45 898745
46 984106
47 1075412
48 1172933
49 1276945
50 1387730
51 1505576
52 1630777
53 1763633
54 1904450
55 2053540
56 2211221
57 2377817
58 2553658
59 2739080
60 2934425
61 3140041
62 3356282
63 3583508
64 3822085
65 4072385
66 4334786
67 4609672
68 4897433
69 5198465
70 5513170
71 5841956
72 6185237
73 6543433
74 6916970
75 7306280
76 7711801
77 8133977
78 8573258
79 9030100
80 9504965
81 9998321
82 10510642
83 11042408
84 11594105
85 12166225
86 12759266
87 13373732
88 14010133
89 14668985
90 15350810
91 16056136
92 16785497
93 17539433
94 18318490
95 19123220
96 19954181
97 20811937
98 21697058
99 22610120
100 23551705
101 24522401
102 25522802
103 26553508
104 27615125
105 28708265
106 29833546
107 30991592
108 32183033
109 33408505
110 34668650
111 35964116
112 37295557
113 38663633
114 40069010
115 41512360
116 42994361
117 44515697
118 46077058
119 47679140
120 49322645
121 51008281
122 52736762
123 54508808
124 56325145
125 58186505
126 60093626
127 62047252
128 64048133
129 66097025
130 68194690
131 70341896
132 72539417
133 74788033
134 77088530
135 79441700
136 81848341
137 84309257
138 86825258
139 89397160
140 92025785
141 94711961
142 97456522
143 100260308
144 103124165
145 106048945
146 109035506
147 112084712
148 115197433
149 118374545
150 121616930
151 124925476
152 128301077
153 131744633
154 135257050
155 138839240
156 142492121
157 146216617
158 150013658
159 153884180
160 157829125
161 161849441
162 165946082
163 170120008
164 174372185
165 178703585
166 183115186
167 187607972
168 192182933
169 196841065
170 201583370
171 206410856
172 211324537
173 216325433
174 221414570
175 226592980
176 231861701
177 237221777
178 242674258
179 248220200
180 253860665
181 259596721
182 265429442
183 271359908
184 277389205
185 283518425
186 289748666
187 296081032
188 302516633
189 309056585
190 315702010
191 322454036
192 329313797
193 336282433
194 343361090
195 350550920
196 357853081
197 365268737
198 372799058
199 380445220
200 388208405
201 396089801
202 404090602
203 412212008
204 420455225
205 428821465
206 437311946
207 445927892
208 454670533
209 463541105
210 472540850
211 481671016
212 490932857
213 500327633
214 509856610
215 519521060
216 529322261
217 539261497
218 549340058
219 559559240
220 569920345
221 580424681
222 591073562
223 601868308
224 612810245
225 623900705
226 635141026
227 646532552
228 658076633
229 669774625
230 681627890
231 693637796
232 705805717
233 718133033
234 730621130
235 743271400
236 756085241
237 769064057
238 782209258
239 795522260
240 809004485
241 822657361
242 836482322
243 850480808
244 864654265
245 879004145
246 893531906
247 908239012
248 923126933
249 938197145
250 953451130
251 968890376
252 984516377
253 1000330633
254 1016334650
255 1032529940
256 1048918021
257 1065500417
258 1082278658
259 1099254280
260 1116428825
261 1133803841
262 1151380882
263 1169161508
264 1187147285
265 1205339785
266 1223740586
267 1242351272
268 1261173433
269 1280208665
270 1299458570
271 1318924756
272 1338608837
273 1358512433
274 1378637170
275 1398984680
276 1419556601
277 1440354577
278 1461380258
279 1482635300
280 1504121365
281 1525840121
282 1547793242
283 1569982408
284 1592409305
285 1615075625
286 1637983066
287 1661133332
288 1684528133
289 1708169185
290 1732058210
291 1756196936
292 1780587097
293 1805230433
294 1830128690
295 1855283620
296 1880696981
297 1906370537
298 1932306058
299 1958505320
300 1984970105
301 2011702201
302 2038703402
303 2065975508
304 2093520325
305 2121339665
306 2149435346
307 2177809192
308 2206463033
309 2235398705
310 2264618050
311 2294122916
312 2323915157
313 2353996633
314 2384369210
315 2415034760
316 2445995161
317 2477252297
318 2508808058
319 2540664340
320 2572823045
321 2605286081
322 2638055362
323 2671132808
324 2704520345
325 2738219905
326 2772233426
327 2806562852
328 2841210133
329 2876177225
330 2911466090
331 2947078696
332 2983017017
333 3019283033
334 3055878730
335 3092806100
336 3130067141
337 3167663857
338 3205598258
339 3243872360
340 3282488185
341 3321447761
342 3360753122
343 3400406308
344 3440409365
345 3480764345
346 3521473306
347 3562538312
348 3603961433
349 3645744745
350 3687890330
351 3730400276
352 3773276677
353 3816521633
354 3860137250
355 3904125640
356 3948488921
357 3993229217
358 4038348658
359 4083849380
360 4129733525
361 4176003241
362 4222660682
363 4269708008
364 4317147385
365 4364980985
366 4413210986
367 4461839572
368 4510868933
369 4560301265
370 4610138770
371 4660383656
372 4711038137
373 4762104433
374 4813584770
375 4865481380
376 4917796501
377 4970532377
378 5023691258
379 5077275400
380 5131287065
381 5185728521
382 5240602042
383 5295909908
384 5351654405
385 5407837825
386 5464462466
387 5521530632
388 5579044633
389 5637006785
390 5695419410
391 5754284836
392 5813605397
393 5873383433
394 5933621290
395 5994321320
396 6055485881
397 6117117337
398 6179218058
399 6241790420
400 6304836805
401 6368359601
402 6432361202
403 6496844008
404 6561810425
405 6627262865
406 6693203746
407 6759635492
408 6826560533
409 6893981305
410 6961900250
411 7030319816
412 7099242457
413 7168670633
414 7238606810
415 7309053460
416 7380013061
417 7451488097
418 7523481058
419 7595994440
420 7669030745
421 7742592481
422 7816682162
423 7891302308
424 7966455445
425 8042144105
426 8118370826
427 8195138152
428 8272448633
429 8350304825
430 8428709290
431 8507664596
432 8587173317
433 8667238033
434 8747861330
435 8829045800
436 8910794041
437 8993108657
438 9075992258
439 9159447460
440 9243476885
441 9328083161
442 9413268922
443 9499036808
444 9585389465
445 9672329545
446 9759859706
447 9847982612
448 9936700933
449 10026017345
450 10115934530
451 10206455176
452 10297581977
453 10389317633
454 10481664850
455 10574626340
456 10668204821
457 10762403017
458 10857223658
459 10952669480
460 11048743225
461 11145447641
462 11242785482
463 11340759508
464 11439372485
465 11538627185
466 11638526386
467 11739072872
468 11840269433
469 11942118865
470 12044623970
471 12147787556
472 12251612437
473 12356101433
474 12461257370
475 12567083080
476 12673581401
477 12780755177
478 12888607258
479 12997140500
480 13106357765
481 13216261921
482 13326855842
483 13438142408
484 13550124505
485 13662805025
486 13776186866
487 13890272932
488 14005066133
489 14120569385
490 14236785610
491 14353717736
492 14471368697
493 14589741433
494 14708838890
495 14828664020
496 14949219781
497 15070509137
498 15192535058
499 15315300520
500 15438808505
501 15563062001
502 15688064002
503 15813817508
504 15940325525
505 16067591065
506 16195617146
507 16324406792
508 16453963033
509 16584288905
510 16715387450
511 16847261716
512 16979914757
513 17113349633
514 17247569410
515 17382577160
516 17518375961
517 17654968897
518 17792359058
519 17930549540
520 18069543445
521 18209343881
522 18349953962
523 18491376808
524 18633615545
525 18776673305
526 18920553226
527 19065258452
528 19210792133
529 19357157425
530 19504357490
531 19652395496
532 19801274617
533 19950998033
534 20101568930
535 20252990500
536 20405265941
537 20558398457
538 20712391258
539 20867247560
540 21022970585
541 21179563561
542 21337029722
543 21495372308
544 21654594565
545 21814699745
546 21975691106
547 22137571912
548 22300345433
549 22464014945
550 22628583730
551 22794055076
552 22960432277
553 23127718633
554 23295917450
555 23465032040
556 23635065721
557 23806021817
558 23977903658
559 24150714580
560 24324457925
561 24499137041
562 24674755282
563 24851316008
564 25028822585
565 25207278385
566 25386686786
567 25567051172
568 25748374933
569 25930661465
570 26113914170
571 26298136456
572 26483331737
573 26669503433
574 26856654970
575 27044789780
576 27233911301
577 27424022977
578 27615128258
579 27807230600
580 28000333465
581 28194440321
582 28389554642
583 28585679908
584 28782819605
585 28980977225
586 29180156266
587 29380360232
588 29581592633
589 29783856985
590 29987156810
591 30191495636
592 30396876997
593 30603304433
594 30810781490
595 31019311720
596 31228898681
597 31439545937
598 31651257058
599 31864035620
600 32077885205
601 32292809401
602 32508811802
603 32725896008
604 32944065625
605 33163324265
606 33383675546
607 33605123092
608 33827670533
609 34051321505
610 34276079650
611 34501948616
612 34728932057
613 34957033633
614 35186257010
615 35416605860
616 35648083861
617 35880694697
618 36114442058
619 36349329640
620 36585361145
621 36822540281
622 37060870762
623 37300356308
624 37541000645
625 37782807505
626 38025780626
627 38269923752
628 38515240633
629 38761735025
630 39009410690
631 39258271396
632 39508320917
633 39759563033
634 40012001530
635 40265640200
636 40520482841
637 40776533257
638 41033795258
639 41292272660
640 41551969285
641 41812888961
642 42075035522
643 42338412808
644 42603024665
645 42868874945
646 43135967506
647 43404306212
648 43673894933
649 43944737545
650 44216837930
651 44490199976
652 44764827577
653 45040724633
654 45317895050
655 45596342740
656 45876071621
657 46157085617
658 46439388658
659 46722984680
660 47007877625
661 47294071441
662 47581570082
663 47870377508
664 48160497685
665 48451934585
666 48744692186
667 49038774472
668 49334185433
669 49630929065
670 49929009370
671 50228430356
672 50529196037
673 50831310433
674 51134777570
675 51439601480
676 51745786201
677 52053335777
678 52362254258
679 52672545700
680 52984214165
681 53297263721
682 53611698442
683 53927522408
684 54244739705
685 54563354425
686 54883370666
687 55204792532
688 55527624133
689 55851869585
690 56177533010
691 56504618536
692 56833130297
693 57163072433
694 57494449090
695 57827264420
696 58161522581
697 58497227737
698 58834384058
699 59172995720
700 59513066905
701 59854601801
702 60197604602
703 60542079508
704 60888030725
705 61235462465
706 61584378946
707 61934784392
708 62286683033
709 62640079105
710 62994976850
711 63351380516
712 63709294357
713 64068722633
714 64429669610
715 64792139560
716 65156136761
717 65521665497
718 65888730058
719 66257334740
720 66627483845
721 66999181681
722 67372432562
723 67747240808
724 68123610745
725 68501546705
726 68881053026
727 69262134052
728 69644794133
729 70029037625
730 70414868890
731 70802292296
732 71191312217
733 71581933033
734 71974159130
735 72367994900
736 72763444741
737 73160513057
738 73559204258
739 73959522760
740 74361472985
741 74765059361
742 75170286322
743 75577158308
744 75985679765
745 76395855145
746 76807688906
747 77221185512
748 77636349433
749 78053185145
750 78471697130
751 78891889876
752 79313767877
753 79737335633
754 80162597650
755 80589558440
756 81018222521
757 81448594417
758 81880678658
759 82314479780
760 82750002325
761 83187250841
762 83626229882
763 84066944008
764 84509397785
765 84953595785
766 85399542586
767 85847242772
768 86296700933
769 86747921665
770 87200909570
771 87655669256
772 88112205337
773 88570522433
774 89030625170
775 89492518180
776 89956206101
777 90421693577
778 90888985258
779 91358085800
780 91828999865
781 92301732121
782 92776287242
783 93252669908
784 93730884805
785 94210936625
786 94692830066
787 95176569832
788 95662160633
789 96149607185
790 96638914210
791 97130086436
792 97623128597
793 98118045433
794 98614841690
795 99113522120
796 99614091481
797 100116554537
798 100620916058
799 101127180820
800 101635353605
801 102145439201
802 102657442402
803 103171368008
804 103687220825
805 104205005665
806 104724727346
807 105246390692
808 105770000533
809 106295561705
810 106823079050
811 107352557416
812 107884001657
813 108417416633
814 108952807210
815 109490178260
816 110029534661
817 110570881297
818 111114223058
819 111659564840
820 112206911545
821 112756268081
822 113307639362
823 113861030308
824 114416445845
825 114973890905
826 115533370426
827 116094889352
828 116658452633
829 117224065225
830 117791732090
831 118361458196
832 118933248517
833 119507108033
834 120083041730
835 120661054600
836 121241151641
837 121823337857
838 122407618258
839 122993997860
840 123582481685
841 124173074761
842 124765782122
843 125360608808
844 125957559865
845 126556640345
846 127157855306
847 127761209812
848 128366708933
849 128974357745
850 129584161330
851 130196124776
852 130810253177
853 131426551633
854 132045025250
855 132665679140
856 133288518421
857 133913548217
858 134540773658
859 135170199880
860 135801832025
861 136435675241
862 137071734682
863 137710015508
864 138350522885
865 138993261985
866 139638237986
867 140285456072
868 140934921433
869 141586639265
870 142240614770
871 142896853156
872 143555359637
873 144216139433
874 144879197770
875 145544539880
876 146212171001
877 146882096377
878 147554321258
879 148228850900
880 148905690565
881 149584845521
882 150266321042
883 150950122408
884 151636254905
885 152324723825
886 153015534466
887 153708692132
888 154404202133
889 155102069785
890 155802300410
891 156504899336
892 157209871897
893 157917223433
894 158626959290
895 159339084820
896 160053605381
897 160770526337
898 161489853058
899 162211590920
900 162935745305
901 163662321601
902 164391325202
903 165122761508
904 165856635925
905 166592953865
906 167331720746
907 168072941992
908 168816623033
909 169562769305
910 170311386250
911 171062479316
912 171816053957
913 172572115633
914 173330669810
915 174091721960
916 174855277561
917 175621342097
918 176389921058
919 177161019940
920 177934644245
921 178710799481
922 179489491162
923 180270724808
924 181054505945
925 181840840105
926 182629732826
927 183421189652
928 184215216133
929 185011817825
930 185811000290
931 186612769096
932 187417129817
933 188224088033
934 189033649330
935 189845819300
936 190660603541
937 191478007657
938 192298037258
939 193120697960
940 193945995385
941 194773935161
942 195604522922
943 196437764308
944 197273664965
945 198112230545
946 198953466706
947 199797379112
948 200643973433
949 201493255345
950 202345230530
951 203199904676
952 204057283477
953 204917372633
954 205780177850
955 206645704840
956 207513959321
957 208384947017
958 209258673658
959 210135144980
960 211014366725
961 211896344641
962 212781084482
963 213668592008
964 214558872985
965 215451933185
966 216347778386
967 217246414372
968 218147846933
969 219052081865
970 219959124970
971 220868982056
972 221781658937
973 222697161433
974 223615495370
975 224536666580
976 225460680901
977 226387544177
978 227317262258
979 228249841000
980 229185286265
981 230123603921
982 231064799842
983 232008879908
984 232955850005
985 233905716025
986 234858483866
987 235814159432
988 236772748633
989 237734257385
990 238698691610
991 239666057236
992 240636360197
993 241609606433
994 242585801890
995 243564952520
996 244547064281
997 245532143137
998 246520195058
999 247511226020
1000 248505242005