73 20 505961288 565707166 261047080 207716235 366808435 926840869 81657459 231265112 377506150 630289214 421163249 190826194 762145488 113329431 645113820 955513172 271747003 567821354 266395662 197742616 20 284414019 353069813 434810143 521317267 265620915 235691517 398132647 671481419 831730948 636403929 417692122 301628647 617086829 309037489 194708929 590315811 563469536 827608081 610152019 394891637 99 626175313 566563419 804273640 55443882 646501754 51163184 31811818 288941062 423663937 132604336 23860114 755565393 563582698 172819515 549601960 18007563 214797659 308942288 25083846 748903293 231451939 221782035 392543308 143987215 724653783 710872364 743291356 153508034 142891239 656639599 453157458 982553092 678270726 145839768 625078844 882658436 159259388 999441858 408012057 983349498 347003308 900073270 64285433 581300393 855345074 354002058 570910658 848874800 15357056 482541704 827191699 335596556 847223536 256122312 805132229 162347180 637198550 946824204 570672455 2701827 298192985 749827605 294282753 798230686 974500189 100734859 321462444 955920100 138914587 841016943 632962235 697993010 500376971 345349956 999826660 314849936 821671641 866768136 444641821 244501001 9792950 773482490 510082305 542735524 338354820 1907252 254793156 406091854 890083260 989444806 507056673 318739755 989215196 623532849 79334957 851056449 536402337 641119625 18087354 88 205079940 33664119 458945362 703442517 767806623 790982869 895276509 601684010 142345632 878737895 819387249 697966524 411111360 193103642 206859801 454426736 220426028 515590303 875890027 538882806 358600112 632438418 255859633 614490143 185820685 966551745 444424898 571797529 833208824 999352475 695148282 50061754 311929937 899187485 448528645 668348360 120011867 465486489 414776682 305322787 244512679 897738879 925783430 483603940 895632486 438743270 741887534 988780349 270928816 361483088 329899350 864739642 124256510 251068190 653271406 678801423 321997251 246392837 729869324 731176229 193002572 854386639 406765039 862638294 630393540 756725872 568197694 130115336 726939116 858230580 223840165 967982817 979700301 917449567 261211935 592824679 467529849 919834666 575016717 708506237 479090756 121540151 425657576 428065126 707192545 966459082 385497432 740345788 9 963571559 837003110 672188316 542275577 43179290 88553419 640799075 199514070 961764074 31 321265411 107168797 147150572 877591282 890903725 917860655 515178640 260004557 238777886 428761813 449786183 362049217 342096820 836067198 228184400 990892025 677697846 613814821 89150195 244732141 959309041 240856031 843013030 688515598 350041 637759922 67668354 746234775 453137640 224965661 766439934 82 658697164 836796215 427974973 750947185 294635120 457011520 569893008 330579576 487966575 599798788 552202381 341352552 599301271 678449739 341850564 264751392 242760623 465059570 345891086 792492195 646460323 832491388 400613316 761561514 917999855 691914442 404023073 326974250 443522681 132624901 183473237 343815812 638276108 751307939 298389860 581964291 49393580 488584688 443743828 196926220 484397102 372849531 364691066 692975913 427267511 666514265 343172505 441295720 341706567 267363356 601080155 507746209 152514100 311361658 970736849 314334478 743753887 249917785 434206711 175259341 464208149 827911888 974361649 618671557 787828277 997957104 91902681 134556697 562556452 962313993 778275638 5443338 824914628 997697159 328318677 186664574 591480862 513785776 675810648 909629978 40982579 17181509 21 173262279 416144017 205658613 567012169 972122974 139115414 986916623 763079605 565487796 608356725 736575811 503991056 181519802 256983917 605736857 751611775 858131575 763187924 894212693 685841314 679205131 81 432462300 749546643 54672300 13447611 767588264 230056147 269793986 635857092 262742357 536810635 758201540 199438773 281148736 70385061 215234919 832710689 470603910 741988676 473608428 459707029 719639151 833799352 279044692 394446820 836771601 339813348 796203939 795291987 928947574 880715559 591643110 151181686 886360769 298093867 53789696 197317141 578145846 415605536 728298046 924573749 518681167 979702184 559419964 739560039 656088695 39988415 337662708 624579552 851562110 48900412 526243522 521623981 342584969 448653859 244260130 923797098 52630098 334732862 878744429 133404386 26362419 312487038 994441796 244987634 986507889 256138334 391091397 48972832 526351079 791472614 543925226 681858551 330666424 805555324 521103292 79915529 733070843 360309876 410660180 944538781 362292029 33 766032029 32299400 101926258 139503927 758089752 137569284 286654161 638200069 798020 112606899 645208048 158730582 539170291 326866375 902894193 104331186 461938329 513487895 583550024 624838663 625354640 793659842 551495022 395674786 375263158 117398748 922643394 83560710 732713235 883954123 339753769 886525816 648430217 56 241060640 110773876 34952815 612753201 974141902 153250488 156046454 959102570 909746850 265706613 390444964 287585455 876826912 117970614 328615986 54621969 963114993 150519848 925137549 266523837 219303223 770634486 312675987 590068185 132781198 28539991 208926276 34997163 451072358 168224707 261687216 740080417 612703916 420067897 804163415 541166677 152961575 558171970 953121814 21651033 188369025 962235990 898567694 259304528 395722597 174580845 45276455 401008929 464725427 982991538 139485453 392137545 650512205 137536516 202564990 63706314 78 744222841 456727366 679340929 602892067 775713415 774954470 327442566 348077571 922865952 596497440 722245029 812108818 793326329 850521672 381111977 566822260 866621058 568916151 786734845 723680569 659802109 188197711 906730108 739343733 685585704 221363435 357524205 754637602 34032501 52711177 900418701 464309667 554230232 632170310 151008467 350594502 644326674 265588035 320760361 477527340 797803266 773440368 495252779 568588549 970558557 338444439 246358689 257483249 15485388 554618577 517537147 200068998 399062623 627170164 335511323 6677458 108875972 169719236 470516081 462348756 956788827 291128262 181001691 357119983 247418699 590416692 873840910 176411727 278895347 555119001 776915 447799579 156751269 955753726 984637210 456481344 364756154 830268374 71 379964704 611712610 868807411 289634935 109054436 58923461 285787463 939994637 916730137 858700270 849934018 935127183 87840917 719068614 117218157 857013165 222324138 797388525 624423212 561148263 407533610 412819975 938466267 775877734 60263736 788816083 750245504 526137759 3459400 209514166 433039670 522900894 272903562 849502789 10503748 195860412 803867662 797148290 568070847 393679086 459815492 723672920 558968327 631833583 372432545 538530714 185289540 577460609 374710461 96164167 556117446 134649812 128729739 916566009 497569130 802408794 170306013 559945627 162646366 477515762 837544041 489508736 798681490 555369459 177626266 300518526 288846695 402870447 241969273 853044203 721870738 13 928830699 193663616 697734342 830615052 455664504 71348647 278229741 485746842 64878978 313728128 176686425 595359455 329412206 75 797045691 800172477 79760948 724123476 647110564 600977315 989855666 929035487 84654164 750145782 249035463 293531597 507215218 831134119 426246235 311560057 408799160 773880445 116252969 871262148 822760268 810969726 276202283 991945459 473275637 393067691 820587787 705847938 712964482 536861723 622943404 546019885 245032850 363494235 545518262 147460441 969791997 921746408 938827909 529724808 697270278 181380322 48112975 935144332 799327819 746109391 812877039 355985367 848873669 300143411 80114775 17389052 782802077 997368111 740034231 403766778 374439482 743532993 491995271 129147263 640976744 524153346 418023043 291190997 637057441 621668006 492514991 528440237 420774961 617180099 403418425 897736604 884653122 791283046 337967054 81 554172256 401507092 596298985 474227978 965900461 243577434 617276859 779799442 312703636 328456374 363049633 461689498 442008891 941188738 867843541 768387229 469433919 361157326 81959343 411862586 466724347 255855378 589982854 200742063 654627926 412415447 911247538 253930747 545938073 938035992 395177307 293213765 257475970 875335831 710276453 418034841 710285404 505262243 158033383 775789058 996139526 249466440 753488858 220242067 490168491 798816549 320744652 177808419 959125983 859780639 983386481 458099790 99590314 385415917 207773727 659207159 446993792 374718942 954539078 917363999 210364995 217914666 793488570 686095810 284840451 292185831 180574423 728157882 778457817 218569981 156126142 219304308 515400766 644787798 58561291 4446326 92468977 677975543 414693448 853630392 508360093 63 128955253 751940004 410377233 298359073 83293469 131705970 618918134 809816922 332493708 884389159 790231700 151791468 388666019 290331573 630560605 911723486 908918049 202213092 880265009 974813192 650317019 513312816 605531729 456876632 252108564 26446079 760482706 30087023 827054466 165464938 137406952 686869194 478828950 703087722 226365176 997731314 426312228 319864260 643475112 336518479 960995308 4866560 475886114 220577625 670959342 650117808 575198280 676036049 992129990 268027570 827146774 607103548 207187949 225738204 798597172 28986904 658722173 877043516 208407110 131778088 3160729 390419975 258256675 43 517275948 190173667 718622510 33187744 500788013 425793264 446040985 570237427 399688134 61988553 493358733 466782914 857953380 77603701 275967562 724089028 256695827 27566691 813414307 89751574 802189985 358225510 651871988 307655619 493854422 101164096 821496940 23155564 270910638 401117424 913209718 171354355 827770490 458802302 240265953 695959150 322203500 554763773 393519034 864780015 233114790 857954400 339802077 94 829485941 155302015 747733573 594466532 296482499 245442989 59868265 558359974 795117038 331807379 455247051 943919881 269172722 715030281 412614741 18068495 714935569 766545597 324356866 588108034 900517172 759893580 44160222 691988243 683622917 680680235 535631386 434315031 906988880 597121623 214680976 892219071 717228798 259488286 623565019 715674702 374316517 787627332 877838112 845279686 378339355 486702714 384064158 466999383 413035021 362549045 705345242 608533739 496534379 130043259 531260420 473596575 597647732 914065402 697584711 636222710 581878511 188874218 881829731 484931597 386179836 889326417 740528959 798738642 697362897 107906642 356037762 956007514 548564067 243753516 266245071 239941109 177646150 217433000 104013146 347039559 97239432 945530410 329892495 8897509 628816903 517113560 724777493 165162331 229001605 161221489 809679473 645058438 28472398 102577406 599712534 391723505 68440490 302425566 27 261948264 981805385 245620092 281889376 306053952 16484004 386542610 727773971 127951284 850175438 509417802 792718843 629001070 296361787 575029376 373544095 409382861 724324418 678378463 722148038 938341532 176640301 431059054 320011188 962957201 980972353 92950187 25 492954874 330241719 91943135 258007531 625947925 215248201 96286916 579230005 292243916 375038657 331190690 854507219 54607995 623444076 223068531 822178058 66759239 100646489 495860146 259755701 187772414 761580751 112792569 341084019 970183236 33 431838801 160463015 815547294 359400434 46079620 143035957 68264901 292344012 422987 348435511 373669241 290172678 121444371 767741242 457554778 147954200 657274908 894072788 429359096 143986257 421515347 81314194 919775180 756112355 859822920 2768648 86622052 946154112 5266541 229708854 945136840 686320250 877166637 31 149958296 610780074 614419160 319457638 125112441 542889413 37524779 834387341 30269010 66717731 619722675 433659665 906739613 197012556 718281497 344735646 807948102 954168642 911395794 761305740 602771424 435337998 343023582 162883272 370069744 44356663 88070576 876647170 488035141 910011366 909041809 4 978454055 524790288 506069372 420400805 48 997859141 599512594 738488990 271776100 3907429 737007037 124003762 637234820 855243992 703789677 75046145 972662319 265025855 700740532 202514318 254543927 483716584 191078456 18161952 224893339 599598581 81051400 658587276 35607081 248196953 736042523 66326681 32169617 289270058 738053272 198217769 741938110 219653437 910415339 312363287 843760523 526588284 544066838 246671331 258297403 423960534 159438281 50962251 252105997 1025466 896900656 720270021 610633772 32 510224474 961327397 718344518 941372096 255905458 303474144 981935834 658233794 653031448 726257931 325014218 624956361 504576308 479790031 804371123 353576268 895671176 597486202 531465426 445600742 682897674 621037975 282531399 638407936 899053372 365302671 286567059 361958906 889872220 139245544 192293606 582059789 12 72407907 482936776 837473893 584294180 70184761 543014827 137107956 967183540 677586425 759898232 754618228 241806510 4 421480022 161257955 759278883 631123316 41 937977753 274435452 940984836 690664412 934522511 202234397 790933512 368936889 329117082 996328646 586808251 74726897 60818504 738227080 472266018 599782903 742150231 515704313 109789224 249018726 956466820 785691536 747793802 514803327 77950701 148836007 654068594 975482434 899693165 198108299 850559461 869435047 341731405 237469176 296091226 90419518 798178768 286845963 660867978 252821507 863685288 30 639801532 457001137 811500529 497172918 833641330 926993208 334930818 482955988 444523694 341158910 885738976 150921878 573818417 371634491 544875471 631411409 785206757 534081476 201637698 520003230 506797787 395601234 913634803 109476403 54315853 938989990 123621251 616623881 33037172 376255630 33 951112889 7749184 677991204 564420086 440658452 397633565 397165583 472398931 160234441 737314626 218460988 644932940 808151528 539027733 811469323 810539754 407248068 499652502 58587381 185663552 888061561 691382782 654459681 294202475 563049242 137086062 599318658 87320703 662498724 508960237 819828871 70597026 779259129 59 398964095 411362299 984900111 26452917 481793672 65873509 695223126 948203479 305353128 840180508 110311938 90869424 938522906 425444131 10007519 187385020 183242748 388991880 892482141 500479609 153176134 794253611 430871940 416696326 94181709 100560038 154945927 321843547 882431492 267673212 291539816 618430039 58844221 356314967 314850127 53962466 785018298 770826992 112691463 272464942 675687522 511904868 849390244 119380201 274606482 346424952 411619602 495898816 987112409 27805381 512335133 474199340 284648133 237313428 189254285 512840520 509761370 846062798 265586111 79 829379212 760691568 195612103 702323367 757876750 618897434 871625951 977572074 573142628 580028155 257648007 309034965 780036282 923097552 416664785 83458527 781637105 250877599 717529660 843333422 977314123 253262192 161742412 35766070 45863686 141582424 817335820 337796979 565355566 913963708 790829655 482227985 969962254 886009185 148143377 443691767 963868356 334370382 295642451 799823975 362099270 690364109 76102385 986499108 51560244 897372395 536869286 42785448 324397285 762356825 293047839 818506530 949417775 446131811 690533082 935011316 714633411 940933685 83841815 122548439 658910722 394521832 680271806 583543363 557291483 424428297 526090324 409431926 322895867 390433652 938290388 400043614 673832479 956298689 262283465 510084195 981557661 65983499 944583008 91 6719359 384878353 685227014 670554184 37727346 381187845 543951124 922101038 487901854 489707988 598443625 909102673 123064491 751675173 996010832 483256685 585728906 873249493 153239676 882452885 940951344 802505289 222573506 130519879 856801562 616632967 414814697 462435443 405605200 169591352 955417577 120656453 642125215 537162640 271244325 518214387 934227768 677958663 552477207 529927753 522484363 850215765 288045688 774152020 24904955 550656544 916257760 267756932 169225004 952995678 936093387 683355360 661483029 674002181 850531843 808316406 354333867 79807663 974775178 72089336 673403585 172012885 726641179 775196567 242543347 712332890 945612855 119251643 765630319 675698225 535165642 978532166 864121422 118496647 471273725 608027489 217974874 86462351 364370885 800437654 588030943 845794575 154394613 624750152 100361217 119059614 504768074 862596750 593508356 498719246 847688406 53 804146805 913615306 416526556 992678920 905617435 687511301 833494205 166985482 145314736 169291754 38072164 177320487 219462201 715474167 134984720 961806991 104555446 325012922 373789714 200784817 265112667 898786535 888218659 320625223 644878937 996003391 797028106 996063742 561736009 322980648 233222631 161274504 70939979 297614095 874818812 656609699 629156073 290583692 953839257 982244493 320624134 158196104 458954973 600033682 478383599 652542728 718611905 56179882 739328633 218478233 637018224 810246577 778330625 66 152780407 136508354 903816864 74005981 538441117 678202403 705626689 652134240 898891577 526996601 205177163 96737937 738755626 595115044 112268303 732902141 235792393 409401587 286977722 705406165 98035394 672503388 989888527 463060889 900785207 714354400 519564495 166543146 46362787 686822752 520504523 999951162 448371878 972222154 205133632 946221952 353892230 735253104 676635595 252608256 810653886 751390414 539614387 697925528 399066550 316864996 202729903 338318763 445676626 927374282 150971341 237905421 924108207 517495823 758548175 77969152 458152554 689749005 322422355 643950199 754870986 457177454 143232087 933404789 695031132 393685166 36 601141165 139909381 667911741 363769585 799978447 36821219 622781781 94645215 700902847 46452991 35188767 900220586 830222473 387427652 861018434 990342778 759234943 54818368 573967597 668507790 82004561 442451335 213767768 833430547 371722589 353025833 978968744 880632597 294482264 167178170 343510582 779420470 442796393 160184455 503004289 612229989 100 85982330 851539176 956012513 631198296 280765374 580765645 769355954 266640250 263845912 290900691 113511560 856418314 837923874 109406050 808830600 101802001 719988189 387957807 468182524 859849917 746665890 210186399 259702918 746888517 162153711 32879589 63033255 591202406 182612309 466461254 974610073 48715856 563047957 574301092 895401388 323537362 331162068 446588642 626316452 660780619 145044228 8722380 360373308 659236546 370013746 163780393 298602995 620212696 838996137 556478369 12669603 911324053 937597999 948482043 46018753 915523933 616384213 975678434 959121254 23421935 368069494 832336374 124866998 176673374 417040223 415545849 961691506 556452326 345084658 902792523 693257553 561406899 671582261 288529729 297953187 507995556 83265868 761479159 459392420 516206542 555987591 71185663 805163719 752874194 708235073 597854207 743710933 115833467 754839822 772126612 276762439 580215922 962748615 89802975 16140111 672175603 623414315 140451686 887456397 794084972 48 287102371 163156894 198517016 241983468 85942937 878496860 118237596 555640338 588144683 414946055 235191849 157104712 70272983 448119529 513801841 63009386 12975718 751666020 260344089 252427179 681818378 412671848 98581957 449103455 38729355 998829929 667800374 183547227 845778223 555052240 271253952 870681620 638115694 205826651 576356740 753223979 692171652 416737841 58969887 12749930 942945285 215516062 42667054 960636560 797543403 92174273 929669657 891682840 50 922755954 649689471 919442470 190698658 641766575 646219644 765386912 17896010 537189191 689348562 30767197 338137399 80661452 38370476 548448580 118629015 394082752 11245541 41840497 731939486 707594957 1686955 193686860 694649494 654332841 727899412 464306458 80751380 145445310 296536127 212573489 40523290 759562083 889334572 696960644 808415296 685361335 599181149 85818373 517289415 266503539 783590314 337387175 784790364 445112034 700346187 638510671 82154522 150075704 269795854 4 686552895 142073953 642425011 237624939 56 89405378 841265378 527884028 174462598 202166744 125356267 718491192 740188077 761804396 501451640 457301823 16576809 495806359 875612109 372798807 217964839 235413301 993971846 225238551 590866754 853399613 230758757 604991723 262983354 971537877 890592973 964865862 350694818 746967733 747077234 948999823 791464056 154200441 483538191 272404526 230075215 298233373 420613139 143496616 901952995 645770441 929876281 842382340 147759962 636865482 882968202 613924171 122572591 224783117 185397873 123316942 686552532 144430577 936809829 373870740 390673701 81 194597411 402670606 385892258 943286 838439778 359241915 52842285 702679727 933725663 234107219 581138171 824006509 835950353 163046696 70333279 958894314 943904950 902624362 616653630 37242111 896367644 174009315 980386519 612984389 707717396 265704606 315925481 770550684 169321456 38530752 896610149 193751214 490059235 618841275 42565676 483370939 109947843 653464755 674983294 384739793 715602184 495255788 233622398 713637356 137036710 499361932 147741268 114234784 738122284 849013300 862267304 996066371 881499831 223357688 250553923 991791934 560557311 295292203 888987215 776893492 199429712 703566793 996980312 900655492 796209916 273088369 495910260 140530388 643766160 864295114 801843044 993738614 473519880 643203402 813464275 136235814 247297405 889081199 659125537 632307588 167747529 37 30081726 20093499 516739966 853550915 533444258 106075316 702355084 505936855 375886388 125851797 450411166 320043985 354833397 734469411 991260669 99400862 76614558 163972770 732314827 851200503 47723463 409292764 937503928 512797760 335577132 108447761 777230370 918068098 797774746 212854870 926081032 633771271 995074717 574960387 820312771 928343550 275834249 39 288837677 588480615 237618824 452826838 637895047 611574251 621268858 347976472 738916625 786024709 412028507 859990036 985053213 933018580 578012899 93161080 902459895 585951349 439237855 52193663 689361052 282742126 340941920 308133222 940080495 171773589 996897436 204310327 196376495 138553017 253755194 245648344 714518199 762746704 58444227 352202788 120921125 932224394 384190387 65 471018834 872353755 204316161 71865795 984337137 654737301 405171088 453741768 359509127 817269666 93271916 132288093 752748415 378348459 720726043 64121687 979192668 885029055 166617584 415605512 518616776 702687359 383624251 143720817 802933660 490261321 682392066 452123813 990162458 899871401 820694627 566958403 386818802 572798133 394965435 322255073 778230807 399795195 105328441 99177928 740358430 429056623 526959348 656464496 589713932 834677922 670055116 919831035 299439751 351881920 188802617 632097980 194146892 769002538 746467531 270069271 319006655 829962809 537601668 848517274 368502120 192205177 323931944 710255127 998510689 34 345669147 252738745 907378112 892333973 564925047 887939399 501942923 985948746 619740305 485136824 172033767 36307923 724372685 46822256 562155992 542548671 667650909 77845046 575686558 636547661 866404114 150892699 9073042 365573587 927427734 914453543 502900330 339804645 623406253 466173304 574417253 542722159 163052019 483512317 22 891951890 404473925 655109567 168766744 625391846 700688483 527961689 267843562 460208295 236403248 923243719 781137446 803902183 665845059 772347597 8415759 722083966 787359997 977403579 568981363 483579345 599045950 70 666225463 419470079 514265397 591475972 326939621 959613210 83939697 513597839 783583434 662527280 194765675 657679968 237979149 364491799 703036168 940403061 915390557 154148700 674409839 780574338 256996204 523272326 100890674 906472643 361434354 990478290 126878901 581433538 194557115 444247429 770806054 24143148 218758058 231910057 227345518 378767651 117424203 244816345 645232551 300346813 136452931 396089331 168418158 53121075 159719986 407643896 213058779 771604673 142423355 245735328 850756573 230126279 946442562 582507345 287547034 839759209 54655357 266674857 146016877 836361240 299754871 109261720 23344675 79657337 890049792 329039293 4194686 168540455 868105089 952192214 84 365599089 877538057 239708095 274602911 629332898 774615064 429564023 554378411 80138050 800075385 326219032 713524502 831046546 753027946 189566296 45128276 347307245 211189276 772566823 972182056 520895389 899470876 386868530 209745023 27456064 285103777 780217047 150167954 342049860 909672124 916184558 635027838 991828098 504032607 334732289 845391326 731085027 180875751 298042292 343145798 599367402 494349349 752239758 971988852 626060692 132359086 777644269 815422405 698614190 837819435 447797956 243777815 764012190 971544530 929559862 831134881 29847949 42521662 732501246 721640753 799618656 1940030 195138290 142588067 251615064 633139203 126874837 786351128 828973340 90004560 886798926 247758749 164144040 265911297 93335893 388669825 452523061 783186752 361332954 327197915 893472591 881593370 387754932 292068873 33 586543901 884593877 927646465 927131582 782340807 231935686 146714682 726932412 884442448 455473613 594650388 90971599 589098880 237431104 258973997 610316606 309515700 312705105 545005027 749293874 220347790 945501059 962768122 212111403 437701378 36223343 428486377 103991961 213585682 2200656 509841964 375993607 504524985 21 362167500 341736350 77549109 565062400 337848227 487530280 4717852 172964541 295141998 310235169 499802351 814052405 7502082 865533414 183629867 710232131 578115479 202158581 210629432 785824147 392405319 88 608373458 872542952 669469846 46812202 349056392 657819646 824864802 234550922 562042370 873582787 979908059 774494439 895225749 374269373 596172077 85193740 313387121 43277397 714114618 350483381 907138298 500907368 58296865 443049432 529671490 504028440 989363651 396144209 962998164 743852256 811892521 555940963 94269757 506574950 719612049 344459590 633151106 893184364 219301907 418979721 52645455 502933297 682258963 340683898 157453871 675359089 737414942 599178809 956909083 629226297 310755648 380348744 682440140 351129415 956523604 919510903 856856621 864096085 130483883 973277936 612167353 705171776 297688631 928087731 103503840 1426004 433117772 811320001 761062229 589462449 791752850 406741950 197707467 498579681 669228582 109567530 930368579 842992168 545310468 405789185 606856703 241064964 760614197 448879614 876886008 403234765 287401798 622214906 54 382359280 33442027 954064624 988262203 710649485 338684645 707205049 419048591 369371759 658646191 262188094 354402831 396210844 352736979 98585690 566384208 231089605 238300138 642603173 516653924 127725722 635240654 489650001 784840439 50052037 680935806 169065754 64582821 507160246 447343315 111752430 37211035 256629565 903061149 264164174 155391855 304307880 998245085 130044686 894163045 743127073 964897746 144365455 253450198 748144955 44971415 918646299 160619350 829803618 708919110 2676870 169329322 386391094 22305971 65 76925351 372613936 339222377 911069672 295881683 944653435 770471263 628546662 553079393 423667890 579807459 136497336 597780015 810435489 568544617 5264948 312329280 395641298 197219787 1482310 259867748 85446084 229690054 828743650 504468362 715160744 501525974 367324789 867254286 493720503 634833387 446769016 618123848 868744710 197475425 619017616 617295954 747965408 158923486 858532876 949211793 539870135 938773944 847600552 922836119 775482299 847133250 567622489 848382281 300878090 165756598 548825137 837070564 193734724 18071517 104927207 345921808 857613773 910029598 906802711 53623562 511853276 235022613 542393620 721702688 51 473841870 147478966 111835410 736541067 138251392 370900591 817624459 885986677 661827793 914330883 119079094 770024042 466493473 895453128 389392758 203066982 637823113 699259538 172904052 472950768 309456633 141294673 232467538 921186506 226660502 767617777 27184236 575530398 301434118 175280397 938311494 622582413 859954412 803027719 665964568 596709456 460853873 725697476 903157479 568736111 717854530 15272790 256599517 49910801 301546699 351916370 92065760 981573013 191221784 419392527 307633658 72 679002160 133215219 917812812 779692592 918201972 234094186 555787024 193326585 679460296 487112471 743858451 138459565 449624008 691567092 666544851 477355415 852876126 105139089 950798282 798220800 720851452 906481714 465194756 572049666 97749958 803624453 536717109 593484520 76401222 452191668 528150852 480886069 678416504 67942252 843613590 844626365 97776242 413815102 627344304 706492385 770297487 351702292 518268563 373322024 646680814 667669122 328975328 374234182 627058499 840555721 635136412 149117412 163469562 392415763 884722114 563438676 721423027 547049101 526759594 55909266 237012774 942506814 860169235 319079103 389883724 356229973 599912420 377499275 328068872 559467606 853224955 665751765 48 158543283 297822393 691746564 610362683 636005136 816871231 44427408 829580081 161469480 635921886 48431527 601397584 186675075 595509591 380648406 616448225 330450584 519722085 666743223 540049439 511745180 500897397 839389006 888282542 326089929 467017754 904750868 662134419 571886363 941117344 556759109 829193425 335043834 707807403 478154261 25627500 766060771 953498991 5827596 420100365 30403476 341224458 920841120 228556228 874844109 189827658 687142693 442832559 43 590339962 469166772 193429912 595435256 993389689 431213905 115404404 526949628 378852688 260763379 324990532 542103607 587162634 471944487 734829528 544687977 877096236 192699007 252108446 426101981 977986557 804000917 674355959 703666035 740188628 573755900 21638260 384857590 413219705 584102633 633187808 510974508 857301121 688151891 396792541 243066344 784650084 661325726 652287501 642950289 211820075 679831062 959363647 55 924901210 76419430 844115967 567609614 997733466 624835884 553932575 807549529 250075099 691217030 735860304 887555610 458166539 783454272 694349275 823683894 237892356 365266779 123995668 243785544 358415884 326530607 232843741 719154190 89008440 994391733 817725642 665062313 704253543 420171905 109257461 704278863 840557021 26676240 635938996 568497837 300078831 187960277 437994841 930130463 142258742 383684543 845597811 372188863 952263954 145525256 306182184 199915117 132693952 521473487 66149116 381562666 531443710 199356238 717166444 94 732343210 929400104 180417915 683521186 843067844 609753008 344223247 836207034 310932525 47174901 82917312 931505903 349429707 65738901 273427417 792685407 599630627 877858055 372115170 938897604 555315170 783950006 755430482 473910186 193758621 975302090 706005584 423510615 510719548 768452256 884685885 301352209 215001178 777392198 437984682 781359458 708674213 260072145 287036522 710101783 686159787 444380962 561883439 751050734 13362550 246027628 379324162 312162200 238706813 657208545 472123456 15035910 709104851 962736857 689852137 113353652 861101437 208022196 394202000 862918887 940283801 851397849 414198534 356536667 917326849 596069744 744059477 222423565 484907060 946622326 162935001 87229300 411902902 917006967 489971122 371464584 866892710 865355488 311304079 461736625 640438844 656569932 62838103 486744435 547428095 866151825 854015690 128213894 391652173 479777557 21481168 208126763 112552129 150963126 88 367416027 985772311 25410999 11962343 711961903 47046684 688278630 936412573 32652499 727747147 782162972 350170850 62032824 61481529 612124973 744265993 46004641 521778662 818609056 589073068 767584039 591292785 740179224 43617369 599322234 693085128 883116813 758697379 759272237 219860194 366766161 41947457 547861179 20684045 519798977 65505401 746549874 919737270 472826732 372491347 522966242 849307973 408958936 221023640 767462243 608942093 205955097 130969814 892943872 755462739 242097904 358220381 404501005 911174965 420221989 797512281 36909982 281482229 796480821 498606027 465406633 99899987 475082382 589635225 622636905 560478139 504240146 422139897 483513529 28871723 891745256 439072645 905161840 593872546 953929168 135459411 462416675 585505805 243598260 640695636 545373068 45610088 884373142 311299056 241116984 565814413 544381253 42241966 37 958038487 902994474 430884258 811106988 394767877 989919149 356749984 343833690 504822600 491109169 617027994 51085097 748634105 183400346 633179323 221735588 142084724 556754207 118264155 469116677 108760509 707189554 897512333 108969428 550622431 55366507 813039234 174756441 539462095 328465803 998000816 171076104 20589304 756207773 555065590 576615827 932441958 78 837845862 808082190 453073048 496915993 183409828 974506452 90669186 532307856 669995972 197595963 766657856 630707157 556192917 411886526 681133582 629933117 929934620 776032918 578284187 899801272 982973342 174385405 799887623 920427913 368621137 960240933 211349849 660770092 287326163 765984722 553620803 363653584 129715772 190498251 694139004 176229769 467661009 602051763 354618043 965570597 674856027 854745917 405377239 44790145 560346087 277405168 377119964 248591840 122344998 203521178 180937237 976687650 751105226 981372760 51671128 59242895 300864017 40322053 455439167 777550428 94831131 928191106 431311237 438055600 215446614 333867732 178226351 424536784 707694809 436741575 905708006 964703510 989332899 699769307 248869578 657384579 202673660 160371853 36 125005429 526388303 472689503 939973533 479486094 357236415 991736056 420285644 260408110 568817657 267800246 430035649 82834839 479965988 926268129 294064348 134069507 57279020 657458082 334882775 469718835 838179346 63040560 306961643 338521559 561348750 63660614 23181333 891793875 726514254 87970967 796079913 632840596 954835730 223487363 760983745 15 509927301 915301540 318997297 730839900 861472253 754747155 223259632 345571249 659153930 857095967 345245938 847241458 589976924 678644013 211343213 76 950064086 852547895 118964493 304870177 740670708 163755846 243354199 429990039 735882091 778406671 11773586 840427041 504481742 353285084 730105515 731652371 397198698 805341113 585911366 238140293 333998923 337447379 814470793 312029583 178061472 482704059 136006233 854610595 887864896 471535189 936180164 997719854 157386312 714228220 14947829 491189165 955030896 620853498 441931304 118081877 474879780 415748214 163189344 290475100 736548078 595675467 199060385 379898799 429032848 377854505 579403552 945893927 345449097 878567816 493770779 519980557 15838623 656986505 497170347 816088723 737562584 559826827 421574746 640846120 386500245 215985287 486918695 757340773 402318498 200901686 848544559 579678499 27153404 26988154 637349957 313552285 20 745710082 905539612 955466531 337170155 673147649 424277627 362793530 522850119 66892851 92283071 427181459 188099601 7951147 744000837 839604002 863129407 111441710 15922854 612101070 265078180 95 66437857 665975310 191901797 288095496 782673472 409656172 754897618 570232971 27361183 565701561 349891382 682418832 990947139 15152675 559190314 869771791 416358438 491358154 682175660 160670075 83981984 126708049 928903945 114200355 953227805 750433141 983438212 427522014 212651977 547708069 18675250 672357621 407413677 186575803 560306400 276871640 180383892 595380206 352425100 806984311 162190298 236455260 325427991 109791553 369932833 320467770 66079390 103475221 371383197 819590562 382118237 952751023 476011516 47099273 204859033 852464277 229264043 201621937 391963609 180811542 10517205 663641285 322854240 368705804 490281486 684200707 822227673 490080515 283885330 243077347 577994154 789294876 125657761 758012597 394059860 105968549 426321693 139198955 166892064 314409544 516586485 142317993 440022549 748370005 100861041 563849988 224269262 11780845 574270775 694497785 294756641 650301000 787303438 213377451 260005812 60 669627787 28147443 580203578 785974578 876362108 708585361 222945579 410865806 909450213 63099220 732609857 277969055 350457182 902063679 168316751 197554126 979481683 537153253 871868916 978457555 212368524 730184559 938708920 902991685 32902023 158739271 469492797 840066862 138699912 867190227 611480641 893694823 614002890 737905570 22675690 392730124 309326255 155637663 669378915 328644063 518497171 105510029 636376462 739109728 495483656 275909357 993269096 493939071 200261529 122813171 809750499 535463736 483730653 627576917 501012912 403674809 970138048 131984453 570612496 933821330 55 496851924 652626572 245806788 388578008 999981488 305114342 33373677 499093177 767565717 778738174 314770126 253455945 929097123 321288071 494870042 776405741 365228553 508549609 33945450 21665028 37615212 802396634 657627009 638305631 395285739 474780319 877567851 70747390 485461895 899703552 575641462 229998438 337572214 478705634 997538072 376231957 943125190 896033232 54831411 270792488 838571461 372108269 224995192 118928549 297149013 189146504 688411124 175382367 953849712 216191912 578436136 861298855 81266335 323142083 226691139 46 439175351 276324515 619936475 954430744 65322633 431511055 753300058 115588393 30730327 468203237 441177203 703619816 25655365 57021437 378520995 300695489 543059418 853420850 31107614 710954331 731498964 99101283 528536656 704222028 384518001 176725249 213342069 204811029 271385674 685763253 922084218 511022786 198096053 723996144 703916915 457771766 515485315 481117523 70325124 974177017 15834772 679720595 239109037 283246954 822605661 849391154 21 648768929 724102716 919032332 286589064 976649901 480500740 570656926 476192777 432671080 659179210 427068874 79389958 474700839 194145472 46409145 426338781 997005515 594472848 39754403 440789043 835124413