1 1
2 1
3 2
4 4
5 8
6 14
7 25
8 40
9 65
10 97
11 146
12 206
13 292
14 394
15 533
16 694
17 905
18 1145
19 1450
20 1792
21 2216
22 2686
23 3257
24 3884
25 4633
26 5449
27 6410
28 7450
29 8660
30 9962
31 11461
32 13066
33 14897
34 16849
35 19058
36 21404
37 24040
38 26830
39 29945
40 33232
41 36881
42 40721
43 44962
44 49414
45 54308
46 59434
47 65045
48 70910
49 77305
50 83977
51 91226
52 98776
53 106952
54 115454
55 124633
56 134164
57 144425
58 155065
59 166490
60 178322
61 190996
62 204106
63 218117
64 232594
65 248033
66 263969
67 280930
68 298420
69 317000
70 336142
71 356441
72 377336
73 399457
74 422209
75 446258
76 470974
77 497060
78 523850
79 552085
80 581062
81 611561
82 642841
83 675722
84 709424
85 744808
86 781054
87 819065
88 857980
89 898745
90 940457
91 984106
92 1028746
93 1075412
94 1123114
95 1172933
96 1223834
97 1276945
98 1331185
99 1387730
100 1445452
101 1505576
102 1566926
103 1630777
104 1695904
105 1763633
106 1832689
107 1904450
108 1977590
109 2053540
110 2130922
111 2211221
112 2293006
113 2377817
114 2464169
115 2553658
116 2644744
117 2739080
118 2835070
119 2934425
120 3035492
121 3140041
122 3246361
123 3356282
124 3468034
125 3583508
126 3700874
127 3822085
128 3945250
129 4072385
130 4201537
131 4334786
132 4470116
133 4609672
134 4751374
135 4897433
136 5045704
137 5198465
138 5353505
139 5513170
140 5675182
141 5841956
142 6011146
143 6185237
144 6361814
145 6543433
146 6727609
147 6916970
148 7108960
149 7306280
150 7506302
151 7711801
152 7920076
153 8133977
154 8350729
155 8573258
156 8798714
157 9030100
158 9264490
159 9504965
160 9748522
161 9998321
162 10251281
163 10510642
164 10773244
165 11042408
166 11314894
167 11594105
168 11876720
169 12166225
170 12459217
171 12759266
172 13062886
173 13373732
174 13688234
175 14010133
176 14335774
177 14668985
178 15006025
179 15350810
180 15699512
181 16056136
182 16416766
183 16785497
184 17158324
185 17539433
186 17924729
187 18318490
188 18716530
189 19123220
190 19534282
191 19954181
192 20378546
193 20811937
194 21249889
195 21697058
196 22148884
197 22610120
198 23076110
199 23551705
200 24032152
201 24522401
202 25017601
203 25522802
204 26033054
205 26553508
206 27079114
207 27615125
208 28156390
209 28708265
210 29265497
211 29833546
212 30407056
213 30991592
214 31581694
215 32183033
216 32790044
217 33408505
218 34032745
219 34668650
220 35310442
221 35964116
222 36623786
223 37295557
224 37973434
225 38663633
226 39360049
227 40069010
228 40784300
229 41512360
230 42246862
231 42994361
232 43748416
233 44515697
234 45289649
235 46077058
236 46871254
237 47679140
238 48493930
239 49322645
240 50158382
241 51008281
242 51865321
243 52736762
244 53615464
245 54508808
246 55409534
247 56325145
248 57248260
249 58186505
250 59132377
251 60093626
252 61062626
253 62047252
254 63039754
255 64048133
256 65064514
257 66097025
258 67137665
259 68194690
260 69259972
261 70341896
262 71432206
263 72539417
264 73655144
265 74788033
266 75929569
267 77088530
268 78256270
269 79441700
270 80636042
271 81848341
272 83069686
273 84309257
274 85558009
275 86825258
276 88101824
277 89397160
278 90701950
279 92025785
280 93359212
281 94711961
282 96074441
283 97456522
284 98848474
285 100260308
286 101682154
287 103124165
288 104576330
289 106048945
290 107531857
291 109035506
292 110549596
293 112084712
294 113630414
295 115197433
296 116775184
297 118374545
298 119984785
299 121616930
300 123260102
301 124925476
302 126602026
303 128301077
304 130011454
305 131744633
306 133489289
307 135257050
308 137036440
309 138839240
310 140653822
311 142492121
312 144342356
313 146216617
314 148102969
315 150013658
316 151936594
317 153884180
318 155844170
319 157829125
320 159826642
321 161849441
322 163884961
323 165946082
324 168020084
325 170120008
326 172232974
327 174372185
328 176524600
329 178703585
330 180895937
331 183115186
332 185347966
333 187607972
334 189881674
335 192182933
336 194498054
337 196841065
338 199198105
339 201583370
340 203982832
341 206410856
342 208853246
343 211324537
344 213810364
345 216325433
346 218855209
347 221414570
348 223988810
349 226592980
350 229212202
351 231861701
352 234526426
353 237221777
354 239932529
355 242674258
356 245431564
357 248220200
358 251024590
359 253860665
360 256712672
361 259596721
362 262496881
363 265429442
364 268378294
365 271359908
366 274357994
367 277389205
368 280437070
369 283518425
370 286616617
371 289748666
372 292897736
373 296081032
374 299281534
375 302516633
376 305769124
377 309056585
378 312361625
379 315702010
380 319060162
381 322454036
382 325865866
383 329313797
384 332779874
385 336282433
386 339803329
387 343361090
388 346937380
389 350550920
390 354183182
391 357853081
392 361541896
393 365268737
394 369014689
395 372799058
396 376602734
397 380445220
398 384307210
399 388208405
400 392129302
401 396089801
402 400070201
403 404090602
404 408131104
405 412212008
406 416313214
407 420455225
408 424617740
409 428821465
410 433045897
411 437311946
412 441598906
413 445927892
414 450277994
415 454670533
416 459084394
417 463541105
418 468019345
419 472540850
420 477084092
421 481671016
422 486279886
423 490932857
424 495607984
425 500327633
426 505069649
427 509856610
428 514666150
429 519521060
430 524398762
431 529322261
432 534268766
433 539261497
434 544277449
435 549340058
436 554426104
437 559559240
438 564716030
439 569920345
440 575148532
441 580424681
442 585724921
443 591073562
444 596446514
445 601868308
446 607314634
447 612810245
448 618330610
449 623900705
450 629495777
451 635141026
452 640811476
453 646532552
454 652279054
455 658076633
456 663899864
457 669774625
458 675675265
459 681627890
460 687606622
461 693637796
462 699695306
463 705805717
464 711942694
465 718133033
466 724350169
467 730621130
468 736919120
469 743271400
470 749650942
471 756085241
472 762547036
473 769064057
474 775608809
475 782209258
476 788837674
477 795522260
478 802235050
479 809004485
480 815802362
481 822657361
482 829541041
483 836482322
484 843452524
485 850480808
486 857538254
487 864654265
488 871799680
489 879004145
490 886238257
491 893531906
492 900855446
493 908239012
494 915652714
495 923126933
496 930631534
497 938197145
498 945793385
499 953451130
500 961139752
501 968890376
502 976672126
503 984516377
504 992392004
505 1000330633
506 1008300889
507 1016334650
508 1024400290
509 1032529940
510 1040691722
511 1048918021
512 1057176706
513 1065500417
514 1073856769
515 1082278658
516 1090733444
517 1099254280
518 1107808270
519 1116428825
520 1125082792
521 1133803841
522 1142558561
523 1151380882
524 1160237134
525 1169161508
526 1178120074
527 1187147285
528 1196208950
529 1205339785
530 1214505337
531 1223740586
532 1233010816
533 1242351272
534 1251726974
535 1261173433
536 1270655404
537 1280208665
538 1289797705
539 1299458570
540 1309155482
541 1318924756
542 1328730346
543 1338608837
544 1348523914
545 1358512433
546 1368537809
547 1378637170
548 1388773660
549 1398984680
550 1409233102
551 1419556601
552 1429917776
553 1440354577
554 1450829329
555 1461380258
556 1471969414
557 1482635300
558 1493339690
559 1504121365
560 1514941822
561 1525840121
562 1536777481
563 1547793242
564 1558848344
565 1569982408
566 1581156094
567 1592409305
568 1603702420
569 1615075625
570 1626489017
571 1637983066
572 1649517586
573 1661133332
574 1672789834
575 1684528133
576 1696307474
577 1708169185
578 1720072225
579 1732058210
580 1744085812
581 1756196936
582 1768349966
583 1780587097
584 1792866424
585 1805230433
586 1817636929
587 1830128690
588 1842663230
589 1855283620
590 1867947082
591 1880696981
592 1893490246
593 1906370537
594 1919294489
595 1932306058
596 1945361584
597 1958505320
598 1971693310
599 1984970105
600 1998291452
601 2011702201
602 2025157801
603 2038703402
604 2052294154
605 2065975508
606 2079702314
607 2093520325
608 2107384090
609 2121339665
610 2135341297
611 2149435346
612 2163575756
613 2177809192
614 2192089294
615 2206463033
616 2220883744
617 2235398705
618 2249960945
619 2264618050
620 2279322742
621 2294122916
622 2308970986
623 2323915157
624 2338907534
625 2353996633
626 2369134249
627 2384369210
628 2399653000
629 2415034760
630 2430465662
631 2445995161
632 2461574116
633 2477252297
634 2492980249
635 2508808058
636 2524685954
637 2540664340
638 2556693130
639 2572823045
640 2589003682
641 2605286081
642 2621619521
643 2638055362
644 2654542564
645 2671132808
646 2687774734
647 2704520345
648 2721317960
649 2738219905
650 2755174177
651 2772233426
652 2789345326
653 2806562852
654 2823833354
655 2841210133
656 2858640214
657 2876177225
658 2893767865
659 2911466090
660 2929218272
661 2947078696
662 2964993406
663 2983017017
664 3001095244
665 3019283033
666 3037525769
667 3055878730
668 3074286970
669 3092806100
670 3111380842
671 3130067141
672 3148809386
673 3167663857
674 3186574609
675 3205598258
676 3224678524
677 3243872360
678 3263123150
679 3282488185
680 3301910512
681 3321447761
682 3341042641
683 3360753122
684 3380521574
685 3400406308
686 3420349354
687 3440409365
688 3460528030
689 3480764345
690 3501059657
691 3521473306
692 3541946296
693 3562538312
694 3583190014
695 3603961433
696 3624792884
697 3645744745
698 3666756985
699 3687890330
700 3709084402
701 3730400276
702 3751777226
703 3773276677
704 3794837554
705 3816521633
706 3838267489
707 3860137250
708 3882069140
709 3904125640
710 3926244622
711 3948488921
712 3970796056
713 3993229217
714 4015725569
715 4038348658
716 4061035294
717 4083849380
718 4106727370
719 4129733525
720 4152803942
721 4176003241
722 4199267161
723 4222660682
724 4246119184
725 4269708008
726 4293362174
727 4317147385
728 4340998300
729 4364980985
730 4389029737
731 4413210986
732 4437458666
733 4461839572
734 4486287274
735 4510868933
736 4535517754
737 4560301265
738 4585152305
739 4610138770
740 4635193132
741 4660383656
742 4685642446
743 4711038137
744 4736502464
745 4762104433
746 4787775409
747 4813584770
748 4839463510
749 4865481380
750 4891569002
751 4917796501
752 4944094126
753 4970532377
754 4997041129
755 5023691258
756 5050412264
757 5077275400
758 5104209790
759 5131287065
760 5158435972
761 5185728521
762 5213093081
763 5240602042
764 5268183394
765 5295909908
766 5323709194
767 5351654405
768 5379672770
769 5407837825
770 5436076417
771 5464462466
772 5492922436
773 5521530632
774 5550213134
775 5579044633
776 5607950824
777 5637006785
778 5666137825
779 5695419410
780 5724776462
781 5754284836
782 5783869066
783 5813605397
784 5843417974
785 5873383433
786 5903425529
787 5933621290
788 5963894080
789 5994321320
790 6024825982
791 6055485881
792 6086223596
793 6117117337
794 6148089289
795 6179218058
796 6210425434
797 6241790420
798 6273234410
799 6304836805
800 6336518602
801 6368359601
802 6400280401
803 6432361202
804 6464522204
805 6496844008
806 6529246414
807 6561810425
808 6594455440
809 6627262865
810 6660151697
811 6693203746
812 6726337606
813 6759635492
814 6793015594
815 6826560533
816 6860188094
817 6893981305
818 6927857545
819 6961900250
820 6996026392
821 7030319816
822 7064697086
823 7099242457
824 7133872084
825 7168670633
826 7203553849
827 7238606810
828 7273744850
829 7309053460
830 7344447562
831 7380013061
832 7415664466
833 7451488097
834 7487398049
835 7523481058
836 7559650804
837 7595994440
838 7632425230
839 7669030745
840 7705723832
841 7742592481
842 7779549121
843 7816682162
844 7853903614
845 7891302308
846 7928789834
847 7966455445
848 8004210310
849 8042144105
850 8080167577
851 8118370826
852 8156664176
853 8195138152
854 8233702654
855 8272448633
856 8311285564
857 8350304825
858 8389415465
859 8428709290
860 8468094922
861 8507664596
862 8547326506
863 8587173317
864 8627112794
865 8667238033
866 8707456369
867 8747861330
868 8788359820
869 8829045800
870 8869825742
871 8910794041
872 8951856736
873 8993108657
874 9034455409
875 9075992258
876 9117624374
877 9159447460
878 9201366250
879 9243476885
880 9285683662
881 9328083161
882 9370579241
883 9413268922
884 9456055624
885 9499036808
886 9542115454
887 9585389465
888 9628761380
889 9672329545
890 9715996057
891 9759859706
892 9803822146
893 9847982612
894 9892242314
895 9936700933
896 9981259234
897 10026017345
898 10070875585
899 10115934530
900 10161094052
901 10206455176
902 10251917326
903 10297581977
904 10343348104
905 10389317633
906 10435389089
907 10481664850
908 10528042990
909 10574626340
910 10621312522
911 10668204821
912 10715200406
913 10762403017
914 10809709369
915 10857223658
916 10904842144
917 10952669480
918 11000601470
919 11048743225
920 11096990092
921 11145447641
922 11194010761
923 11242785482
924 11291666234
925 11340759508
926 11389959274
927 11439372485
928 11488892650
929 11538627185
930 11588469137
931 11638526386
932 11688691516
933 11739072872
934 11789562574
935 11840269433
936 11891085104
937 11942118865
938 11993261905
939 12044623970
940 12096095782
941 12147787556
942 12199589546
943 12251612437
944 12303746014
945 12356101433
946 12408568009
947 12461257370
948 12514058360
949 12567083080
950 12620219902
951 12673581401
952 12727055476
953 12780755177
954 12834567929
955 12888607258
956 12942760114
957 12997140500
958 13051634890
959 13106357765
960 13161195122
961 13216261921
962 13271443681
963 13326855842
964 13382383444
965 13438142408
966 13494017294
967 13550124505
968 13606348120
969 13662805025
970 13719378817
971 13776186866
972 13833112286
973 13890272932
974 13947551434
975 14005066133
976 14062699174
977 14120569385
978 14178558425
979 14236785610
980 14295132112
981 14353717736
982 14412423166
983 14471368697
984 14530434524
985 14589741433
986 14649169129
987 14708838890
988 14768629930
989 14828664020
990 14888819882
991 14949219781
992 15009741946
993 15070509137
994 15131399089
995 15192535058
996 15253794284
997 15315300520
998 15376930510
999 15438808505
1000 15500810752