-1 1
0 0
1 4
2 4
3 10
4 12
5 26
6 28
7 51
8 60
9 102
10 116
11 189
12 220
13 336
14 396
15 575
16 684
17 974
18 1152
19 1588
20 1892
21 2554
22 3032
23 4017
24 4780
25 6234
26 7404
27 9519
28 11292
29 14368
30 17012
31 21402
32 25308
33 31552
34 37228
35 46039
36 54216
37 66566
38 78232
39 95384
40 111892
41 135624
42 158764
43 191359
44 223592
45 268128
46 312656
47 373189
48 434332
49 516186
50 599640
51 709764
52 822980
53 970552
54 1123284
55 1320079
56 1525164
57 1786548
58 2060456
59 2406247
60 2770484
61 3226192
62 3708384
63 4306680
64 4942412
65 5725238
66 6560008
67 7580655
68 8672764
69 9999260
70 11422676
71 13141147
72 14990088
73 17209644
74 19603268
75 22461452
76 25550408
77 29220772
78 33194612
79 37894758
80 42992164
81 48995184
82 55514992
83 63162221
84 71478604
85 81196186
86 91776100
87 104094491
88 117519624
89 133098672
90 150091944
91 169749372
92 191208080
93 215956996
94 242991388
95 274083525
96 308066188
97 347045668
98 389669424
99 438437487
100 491786800
101 552681284
102 619317996
103 695207083
104 778275284
105 872674094
106 976024480
107 1093232585
108 1221575700
109 1366844822
110 1525932184
111 1705666707
112 1902511388
113 2124511380
114 2367650664
115 2641399595
116 2941213304
117 3278227830
118 3647314744
119 4061559577
120 4515193892
121 5023580304
122 5580252016
123 6203230893
124 6885294800
125 7647568838
126 8482015416
127 9413380394
128 10432758908
129 11569114354
130 12812623548
131 14197166870
132 15711961672
133 17396611760
134 19239346296
135 21286429503
136 23525092812
137 26009348008
138 28725436880
139 31736380137
140 35027476532
141 38672212006
142 42655022980
143 47061554501
144 51875516520
145 57196667672
146 63008191224
147 69426224514
148 76433708660
149 84165779676
150 92605516880
151 101910086763
152 112063223528
153 123247621392
154 135448334440
155 148877636739
156 163522760372
157 179630232720
158 197190553008
159 216489901194
160 237523419444
161 260623172076
162 285790649220
163 313410996703
164 343494181120
165 376486719896
166 412409664912
167 451780483280
168 494634513820
169 541571200648
170 592644074260
171 648547270173
172 709357256580
173 775877508932
174 848213157272
175 927293893910
176 1013260436520
177 1107188108072
178 1209261516408
179 1320723984553
180 1441813969848
181 1573968513464
182 1717491820356
183 1874044243357
184 2044009929040
185 2229306566370
186 2430415105360
187 2649549690398
188 2887308120364
189 3146245927986
190 3427101478136
191 3732823339554
192 4064318498236
193 4424987846692
194 4815940098136
195 5241096541780
196 5701806642616
197 6202590208250
198 6745083328800
199 7334493972611
200 7972798781584
201 8665996664812
202 9416468036416
203 10231120630872
204 11112812701356
205 12069495889972
206 13104592929760
207 14227254161979
208 15441568041380
209 16758060912940
210 18181605053732
211 19724305849956
212 21391957122640
213 23198475669166
214 25150737157232
215 27264735765713
216 29548615475076
217 32020752048312
218 34690774424804
219 37579787855567
220 40699157731128
221 44073116502914
222 47715057597636
223 51652795207955
224 55902088689164
225 60494853211002
226 65449605104552
227 70802953608440
228 76576624318248
229 82812597608646
230 89536330957616
231 96795948671176
232 104621243558744
233 113067365574262
234 122169138954624
235 131989745022438
236 142569841995016
237 153981789217304
238 166273003270540
239 179526328641057
240 193797004343924
241 209179849353264
242 225739149032580
243 243583393403217
244 262787321044704
245 283475024946736
246 305733312801216
247 329704079835462
248 355488057887696
249 383247447072432
250 413099031242652
251 445228162635878
252 479770116607176
253 516936635438696
254 556884280908416
255 599854866562959
256 646029440873836
257 695684072436794
258 749027958442036
259 806376176040450
260 867970259441676
261 934169693234712
262 1005253135746772
263 1081630609259410
264 1163623364928808
265 1251698920832524
266 1346227364757128
267 1447741606090290
268 1556667694273448
269 1673612886231948
270 1799067319099356
271 1933722753702953
272 2078142678193212
273 2233114870674974
274 2399286724224576
275 2577555082313674
276 2768663261523920
277 2973631952931952
278 3193314076222452
279 3428870912046870
280 3681280546008740
281 3951863803768424
282 4241741633269756
283 4552415860247970
284 4885170408720820
285 5241712380910644
286 5623511526896328
287 6032507686366427
288 6470382382605576
289 6939339245816890
290 7441301023158536
291 7978770240084506
292 8553944280346504
293 9169664237454374
294 9828440022537528
295 10533496119065582
296 11287697916975332
297 12094703913245280
298 12957783643122616
299 13881086776864311
300 14868342114723920
301 15924255019985250
302 17053075960466964
303 18260138798835583
304 19550286289868936
305 20929562928211508
306 22403483641183128
307 23978896181856519
308 25662077983069384
309 27460784486097904
310 29382157735096912
311 31434978563388574
312 33627368995764644
313 35969267883106270
314 38469907536725592
315 41140534221400962
316 43991637656473424
317 47035939759673156
318 50285353703109072
319 53754266461946218
320 57456201995807748
321 61407425508235484
322 65623283023071824
323 70122157825270211
324 74921456197308492
325 80041949302733882
326 85503372128945536
327 91329187113654253
328 97541760384369344
329 104167586735243074
330 111232004042776280
331 118764922801861949
332 126795036109864896
333 135356100885075432
334 144480597026946896
335 154206611702660617
336 164570897179338700
337 175616414197814278
338 187384733514327652
339 199924299420006143
340 213282115189765460
341 227512793284076572
342 242669459653794240
343 258813663118265543
344 276005427781839540
345 294314100552201412
346 313807474754519168
347 334563661789465328
348 356659202338388120
349 380182055800788562
350 405218608236378464
351 431867881522111809
352 460227339321888712
353 490408426916506852
354 522521067983956520
355 556690655846802769
356 593041124631788616
357 631713523302652890
358 672847534795493684
359 716601775743308622
360 763133626383036312
361 812621411396823760
362 865242391705335152
363 921196995436483811
364 980684810077570676
365 1043931047321041088
366 1111160360374385056
367 1182625742425555467
368 1258579979122139536
369 1339307197737000756
370 1425091748845103676
371 1516252642080876452
372 1613109633756305872
373 1716020805492557240
374 1825345615852916648
375 1941485900239163661
376 2064845624436332412
377 2195875608126645560
378 2335029696450818052
379 2482813535468298690
380 2639736854304603992
381 2806366649025138460
382 2983275242533521656
383 3171098263824721275
384 3370478125367223724
385 3582127217733932912
386 3806766414608315632
387 4045193938574643225
388 4298218471953487464
389 4566734188284341184
390 4851648012751029436
391 5153961355861133275
392 5474691030073765432
393 5814958267610796146
394 6175902759855635180
395 6558779590427871648
396 6964865820744504048
397 7395566022734424772
398 7852310787436489832
399 8336671599361390413
400 8850250594874934288
401 9394805582578759944
402 9972130324235552584
403 10584190573030901335
404 11232994091651004208
405 11920738653290183022
406 12649670948897337848
407 13422247574784880979
408 14240981913666438204
409 15108619218153445680
410 16027970477698839328
411 17002102799667347490
412 18034159196278793504
413 19127565564856730556
414 20285835244945581600
415 21512794007395468969
416 22812368141579248820
417 24188828979774956350
418 25646563177392429072
419 27190338425407855352
420 28825054482210472964
421 30556031863344638562
422 32388742071529125300
423 34329121200502153056
424 36383277689363898448
425 38557832936763762040
426 40859604776401361764
427 43295977370107226592
428 45874558462473256688
429 48603581007535344128
430 51491532111444044652
431 54547589048608855057
432 57781217641311514452
433 61202645538458054234
434 64822427609376067824
435 68651959593039362617
436 72703007899129664852
437 76988266989110244680
438 81520850780135801576
439 86314897393165048579
440 91385019143547058008
441 96746958587022406914
442 102416993853856178148
443 108412650242870941849
444 114752057412753936516
445 121454721118992141284
446 128540828515427759300
447 136032085001154292728
448 143950963606313755196
449 152321612317801324284
450 161169043224483680328
451 170520116124302846815
452 180402662784227631512
453 190846553099481141498
454 201882749481259209584
455 213544462344109715637
456 225866129268231622536
457 238884667136342851040
458 252638370325734968172
459 267168267404450114757
460 282516932189494175792
461 298729953547150846022
462 315854652706142475880
463 333941675392116121194
464 353043608306223047096
465 373216703563054404980
466 394519386734176338156
467 417014124356390834847
468 440765815394076153624
469 465843813445063501896
470 492320192893118321796
471 520271938366898168309
472 549779076232195423528
473 580927044860623322016
474 613804681447948233872
475 648506787729078063033
476 685131961401370681516
477 723785373087194333244
478 764576430886877663084
479 807621785646298806251
480 853042816360219214276
481 900968882157039809562
482 951534615416798926344
483 1004883440346124283855
484 1061164659762953772684
485 1120537261710027907744
486 1183166784887196791232
487 1249229436450489534684
488 1318908720039247209888
489 1392399889739321376884
490 1469906323552692903416
491 1551644340478165856032
492 1637839301101716630336
493 1728730816877138892360
494 1824568558272351184392
495 1925617887627860483550
496 2032155353973410332816
497 2144474783316712150146
498 2262882437841942029952
499 2387703600148914762750
500 2519277373055546641884
501 2657963797183331460636
502 2804138266005430348224
503 2958199219274269181370
504 3120562146280444520424
505 3291667900959703346552
506 3471976264550581289312
507 3661974931819756339552
508 3862172602422955289664
509 4073108691569792266532
510 4295345917397756667492
511 4529480793581983298175
512 4776135677920539812380
513 5035970108904332147820
514 5309672278477905146236
515 5597971279445314199930
516 5901627963008268244372
517 6221448169122259088684
518 6558272926917435741348
519 6912992745764950712600
520 7286537114049231425436
521 7679889934788836206118
522 8094078275445754949376
523 8530189038502159273672
524 8989356912056757380500
525 9472782372825033631664
526 9981718784178357577712
527 10517491836650370738020
528 11081485736814992243272
529 11675164198587760770068
530 12300055662908123548240
531 12957775961967698782902
532 13650012506053820544168
533 14378548752366088424512
534 15145247291586097443624
535 15952076263212590407582
536 16801091270440594011848
537 17694463895010971084742
538 18634462364805224490384
539 19623482333129330176089
540 20664026219052530134812
541 21758736428894200948938
542 22910373284751317183324
543 24121850879802613394580
544 25396213505675133707948
545 26736674348099173577506
546 28146590318755546159652
547 29629503813891155938726
548 31189115851061813503248
549 32829331130641103505180
550 34554229372426372863536
551 36368113938639889989720
552 38275481259696017210768
553 40281073297407286180048
554 42389844943318652663968
555 44607020622504484322949
556 46938059541761576859572
557 49388716757736972835842
558 51965006145937536310896
559 54673266282093600401875
560 57520120996393194693620
561 60512550444102803451720
562 63657849102674961837624
563 66963702436866875848326
564 70438142189408782058140
565 74089629077346567672876
566 77927005219806291611184
567 81959583336214420244439
568 86197096147364387471076
569 90649792582727053161246
570 95328383983535267942136
571 100244147865792316075153
572 105408870746460569416440
573 110834960051226736693816
574 116535383377135842674208
575 122523789179917162368217
576 128814442278573828184872
577 135422354006367743481180
578 142363213754993391465352
579 149653529326440015106490
580 157310554306485611744232
581 165352439411897389140620
582 173798155475125845342536
583 182667656642990894511118
584 191981798746690500466984
585 201762515274594826144824
586 212032730894071962538292
587 222816551192649317717809
588 234139171110771464530872
589 246027079522787659061236
590 258507962332676161593848
591 271610923049512582376253
592 285366380291513359331380
593 299806305600298001690692
594 314964115092427337880600
595 330874925853397274689026
596 347575441470293678496136
597 365104228450587607168988
598 383501595364732868987248
599 402809890847058606893683
600 423073376073247895658512
601 444338546021572675808870
602 466653995007382797328500
603 490070763013280828699208
604 514642194001210010832100
605 540424309260654891525010
606 567475658218856942294704
607 595857720907541919405642
608 625634750993450849496488
609 656874209627287338137912
610 689646600420394970404992
611 724025937115507088399582
612 760089570241323917856648
613 797918691234222769648060
614 837598150511019363675672
615 879217000875126211900152
616 922868306759287058128168
617 968649729969905997532404
618 1016663329866427913308576
619 1067016194734942416354883
620 1119820232689596080972464
621 1175192852222440489018980
622 1233256743635302902410552
623 1294140612588640758317935
624 1357978951900216544387060
625 1424912832212996360872984
626 1495089664030383498945220
627 1568664049943634130149843
628 1645797536812975056502696
629 1726659534340413083789014
630 1811427057352540180778040
631 1900285715876935317941843
632 1993429447536664955465360
633 2091061584689817971937650
634 2193394577008546332904184
635 2300651141673903706467406
636 2413063976284735304261712
637 2530876998566351420469826
638 2654345049837765399592816
639 2783735231195460716294172
640 2919326597862596962463508
641 3061411599351063849424292
642 3210295765124654533117232
643 3366299256826806491983630
644 3529756545812836606505936
645 3701018086160548482461870
646 3880449984766036286755400
647 4068435804533254144552098
648 4265376227885381212958844
649 4471691000261339105314140
650 4687818588072198826792520
651 4914218273421637747695706
652 5151369807736471650208592
653 5399775669478626215381600
654 5659960714902912104382244
655 5932474611445060750153573
656 6217891487310864006669632
657 6516812554213376522620548
658 6829865757778293805935580
659 7157708604369149926164169
660 7501027814607348024761240
661 7860542370173111097315996
662 8237003173088236793901152
663 8631196329619193791314216
664 9043942818360084708006144
665 9476102029699629727182956
666 9928571446174966593919176
667 10402290457403885181398535
668 10898240056661317725734240
669 11417446952730227291479338
670 11960983287186694313896216
671 12529971066296104303209570
672 13125581904084800898138748
673 13749041799212129178338294
674 14401630909562363827490884
675 15084688700967952546485519
676 15799613759781014364220204
677 16547869342419794640905388
678 17330983233181202294079800
679 18150553725842896431894827
680 19008249534864439017010436
681 19905816242714365748673636
682 20845076273585584667505664
683 21827935842744026245879889
684 22856385002962646103375792
685 23932505135020653909373340
686 25058469078249395837061332
687 26236549204364743673245281
688 27469117644827598013832516
689 28758654993484036198520416
690 30107750644884475357092592
691 31519112174755235776252600
692 32995565805005815538630576
693 34540066514881671842773188
694 36155698650131956661355828
695 37845686821818167290015207
696 39613396679029617568885688
697 41462346656769447570154396
698 43396208933707885099086388
699 45418822095361036758229621
700 47534192300679834163377808
701 49746506931905104659511716
702 52060135996321708418667996
703 54479646839744762500756023
704 57009805812544195409957608
705 59655594129723085049503586
706 62422209833359791938337760
707 65315084888714030054333515
708 68339887478565899715676520
709 71502540431765016967546228
710 74809223888594244855620764
711 78266395165701274997228892
712 81880791835607979228499176
713 85659453140074621431994176
714 89609723531244286447784892
715 93739275754233043365420522
716 98056114902176249658819092
717 102568603298262657163788306
718 107285465122171786873390000
719 112215813231929152183604988
720 117369154424930682094921464
721 122755418350947006538496976
722 128384963477164753724121892
723 134268608255471696304843108
724 140417637867751946779097536
725 146843837823306945028069408
726 153559501568072329641281180
727 160577466701743625531038950
728 167911123542691311676881572
729 175574454169141511389882488
730 183582042040411525927242168
731 191949114082427656107150552
732 200691551475550187023698976
733 209825935021881868281556966
734 219369557220468347779541064
735 229340471172357887036060952
736 239757504075425658956618192
737 250640309943091448625410396
738 262009384663505430133147632
739 273886122829327353048028944
740 286292834519615536925305212
741 299252806561238387032362300
742 312790321206622854780276720
743 326930722172336331070626069
744 341700435401979072711428752
745 357127040254380777252427396
746 373239292558475384325751616
747 390067201352551840510829466
748 407642054457050377232902664
749 425996501197552529263962660
750 445164580742216576029538700
751 465181811274861581741623803
752 486085221366358033182274860
753 507913446100441638566156580
754 530706761772946808457375416
755 554507189512079664994051086
756 579358533626092943136648036
757 605306493301871017416092336
758 632398704950674676116237392
759 660684862614277488230566472
760 690216764689951967955791096
761 721048443722297656732264300
762 753236217922906508926789312
763 786838831078709263826224557
764 821917509318974547693510488
765 858536111927762732336602776
766 896761193851325778736745092
767 936662168263410366688051491
768 978311375349999256138309468
769 1021784257542085476170199124
770 1067159435162317754826829976
771 1114518895310838183598385841
772 1163948075010073955568085184
773 1215536064805683053288141242
774 1269375700101806977612099032
775 1325563780621523310512677224
776 1384201170685701028023856776
777 1445393035766067934088771850
778 1509248952526782254828714344
779 1575883163798774057796833545
780 1645414699274686092357280252
781 1717967650336065534827825804
782 1793671302369889181436278608
783 1872660430991029167554418336
784 1955075447032654660244842840
785 2041062715825779360436643512
786 2130774716006955003050720900
787 2224370383645282282862558538
788 2322015286109554183256891612
789 2423881992971577751004120508
790 2530150266281906492416107952
791 2641007460327433676457078198
792 2756648729780740724448793584
793 2877277460550496119135001288
794 3003105497394961706184698248
795 3134353608276639006657897174
796 3271251733166395370594929256
797 3414039484499981771197066124
798 3562966419046404876414884424
799 3718292577264408526885086885
800 3880288780268031130945014864
801 4049237211096984580024798500
802 4225431738984775196819455696
803 4409178545789298481197328245
804 4600796479955519008556060680
805 4800617731602784901814365844
806 5008988218775992987639835296
807 5226268314955465794284163612
808 5452833270408997119046169520
809 5689073996180080963994615678
810 5935397523589559309407392948
811 6192227849070110418200919517
812 6460006435121827842305616152
813 6739193120696846120601020398
814 7030266667189601507164082936
815 7333725739437103712904771232
816 7650089500623517419675756396
817 7979898669350822396556859260
818 8323716167660491849864648608
819 8682128260048208723781718422
820 9055745259154721720374979136
821 9445202753049148070688088994
822 9851162373518628699707061264
823 10274313118429960533470349976
824 10715372187955676732957399456
825 11175086409345908469086708792
826 11654233146869384423675476232
827 12153621836889310631740093847
828 12674094977774100586769362656
829 13216529783775678078460951928
830 13781839261679299395082506016
831 14370973992633247557240343794
832 14984923302862889463606152068
833 15624717183300700064555636896
834 16291427562289938305668284964
835 16986170373617033933741088040
836 17710106939778442755885801072
837 18464446199827640973655319364
838 19250446212478574821798215484
839 20069416556051128834759159358
840 20922719961440145733659068276
841 21811774897380876011747831356
842 22738057344128147114122313028
843 23703103578271914831514059577
844 24708512098851473139551910068
845 25755946627036133288597349954
846 26847138197349409450163207448
847 27983888388696763826939680073
848 29168071594399882831666436368
849 30401638502308484146142638708
850 31686618558450928497822587904
851 33025123715316880034098782988
852 34419351105123835984309051588
853 35871587076809045279381834094
854 37384210096198812767146142016
855 38959695093809116419665728731
856 40600616610592993852296949808
857 42309653480327920995234886808
858 44089592241114003256986094808
859 45943332177931156098322511707
860 47873889021675575856516593004
861 49884400379410509612715937772
862 51978129744469577469609278924
863 54158472344011543540144263127
864 56428959485596186442212317732
865 58793264853896837288605813928
866 61255209221178060818912067812
867 63818767227431460402817508251
868 66488072484365633078584991312
869 69267424875823362481901122456
870 72161296087245181502962714120
871 75174337466013006917999281623
872 78311386010882119487377747268
873 81577472834891949101601409164
874 84977829651991268155884093664
875 88517897888376680043741775546
876 92203335706477261016150682344
877 96040027814041937590865663294
878 100034093068818764045921389144
879 104191895038431610594146311515
880 108520050232502984769083325496
881 113025439470357409682682764770
882 117715216791013729782853453128
883 122596821690047751869124939667
884 127677988761840240275520458004
885 132966760871546835002568428560
886 138471499588252839827486020076
887 144200899362957740347741566170
888 150163998815880410609143121460
889 156370195996694068916061732220
890 162829260594170368421017267448
891 169551350360625535738015598256
892 176547024317415490987785213428
893 183827260431704377260544068360
894 191403469897053859949265672552
895 199287516157232558202331306855
896 207491730347311590229233325100
897 216028931766331117951083104116
898 224912444570953879695234293432
899 234156119806429149153500282499
900 243774353452001695600313275776
901 253782110127802541153800584740
902 264194942598900373947406727776
903 275029017284543964252305645275
904 286301135336017174676466133624
905 298028760084104164182022645136
906 310230039814811423999853045588
907 322923837301071569262758995035
908 336129754409973113911837804640
909 349868163875612774180956689372
910 364160235881776246968185163228
911 379027972244547266657193723936
912 394494235125464415772439568936
913 410582783805056375417246789164
914 427318305693418666340356039592
915 444726455889331534131979348391
916 462833890668018613684053490460
917 481668310034984146491434921130
918 501258493884499535518842004548
919 521634347772842412208988521493
920 542826941955878413880929994096
921 564868560623073511320764308808
922 587792744038473815881154122948
923 611634341494777623749325157864
924 636429556799147943520058252392
925 662216005225860954062738361608
926 689032762606802513658681172560
927 716920426581850596498871850520
928 745921169573702986334140803992
929 776078804657305023902020508972
930 807438842719932550953463148912
931 840048563294752563777188763147
932 873957076229952161214446062236
933 909215397857035896565525861692
934 945876517517364778320630458416
935 983995479463176079460895194211
936 1023629454616301564182658917080
937 1064837828629278074267042109968
938 1107682279279385371493934505320
939 1152226871148743423115482824586
940 1198538139087291502751817199332
941 1246685190004595490105760575686
942 1296739792868135477983067815304
943 1348776488135839361192548308652
944 1402872684791221574494195236040
945 1459108777984595350417656532926
946 1517568253644387675646398513528
947 1578337814936752057991069660719
948 1641507495032964384365418833168
949 1707170793041964583166318839628
950 1775424795557318478200034930384
951 1846370322765278562332734368564
952 1920112059441596449008020680124
953 1996758711989243766616151333286
954 2076423149605612321883678690736
955 2159222573059326129585583121263
956 2245278666802322559685059046748
957 2334717780354483707810293506728
958 2427671092193020149332864650588
959 2524274804677241173204339826500
960 2624670320609851028968432742612
961 2729004452702370222180504627752
962 2837429613769710549721547540652
963 2950104041809882629827000993442
964 3067192004864870769708005169368
965 3188864042866667340395964442400
966 3315297188274375300264162567824
967 3446675225922674929129679796459
968 3583188930627619479287453876412
969 3725036346363767730174897096828
970 3872423042119712499706435416408
971 4025562411826735466305329713516
972 4184675949840153681722381433792
973 4349993573145933522824144612374
974 4521753917945922239165523577392
975 4700204685779890641609632246746
976 4885602962802133382791672398496
977 5078215591575424725605216069008
978 5278319514743856233803059303632
979 5486202174382753527144518163838
980 5702161881898544603124991912712
981 5926508246955404463127639630200
982 6159562575568022980348647382500
983 6401658330772267760773339293943
984 6653141561021602043283638286144
985 6914371394926078669937171451390
986 7185720502218546818675164912056
987 7467575625054554611066351498708
988 7760338073981128745809208738456
989 8064424298470465117456582643924
990 8380266420502770617083834910832
991 8708312847199810742088715673288
992 9049028844824927359945989412048
993 9402897196589499574324303443344
994 9770418820078714841368973552388
995 10152113473525757675229073387507
996 10548520419892198401239808568704
997 10960199185142294790320592100604
998 11387730272443026131513958702864
999 11831715976225389200665761260019
1000 12292781150222272163307451038060