1 1
2 2
3 4
4 7
5 12
6 18
7 28
8 39
9 55
10 74
11 100
12 127
13 167
14 208
15 261
16 322
17 399
18 477
19 581
20 686
21 820
22 967
23 1142
24 1318
25 1545
26 1778
27 2053
28 2347
29 2697
30 3048
31 3486
32 3925
33 4441
34 4986
35 5610
36 6250
37 7024
38 7799
39 8680
40 9604
41 10673
42 11743
43 13008
44 14274
45 15718
46 17239
47 18937
48 20636
49 22623
50 24621
51 26872
52 29203
53 31812
54 34422
55 37411
56 40432
57 43814
58 47303
59 51144
60 54986
61 59401
62 63817
63 68673
64 73692
65 79227
66 84808
67 91088
68 97369
69 104277
70 111363
71 119150
72 126938
73 135687
74 144437
75 153963
76 163777
77 174475
78 185210
79 197109
80 209009
81 222039
82 235363
83 249758
84 264154
85 280139
86 296207
87 313542
88 331230
89 350373
90 369517
91 390637
92 411808
93 434680
94 457993
95 483006
96 508129
97 535678
98 563228
99 592818
100 622969
101 655479
102 687990
103 723384
104 758779
105 796794
106 835638
107 877093
108 918549
109 963664
110 1008780
111 1057084
112 1106165
113 1158689
114 1211214
115 1268010
116 1324987
117 1385808
118 1447569
119 1513173
120 1578865
121 1650083
122 1721328
123 1796990
124 1873724
125 1955317
126 2037143
127 2125184
128 2213226
129 2306803
130 2401648
131 2502327
132 2603007
133 2711263
134 2819634
135 2934287
136 3050736
137 3174104
138 3297473
139 3429456
140 3561440
141 3701613
142 3843487
143 3993150
144 4142880
145 4303119
146 4463714
147 4633060
148 4804540
149 4985549
150 5166559
151 5359758
152 5552958
153 5756867
154 5963123
155 6180303
156 6397927
157 6629811
158 6861696
159 7105482
160 7351880
161 7611747
162 7871800
163 8147872
164 8423945
165 8714416
166 9008479
167 9316939
168 9625400
169 9953054
170 10280749
171 10625077
172 10972910
173 11338081
174 11703253
175 12089609
176 12476832
177 12883259
178 13293530
179 13722946
180 14152363
181 14607517
182 15062672
183 15539273
184 16020292
185 16524194
186 17028876
187 17561294
188 18093816
189 18651354
190 19214186
191 19802936
192 20391687
193 21013006
194 21634326
195 22283197
196 22938585
197 23623860
198 24309136
199 25030376
200 25751617
201 26506303
202 27267272
203 28060753
204 28854595
205 29690142
206 30526764
207 31398782
208 32277902
209 33195098
210 34112425
211 35077170
212 36041916
213 37048120
214 38062114
215 39117565
216 40174287
217 41284099
218 42394360
219 43549738
220 44713868
221 45927676
222 47141602
223 48413366
224 49685131
225 51009859
226 52345861
227 53734389
228 55122918
229 56578087
230 58033257
231 59546945
232 61072020
233 62657927
234 64243835
235 65902557
236 67562983
237 69289016
238 71026951
239 72831165
240 74635380
241 76524473
242 78413567
243 80374054
244 82347865
245 84397341
246 86449444
247 88591612
248 90733925
249 92957842
250 95196157
251 97518316
252 99840476
253 102266037
254 104691800
255 107205606
256 109737786
257 112363543
258 114989301
259 117725979
260 120463442
261 123304023
262 126162308
263 129121274
264 132080241
265 135165339
266 138253052
267 141449953
268 144666000
269 147996703
270 151327407
271 154796769
272 158266132
273 161858924
274 165473904
275 169212254
276 172953852
277 176848634
278 180743417
279 184770185
280 188820282
281 193014508
282 197208735
283 201568156
284 205927578
285 210436666
286 214974314
287 219662073
288 224350912
289 229225552
290 234100270
291 239139092
292 244205466
293 249441189
294 254676913
295 260112785
296 265552504
297 271173243
298 276824408
299 282656584
300 288488976
301 294548695
302 300609690
303 306863886
304 313150595
305 319641274
306 326136374
307 332870871
308 339605369
309 346558610
310 353547248
311 360757946
312 367968645
313 375446810
314 382924976
315 390635028
316 398390240
317 406389241
318 414388243
319 422672494
320 430957122
321 439506636
322 448097608
323 456950196
324 465802966
325 474973934
326 484150710
327 493603560
328 503101528
329 512889978
330 522680137
331 532815580
332 542951024
333 553394931
334 563887935
335 574689401
336 585497153
337 596683400
338 607869648
339 619383825
340 630950529
341 642867950
342 654785836
343 667104940
344 679426042
345 692112326
346 704862550
347 717977947
348 731093345
349 744652106
350 758210868
351 772165998
352 786183164
353 800607196
354 815031229
355 829927301
356 844831166
357 860164450
358 875565813
359 891396594
360 907227376
361 923587903
362 939948535
363 956764323
364 973651874
365 991018654
366 1008394189
367 1026321995
368 1044249802
369 1062681572
370 1081190092
371 1100212064
372 1119236656
373 1138870430
374 1158504205
375 1178671195
376 1198929592
377 1219745538
378 1240561875
379 1262026676
380 1283491478
381 1305554952
382 1327706470
383 1350446740
384 1373187011
385 1396636643
386 1420100628
387 1444185934
388 1468366101
389 1493195142
390 1518024184
391 1543614804
392 1569205677
393 1595484857
394 1621864719
395 1648929858
396 1676006902
397 1703907802
398 1731808703
399 1760430846
400 1789164878
401 1818665557
402 1848166237
403 1878536264
404 1908906770
405 1940070760
406 1971364229
407 2003455071
408 2035546714
409 2068590540
410 2101634367
411 2135528160
412 2169545324
413 2204434509
414 2239327546
415 2275224678
416 2311136211
417 2347965379
418 2384926533
419 2422805937
420 2460685342
421 2499680143
422 2538674945
423 2578634494
424 2618735933
425 2659843587
426 2700967536
427 2743247360
428 2785531610
429 2828871314
430 2872362147
431 2916925790
432 2961489434
433 3007314380
434 3053139327
435 3100078993
436 3147196644
437 3195469676
438 3243742988
439 3293341032
440 3342939077
441 3393769553
442 3444776381
443 3496997914
444 3549219448
445 3602884256
446 3656568213
447 3711523936
448 3766660671
449 3823127153
450 3879593636
451 3937598728
452 3995604916
453 4054999635
454 4114587556
455 4175564007
456 4236567793
457 4299220135
458 4361872478
459 4425979992
460 4490294037
461 4556143049
462 4621992062
463 4689579252
464 4757166443
465 4826339602
466 4895753312
467 4966752931
468 5037752551
469 5110631518
470 5183516776
471 5258085793
472 5332886697
473 5409413645
474 5485941885
475 5564439952
476 5642963369
477 5723297578
478 5803878201
479 5886263040
480 5968647880
481 6053193773
482 6137740481
483 6224176284
484 6310879184
485 6399543840
486 6488236051
487 6579164821
488 6670093592
489 6763071850
490 6856326183
491 6951667316
492 7047008450
493 7144767855
494 7242527688
495 7342430843
496 7442659111
497 7545111357
498 7647571401
499 7752563830
500 7857556260
501 7964901108
502 8072554419
503 8182529891
504 8292505364
505 8405225855
506 8517978862
507 8633159301
508 8748668318
509 8866691144
510 8984713971
511 9105630106
512 9226555001
513 9350105653
514 9474004413
515 9600528932
516 9727088851
517 9856733311
518 9986379496
519 10118771936
520 10251529550
521 10387164075
522 10522798601
523 10661660158
524 10800521716
525 10942342243
526 11084597723
527 11229812171
528 11375027135
529 11523716180
530 11672405401
531 11824221199
532 11976447284
533 12131880381
534 12287314588
535 12446375120
536 12605477113
537 12767909820
538 12930771946
539 13096964777
540 13263170330
541 13433320735
542 13603471141
543 13777090911
544 13951165838
545 14128833996
546 14306547275
547 14488342775
548 14670138276
549 14855672130
550 15041687019
551 15231490787
552 15421295010
553 15615475221
554 15809667342
555 16007754247
556 16206394193
557 16409060910
558 16611727628
559 16818953626
560 17026180930
561 17237663502
562 17449681365
563 17665893456
564 17882105548
565 18103209613
566 18324366208
567 18549882226
568 18775974106
569 19006575085
570 19237176065
571 19472931202
572 19708686340
573 19949132837
574 20190168087
575 20435905542
576 20681700201
577 20932963270
578 21184226340
579 21440364674
580 21697124330
581 21958979893
582 22220849862
583 22488407532
584 22755967838
585 23028763878
586 23302277587
587 23581027021
588 23859776456
589 24144631871
590 24429487829
591 24719845287
592 25010888023
593 25307551559
594 25604215096
595 25907223497
596 26210314204
597 26519237090
598 26828881219
599 27144359495
600 27459837772
601 27782163812
602 28104489853
603 28432892999
604 28762057130
605 29097475460
606 29432968029
607 29775508283
608 30118048538
609 30467079911
610 30816922597
611 31173331648
612 31529742438
613 31893688518
614 32257634599
615 32628315179
616 32999908098
617 33378474978
618 33757041859
619 34143434007
620 34529826156
621 34923505845
622 35318064929
623 35719834713
624 36121623651
625 36531771634
626 36942001443
627 37359709419
628 37778338622
629 38204677880
630 38631017990
631 39066140261
632 39501262533
633 39944383817
634 40388469849
635 40840554884
636 41292727966
637 41754150075
638 42215595342
639 42685328874
640 43156076416
641 43635461514
642 44114846613
643 44603836685
644 45092826758
645 45590690887
646 46089705370
647 46597573944
648 47105442519
649 47623546759
650 48141654867
651 48669036847
652 49197552096
653 49735520198
654 50273488301
655 50822064640
656 51370741664
657 51929207199
658 52488836880
659 53058280075
660 53627723271
661 54208571963
662 54789420656
663 55380404794
664 55972605992
665 56575251108
666 57178030237
667 57792525131
668 58407020551
669 59032317440
670 59658886096
671 60296370895
672 60933860136
673 61583832951
674 62233805767
675 62894964832
676 63557574827
677 64231701333
678 64905827840
679 65592857060
680 66279913840
681 66979005425
682 67679485541
683 68391888107
684 69104290674
685 69830411358
686 70556655416
687 71295248168
688 72035296092
689 72788030361
690 73540767280
691 74307834860
692 75074902441
693 75855085422
694 76636827940
695 77431685857
696 78226675763
697 79036749692
698 79846824768
699 80670458607
700 81495678356
701 82335015772
702 83174353189
703 84029307343
704 84884262376
705 85753646460
706 86624831198
707 87510439970
708 88396081263
709 89298279084
710 90200476906
711 91117720487
712 92036702019
713 92971016846
714 93905332287
715 94856821200
716 95808468372
717 96775946328
718 97745228501
719 98730341457
720 99715454414
721 100718895503
722 101722371997
723 102742209899
724 103763936897
725 104802479686
726 105841183297
727 106898669288
728 107956155280
729 109031046479
730 110107911489
731 111202312649
732 112296715152
733 113411019302
734 114525323453
735 115657555412
736 116792047024
737 117944970845
738 119097900973
739 120271405133
740 121444909294
741 122637607015
742 123832451314
743 125046359091
744 126260266869
745 127495950921
746 128731815988
747 129987314831
748 131245052005
749 132522963719
750 133800916899
751 135101550176
752 136402183454
753 137723632739
754 139047404186
755 140391995693
756 141736780405
757 143105408894
758 144474037384
759 145864130677
760 147256657159
761 148671441250
762 150086225342
763 151525586722
764 152964993228
765 154427140007
766 155892024335
767 157379648935
768 158867277417
769 160380887711
770 161894498006
771 163431830952
772 164971789658
773 166535833673
774 168099877689
775 169690743783
776 171281827728
777 172897740725
778 174516439625
779 176159967568
780 177803496685
781 179475577817
782 181147666763
783 182845348649
784 184545889095
785 186272757863
786 187999858521
787 189756197333
788 191512536146
789 193295940101
790 195082303025
791 196895974898
792 198709699306
793 200554309244
794 202398923638
795 204271438934
796 206147285784
797 208051754780
798 209956223777
799 211892568937
800 213828915873
801 215795010325
802 217764320840
803 219763132036
804 221761952008
805 223794358084
806 225827081638
807 227890180348
808 229956609764
809 232054203181
810 234151796599
811 236284296452
812 238416796306
813 240581444276
814 242749561611
815 244949779487
816 247150273441
817 249387282344
818 251624292617
819 253894346718
820 256168081492
821 258475986240
822 260783890989
823 263129427889
824 265474964790
825 267855390887
826 270239859150
827 272659282253
828 275078705357
829 277537789032
830 279996872708
831 282492162000
832 284991346077
833 287527364341
834 290063450284
835 292640392171
836 295217642524
837 297832783364
838 300451974576
839 303109045194
840 305766115813
841 308466609615
842 311167103768
843 313906592724
844 316650275909
845 319433918646
846 322217894618
847 325046189654
848 327874566643
849 330744051347
850 333617895475
851 336533193810
852 339448493095
853 342410431656
854 345372370218
855 348376664317
856 351385841852
857 354438359102
858 357490876353
859 360591438788
860 363692001224
861 366837475244
862 369987713901
863 373182516203
864 376377318506
865 379622660156
866 382868366983
867 386159898758
868 389456307504
869 392799732947
870 396143170316
871 399538969092
872 402934774189
873 406378852329
874 409827996859
875 413325416998
876 416823305953
877 420375859356
878 423928412760
879 427530564210
880 431137951386
881 434796568222
882 438455185059
883 442170155020
884 445885124982
885 449652325092
886 453425371403
887 457250639249
888 461075907096
889 464960279657
890 468844740270
891 472783295131
892 476727514187
893 480726688969
894 484725865554
895 488785830046
896 492846223960
897 496963172398
898 501085961019
899 505265216124
900 509444472018
901 513688029581
902 517931589831
903 522233169741
904 526540904359
905 530908033707
906 535275618215
907 539708851646
908 544142085078
909 548636294964
910 553136791575
911 557698849352
912 562260907130
913 566891905719
914 571522918730
915 576216584085
916 580917221196
917 585681965824
918 590446811142
919 595282501356
920 600118191571
921 605020212752
922 609928968433
923 614903573128
924 619878185651
925 624927236528
926 629976792314
927 635093935292
928 640218066924
929 645411372154
930 650604677385
931 655874894439
932 661145221851
933 666486548885
934 671835086620
935 677254623976
936 682674712833
937 688174934726
938 693675156620
939 699248372185
940 704829065918
941 710484861298
942 716140656679
943 721878731137
944 727616806840
945 733431409552
946 739254439942
947 745154014788
948 751053589635
949 757039417791
950 763025254737
951 769090180725
952 775163105717
953 781316484399
954 787469863082
955 793711860319
956 799954446312
957 806279417147
958 812612690463
959 819028348620
960 825444130156
961 831953335983
962 838462542249
963 845056304207
964 851658657153
965 858347445905
966 865036855982
967 871821685939
968 878606515897
969 885480028210
970 892362398928
971 899334083197
972 906305767467
973 913377275403
974 920448915333
975 927611484035
976 934783888846
977 942049271976
978 949314655107
979 956682469354
980 964050302771
981 971514265095
982 978987725403
983 986556526846
984 994125328290
985 1001801387294
986 1009478131579
987 1017252639732
988 1025037078353
989 1032921432277
990 1040805787642
991 1048800917153
992 1056796046665
993 1064893628862
994 1073001346505
995 1081211666108
996 1089422706957
997 1097748875709
998 1106075044462
999 1114506205646
1000 1122947860109