-1 1
0 1
1 2
2 2
3 4
4 5
5 7
6 8
7 12
8 14
9 20
10 23
11 31
12 37
13 47
14 56
15 71
16 84
17 104
18 122
19 151
20 178
21 215
22 252
23 303
24 355
25 423
26 492
27 582
28 676
29 795
30 920
31 1076
32 1242
33 1445
34 1662
35 1926
36 2210
37 2549
38 2916
39 3353
40 3827
41 4386
42 4992
43 5703
44 6478
45 7379
46 8362
47 9499
48 10742
49 12174
50 13738
51 15533
52 17496
53 19736
54 22190
55 24979
56 28036
57 31497
58 35290
59 39574
60 44269
61 49554
62 55348
63 61850
64 68980
65 76959
66 85706
67 95475
68 106178
69 118106
70 131172
71 145703
72 161616
73 179276
74 198608
75 220028
76 243462
77 269383
78 297728
79 329034
80 363250
81 400982
82 442200
83 487595
84 537153
85 591658
86 651130
87 716461
88 787704
89 865868
90 951056
91 1044421
92 1146116
93 1257447
94 1378643
95 1511188
96 1655396
97 1812945
98 1984260
99 2171255
100 2374468
101 2596073
102 2836764
103 3099015
104 3383696
105 3693602
106 4029828
107 4395559
108 4792130
109 5223160
110 5690276
111 6197603
112 6747113
113 7343480
114 7989092
115 8689263
116 9446850
117 10267893
118 11155798
119 12117447
120 13156874
121 14281892
122 15497290
123 16811953
124 18231528
125 19766103
126 21422316
127 23211651
128 25141886
129 27226064
130 29473284
131 31898368
132 34511940
133 37330830
134 40367410
135 43640801
136 47165374
137 50962832
138 55049858
139 59451088
140 64185838
141 69282053
142 74762070
143 80657601
144 86994427
145 93808498
146 101129538
147 108998301
148 117449004
149 126527830
150 136274108
151 146740170
152 157971154
153 170026325
154 182957458
155 196831641
156 211708166
157 227662950
158 244763832
159 263096718
160 282739104
161 303788143
162 326332316
163 350481451
164 376336460
165 404021435
166 433651366
167 465366444
168 499297532
169 535602939
170 574431504
171 615961921
172 660363312
173 707837264
174 758575832
175 812806378
176 870746754
177 932653275
178 998772906
179 1069394505
180 1144797807
181 1225308155
182 1311242224
183 1402966343
184 1500838686
185 1605271538
186 1716669770
187 1835497236
188 1962211244
189 2097333389
190 2241379924
191 2394937190
192 2558587548
193 2732989807
194 2918800524
195 3116759682
196 3327607008
197 3552173252
198 3791291384
199 4045893739
200 4316917672
201 4605409066
202 4912422174
203 5239129826
204 5586717062
205 5956498452
206 6349805366
207 6768110733
208 7212909448
209 7685851175
210 8188613534
211 8723043465
212 9291022682
213 9894618074
214 10535939244
215 11217298359
216 11941059290
217 12709807575
218 13526190684
219 14393098781
220 15313495499
221 16290610193
222 17327758932
223 18428548710
224 19596688166
225 20836204524
226 22151243560
227 23546300090
228 25026006416
229 26595377280
230 28259586354
231 30024226373
232 31895073120
233 33878361614
234 35980537040
235 38208547969
236 40569583440
237 43071384404
238 45721966332
239 48529949803
240 51504267964
241 54654517494
242 57990650300
243 61523345972
244 65263686808
245 69223553254
246 73415281596
247 77852083587
248 82547685976
249 87516775868
250 92774621352
251 98337544091
252 104222520030
253 110447681070
254 117031895102
255 123995298230
256 131358853270
257 139144914503
258 147376763856
259 156079210014
260 165278101050
261 175000960352
262 185276474903
263 196135169912
264 207608871781
265 219731423808
266 232538123168
267 246066480018
268 260355627144
269 275447125532
270 291384345734
271 308213322517
272 325982106872
273 344741672747
274 364545239122
275 385449231679
276 407512573610
277 430797706053
278 455369846680
279 481298072410
280 508654544496
281 537515657439
282 567961230072
283 600075724412
284 633947401528
285 669669614969
286 707339930592
287 747061499191
288 788942139002
289 833095792642
290 879641571850
291 928705303692
292 980418536490
293 1034920181130
294 1092355477648
295 1152877737591
296 1216647270234
297 1283833232508
298 1354612514674
299 1429171704400
300 1507705931198
301 1590420952132
302 1677531954830
303 1769265772547
304 1865859645288
305 1967563572602
306 2074639033250
307 2187361484226
308 2306019038936
309 2430915122171
310 2562367107282
311 2700709137254
312 2846290721119
313 2999479732035
314 3160660964328
315 3330239319671
316 3508638325972
317 3696303524164
318 3893700950492
319 4101320737224
320 4319675559800
321 4549304466017
322 4790771290716
323 5044668727928
324 5311616716068
325 5592266769397
326 5887300337316
327 6197433412413
328 6523414867126
329 6866031357621
330 7226105642624
331 7604501802546
332 8002123545854
333 8419919764794
334 8858882835802
335 9320054534407
336 9804524336150
337 10313435715959
338 10847984457542
339 11409425362988
340 11999070579552
341 12618296747956
342 13268543357316
343 13951320361717
344 14668206574176
345 15420857784704
346 16211005206492
347 17040464129725
348 17911132434036
349 18824999815665
350 19784146382968
351 20790752496454
352 21847097464704
353 22955570040992
354 24118667239958
355 25339005536359
356 26619319824420
357 27962475368625
358 29371466931150
359 30849431527270
360 32399647747286
361 34025549374720
362 35730724933348
363 37518932229041
364 39394098154727
365 41360334221977
366 43421936661800
367 45583403016279
368 47849432574760
369 50224944102671
370 52715076657866
371 55325208538381
372 58060958527332
373 60928206147717
374 63933093390980
375 67082046372554
376 70381777602528
377 73839309144545
378 77461975493558
379 81257448347529
380 85233740162278
381 89399230653851
382 93762671109540
383 98333212746377
384 103120411863074
385 108134260191027
386 113385190980554
387 118884111490811
388 124642410110938
389 130671991146666
390 136985283088392
391 143595275862642
392 150515530368122
393 157760218374242
394 165344133457908
395 173282733744662
396 181592154389350
397 190289253371022
398 199391625675326
399 208917652368744
400 218886516653562
401 229318256465367
402 240233782587276
403 251654935032402
404 263604503419124
405 276106287421187
406 289185119625106
407 302866930349995
408 317178773226412
409 332148894712834
410 347806762656688
411 364183140858029
412 381310120894380
413 399221202110161
414 417951327013244
415 437536967094886
416 458016162131194
417 479428612271022
418 501815721604402
419 525220696987983
420 549688596271243
421 575266434366717
422 602003236559874
423 629950152366202
424 659160514385752
425 689689960532624
426 721596498934880
427 754940639164671
428 789785463722722
429 826196768948063
430 864243143673642
431 903996120542280
432 945530262467346
433 988923325138064
434 1034256351973668
435 1081613848658734
436 1131083887332118
437 1182758294060058
438 1236732763063742
439 1293107058103002
440 1351985137610534
441 1413475371034265
442 1477690675819890
443 1544748749836058
444 1614772221219056
445 1687888898093751
446 1764231932378664
447 1843940088103914
448 1927157920360296
449 2014036063614901
450 2104731427086828
451 2199407504564017
452 2298234587586598
453 2401390098384314
454 2509058822361120
455 2621433265891705
456 2738713909716876
457 2861109593469606
458 2988837791721858
459 3122125027247933
460 3261207171596704
461 3406329889253734
462 3557748964763426
463 3715730780110129
464 3880552670570490
465 4052503437808148
466 4231883736811872
467 4419006627382322
468 4614197994690854
469 4817797142039401
470 5030157247774522
471 5251646002414212
472 5482646104861674
473 5723555947223297
474 5974790153499100
475 6236780315659905
476 6509975578233334
477 6794843429476791
478 7091870335542624
479 7401562590866185
480 7724447005873749
481 8061071821011099
482 8412007452266860
483 8777847473589932
484 9159209424824940
485 9556735867620858
486 9971095260727226
487 10402983094871713
488 10853122840738710
489 11322267168699495
490 11811198975203290
491 12320732693671340
492 12851715405463332
493 13405028248714002
494 13981587620505452
495 14582346690920195
496 15208296703545688
497 15860468602555335
498 16539934439212016
499 17247809120354671
500 17985251929141680
501 18753468403936911
502 19553711982154272
503 20387286019190572
504 21255545564890832
505 22159899532884271
506 23101812619904414
507 24082807636632408
508 25104467580865788
509 26168438141786131
510 27276429938791172
511 28430221211965008
512 29631660239259078
513 30882668226876466
514 32185241918431865
515 33541456699948012
516 34953469415628302
517 36423521703232062
518 37953943032176988
519 39547154286195425
520 41205671040633660
521 42932107410518290
522 44729179585164084
523 46599709961078275
524 48546630953313146
525 50572989434039783
526 52681950841509796
527 54876803946622845
528 57160965281876396
529 59537984259862758
530 62011547946223796
531 64585486555722203
532 67263778594960824
533 70050556763512116
534 72950113494041264
535 75966907287938823
536 79105568682480928
537 82370907052521110
538 85767917036470194
539 89301785837848429
540 92977900144158528
541 96801853964509605
542 100779456077923280
543 104916738445809806
544 109219964228868209
545 113695636815958281
546 118350508451575010
547 123191589925602756
548 128226159856347550
549 133461775088813858
550 138906280681509982
551 144567821064252233
552 150454850780396916
553 156576146458785993
554 162940818366749742
555 169558323254658330
556 176438476778974968
557 183591467282000442
558 191027869148480534
559 198758657587527277
560 206795222990786130
561 215149386788231849
562 223833416880725724
563 232860044646410206
564 242242481525632442
565 251994437260042671
566 262130137713378120
567 272664344431108809
568 283612373786456800
569 294990117954579201
570 306814065479494616
571 319101323763349036
572 331869641156640282
573 345137431070124436
574 358923795697923648
575 373248551867107092
576 388132256510941022
577 403596234379183632
578 419662605386942056
579 436354314317255461
580 453695160179778556
581 471709828046355767
582 490423920563121396
583 509863992069494526
584 530057582417278700
585 551033253533915768
586 572820625712849460
587 595450416792975036
588 618954481095921792
589 643365851405499978
590 668718780739740338
591 695048787326779815
592 722392699412490384
593 750788703442761183
594 780276392121431844
595 810896816023336915
596 842692535132057906
597 875707674123496149
598 909987977628777076
599 945580869444521752
600 982535511783103748
601 1020902868683317701
602 1060735769528207244
603 1102088976948511356
604 1145019254907482240
605 1189585441409447512
606 1235848521471548522
607 1283871704971016928
608 1333720504845628110
609 1385462820435993252
610 1439169021279869964
611 1494912036329963320
612 1552767443732110387
613 1612813566324912694
614 1675131567818372384
615 1739805555009193961
616 1806922680804752274
617 1876573253617264805
618 1948850847708181976
619 2023852420255720566
620 2101678429526947356
621 2182432960146548481
622 2266223849638220622
623 2353162822458113212
624 2443365625483732034
625 2536952171413421305
626 2634046683820020924
627 2734777850558165685
628 2839278979041511752
629 2947688160342727958
630 3060148435397453584
631 3176807970527759095
632 3297820235323234948
633 3423344190367630643
634 3553544477597849484
635 3688591621065598704
636 3828662230628706472
637 3973939216635178335
638 4124612007858436142
639 4280876781050349113
640 4442936694092898742
641 4611002131429803402
642 4785290953472030112
643 4966028758984772079
644 5153449151853347356
645 5347794021573835829
646 5549313828559552218
647 5758267903959826189
648 5974924754765652584
649 6199562384262241225
650 6432468618275998478
651 6673941447652855442
652 6924289377077677380
653 7183831791062388778
654 7452899326863636936
655 7731834265562677932
656 8020990930707960494
657 8320736106173033532
658 8631449462258108566
659 8953524002123245836
660 9287366517197257154
661 9633398064101618765
662 9992054451336772240
663 10363786748737983221
664 10749061807538605128
665 11148362804532995686
666 11562189797754184420
667 11991060307661411304
668 12435509910816342500
669 12896092860564427687
670 13373382721249952184
671 13867973031021726241
672 14380477979293381962
673 14911533114475581324
674 15461796067564757208
675 16031947307786627333
676 16622690915384642304
677 17234755388353899641
678 17868894467700657264
679 18525887998652396902
680 19206542811872579830
681 19911693642752469717
682 20642204072291728674
683 21398967508311395416
684 22182908189951704767
685 22994982234894307273
686 23836178711684813644
687 24707520757316773926
688 25610066721858766026
689 26544911361033888321
690 27513187057920841850
691 28516065095461667004
692 29554756960314194352
693 30630515700538682173
694 31744637317006444114
695 32898462211854005125
696 34093376673200760566
697 35330814420318599673
698 36612258187781504944
699 37939241373680495129
700 39313349729721391536
701 40736223119220906639
702 42209557320086923236
703 43735105899763000513
704 45314682138469832346
705 46950161028724023006
706 48643481326691655346
707 50396647684394463625
708 52211732837528261404
709 54090879878987462778
710 56036304592034419112
711 58050297874323406988
712 60135228225873500572
713 62293544333357734733
714 64527777722934164546
715 66840545515186926561
716 69234553253509663458
717 71712597840744958497
718 74277570554493745680
719 76932460177200372953
720 79680356210483275884
721 82524452211157326053
722 85468049217447620554
723 88514559304231355165
724 91667509234810703142
725 94930544249496110022
726 98307431957478906446
727 101802066373769558103
728 105418472066628821808
729 109160808458821358804
730 113033374247039269204
731 117040611984436829323
732 121187112789515471262
733 125477621227972865053
734 129917040329617611732
735 134510436788699136383
736 139263046308587268300
737 144180279140952525928
738 149267725779184568792
739 154531162858069549398
740 159976559218236393262
741 165610082189333514599
742 171438104049187711548
743 177467208714921318093
744 183704198621989939466
745 190156101849208193454
746 196830179444404801012
747 203733933010945623540
748 210875112508413130624
749 218261724329935195718
750 225902039608066597660
751 233804602814056806024
752 241978240600989918064
753 250432070958060900189
754 259175512625023798224
755 268218294836600138896
756 277570467344400130044
757 287242410788766344148
758 297244847366576341248
759 307588851870136666025
760 318285863041655444469
761 329347695321254219036
762 340786550931423828620
763 352615032378822887478
764 364846155314708137900
765 377493361837947478907
766 390570534180256263634
767 404092008860778882389
768 418072591247974646688
769 432527570619225148558
770 447472735654407789940
771 462924390457276814075
772 478899371039149834404
773 495415062362299840305
774 512489415875771872682
775 530140967644723014942
776 548388857004194579602
777 567252845842259745264
778 586753338441614211276
779 606911401988549718119
780 627748787676506450042
781 649287952517299293951
782 671552081785312863000
783 694565112212080522157
784 718351755854612715172
785 742937524759382305317
786 768348756343375139336
787 794612639618785440311
788 821757242180780953478
789 849811538089776587561
790 878805436565633236968
791 908769811630274842752
792 939736532614108831164
793 971738495668000933715
794 1004809656194136372934
795 1038985062342988622422
796 1074300889487654975298
797 1110794475828471929347
798 1148504359037079260462
799 1187470314098768735541
800 1227733392260180790022
801 1269335961247349355914
802 1312321746659040002484
803 1356735874706797456800
804 1402624916204519850266
805 1450036931985654440265
806 1499021519648697675754
807 1549629861816047328516
808 1601914775804751877104
809 1655930764901444327028
810 1711734071137868447102
811 1769382729766823050414
812 1828936625332799756848
813 1890457549544990651225
814 1954009260844817687734
815 2019657545883837211114
816 2087470282802061650448
817 2157517506531069561159
818 2229871476009855182690
819 2304606743546662436094
820 2381800226212688300296
821 2461531279510146249389
822 2543881773198539080224
823 2628936169531266258376
824 2716781603784416740308
825 2807507967339913201504
826 2901207993202904476836
827 2997977344226037550885
828 3097914703918603751342
829 3201121870124099866645
830 3307703851442356755584
831 3417768966691149679244
832 3531428947281669809760
833 3648799042814630111386
834 3769998129769690285376
835 3895148823607340454408
836 4024377594154322241082
837 4157814884604624298658
838 4295595234005624429240
839 4437857403574868011303
840 4584744506715659665171
841 4736404143090991623828
842 4892988536622714261248
843 5054654677790113796210
844 5221564470093668565360
845 5393884881073426508227
846 5571788097746792878364
847 5755451686871114020848
848 5945058759895031023454
849 6140798143020629126882
850 6342864552239724929657
851 6551458773783686578049
852 6766787849849698473216
853 6989065270060998511920
854 7218511168523788847284
855 7455352526957280257238
856 7699823383759600686988
857 7952165049505797276196
858 8212626328740953306640
859 8481463748585295146958
860 8758941794014885828726
861 9045333150356344222922
862 9340918952860070209386
863 9645989043912940175026
864 9960842237756171644690
865 10285786593292854204652
866 10621139694852425952112
867 10967228941521180772494
868 11324391844908057721300
869 11692976335980491833784
870 12073341080841972502784
871 12465855806112941330661
872 12870901633789526754990
873 13288871426269814331098
874 13720170141425492638848
875 14165215198437913282914
876 14624436854280276973634
877 15098278591595657812206
878 15587197517857019092094
879 16091664776591004598292
880 16612165970556712089792
881 17149201597694770882927
882 17703287499743640635760
883 18274955324373528125783
884 18864753000741254785204
885 19473245229353158378050
886 20101013986146533423364
887 20748659041715070148044
888 21416798495596778912210
889 22106069326590008694975
890 22817127959024896657288
891 23550650845997864941097
892 24307335069506280641868
893 25087898958534852485847
894 25893082725041652542906
895 26723649118941338854924
896 27580384102045302007840
897 28464097542104459390466
898 29375623926927389654268
899 30315823099769929807350
900 31285581015983108956472
901 32285810522168301608395
902 33317452157841949695118
903 34381474980913974555205
904 35478877416999083737072
905 36610688133922932492621
906 37777966941460672608662
907 38981805717730415826348
908 40223329362299041639208
909 41503696777486308161997
910 42824101877946265143046
911 44185774630078364960640
912 45589982121370621432514
913 47038029661296804424425
914 48531261913895267501272
915 50071064063724300400703
916 51658863015348869924496
917 53296128628130021536973
918 54984374986501219582464
919 56725161707582928548128
920 58520095286351412710840
921 60370830480296918511901
922 62279071733821346053344
923 64246574644398458897008
924 66275147470783450523325
925 68366652685387025786565
926 70523008571140272230692
927 72746190865062024188166
928 75038234448897367187680
929 77401235089140187945984
930 79837351226853887102540
931 82348805819709253419147
932 84937888236702374858500
933 87606956208082815641480
934 90358437831007183595766
935 93194833633564941951061
936 96118718697747543701522
937 99132744844130033877647
938 102239642878896082330284
939 105442224906103834585829
940 108743386705887597564108
941 112146110181627241126347
942 115653465876848808083364
943 119268615565029273023340
944 122994814913142107046746
945 126835416222264545575114
946 130793871246161350708246
947 134873734091321167412850
948 139078664199443666918690
949 143412429416016390586888
950 147878909146068470593884
951 152482097600910951049986
952 157226107137045781870776
953 162115171691232420511336
954 167153650312995272754336
955 172346030798748945123802
956 177696933428932331680632
957 183211114812525818777733
958 188893471840457444382408
959 194749045752479349829259
960 200783026319142608736792
961 207000756143669062843665
962 213407735085478366212140
963 220009624810396915939326
964 226812253469445314940868
965 233821620511470396291525
966 241043901631665709471970
967 248485453861497726045366
968 256152820802238241148408
969 264052738007883936811715
970 272192138519830018981296
971 280578158559355716970538
972 289218143380465420403664
973 298119653289433846531902
974 307290469833786902448182
975 316738602167371721386877
976 326472293594447085252706
977 336500028299768018250833
978 346830538267807635443380
979 357472810398426330284106
980 368436093822356283486328
981 379729907424164484571699
982 391364047576300913979918
983 403348596092265848182292
984 415693928402756149185576
985 428410721963213835894820
986 441509964896905382992866
987 455002964882363889036971
988 468901358289607382434464
989 483217119574394754980659
990 497962570935234567322154
991 513150392242859112558625
992 528793631247199074652814
993 544905714072044711776235
994 561500456002768125465384
995 578592072577789891108990
996 596195190989524037425994
997 614324861806007011242690
998 632996571019325371692976
999 652226252432596501761017
1000 672030300392020355685888