1 1
2 0
3 1
4 1
5 3
6 3
7 6
8 7
9 12
10 14
11 22
12 27
13 40
14 49
15 69
16 86
17 118
18 146
19 195
20 242
21 317
22 392
23 505
24 623
25 793
26 973
27 1224
28 1498
29 1867
30 2274
31 2811
32 3411
33 4186
34 5059
35 6168
36 7427
37 9005
38 10801
39 13026
40 15572
41 18692
42 22267
43 26613
44 31602
45 37619
46 44533
47 52815
48 62338
49 73680
50 86716
51 102162
52 119918
53 140853
54 164903
55 193144
56 225566
57 263490
58 306993
59 357699
60 415814
61 483338
62 560641
63 650196
64 752622
65 870953
66 1006132
67 1161916
68 1339677
69 1544048
70 1776980
71 2044188
72 2348384
73 2696627
74 3092594
75 3545015
76 4058848
77 4644850
78 5309608
79 6066425
80 6923959
81 7898630
82 9001747
83 10253568
84 11668765
85 13272332
86 15083146
87 17132044
88 19443237
89 22054694
90 24997285
91 28317803
92 32055418
93 36267714
94 41004230
95 46335767
96 52324747
97 59058176
98 66614382
99 75100211
100 84613725
101 95285933
102 107239203
103 120634125
104 135622955
105 152402294
106 171161152
107 192139963
108 215572796
109 241753433
110 270970998
111 303584109
112 339949238
113 380503578
114 425685678
115 476028109
116 532069294
117 594457221
118 663851774
119 741040507
120 826830709
121 922178606
122 1028069997
123 1145664693
124 1276164654
125 1420974960
126 1581558720
127 1759616557
128 1956926660
129 2175545082
130 2417629854
131 2685664089
132 2982263029
133 3310422523
134 3673307317
135 4074528159
136 4517909823
137 5007799482
138 5548813432
139 6146180442
140 6805464937
141 7532949590
142 8335333558
143 9220158247
144 10195479211
145 11270340005
146 12454415595
147 13758540358
148 15194321234
149 16774725237
150 18513661361
151 20426634675
152 22530294442
153 24843162935
154 27385148539
155 30178357193
156 33246569505
157 36616144467
158 40315458727
159 44375914168
160 48831338330
161 53719106921
162 59079505752
163 64956982102
164 71399466780
165 78459770304
166 86194865956
167 94667447031
168 103945172648
169 114102405525
170 125219421613
171 137384351371
172 150692356248
173 165247796646
174 181163380983
175 198562588546
176 217578795417
177 238357984581
178 261057857148
179 285850863883
180 312923312758
181 342478762147
182 374737136247
183 409938526880
184 448342332806
185 490231519559
186 535911804332
187 585716432648
188 640005430863
189 699170967038
190 763636701449
191 833863804673
192 910350443224
193 993638539962
194 1084313436127
195 1183011492536
196 1290419979618
197 1407285626147
198 1534414801252
199 1672683135737
200 1823036066020
201 1986499671158
202 2164181666225
203 2357283613018
204 2567102466808
205 2795044343438
206 3042626737181
207 3311494054514
208 3603420644332
209 3920328330754
210 4264290424439
211 4637551523826
212 5042532696911
213 5481853858834
214 5958340351357
215 6475048240693
216 7035272560447
217 7642575925363
218 8300798740512
219 9014091584553
220 9786927741019
221 10624139858112
222 11530935219155
223 12512937262692
224 13576204064666
225 14727275385145
226 15973194917134
227 17321563609480
228 18780566325055
229 20359032298640
230 22066466937811
231 23913120397333
232 25910025374084
233 28069074902464
234 30403067129724
235 32925793597839
236 35652092120540
237 38597946993835
238 41780551274844
239 45218420549441
240 48931466108724
241 52941124133557
242 57270441474229
243 61944222372090
244 66989128806555
245 72433847147773
246 78309205329627
247 84648362166157
248 91486943919174
249 98863259387551
250 106818458823410
251 115396778310845
252 124645724412543
253 134616351842882
254 145363477695104
255 156945996964271
256 169427130763551
257 182874784847878
258 197361836861762
259 212966543725896
260 229772873645703
261 247870969018586
262 267357529754616
263 288336339236933
264 310918706425387
265 335224063427995
266 361380474876506
267 389525316822980
268 419805863065542
269 452380056354758
270 487417182694402
271 525098747327607
272 565619249519999
273 609187177461859
274 656025897775021
275 706374785316398
276 760490243595778
277 818646987602104
278 881139213487980
279 948282054947232
280 1020412923021273
281 1097893159226402
282 1181109569160913
283 1270476298657758
284 1366436588007316
285 1469464900867384
286 1580068929531253
287 1698792010182008
288 1826215413696334
289 1962961085239727
290 2109694259637610
291 2267126568272699
292 2436019023241565
293 2617185540049481
294 2811496340618673
295 3019881946594520
296 3243337057795974
297 3482925078045049
298 3739782533097967
299 4015124198846010
300 4310248131133290
301 4626541475193425
302 4965486189130200
303 5328665623593822
304 5717771031335221
305 6134609017455669
306 6581108939414254
307 7059331341037265
308 7571476360738980
309 8119893276906634
310 8707090057269933
311 9335744159426003
312 10008713371329583
313 10729048028979543
314 11500003317085346
315 12325053086440349
316 13207903805378874
317 14152510182294055
318 15163090982721167
319 16244146688351003
320 17400477421671388
321 18637202901868647
322 19959782749545640
323 21374039032406253
324 22886179256869755
325 24502821833044635
326 26231022098466166
327 28078301072924502
328 30052674902788869
329 32162687322176868
330 34417442954824019
331 36826643949750324
332 39400627631875801
333 42150407838222896
334 45087717469491145
335 48225055117579740
336 51575733138671944
337 55153930235582573
338 58974745749357200
339 63054258941385679
340 67409590286349994
341 72058968290076968
342 77021798662782558
343 82318739610778598
344 87971779876391940
345 94004323555916610
346 100441278113091302
347 107309149903404234
348 114636143402804330
349 122452268761571633
350 130789453640582245
351 139681664277984816
352 149165031494064973
353 159277986932696068
354 170061404984502316
355 181558756065135164
356 193816266417099786
357 206883090510462438
358 220811490919469394
359 235657032180871515
360 251478783204819624
361 268339535205081174
362 286306029397680560
363 305449201928932058
364 325844439943910048
365 347571856785922603
366 370716579883781819
367 395369059884829412
368 421625394219217805
369 449587674262072455
370 479364348890098971
371 511070614251846573
372 544828822141857158
373 580768917497559464
374 619028896984681949
375 659755299940989585
376 703103723201044046
377 749239371877508188
378 798337637160565588
379 850584714075392933
380 906178249779495260
381 965328036268312714
382 1028256737572313785
383 1095200666310896652
384 1166410599169829599
385 1242152647238021780
386 1322709170235778087
387 1408379751720964486
388 1499482223752741187
389 1596353759335847973
390 1699352020556295505
391 1808856382060400000
392 1925269217203188978
393 2049017267947868198
394 2180553085242406849
395 2320356562492834580
396 2468936548246657095
397 2626832562360473550
398 2794616601141035614
399 2972895057515422479
400 3162310741085699958
401 3363545026042077021
402 3577320111150156951
403 3804401421852166241
404 4045600138054433470
405 4301775879867863696
406 4573839534230118797
407 4862756257076527102
408 5169548633350202045
409 5495300032106173820
410 5841158138371323207
411 6208338701807248878
412 6598129483224046135
413 7011894442005318190
414 7451078144901648657
415 7917210442505066203
416 8411911393300775754
417 8936896485121878317
418 9493982133380560809
419 10085091509696809621
420 10712260679825155004
421 11377645108601751229
422 12083526510399608076
423 12832320107249534630
424 13626582272774652609
425 14469018628893122822
426 15362492573186346394
427 16310034309077049584
428 17314850356568790583
429 18380333621310142021
430 19510073999712547155
431 20707869603969299373
432 21977738584828555646
433 23323931642557872414
434 24750945204246240812
435 26263535365023922270
436 27866732571834489733
437 29565857155082708059
438 31366535687508994262
439 33274718284010754229
440 35296696822737974338
441 37439124210294462544
442 39709034672646308574
443 42113865204456975962
444 44661478160067287285
445 47360185129574068554
446 50218772085230796425
447 53246525953283993791
448 56453262598914280584
449 59849356392063753043
450 63445771344766626250
451 67254094001531547368
452 71286568076907025289
453 75556131036747528158
454 80076452621465176111
455 84861975524064146283
456 89927958226119909551
457 95290520222209958626
458 100966689641647897744
459 106974453517302139022
460 113332810716953183403
461 120061827807952715146
462 127182697878268590363
463 134717802607525180052
464 142690777619903329741
465 151126581437396789518
466 160051568075356521116
467 169493563625935362520
468 179481946882875373580
469 190047734382800700866
470 201223669929580060725
471 213044319009138123695
472 225546168176198897987
473 238767729855469463867
474 252749652655675613100
475 267534837677270699150
476 283168560931394261794
477 299698602392702065088
478 317175381825298619532
479 335652101950005742254
480 355184899116628112701
481 375833002099229990597
482 397658899205596985305
483 420728514373243975552
484 445111392474080516625
485 470880894559435143053
486 498114403302296224257
487 526893539433273801654
488 557304389466109963322
489 589437745580029870619
490 623389357998414225548
491 659260200808419233431
492 697156751609876243889
493 737191286022594894908
494 779482187495008986845
495 824154273535634925170
496 871339138871261151257
497 921175516754271807594
498 973809658991062716164
499 1029395736024285204387
500 1088096257716722498340
501 1150082516290163799799
502 1215535052151559153695
503 1284644144191718558434
504 1357610325382866080667
505 1434644925404546382844
506 1515970641228768672736
507 1601822137551633199728
508 1692446678118545987920
509 1788104790002805589794
510 1889070962013755559680
511 1995634379483016900855
512 2108099696748277812080
513 2226787849789622936153
514 2352036910496822339102
515 2484202985248444831948
516 2623661159457438580930
517 2770806491011180056199
518 2926055054455902271162
519 3089845039123919717994
520 3262637903269816950747
521 3444919587709916221864
522 3637201791270582538704
523 3840023311863474065033
524 4053951455758163686735
525 4279583519224582038058
526 4517548345408625087711
527 4768507961001156087483
528 5033159295887551653122
529 5312235990762402450202
530 5606510296254311763885
531 5916795069009861276440
532 6243945868676870012668
533 6588863161744337670359
534 6952494636615519067663
535 7335837636427850335216
536 7739941714477722681159
537 8165911319372712870612
538 8614908615300533712562
539 9088156445203717277719
540 9586941442835220236422
541 10112617302213308750235
542 10666608211096889261012
543 11250412457797880958042
544 11865606218663738240613
545 12513847536420336603628
546 13196880497492737860072
547 13916539619450141464868
548 14674754457556506539565
549 15473554442619500963615
550 16315073960070569806055
551 17201557683613863732939
552 18135366174424005850702
553 19118981760483531377479
554 20155014708192365723308
555 21246209702211438780503
556 22395452646940600715723
557 23605777807093445619130
558 24880375302163622912433
559 26222598973887105919342
560 27635974643028255112998
561 29124208776390621623628
562 30691197582065816781556
563 32341036555786935507880
564 34078030498252251417850
565 35906704028436077766792
566 37831812614787824681679
567 39858354151688702312815
568 41991581105302858027092
569 44237013258765947055483
570 46600451083303321513767
571 49087989768035970459056
572 51706033937762379463783
573 54461313094553676030909
574 57360897815409708683792
575 60412216745181306738905
576 63623074420254416476082
577 67001669965884699310367
578 70556616706242264324339
579 74296962734083220855934
580 78232212483017534729404
581 82372349353694680895683
582 86727859441164932623949
583 91309756419554171287541
584 96129607636012645555951
585 101199561475341643228147
586 106532376052414315186600
587 112141449299551913998549
588 118040850511623339342714
589 124245353422323102459442
590 130770470880589585375202
591 137632491207498605195777
592 144848516309381240761484
593 152436501635020825625668
594 160415298060113708611731
595 168804695795067432247305
596 177625470407465619837187
597 186899431064255063468716
598 196649471093904060601627
599 206899620983402432054636
600 217675103920119184694145
601 229002394004112641422060
602 240909277251601672241748
603 253424915526909986992101
604 266579913535296304288192
605 280406389026782996789370
606 294938046356205313096776
607 310210253563576863207225
608 326260123134009868989265
609 343126596616559310183698
610 360850533276564242872666
611 379474802977536759513486
612 399044383483946388097474
613 419606462399167741896125
614 441210543948285732223797
615 463908560839919157659690
616 487754991436819671253030
617 512806982491127687484617
618 539124477695978309576253
619 566770352333053038710240
620 595810554291751070536921
621 626314251765464167719020
622 658353987926840920106046
623 692005842915783234179756
624 727349603470707571980529
625 764468940567657395389920
626 803451595429102271923234
627 844389574300671735697147
628 887379352391859849536137
629 932522087415682123612558
630 979923843160681705075923
631 1029695823570348434254076
632 1081954617804155366629294
633 1136822456799007718103980
634 1194427481849874945721794
635 1254904025776109294534801
636 1318392907240885536763820
637 1385041738842307197121179
638 1455005249596745370696950
639 1528445622489719133173131
640 1605532847772884596485287
641 1686445092744349331822447
642 1771369088754187581247061
643 1860500536239884207697111
644 1954044528602674988370221
645 2052215995803125943857004
646 2155240168562313731635297
647 2263353064127211864363357
648 2376801994568905615360381
649 2495846098659741321326280
650 2620756898387773834663385
651 2751818881250001166043894
652 2889330109480638569338615
653 3033602857459886506486874
654 3184964278566207054052926
655 3343757102830871524259550
656 3510340366774219626854515
657 3685090176905871633166713
658 3868400508395281816529572
659 4060684040529423076995422
660 4262373030602394994658054
661 4473920228000341183337648
662 4695799830277343305104902
663 4928508483145384018014122
664 5172566326338496045246453
665 5428518087448161559460270
666 5696934225869303294400066
667 5978412129143424340968514
668 6273577364033540376120891
669 6583084984823839115211684
670 6907620901391508030684652
671 7247903309768410128524797
672 7604684187971880810447709
673 7978750860067048011738118
674 8370927631492488076573156
675 8782077498878068728666674
676 9213103937661855809565059
677 9664952771025011072162154
678 10138614123751120995740185
679 10635124464844650227919791
680 11155568742841166237568673
681 11701082617987726751179861
682 12272854795581255330039077
683 12872129465017359820737523
684 13500208849224099143518756
685 14158455869440223854838623
686 14848296930433323458869286
687 15571224831560353072175148
688 16328801809224128874681454
689 17122662716610202770684430
690 17954518346756328129024744
691 18826158905363235890535456
692 19739457639941534919432161
693 20696374632273804949600723
694 21698960761377091311132804
695 22749361844565240763100791
696 23849822964438615466076483
697 25002692990075338134851417
698 26210429300950357384510324
699 27475602722590231288103585
700 28800902683249968073115380
701 30189142601417684731488934
702 31643265514260058507838230
703 33166349957681830697699368
704 34761616109011296579109726
705 36432432203928161434252765
706 38182321239623201190241563
707 40014967976831342315928905
708 41934226253790400160319732
709 43944126625881480384576641
710 46048884345158699808458435
711 48252907694735412614261639
712 50560806693490570646818806
713 52977402187378655876266430
714 55507735344171950138548265
715 58157077569348880184716035
716 60930940861440837016838489
717 63835088626105287871182367
718 66875546968849830085926032
719 70058616487363415869174153
720 73390884585131233412485980
721 76879238329123649828325196
722 80530877875139013392917681
723 84353330485583057247581364
724 88354465165332376606184572
725 92542507942628650285487375
726 96926057822897081733218875
727 101514103444785806172249364
728 106316040468759204295677896
729 111341689730093863366098415
730 116601316189259451289954445
731 122105648714304243872406422
732 127865900731104521961748385
733 133893791779106093840221120
734 140201570011540982802085211
735 146802035681013618027702134
736 153708565652831112033981517
737 160935138990517331568125184
738 168496363659567190168127169
739 176407504397729046043963225
740 184684511801868236012381768
741 193344052683876087406609383
742 202403541750015283047163873
743 211881174660698244285002851
744 221795962529797171925467812
745 232167767925400463978623369
746 243017342436222885916543936
747 254366365870920332210995850
748 266237487160059878801774058
749 278654367033785155060883832
750 291641722550942039257484785
751 305225373558984856627883532
752 319432291166952760943568530
753 334290648317648602295035100
754 349829872548387647692485872
755 366080701033836939885200362
756 383075238007989499406754956
757 400847014666807030815793712
758 419431051656901263701254198
759 438863924260476835147107495
760 459183830390934889453374127
761 480430661518782156082120474
762 502646076652035308706549693
763 525873579500980673593128708
764 550158598962094547338400941
765 575548573062058774946695315
766 602093036508185556500797944
767 629843711998191192053457011
768 658854605448108703245033669
769 689182105304291587850916285
770 720885086111821927285978563
771 754025016519378429199298807
772 788666071907534791732878277
773 824875251835828150559848572
774 862722502511452669384008339
775 902280844491480468070667043
776 943626505838678365820690180
777 986839060960768636722663676
778 1032001575371853872811079824
779 1079200756625297588298097966
780 1128527111676988818953218139
781 1180075110949346314349036261
782 1233943359376883207107076384
783 1290234774726505312526981133
784 1349056773497079331134362383
785 1410521464716159081774352765
786 1474745851964093654615547231
787 1541852043970173453436452342
788 1611967474138859404354911936
789 1685225129379740006333078048
790 1761763788629391236110130865
791 1841728271470175093550901678
792 1925269697266778530826910361
793 2012545755259518228141673094
794 2103720986070540519205749814
795 2198967075098742115027024911
796 2298463158297789543720985032
797 2402396140852902623596015776
798 2510961029292187473442097566
799 2624361277591310882945003037
800 2742809147852125111490713322
801 2866526086160715470013815443
802 2995743114253996902942537090
803 3130701237650855071664777562
804 3271651870929468723648387078
805 3418857280861486289773900595
806 3572591048141521291960189515
807 3733138548481807829995892944
808 3900797453871975440896541599
809 4075878254837807273266812205
810 4258704804565480084067949177
811 4449614885794419469747312194
812 4648960801417260244738369569
813 4857109989764985358973117928
814 5074445665593617018398320888
815 5301367487831601321852134369
816 5538292255188511342007436571
817 5785654630771899622802895396
818 6043907896904056720284501353
819 6313524741380351164097627660
820 6594998076459473237599976265
821 6888841891929832391860316624
822 7195592143649028069879405152
823 7515807679011569101050494171
824 7850071200857035289815221786
825 8198990271393802630593988840
826 8563198357775171974313747540
827 8943355921032712776619156829
828 9340151550138431194744293425
829 9754303143040788394452738936
830 10186559136591881185719366489
831 10637699787362390776217508431
832 11108538505419122091072707987
833 11599923243225593074452780349
834 12112737941910757163731259864
835 12647904037243425175127861150
836 13206382027741498091176312916
837 13789173107444993552322273236
838 14397320865980870514146225772
839 15031913058655500734015889910
840 15694083449417732472952600550
841 16385013729651939240724244697
842 17105935515876263963032167088
843 17858132429546999238445359375
844 18642942262295279256987750445
845 19461759230058004748334308578
846 20316036319700325798947978470
847 21207287731873558482749646063
848 22137091423998793415019286025
849 23107091757424662100244796436
850 24119002252965961389469839340
851 25174608459200618401452763879
852 26275770938073506929782363962
853 27424428372539971663292324109
854 28622600801166755001213723835
855 29872392984806995654537091955
856 31175997910665711312250758629
857 32535700439286929744909334565
858 33953881100209460667674100566
859 35433020042270068119896896829
860 36975701144765988095551232465
861 38584616295938852494163372545
862 40262569845493993617808589694
863 42012483238139005467144866240
864 43837399835397557151181689888
865 45740489933245689354150527819
866 47725055983411742227988940364
867 49794538026495299821936047168
868 51952519345377967908657036331
869 54202732347737836157047017113
870 56549064686822270572983117125
871 58995565629999448325572709618
872 61546452684979197252970252660
873 64206118493988284474126146542
874 66979138006584949883873538888
875 69870275942223122610805381950
876 72884494554108222731115464923
877 76026961706345569822895451102
878 79303059276848187031663760032
879 82718391898965988107156456790
880 86278796055301086711465652670
881 89990349537708047857688148928
882 93859381288020526257473120564
883 97892481634621715848573305388
884 102096512940561643194065828091
885 106478620679545464194977876455
886 111046244956748864823699785120
887 115807132492086437547676665869
888 120769349084240785579379946297
889 125941292574482286624772813101
890 131331706330045150266097575638
891 136949693267604043179356910779
892 142804730438189260963207553359
893 148906684195717887170509387765
894 155265825972174586701317622868
895 161892848683380658059234057207
896 168798883790213521273503261147
897 175995519041114362526839829375
898 183494816922717768061404273344
899 191309333846488726895496171840
900 199452140100326663731568643073
901 207936840595229562279881058485
902 216777596438269729931676719803
903 225989147364354298957694872307
904 235586835060492757081676711112
905 245586627417610261089658029208
906 256005143746292383915625558204
907 266859680994265607620020193065
908 278168241004869993761543530205
909 289949558857309162246456993425
910 302223132331028145138518806650
911 315009252538216848638302517415
912 328329035770124315681216484401
913 342204456604643682384189877429
914 356658382324446571532336514412
915 371714608696857652988891600855
916 387397897168620417042739947227
917 403734013530764967159031552388
918 420749768110901257771436313114
919 438473057552480015610102965806
920 456932908242840160293664765633
921 476159521454251533462432426004
922 496184320264614815085923042697
923 517039998327054720900584219586
924 538760570560285614892201928659
925 561381425834401129489013161799
926 584939381729586889748954135769
927 609472741448241214997976114574
928 635021352964056221582722804706
929 661626670494827052398692702894
930 689331818389061309280790712758
931 718181657519923012761265442908
932 748222854283604575392936568920
933 779503952302948196386269298183
934 812075446940971419790600687264
935 845989862732965321427628248423
936 881301833849962108918172251681
937 918068187710690076930977653551
938 956348031863579532896982015366
939 996202844265035150566870126333
940 1037696567084977277622582091010
941 1080895704175662234853814841147
942 1125869422344945946426492604260
943 1172689656580545269136502674649
944 1221431219377400689202287030772
945 1272171914326045448667043464185
946 1324992654125860298126773467643
947 1379977583193336826471989468977
948 1437214205041903344384996933303
949 1496793514616586712987273204798
950 1558810135773705869216531417970
951 1623362464103023649150541482503
952 1690552815297234207880482591715
953 1760487579281444048915811333706
954 1833277380323323461848649434497
955 1909037243352977025838574906136
956 1987886766730211411129286213959
957 2069950301705886052345025560876
958 2155357138833318496645163569622
959 2244241701595406674459393613695
960 2336743747523122486996827592339
961 2433008577091455794788118303497
962 2533187250689638862396162481451
963 2637436813973695171205237006607
964 2745920531920923125558356395379
965 2858808131917987176799897311155
966 2976276056226732159701361228603
967 3098507724184810103249167542497
968 3225693804511594220003081475580
969 3358032498103807706186063600241
970 3495729831719692944271627222155
971 3638999962965552086362585105782
972 3788065497013975999225832023244
973 3943157815499214764673698553202
974 4104517418051798056999685987878
975 4272394276951864885438661244485
976 4447048205398573485812462798649
977 4628749239911618569482580219136
978 4817778037400144037342062023561
979 5014426287454397877236643030117
980 5218997140436186757168107043745
981 5431805651965752657376900765435
982 5653179244424962215625874861775
983 5883458186119882162502615181553
984 6122996088769755618702270237199
985 6372160424014314421021211195893
986 6631333059657101082945591894564
987 6900910816389260662019836092638
988 7181306045765931333178564701034
989 7472947230236153374935071702254
990 7776279606056957651572963293736
991 8091765809953237860975338140221
992 8419886550416978222545574601100
993 8761141304572662574868392156419
994 9116049041570048633499518007202
995 9485148973501226962218065783480
996 9869001334875808686613820336945
997 10268188191726486089453089419757
998 10683314281456890548485226621322
999 11115007884584932787021029432044
1000 11563921729577449478924425722545