-1 1
0 0
1 1
2 1
3 1
4 0
5 3
6 2
7 2
8 2
9 2
10 2
11 5
12 3
13 6
14 5
15 7
16 5
17 10
18 7
19 11
20 11
21 13
22 12
23 19
24 15
25 21
26 22
27 26
28 23
29 35
30 30
31 39
32 38
33 47
34 45
35 60
36 54
37 68
38 69
39 81
40 78
41 104
42 95
43 117
44 118
45 137
46 134
47 171
48 162
49 192
50 197
51 225
52 223
53 274
54 265
55 313
56 318
57 363
58 363
59 434
60 424
61 494
62 508
63 570
64 575
65 675
66 670
67 765
68 789
69 884
70 895
71 1035
72 1034
73 1171
74 1208
75 1344
76 1371
77 1561
78 1576
79 1764
80 1824
81 2014
82 2065
83 2331
84 2359
85 2628
86 2721
87 2988
88 3066
89 3434
90 3500
91 3861
92 4005
93 4377
94 4509
95 5002
96 5117
97 5623
98 5833
99 6351
100 6551
101 7221
102 7408
103 8097
104 8413
105 9118
106 9430
107 10327
108 10623
109 11554
110 12018
111 12987
112 13437
113 14650
114 15102
115 16357
116 17012
117 18331
118 19003
119 20609
120 21286
121 22971
122 23908
123 25677
124 26639
125 28795
126 29773
127 32031
128 33340
129 35718
130 37080
131 39938
132 41352
133 44346
134 46181
135 49349
136 51262
137 55030
138 57038
139 61020
140 63534
141 67761
142 70417
143 75377
144 78170
145 83436
146 86903
147 92473
148 96138
149 102646
150 106525
151 113432
152 118147
153 125513
154 130505
155 139025
156 144334
157 153396
158 159759
159 169430
160 176214
161 187305
162 194546
163 206369
164 214919
165 227557
166 236703
167 251140
168 260885
169 276299
170 287718
171 304186
172 316401
173 335126
174 348226
175 368190
176 383369
177 404757
178 421029
179 445195
180 462649
181 488516
182 508556
183 536259
184 557772
185 588928
186 612041
187 645396
188 671786
189 707507
190 735868
191 775886
192 806348
193 849225
194 883802
195 929790
196 966908
197 1018232
198 1058176
199 1113157
200 1158210
201 1217222
202 1265703
203 1331258
204 1383412
205 1453722
206 1512263
207 1587709
208 1650691
209 1734343
210 1802085
211 1891785
212 1967501
213 2063770
214 2145253
215 2251657
216 2339368
217 2453445
218 2551098
219 2673557
220 2778612
221 2913605
222 3026708
223 3171528
224 3296906
225 3452372
226 3587322
227 3758214
228 3903445
229 4086816
230 4247425
231 4444161
232 4616953
233 4832800
234 5018739
235 5250285
236 5455270
237 5703818
238 5924265
239 6196319
240 6433508
241 6725328
242 6986123
243 7299292
244 7579788
245 7921844
246 8223570
247 8590455
248 8921335
249 9315000
250 9670804
251 10100107
252 10482585
253 10942983
254 11361589
255 11855400
256 12305325
257 12842973
258 13326664
259 13902972
260 14431182
261 15049286
262 15616837
263 16288668
264 16898524
265 17618730
266 18283383
267 19055518
268 19769438
269 20607446
270 21374308
271 22272373
272 23106805
273 24069257
274 24965205
275 26008363
276 26970267
277 28087883
278 29132880
279 30330406
280 31451787
281 32748055
282 33951636
283 35339901
284 36645369
285 38132471
286 39533066
287 41140593
288 42643096
289 44364340
290 45991750
291 47834800
292 49579965
293 51570300
294 53441525
295 55571829
296 57595983
297 59876236
298 62045940
299 64505682
300 66831270
301 69462972
302 71975519
303 74791515
304 77483421
305 80517974
306 83402052
307 86647846
308 89759880
309 93231707
310 96564639
311 100302130
312 103871257
313 107867581
314 111714992
315 115987715
316 120106242
317 124701916
318 129110349
319 134022354
320 138769497
321 144019705
322 149098960
323 154740884
324 160175298
325 166203367
326 172049634
327 178490213
328 184743000
329 191658161
330 198345190
331 205730982
332 212917958
333 220806202
334 228489615
335 236952703
336 245165660
337 254201376
338 263020923
339 272667434
340 282091861
341 292433606
342 302503666
343 313540585
344 324345163
345 336123994
346 347664600
347 360282953
348 372608604
349 386070761
350 399284733
351 413646118
352 427754243
353 443128514
354 458189838
355 474585939
356 490720899
357 508205315
358 525424733
359 544129926
360 562504593
361 582445594
362 602115946
363 623372953
364 644355942
365 667082575
366 689464204
367 713683025
368 737626019
369 763433597
370 788964427
371 816538627
372 843759490
373 873133749
374 902234254
375 933523482
376 964540800
377 997952891
378 1031009405
379 1066589241
380 1101905975
381 1139791255
382 1177418910
383 1217851257
384 1257936796
385 1300976273
386 1343776425
387 1389587995
388 1435169996
389 1484034554
390 1532574543
391 1584571716
392 1636367558
393 1691693588
394 1746834546
395 1805815724
396 1864511233
397 1927251222
398 1989849243
399 2056580888
400 2123195076
401 2194299281
402 2265179775
403 2340788044
404 2416339523
405 2496730519
406 2577097659
407 2662712991
408 2748194306
409 2839200786
410 2930267115
411 3026995853
412 3123830500
413 3226794921
414 3329752360
415 3439162396
416 3548790105
417 3665038870
418 3781566930
419 3905252435
420 4029100880
421 4160483757
422 4292291403
423 4431837535
424 4571889166
425 4720294964
426 4869091004
427 5026677603
428 5184959661
429 5352281167
430 5520401644
431 5698266826
432 5876818701
433 6065624893
434 6255470893
435 6455872174
436 6657446190
437 6870383774
438 7084388031
439 7310348232
440 7537787461
441 7777543671
442 8018947683
443 8273595498
444 8529794560
445 8799926775
446 9072090713
447 9358622370
448 9647394918
449 9951599107
450 10257964010
451 10580560093
452 10905876646
453 11247946018
454 11592997944
455 11956019123
456 12321965666
457 12706811934
458 13095234835
459 13503180089
460 13915026676
461 14347792542
462 14784430104
463 15243067569
464 15706336716
465 16192347750
466 16683390350
467 17198775882
468 17719204760
469 18265228753
470 18817182869
471 19395615084
472 19980466341
473 20593631985
474 21213280733
475 21862697907
476 22519628574
477 23207377817
478 23903238438
479 24632020707
480 25369044968
481 26140678659
482 26921757344
483 27738685492
484 28565786571
485 29431150316
486 30306900280
487 31222868797
488 32150626123
489 33120072025
490 34102184844
491 35128753004
492 36168307434
493 37254583586
494 38355480771
495 39504835115
496 40669873271
497 41886537505
498 43119336246
499 44406387093
500 45711476030
501 47072864349
502 48453570871
503 49894211092
504 51354776087
505 52878318347
506 54424004945
507 56035076284
508 57669829269
509 59374134995
510 61102926670
511 62904788572
512 64733723599
513 66638562194
514 68572313630
515 70586745358
516 72631132458
517 74760274374
518 76922379927
519 79172567217
520 81457918476
521 83836826460
522 86252228898
523 88765900371
524 91319572049
525 93975410057
526 96673873722
527 99480780025
528 102331987342
529 105297087346
530 108310569773
531 111442511431
532 114625953983
533 117935052932
534 121297746338
535 124792391703
536 128345380979
537 132035666674
538 135788003607
539 139685878297
540 143648398018
541 147763732902
542 151949235387
543 156293796874
544 160712921673
545 165300555981
546 169965935555
547 174808229720
548 179734693375
549 184845359474
550 190045397392
551 195440466859
552 200928800244
553 206621863287
554 212415659961
555 218422685898
556 224536589502
557 230876132882
558 237327285345
559 244015271851
560 250823539110
561 257878546833
562 265061086110
563 272504580604
564 280081330734
565 287931952053
566 295925905056
567 304205249701
568 312636469553
569 321369370955
570 330261040750
571 339469283448
572 348847992865
573 358556679208
574 368445873126
575 378683704860
576 389110321244
577 399902738768
578 410897515745
579 422273666305
580 433863976275
581 445857026619
582 458074141040
583 470713772344
584 483593209090
585 496913242748
586 510486925866
587 524525678968
588 538829884386
589 553621942620
590 568697705793
591 584282287102
592 600166794194
593 616588146191
594 633323467552
595 650621850487
596 668255356366
597 686476229127
598 705051203730
599 724245630048
600 743810819141
601 764025640221
602 784635712581
603 805923566064
604 827628859654
605 850048660462
606 872905619805
607 896511803646
608 920583500807
609 945436989040
610 970781902508
611 996950641884
612 1023634087748
613 1051181284852
614 1079275996900
615 1108272124905
616 1137845977830
617 1168369354595
618 1199497898372
619 1231621851132
620 1264388911951
621 1298194911391
622 1332679225957
623 1368257502648
624 1404546378442
625 1441981947549
626 1480171964638
627 1519558939457
628 1559741344112
629 1601183658472
630 1643459295904
631 1687055409517
632 1731535507836
633 1777394086209
634 1824184305390
635 1872424997744
636 1921641759552
637 1972378520241
638 2024149852055
639 2077508078181
640 2131956234321
641 2188073606160
642 2245332908723
643 2304341225163
644 2364558970099
645 2426602836209
646 2489920391479
647 2555158164585
648 2621730397991
649 2690314400809
650 2760310729703
651 2832407618598
652 2905991359821
653 2981783215536
654 3059132837509
655 3138795557964
656 3220105814801
657 3303831391452
658 3389290836687
659 3477288500276
660 3567102685910
661 3659575431996
662 3753968138909
663 3851136999665
664 3950325778461
665 4052431092802
666 4156652537748
667 4263928416816
668 4373439545600
669 4486140313445
670 4601191958103
671 4719593579969
672 4840457910329
673 4964830181146
674 5091802282156
675 5222437669675
676 5355806532220
677 5493021766503
678 5633100349306
679 5777206140126
680 5924333041506
681 6075665565971
682 6230173542575
683 6389096135050
684 6551344826122
685 6718215124693
686 6888592905676
687 7063797077110
688 7242686857956
689 7426641536561
690 7614456378804
691 7807572931674
692 8004758125750
693 8207479928523
694 8414475796895
695 8627280399885
696 8844561108337
697 9067921386351
698 9295997252375
699 9530422017881
700 9769799069119
701 10015835430881
702 10267057723850
703 10525248929149
704 10788901021835
705 11059830671790
706 11336493796611
707 11620788413321
708 11911086443122
709 12209369782030
710 12513972048099
711 12826913122048
712 13146486809947
713 13474802819661
714 13810062987226
715 14154469651983
716 14506182371062
717 14867446255147
718 15236376930186
719 15615318648507
720 16002286458088
721 16399726807103
722 16805608135971
723 17222425026013
724 17648097452736
725 18085229419476
726 18531630931156
727 18990018769227
728 19458151510961
729 19938800121874
730 20429669762096
731 20933652085131
732 21448332088521
733 21976725857283
734 22516361741628
735 23070316652779
736 23636060169180
737 24216802333474
738 24809881424810
739 25418644739730
740 26040368207520
741 26678467456739
742 27330153670248
743 27998989336405
744 28682042279740
745 29383026329684
746 30098940726777
747 30833575976504
748 31583860142636
749 32353745602004
750 33140003997394
751 33946754560644
752 34770693518201
753 35616026113895
754 36479370349444
755 37365109922196
756 38269692129268
757 39197684666860
758 40145451976982
759 41117658108489
760 42110581626216
761 43129083278578
762 44169255495130
763 45236161737088
764 46325803550426
765 47443352324615
766 48584715321668
767 49755280694649
768 50950752840280
769 52176743323320
770 53428856759200
771 54712825575567
772 56024151007945
773 57368804282839
774 58742065631059
775 60150152417234
776 61588235529440
777 63062667472940
778 64568505908358
779 66112366387707
780 67689065880479
781 69305491107201
782 70956339261641
783 72648648177333
784 74376990989341
785 76148695334189
786 77958072357518
787 79812748303872
788 81706903251655
789 83648332330147
790 85631079885900
791 87663260083406
792 89738632331060
793 91865639636632
794 94037898000452
795 96264039069346
796 98537530453905
797 100867355115905
798 103246670714211
799 105684822345973
800 108174810951990
801 110726192185414
802 113331804872829
803 116001591416438
804 118728053804280
805 121521533015913
806 124374359962283
807 127297110553444
808 130281938680682
809 133339845996286
810 136462620462484
811 139661702467292
812 142928693194080
813 146275295154389
814 149692916410275
815 153193727965084
816 156768740598388
817 160430608188253
818 164170137871335
819 168000275611926
820 171911618148651
821 175917626999119
822 180008467685607
823 184198133096904
824 188476566906460
825 192858087531792
826 197332409353563
827 201914418122577
828 206593360506098
829 211384706862347
830 216277462362524
831 221287459945748
832 226403455301871
833 231641905401352
834 236991058973980
835 242468016115994
836 248060762833135
837 253786802967558
838 259633851237235
839 265620097938839
840 271732708372230
841 277990580397936
842 284380593770862
843 290922095622400
844 297601671020174
845 304439422131185
846 311421339066446
847 318568302055336
848 325865991284663
849 333335786837060
850 340963048930242
851 348769988007321
852 356741320383494
853 364900112232002
854 373230743461804
855 381756836255554
856 390462423526861
857 399372040490650
858 408469023575039
859 417778848961836
860 427284488509311
861 437012036396074
862 446944088610153
863 457107743198510
864 467484843156071
865 478103521190806
866 488945225494559
867 500038775616678
868 511365212716056
869 522954460157572
870 534786745546058
871 546893129648383
872 559253413015307
873 571899419517174
874 584810509538598
875 598019720166558
876 611505533537954
877 625302237106014
878 639387851351029
879 653797511269368
880 668508761826567
881 683558071658645
882 698922037853329
883 714638503576651
884 730683567509265
885 747096013762598
886 763851427835445
887 780990059625342
888 798486472580412
889 816382427172013
890 834651949452010
891 853337844267269
892 872413584339360
893 891923585498935
894 911840219084816
895 932209561098528
896 953003403749865
897 974268982105962
898 995977492473978
899 1018177940134726
900 1040840335445569
901 1064015508129443
902 1087672845391013
903 1111864462461845
904 1136559105782688
905 1161810835793977
906 1187587122627238
907 1213944031522882
908 1240848362901078
909 1268357607734795
910 1296437877789308
911 1325148801519824
912 1354455118337028
913 1384418659419441
914 1415003445318412
915 1446272887918271
916 1478190268965818
917 1510821348548647
918 1544127934067958
919 1578178205697450
920 1612933200125268
921 1648462849711199
922 1684727399473185
923 1721799361585732
924 1759637398003482
925 1798316679915373
926 1837795044175960
927 1878149603496794
928 1919337347723506
929 1961438223669514
930 2004407523085152
931 2048328113553897
932 2093154405088029
933 2138971416287290
934 2185732652022510
935 2233526244148291
936 2282303877636068
937 2332156892916944
938 2383036033549248
939 2435035022685445
940 2488103638352493
941 2542339023288255
942 2597689006827498
943 2654254256111052
944 2711981597459823
945 2770974336302502
946 2831178270904101
947 2892700462641190
948 2955484625007553
949 3019641690645132
950 3085114306117447
951 3152016325045882
952 3220289300796122
953 3290051212544654
954 3361241385591748
955 3433982050860866
956 3508211400991766
957 3584054900181971
958 3661449581162178
959 3740525438738999
960 3821217127275364
961 3903659311265853
962 3987785444706204
963 4073733770284138
964 4161436513819798
965 4251036893804957
966 4342464599278018
967 4435867977443478
968 4531175448216495
969 4628539317746199
970 4727886708329407
971 4829375390466998
972 4932929784398926
973 5038713292662630
974 5146648997025309
975 5256904679487969
976 5369402053914369
977 5484314903135755
978 5601562066234977
979 5721323511023080
980 5843516667911073
981 5968326348883509
982 6095668546186249
983 6225734661177254
984 6358437631672638
985 6493975651028166
986 6632260179029345
987 6773494765347739
988 6917589362467923
989 7064754755815523
990 7214897656601641
991 7368236308599653
992 7524675876929792
993 7684440527635579
994 7847433850101465
995 8013887955956618
996 8183703000367784
997 8357119284610322
998 8534035351970444
999 8714698050392361
1000 8899004282260122