-1 1
0 0
1 2
2 2
3 5
4 4
5 9
6 8
7 16
8 16
9 25
10 26
11 44
12 44
13 67
14 70
15 103
16 108
17 155
18 166
19 230
20 248
21 333
22 362
23 482
24 524
25 680
26 748
27 959
28 1052
29 1330
30 1468
31 1834
32 2028
33 2500
34 2770
35 3394
36 3760
37 4561
38 5066
39 6100
40 6772
41 8102
42 9000
43 10702
44 11888
45 14048
46 15612
47 18360
48 20396
49 23865
50 26516
51 30891
52 34300
53 39798
54 44180
55 51070
56 56672
57 65263
58 72392
59 83109
60 92128
61 105428
62 116824
63 133302
64 147612
65 167982
66 185908
67 211025
68 233404
69 264277
70 292126
71 330038
72 364564
73 410975
74 453700
75 510421
76 563092
77 632267
78 697060
79 781261
80 860752
81 963016
82 1060300
83 1184336
84 1303092
85 1453181
86 1597882
87 1779236
88 1955084
89 2173818
90 2387114
91 2650509
92 2908692
93 3225299
94 3537214
95 3917269
96 4293332
97 4748750
98 5201412
99 5746376
100 6290164
101 6941300
102 7593504
103 8370408
104 9151300
105 10076886
106 11010380
107 12111719
108 13225796
109 14534365
110 15862054
111 17414918
112 18994676
113 20835046
114 22712104
115 24890510
116 27117644
117 29692919
118 32331824
119 35372798
120 38495320
121 42081812
122 45771962
123 49997072
124 54352288
125 59324115
126 64458018
127 70302091
128 76346532
129 83208326
130 90316440
131 98364890
132 106714072
133 116144309
134 125940428
135 136978588
136 148459464
137 161366733
138 174807772
139 189885866
140 205605064
141 223201966
142 241566508
143 262083858
144 283517080
145 307416996
146 332407202
147 360222166
148 389331032
149 421673299
150 455547628
151 493121031
152 532504144
153 576116772
154 621862766
155 672442670
156 725531692
157 784142405
158 845699368
159 913560424
160 984873960
161 1063381649
162 1145928442
163 1236680990
164 1332150880
165 1436975669
166 1547301744
167 1668288169
168 1795679604
169 1935213001
170 2082194066
171 2242997993
172 2412449048
173 2597629765
174 2792837564
175 3005936382
176 3230647400
177 3475698249
178 3734181176
179 4015778108
180 4312892696
181 4636261745
182 4977539124
183 5348624560
184 5740353308
185 6165910434
186 6615239072
187 7102941544
188 7617989224
189 8176547733
190 8766531906
191 9405831102
192 10081208972
193 10812455972
194 11585086856
195 12420984878
196 13304307240
197 14259244989
198 15268482242
199 16358750272
200 17511135724
201 18755166843
202 20070200364
203 21488843153
204 22988576196
205 24605395368
206 26314754988
207 28156376354
208 30103521180
209 32200010982
210 34416739092
211 36802033805
212 39324231788
213 42036615691
214 44904766560
215 47987411764
216 51247159580
217 54748721486
218 58451508508
219 62426802285
220 66630572616
221 71141320357
222 75911317232
223 81026988924
224 86436636116
225 92235384479
226 98367277100
227 104936988199
228 111883993948
229 119323448747
230 127189944272
231 135610128405
232 144513366764
233 154038919240
234 164110569248
235 174881405716
236 186269255516
237 198442371187
238 211312234678
239 225063722290
240 239601556768
241 255128838872
242 271543112264
243 289067444630
244 307591755680
245 327360997609
246 348257009576
247 370548716247
248 394109404288
249 419234258070
250 445787531110
251 474093167638
252 504005886096
253 535881127951
254 569563580212
255 605443163265
256 643354019228
257 683723821562
258 726375656924
259 771778517974
260 819743925696
261 870786094552
262 924704481574
263 982062786190
264 1042647902560
265 1107077678220
266 1175125982366
267 1247469891438
268 1323869800652
269 1405067584146
270 1490809756264
271 1581909056632
272 1678097756196
273 1780266093729
274 1888131799618
275 2002669854120
276 2123583205924
277 2251939492359
278 2387426748290
279 2531213893903
280 2682974007036
281 2843986731278
282 3013910277748
283 3194145300792
284 3384335381704
285 3586013423348
286 3798808797920
287 4024398920494
288 4262399558896
289 4514646033657
290 4780741378044
291 5062693412798
292 5360093560292
293 5675138096662
294 6007408283632
295 6359306238904
296 6730404875648
297 7123331131534
298 7537651811686
299 7976239376151
300 8438657213764
301 8928045901073
302 9443968679292
303 9989858860108
304 10565283396764
305 11173995223372
306 11815569577182
307 12494108309194
308 13209200300816
309 13965328279005
310 14762101038456
311 15604417027668
312 16491912201988
313 17429938738035
314 18418168178492
315 19462447833156
316 20562494502776
317 21724695813537
318 22948824946660
319 24241859062572
320 25603640448768
321 27041789463757
322 28556232046788
323 30155290238879
324 31838990153956
325 33616419270808
326 35487722705384
327 37462822810992
328 39542005006712
329 41736102237954
330 44045564351972
331 46482217342657
332 49046702726136
333 51751929401041
334 54598761293188
335 57601288087811
336 60760630680372
337 64092166189672
338 67597311401146
339 71292846980554
340 75180529244152
341 79278668936480
342 83589410863742
343 88132733595548
344 92911225246484
345 97946682237986
346 103242197340796
347 108821548180750
348 114688400672828
349 120868691531366
350 127366736347308
351 134210824524172
352 141406006607376
353 148983135529921
354 156948091832748
355 165334521416542
356 174149240598848
357 183428938006959
358 193181483416532
359 203446879993188
360 214234181673140
361 225587001992756
362 237515724283172
363 250067894288977
364 263255385805988
365 277130027068064
366 291705360969892
367 307037879249142
368 323142991816628
369 340082268450370
370 357873205272148
371 376582901012727
372 396231180475760
373 416891161835666
374 438585266852434
375 461393166508992
376 485340175935900
377 510513099079889
378 536940471918156
379 564716862123913
380 593874388039128
381 624516066941679
382 656677998496030
383 690472395257022
384 725939778090500
385 763202365504168
386 802305584586368
387 843382540899064
388 886484102005800
389 931755218347730
390 979252786357616
391 1029134642211118
392 1081464358836480
393 1136413789309584
394 1194053895651820
395 1254571776949596
396 1318046567854856
397 1384681948962324
398 1454566089053230
399 1527920700988257
400 1604843934160596
401 1685577109839226
402 1770229397690628
403 1859063439252502
404 1952200565913960
405 2049926598798338
406 2152376283850728
407 2259860640955545
408 2372529204932532
409 2490720387102522
410 2614600018587396
411 2744536282749461
412 2880712959433144
413 3023530588833948
414 3173192710523000
415 3330135027332432
416 3494582822545140
417 3667010007324054
418 3847665781560786
419 4037065570388370
420 4235484869018592
421 4443484204102675
422 4661367969826136
423 4889745687176150
424 5128953497782020
425 5379654141088399
426 5642218621847488
427 5917367480626758
428 6205509992048676
429 6507429469292108
430 6823577180909166
431 7154804605287186
432 7501609074286532
433 7864916080451648
434 8245273464954248
435 8643687077418442
436 9060760123845588
437 9497585689433662
438 9954827646702600
439 10433673774358772
440 10934854398509676
441 11459660077142213
442 12008893905349780
443 12583957985772560
444 13185735072198872
445 13815748313243732
446 14474967636362220
447 15165047533721898
448 15887053300624964
449 16642781932893574
450 17433403026693776
451 18260868174424200
452 19126461008921576
453 20032300822009174
454 20979795891602300
455 21971247404363199
456 23008199839207612
457 24093151655372713
458 25227796118675054
459 26414845617217845
460 27656155907354496
461 28954671346158392
462 30312425098315356
463 31732613025874062
464 33217461937400012
465 34770440354251120
466 36393986394932370
467 38091864144168374
468 39866742248148776
469 41722705151178409
470 43662672929291770
471 45691077227640227
472 47811112280418268
473 50027585986563318
474 52343991447920632
475 54765544259765580
476 57296063248969828
477 59941205733008417
478 62705145450091990
479 65594018257113994
480 68612384513615248
481 71766898449668672
482 75062541492261332
483 78506529336856263
484 82104301887564620
485 85863682918745568
486 89790611432716028
487 93893569698780355
488 98179039916613500
489 102656217374406622
490 107332175335478772
491 112216881066853188
492 117318050839971008
493 122646487651310044
494 128210607141382428
495 134022116958581716
496 140090193252637360
497 146427522831337124
498 153044108667080376
499 159953697262256234
500 167167190322847144
501 174699481088343894
502 182562447965718518
503 190772224996807110
504 199341751807497852
505 208288504886490536
506 217626576682931080
507 227374895954352612
508 237548807239136824
509 248168810210250783
510 259251609046426956
511 270819402501327372
512 282890370901318964
513 295488550515129583
514 308633724005407888
515 322351914666062748
516 336664644146450240
517 351600084221515277
518 367181643484367692
519 383439816527682870
520 400400059059288400
521 418095376717204142
522 436553445690439660
523 455809985864628503
524 475895081528142568
525 496847386161205191
526 518699595161503878
527 541493532353070139
528 565264723871222680
529 590058419390281435
530 615913213355461560
531 642878057011313952
532 670994870053075212
533 700316602799762919
534 730888778042649888
535 762768666149514921
536 796005693413994116
537 830661796514699820
538 866790629998110872
539 904459170356661460
540 943725651402882016
541 984662492289708547
542 1027332885442092892
543 1071815127123065576
544 1118177778273520948
545 1166505480753295136
546 1216872606878886492
547 1269370649243175014
548 1324080269933543212
549 1381100356875448643
550 1440518378636608720
551 1502441205560337122
552 1566963670705476556
553 1634201259655690700
554 1704256772492674182
555 1777254992092337416
556 1853307336069758088
557 1932548619633256401
558 2015099580146119048
559 2101105857211101238
560 2190698265862809648
561 2284034123522561736
562 2381255140836835188
563 2482531232492126650
564 2588015887335287488
565 2697892607796997488
566 2812327613146309530
567 2931519060448170342
568 3055646926601862768
569 3184925172391958562
570 3319548640303336748
571 3459748332326426232
572 3605735151423190808
573 3757758473348544938
574 3916046550024077828
575 4080868565760930656
576 4252471510661598760
577 4431145922310689803
578 4617159026639614224
579 4810824377404390284
580 5012431050691893792
581 5222317406378495042
582 5440796110584467960
583 5668232255820191759
584 5904963973195280528
585 6151385161152387874
586 6407861436060666452
587 6674817733342369564
588 6952649331199148920
589 7241814602600091417
590 7542740832263838388
591 7855922413419897898
592 8181821162769570584
593 8520970272219716858
594 8873868810312789280
595 9241091756288610994
596 9623178359388917896
597 10020748600683607117
598 10434385063655030668
599 10864756188273625712
600 11312491287314122828
601 11778310977242518058
602 12262894954756929470
603 12767020010185657260
604 13291420157737936536
605 13836932659394036896
606 14404350080220734176
607 14994574774195765283
608 15608462412659487260
609 16246985408230618923
610 16911067439948004358
611 17601756317461052262
612 18320049000612013248
613 19067074433503346015
614 19843908529110553192
615 20651767531686604546
616 21491812408421062244
617 22365353329045128200
618 23273642876467869360
619 24218092264447609086
620 25200052747496016432
621 26221044231178788634
622 27282524228278424458
623 28386129551758867103
624 29533432129147264492
625 30726194505549577308
626 31966111791356697000
627 33255081741997868564
628 34594932075319352136
629 35987705936147258372
630 37435373778902685006
631 38940135068590867200
632 40504113881341184888
633 42129677739272264445
634 43819116036542980288
635 45574976953770999352
636 47399727769755966412
637 49296110851891619529
638 51266784863850920820
639 53314700881823688833
640 55442723456030057392
641 57654027958814319178
642 59951700402716364340
643 62339157185564416174
644 64819722509893040844
645 67397071752369796201
646 70074785268427913178
647 72856816678779902916
648 75747021779103672448
649 78749653105223703452
650 81868862600387951596
651 85109223893066367138
652 88475207303640164592
653 91971731344908224662
654 95603608575671888844
655 99376127914100048858
656 103294469767604160032
657 107364320833412831718
658 111591256852066827754
659 115981391658089323373
660 120540725818215626816
661 125275831788157791654
662 130193166606103978180
663 135299795109448805682
664 140602664758961728664
665 146109368972285597154
666 151827382054213012204
667 157764864811949157975
668 163929857461973749840
669 170331129805810296016
670 176977329873696512472
671 183877881059163112636
672 191042084143955134476
673 198480063915417725600
674 206201822095522933264
675 214218236097139033189
676 222540060252367068680
677 231178979502621165694
678 240146556187418894224
679 249455341609102547603
680 259117765502516065444
681 269147308568533172909
682 279557331597313541432
683 290362312225924087760
684 301576610532788949872
685 313215773444014358296
686 325295233453861926818
687 337831684282258309315
688 350841709205290214704
689 364343231753300937133
690 378354069956079477248
691 392893466067297867846
692 407980562840918991640
693 423636016474013725560
694 439880390833454755670
695 456735858025839932556
696 474224506286362385060
697 492370132812207690394
698 511196460808111965638
699 530729029458660805110
700 550993315397017742508
701 572016724942687585596
702 593826615020638379452
703 616452393054816715069
704 639923432113957063704
705 664271284128112656278
706 689527483774217406000
707 715725880973747992940
708 742900327755034101564
709 771087136295620446707
710 800322642708782159020
711 830645797214838730067
712 862095598495730641664
713 894713822916303494836
714 928542322772392687440
715 963625901836641075502
716 1000009470491732270528
717 1037741075246498078604
718 1076868903395926166670
719 1117444474542985347054
720 1159519487060097892208
721 1203149180061214291540
722 1248389013554766603698
723 1295298209739906142100
724 1343936258337763361416
725 1394366646536533098680
726 1446653180565196947052
727 1500863914085236340936
728 1557067276628042742428
729 1615336210727600663638
730 1675744097378574709530
731 1738369112725435866510
732 1803289940211738919912
733 1870590358188117757773
734 1940354727913490413104
735 2012672824018257927479
736 2087635086984077908956
737 2165337709000914463876
738 2245877638992367922380
739 2329357937037193035584
740 2415882519420927798208
741 2505561795455622763340
742 2598507139424332793300
743 2694836824328544282486
744 2794670206948760569424
745 2898133973779119470450
746 3005356024753442117300
747 3116472047392317563628
748 3231619084038265478816
749 3350942451044015941963
750 3474588973621270482276
751 3602714267741695501990
752 3735475625929792842000
753 3873039680432222365588
754 4015574922474788970724
755 4163259766183049046986
756 4316274682974797613468
757 4474810686687651200327
758 4639061063889902861128
759 4809230301690932452721
760 4985525393823158349252
761 5168165233681167975683
762 5357371475053697283696
763 5553378414059525846245
764 5756423382389177031148
765 5966757142982465134671
766 6184633792572722090576
767 6410321697184975965676
768 6644092879658914539884
769 6886234522340843599857
770 7137037814093009189602
771 7396810048909419018226
772 7665862905696321183512
773 7944525172964885879356
774 8233130433387974488042
775 8532030446214528174471
776 8841582207268935861240
777 9162162022296147910038
778 9494151911669140290154
779 9837954409513639455062
780 10193978280923720931488
781 10562654083434304255531
782 10944419163011882791828
783 11339734016245191844034
784 11749066529774547583864
785 12172909183460499546986
786 12611762496237934449732
787 13066153112503016169571
788 13536616415624073076336
789 14023715541863143115808
790 14528023120941107706448
791 15050141263986143774814
792 15590682388632164513780
793 16150290229767294532820
794 16729619704638669040830
795 17329358997564415277018
796 17950208418420522292588
797 18592903614985202316531
798 19258193375990636853960
799 19946864027394192563680
800 20659716128885485730076
801 21397590113130554261124
802 22161341822228275104296
803 22951869451857103130744
804 23770087871670023712396
805 24616956939295226847440
806 25493454546040681254160
807 26400606368866360801188
808 27339457580033411616464
809 28311104108483427931085
810 29316662949207666931202
811 30357305008945235190359
812 31434223948059884903700
813 32548670689111436206625
814 33701920720905540325940
815 34895310352308931252540
816 36130202404875538230660
817 37408024298274568705528
818 38730232054488387016584
819 40098350305411219314078
820 41513934528054187710464
821 42978613069260916309878
822 44494047527636200888784
823 46061976894922023209478
824 47684175996482139658336
825 49362501853697950810718
826 51098850090784437752672
827 52895203627610110882997
828 54753586956383040930680
829 56676117279583637313022
830 58664956555635265516568
831 60722365202173743676928
832 62850651805197447786812
833 65052229513695330199198
834 67329563301947875810524
835 69685229187608048889916
836 72121858931788810664496
837 74642202219051743696990
838 77249068674659773978632
839 79945393151589603568389
840 82734174938840702430792
841 85618546307564381580343
842 88601708778592240587844
843 91687005087081037739444
844 94877852371445765057388
845 98177817723571299087827
846 101590548155096282786126
847 105119849908255548489904
848 108769615048950652104444
849 112543904721678328942086
850 116446872212030156295788
851 120482850337949287525614
852 124656270817213822311064
853 128971755996465451526535
854 133434034351836364014942
855 138048036766828038954568
856 142818807986527507977284
857 147751607665503085865822
858 152851817588008936084472
859 158125047717627651839788
860 163577038987469255267304
861 169213774594350575366553
862 175041378154241396702856
863 181066230495350427863609
864 187294862964942850507244
865 193734079987826777806798
866 200390847301147487243588
867 207272420557461362650736
868 214386228254187045237792
869 221740006673743007849878
870 229341677263987736897032
871 237199488221809395217070
872 245321886070099510997004
873 253717664205747878650666
874 262395828407448805112172
875 271365752684301505198788
876 280637038437026649846636
877 290219677959334010924385
878 300123906962910588819476
879 310360376100425635867296
880 320939996551920544890704
881 331874119955811984566380
882 343174376741046877576748
883 354852864870772793538954
884 366921980590798187660980
885 379394616409763656474401
886 392283983920045455669142
887 405603821458321096094977
888 419368208640050489754680
889 433591784165326474790596
890 448289551692438814225688
891 463477108275877236543584
892 479170441188204739770328
893 495386167500083797344705
894 512141321442730858715460
895 529453605663912198841587
896 547341168705595628223548
897 565822868495061078547523
898 584918039493980317834264
899 604646769010160355459690
900 625029653555139522242744
901 646088088589683858657381
902 667844013607058716200276
903 690320215954285428476556
904 713540064137501735492352
905 737527826391218558604782
906 762308391680587883050192
907 787907603722538641672715
908 814351969137295703513516
909 841669007658385151873876
910 869886946862358315613960
911 899035089339307708583391
912 929143493405411319865564
913 960243358041862738750410
914 992366688969526947678862
915 1025546702202135110203340
916 1059817474835997221617888
917 1095214368103022527847712
918 1131773662201027274037420
919 1169532999773696130450548
920 1208531004078516330368640
921 1248807743864279413267404
922 1290404334144024309103214
923 1333363423486180751714506
924 1377728776629071493185064
925 1423545785249412537868414
926 1470861031622864529896022
927 1519722823983426809952033
928 1570180740401195473839028
929 1622286189898321222286025
930 1676091935680478950036240
931 1731652683229608866663161
932 1789024581989582826107088
933 1848265841713026266734484
934 1909436211664229077040086
935 1972597626557068606757496
936 2037813662299307027170280
937 2105150212921125548421985
938 2174674921844522695082836
939 2246457891267353227511449
940 2320571087899538654091096
941 2397089086335915963326264
942 2476088448157335686457920
943 2557648500897203660670907
944 2641850689360216568809612
945 2728779391862371195006386
946 2818521242573011765312038
947 2911165986786437627504734
948 3006805773044050189267528
949 3105536049277672060107783
950 3207454823417820249940836
951 3312663602334623194814808
952 3421266619585546829858600
953 3533371819169536873044632
954 3649090049012817177057536
955 3768536091645774494749738
956 3891827821968666942036844
957 4019087287058999174227222
958 4150439826700050745398296
959 4286015204629260535834364
960 4425946690251338378316832
961 4570372243745698720461790
962 4719433557322478897452472
963 4873277296719550644792590
964 5032054100293959017577184
965 5195919879556727192031392
966 5365034774323971075190692
967 5539564515060835685502656
968 5719679332245753085239548
969 5905555383423658909882299
970 6097373614863461070546480
971 6295321256355444039133658
972 6499590633165918902952512
973 6710380731754705899150455
974 6927895959952055354454292
975 7152347786919590690166332
976 7383953449392836563691832
977 7622937669363307182501198
978 7869531304145259843054688
979 8123973145418038906843564
980 8386508510787898905099312
981 8657391127998592308038913
982 8936881665568179521346200
983 9225249706152521297210919
984 9522772213742817154037744
985 9829735600351491387486550
986 10146434127158676796883488
987 10473172068883340683929066
988 10810262046165957196613228
989 11158027292190002093262910
990 11516799913483529438572534
991 11886923263567780666704841
992 12268750129252197110640208
993 12662645216308271714896141
994 13068983258220579040444420
995 13488151619115596339221210
996 13920548321815509747504312
997 14366584773494017843319199
998 14826683709759865486035086
999 15301282048765108185088550
1000 15790828747921422657837676