-1 1
0 0
1 1
2 0
3 2
4 2
5 2
6 2
7 3
8 2
9 4
10 4
11 7
12 4
13 10
14 8
15 11
16 10
17 14
18 14
19 21
20 18
21 25
22 22
23 33
24 32
25 41
26 38
27 52
28 50
29 65
30 62
31 82
32 78
33 101
34 102
35 124
36 122
37 150
38 152
39 189
40 186
41 230
42 226
43 279
44 280
45 334
46 340
47 402
48 412
49 487
50 492
51 582
52 592
53 697
54 714
55 831
56 850
57 980
58 1014
59 1173
60 1204
61 1383
62 1424
63 1634
64 1690
65 1917
66 1990
67 2256
68 2340
69 2654
70 2748
71 3101
72 3214
73 3626
74 3776
75 4223
76 4404
77 4910
78 5126
79 5721
80 5962
81 6636
82 6916
83 7696
84 8036
85 8887
86 9292
87 10264
88 10748
89 11852
90 12398
91 13650
92 14272
93 15699
94 16454
95 18034
96 18892
97 20686
98 21688
99 23720
100 24854
101 27142
102 28450
103 31036
104 32564
105 35422
106 37172
107 40397
108 42416
109 46063
110 48322
111 52425
112 55002
113 59599
114 62580
115 67695
116 71084
117 76795
118 80684
119 87106
120 91448
121 98639
122 103576
123 111639
124 117256
125 126198
126 132550
127 142529
128 149734
129 160908
130 168994
131 181437
132 190552
133 204439
134 214744
135 230140
136 241752
137 258885
138 271948
139 291089
140 305666
141 326908
142 343296
143 366952
144 385386
145 411527
146 432192
147 461213
148 484356
149 516622
150 542426
151 578222
152 607012
153 646739
154 678982
155 722827
156 758808
157 807378
158 847554
159 901365
160 946014
161 1005511
162 1055192
163 1121074
164 1176460
165 1249088
166 1310652
167 1390922
168 1459360
169 1548050
170 1623914
171 1721823
172 1806016
173 1914038
174 2007562
175 2126487
176 2230080
177 2361181
178 2476060
179 2620644
180 2747546
181 2906805
182 3047206
183 3222567
184 3378008
185 3570732
186 3742536
187 3954520
188 4144384
189 4377587
190 4586928
191 4843283
192 5074284
193 5356043
194 5610942
195 5920131
196 6201090
197 6540453
198 6850164
199 7222860
200 7563598
201 7972362
202 8347484
203 8795869
204 9208704
205 9699907
206 10153950
207 10692269
208 11191400
209 11781364
210 12329374
211 12975384
212 13577228
213 14284582
214 14945588
215 15719143
216 16444444
217 17290675
218 18086282
219 19012073
220 19883944
221 20896010
222 21851412
223 22957776
224 24004670
225 25212697
226 26359200
227 27678668
228 28933816
229 30374689
230 31747580
231 33320245
232 34821776
233 36538029
234 38180260
235 40051766
236 41846500
237 43887389
238 45848550
239 48073730
240 50215036
241 52640140
242 54978054
243 57620374
244 60172576
245 63049653
246 65834096
247 68967033
248 72004280
249 75415115
250 78725776
251 82437701
252 86046058
253 90084565
254 94016920
255 98408496
256 102691802
257 107466731
258 112131268
259 117322446
260 122398848
261 128040347
262 133564776
263 139694424
264 145704812
265 152361573
266 158898168
267 166126460
268 173233768
269 181081516
270 188805390
271 197322537
272 205715244
273 214956978
274 224074508
275 234098358
276 243999712
277 254870488
278 265620280
279 277407591
280 289073482
281 301849956
282 314508262
283 328354698
284 342086848
285 357086387
286 371978662
287 388225550
288 404371638
289 421966561
290 439465674
291 458514733
292 477476580
293 498095808
294 518638802
295 540949556
296 563198644
297 587336490
298 611428088
299 637537556
300 663614812
301 691849340
302 720070738
303 750597585
304 781133780
305 814128230
306 847159016
307 882815638
308 918537176
309 957062832
310 995682464
311 1037298112
312 1079043132
313 1123987249
314 1169102020
315 1217627108
316 1266369896
317 1318753262
318 1371405472
319 1427943756
320 1484801338
321 1545809330
322 1607198020
323 1673016105
324 1739284170
325 1810273286
326 1881790644
327 1958344346
328 2035511220
329 2118051054
330 2201290546
331 2290265295
332 2380040068
333 2475933009
334 2572737438
335 2676061492
336 2780421500
337 2891733868
338 3004217782
339 3124115984
340 3245325428
341 3374443077
342 3505032532
343 3644054341
344 3784722632
345 3934373930
346 4085866834
347 4246934739
348 4410052832
349 4583378719
350 4758973844
351 4945451978
352 5134446632
353 5335040593
354 5538420568
355 5754151917
356 5972966388
357 6204940845
358 6440317504
359 6689717168
360 6942854782
361 7210936474
362 7483128840
363 7771243452
364 8063874320
365 8373454490
366 8687997024
367 9020592088
368 9358626400
369 9715887130
370 10079093864
371 10462780009
372 10852967904
373 11264966506
374 11684070682
375 12126385844
376 12576462948
377 13051252891
378 13534510074
379 14044077137
380 14562859956
381 15109656221
382 15666487470
383 16253137826
384 16850709572
385 17480004862
386 18121181732
387 18796121651
388 19483973220
389 20207755274
390 20945541842
391 21721571181
392 22512794850
393 23344710990
394 24193108764
395 25084784277
396 25994330080
397 26949915377
398 27924861608
399 28948783924
400 29993648126
401 31090617675
402 32210246200
403 33385296899
404 34584851808
405 35843333007
406 37128310550
407 38475950960
408 39852221676
409 41295128038
410 42768931684
411 44313596628
412 45891612464
413 47544970226
414 49234312416
415 51003733481
416 52811972192
417 54705336754
418 56640549324
419 58666251755
420 60737023508
421 62903986535
422 65119497154
423 67437244232
424 69807265444
425 72285909201
426 74820833008
427 77471182479
428 80182087000
429 83015644214
430 85914306596
431 88943298454
432 92042286424
433 95279745379
434 98592439344
435 102052205521
436 105592826700
437 109289674197
438 113073373924
439 117023014779
440 121065887188
441 125285019226
442 129604229434
443 134110638180
444 138724446264
445 143537014440
446 148464817702
447 153603678562
448 158866132458
449 164352685194
450 169971723914
451 175828708208
452 181827700988
453 188079306997
454 194483100066
455 201155014389
456 207989988800
457 215109569029
458 222403801224
459 230000115307
460 237783399680
461 245887312647
462 254191376246
463 262835709178
464 271694259204
465 280913846331
466 290362666644
467 300194572858
468 310271706728
469 320755300664
470 331501113922
471 342678181055
472 354135620540
473 366050562863
474 378265225746
475 390965151452
476 403985428868
477 417520419959
478 431397729770
479 445820960747
480 460609834492
481 475977707440
482 491736116032
483 508108541602
484 524898003970
485 542338511320
486 560224292308
487 578800383101
488 597851769840
489 617635060754
490 637925528556
491 658991961858
492 680599552344
493 703029743814
494 726037242812
495 749916636782
496 774411819800
497 799831146904
498 825907153712
499 852962634475
500 880718189862
501 909511807525
502 939051698592
503 969691646234
504 1001126979902
505 1033727887715
506 1067176420060
507 1101859937046
508 1137446549312
509 1174341602352
510 1212198603862
511 1251441808926
512 1291709543926
513 1333445740553
514 1376272958056
515 1420655554800
516 1466199812448
517 1513391493611
518 1561819815824
519 1611992929501
520 1663482194956
521 1716819283810
522 1771557009328
523 1828251497660
524 1886436314004
525 1946692993561
526 2008535225068
527 2072571146658
528 2138293626672
529 2206338628931
530 2276177234196
531 2348474639357
532 2422679304276
533 2499486805674
534 2578322156304
535 2659912498907
536 2743658617160
537 2830320679771
538 2919274153420
539 3011313727142
540 3105788373440
541 3203529041489
542 3303857210704
543 3407641511269
544 3514174905324
545 3624365211897
546 3737475947734
547 3854455889782
548 3974537804164
549 4098713278929
550 4226182942246
551 4357983275747
552 4493281595384
553 4633161062960
554 4776754435312
555 4925193428121
556 5077575113788
557 5235081937493
558 5396773724904
559 5563885955079
560 5735439546394
561 5912725549468
562 6094724596710
563 6282785505772
564 6475847125016
565 6675318349616
566 6880094928438
567 7091648507466
568 7308829853088
569 7533176201175
570 7763491390284
571 8001381338308
572 8245601257304
573 8497828523681
574 8756767964372
575 9024171225315
576 9298691175722
577 9582157031683
578 9873167481966
579 10173632753576
580 10482095090588
581 10800549519705
582 11127479814330
583 11464969233448
584 11811440969924
585 12169070013274
586 12536217082466
587 12915152964842
588 13304173287172
589 13705648842747
590 14117807518092
591 14543124731173
592 14979758219364
593 15430292226709
594 15892811916322
595 16370014682419
596 16859910803372
597 17365315841772
598 17884162142924
599 18419388565017
600 18968846360744
601 19535603397406
602 20117427009468
603 20717519209481
604 21333560561224
605 21968892565161
606 22621106306084
607 23293688861320
608 23984138292412
609 24696093572954
610 25426956034440
611 26180523496975
612 26954097236908
613 27751640276248
614 28570350445334
615 29414362604751
616 30280767951068
617 31173880600377
618 32090681028862
619 33035670335033
620 34005713918888
621 35005508314545
622 36031800050444
623 37089488899136
624 38175198500672
625 39294040081994
626 40442510671922
627 41625942015495
628 42840699714408
629 44092345562960
630 45377108726326
631 46700791294571
632 48059481561332
633 49459231546572
634 50895984032400
635 52376050973033
636 53895225362184
637 55460090225797
638 57066283156466
639 58720669911653
640 60418726885606
641 62167615066621
642 63962644486772
643 65811283272060
644 67708669698048
645 69662591307414
646 71668009726812
647 73733045491882
648 75852477102330
649 78034772307180
650 80274519906182
651 82580550104499
652 84947255982784
653 87383844849985
654 89884507909598
655 92458844640090
656 95100838616796
657 97820498216603
658 100611592028198
659 103484554591479
660 106432932004552
661 109467603595496
662 112581886090744
663 115787121481900
664 119076390166284
665 122461515324038
666 125935334431116
667 129510172298457
668 133178615059936
669 136953510296546
670 140827184234264
671 144813029974500
672 148903106019116
673 153111372885035
674 157429613501952
675 161872378513150
676 166431167781374
677 171121146959905
678 175933523487548
679 180884103853226
680 185963793270976
681 191189066864141
682 196550518870520
683 202065319822507
684 207723744038868
685 213543685478774
686 219515090161888
687 225656605754051
688 231957839501408
689 238438224329292
690 245087017788580
691 251924471801877
692 258939484517648
693 266153159745445
694 273554026238652
695 281164073980884
696 288971453009164
697 296999076504945
698 305234704060684
699 313702210693272
700 322388953442278
701 331319810178221
702 340481724779266
703 349900618223274
704 359563010145520
705 369495906558118
706 379685392845702
707 390159605202738
708 400904181754808
709 411948436132684
710 423277545954944
711 434922052231047
712 446866660376044
713 459143188222565
714 471735857045714
715 484677812681066
716 497952781452984
717 511595292373964
718 525588562779152
719 539968562290725
720 554717985075594
721 569874302314532
722 585419672390896
723 601393128542154
724 617776280617736
725 634609786548826
726 651874696181504
727 669613359609774
728 687806251663700
729 706497484621229
730 725666943387720
731 745360576580592
732 765557665926000
733 786306070280977
734 807584455116830
735 829442666153474
736 851858740677136
737 874884593634548
738 898497618572620
739 922751885041753
740 947624127153988
741 973170659685367
742 999367543955044
743 1026273430057673
744 1053863693374944
745 1082199413101866
746 1111255266915348
747 1141094863342732
748 1171692166814728
749 1203113419394435
750 1235331856457078
751 1268416463983046
752 1302339735192696
753 1337173510185764
754 1372889527316114
755 1409562595550496
756 1447163687446192
757 1485770703000519
758 1525353834072440
759 1565994198735451
760 1607661192960532
761 1650439287141170
762 1694297069781568
763 1739322498250647
764 1785483341984312
765 1832871185693384
766 1881452970737848
767 1931324057999473
768 1982450547145228
769 2034931730519744
770 2088732852704594
771 2143957300762736
772 2200569455024636
773 2258676961784373
774 2318243328232112
775 2379380631052901
776 2442051498606376
777 2506372619606886
778 2572305732779858
779 2639972328114983
780 2709333244473384
781 2780514972055795
782 2853477444476564
783 2928352353296834
784 3005098722330666
785 3083853653327345
786 3164575259865140
787 3247406275266540
788 3332303896685292
789 3419416719563634
790 3508701020055174
791 3600311497903443
792 3694203508756664
793 3790538102426347
794 3889269716201826
795 3990566004854514
796 4094380494098056
797 4200887713899781
798 4310040279731028
799 4422019877453276
800 4536778215639162
801 4654504431124254
802 4775149335252274
803 4898909815302334
804 5025735797593296
805 5155832231196085
806 5289148174805240
807 5425896968655353
808 5566026815866952
809 5709759789973341
810 5857043253301724
811 6008108372334481
812 6162901691115212
813 6321663834382567
814 6484340554276380
815 6651182313556960
816 6822134104953880
817 6997456630430971
818 7177094151102800
819 7361318025095267
820 7550071812690988
821 7743637966235322
822 7941959385920848
823 8145330063902178
824 8353692285436804
825 8567352046446974
826 8786251070899884
827 9010707846792772
828 9240663585941248
829 9476449776673081
830 9718007172047292
831 9965680793600648
832 10219411001499320
833 10479556894149992
834 10746058510139132
835 11019289590677753
836 11299189934592672
837 11586148521025524
838 11880104987002476
839 12181464169105014
840 12490165626693496
841 12806630702406109
842 13130798977442258
843 13463108963424126
844 13803500369976000
845 14152429567448058
846 14509836514426564
847 14876196165012713
848 15251448843122668
849 15636088841620237
850 16030056975380062
851 16433867665409337
852 16847462361116096
853 17271376420721067
854 17705552082020520
855 18150546480913668
856 18606302814648576
857 19073400880018000
858 19551785002122278
859 20042058557642433
860 20544167180317312
861 21058738788037422
862 21585720525442966
863 22125765837730470
864 22678823596376896
865 23245573798647659
866 23825967279793672
867 24420711665381104
868 25029759991197384
869 25653848629932349
870 26292933071331502
871 26947779605271335
872 27618346454532968
873 28305431027640528
874 29008994578622680
875 29729866883429436
876 30468012550167208
877 31224295033196033
878 31998682620960636
879 32792073808509517
880 33604440911664416
881 34436718891077840
882 35288884469802086
883 36161910537408742
884 37055778628144936
885 37971501082456783
886 38909064680937124
887 39869522810091972
888 40852867939891584
889 41860196161992335
890 42891506104596220
891 43947938298632693
892 45029498040188968
893 46137372082210459
894 47271572929042868
895 48433335410442784
896 49622679818536342
897 50840891001558545
898 52087997633042062
899 53365336599047516
900 54672945580847918
901 56012215612004789
902 57383194059298152
903 58787328275194824
904 60224676027361644
905 61696743246523894
906 63203598866639346
907 64746809759881436
908 66326456811783980
909 67944170295101086
910 69600043876116898
911 71295773793839136
912 73031467387395800
913 74808889506590086
914 76628162103645484
915 78491121389324265
916 80397904932241928
917 82350423180377349
918 84348830350067918
919 86395114119123085
920 88489446438960840
921 90633895338689913
922 92828651669619584
923 95075867032331024
924 97375752404801816
925 99730546306784066
926 102140481148464376
927 104607885868306640
928 107133015653485140
929 109718293501407070
930 112363998794076792
931 115072652384503727
932 117844559360088772
933 120682342349528307
934 123586333736594974
935 126559261999704986
936 129601488506165488
937 132715851842943061
938 135902744103939912
939 139165118411790778
940 142503399422257584
941 145920659410831762
942 149417357545249476
943 152996690022694686
944 156659152574860548
945 160408070278733405
946 164243977600316500
947 168170333675907344
948 172187713951905640
949 176299717008611833
950 180506961634414224
951 184813191468517219
952 189219071145740440
953 193728495164861701
954 198342176640627692
955 203064166962788433
956 207895230505082984
957 212839581845662018
958 217898039499452164
959 223074987780104569
960 228371302368166764
961 233791544139014467
962 239336649140990332
963 245011361865864580
964 250816682092152956
965 256757545264983670
966 262835018438545100
967 269054235665716397
968 275416334955715526
969 281926656928697822
970 288586414407821490
971 295401162874524111
972 302372194044782276
973 309505286839986267
974 316801816146228908
975 324267793245557583
976 331904680699178832
977 339718731453051854
978 347711500421511420
979 355889491889337240
980 364254358027528402
981 372812864536622347
982 381566766020225306
983 390523100021830814
984 399683729000383560
985 409055973184490871
986 418641808595319334
987 428448849450912152
988 438479191260729104
989 448740753987980897
990 459235758840715644
991 469972443767832067
992 480953162218490536
993 492186482801001837
994 503674898059647584
995 515427320434752227
996 527446388770024312
997 539741373070496062
998 552315065964246326
999 565177109298411564
1000 578330457326170694