-1 1
0 1
1 2
2 1
3 5
4 3
5 7
6 7
7 12
8 10
9 18
10 17
11 30
12 29
13 42
14 43
15 64
16 64
17 90
18 94
19 129
20 134
21 182
22 192
23 254
24 267
25 348
26 369
27 475
28 506
29 638
30 685
31 855
32 918
33 1138
34 1226
35 1500
36 1624
37 1964
38 2130
39 2564
40 2781
41 3318
42 3610
43 4283
44 4660
45 5496
46 5983
47 7023
48 7650
49 8925
50 9733
51 11310
52 12330
53 14260
54 15562
55 17932
56 19564
57 22450
58 24504
59 28026
60 30587
61 34862
62 38048
63 43246
64 47184
65 53472
66 58349
67 65946
68 71926
69 81096
70 88433
71 99469
72 108442
73 121686
74 132623
75 148525
76 161814
77 180842
78 196970
79 219700
80 239200
81 266324
82 289851
83 322169
84 350491
85 388908
86 422933
87 468586
88 509356
89 563470
90 612249
91 676346
92 734560
93 810342
94 879726
95 969216
96 1051736
97 1157244
98 1255238
99 1379540
100 1495670
101 1641824
102 1779299
103 1951002
104 2113392
105 2314858
106 2506440
107 2742539
108 2968210
109 3244550
110 3510009
111 3833144
112 4144887
113 4522258
114 4887967
115 5328211
116 5756582
117 6269616
118 6770770
119 7368026
120 7953594
121 8648136
122 9331497
123 10138410
124 10934918
125 11871382
126 12798758
127 13884591
128 14963006
129 16220796
130 17473545
131 18929208
132 20382882
133 22065894
134 23750910
135 25695209
136 27646338
137 29890291
138 32147442
139 34735092
140 37343498
141 40324924
142 43336476
143 46768764
144 50242429
145 54190318
146 58193388
147 62730900
148 67339722
149 72550572
150 77852324
151 83831839
152 89925210
153 96781490
154 103778881
155 111634522
156 119663228
157 128657106
158 137861708
159 148151353
160 158695504
161 170458868
162 182528201
163 195966971
164 209771224
165 225113254
166 240889983
167 258392678
168 276410310
169 296364346
170 316926097
171 339659918
172 363108030
173 388991460
174 415712559
175 445163118
176 475592630
177 509080378
178 543709437
179 581763997
180 621145769
181 664362752
182 709120103
183 758170246
184 809003640
185 864640314
186 922338234
187 985408674
188 1050856478
189 1122311754
190 1196504882
191 1277413146
192 1361468726
193 1453028040
194 1548200171
195 1651754836
196 1759449842
197 1876505966
198 1998301322
199 2130547058
200 2268209298
201 2417535010
202 2573043897
203 2741565586
204 2917137002
205 3107221962
206 3305335606
207 3519632295
208 3743061406
209 3984529300
210 4236375091
211 4508321766
212 4792048756
213 5098168308
214 5417647035
215 5762063781
216 6121615334
217 6508931046
218 6913378092
219 7348727331
220 7803449139
221 8292555250
222 8803550920
223 9352794420
224 9926749412
225 10543237754
226 11187601791
227 11879250888
228 12602319648
229 13377940842
230 14188950083
231 15058349948
232 15967576116
233 16941660626
234 17960536625
235 19051434518
236 20192670464
237 21413861726
238 22691586867
239 24058049204
240 25487961228
241 27016329278
242 28615863571
243 30324607660
244 32113120414
245 34022738078
246 36021714072
247 38154947928
248 40388220616
249 42770293108
250 45264296531
251 47923171847
252 50707211258
253 53673880774
254 56780434314
255 60089235454
256 63554284038
257 67243244584
258 71106638521
259 75217863552
260 79523719330
261 84103808798
262 88900954592
263 94001469194
264 99343926023
265 105021893340
266 110969409447
267 117287888680
268 123906524204
269 130935213701
270 138297987337
271 146113907552
272 154301496764
273 162989727048
274 172091251428
275 181745747066
276 191859614532
277 202584096882
278 213818942345
279 225727886584
280 238203593328
281 251423295358
282 265272126836
283 279941890794
284 295309716000
285 311583143344
286 328630797456
287 346677206956
288 365581967124
289 385587946592
290 406545161689
291 428716274795
292 451941139806
293 476503783132
294 502233294215
295 529436747577
296 557931827582
297 588050482516
298 619598325013
299 652934133832
300 687850753690
301 724735904340
302 763368936574
303 804168786602
304 846900543068
305 892016810726
306 939267632439
307 989141910936
308 1041373814296
309 1096491389798
310 1154212075083
311 1215106116799
312 1278873331169
313 1346129454574
314 1416555768721
315 1490817040760
316 1568575056982
317 1650547434776
318 1736375492190
319 1826833791942
320 1921542167240
321 2021336553010
322 2125814262699
323 2235877350640
324 2351099543408
325 2472454134376
326 2599490180315
327 2733257716966
328 2873280013590
329 3020689777256
330 3174983374401
331 3337382544930
332 3507355607390
333 3686220204864
334 3873415459777
335 4070362285951
336 4276469461012
337 4493269103412
338 4720138504794
339 4958729523168
340 5208386813904
341 5470891160240
342 5745553475622
343 6034293328020
344 6336386794690
345 6653902857126
346 6986081704419
347 7335153145881
348 7700320479038
349 8083986619978
350 8485317049307
351 8906900991253
352 9347865237300
353 9810999523976
354 10295391211512
355 10804045800285
356 11336010565712
357 11894523195986
358 12478590385046
359 13091699639926
360 13732816729014
361 14405697947898
362 15109267997969
363 15847572347740
364 16619494680135
365 17429391561152
366 18276105999842
367 19164329192370
368 20092864069704
369 21066761799758
370 22084786176276
371 23152375535969
372 24268255850288
373 25438281869238
374 26661143493369
375 27943143308180
376 29282937341176
377 30687309800976
378 32154885621974
379 33692966897950
380 35300150830320
381 36984296411012
382 38743977158418
383 40587650847710
384 42513872119544
385 44531742547012
386 46639803565724
387 48847848904032
388 51154413377836
389 53570034835880
390 56093249156875
391 58735394102784
392 61495015425808
393 64384310783310
394 67401845935417
395 70560742821759
396 73859598769274
397 77312529179784
398 80918176120525
399 84691722760909
400 88631870784768
401 92754950945840
402 97059741438455
403 101563806273058
404 106266019126270
405 111185269347674
406 116320547450433
407 121692166948850
408 127299259129598
409 133163667822300
410 139284691912413
411 145685819513954
412 152366546997226
413 159352129176052
414 166642293310512
415 174264192278924
416 182217821354692
417 190532372604062
418 199208150595750
419 208276538028444
420 217738194567517
421 227626856169726
422 237943588381953
423 248724654972086
424 259971583523324
425 271723353024294
426 283982015257024
427 296789465535615
428 310148348409546
429 324103691464958
430 338658807694508
431 353862088659436
432 369717599187260
433 386277343522166
434 403546230158170
435 421580142943625
436 440384934968400
437 460020656157718
438 480494215245362
439 501870135567789
440 524156503346658
441 547422645230828
442 571677958675338
443 596996927550853
444 623390407164490
445 650938418362683
446 679653435021663
447 709621422389454
448 740856648767082
449 773451460971232
450 807422114289590
451 842867805989190
452 879806988808214
453 918346213594116
454 958506360618078
455 1000401873895330
456 1044056312488740
457 1089592592442990
458 1137037225956478
459 1186522221941932
460 1238077344949204
461 1291844362687504
462 1347856618494189
463 1406266352947290
464 1467110843842376
465 1530553570591012
466 1596636132970482
467 1665534070467710
468 1737293726814966
469 1812103582268454
470 1890015183835555
471 1971230896860893
472 2055807971194104
473 2143963669817974
474 2235761488867099
475 2331434674421676
476 2431053559498988
477 2534868537154846
478 2642957419061002
479 2755588992838764
480 2872849245842987
481 2995026697685532
482 3122216268288281
483 3254727642824930
484 3392665495073970
485 3536362212419498
486 3685933113770901
487 3841734935545497
488 4003894608233450
489 4172794982422276
490 4348575648125955
491 4531647461575366
492 4722163808027784
493 4920565576388588
494 5127021177782033
495 5342003705795812
496 5565697930152806
497 5798611476499916
498 6040946916519107
499 6293248901317704
500 6555739366682128
501 6829002660819606
502 7113281774208129
503 7409203614045426
504 7717034054409318
505 8037445627366762
506 8370729068703745
507 8717605819401962
508 9078393615522042
509 9453866324680472
510 9844370995144033
511 10250737688540285
512 10673345263530726
513 11113084010862392
514 11570367298638601
515 12046149967786022
516 12540882811009528
517 13055589846745836
518 13590762440276833
519 14147498742398982
520 14726334089149808
521 15328446069071952
522 15954417656890919
523 16605511558938668
524 17282362346195116
525 17986323924103086
526 18718086729449103
527 19479102376723739
528 20270121773313564
529 21092701211523738
530 21947657034852012
531 22836657672706679
532 23760590257490970
533 24721243339678894
534 25719580610442018
535 26757519285914544
536 27836105833255246
537 28957395279045224
538 30122523564877542
539 31333693313459202
540 32592137155966838
541 33900215782618566
542 35259266284629437
543 36671818623853102
544 38139322717697997
545 39664489787379334
546 41248891583196801
547 42895433410349109
548 44605818545560026
549 46383160098005684
550 48229303302137964
551 50147583747120156
552 52139999847970286
553 54210125372128800
554 56360123987658450
555 58593824430524391
556 60913568605361158
557 63323458174040142
558 65826027239443826
559 68425669593117037
560 71125126546073392
561 73929104555770764
562 76840568276024679
563 79864558788923966
564 83004281431516366
565 86265135389368032
566 89650585316116713
567 93166413603102829
568 96816364239213536
569 100606629657985068
570 104541254688133922
571 108626870493149397
572 112867845837286068
573 117271281279903662
574 121841894322243881
575 126587287696673026
576 131512554269827590
577 136625833979115966
578 141932623642586566
579 147441637841909390
580 153158808028228506
581 159093463437061734
582 165252003080009077
583 171644413598984648
584 178277596896642526
585 185162242703193358
586 192305793716932170
587 199719691563559490
588 207411960396354754
589 215394845880402714
590 223676997232504984
591 232271519861345686
592 241187734811098998
593 250439666738246232
594 260037358656042571
595 269995818026791892
596 280325863587177894
597 291043553490394768
598 302160539816780685
599 313694003910335286
600 325656492950133042
601 338066388895440180
602 350937200201984154
603 364288592121605553
604 378135105293440020
605 392497776542855800
606 407392254657431371
607 422841042292889478
608 438860977756745156
609 455476130167152312
610 472704614503851197
611 490572173776884270
612 509098292969191553
613 528310503661870172
614 548229760776558916
615 568885506874550059
616 590300273808289074
617 612505545771105836
618 635525546080860637
619 659393940001643827
620 684136764907838078
621 709790015942486476
622 736381675736163849
623 763950228105159716
624 792525741330480092
625 822149357342120574
626 852853380287256871
627 884681790996555766
628 917669290186513366
629 951862890469385186
630 987299861035581633
631 1024030452046995954
632 1062094685030023406
633 1101546267199990090
634 1142428169049274620
635 1184797788984120684
636 1228701256721881694
637 1274199911591222196
638 1321343267341777477
639 1370196870569431458
640 1420813859388895244
641 1473264271708097440
642 1527605126910635432
643 1583911257114594720
644 1642243837556112898
645 1702682817547027280
646 1765293821624902517
647 1830162260669787657
648 1897358522095001096
649 1966973845507428062
650 2039083716240191951
651 2113785594049358936
652 2191160420130334164
653 2271312291650248304
654 2354327988033904943
655 2440318688634347996
656 2529377419516980320
657 2621622916293032224
658 2717154887853401870
659 2816100131329267139
660 2918565504233246722
661 3024686403685123482
662 3134577333185976567
663 3248382863661795413
664 3366225675620897256
665 3488260125241675109
666 3614617636932505228
667 3745463003619792282
668 3880936998735641612
669 4021215546079157020
670 4166449413975720120
671 4316826396585693974
672 4472507946415078794
673 4633694515751836350
674 4800558976833874121
675 4973315279213951548
676 5152148499700288798
677 5337286978909533632
678 5528928835569522554
679 5727317753314472349
680 5932665786072749078
681 6145232974323972762
682 6365246260054868934
683 6592983120236427200
684 6828686401221226433
685 7072652166134172606
686 7325140249572544972
687 7586466524949988624
688 7856908970937263040
689 8136804574582034524
690 8426450691070002601
691 8726206808667343567
692 9036390973077547118
693 9357386650958746932
694 9689533979365552710
695 10033241975784077030
696 10388874361879995200
697 10756867379700439872
698 11137609927160394106
699 11531567252302628468
700 11939155125629035068
701 12360869697118999024
702 12797155417625131279
703 13248541356732550355
704 13715502571971794756
705 14198603199608655708
706 14698350956336403654
707 15215347329723944002
708 15750134882332160346
709 16303354883856357168
710 16875587072221351104
711 17467515085455017986
712 18079758318232103750
713 18713045528254334382
714 19368038409898524489
715 20045513767362192462
716 20746178409507938582
717 21470860300324563448
718 22220314360690264369
719 22995423025809138068
720 23796992520434513986
721 24625963272920199114
722 25483196210391823432
723 26369693499930050607
724 27286374389229405270
725 28234306767259933918
726 29214472054061668969
727 30228008096029294686
728 31275962585628690014
729 32359547830290285806
730 33479882158933371927
731 34638257128356813927
732 35835866348507490730
733 37074085716281079264
734 38354189065397756313
735 39677642044715788481
736 41045803971345890842
737 42460235998999015856
738 43922388524525561727
739 45433924321490787252
740 46996390820626929774
741 48611558914846847602
742 50281079403062805864
743 52006838205241358921
744 53790596226650641592
745 55634361755400095346
746 57540012970343540042
747 59509688328890317733
748 61545390906464234054
749 63649397619302771066
750 65823844546481331736
751 68071155870967264185
752 70393609296713543116
753 72793785631518185546
754 75274113371471688405
755 77837339891227347908
756 80486054226118702958
757 83223180879372422784
758 86051479788386251116
759 88974063804279429730
760 91993874783079616251
761 95114225840911015170
762 98338252463087624885
763 101669480688234370888
764 105111252078457896774
765 108667319037923530506
766 112341242435244805898
767 116137015316550158108
768 120058431916959334548
769 124109741085088624512
770 128294985363826394381
771 132618685502637834464
772 137085148228734531294
773 141699183285576905854
774 146465378453838120926
775 151388850619232891635
776 156474486538320931230
777 161727729506383399228
778 167153784295934856642
779 172758441065904804629
780 178547242830667555108
781 184526348325411444338
782 190701660290389059258
783 197079729084189735884
784 203666839991651783788
785 210469959456956499312
786 217495779544084979362
787 224751708745320742941
788 232244871640160685474
789 239983146322154520412
790 247974117215605692549
791 256226161254792855031
792 264747351727529725188
793 273546595435898604892
794 282632485341573640026
795 292014491036397944831
796 301701757866176165460
797 311704353142949897054
798 322032009321554719370
799 332695428493415149188
800 343704967083386478748
801 355072001277567699296
802 366807550596571761621
803 378923707027374906066
804 391432194713065708948
805 404345865681350764704
806 417677192769765287837
807 431439834971331691934
808 445647060587998647084
809 460313385347361999998
810 475452922645501982183
811 491081097727785761634
812 507212921745112424954
813 523864785436945629494
814 541052653581951630633
815 558793941772746968430
816 577105627692869274918
817 596006214730562920992
818 615513756358638747452
819 635647910499211019397
820 656427873121061493504
821 677874527438901761004
822 700008282674063716438
823 722851322350821565401
824 746425343990342303476
825 770753910953251816044
826 795860088653435591072
827 821768904590618628128
828 848504876479593482928
829 876094585319475711604
830 904564090634864081269
831 933941621639958539155
832 964254874580734203558
833 995533827272663482842
834 1027807913316857804538
835 1061108965520010630462
836 1095468261532308970652
837 1130919601897907505780
838 1167496221427787756553
839 1205234007878900173498
840 1244168273130772086661
841 1284337118751883778346
842 1325778060794220974124
843 1368531548776887744556
844 1412637437647589536980
845 1458138666996446887300
846 1505077573457126663815
847 1553499737258676262668
848 1603450128051301589502
849 1654977126211405786132
850 1708128494777280930207
851 1762955583242821950050
852 1819509117976292030462
853 1877843596571986519050
854 1938012888800147420560
855 2000074829933687491653
856 2064086623938809939038
857 2130109644556405919006
858 2198204632090401510581
859 2268436711401111824532
860 2340870373281285529026
861 2415574718912289894112
862 2492618216435561749142
863 2572074181832550480214
864 2654015300901348922070
865 2738519356948567883762
866 2825663507966562298609
867 2915530271970529574095
868 3008201548740371566152
869 3103764874100085793008
870 3202307175139206023117
871 3303921305214632501000
872 3408699521099125807222
873 3516740310989039664390
874 3628141581540652302965
875 3743007791691529328987
876 3861442837038948449996
877 3983557502828744939094
878 4109462032602818758208
879 4239273914278149242107
880 4373110119441602867640
881 4511095237034353768272
882 4653353369101048577580
883 4800016627211953786657
884 4951216669879165694438
885 5107093577491596974112
886 5267787015992299756257
887 5433445506770793354266
888 5604217200551902177454
889 5780259559387090511380
890 5961729724035374962761
891 6148794625921331861348
892 6341620930591683066546
893 6540385598263734683810
894 6745265385216037524553
895 6956447872338258702948
896 7174120505559859227350
897 7398482112632260094790
898 7629731462914448284563
899 7868079293471915501656
900 8113736367721516648934
901 8366926032820489689712
902 8627871755823335059745
903 8896810235259640723334
904 9173978392572033283338
905 9459627061745098074610
906 9754007412874184445286
907 10057385244710785474065
908 10370026816255881322350
909 10692213768131531071492
910 11024228337097883813313
911 11366368933247929783417
912 11718934711313027722304
913 12082241831809572387180
914 12456607361922162038597
915 12842366249909095035564
916 13239854527233619803840
917 13649427026761640720566
918 14071439856648132516353
919 14506268894136962589826
920 14954291500499881704294
921 15415905823577195855806
922 15891511721808796580904
923 16381530910037425563534
924 16886387059363349656651
925 17406526822171453025556
926 17942399073181268554104
927 18494476851157279240695
928 19063235705112197184192
929 19649176591719127890765
930 20252803289156113211538
931 20874646290861410362422
932 21515239247979336350948
933 22175143901788668667264
934 22854925514121293813742
935 23555178882551027340852
936 24276502716505452786826
937 25019526781131156125498
938 25784885175102805915312
939 26573244650983652726862
940 27385276748951987327214
941 28221687343455876140706
942 29083187585222974185475
943 29970524726068645781502
944 30884451819628186959864
945 31825759878321216646316
946 32795246281242632652315
947 33793748319516513324978
948 34822110257701035113802
949 35881218326085676454058
950 36971966379802618713589
951 38095292399035271694071
952 39252142687781434373364
953 40443509945452923326108
954 41670395944900672455423
955 42933851241498138390858
956 44234936267612403791432
957 45574762747982390873706
958 46954453145299189989651
959 48375183853517807787536
960 49838142926591144659760
961 51344575124295524608266
962 52895737853442005508384
963 54492948143855684033253
964 56137536728561660204576
965 57830897030740903652418
966 59574437306452167035265
967 61369631726697565434813
968 63217970503192074043720
969 65121013153115355078624
970 67080336525272609514837
971 69097590338690470011877
972 71174443023222876339666
973 73312639626873663165380
974 75513945381483909880085
975 77780206077537690904048
976 80113289262018430133058
977 82515147183483242662666
978 84987755525490177901060
979 87533179028916358670680
980 90153507660530749111710
981 92850925023888664038028
982 95627641858650204739830
983 98485967355914852640358
984 101428239879758964953228
985 104456901307586138941848
986 107574424861072109863833
987 110783392597006286399612
988 114086420230383431965724
989 117486237906306813916924
990 120985611893346947997443
991 124587428772374420691178
992 128294613873510684305282
993 132110219023267220003742
994 136037337593434971758568
995 140079195953633936385763
996 144239064995320106525538
997 148520355442804583825064
998 152926525710192443167283
999 157461181230121826331765
1000 162127978495880959094234