-1 1
0 0
1 0
2 1
3 1
4 1
5 2
6 1
7 2
8 2
9 2
10 2
11 4
12 3
13 4
14 5
15 5
16 5
17 8
18 7
19 8
20 10
21 10
22 11
23 15
24 14
25 16
26 19
27 20
28 21
29 27
30 26
31 30
32 35
33 36
34 39
35 47
36 47
37 52
38 60
39 63
40 68
41 80
42 81
43 90
44 101
45 106
46 114
47 132
48 135
49 148
50 165
51 174
52 187
53 212
54 219
55 239
56 264
57 279
58 299
59 334
60 348
61 377
62 414
63 438
64 468
65 518
66 541
67 585
68 637
69 674
70 720
71 790
72 828
73 891
74 966
75 1022
76 1090
77 1188
78 1247
79 1338
80 1444
81 1527
82 1626
83 1763
84 1853
85 1982
86 2132
87 2254
88 2396
89 2586
90 2720
91 2902
92 3112
93 3287
94 3491
95 3752
96 3947
97 4203
98 4494
99 4745
100 5031
101 5390
102 5671
103 6027
104 6428
105 6782
106 7182
107 7672
108 8071
109 8562
110 9112
111 9608
112 10163
113 10827
114 11388
115 12063
116 12811
117 13498
118 14262
119 15161
120 15940
121 16860
122 17874
123 18820
124 19862
125 21071
126 22145
127 23393
128 24759
129 26050
130 27466
131 29085
132 30553
133 32234
134 34067
135 35818
136 37726
137 39886
138 41878
139 44133
140 46578
141 48937
142 51498
143 54366
144 57051
145 60057
146 63306
147 66469
148 69884
149 73676
150 77273
151 81265
152 85562
153 89774
154 94307
155 99303
156 104093
157 109369
158 115028
159 120613
160 126600
161 133155
162 139501
163 146443
164 153866
165 161232
166 169106
167 177677
168 186040
169 195136
170 204836
171 214509
172 224818
173 235983
174 246955
175 258827
176 271455
177 284101
178 297545
179 312039
180 326368
181 341804
182 358185
183 374651
184 392114
185 410865
186 429504
187 449502
188 470677
189 492031
190 514632
191 538814
192 562962
193 588776
194 616060
195 643653
196 672800
197 703885
198 735053
199 768267
200 803308
201 838834
202 876299
203 916136
204 956221
205 998817
206 1043684
207 1089272
208 1137267
209 1188171
210 1239552
211 1294010
212 1351286
213 1409593
214 1470892
215 1535753
216 1601396
217 1670813
218 1743721
219 1818067
220 1896120
221 1978535
222 2062142
223 2150373
224 2242921
225 2337433
226 2436535
227 2540978
228 2647146
229 2758977
230 2876144
231 2995952
232 3121430
233 3253439
234 3387877
235 3529242
236 3677190
237 3828643
238 3987095
239 4153533
240 4323294
241 4501531
242 4687880
243 4878830
244 5078404
245 5287734
246 5501542
247 5725708
248 5959850
249 6199980
250 6450726
251 6713382
252 6981977
253 7263219
254 7556726
255 7857960
256 8172237
257 8501045
258 8837642
259 9189673
260 9556750
261 9933731
262 10326723
263 10737431
264 11158246
265 11597878
266 12055952
267 12526646
268 13016959
269 13528846
270 14053752
271 14601580
272 15171977
273 15758365
274 16368766
275 17005423
276 17658716
277 18339909
278 19048685
279 19777632
280 20535918
281 21326133
282 22137481
283 22982753
284 23861688
285 24765948
286 25706023
287 26684882
288 27690429
289 28737187
290 29824982
291 30944447
292 32107564
293 33317747
294 34561474
295 35855217
296 37198910
297 38582065
298 40018350
299 41511708
300 43047027
301 44642986
302 46299680
303 48005366
304 49775640
305 51615039
306 53506727
307 55471863
308 57510741
309 59610254
310 61788184
311 64049761
312 66376244
313 68791593
314 71296374
315 73875978
316 76550656
317 79326455
318 82182550
319 85146058
320 88217878
321 91381777
322 94660810
323 98061953
324 101562115
325 105191969
326 108952858
327 112826753
328 116839892
329 121000343
330 125282546
331 129721186
332 134318134
333 139053439
334 143956944
335 149037985
336 154268307
337 159687128
338 165296986
339 171075845
340 177057626
341 183253141
342 189631236
343 196236218
344 203071456
345 210112663
346 217398400
347 224941188
348 232706721
349 240745071
350 249060627
351 257626682
352 266487039
353 275656223
354 285096554
355 294864586
356 304965935
357 315371339
358 326130546
359 337260401
360 348719598
361 360572004
362 372824767
363 385445870
364 398491805
365 411982125
366 425871670
367 440232545
368 455073722
369 470360315
370 486156456
371 502484848
372 519296218
373 536671973
374 554623317
375 573112332
376 592211804
377 611948113
378 632267653
379 653262322
380 674945988
381 697277595
382 720339760
383 744163122
384 768689527
385 794022699
386 820179742
387 847116355
388 874926270
389 903645131
390 933210022
391 963738032
392 995250100
393 1027698642
394 1061190024
395 1095765685
396 1131357783
397 1168098491
398 1206013371
399 1245051522
400 1285333615
401 1326907866
402 1369701399
403 1413863400
404 1459424925
405 1506331827
406 1554721015
407 1604648595
408 1656036562
409 1709053339
410 1763736540
411 1820028882
412 1878085688
413 1937972254
414 1999605474
415 2063175496
416 2128727709
417 2196201926
418 2265774380
419 2337521060
420 2411353846
421 2487487443
422 2565976486
423 2646758204
424 2730032552
425 2815887989
426 2904231606
427 2995305866
428 3089176318
429 3185778119
430 3285338172
431 3387959432
432 3493544547
433 3602367378
434 3714506426
435 3829895390
436 3948791769
437 4071315415
438 4197365074
439 4327250128
440 4461064322
441 4598740811
442 4740571863
443 4886696947
444 5037011676
445 5191865632
446 5351370559
447 5515460183
448 5684466232
449 5858551049
450 6037608125
451 6222032549
452 6411957233
453 6607317920
454 6808491230
455 7015666053
456 7228735098
457 7448145007
458 7674053580
459 7906400398
460 8145613064
461 8391911365
462 8645188963
463 8905950879
464 9174384119
465 9450434374
466 9734587256
467 10027098397
468 10327864581
469 10637457021
470 10956097000
471 11283739077
472 11620934784
473 11967981431
474 12324781682
475 12691981756
476 13069843051
477 13458332426
478 13858076432
479 14269420725
480 14692277200
481 15127377164
482 15575028989
483 16035215931
484 16508649872
485 16995732585
486 17496389381
487 18011448055
488 18541271842
489 19085865447
490 19646037858
491 20222255909
492 20814463362
493 21423597512
494 22050085696
495 22693960057
496 23356140060
497 24037168008
498 24737012246
499 25456734350
500 26196836380
501 26957385143
502 27739425927
503 28543588406
504 29369872892
505 30219482070
506 31093005114
507 31990552086
508 32913311438
509 33862014110
510 34836701240
511 35838735744
512 36868808162
513 37927082070
514 39014908994
515 40133137043
516 41281858714
517 42462618964
518 43676226270
519 44922909833
520 46204206828
521 47521100968
522 48873748717
523 50263901809
524 51692505783
525 53159869790
526 54667742500
527 56217264399
528 57808670787
529 59443948440
530 61124202014
531 62849837551
532 64622844538
533 66444544706
534 68315269865
535 70237273867
536 72211845984
537 74239509026
538 76322526851
539 78462430527
540 80659669124
541 82916800139
542 85235326906
543 87615912293
544 90061132677
545 92572760866
546 95151387677
547 97799915816
548 100520096478
549 103312760012
550 106180838833
551 109126384700
552 112150158822
553 115255456470
554 118444315791
555 121717766509
556 125079146633
557 128530829703
558 132073780960
559 135711742053
560 139447082992
561 143281070203
562 147217503808
563 151259128264
564 155407152069
565 159665824613
566 164037899448
567 168524923151
568 173131222226
569 177859968616
570 182712659880
571 187694122879
572 192807554089
573 198054830806
574 203440879286
575 208969363690
576 214642123978
577 220464643888
578 226440631120
579 232572352380
580 238865417070
581 245324056006
582 251950513616
583 258751020765
584 265729874710
585 272889799730
586 280237183473
587 287776908642
588 295511696022
589 303448626486
590 311592676784
591 319947107639
592 328519193118
593 337314565507
594 346336505573
595 355593060945
596 365089990996
597 374831184224
598 384824924338
599 395077705092
600 405593463796
601 416381347876
602 427448017536
603 438798094518
604 450441012316
605 462384254321
606 474632526199
607 487196226288
608 500083050954
609 513298477057
610 526853247440
611 540755981646
612 555012282741
613 569633971882
614 584629936706
615 600006649553
616 615776344034
617 631948943500
618 648531097432
619 665536245158
620 682974642814
621 700853920131
622 719188007891
623 737988324845
624 757262738421
625 777026528243
626 797291521835
627 818066692461
628 839367902662
629 861208285566
630 883597124212
631 906551790778
632 930085915922
633 954210030562
634 978942195877
635 1004297509242
636 1030286896512
637 1056930109151
638 1084242845753
639 1112237440827
640 1140934457258
641 1170351242082
642 1200500625108
643 1231405062617
644 1263082623424
645 1295547727928
646 1328823785244
647 1362930717525
648 1397883558190
649 1433707838137
650 1470424341471
651 1508049898057
652 1546611154508
653 1586130979242
654 1626626953213
655 1668128101576
656 1710658317122
657 1754237210165
658 1798895109167
659 1844658251858
660 1891547160548
661 1939594831139
662 1988828713756
663 2039271623693
664 2090958075672
665 2143918158658
666 2198175787574
667 2253768469518
668 2310727722992
669 2369080054169
670 2428864736576
671 2490116259117
672 2552862445405
673 2617145927004
674 2683002872980
675 2750464035619
676 2819574096834
677 2890372570104
678 2962891777891
679 3037180171624
680 3113279233390
681 3191224596200
682 3271067087212
683 3352851954902
684 3436616694762
685 3522416366571
686 3610298519463
687 3700304391345
688 3792491790082
689 3886912507225
690 3983609981036
691 4082646773274
692 4184077357364
693 4287949402511
694 4394328644582
695 4503274336454
696 4614836737178
697 4729086923263
698 4846087267064
699 4965892811112
700 5088578292571
701 5214211469084
702 5342850421777
703 5474575888935
704 5609459249046
705 5747563991480
706 5888975070900
707 6033769934461
708 6182015625946
709 6333803844657
710 6489216232828
711 6648325948828
712 6811229542050
713 6978015494228
714 7148761110763
715 7323570522652
716 7502537063260
717 7685744951037
718 7873303889612
719 8065314921246
720 8261867090898
721 8463078626032
722 8669056170965
723 8879896586046
724 9095724494171
725 9316655228971
726 9542791256032
727 9774266782713
728 10011203601080
729 10253713011793
730 10501936554268
731 10756005815613
732 11016038592488
733 11282187202632
734 11554590668684
735 11833376774261
736 12118706234360
737 12410729113192
738 12709580708926
739 13015433858760
740 13328447175608
741 13648767245712
742 13976576514380
743 14312046041479
744 14655331090712
745 15006627742083
746 15366116872044
747 15733966501558
748 16110383693897
749 16495563356652
750 16889683515174
751 17292966569705
752 17705618686687
753 18127832307432
754 18559842376785
755 19001870877671
756 19454121768117
757 19916847245420
758 20390282191532
759 20874646852541
760 21370207741440
761 21877217568473
762 22395909818918
763 22926570413634
764 23469466825056
765 24024850939093
766 24593025000640
767 25174276577013
768 25768872753071
769 26377137606504
770 26999375582540
771 27635874549914
772 28286977185930
773 28953010583767
774 29634280039710
775 30331152791673
776 31043975211138
777 31773076066052
778 32518843771477
779 33281650222195
780 34061844145360
781 34859841584870
782 35676036435810
783 36510803927657
784 37364584198808
785 38237799905289
786 39130849110247
787 40044203031421
788 40978309409402
789 41933596226056
790 42910562094464
791 43909687160871
792 44931425501674
793 45976310689040
794 47044851447336
795 48137535621503
796 49254927911367
797 50397573549147
798 51565990171488
799 52760781799242
800 53982526196443
801 55231779105877
802 56509179894546
803 57815347450500
804 59150871496763
805 60516435624316
806 61912695726034
807 63340284516468
808 64799925698034
809 66292321480829
810 67818143302562
811 69378164599822
812 70973129644455
813 72603758366631
814 74270869695446
815 75975260060989
816 77717693483337
817 79499044817129
818 81320158269002
819 83181852543913
820 85085054061604
821 87030665755442
822 89019556489758
823 91052715565497
824 93131100146596
825 95255640750996
826 97427385095834
827 99647356455971
828 101916542368672
829 104236061244704
830 106606997875804
831 109030409292895
832 111507480047806
833 114039369342759
834 116627198977685
835 119272232971131
836 121975700262978
837 124738800964778
838 127562873943264
839 130449231875024
840 133399148389646
841 136414051670545
842 139495333403462
843 142644355444590
844 145862630634880
845 149151644873737
846 152512843408693
847 155947839453795
848 159458208368560
849 163045494772159
850 166711407583609
851 170457628142980
852 174285795596096
853 178197731643044
854 182195218859822
855 186280008288270
856 190454029768958
857 194719185070899
858 199077332315649
859 203530528046825
860 208080788530994
861 212730097856044
862 217480634699516
863 222334549352520
864 227293947126617
865 232361149019106
866 237538434748480
867 242828051394758
868 248232457828592
869 253754084437881
870 259395315455966
871 265158769587419
872 271047023446684
873 277062620777875
874 283208335856172
875 289486914640501
876 295901055959940
877 302453713560923
878 309147798524687
879 315986189106105
880 322972014512114
881 330108376115980
882 337398327434500
883 344845199158669
884 352452279028713
885 360222822333953
886 368160357573157
887 376268386268530
888 384550361664118
889 393010038412518
890 401651128279364
891 410477311349950
892 419492565181955
893 428700841657524
894 438106044328678
895 447712404547884
896 457524111263503
897 467545322982634
898 477780522139671
899 488234167315050
900 498910669151047
901 509814794839309
902 520951270148602
903 532324792195902
904 543940410876630
905 555803154663657
906 567918005012544
907 580290331250430
908 592925462851726
909 605828703074768
910 619005739426892
911 632462241134076
912 646203831951192
913 660236557639804
914 674566426370733
915 689199423286933
916 704141952115982
917 719400402269814
918 734981119971515
919 750890910658656
920 767136545249260
921 783724775697141
922 800662810010434
923 817957846800144
924 835617044632289
925 853648061854965
926 872058526310275
927 890856051952544
928 910048749689025
929 929644727049062
930 949652055664422
931 970079351189408
932 990935203879066
933 1012228196347317
934 1033967452812880
935 1056162101400042
936 1078821239648522
937 1101954557379257
938 1125571725384487
939 1149682414408134
940 1174296885559152
941 1199425412588212
942 1225078245322842
943 1251266278524642
944 1278000395754594
945 1305291489665048
946 1333151096532366
947 1361590775672854
948 1390622070695956
949 1420257227608517
950 1450508490719832
951 1481388124341597
952 1512909094595532
953 1545084402942166
954 1577927045140348
955 1611450782072857
956 1645669384349702
957 1680596655520500
958 1716247164528576
959 1752635530121738
960 1789776377403096
961 1827685165090447
962 1866377375252182
963 1905868538144625
964 1946175018915757
965 1987313249452160
966 2029299682402010
967 2072151678829262
968 2115886639282766
969 2160522030381864
970 2206076229617028
971 2252567700956792
972 2300014946220597
973 2348437457358445
974 2397854784801928
975 2448286565929269
976 2499753432074978
977 2552276123976773
978 2605875440371784
979 2660573259415612
980 2716391539998532
981 2773352352235226
982 2831478851072252
983 2890794327394375
984 2951322153716000
985 3013086879558041
986 3076113161129133
987 3140425793995063
988 3206050757972686
989 3273014199440583
990 3341342373993082
991 3411062820915226
992 3482203216329688
993 3554791408215877
994 3628856537594870
995 3704427947294532
996 3781535121432386
997 3860208944474661
998 3940480472629041
999 4022380971397051
1000 4105943118393422