-1 1
0 0
1 2
2 0
3 1
4 2
5 2
6 2
7 4
8 2
9 5
10 6
11 7
12 6
13 12
14 8
15 13
16 14
17 19
18 16
19 25
20 20
21 31
22 32
23 40
24 38
25 55
26 48
27 64
28 68
29 83
30 80
31 108
32 102
33 130
34 136
35 163
36 162
37 209
38 200
39 247
40 260
41 306
42 308
43 383
44 378
45 455
46 478
47 553
48 566
49 683
50 686
51 805
52 848
53 972
54 1004
55 1183
56 1204
57 1395
58 1468
59 1665
60 1728
61 2007
62 2058
63 2348
64 2478
65 2789
66 2906
67 3326
68 3436
69 3884
70 4100
71 4573
72 4786
73 5416
74 5622
75 6296
76 6656
77 7378
78 7736
79 8672
80 9040
81 10052
82 10620
83 11708
84 12300
85 13680
86 14300
87 15798
88 16698
89 18322
90 19270
91 21287
92 22304
93 24502
94 25900
95 28287
96 29782
97 32719
98 34336
99 37532
100 39674
101 43169
102 45476
103 49707
104 52224
105 56857
106 60084
107 65145
108 68658
109 74732
110 78574
111 85221
112 90044
113 97332
114 102600
115 111237
116 117036
117 126518
118 133630
119 144039
120 151856
121 164093
122 172696
123 186136
124 196540
125 211322
126 222760
127 239991
128 252622
129 271569
130 286632
131 307478
132 324078
133 348222
134 366558
135 393103
136 414748
137 443970
138 467836
139 501465
140 527848
141 564863
142 595698
143 636431
144 670462
145 717110
146 754716
147 806040
148 849648
149 906161
150 954286
151 1018647
152 1071856
153 1142705
154 1203944
155 1281910
156 1349520
157 1437956
158 1512656
159 1609941
160 1695432
161 1802501
162 1896814
163 2017767
164 2121964
165 2255002
166 2373572
167 2519912
168 2650700
169 2815461
170 2959812
171 3140937
172 3304480
173 3503638
174 3683916
175 3907399
176 4106262
177 4351853
178 4576182
179 4846053
180 5093220
181 5395173
182 5667584
183 5999196
184 6305376
185 6669624
186 7006712
187 7413111
188 7784348
189 8230465
190 8646288
191 9135952
192 9593430
193 10138472
194 10641834
195 11239687
196 11801882
197 12457740
198 13075696
199 13803996
200 14483402
201 15281810
202 16038504
203 16913680
204 17744820
205 18714696
206 19627592
207 20690068
208 21704368
209 22868241
210 23981312
211 25268559
212 26490104
213 27899331
214 29253380
215 30795939
216 32280674
217 33983686
218 35611620
219 37474648
220 39275460
221 41313320
222 43286196
223 45532158
224 47693484
225 50148748
226 52534914
227 55218561
228 57830544
229 60783682
230 63642602
231 66868504
232 70019244
233 73542730
234 76988656
235 80860117
236 84628596
237 88854704
238 93000864
239 97613285
240 102144224
241 107205232
242 112155936
243 117676423
244 123114952
245 129135782
246 135074012
247 141671547
248 148154588
249 155346066
250 162457394
251 170294891
252 178053444
253 186631063
254 195094268
255 204437302
256 213708158
257 223883264
258 233989584
259 245112338
260 256127744
261 268234503
262 280285500
263 293460980
264 306587726
265 320974265
266 335270256
267 350918424
268 366539580
269 383557160
270 400559450
271 419121321
272 437623684
273 457799563
274 477993642
275 499919720
276 521882628
277 545774315
278 569656516
279 595607711
280 621645176
281 649828447
282 678125308
283 708805033
284 739551880
285 772854048
286 806340656
287 842482501
288 878848502
289 918155410
290 957640864
291 1000279019
292 1043240620
293 1089484032
294 1136106042
295 1186354178
296 1236939360
297 1291410571
298 1346396792
299 1405435013
300 1465064562
301 1529160867
302 1593813576
303 1663251962
304 1733466416
305 1808678493
306 1884769768
307 1966358247
308 2048802996
309 2137135769
310 2226595050
311 2322211918
312 2419093904
313 2522735010
314 2627635778
315 2739774179
316 2853505612
317 2974816288
318 3097903176
319 3229293503
320 3362480816
321 3504557157
322 3648840644
323 3802444128
324 3958495974
325 4124739905
326 4293488592
327 4473145018
328 4655812348
329 4849929299
330 5047370960
331 5257312033
332 5470684432
333 5697430371
334 5928230384
335 6173082873
336 6422396972
337 6687027116
338 6956291312
339 7241938614
340 7532987464
341 7841267612
342 8155473480
343 8488431448
344 8827576576
345 9186775025
346 9553104296
347 9940544022
348 10335787068
349 10753970294
350 11180333612
351 11631222646
352 12091453198
353 12577523312
354 13073791960
355 13598101403
356 14133137304
357 14698144249
358 15275304790
359 15884065394
360 16506068644
361 17162319986
362 17832534726
363 18539345554
364 19261873952
365 20023013885
366 20801247984
367 21621278066
368 22459371428
369 23342115242
370 24245074682
371 25195172311
372 26167222032
373 27190238752
374 28236490152
375 29337175500
376 30463736988
377 31647797322
378 32859913904
379 34134131495
380 35438087024
381 36808351181
382 38211589186
383 39684904964
384 41193925942
385 42778555017
386 44401070164
387 46104296121
388 47849371928
389 49679784936
390 51555456656
391 53523110044
392 55538831002
393 57652716354
394 59819517744
395 62090152463
396 64417949082
397 66857559278
398 69357921208
399 71977582503
400 74663923290
401 77476498098
402 80361024688
403 83381366864
404 86478224084
405 89719953743
406 93045435448
407 96524259312
408 100093369076
409 103827321738
410 107657326928
411 111663123422
412 115773802664
413 120070603042
414 124480361150
415 129090038945
416 133819932016
417 138762969649
418 143836982056
419 149136718589
420 154577392128
421 160260339633
422 166093314376
423 172184524768
424 178438864824
425 184966738553
426 191670001788
427 198666641215
428 205850016720
429 213346018402
430 221044690284
431 229074567674
432 237322177910
433 245924773542
434 254759210172
435 263971830816
436 273435655608
437 283300198605
438 293434412660
439 303997831503
440 314848412020
441 326156132172
442 337774515344
443 349877335347
444 362313422436
445 375268055669
446 388577571394
447 402439245380
448 416684301340
449 431514543094
450 446755781150
451 462623028224
452 478927916096
453 495899225678
454 513342696196
455 531492501053
456 550148151312
457 569558972912
458 589508393382
459 610261535875
460 631595054764
461 653780473770
462 676587285476
463 700304391904
464 724683065068
465 750030316750
466 776089637036
467 803175625579
468 831023557776
469 859967946440
470 889723435584
471 920645297012
472 952439253172
473 985469546283
474 1019432482060
475 1054715117747
476 1090990425624
477 1128669238329
478 1167414308020
479 1207647062112
480 1249019479840
481 1291979107034
482 1336151551708
483 1382011583645
484 1429173127762
485 1478123436138
486 1528464120776
487 1580712328189
488 1634439898536
489 1690195129135
490 1747536517966
491 1807027051289
492 1868211181260
493 1931686089486
494 1996962637520
495 2064673643555
496 2134314762336
497 2206536063901
498 2280817194360
499 2357847328995
500 2437068258380
501 2519209902291
502 2603696733142
503 2691278910722
504 2781362700820
505 2874742954304
506 2970783303334
507 3070325172678
508 3172712512932
509 3278810451744
510 3387942250736
511 3501024102678
512 3617331311550
513 3737833274169
514 3861782947048
515 3990177463004
516 4122246312984
517 4259044944625
518 4399748939508
519 4545474513795
520 4695371923696
521 4850589786064
522 5010251770524
523 5175573077811
524 5345616844384
525 5521667639873
526 5702759934948
527 5890216115695
528 6083040586910
529 6282631719587
530 6487926001676
531 6700400975815
532 6918960742592
533 7145126919844
534 7377769649484
535 7618497243918
536 7866103728380
537 8122287734889
538 8385806737412
539 8658410696902
540 8938818802908
541 9228879886967
542 9527227901260
543 9835814692504
544 10153233042612
545 10481494502511
546 10819148743280
547 11168320049437
548 11527462755816
549 11898818589282
550 12280795569174
551 12675704815361
552 13081905898036
553 13501838423549
554 13933755419428
555 14380230359202
556 14839464272840
557 15314111193625
558 15802317772426
559 16306884462980
560 16825838989184
561 17362134333097
562 17913739919944
563 18483702194371
564 19069929667692
565 19675635574936
566 20298595800792
567 20942197346975
568 21604150863592
569 22287951670495
570 22991242288176
571 23717707998803
572 24464843598992
573 25236532260662
574 26030195898488
575 26849843139015
576 27692819849982
577 28563350938337
578 29458617901904
579 30383070971488
580 31333810387296
581 32315431554580
582 33324949963780
583 34367207227918
584 35439036177724
585 36545534909831
586 37683445810756
587 38858034865913
588 40065950220174
589 41312738055118
590 42594843747790
591 43918105386910
592 45278867912228
593 46683163406225
594 48127232199260
595 49617425204556
596 51149757971820
597 52730913543312
598 54356796138600
599 56034312833487
600 57759252008578
601 59538883429396
602 61368746584776
603 63256489091194
604 65197527330572
605 67199767449357
606 69258497812876
607 71382037103793
608 73565398496528
609 75817330426896
610 78132710230808
611 80520584533423
612 82975689556524
613 85507541040556
614 88110571343592
615 90794784930967
616 93554464675172
617 96399958736128
618 99325394802040
619 102341654428322
620 105442530297388
621 108639459630374
622 111926071017612
623 115314197627262
624 118797297880208
625 122387811307007
626 126078827522806
627 129883417766901
628 133794492071344
629 137825577541917
630 141969398116420
631 146240170137036
632 150630212221580
633 155154458736729
634 159805032327030
635 164597391969239
636 169523457482352
637 174599471130595
638 179816908009740
639 185192826438969
640 190718488411952
641 196411555627058
642 202263069727464
643 208291582507660
644 214487648589632
645 220870747071444
646 227431201647552
647 234189185108120
648 241134782691142
649 248289178489817
650 255641925387624
651 263215261117756
652 270998489368136
653 279014644974462
654 287252774601608
655 295737062021891
656 304455973234908
657 313434889014602
658 322662007620472
659 332163625391005
660 341927664869952
661 351981727507810
662 362313103855634
663 372950755138501
664 383881685723984
665 395135907972548
666 406700131980438
667 418605852520312
668 430839093519752
669 443432894243920
670 456372974407446
671 469693579611943
672 483380117392108
673 497468516950454
674 511943442713104
675 526842578070539
676 542150266229494
677 557905574443192
678 574092516925932
679 590752072909938
680 607867454175064
681 625481632079703
682 643577481735842
683 662199561465497
684 681330402474624
685 701016734193615
686 721240223944688
687 742049863382055
688 763426970184984
689 785422355144845
690 808016979748936
691 831264120043114
692 855143810700724
693 879711896461109
694 904948052706352
695 930910208794089
696 957577675425948
697 985011180948538
698 1013189045433404
699 1042174913795544
700 1071946741810484
701 1102570562346752
702 1134023962985312
703 1166376154366097
704 1199603669772342
705 1233779031120329
706 1268878408392286
707 1304977058109828
708 1342050785184048
709 1380178453675566
710 1419334751733230
711 1459602302672470
712 1500955440223624
713 1543479918231476
714 1587149716871240
715 1632054685279041
716 1678167627196388
717 1725582659311683
718 1774272249724192
719 1824334097872737
720 1875740340631216
721 1928593326139274
722 1982863959640432
723 2038659433691770
724 2095950349298952
725 2154847998014442
726 2215322685331250
727 2277490979541534
728 2341321906218560
729 2406937532585459
730 2474306626897640
731 2543555944760606
732 2614654011447192
733 2687733571842244
734 2762761832498314
735 2839877780030481
736 2919048429942956
737 3000418129788290
738 3083953725124636
739 3169806361394495
740 3257941539667356
741 3348517489870725
742 3441499611834712
743 3537052263936646
744 3635140774384544
745 3735937216839170
746 3839405566190556
747 3945725936938428
748 4054862321424828
749 4167001838060224
750 4282108536471480
751 4400378291371380
752 4521773812229468
753 4646500099642687
754 4774520034042464
755 4906046618539621
756 5041042956964068
757 5179731989813347
758 5322075521577226
759 5468306849887475
760 5618388145910432
761 5772561848432137
762 5930790562748188
763 6093328005194299
764 6260135557420288
765 6431478689811935
766 6607319396877534
767 6787933588429228
768 6973283957647894
769 7163659212297882
770 7359020940577140
771 7559671189357426
772 7765572466572324
773 7977038738280748
774 8194033539685596
775 8416885359916104
776 8645556800956552
777 8880391489272834
778 9121353325579478
779 9368799542127404
780 9622695472123392
781 9883414827962528
782 10150922245886660
783 10425608615962896
784 10707440338236598
785 10996823830213574
786 11293727420454648
787 11598576227089689
788 11911338196475220
789 12232457939057888
790 12561905731914772
791 12900143902310116
792 13247145259771690
793 13603393351115679
794 13968861012880376
795 14344053910287075
796 14728947898274184
797 15124068852527980
798 15529395891684528
799 15945478968701597
800 16372297752159706
801 16810427292470616
802 17259851106537128
803 17721167295253538
804 18194363520942696
805 18680065203448100
806 19178261213669352
807 19689605448525970
808 20214091625074052
809 20752399924317950
810 21304529267242852
811 21871190831208233
812 22452385566511064
813 23048856961153880
814 23660612006450206
815 24288424155893110
816 24932306871350420
817 25593068773862002
818 26270726367454616
819 26966124932523089
820 27679288440579088
821 28411096327595191
822 29161580545902388
823 29931660430536321
824 30721372216755592
825 31531676831406389
826 32362619674552820
827 33215200597300688
828 34089474776470896
829 34986487328619269
830 35906299223064444
831 36850002762934165
832 37817670096835408
833 38810437877892237
834 39828390160940504
835 40872714951159468
836 41943503922573568
837 43041998612115259
838 44168304257528184
839 45323712918477223
840 46508344258063520
841 47723548590691790
842 48969455397708688
843 50247475721603625
844 51557755423635992
845 52901763089945752
846 54279661979955788
847 55692986762770311
848 57141913152347344
849 58628044706627425
850 60151576837950620
851 61714178632596378
852 63316066402431060
853 64958984193570671
854 66643163920097104
855 68370427771274700
856 70141031262685216
857 71956871190595768
858 73818228085348376
859 75727083768885277
860 77683738119686760
861 79690261596062029
862 81746982259526788
863 83856055496706836
864 86017839212429758
865 88234585231709134
866 90506675250791274
867 92836461628845665
868 95224359614302904
869 97672818226055210
870 100182288210974784
871 102755327965898932
872 105392417285359192
873 108096228589038259
874 110867281504916928
875 113708358444891320
876 116620021148624220
877 119605176074827510
878 122664420212106988
879 125800789333825692
880 129014927599752720
881 132309995924175286
882 135686688299933040
883 139148306316819594
884 142695586516172704
885 146331977136351932
886 150058270448642494
887 153878057042324587
888 157792188024792660
889 161804413508985053
890 165915635723711202
891 170129771078239895
892 174447787501390588
893 178873763301023433
894 183408735724638148
895 188056963966372003
896 192819546444113564
897 197700930916162733
898 202702293098613814
899 207828264847975248
900 213080103389556522
901 218462645675736965
902 223977221858555724
903 229628882690208027
904 235419049097461712
905 241352981136823430
906 247432195402911868
907 253662184482329398
908 260044551627244176
909 266585031819505483
910 273285334725760048
911 280151433247711322
912 287185149146273616
913 294392718937678338
914 301776067050248260
915 309341704795682571
916 317091681147714872
917 325032777817203822
918 333167174907722192
919 341501952962323110
920 350039413391681388
921 358786948240746281
922 367747004461252380
923 376927281356366115
924 386330379044592732
925 395964335556499044
926 405831893987261878
927 415941445450817986
928 426295902872502636
929 436904006445342854
930 447768847746372392
931 458899550886014871
932 470299375576900684
933 481977846110614020
934 493938420100673126
935 506191018360706825
936 518739306600907648
937 531593640733036032
938 544757883774801876
939 558242845159785296
940 572052618218507040
941 586198462716536654
942 600684714068838748
943 615523125098914500
944 630718262314714144
945 646282392464311261
946 662220349758114924
947 678544912297318145
948 695261195574635844
949 712382536376925614
950 729914320372407832
951 747870466665155074
952 766256671721696472
953 785087435183853452
954 804368779967063604
955 824115838700929533
956 844334949638601504
957 865041905155276686
958 886243403932519960
959 907955897310220903
960 930186462421553664
961 952952267705000528
962 976260757763764312
963 1000129848429795237
964 1024567401845219828
965 1049592081692440821
966 1075212188389803832
967 1101447197921470347
968 1128305838295842834
969 1155808432092056364
970 1183964190523570606
971 1212794284741681779
972 1242308433007523994
973 1272528726516605215
974 1303465380384877458
975 1335141444666997970
976 1367567693132176184
977 1400768138517890536
978 1434754140637217720
979 1469550754189688054
980 1505169915572859332
981 1541637765373233455
982 1578966885264752280
983 1617184507772702855
984 1656303891292478444
985 1696353448248708836
986 1737347105315699912
987 1779314504518907831
988 1822270317194130368
989 1866245423687313494
990 1911255276067947310
991 1957332090621800892
992 2004492093065984168
993 2052768891853532593
994 2102179571310779900
995 2152759143957394724
996 2204525594082627048
997 2257515446637753490
998 2311747580542945520
999 2367260096783311038
1000 2424072863447967260