1 1
2 4
3 17
4 38
5 81
6 138
7 229
8 340
9 497
10 680
11 921
12 1194
13 1537
14 1918
15 2381
16 2888
17 3489
18 4140
19 4897
20 5710
21 6641
22 7634
23 8757
24 9948
25 11281
26 12688
27 14249
28 15890
29 17697
30 19590
31 21661
32 23824
33 26177
34 28628
35 31281
36 34038
37 37009
38 40090
39 43397
40 46820
41 50481
42 54264
43 58297
44 62458
45 66881
46 71438
47 76269
48 81240
49 86497
50 91900
51 97601
52 103454
53 109617
54 115938
55 122581
56 129388
57 136529
58 143840
59 151497
60 159330
61 167521
62 175894
63 184637
64 193568
65 202881
66 212388
67 222289
68 232390
69 242897
70 253610
71 264741
72 276084
73 287857
74 299848
75 312281
76 324938
77 338049
78 351390
79 365197
80 379240
81 393761
82 408524
83 423777
84 439278
85 455281
86 471538
87 488309
88 505340
89 522897
90 540720
91 559081
92 577714
93 596897
94 616358
95 636381
96 656688
97 677569
98 698740
99 720497
100 742550
101 765201
102 788154
103 811717
104 835588
105 860081
106 884888
107 910329
108 936090
109 962497
110 989230
111 1016621
112 1044344
113 1072737
114 1101468
115 1130881
116 1160638
117 1191089
118 1221890
119 1253397
120 1285260
121 1317841
122 1350784
123 1384457
124 1418498
125 1453281
126 1488438
127 1524349
128 1560640
129 1597697
130 1635140
131 1673361
132 1711974
133 1751377
134 1791178
135 1831781
136 1872788
137 1914609
138 1956840
139 1999897
140 2043370
141 2087681
142 2132414
143 2177997
144 2224008
145 2270881
146 2318188
147 2366369
148 2414990
149 2464497
150 2514450
151 2565301
152 2616604
153 2668817
154 2721488
155 2775081
156 2829138
157 2884129
158 2939590
159 2995997
160 3052880
161 3110721
162 3169044
163 3228337
164 3288118
165 3348881
166 3410138
167 3472389
168 3535140
169 3598897
170 3663160
171 3728441
172 3794234
173 3861057
174 3928398
175 3996781
176 4065688
177 4135649
178 4206140
179 4277697
180 4349790
181 4422961
182 4496674
183 4571477
184 4646828
185 4723281
186 4800288
187 4878409
188 4957090
189 5036897
190 5117270
191 5198781
192 5280864
193 5364097
194 5447908
195 5532881
196 5618438
197 5705169
198 5792490
199 5880997
200 5970100
201 6060401
202 6151304
203 6243417
204 6336138
205 6430081
206 6524638
207 6620429
208 6716840
209 6814497
210 6912780
211 7012321
212 7112494
213 7213937
214 7316018
215 7419381
216 7523388
217 7628689
218 7734640
219 7841897
220 7949810
221 8059041
222 8168934
223 8280157
224 8392048
225 8505281
226 8619188
227 8734449
228 8850390
229 8967697
230 9085690
231 9205061
232 9325124
233 9446577
234 9568728
235 9692281
236 9816538
237 9942209
238 10068590
239 10196397
240 10324920
241 10454881
242 10585564
243 10717697
244 10850558
245 10984881
246 11119938
247 11256469
248 11393740
249 11532497
250 11672000
251 11813001
252 11954754
253 12098017
254 12242038
255 12387581
256 12533888
257 12681729
258 12830340
259 12980497
260 13131430
261 13283921
262 13437194
263 13592037
264 13747668
265 13904881
266 14062888
267 14222489
268 14382890
269 14544897
270 14707710
271 14872141
272 15037384
273 15204257
274 15371948
275 15541281
276 15711438
277 15883249
278 16055890
279 16230197
280 16405340
281 16582161
282 16759824
283 16939177
284 17119378
285 17301281
286 17484038
287 17668509
288 17853840
289 18040897
290 18228820
291 18418481
292 18609014
293 18801297
294 18994458
295 19189381
296 19385188
297 19582769
298 19781240
299 19981497
300 20182650
301 20385601
302 20589454
303 20795117
304 21001688
305 21210081
306 21419388
307 21630529
308 21842590
309 22056497
310 22271330
311 22488021
312 22705644
313 22925137
314 23145568
315 23367881
316 23591138
317 23816289
318 24042390
319 24270397
320 24499360
321 24730241
322 24962084
323 25195857
324 25430598
325 25667281
326 25904938
327 26144549
328 26385140
329 26627697
330 26871240
331 27116761
332 27363274
333 27611777
334 27861278
335 28112781
336 28365288
337 28619809
338 28875340
339 29132897
340 29391470
341 29652081
342 29913714
343 30177397
344 30442108
345 30708881
346 30976688
347 31246569
348 31517490
349 31790497
350 32064550
351 32340701
352 32617904
353 32897217
354 33177588
355 33460081
356 33743638
357 34029329
358 34316090
359 34604997
360 34894980
361 35187121
362 35480344
363 35775737
364 36072218
365 36370881
366 36670638
367 36972589
368 37275640
369 37580897
370 37887260
371 38195841
372 38505534
373 38817457
374 39130498
375 39445781
376 39762188
377 40080849
378 40400640
379 40722697
380 41045890
381 41371361
382 41697974
383 42026877
384 42356928
385 42689281
386 43022788
387 43358609
388 43695590
389 44034897
390 44375370
391 44718181
392 45062164
393 45408497
394 45756008
395 46105881
396 46456938
397 46810369
398 47164990
399 47521997
400 47880200
401 48240801
402 48602604
403 48966817
404 49332238
405 49700081
406 50069138
407 50440629
408 50813340
409 51188497
410 51564880
411 51943721
412 52323794
413 52706337
414 53090118
415 53476381
416 53863888
417 54253889
418 54645140
419 55038897
420 55433910
421 55831441
422 56230234
423 56631557
424 57034148
425 57439281
426 57845688
427 58254649
428 58664890
429 59077697
430 59491790
431 59908461
432 60326424
433 60746977
434 61168828
435 61593281
436 62019038
437 62447409
438 62877090
439 63309397
440 63743020
441 64179281
442 64616864
443 65057097
444 65498658
445 65942881
446 66388438
447 66836669
448 67286240
449 67738497
450 68192100
451 68648401
452 69106054
453 69566417
454 70028138
455 70492581
456 70958388
457 71426929
458 71896840
459 72369497
460 72843530
461 73320321
462 73798494
463 74279437
464 74761768
465 75246881
466 75733388
467 76222689
468 76713390
469 77206897
470 77701810
471 78199541
472 78698684
473 79200657
474 79704048
475 80210281
476 80717938
477 81228449
478 81740390
479 82255197
480 82771440
481 83290561
482 83811124
483 84334577
484 84859478
485 85387281
486 85916538
487 86448709
488 86982340
489 87518897
490 88056920
491 88597881
492 89140314
493 89685697
494 90232558
495 90782381
496 91333688
497 91887969
498 92443740
499 93002497
500 93562750
501 94126001
502 94690754
503 95258517
504 95827788
505 96400081
506 96973888
507 97550729
508 98129090
509 98710497
510 99293430
511 99879421
512 100466944
513 101057537
514 101649668
515 102244881
516 102841638
517 103441489
518 104042890
519 104647397
520 105253460
521 105862641
522 106473384
523 107087257
524 107702698
525 108321281
526 108941438
527 109564749
528 110189640
529 110817697
530 111447340
531 112080161
532 112714574
533 113352177
534 113991378
535 114633781
536 115277788
537 115925009
538 116573840
539 117225897
540 117879570
541 118536481
542 119195014
543 119856797
544 120520208
545 121186881
546 121855188
547 122526769
548 123199990
549 123876497
550 124554650
551 125236101
552 125919204
553 126605617
554 127293688
555 127985081
556 128678138
557 129374529
558 130072590
559 130773997
560 131477080
561 132183521
562 132891644
563 133603137
564 134316318
565 135032881
566 135751138
567 136472789
568 137196140
569 137922897
570 138651360
571 139383241
572 140116834
573 140853857
574 141592598
575 142334781
576 143078688
577 143826049
578 144575140
579 145327697
580 146081990
581 146839761
582 147599274
583 148362277
584 149127028
585 149895281
586 150665288
587 151438809
588 152214090
589 152992897
590 153773470
591 154557581
592 155343464
593 156132897
594 156924108
595 157718881
596 158515438
597 159315569
598 160117490
599 160922997
600 161730300
601 162541201
602 163353904
603 164170217
604 164988338
605 165810081
606 166633638
607 167460829
608 168289840
609 169122497
610 169956980
611 170795121
612 171635094
613 172478737
614 173324218
615 174173381
616 175024388
617 175879089
618 176735640
619 177595897
620 178458010
621 179323841
622 180191534
623 181062957
624 181936248
625 182813281
626 183692188
627 184574849
628 185459390
629 186347697
630 187237890
631 188131861
632 189027724
633 189927377
634 190828928
635 191734281
636 192641538
637 193552609
638 194465590
639 195382397
640 196301120
641 197223681
642 198148164
643 199076497
644 200006758
645 200940881
646 201876938
647 202816869
648 203758740
649 204704497
650 205652200
651 206603801
652 207557354
653 208514817
654 209474238
655 210437581
656 211402888
657 212372129
658 213343340
659 214318497
660 215295630
661 216276721
662 217259794
663 218246837
664 219235868
665 220228881
666 221223888
667 222222889
668 223223890
669 224228897
670 225235910
671 226246941
672 227259984
673 228277057
674 229296148
675 230319281
676 231344438
677 232373649
678 233404890
679 234440197
680 235477540
681 236518961
682 237562424
683 238609977
684 239659578
685 240713281
686 241769038
687 242828909
688 243890840
689 244956897
690 246025020
691 247097281
692 248171614
693 249250097
694 250330658
695 251415381
696 252502188
697 253593169
698 254686240
699 255783497
700 256882850
701 257986401
702 259092054
703 260201917
704 261313888
705 262430081
706 263548388
707 264670929
708 265795590
709 266924497
710 268055530
711 269190821
712 270328244
713 271469937
714 272613768
715 273761881
716 274912138
717 276066689
718 277223390
719 278384397
720 279547560
721 280715041
722 281884684
723 283058657
724 284234798
725 285415281
726 286597938
727 287784949
728 288974140
729 290167697
730 291363440
731 292563561
732 293765874
733 294972577
734 296181478
735 297394781
736 298610288
737 299830209
738 301052340
739 302278897
740 303507670
741 304740881
742 305976314
743 307216197
744 308458308
745 309704881
746 310953688
747 312206969
748 313462490
749 314722497
750 315984750
751 317251501
752 318520504
753 319794017
754 321069788
755 322350081
756 323632638
757 324919729
758 326209090
759 327502997
760 328799180
761 330099921
762 331402944
763 332710537
764 334020418
765 335334881
766 336651638
767 337972989
768 339296640
769 340624897
770 341955460
771 343290641
772 344628134
773 345970257
774 347314698
775 348663781
776 350015188
777 351371249
778 352729640
779 354092697
780 355458090
781 356828161
782 358200574
783 359577677
784 360957128
785 362341281
786 363727788
787 365119009
788 366512590
789 367910897
790 369311570
791 370716981
792 372124764
793 373537297
794 374952208
795 376371881
796 377793938
797 379220769
798 380649990
799 382083997
800 383520400
801 384961601
802 386405204
803 387853617
804 389304438
805 390760081
806 392218138
807 393681029
808 395146340
809 396616497
810 398089080
811 399566521
812 401046394
813 402531137
814 404018318
815 405510381
816 407004888
817 408504289
818 410006140
819 411512897
820 413022110
821 414536241
822 416052834
823 417574357
824 419098348
825 420627281
826 422158688
827 423695049
828 425233890
829 426777697
830 428323990
831 429875261
832 431429024
833 432987777
834 434549028
835 436115281
836 437684038
837 439257809
838 440834090
839 442415397
840 443999220
841 445588081
842 447179464
843 448775897
844 450374858
845 451978881
846 453585438
847 455197069
848 456811240
849 458430497
850 460052300
851 461679201
852 463308654
853 464943217
854 466580338
855 468222581
856 469867388
857 471517329
858 473169840
859 474827497
860 476487730
861 478153121
862 479821094
863 481494237
864 483169968
865 484850881
866 486534388
867 488223089
868 489914390
869 491610897
870 493310010
871 495014341
872 496721284
873 498433457
874 500148248
875 501868281
876 503590938
877 505318849
878 507049390
879 508785197
880 510523640
881 512267361
882 514013724
883 515765377
884 517519678
885 519279281
886 521041538
887 522809109
888 524579340
889 526354897
890 528133120
891 529916681
892 531702914
893 533494497
894 535288758
895 537088381
896 538890688
897 540698369
898 542508740
899 544324497
900 546142950
901 547966801
902 549793354
903 551625317
904 553459988
905 555300081
906 557142888
907 558991129
908 560842090
909 562698497
910 564557630
911 566422221
912 568289544
913 570162337
914 572037868
915 573918881
916 575802638
917 577691889
918 579583890
919 581481397
920 583381660
921 585287441
922 587195984
923 589110057
924 591026898
925 592949281
926 594874438
927 596805149
928 598738640
929 600677697
930 602619540
931 604566961
932 606517174
933 608472977
934 610431578
935 612395781
936 614362788
937 616335409
938 618310840
939 620291897
940 622275770
941 624265281
942 626257614
943 628255597
944 630256408
945 632262881
946 634272188
947 636287169
948 638304990
949 640328497
950 642354850
951 644386901
952 646421804
953 648462417
954 650505888
955 652555081
956 654607138
957 656664929
958 658725590
959 660791997
960 662861280
961 664936321
962 667014244
963 669097937
964 671184518
965 673276881
966 675372138
967 677473189
968 679577140
969 681686897
970 683799560
971 685918041
972 688039434
973 690166657
974 692296798
975 694432781
976 696571688
977 698716449
978 700864140
979 703017697
980 705174190
981 707336561
982 709501874
983 711673077
984 713847228
985 716027281
986 718210288
987 720399209
988 722591090
989 724788897
990 726989670
991 729196381
992 731406064
993 733621697
994 735840308
995 738064881
996 740292438
997 742525969
998 744762490
999 747004997
1000 749250500