1 1
2 1
3 3
4 4
5 5
6 7
7 9
8 14
9 18
10 24
11 31
12 43
13 55
14 72
15 94
16 123
17 156
18 200
19 254
20 324
21 408
22 513
23 641
24 804
25 997
26 1236
27 1526
28 1883
29 2308
30 2829
31 3451
32 4209
33 5109
34 6194
35 7485
36 9038
37 10871
38 13063
39 15654
40 18738
41 22365
42 26665
43 31716
44 37682
45 44669
46 52887
47 62494
48 73767
49 86902
50 102260
51 120132
52 140970
53 165153
54 193277
55 225854
56 263647
57 307329
58 357877
59 416198
60 483547
61 561087
62 650432
63 753132
64 871229
65 1006720
66 1162228
67 1340347
68 1544409
69 1777750
70 2044596
71 2349258
72 2697098
73 3093596
74 3545545
75 4059984
76 4645459
77 5310902
78 6067111
79 6925423
80 7899414
81 9003413
82 10254449
83 11670643
84 13273336
85 15085276
86 17133170
87 19445635
88 22055973
89 24999995
90 28319236
91 32058464
92 36269335
93 41007664
94 46337581
95 52328597
96 59060224
97 66618714
98 75102497
99 84618575
100 95288507
101 107244643
102 120636996
103 135629035
104 152405517
105 171167962
106 192143553
107 215580390
108 241757455
109 270979486
110 303588581
111 339958692
112 380508578
113 425696222
114 476033662
115 532081020
116 594463415
117 663864830
118 741047378
119 826845203
120 922186258
121 1028086111
122 1145673167
123 1276182520
124 1420984380
125 1581578544
126 1759626979
127 1956948610
128 2175556646
129 2417654178
130 2685676867
131 2982289921
132 3310436680
133 3673337073
134 4074543782
135 4517942683
136 5007816766
137 5548849736
138 6146199495
139 6805504979
140 7532970635
141 8335377742
142 9220181421
143 10195527881
144 11270365570
145 12454469233
146 13758568475
147 15194380254
148 16774756214
149 18513726317
150 20426668712
151 22530365838
152 24843200384
153 27385227031
154 30178398299
155 33246655679
156 36616189642
157 40315553357
158 44375963702
159 48831442120
160 53719161297
161 59079619598
162 64957041669
163 71399591520
164 78459835617
165 86195002642
166 94667518514
167 103945322260
168 114102483824
169 125219585391
170 137384436983
171 150692535352
172 165247890325
173 181163576841
174 198562690888
175 217579009409
176 238358096453
177 261058090946
178 285850985994
179 312923567966
180 342478895505
181 374737414821
182 409938672317
183 448342636636
184 490231678247
185 535912135678
186 585716605571
187 640005791947
188 699171155543
189 763637094903
190 833864009926
191 910350871632
192 993638763523
193 1084313902557
194 1183011735763
195 1290420487092
196 1407285890850
197 1534415353304
198 1672683423513
199 1823036666190
200 1986499984086
201 2164182318619
202 2357283952971
203 2567103175522
204 2795044712819
205 3042627506977
206 3311494455502
207 3603421479984
208 3920328766125
209 4264291331433
210 4637551996123
211 5042533680801
212 5481854371243
213 5958341418485
214 6475048796184
215 7035273717233
216 7642576527608
217 8300799994292
218 9014092236988
219 9786929099233
220 10624140564969
221 11530936690233
222 12512938027965
223 13576205657232
224 14727276213685
225 15973196640912
226 17321564505921
227 18780568189975
228 20359033268558
229 22066468955077
230 23913121446079
231 25910027555172
232 28069076036445
233 30403069487486
234 32925794823242
235 35652094668218
236 38597948317993
237 41780554027210
238 45218421979506
239 48931469080998
240 52941125677938
241 57270444683389
242 61944224039011
243 66989132270111
244 72433848946874
245 78309209067011
246 84648364106917
247 91486947950530
248 98863261480981
249 106818463171020
250 115396780567854
251 124645729099489
252 134616354276067
253 145363482746912
254 156945999586148
255 169427136206707
256 182874787672852
257 197361842725428
258 212966546768332
259 229772879960241
260 247870972294912
261 267357536553370
262 288336342763631
263 310918713743069
264 335224067223815
265 361380482751226
266 389525320906773
267 419805871537002
268 452380060747914
269 487417191806044
270 525098752051704
271 565619259317215
272 609187182541244
273 656025908307367
274 706374790775744
275 760490254915016
276 818646993469141
277 881139225650598
278 948282061250112
279 1020412936086331
280 1097893165996690
281 1181109583192683
282 1270476305927576
283 1366436603073122
284 1469464908672597
285 1580068945704235
286 1698792018559251
287 1826215431053104
288 1962961094229759
289 2109694278261360
290 2267126577917211
291 2436019043219473
292 2617185550394771
293 2811496362045191
294 3019881957688045
295 3243337080770254
296 3482925089939316
297 3739782557727267
298 4015124211594990
299 4310248157530180
300 4626541488856673
301 4965486217416402
302 5328665638232627
303 5717771061638545
304 6134609033137542
305 6581108971872646
306 7059331357831790
307 7571476395497448
308 8119893294890239
309 8707090094484791
310 9335744178677645
311 10008713411165141
312 10729048049585738
313 11500003359718636
314 12325053108490557
315 13207903850996030
316 14152510205886162
317 15163091031522427
318 16244146713586355
319 17400477473867496
320 18637202928857864
321 19959782805363062
322 21374039061264063
323 22886179316546791
324 24502821863896030
325 26231022162258784
326 28078301105899217
327 30052674970966481
328 32162687357416054
329 34417443027675643
330 36826643987400633
331 39400627709705827
332 42150407878443569
333 45087717552625811
334 48225055160536460
335 51575733227454818
336 55153930281454947
337 58974745844156344
338 63054258990360682
339 67409590387553058
340 72058968342357072
341 77021798770804386
342 82318739666574750
343 87971779991669686
344 94004323615456850
345 100441278236092412
346 107309149966926403
347 114636143534021310
348 122452268829332493
349 130789453780541515
350 139681664350252296
351 149165031643321233
352 159277987009759120
353 170061405143647908
354 181558756147295487
355 193816266586759088
356 206883090598044952
357 220811491100308692
358 235657032274215765
359 251478783397541168
360 268339535304552401
361 286306029603033438
362 305449202034912073
363 325844440162683774
364 347571856898821769
365 370716580116817911
366 395369060005076917
367 421625394467403439
368 449587674390129016
369 479364349154379177
370 511070614388194357
371 544828822423228090
372 580768917642715542
373 619028897284204323
374 659755300095495255
375 703103723519835970
376 749239372041943483
377 798337637499816818
378 850584714250365274
379 906178250140460120
380 965328036454472330
381 1028256737956326255
382 1095200666508924825
383 1166410599578295875
384 1242152647448647160
385 1322709170670193141
386 1408379751944950666
387 1499482224214680827
388 1596353759574011093
389 1699352021047434035
390 1808856382313595577
391 1925269217725291438
392 2049017268217009803
393 2180553085797347681
394 2320356562778880225
395 2468936548836412025
396 2626832562664445487
397 2794616601767702134
398 2972895057838392840
399 3162310741751488776
400 3363545026385189137
401 3577320111857413789
402 3804401422216619454
403 4045600138805630752
404 4301775880254936028
405 4573839535027878813
406 4862756257487559577
407 5169548634197288347
408 5495300032542594466
409 5841158139270665939
410 6208338702270556252
411 6598129484178732999
412 7011894442497107226
413 7451078145914951965
414 7917210443027010839
415 8411911394376143826
416 8936896485675758947
417 9493982134521646687
418 10085091510284495204
419 10712260681035807628
420 11377645109225228428
421 12083526511683903694
422 12832320107910889044
423 13626582274136885651
424 14469018629594570316
425 15362492574631063016
426 16310034309820916563
427 17314850358100780119
428 18380333622098898754
429 19510074001336877865
430 20707869604805539741
431 21977738586550566130
432 23323931643444349251
433 24750945206071578994
434 26263535365963526205
435 27866732573769104113
436 29565857156078505532
437 31366535689559175644
438 33274718285065965320
439 35296696824910348006
440 37439124211412501399
441 39709034674947878758
442 42113865205641428105
443 44661478162505429479
444 47360185130828733842
445 50218772087813305933
446 53246525954612862792
447 56453262601649364956
448 59849356393471053175
449 63445771347662957250
450 67254094003021718264
451 71286568079973732591
452 75556131038325270796
453 80076452624711902837
454 84861975525734397884
455 89927958229556806543
456 95290520223977944844
457 100966689645285684026
458 106974453519173347934
459 113332810720803140921
460 120061827809932953357
461 127182697882342628861
462 134717802609620545685
463 142690777624213983351
464 151126581439613731949
465 160051568079917017740
466 169493563628280655011
467 179481946887699632486
468 190047734385281504121
469 201223669934682768145
470 213044319011761957668
471 225546168181595505767
472 238767729858244276008
473 252749652661382419816
474 267534837680204835325
475 283168560937428413968
476 299698602395804342338
477 317175381831678198570
478 335652101953285419530
479 355184899123372137907
480 375833002102696846200
481 397658899212725508445
482 420728514376908277201
483 445111392481614626713
484 470880894563307731104
485 498114403310258149253
486 526893539437366058449
487 557304389474523078530
488 589437745584353809211
489 623389358007303162686
490 659260200812987467070
491 697156751619266902211
492 737191286027420731592
493 779482187504928651811
494 824154273540732336750
495 871339138881738508603
496 921175516759655531316
497 973809659002127979522
498 1029395736029970711598
499 1088096257728407428230
500 1150082516296167404370
501 1215535052163897194667
502 1284644144198057386021
503 1357610325395892384439
504 1434644925411238486487
505 1515970641242520247276
506 1601822137558697529172
507 1692446678133061724922
508 1788104790010262115711
509 1889070962029076395180
510 1995634379490886584265
511 2108099696764446760724
512 2226787849797927861081
513 2352036910513884666818
514 2484202985257208176069
515 2623661159475441845162
516 2770806491020426232464
517 2926055054474896508594
518 3089845039133674345982
519 3262637903289854723989
520 3444919587720206279944
521 3637201791291719138580
522 3840023311874327862546
523 4053951455780457188087
524 4279583519236029378024
525 4517548345432136567269
526 4768507961013228240911
527 5033159295912345253806
528 5312235990775132329875
529 5606510296280454931505
530 5916795069023283412910
531 6243945868704433569300
532 6588863161758488398769
533 6952494636644577467035
534 7335837636442767773173
535 7739941714508354094441
536 8165911319388437118033
537 8614908615332820303512
538 9088156445220290398123
539 9586941442869248258954
540 10112617302230774984484
541 10666608211132749358160
542 11250412457816286708633
543 11865606218701525554871
544 12513847536439730664464
545 13196880497532552356092
546 13916539619470575008917
547 14674754457598453130987
548 15473554442641027788969
549 16315073960114758703635
550 17201557683636540255657
551 18135366174470552705398
552 19118981760507416894883
553 20155014708241392004320
554 21246209702236595468909
555 22395452646992233871093
556 23605777807119938817052
557 24880375302217996777453
558 26222598973915004130619
559 27635974643085510092916
560 29124208776419996820877
561 30691197582126100292324
562 32341036555817863143186
563 34078030498315718090798
564 35906704028468637096806
565 37831812614854636842237
566 39858354151722976416846
567 41991581105373185923366
568 44237013258802023185196
569 46600451083377343833859
570 49087989768073940064780
571 51706033937840283593543
572 54461313094593635136690
573 57360897815491691265606
574 60412216745223355979590
575 63623074420340683696356
576 67001669965928944333628
577 70556616706333032520099
578 74296962734129772370187
579 78232212483113030707908
580 82372349353743655102809
581 86727859441265394318649
582 91309756419605689942736
583 96129607636118322384701
584 101199561475395834104266
585 106532376052525468760458
586 112141449299608910961016
587 118040850511740243863700
588 124245353422383045964468
589 130770470880712528405814
590 137632491207561642380689
591 144848516309510523665492
592 152436501635087110845221
593 160415298060249647386421
594 168804695795137127180980
595 177625470407608545604813
596 186899431064328337696718
597 196649471094054320509207
598 206899620983479463185881
599 217675103920277142457565
600 229002394004193615712558
601 240909277251767709122234
602 253424915526995099494431
603 266579913535470819693398
604 280406389026872452018690
605 294938046356388725637400
606 310210253563670875314323
607 326260123134202617146533
608 343126596616658103670617
609 360850533276766786140962
610 379474802977640569434737
611 399044383484159207721112
612 419606462399276814627580
613 441210543948509332436959
614 463908560840033751129275
615 487754991437054580091918
616 512806982491248072000557
617 539124477696225080220819
618 566770352333179497224058
619 595810554292010282209527
620 626314251765596996716151
621 658353987927113179522984
622 692005842915922743980389
623 727349603470993514341765
624 764468940567803911106385
625 803451595429402562487040
626 844389574300825597574712
627 887379352392175184707567
628 932522087415843688061138
629 979923843161012814111221
630 1029695823570518074232749
631 1081954617804503012836966
632 1136822456799185824230804
633 1194427481850239928306582
634 1254904025776296275521868
635 1318392907241268692146690
636 1385041738842503480968416
637 1455005249597147574515178
638 1528445622489925167656919
639 1605532847773306765041619
640 1686445092744565585782322
641 1771369088754630673674565
642 1860500536240111171582936
643 1954044528603140008227205
644 2052215995803364131113902
645 2155240168562801729248005
646 2263353064127461812045773
647 2376801994569417689572747
648 2495846098660003591588296
649 2620756898388311135377245
650 2751818881250276346824587
651 2889330109481202299431315
652 3033602857460175213117081
653 3184964278566798472127080
654 3343757102831174400225000
655 3510340366774840049344209
656 3685090176906189351838000
657 3868400508395932620675852
658 4060684040529756342479209
659 4262373030603077620815738
660 4473920228000690732339247
661 4695799830278059259968328
662 4928508483145750620782774
663 5172566326339246904373993
664 5428518087448546021797515
665 5696934225870090705705680
666 5978412129143827505276057
667 6273577364034366062641437
668 6583084984824261862654669
669 6907620901392373794358364
670 7247903309768853380194973
671 7604684187972788535140849
672 7978750860067512730983581
673 8370927631493439732174874
674 8782077498878555922378522
675 9213103937662853455295095
676 9664952771025521793287126
677 10138614123752166784581013
678 10635124464845185576881348
679 11155568742842262419885541
680 11701082617988287878585281
681 12272854795582404258375771
682 12872129465017947928949177
683 13500208849225303276551462
684 14158455869440840200890449
685 14848296930434585366602784
686 15571224831560998969505049
687 16328801809225451242764954
688 17122662716610879592279870
689 17954518346757713764375158
690 18826158905363945070841185
691 19739457639942986754950179
692 20696374632274547987908753
693 21698960761378612411787178
694 22749361844566019225652923
695 23849822964440209034049089
696 25002692990076153658492088
697 26210429300952026765786088
698 27475602722591085582591683
699 28800902683251716763091860
700 30189142601418579583438143
701 31643265514261890158456330
702 33166349957682767973117410
703 34761616109013215004975462
704 36432432203929143082788470
705 38182321239625210376340019
706 40014967976832370373663141
707 41934226253792504268686000
708 43944126625882556978599740
709 46048884345160903186530385
710 48252907694736539965734983
711 50560806693492877834702922
712 52977402187379836305360093
713 55507735344174365878055785
714 58157077569350116113964300
715 60930940861443366259404817
716 63835088626106581830806580
717 66875546968852478002384474
718 70058616487364770500762207
719 73390884585134005401689070
720 76879238329125067890568995
721 80530877875141915092316481
722 84353330485584541620304975
723 88354465165335413901209418
724 92542507942630203975836250
725 96926057822900260768722137
726 101514103444787432319096777
727 106316040468762531486147296
728 111341689730095565246717844
729 116601316189262933331886955
730 122105648714306024907293749
731 127865900731108165844757895
732 133893791779107957600287483
733 140201570011544795822292135
734 146802035681015568239543732
735 153708565652835101806088303
736 160935138990519372121781979
737 168496363659571364639896683
738 176407504397731180998674023
739 184684511801872603477770846
740 193344052683878320999176774
741 202403541750019852161976499
742 211881174660700580936080072
743 221795962529801951721626288
744 232167767925402908301731827
745 243017342436227885819020784
746 254366365870922889019384795
747 266237487160065108644093088
748 278654367033787829377256858
749 291641722550947509300025395
750 305225373558987653691878787
751 319432291166958481890409162
752 334290648317651527573711400
753 349829872548393630711187958
754 366080701033839999081195856
755 383075238007995756146649878
756 400847014666810229878630185
757 419431051656907806314836152
758 438863924260480180282079827
759 459183830390941730616147489
760 480430661518785653762488342
761 502646076652042461640148761
762 525873579500984330569797237
763 550158598962102025832136683
764 575548573062062598261358585
765 602093036508193374936640152
766 629843711998195189049141883
767 658854605448116876620986097
768 689182105304295766186150470
769 720885086111830471243082641
770 754025016519382796859584695
771 788666071907543722580563213
772 824875251835832715872941822
773 862722502511462004129266207
774 902280844491485239719056479
775 943626505838688122195574220
776 986839060960773623760041028
777 1032001575371864069304219800
778 1079200756625302800162933405
779 1128527111676999474839629593
780 1180075110949351760882330817
781 1233943359376894342482214188
782 1290234774726511003987022537
783 1349056773497090966946425597
784 1410521464716165028855856225
785 1474745851964105812702258891
786 1541852043970179667286592523
787 1611967474138872107478533788
788 1685225129379746498572120035
789 1761763788629404507997181605
790 1841728271470181876289620434
791 1925269697266792396206096491
792 2012545755259525314003588249
793 2103720986070555003850866298
794 2198967075098749517167314883
795 2298463158297804674491993276
796 2402396140852910355725487585
797 2510961029292203278331445786
798 2624361277591318959350621289
799 2742809147852141619667828134
800 2866526086160723905584534350
801 2995743114254014144803827804
802 3130701237650863881913823199
803 3271651870929486730865409842
804 3418857280861495490866607400
805 3572591048141540097533638665
806 3733138548481817438773874336
807 3900797453871995079208376089
808 4075878254837817307277963048
809 4258704804565500590939667599
810 4449614885794429947272018620
811 4648960801417281657487428729
812 4857109989764996299056585519
813 5074445665593639375901025064
814 5301367487831612744332808952
815 5538292255188534684759974415
816 5785654630771911548347293509
817 6043907896904081090470823355
818 6313524741380363614231138279
819 6594998076459498679157811265
820 6888841891929845389004734190
821 7195592143649054628573498442
822 7515807679011582668557389789
823 7850071200857063013308740768
824 8198990271393816792785144770
825 8563198357775200912247291422
826 8943355921032727558822720508
827 9340151550138461398813095965
828 9754303143040803823046779134
829 10186559136591912709758540983
830 10637699787362406878669165290
831 11108538505419154991140698665
832 11599923243225609879365189925
833 12112737941910791498201786252
834 12647904037243442712282537025
835 13206382027741533920828576630
836 13789173107445011852729648222
837 14397320865980907902264066650
838 15031913058655519829961193650
839 15694083449417771485421969850
840 16385013729651959165821935491
841 17105935515876304668448067642
842 17858132429547020027688764710
843 18642942262295321726759537805
844 19461759230058026438154252464
845 20316036319700370107414665238
846 21207287731873581111068146090
847 22137091423998839639563299121
848 23107091757424685706538195576
849 24119002252966009610641323980
850 25174608459200643026809811962
851 26275770938073557231422034088
852 27424428372539997350482153504
853 28622600801166807470586874105
854 29872392984807022448072016760
855 31175997910665766040179907537
856 32535700439286957691118046428
857 33953881100209517748683431364
858 35433020042270097266992347391
859 36975701144766047628009805245
860 38584616295938882892321574358
861 40262569845494055704086001328
862 42012483238139037168578264271
863 43837399835397621897802649510
864 45740489933245722413192825362
865 47725055983411809745801022128
866 49794538026495334295121482087
867 51952519345378038312997486159
868 54202732347737872103201677744
869 56549064686822343983859595695
870 58995565629999485805900170015
871 61546452684979273795240834124
872 64206118493988323552305749351
873 66979138006585029687441421968
874 69870275942223163353084734850
875 72884494554108305931123150933
876 76026961706345612298196197383
877 79303059276848273768702811896
878 82718391898966032387174150033
879 86278796055301177131786129670
880 89990349537708094017006083944
881 93859381288020620513209497748
882 97892481634621763964770335003
883 102096512940561741443462873369
884 106478620679545514348750894920
885 111046244956748967231355851412
886 115807132492086489822956988350
887 120769349084240892316490517831
888 125941292574482341108857954629
889 131331706330045261510717263276
890 136949693267604099963036171000
891 142804730438189376900512643769
892 148906684195717946348205631964
893 155265825972174707523888157054
894 161892848683380719729139204946
895 168798883790213647181606051171
896 175995519041114426791067369715
897 183494816922717899263296561638
898 191309333846488793860227322321
899 199452140100326800443803106581
900 207936840595229632055528810025
901 216777596438269872379428351545
902 225989147364354371659061615196
903 235586835060492905499071462662
904 245586627417610336836111996824
905 256005143746292538546092150004
906 266859680994265686535665419740
907 278168241004870154858167537401
908 289949558857309244460323062975
909 302223132331028312964421249560
910 315009252538216934284527798438
911 328329035770124490509935240367
912 342204456604643771602225557274
913 356658382324446753648233708266
914 371714608696857745923699185000
915 387397897168620606741412728117
916 403734013530765063961302254489
917 420749768110901455360155155594
918 438473057552480116436470539847
919 456932908242840366091815836601
920 476159521454251638475709030204
921 496184320264615029425479695757
922 517039998327054830269989746916
923 538760570560285838118200987087
924 561381425834401243390428787622
925 584939381729587122220003067749
926 609472741448241333614191345319
927 635021352964056463671512439674
928 661626670494827175919677922876
929 689331818389061561374640700866
930 718181657519923141384438000691
931 748222854283604837894347268846
932 779503952302948330316786432075
933 812075446940971693117839724718
934 845989862732965460878673645609
935 881301833849962393505868451431
936 918068187710690222124076243121
937 956348031863579829196756115612
938 996202844265035301732196617403
939 1037696567084977586103685821280
940 1080895704175662392230532000994
941 1125869422344946267576486766908
942 1172689656580545432973093472389
943 1221431219377401023527729093478
944 1272171914326045619221674532120
945 1324992654125860646153946475693
946 1379977583193337004012868617522
947 1437214205041903706660649156875
948 1496793514616586897793039899662
949 1558810135773706246308659852590
950 1623362464103023841510651588003
951 1690552815297234600379128480581
952 1760487579281444249130956590572
953 1833277380323323870366740308889
954 1909037243352977234221096906373
955 1987886766730211836303491428961
956 2069950301705886269219366316713
957 2155357138833318939136799145792
958 2244241701595406900162540933783
959 2336743747523122947492776125203
960 2433008577091456029670089704078
961 2533187250689639341609845394773
962 2637436813973695415629558776116
963 2745920531920923624230722921027
964 2858808131917987431144124199715
965 2976276056226732678601932933779
966 3098507724184810367905397978597
967 3225693804511594759931015394854
968 3358032498103807981561497726421
969 3495729831719693506056837891355
970 3638999962965552372880078811917
971 3788065497013976583730134124622
972 3943157815499215062772362623187
973 4104517418051798665117999547042
974 4272394276951865195574457018705
975 4447048205398574118474041114217
976 4628749239911618892128962836992
977 4817778037400144695511785997823
978 5014426287454398212885201748605
979 5218997140436187441847804628235
980 5431805651965753006538049451427
981 5653179244424962927855710945489
982 5883458186119882525706280554643
983 6122996088769756359562164194507
984 6372160424014314798817573959989
985 6631333059657101853556709960324
986 6900910816389261054980070558362
987 7181306045765932134704842701354
988 7472947230236153783652141214745
989 7776279606056958485222708836592
990 8091765809953238286064789795636
991 8419886550416979089573102627654
992 8761141304572663016969210392235
993 9116049041570049535206870670624
994 9485148973501227421993526194450
995 9869001334875809624352523454037
996 10268188191726486567591674665250
997 10683314281456891523658135725492
998 11115007884584933284237346390577
999 11563921729577450492987612096865
1000 12030733932016312012399718564962