-1 1
0 0
1 2
2 2
3 4
4 5
5 7
6 9
7 13
8 16
9 22
10 27
11 36
12 43
13 56
14 68
15 87
16 104
17 130
18 156
19 193
20 230
21 281
22 333
23 404
24 477
25 572
26 673
27 802
28 940
29 1113
30 1299
31 1531
32 1780
33 2085
34 2418
35 2820
36 3259
37 3784
38 4362
39 5047
40 5799
41 6685
42 7662
43 8806
44 10066
45 11532
46 13152
47 15026
48 17098
49 19482
50 22120
51 25143
52 28487
53 32305
54 36531
55 41337
56 46654
57 52682
58 59352
59 66892
60 75228
61 84625
62 95014
63 106697
64 119603
65 134080
66 150069
67 167965
68 187716
69 209778
70 234114
71 261246
72 291150
73 324433
74 361096
75 401830
76 446668
77 496408
78 551124
79 611731
80 678348
81 752035
82 832977
83 922388
84 1020530
85 1128801
86 1247564
87 1378428
88 1521867
89 1679737
90 1852659
91 2042770
92 2250858
93 2479388
94 2729361
95 3003609
96 3303381
97 3631945
98 3990854
99 4383864
100 4812875
101 5282229
102 5794248
103 6353926
104 6964081
105 7630467
106 8356500
107 9148799
108 10011469
109 10952140
110 11975730
111 13091024
112 14303890
113 15624445
114 17059680
115 18621228
116 20317388
117 22161544
118 24163527
119 26338726
120 28698735
121 31261262
122 34039966
123 37055199
124 40323004
125 43866769
126 47705328
127 51865531
128 56369418
129 61247828
130 66526521
131 72240887
132 78420966
133 85107368
134 92335088
135 100150683
136 108594846
137 117720952
138 127576260
139 138221914
140 149712706
141 162118674
142 175503273
143 189946670
144 205522246
145 222321726
146 240429902
147 259951653
148 280984810
149 303649258
150 328057761
151 354347287
152 382647644
153 413115249
154 445899414
155 481178644
156 519124489
157 559940590
158 603823882
159 651006537
160 701714385
161 756212024
162 814758222
163 877654345
164 945196606
165 1017728103
166 1095587661
167 1179165662
168 1268849316
169 1365082613
170 1468307726
171 1579029335
172 1697751952
173 1825048973
174 1961495646
175 2107743067
176 2264446616
177 2432345286
178 2612185239
179 2804804789
180 3011052798
181 3231879814
182 3468250922
183 3721243349
184 3991953528
185 4281601678
186 4591432692
187 4922828046
188 5277200218
189 5656112537
190 6061166658
191 6494130808
192 6956819977
193 7451233225
194 7979426102
195 8543657487
196 9146253945
197 9789766799
198 10476827853
199 11210317339
200 11993210566
201 12828757625
202 13720320342
203 14671564384
204 15686286156
205 16768618179
206 17922845352
207 19153624353
208 20465788760
209 21864583584
210 23355458526
211 24944318569
212 26637304834
213 28441062426
214 30362508162
215 32409116660
216 34588674459
217 36909585647
218 39380611590
219 42011197280
220 44811196062
221 47791218315
222 50962340250
223 54336476275
224 57926071304
225 61744498471
226 65805734136
227 70124782440
228 74717332358
229 79600211116
230 84791022280
231 90308629893
232 96172776900
233 102404602216
234 109026238539
235 116061364383
236 123534780662
237 131473000157
238 139903801872
239 148856860332
240 158363277018
241 168456252433
242 179170593520
243 190543431268
244 202613703466
245 215422921094
246 229014625497
247 243435206644
248 258733334076
249 274960830855
250 292172077266
251 310424944177
252 329780168864
253 350302352064
254 372059305090
255 395123114736
256 419569461278
257 445478756137
258 472935429924
259 502029147776
260 532854067132
261 565510136457
262 600102322026
263 636741995700
264 675546130635
265 716638784613
266 760150264308
267 806218710639
268 854989231804
269 906615598171
270 961259343915
271 1019091579151
272 1080292060630
273 1145051129744
274 1213568752665
275 1286056592970
276 1362737022318
277 1443845337658
278 1529628743204
279 1620348722597
280 1716279993726
281 1817713047492
282 1924953076965
283 2038322694583
284 2158160838186
285 2284825680018
286 2418693512067
287 2560161860663
288 2709648354546
289 2867594060726
290 3034462338650
291 3210742413584
292 3396948221458
293 3593622237881
294 3801334318533
295 4020685802583
296 4252308355016
297 4496868365352
298 4755065798385
299 5027638910356
300 5315363116153
301 5619056047511
302 5939576445206
303 6277829584974
304 6634766205310
305 7011388329537
306 7408748240514
307 7827954728869
308 8270172127910
309 8736627021446
310 9228607353186
311 9747469629421
312 10294638119682
313 10871612593192
314 11479967629092
315 12121360927677
316 12797532751570
317 13510314857038
318 14261630089014
319 15053501980800
320 15888054529190
321 16767522515940
322 17694251491332
323 18670708873934
324 19699484175469
325 20783300940872
326 21925017250022
327 23127638564264
328 24394318545297
329 25728372881034
330 27133280465250
331 28612698280645
332 30170462988582
333 31810606954577
334 33537360301905
335 35355168170692
336 37268693295848
337 39282834599548
338 41402730359238
339 43633778240592
340 45981639129024
341 48452258720462
342 51051872096226
343 53787026997284
344 56664589231888
345 59691767770605
346 62876121084126
347 66225584206339
348 69748476110484
349 73453528901632
350 77349896348688
351 81447185379649
352 85755465899991
353 90285304779792
354 95047777100715
355 100054502838327
356 105317659695246
357 110850022700421
358 116664978799644
359 122776569610832
360 129199507961079
361 135949224058413
362 143041884181168
363 150494440546843
364 158324652380890
365 166551139788124
366 175193407448208
367 184271902818958
368 193808042730358
369 203824276278582
370 214344114614226
371 225392198914140
372 236994333688778
373 249177560252731
374 261970193905046
375 275401903352448
376 289503752150859
377 304308284575210
378 319849571744058
379 336163304469343
380 353286844526522
381 371259325063991
382 390121707521442
383 409916890224740
384 430689771503151
385 452487367149438
386 475358880334432
387 499355828666609
388 524532121558282
389 550944197682251
390 578651110500357
391 607714676979162
392 638199572057252
393 670173489555024
394 703707246424767
395 738874956864814
396 775754147273538
397 814425944664019
398 854975203321962
399 897490708706089
400 942065316900092
401 988796175284226
402 1037784875965146
403 1089137694607456
404 1142965759131630
405 1199385308211267
406 1258517876639580
407 1320490575119637
408 1385436293823840
409 1453494005241382
410 1524808987584686
411 1599533152600887
412 1677825290624704
413 1759851425419746
414 1845785082830112
415 1935807674883933
416 2030108794166745
417 2128886629605206
418 2232348288863898
419 2340710248423067
420 2454198706499658
421 2573050070249446
422 2697511341923354
423 2827840646252214
424 2964307652783160
425 3107194146757216
426 3256794490817241
427 3413416242955376
428 3577380661055952
429 3749023371784368
430 3928694921717136
431 4116761501355310
432 4313605546911892
433 4519626523975282
434 4735241584362892
435 4960886414323200
436 5197015951236322
437 5444105301642030
438 5702650522963104
439 5973169617071062
440 6256203382641610
441 6552316490434605
442 6862098412352640
443 7186164585105475
444 7525157422549514
445 7879747574947113
446 8250635031704226
447 8638550484010827
448 9044256525683284
449 9468549127601367
450 9912258944991378
451 10376252912745777
452 10861435668170256
453 11368751277002405
454 11899184781380715
455 12453764067159193
456 13033561547656350
457 13639696183712086
458 14273335314630170
459 14935696843332102
460 15628051226837520
461 16351723839857151
462 17108097138151974
463 17898613214962489
464 18724776151671258
465 19588154782611945
466 20490385248620142
467 21433173986991915
468 22418300504766637
469 23447620611936740
470 24523069432655150
471 25646664901222565
472 26820511030875645
473 28046801693622109
474 29327824167835038
475 30665963224659793
476 32063704977339476
477 33523641298709439
478 35048473997000517
479 36641019590856780
480 38304213838336329
481 40041116897965057
482 41854918239770642
483 43748942223110574
484 45726653420865209
485 47791662647185442
486 49947732728426385
487 52198785016540375
488 54548905642987294
489 57002352556288523
490 59563562297997723
491 62237157605921537
492 65027954754312012
493 67940971767488694
494 70981436369716960
495 74154794857428546
496 77466720707815534
497 80923124161584765
498 84530161543122153
499 88294245609726223
500 92222055640326004
501 96320548611464097
502 100596970115981916
503 105058866430660534
504 109714096331066946
505 114570844120762890
506 119637632413633996
507 124923336199941571
508 130437196672984834
509 136188836413054250
510 142188274341209202
511 148445942108394194
512 154972700265507490
513 161779855951622807
514 168879180376385922
515 176282927908450968
516 184003854973632128
517 192055240652381553
518 200450907105051380
519 209205241795520298
520 218333219563457637
521 227850426600116800
522 237773084296653300
523 248118075107660440
524 258902968314452844
525 270146047922203616
526 281866340487682002
527 294083645206881750
528 306818563968080076
529 320092533798712187
530 333927859316826122
531 348347747718682662
532 363376343814809192
533 379038767753485097
534 395361152841682131
535 412370686214266494
536 430095649655254458
537 448565463438332238
538 467810730380094564
539 487863283094395280
540 508756231526689320
541 530524013882898052
542 553202447912692816
543 576828785793040847
544 601441769448380874
545 627081689689942594
546 653790445882330200
547 681611609662145380
548 710590489283656494
549 740774198264350049
550 772211724767197719
551 804954005546589894
552 839054000751379212
553 874566773572376867
554 911549570878940296
555 950061908998933341
556 990165660632313448
557 1031925147226354009
558 1075407232642580190
559 1120681422624238282
560 1167819965728229082
561 1216897960418489274
562 1267993463812404921
563 1321187606973073883
564 1376564712060273738
565 1434212416436736000
566 1494221798857239750
567 1556687513049202343
568 1621707923620122639
569 1689385249821240556
570 1759825711903539726
571 1833139685825126935
572 1909441860839606450
573 1988851405963473300
574 2071492139638094826
575 2157492708833012933
576 2246986771684328857
577 2340113190173697043
578 2437016226711845250
579 2537845751401465238
580 2642757453605272332
581 2751913064874322566
582 2865480586615700832
583 2983634529846309312
584 3106556160156376138
585 3234433755532882671
586 3367462869901925769
587 3505846610356017166
588 3649795920651364467
589 3799529879269755290
590 3955276004346422738
591 4117270574100503013
592 4285758954775832008
593 4460995945084567671
594 4643246128857460221
595 4832784245263608660
596 5029895567989031146
597 5234876303122278701
598 5448033996811003956
599 5669687962838798233
600 5900169720849573009
601 6139823455786193419
602 6389006488922420440
603 6648089771489276237
604 6917458390914787096
605 7197512101130301357
606 7488665866589979876
607 7791350431927176556
608 8106012906509380026
609 8433117376305125727
610 8773145531926659510
611 9126597325771459127
612 9493991646715212780
613 9875867025809860909
614 10272782361014432936
615 10685317674964480080
616 11114074893368954502
617 11559678658615094845
618 12022777165716861684
619 12504043035785790823
620 13004174213691727822
621 13523894905715124972
622 14063956543375089672
623 14625138789883247166
624 15208250574908799310
625 15814131174779825486
626 16443651323291443810
627 17097714370948621734
628 17777257477283187778
629 18483252854804476467
630 19216709048675350446
631 19978672271434845001
632 20770227776294279910
633 21592501289121309776
634 22446660482056338771
635 23333916509701782806
636 24255525590228328438
637 25212790653198823533
638 26207063035835385538
639 27239744250426167292
640 28312287803960169903
641 29426201093619493930
642 30583047358561164702
643 31784447712589663861
644 33032083237476674060
645 34327697162541321627
646 35673097109552014164
647 37070157429617517832
648 38520821610412872084
649 40027104781506148920
650 41591096295395666129
651 43214962413167993236
652 44900949071629601056
653 46651384762014756401
654 48468683496344620356
655 50355347892782488344
656 52313972355260862676
657 54347246380019856068
658 56457957963511639602
659 58648997145659577487
660 60923359662083864454
661 63284150740688404465
662 65734589015355634184
663 68278010593609660398
664 70917873250106945079
665 73657760784342657671
666 76501387513521872904
667 79452602940576434580
668 82515396567343935214
669 85693902894550146131
670 88992406577655772650
671 92415347781940308648
672 95967327704905438398
673 99653114311176263029
674 103477648246981451102
675 107446048981273559677
676 111563621139546452801
677 115835861079374957099
678 120268463672686707474
679 124867329345839895896
680 129638571341447302462
681 134588523255157392441
682 139723746810240828930
683 145051039925422875358
684 150577445037695911964
685 156310257737879039367
686 162257035679523074424
687 168425607821355752882
688 174824083962708248872
689 181460864634651650755
690 188344651305106488216
691 195484456963298765095
692 202889617040627470038
693 210569800736077930566
694 218535022702028439486
695 226795655161467023976
696 235362440411229770742
697 244246503785287317312
698 253459367031437352348
699 263012962178572794951
700 272919645846613568356
701 283192214079554257339
702 293843917652430484674
703 304888477936085176724
704 316340103269238849726
705 328213505925327108588
706 340523919622298709333
707 353287117666579934788
708 366519431678077660950
709 380237770991337590383
710 394459642678400770538
711 409203172292561956391
712 424487125277237687727
713 440330929143419515525
714 456754696358581390968
715 473779248054982340829
716 491426138498893778004
717 509717680433361410856
718 528676971234693506937
719 548327920000167475036
720 568695275505814335732
721 589804655156878559006
722 611682574868489536042
723 634356480004482257378
724 657854777310593046478
725 682206867975554047359
726 707443181755018950747
727 733595212297688069551
728 760695553607293668300
729 788777937785929076707
730 817877273991137631942
731 848029688758644994814
732 879272567621938316846
733 911644598187274518646
734 945185814594146740268
735 979937643526803674925
736 1015942951705721142000
737 1053246095031962445508
738 1091892969312248759109
739 1131931062745364006983
740 1173409510096696597160
741 1216379148749593880603
742 1260892576559380091592
743 1307004211707147045718
744 1354770354478292969478
745 1404249251171753431734
746 1455501160064109997942
747 1508588419643777119668
748 1563575519038759122024
749 1620529170862877653884
750 1679518386403374620670
751 1740614553384956968636
752 1803891516232720421000
753 1869425659079674535295
754 1937295991440969873846
755 2007584236811721009388
756 2080374924110335351826
757 2155755482235954730903
758 2233816337661889080454
759 2314651015345932442002
760 2398356242879586145590
761 2485032058169962243283
762 2574781920576730633578
763 2667712825811396731172
764 2763935424521823200854
765 2863564144883460106716
766 2966717319120978068655
767 3073517314296644858281
768 3184090667290173237232
769 3298568224321991675989
770 3417085284945973473136
771 3539781750879961046127
772 3666802279601727386914
773 3798296443095911173709
774 3934418891681498450208
775 4075329523323444829207
776 4221193658360294267170
777 4372182220070348858077
778 4528471921010910443670
779 4690245455573060081316
780 4857691698689574251454
781 5031005911159356993357
782 5210389951529511877712
783 5396052495020401225221
784 5588209259438824694412
785 5787083238587744114089
786 5992904943122216480886
787 6205912649384212315681
788 6426352656171073979582
789 6654479549995774955040
790 6890556478799433994620
791 7134855434701028874894
792 7387657545751116614547
793 7649253377302658334157
794 7919943242972812090532
795 8200037525838388992060
796 8489857009846649435566
797 8789733222115253389075
798 9100008786111668801628
799 9421037786418574664136
800 9753186145085064554922
801 10096832010304600535817
802 10452366157429963927887
803 10820192403102348851174
804 11200728032516293735178
805 11594404240635672089400
806 12001666587394967573412
807 12422975467741111932609
808 12858806596563800114394
809 13309651509411708180900
810 13776018079057459998759
811 14258431048853119448569
812 14757432582955316906628
813 15273582834408462266375
814 15807460531182841184154
815 16359663581205174160056
816 16930809696497648714022
817 17521537037514717645425
818 18132504877814519322562
819 18764394290208654566615
820 19417908854549767524936
821 20093775388357984620945
822 20792744700470116647225
823 21515592368973034107040
824 22263119543631573310004
825 23036153774135942867979
826 23835549864407571523674
827 24662190754355306872234
828 25516988429351765546106
829 26400884858892251111365
830 27314852964739329955886
831 28259897620089752199437
832 29237056680102691650761
833 30247402045404234686453
834 31292040758945743625760
835 32372116137913459468503
836 33488808941108573978698
837 34643338573581995173370
838 35836964328987789512226
839 37070986671531053842576
840 38346748558022311262682
841 39665636802010641719714
842 41029083480559331003474
843 42438567385737909472347
844 43895615521449867535330
845 45401804647777071435143
846 46958762873519732759349
847 48568171299225904831807
848 50231765711453253823212
849 51951338330676147201767
850 53728739613649310415510
851 55565880112766624884208
852 57464732393299728213558
853 59427333011187340966798
854 61455784552338613887796
855 63552257736260972539500
856 65718993585059944951518
857 67958305660768604735830
858 70272582372144221232315
859 72664289354044932188077
860 75135971920620428378488
861 77690257595593124315508
862 80329858720966894063047
863 83057575147612454343892
864 85876297009176679948947
865 88789007582946990961215
866 91798786239235868745542
867 94908811483108675464547
868 98122364090145649104704
869 101442830340263819781340
870 104873705351424082554378
871 108418596517462869090760
872 112081227052017100863886
873 115865439643007310723431
874 119775200219800714603404
875 123814601837756970578124
876 127987868682441759605642
877 132299360198461875789172
878 136753575345381203576112
879 141355156985936054652915
880 146108896409195051028306
881 151019737994161420984432
882 156092784016660984352916
883 161333299605308515538029
884 166746717849606889549784
885 172338645066282813160959
886 178114866227138516144610
887 184081350554851523708271
888 190244257290241545691206
889 196609941637783091951786
890 203184960893138100400406
891 209976080759852863492962
892 216990281859265333815244
893 224234766441153034229674
894 231716965299456998950545
895 239444544901019310104766
896 247425414731977621543382
897 255667734870184172147508
898 264179923788620395303443
899 272970666398628430197736
900 282048922338279302625145
901 291423934515178087453530
902 301105237909396693240394
903 311102668646340203670604
904 321426373345631841148404
905 332086818756356216998747
906 343094801685165327908508
907 354461459228150375546677
908 366198279313429733290578
909 378317111565950894989023
910 390830178501930650687934
911 403750087065059184274652
912 417089840512395995165000
913 430862850662746154848461
914 445082950515979969650946
915 459764407256784290314428
916 474921935651877100291738
917 490570711854912333640407
918 506726387628710493006876
919 523405104999821892108649
920 540623511355699511896672
921 558398775000311635134599
922 576748601179152369463503
923 595691248590349463590095
924 615245546393550700448334
925 635430911734205978785531
926 656267367795694078340444
927 677775562397880104953283
928 699976787155367487529716
929 722892997215053447320568
930 746546831587116630896598
931 770961634090125811792737
932 796161474925316051347230
933 822171172901861456705490
934 849016318329164609028540
935 876723296599195647403341
936 905319312475934028975783
937 934832415116216964859927
938 965291523840143232139656
939 996726454676678292176486
940 1029167947703771493159306
941 1062647695210048091377389
942 1097198370698619217251198
943 1132853658761568375722316
944 1169648285846964319050012
945 1207618051948538195114763
946 1246799863241260209442944
947 1287231765694621128476352
948 1328952979688322520619174
949 1372003935663941506820944
950 1416426310838830660821498
951 1462263067017677476183665
952 1509558489529633969889820
953 1558358227328403152571150
954 1608709334284941438161880
955 1660660311712235472863838
956 1714261152153665224474362
957 1769563384476599085218838
958 1826620120304695873491711
959 1885486101832868707725245
960 1946217751060465307980764
961 2008873220489057641585662
962 2073512445322598469425794
963 2140197197218911525823863
964 2208991139632606302651490
965 2279959884801101403518084
966 2353171052416318743278508
967 2428694330036601166819519
968 2506601535284032854589506
969 2586966679884743467346976
970 2669866035600146614448814
971 2755378202109890604612589
972 2843584176897406208695783
973 2934567427202204370284531
974 3028413964092914960539146
975 3125212418728782316511365
976 3225054120866897060258896
977 3328033179686640963166007
978 3434246566992105144448800
979 3543794202867928581285975
980 3656779043853001335738698
981 3773307173711670441818867
982 3893487896870791838039664
983 4017433834606690206646706
984 4145261024054496129990369
985 4277089020128592159517794
986 4413041000431003132313636
987 4553243873241391450190643
988 4697828388670112047317514
989 4846929253073190574405126
990 5000685246815566698931914
991 5159239345486957646223142
992 5322738844661853944939166
993 5491335488313798793844195
994 5665185600980931908375418
995 5844450223799067030984322
996 6029295254505068510160078
997 6219891591533253066134986
998 6416415282313700091144840
999 6619047675902011359206348
1000 6827975580055873555713954