10000
766002689 936026861 81430053 420041425 706663384 75357400 751693170 500939801 44455600 587175481 561964182 82868488 422842840 765204608 683196426 28449177 239492921 429545968 971756361 316902640 524401101 58244885 385603781 988730081 951996281 658723828 419519091 590402175 639546048 456491280 464492800 260815460 768368122 636530377 368516161 446187501 185307500 830449372 953715453 695540057 194355225 106452716 845581504 806116296 555527312 160843564 987629501 181762748 305053701 27627080 956238800 417908980 275527366 675681497 888419231 643191201 525516897 854953856 517405039 166513357 542938800 911208752 178131860 852327081 900648605 347654049 447899720 931988871 780873747 782373521 505511961 145009857 248852961 67282251 159235012 898947728 554899971 701718255 576719200 326389060 654664371 238186197 236596289 233781031 300289700 725312800 381597137 353726033 673931641 953924965 367476768 331012479 538242759 592799511 36872333 741993777 406214301 612613126 376190224 797924130 202076624 126029691 472515377 606671905 267726820 178333820 824728641 459149158 445432440 9804665 53402720 579332742 519957095 960453080 13093124 567569921 107382091 583676534 220536898 665428998 715715841 434856193 798588424 604503530 933469041 834270013 877368256 614694077 147400103 980841412 771174881 925760930 538797176 412263201 83271453 83799241 871630840 588137232 975639293 534850385 199335968 317203744 488439121 128598250 837246084 633338897 185788921 91038160 344667361 554461660 355960469 852338097 413970945 366045507 843237520 117975049 866013740 853803020 464697003 988247521 10717761 580165121 480801777 999800531 863206111 66614033 822226605 945737553 152881079 964773633 203660000 942936441 318554240 19699232 219680941 676994129 164296565 397696441 174583060 653254441 817301601 993478865 217467760 551648601 14565024 29862729 739343460 222492695 912574664 695262656 441298196 396504890 446902400 922064120 124660438 895493921 901888833 558976220 643327929 642979389 631505857 618274385 118467251 757067280 944169600 627290067 398489342 832804865 315504531 378466816 689934191 49004800 844366306 117275904 492813864 509452256 889369821 338775001 67410507 706557606 481639425 321949185 731441801 799648064 969484070 274537261 404043576 644576044 319600993 301922656 738595822 609349201 145554665 188788911 927813120 821141286 111514134 948042864 687484380 976897601 875403969 284049590 503596482 763168681 946516826 917827163 352679617 651230059 399393280 763555113 936553900 404986400 796689701 669155201 840689405 576080098 458379560 759289388 409641381 949648000 177453878 234967761 224222145 135347073 408685950 974989595 332835202 554293089 693129620 296989884 412137854 383208353 965581881 177153153 941591191 337592745 221935038 229069161 311362001 583562513 948872521 304225277 156526133 291881580 777975001 47783676 38165716 372028921 228780937 596415417 995488551 962638545 103476376 631185632 898071780 857696801 300025161 822181606 612110401 354139652 348997345 106393473 621378616 701856320 789241217 964197326 955496408 627543841 569157767 526399104 231863880 115734017 542393800 356379228 52953241 691352484 742149276 308133520 685929757 170674889 121141271 432245200 476781656 827282440 751545000 890051261 475820661 998596241 12767461 85771654 505265006 656129466 498520758 781261096 486475756 586095297 17737388 397720932 578026861 572197281 784368766 418855473 671574087 58558319 507196097 892085441 558871541 469536896 114937600 851838581 784951126 184208681 204401280 127353135 378851650 806159771 18327984 703045106 308486510 90613249 495660658 186533 970640705 206890961 827457468 877598623 454196349 6363594 797481988 616037186 652506112 397694321 71120601 121829728 786248471 412948775 27032192 116151840 160370986 229047101 498483456 617525829 662818883 825965989 905223697 177160141 140515703 308616025 969483246 39048620 744717259 603600917 681645558 725962936 874633751 476373776 202374113 666885160 997206188 512109201 677616057 292779301 180964187 63691301 506960531 828516180 239111397 777359825 557235200 635633750 337623744 786556125 458342926 496383064 467086848 654026457 92024041 835196464 618951397 804833200 582515443 136790688 365351974 823277209 476307001 386553489 226989008 219936500 389738320 919379101 193658950 273832051 26036990 680711125 421654899 162741824 169727790 238426416 608311037 23209601 950791400 108167747 308185024 959233409 316787735 393261992 562624467 347156000 308082417 336202976 636480055 533457279 989348013 715347330 787221738 335216321 680690680 859101185 546693211 753123387 791604673 669565700 420439681 524822577 942788001 502918928 187475841 993603343 263931080 832455440 960733785 90852003 18023452 121304135 571087548 628639761 97805308 377501478 514022784 405656700 832197903 156325160 236666896 541410959 535933965 450238350 877123001 854060769 466367839 400451964 279534144 413559993 327812220 200165821 198402131 800632182 623012626 349572586 105428362 196584744 413753150 81137501 784547000 825469860 330116600 391190536 16247163 890846273 466436920 425237126 833780137 32704820 754781677 322929706 737479361 754181681 931819601 740876239 2128905 395869713 706909912 711059178 817022298 849058001 135329201 552728968 928024701 128626237 957568740 352180480 510818153 673350601 486956480 221133956 684212144 152534657 898894920 512394054 209786961 156799681 776363603 956335292 461975000 806926633 418093632 183853168 589836321 110880428 583594113 917121261 100896709 697558801 588369600 648896201 641198497 309956289 615710733 374512877 800136001 613737830 749468672 444942971 447747201 110319923 152852609 211348497 770406611 379576000 431585280 85942161 65760001 824644609 520669953 228130980 843380032 466329441 649065345 742324457 636615552 354461404 128715832 806495920 298917696 318509153 470841318 590204250 407500904 369221600 629622481 325481060 569239280 215281110 998088129 791890593 932462004 483197122 764961857 635564921 227630401 120573311 783483403 325399553 574722905 826852284 434378580 823950081 64215041 697240240 821521984 560848136 676528476 619894376 182404761 850719133 528179767 338181329 533218007 168893521 872608903 816634240 454753740 91871745 737887616 958549901 597517952 487497158 176778009 434845100 371606704 772367104 179998992 865337626 401527169 376963947 344614758 212336984 345442560 376515281 275434720 866304921 889935101 353654209 592977969 662133610 521306896 374033508 15521161 680178929 360673226 957092667 155916321 285054887 390690801 458134794 241322081 252587368 654406111 338012080 685135521 171929600 45476721 593607329 875794346 422942080 446594441 329671633 438929216 993092008 898336257 779054732 235905441 184572513 15654067 925634712 636442829 772199251 755774460 762961755 648504521 124900641 408759752 471837220 266736200 167966473 978864560 70743991 578339273 978867653 695350701 461631395 27769947 263321225 463939400 351954140 716884959 209562500 928087311 21556060 119464920 813520250 504619453 505716895 348234393 556437034 820920841 513179979 666889190 190402597 397594705 421748589 551804971 499431801 63842208 756695400 822695841 611100224 975290241 333636865 35729744 808065617 976941018 349243145 123205041 81353416 677933380 784049500 586614590 258794010 952411200 297270861 213165049 316685312 241488920 431554560 201631991 42960196 61440702 894412100 968261989 289471178 978392930 76475241 298352651 116620673 723457523 317559376 719890548 186590778 990908033 226176513 221779969 498599312 763033074 888114401 254752561 682830917 10534785 732712000 481814801 484984814 864307201 742875446 155756480 874854860 569993313 417904370 433488585 833882820 437304590 648311571 259485850 232486688 474740850 713486855 527608813 333711520 467327033 952810240 342178616 799139060 161341953 124160345 408214320 920150017 581282651 844978000 285710801 258842720 970790641 611869740 809335193 639198248 283934925 35112960 626555671 243563024 134371601 773938683 542817028 780824250 905120157 658918781 746927424 599549441 326080439 793797401 711573453 73852217 971510656 937810923 875266753 467437400 395889761 326418751 206197174 295612336 10422793 289008140 382131235 116342321 844852641 90854081 328960400 215673216 505446951 206689965 946247645 875325665 717704925 635399437 658065601 211826631 459648800 663563601 806155215 723514501 282067633 755183070 265268621 77515936 288875360 994108991 334828761 144565961 263567901 961444961 736279820 150817086 66388491 170781121 806796622 463992912 207237027 953418561 703417111 610882574 297615795 909179520 856977697 363702208 129703245 41864632 846550160 57752260 130261721 23843187 602302981 549431920 500623361 277299008 357629550 609308897 452736 524699712 984822581 636236101 620728651 659092663 493359101 205926577 475808041 773164361 355456625 349952401 522836198 310842761 677983111 412252163 422863361 419983033 872636001 71094401 258623320 228510164 641279776 846450177 518321792 759278441 138312580 719514641 677540290 770499520 703339375 889081560 526659750 998151760 487995921 902062532 215699251 704150365 696718518 584109815 743114400 4790465 163804383 399437221 436880000 630466530 851258881 693176128 77433929 905502940 632195184 426484997 908511981 654094601 659895240 377248769 775766243 836796741 588725616 278482184 4050159 646256580 174973975 73097105 585207761 610656975 525918560 100639950 841402321 180944030 476148230 788067953 555745600 3457359 344876273 362750181 872136161 553804850 112184766 68117640 627614801 578169921 655677442 455250817 871113600 835627601 539970860 174814785 893850660 245284208 296640885 992524600 261476528 580205441 533699472 941873300 833232537 841725436 13207350 684692279 696406105 218226921 450044198 795159785 24099253 859476352 485702097 834245152 860813270 648991135 406670702 958907741 637613765 379875001 296557520 731063901 88706251 849563264 147320117 407361819 193591558 293911941 301009475 507905553 861737550 966578353 52927995 498377201 540541128 869332023 492552500 625156000 622985473 286936120 920109480 696913944 504566740 175356600 569580227 221783220 552667221 444186368 20351040 299205296 351600160 366778041 83931752 40447625 109838833 621173200 75580992 838926704 419193741 382654620 164144144 600587911 605168501 735748032 717202880 618748800 873283016 474700501 876725510 97979141 40495854 170851601 248196593 622056340 610546071 94526250 926587969 641314261 251997361 861113952 675268640 824729600 701042576 667543361 428093851 319436330 221314732 517752689 416341713 536470603 11931200 352796913 155758400 331008745 806634486 251520497 927957949 374661409 192185133 962802280 505012801 696003451 323962971 778831040 833871187 374018856 822117731 884526881 138720653 320154703 326963650 333965626 173247681 675970416 633847778 322092144 342377489 341087821 708270760 361566367 444447850 999866400 226225153 529502400 58313401 624245644 401821106 156280750 879945898 674338464 75022869 548362752 803114315 534967120 682215740 804838701 337753496 860155759 716342036 29350953 689759421 407518046 134140200 216797800 517831701 800845228 108582105 883554977 376318301 658978810 808290097 691723488 232812825 124341760 493273801 469529442 825228871 755830545 662064830 270134150 740011681 222596609 914785540 89457521 655959844 799656030 660753417 605549122 312939862 12440281 125665472 122425648 381135093 117425006 687164100 477359058 670562432 505806364 594976300 691546520 609655531 26581292 717244871 702054012 715572350 906787711 30488725 487218995 965946600 255241736 506869841 731127323 497439280 514449980 123879544 270063800 486698958 848119697 615785915 970346153 604061007 753112056 479719220 931923451 222968124 981256660 283952960 384100113 724216845 142381400 670778608 48228054 653206160 180591200 253721110 522871239 591711911 922913441 132979121 783134720 79805115 931672441 410967681 97287601 598974113 389592505 526142633 15057325 113229653 32810880 576607641 925111296 516976128 935710401 127512040 383742771 281379211 504540070 134039891 598668153 852056171 75530608 110605575 659588480 749953592 251018733 891110427 579740751 617458285 693352649 544074983 40070408 944633237 626180225 770915877 825720113 415275217 552508384 241011021 127715009 797893825 562429981 67221025 554230915 897762287 996458161 708437665 712577686 161362725 735155808 21839733 816425657 360709121 125399616 225792902 458380000 314008346 81407600 771236353 352502780 976809761 111217023 818995201 17508510 529302985 540991968 108888171 497921043 939989201 774542881 401438784 923622480 546137931 596121141 992109111 535709431 881537921 154239560 656432869 234226623 887600017 574962265 151508790 807873404 658260460 103142065 49382523 640449131 521807000 713018881 892574721 956925716 585804801 8656606 15201300 861227810 231702634 184335050 349413600 540850176 698689089 619286688 796050321 80465944 476123950 643261980 316177324 358178201 213201350 835772928 186457950 976017804 232573361 708874066 375345665 229988129 727823659 47980320 49724288 712710665 163365071 512956636 849985577 566217001 22126320 88374875 217938200 414482828 924016280 41550581 748676448 308409250 394081726 57053137 261621968 528293441 804740790 25647458 758242353 124524714 544206080 21725400 448792220 972142685 831002193 341484033 239159064 851241144 431044916 356049920 971780800 195932865 481849230 788188801 938732848 821000457 911552233 521443798 302774474 771312888 961118241 667420969 343893073 350858135 522989057 821586520 926840950 270158880 871324911 950340547 631798512 178535890 929167721 170179960 622396520 990792356 876278751 191271960 539595936 438157180 395197960 100708843 209482125 331190441 647265201 868056925 801777217 456813500 587801160 682383100 864537767 201997075 405233217 59236216 70418775 576917030 323266400 377292081 575567251 129274845 605274979 849668717 352563823 684869168 935300185 444722015 886522818 870625001 897369402 273699101 437650941 676314993 348634751 719250501 174183983 69636641 24526781 312744321 81494937 231953470 799000 434583465 226186876 390055554 479688960 196195894 848972481 213461189 530264321 705921712 575876261 998672689 923136915 974135561 54097984 733261846 723820437 609126871 783898099 580487447 335226886 547567153 972012969 145493528 318103301 968022848 108483740 250332129 14251235 79775169 248406520 627874564 386090144 468525616 517343880 155358400 388424777 594462977 901073917 136863249 433820800 151582753 152583517 439455750 469293445 308967851 957040375 135806640 632403310 483786486 948372301 599580600 571198601 265166501 746057431 173580977 464093280 140051540 471493373 38907210 62321846 525698952 71446400 121528716 911065464 751448121 39025963 392560909 330281129 95332113 226818221 213408825 908009790 964470000 112601264 491907652 17592746 931648452 157953900 935400475 534011832 465663745 540043360 946034289 553788481 940257160 914835501 939290021 865531600 949477923 295910112 225948116 8279360 471561125 4206757 665280451 162530451 773921126 976023493 684096250 611485777 189677501 438222741 620078272 635782900 43109505 769256533 439362021 234556105 869420000 423621120 229877684 814092420 118595900 783399056 896178743 560718785 688873241 314946800 200307693 755488931 884778498 79863311 155546144 863535744 330597234 961875387 547333495 69994240 886016240 831239361 652205921 350709473 744248625 240958922 803414860 445698208 543623920 733945201 150708644 273242438 747575551 603853110 648467554 671173441 497824200 917801568 647698848 154519800 159412451 892105376 564145776 669695901 641239504 286874300 596570185 548189322 752843765 447964880 871029325 727740811 71159905 897225001 954985596 227361232 180424601 30194788 990942900 786033744 755944601 409088846 342584321 283401055 164843721 620883628 258397052 262288197 932441901 590642504 894325988 669600801 763815411 970450651 306165440 694540161 770246544 914064083 958438211 22700215 314642860 196290341 992377220 513539467 485781908 683124136 790174336 510320921 272612480 47321538 588821249 760467754 378919936 499193860 190568441 482892151 384680182 928300388 169673120 575532568 694141960 109815264 670828511 899169752 306273594 883565581 810060185 772627489 388443626 891294662 754499800 750792321 259066048 456610162 363418229 296127933 384522000 191027661 461821505 452929829 987114149 437647032 481711473 824434561 667775649 1393385 483089490 167099768 364239541 267247424 818810080 634051105 55490553 71918453 737223151 226920596 454716720 99129016 394944500 63283464 446903871 6032426 989245550 513665001 199017524 438909209 491884417 713703153 115781721 195090464 305418041 880646200 751133089 110137641 848252254 514691000 921582800 227869489 57128834 120485272 874192950 256357737 671124100 535799680 17324334 40965550 982920610 597067494 867696637 8059201 903368450 932828125 885182168 859709057 443728613 731130775 873402080 913648793 639719792 599184076 322995568 285340242 86725386 101081080 526406600 605838200 819605201 942633345 642402512 616869051 839114995 735650320 267248800 692732 318280196 140426780 757136200 630450606 50524721 482253 75308368 285015400 20486572 196153051 501364600 79608705 431851301 345814674 223743086 638175245 636462240 822511913 167133141 681173440 70114309 24879377 79804300 279634031 262213988 360315296 129117710 482258706 585882070 201702227 635239041 838083003 595126240 492994953 312901579 544833521 317724650 944630822 864837761 861974528 267559515 751212721 761502361 327588336 526136251 44358032 274616500 797122625 182531221 613617792 227618621 746407380 188469113 63950301 218469083 887984972 830578474 133823681 597507600 566974464 632295001 788449521 148119001 665700000 866503921 567046721 13890360 342202092 841844040 987820601 927594350 973147830 272303532 68317766 943237763 916627146 862823848 399001152 775775761 33960360 585053574 30198796 793847815 84900481 351516800 130444190 422357248 848885521 17406178 342335999 606824592 396538848 331614345 73344875 790146944 253962125 215340095 220000383 604028192 858368153 432093501 154265280 746368792 742567070 726684073 601323980 381294320 985201633 163805601 566912805 443424321 299936745 898283200 880423424 896011206 299818200 102746437 564942310 835589537 721458661 638925461 204852481 989063200 733833271 776943064 287389801 424006944 518904824 85226761 464821760 285200121 66890121 279667201 285274797 884903760 704842276 478915495 280866769 792534464 121999150 516327565 890892432 801375377 332014385 395815016 194393230 894757184 574692517 817760110 27963007 935891251 87994199 256938561 150277167 564545100 481051140 368880128 595358976 503875700 402842331 2374460 795548441 500661273 508607360 742522100 494718120 944452096 678524441 948213169 899632720 311034889 16100961 652281156 374278721 56996473 442275600 391735271 467764764 631085240 628890741 176282561 435409133 291536192 750934466 411985113 603311545 482329088 603153584 556478353 310150114 871900392 962473472 930562337 571485328 807786391 882382937 295744100 78924893 720529641 307111020 431282297 384269601 773490928 506483120 538305 737812501 900333538 145121000 721992727 485985520 838372704 791636319 290218352 16180000 457159680 901860400 876867760 61528901 676351202 817572 117524600 360542735 957626415 285480141 291743750 258437941 870085126 229536000 746212511 929427232 576602940 508377373 933867400 232571281 326369024 83215611 723452072 622935351 226218396 935687885 369520680 89358640 91711760 236362577 331707771 641228660 978366401 76743936 667421292 522995840 715687000 353661771 230485129 936085656 817814034 2428900 954466601 943231099 679685054 542862688 568101281 803780056 460727825 61779216 670367926 68220768 36315196 982440125 867038601 60596451 836117200 941369733 471213112 255736640 372174809 181998875 872616670 371877971 630714466 843354993 876984995 354052463 802270400 797693003 210159932 551470075 841631840 286465313 268182480 362572600 747241820 403123273 95758102 634463064 343328304 448020916 536459360 373381095 67163836 740841657 361881088 971193040 99908970 33844800 627316801 591572401 160409377 332401121 636700656 754580801 519253885 3733480 558398710 315986740 803674720 159809536 463353016 666762219 225111420 179042683 39908601 179565280 171928250 659681655 373305952 385883025 151989121 373359577 580644217 373190891 652517437 928459400 371432993 892475712 819302150 733358246 42216577 717746320 773157820 986963038 82811572 262085499 821171868 962437901 730234805 217820257 962342092 294374360 829972252 246985169 728667681 66961251 469846773 338505441 788970256 76635280 48685406 413089842 828965201 771708481 540556544 413913701 89883488 992398840 192128917 413376680 864422790 659092146 633131216 445395526 122161590 700512698 718297288 462666496 137379201 746327286 486947145 668707156 622440848 418242761 388193520 642006521 276056360 244022923 789147425 758061801 644455851 905059121 428254977 587096065 74179126 824220481 731945251 523735600 859833920 530592000 37986811 665414916 415988380 543392332 800540960 898965233 258059624 327570121 575314400 54939889 639374522 931840001 267617605 351872704 527575058 359369420 513945420 630852937 842467329 130538696 168063021 821361067 703726461 262342864 287752769 293516420 488571857 672393561 311390201 278403032 86113751 101438000 842773243 914912969 396959922 562125000 786876176 706176191 932928000 25505999 655869050 449558961 759012631 67677961 407567073 143864576 983227920 873016801 602525231 44401506 128800261 206500865 199849457 160662265 201371841 697423948 898233601 171271341 392917951 304506336 159787921 561033700 750635761 154110596 503260080 763124001 174225431 689746944 178190360 913108601 873192992 558171465 990239447 894349440 389344921 939021643 907965600 694625127 180278440 551920713 437472001 312235540 338131624 363876065 584131329 654712672 870596005 587134361 118288880 412221760 690976301 736721153 687622807 286380752 833600960 115428340 302206481 459415926 884210280 209115350 875064433 420976520 652619776 716125451 94376050 751612750 617476384 869343585 216153424 172062961 147930400 977426990 984324252 164847552 125629056 486309225 258201361 161988180 928067640 312963141 888495968 332850994 625977046 713164901 913557984 397055455 86612036 343966442 307229504 849246500 951038037 475258561 358969169 235486540 663783751 100060321 972886271 208145281 768691072 892872548 200535521 578289917 700800268 741317184 325824470 205795920 459516101 676004049 899931514 513464851 805314012 144648350 721734921 21997000 912363521 886807653 208666480 626839553 771478815 805626464 104342012 354083520 434236261 878964501 10425347 909921795 968103552 817017309 537380704 345175192 340894601 700180480 85272201 210724061 822742400 372117409 490703680 671922533 107348251 191028001 830482320 427376361 273236480 581370977 49011851 761034241 421436875 361061593 144656480 102210464 758242102 438822781 61575656 488927168 375262065 333078361 209953696 572295476 73728751 815270800 852480001 307615833 279097661 155595512 78674261 732568816 423746030 717017345 934665088 436391713 55607201 35239793 686191181 692348140 448696960 104595100 16458894 563011925 280111925 72369475 47146000 136356250 421654872 549543282 952623773 322403635 576477313 941402736 56575601 713014530 832757511 751349249 513413944 127274214 2749484 709074498 52217761 581790921 112586104 387943268 306461435 385089921 920302374 261993626 840538121 278032791 856883841 495343850 149232032 583929061 51804392 540292400 581620853 557400715 616852480 479102912 619081601 817822245 909522398 224230664 9671041 134543680 985548930 69161152 319710145 759298571 974437952 659382081 368192880 852635245 159572008 223217792 305394077 272278841 942853556 79398720 905145225 690253500 433892281 450002771 832696483 43547540 277443584 360776635 599900913 94749911 831584101 294393136 259721487 194935761 950881006 238510293 490506200 687765124 654082709 412972832 267776971 462986817 321684660 338954401 344348875 146356829 175457120 670453609 623809002 878347700 877057920 939741085 813222160 118733700 206662856 594311961 120268261 428793559 403250160 261236996 597514921 141920960 392335674 225517057 505025241 784203801 687401000 193435251 77403904 578507972 918342400 471177142 53078751 55868278 508586526 582465001 762370790 739362561 739682284 151942801 373265884 369343680 190637673 905301580 148649601 798391777 386196348 71278136 731991508 24682560 816063704 944949452 11563563 310129721 804655729 282254760 752199841 406536651 336425262 11358080 55911753 443733841 851823840 98341600 480995719 219370560 123819241 107863491 90190630 956061368 139273488 807429712 515909968 53138752 614102321 112368641 63930700 934924289 159529768 949639781 991692768 911367461 850205378 41232469 26196480 482732180 310600361 908484801 583685551 354056157 420730976 227101340 640120341 326448362 44550401 624748673 728378261 934744437 146708451 393490500 924606145 839373121 925365126 143037840 416241888 673471740 430336773 82954160 215952169 553736000 55542232 308533840 352136240 325374960 421355905 879178881 112135773 679624423 41084180 974521551 965053405 879830914 171990688 913279266 152758948 31209381 419325102 306117312 419920961 309706799 472521504 575541180 628435041 211380640 311406768 295551928 334689361 46223813 541536751 442545469 321761775 359425396 919524433 843095000 956504478 733782723 632783981 749110465 199439600 234237899 856544926 55694391 655714272 685596685 233300375 257795586 70461298 714006929 12010922 87279329 972222000 94782428 876470676 145844230 216646720 506153126 219300032 65946040 664173021 325090541 687169870 27367168 599052001 111190808 38278356 245612001 920432001 983242040 658593330 871345609 687907218 525721601 688729441 682645097 427859693 111292072 134799 362807072 835677495 370778511 459882776 28557401 827167664 55873164 609137019 771174940 838209374 722702185 35574560 715850987 536330560 931041704 277217920 906001025 103972872 700325300 596300545 395690001 801090581 464905569 632011090 628081088 491669184 356812970 345822065 881964961 751164640 93680780 106503831 314983880 614351041 704065457 9019800 844321658 758428775 125667441 768535041 242856901 834722940 430445138 227956525 695039521 874037058 992960977 677442729 63437315 206863713 751296001 591568079 3353057 41499136 202115140 310717351 920710648 511249170 818803182 581692500 528686451 976918450 199912061 446015880 954785153 945192785 781356161 330336897 266520569 688965793 478514461 8436128 22490380 756284644 591890661 695843840 112082317 689670180 857301638 117299001 399247206 464874402 904908601 330409428 478214171 23361750 319360769 248420346 11478489 999229009 226389601 871892003 63426781 847628213 784929662 583776257 206547801 182341270 452237457 686944340 814334320 351663840 157861500 112606581 221246901 866265473 258649684 811890859 112799526 690757085 268294440 623864874 152955873 394384376 564321940 330014796 682394000 102055721 140079404 790837921 175221900 811731200 869900801 235491401 430647185 980670095 753010993 647858081 118476840 405221265 171626850 560755160 363831585 533264009 229918780 904760027 358716381 871535046 926364800 764703864 305660861 422409041 740846553 202350000 994523920 318480035 99387836 927002300 306624800 566239433 204366960 139250893 588277649 657594401 523035005 232865517 508648040 69561830 625803201 239943596 296181440 453374981 130583825 694786497 484408412 718847170 659201429 79598440 814941601 333472632 4218960 492763921 274218997 814956961 553675536 654759840 511243164 318518896 721343751 394521158 134999229 842849280 537097280 966598237 273184005 49624816 912686037 827806103 294685389 89228526 454712198 844736369 531345969 122101440 567504151 166284178 794787289 940902560 841485197 81880001 821093089 481967041 765235411 463719840 505071766 943112320 808621311 194216344 730449552 830624240 16544205 491581341 29450129 272281312 84525140 304971827 876534720 462691782 407199896 757091528 152906920 770099661 857731137 935741364 679340901 907005848 251701504 514742918 213253030 381936928 959390216 102495181 985054976 234423500 930217600 831887469 183189566 679183248 71042385 886459095 808785738 706742379 453122841 52994433 680177801 92121857 145573794 824853761 445692650 763816501 497822629 874216185 111523517 618431601 24060400 551838849 438821388 48159997 578587840 237580776 336802615 411668558 70651104 433366200 790394375 566844120 761297545 332395600 41693681 983489106 284347575 115449882 856177965 867695800 374472340 40278061 723759905 492729519 765919560 531372000 892079160 792674180 689554151 736832001 513994240 648648517 594020700 892888160 543080932 470656975 583107400 485463627 672258138 524514045 810715185 936239460 351751120 793915761 169640448 179590251 311259149 147758644 419944225 816942176 509412778 335816196 714521572 864933761 701571316 378587200 426745433 687901163 361790624 423898604 152506721 156245186 62050438 872238049 761319681 299705480 677680688 433854377 585635259 408427501 264491040 961648952 284191361 763289401 885505404 970705521 743922553 181295472 639167482 381242325 854192532 781265810 390694125 305553780 742891676 633730 898115216 213001221 149476190 14913600 582223721 274149345 278139576 687902620 456091890 681823214 892480572 171439760 497998230 532913491 754955475 389685376 478307521 557902124 357508080 745013285 845026251 482501445 995885821 253871321 532464496 125362421 415862080 921225857 559071680 939176432 782603873 983262562 43854221 363186248 671552000 698039738 660048391 864396776 82881602 970567297 860694672 461068601 288271391 665774130 966598126 812785750 97119562 295770752 221521697 123231808 630150126 24118920 942074380 255930177 432429760 222151200 96436736 72844480 539730935 543342260 920316460 442345080 298852981 187311322 313560433 632976134 658525640 682897200 975634640 480136782 959720281 654332373 427662640 418362480 422451053 955958496 351685676 643927040 545101301 225977540 513039041 893931677 185669537 368610875 251283577 106094344 528762241 783428781 408347790 722780088 13179120 202475483 168116166 432122400 830917600 382968368 577544987 625830819 457718176 585542289 43728577 60529209 241971720 607626650 111827161 192515200 143957980 543545266 674175696 697487701 348866613 197958081 747170826 780782744 761194419 319295640 4692389 873127219 517253699 110697088 563879635 537105700 968004821 895114561 413152394 996598080 670747401 142668205 359807821 872894201 847591184 249897984 241980115 370848005 587092339 642189321 145733440 532210303 534495841 938968617 51587072 757111481 745440969 949992785 29298540 44340872 239427163 371776490 464855041 784598229 728095529 154521111 291165666 917800496 997271281 760989780 170281281 804334675 688937404 189534649 244360640 949141250 562869672 606083860 445220520 429117313 358660661 643660865 440703287 529516800 283769620 297137011 797374101 987504000 603336465 56570521 766499745 205510144 404837263 804577581 581203009 7976068 252954120 987039704 86352320 120093226 61033438 396180384 672782500 424246911 267614720 73753859 546466088 624624024 427221361 863854785 596044671 984188290 236035120 217470481 603006517 900453529 640912590 650915137 809444977 530683632 678701828 205131521 706544594 521231945 854663961 313204801 278344478 821132098 42681377 886940537 460050048 388440765 382729856 908753493 769240321 463357280 337819961 36412137 202801089 452468101 492110870 99483190 780358241 255642113 604664824 582017025 774479500 66050860 854292560 954937105 763358800 718582361 48688768 779678081 958812424 435204900 615326200 528820886 364014421 430083257 823851250 980624160 284063319 400572400 802270340 914141299 113466438 651489119 161386271 485583856 294272865 921724701 788509464 442787261 944124801 61431360 473683543 348295030 220013649 593843601 708617500 166927268 417659000 140939951 263740423 132573160 835823200 372133921 329218201 853902500 958257800 756506600 31580000 135518797 95244481 131570228 218529840 767976711 57261801 743249250 767484465 953551217 197674689 964916580 103173724 751673077 581730701 336826240 256814845 84771561 648069043 191287265 957143531 315601921 901611761 810272968 935350560 475683713 942788874 520816585 12710081 591589093 628177528 298270192 287802668 105973328 718480000 605214544 90345527 435225001 747706979 935406785 754001182 875071681 203654101 977095035 900503648 723025961 196606116 28752320 707719800 910939801 238628501 140668361 262020993 521140150 426144751 585638270 771588672 488421940 36355821 607360001 301426336 850323201 479569866 954156014 787801392 920568511 990819360 942375936 120720841 459583200 860468957 444856437 581122620 530678870 725246112 820530047 970923720 296521601 583864320 418475408 24877648 578032208 846508180 981686209 235774667 999293971 298437476 979287881 74810936 844895360 147894360 433647799 239397040 450456497 236435809 953764100 179321344 925941200 271993737 667669737 237561036 711608964 468223744 124800805 536928254 229055551 47090600 534953933 145882560 238892761 344510649 815833313 637843716 908508410 686626969 270401410 912890393 75687680 12670714 691193133 164538274 201409476 827095504 653754331 42890137 960402665 114302065 954492993 317078206 759420657 861011191 589539141 625579321 957162985 228854105 989631744 443862376 434947393 891956458 774794255 642593424 738792673 193341064 289862819 248199781 796239569 47155195 451374137 972475520 442555112 654185181 248969379 972035601 438687220 914617601 542983081 302881101 712386424 325906881 581515686 372825005 661613600 187132737 131846204 957793125 816433573 477426801 545050977 112481443 529864578 541268700 604979251 330072850 756562561 239397121 480315821 943575751 321450753 492073065 632511488 836276296 755525140 434150821 436376580 941925824 308839065 737671249 575701840 977782770 536474747 57147593 102467481 706042368 762750231 321757001 745404899 491641970 894554750 81025333 27304920 415711384 269323397 479885869 211553586 682132868 221685817 352062181 886730750 517864017 476910048 574246355 575283524 631559464 307130820 3817365 983036801 802405056 713609701 504006017 771555866 232848800 71094439 106994889 735893057 153957153 547856384 589140994 806162000 664339539 374623769 682458401 100993957 614694150 170660476 409874497 276378200 450975780 10715936 508375560 294657024 813449594 875481655 70742781 266825824 565129262 670287760 193550382 51455269 751939536 801962720 843090006 229412846 227068861 270941813 788240960 551848777 424407296 208346931 21157150 44983036 553209966 59859152 747445081 847365640 129925185 581486681 881555684 994263441 880820064 7378689 405393252 157586300 417991700 659889841 798619766 209078448 729697327 518428289 439524393 518760848 458086686 857023651 138747970 652007441 436114263 109412880 508748176 147615480 663758561 154808344 367206145 756993661 519171046 228645127 772501341 744898061 755072178 986276161 803714200 361425171 894648720 444447560 760142230 83354668 886544001 142772093 592237853 208848701 302833251 699765633 741090313 396382380 101971201 90392816 136949679 716636920 798640496 232322779 594823680 372063321 541994901 70286177 60654501 302464349 580539361 729573751 952757669 602943293 549165393 509528256 976992981 636768528 210449978 999409602 489964766 554865560 82654577 435779667 217086161 753419845 893804845 716652532 737113740 753375889 613631801 563257800 486806650 311511321 826309842 664262976 474639150 735538320 821790851 122322401 384266292 738981026 271186956 221414279 878774073 135143351 86979041 806725926 721160300 828549347 398927320 912459328 281723317 596366956 477460504 579705556 126529600 311725741 327126121 617745261 874142441 658107519 547360875 61250056 369880279 974340880 869431363 635210112 415954481 48982031 971038529 762629819 697747096 507716609 433739801 397311800 781032360 26063513 211124332 275608289 648505251 354612469 338400376 680926368 379155230 694452605 784965973 369466161 492734294 120142901 415659509 349706013 557388256 693215635 585575725 750245846 322997862 452398024 344949781 492191201 959680840 697889281 44101269 83897361 257610461 819579000 468242325 433990880 7955889 674127825 819405000 196453915 559241101 39747202 117764848 475993632 483873285 273429104 451216120 856641985 273000412 745622481 218492639 30604111 372907824 585925861 669681912 572806893 917488849 162829110 453135483 105671281 402316861 697382400 684381577 843924611 26365341 118799616 879984712 825070525 411712750 212396405 918021849 83925373 417354995 668231870 750753740 446718264 241998033 199048199 491411255 303926830 179238944 825021953 703066400 535747121 153884801 13597942 601546980 581560301 107250940 712840200 19466240 87430356 356324409 707366700 785566730 11109201 569746744 201850849 618487875 946506080 27825441 761190321 344348801 70790400 150191008 546486542 600649563 994942128 93279199 385292751 454817775 781683400 507666429 274010088 415000000 182345035 76195269 187463000 799608040 501846481 551284017 1327790 589058369 151790784 278645225 245607070 251341664 249947913 98812112 22175001 857111600 112296976 515728120 651609201 346611151 530044320 490162593 929178 10552800 995279080 674534784 203698085 795331621 621835521 547059220 970644996 371493972 363439289 155253740 54290834 645403160 458453105 498031423 745101500 316317433 244741489 10849465 930005794 827407250 473882401 220790269 964787890 749985525 877844593 860580925 732733933 862497073 543121481 200671004 336838976 289612224 733581601 152197749 277683829 541602740 142065029 941727672 159724590 146979121 845314344 933183700 709779213 347172492 51516450 317193840 652196801 205319936 89123077 574130242 452135271 378322390 988821843 967245679 26904121 54713201 198203040 538701116 232122841 596622240 984663949 860980289 28049949 430135452 98636440 139030095 604488001 556333320 214050070 708092955 314130445 71737681 351489024 235025953 560307792 891078164 584312744 63264001 898234978 498914092 71705400 253873048 429004201 807223624 230025601 86548271 917588813 73187090 675888808 390940480 474560401 643317809 583591501 839576745 859991301 512213760 92541318 590758199 106451018 554476001 627603709 757342321 426892976 797410753 55695100 946480701 852682176 628551963 796282690 922888840 357919817 528746305 901433056 844604080 575800192 219859581 841130239 868362149 938634530 426933751 751812501 871972478 734442231 30592991 441604353 703790016 163325972 301675050 584309569 120638401 930784700 15122769 928965129 567333408 349612696 654212809 808092064 780115129 585041313 129305497 637052800 862023728 832007060 162851430 481274000 305310000 106640481 314052336 439212473 52084345 535851521 593943820 410627301 565352751 979960873 179236221 86792300 81283780 768693972 719941500 365484061 119442310 819909929 947946811 875423809 132654638 576932980 162200236 770404756 516725172 602317191 863357584 146273151 483162080 586136511 386196425 332525215 470809421 832784850 534139531 769510601 991385600 326251393 368483694 839036721 250989227 901281793 944477200 234339376 261490297 995167203 447615105 294276461 771503676 436045952 624617601 189378365 378051722 263500262 66826752 734559515 384118681 163915284 974166101 401868175 300715568 785631804 641728828 688602681 136358500 673488372 403888083 920389601 678299473 395678280 806545001 50844501 768274501 476518740 411838290 77602432 689731500 920610039 486689746 507760905 584931969 942990615 902894704 900883314 804727661 858416895 409752000 831963393 414103041 496518829 760113601 830383361 608445222 740783961 248268031 919608601 653681601 306507201 870159552 190208911 909365329 426638029 167625762 257067220 959055328 465032167 279584664 688451743 74756578 606010790 305604921 419690689 71277531 939857481 85272858 609549249 607393210 400388791 541510001 692147250 948441152 124799321 187999009 276797713 314633600 941106261 341680001 151342590 784168584 104644763 47128337 823435921 170718314 556948280 227037001 254940210 583923090 969158686 845898400 509554945 937180081 92910200 606209520 475968880 583937621 103718001 427836871 232020937 74041537 183363417 399263488 572751641 213758400 250818401 416156615 811479520 401858103 494646417 10742616 845674156 977874433 237576411 622905310 481913271 261974212 201259890 799452931 193276933 663498400 925889179 472788845 167539541 814068856 210181732 551272716 216394716 822214401 599014273 797685151 596397004 398628900 105808361 229815451 42486781 575480281 882844682 503263600 977240748 562138329 393607426 511616340 518931551 838028145 57339196 481925903 61979505 558709857 515325681 995514860 453792205 948962700 64721712 164565301 755772677 757015980 410444201 361817532 116576000 914387908 73868400 666654760 394801174 964432156 408110255 778382723 806197550 582080251 326445980 253475073 107796037 5893149 699183576 986793781 52662901 408281125 180943410 945725101 404546337 71905951 354009278 278987711 602106055 883235832 498776636 809163930 288287989 313286180 98671473 290028489 40079329 770412996 933799428 281554744 326310593 600544000 895118221 885636024 934739486 463677120 581096793 622383709 162718470 870405257 589147137 644730961 61644552 845990132 916013528 787048666 810411297 202019550 22208376 645823518 819193067 149161669 357820010 33155340 622512820 693135664 765009641 212918100 289586792 206518640 623805440 402895977 89429745 58562821 140865679 938046409 262058060 732297238 648399353 699725840 828956081 315753142 513648000 269280500 757564592 642687392 875400705 115791293 453365535 417465505 239422189 671921222 867918800 395048244 594501091 921455802 923316810 729062281 878761564 509561969 252807870 221799757 20354576 867776039 898662956 634539054 792730936 148093500 259944673 204663253 909369920 524952450 954063328 650997661 877428743 588878250 298333128 716143072 802522096 781808851 595136001 322152961 523083960 945950101 641158792 632560020 921568768 575918048 950207425 401003693 763024650 937274636 877831667 82009371 79271033 302040319 432178604 111462548 641197920 803248816 793890922 372895058 780604672 726836720 987712501 278488900 623397134 301793273 340258150 887339669 628203001 531567076 527178363 512649600 708848320 395560580 775408377 530382800 442903680 60050281 179124159 391410218 60248261 989224785 477914475 824583534 19903667 13399041 120203192 974990761 925601088 682154633 616888204 37734833 683379401 994866784 540274921 892389948 374646653 30565121 20330371 929774545 831351297 486128419 8105351 671762747 743949151 892833231 656816577 952449312 618193620 363914781 489276081 703809600 49298820 785353190 7579122 756617374 333279417 943793670 598755436 216156876 300523601 269155656 503567540 940168673 318535584 266646290 787404760 769728440 504607744 664097760 229856001 78836737 979683976 57079181 618711473 462701396 53589703 437726437 676850618 273869313 464983500 988151588 565730011 464291 665623733 610640651 474861120 127352921 624311233 448708286 949278320 718069569 17948732 254343311 740685160 867268633 63473691 243450776 229929961 437643884 986275709 331658272 566666160 972932471 384150960 351126359 656395537 382889208 281090136 382584908 501298000 395776038 628683225 800818750 409620843 290379448 435112950 758280554 197103222 203558088 262004961 978153121 297849569 366409977 799362049 892319201 754848400 523378878 715789841 630341994 695712305 896104337 130843340 122798141 1186817 152675880 196232778 553370080 47863731 555628660 954418631 176108068 383473024 59376641 979963120 802514681 877854401 358951809 792583746 417154890 894420532 872035334 960279617 109224961 78123400 108561601 650535751 576489545 232837548 315552561 79491718 974243635 277401668 630232900 583454528 369145063 978538895 643468951 876502725 10838620 289558677 635847751 671684840 261321864 719314206 402335500 91561040 476616145 10827961 500308240 503201433 186864768 64418815 170233831 998397000 633808720 222518272 877282079 559353445 454101561 417601193 957919753 839725248 937122601 98816057 896565745 65843824 833149496 651072101 73020886 324443251 661739990 451087450 256697563 108641082 992758852 808328687 266716751 96200715 165604801 335075200 835968000 186628430 575653681 883355881 280613501 986041900 950772614 277998491 750886401 868362785 291819136 64396154 559678048 265038112 354969089 203194182 700637671 168951450 28331864 872892384 804170096 206567881 633547348 659759801 526525760 796086251 400348929 958880953 826369960 595335050 524199717 968940037 139159856 1878448 740490456 186579073 268959353 8845952 355140000 917902581 357303640 245381408 722477976 976621697 136735960 146143969 109270225 211924481 383227969 1383036 616895521 733466963 675786998 925678436 58162840 4275000 46688888 649464929 110169801 212696064 799274406 776607700 718333320 339586080 334230336 829985793 918276865 628814937 450184737 596819380 540553837 911259328 622947097 110861689 638070630 28298401 4294873 940748720 723623084 161858381 755788093 772284828 733703929 983923340 739929800 422804051 526289561 347397001 143927121 257455533 664273161 379434206 176274120 817889856 422729400 857059121 562078660 937443750 19812064 917295381 19804416 858843849 804872659 811486164 707340454 481766496 806780070 809807410 831521601 257898560 589882176 712235925 216108890 390476699 96805352 556218020 413689361 897320248 662296320 278225530 207775317 933022581 472452281 163750241 577740609 816232174 664664361 164190465 591010521 441197393 637674626 933667956 665551624 309329728 772257281 161079571 302593809 832938097 974932207 256735937 976066616 469570289 265563200 92111731 126504321 465052800 653060808 3086751 388994134 822117120 30045289 822481985 790356240 503882880 386691328 946150620 209115280 243356793 5413049 144680850 987938561 568620081 210853224 914666280 663031521 130387701 52270612 117955730 775425890 875454976 98684741 650386510 657175636 797618721 113129473 537858996 462843392 702778089 50664001 373913361 455327481 408179097 232124320 806000294 217835208 714468740 767351820 110007128 425847669 279039340 436086336 932939500 251924450 196100740 80639116 555865246 465314692 608282386 742476874 480074800 140070400 256783815 103893081 946321626 568168243 472412292 504280320 403051472 919996796 830951777 207059890 64899438 281350206 889498230 762774106 280669103 850350194 545228457 876242760 541390201 958552383 790240001 886318201 130158966 843925000 64117510 732400750 100421372 126675625 902841151 59639181 768173840 232512100 550893081 343466801 332543900 780429397 992236945 54981400 970217448 349852896 180700654 440467146 255463484 439707296 813978741 557938465 837247000 635961960 400522625 997663300 679230882 350184991 799315570 448769076 319806880 859781900 430621861 612052989 435775297 123523061 800940476 535384361 663365274 623011424 878960336 606068303 735259456 665888700 563175731 278863736 357842972 640732806 475688520 146599216 58551681 584448001 18624543 988129001 936301841 428503601 831786944 949621761 127885899 204071626 650042221 42799170 984273089 790640467 613272193 616358896 40149090 453053120 199737500 735088950 486270895 558307712 368629601 964360175 917939625 7249360 620250195 140724102 509036601 627754626 753260993 678235726 363776609 931739455 934055636 418670849 257400870 60984321 771554321 102673165 759699941 73773997 510246300 329614051 56600151 561543891 240632000 295303337 662207119 256602100 818387520 602122341 951959160 795330588 501924281 79720768 484988648 151338774 350707058 640909635 857657801 185548400 343008501 840409153 984309201 761826048 629779368 714055623 624352101 85312500 989264100 716590725 969451001 446822401 251615771 312311649 806146513 128989401 566142072 221460840 863440264 60631500 822701925 931724480 833842360 80313546 623088300 905156600 840902176 818013565 943990160 788665600 979499271 500856665 774080107 839530068 951506349 406652856 24898780 474103251 706594926 740017280 730098076 215250101 272076569 347592823 826142720 322068354 200850659 663420520 205805953 908604087 772755988 134825574 368256472 200936880 345704201 958284800 258406525 423347582 281581648 363250880 414207353 266967521 848501633 164049281 564392409 901190532 617259360 179343992 495676875 881963920 33650569 189978501 723557011 538977200 34363601 839457161 344504497 259041504 125994234 780020037 694622977 838980165 392037938 707255351 724079686 264610075 219042419 703986501 547156656 902531745 310911489 934749696 794047287 952433589 665195295 586130349 783386401 210836161 900133190 889331881 22423989 837812217 356908880 337624561 806744913 49227180 270140992 208544409 394882425 667951280 781614100 993272565 414369840 423833001 955563904 764323601 734986016 703679629 893221040 995729088 829129162 324603137 762483712 509525968 78427664 422889461 804363800 586847380 922434376 76368601 846500161 366213424 955692289 695538688 132629385 252609800 950702448 97274133 534552704 148787009 122040042 813191872 429459814 31035632 801985149 683012526 987106001 736200512 25729145 786649392 103364200 916071249 916209803 30095873 851516801 547096112 759792738 481820830 791929856 459245190 956281723 439090504 720541553 762326193 419011632 730603318 894112102 881153568 656943145 334803040 739031929 576701313 967221141 464888801 162646320 869490421 835007764 364976481 874019080 710409101 911832537 433939808 133563057 58141204 733672755 178068851 372692111 498746401 40389377 597489875 517559940 417389359 630012161 83334622 374518201 594308524 409217565 4346512 722614017 694141565 747850 981058001 669490321 881209571 793068449 588936845 352050109 411983321 736053888 653478336 168388993 836607010 188784566 194256017 197041711 151800941 481882456 138594268 90023545 992966635 392838760 26963255 322107521 614636673 89574288 454450115 900940720 291712640 463685032 353033428 170464386 684437449 931215600 402348369 1877724 830814702 262021597 594548244 600329797 636910400 355502816 178972201 78056992 147921360 982680065 966305118 898337410 981982977 865621690 326210640 519134651 572296616 983596591 298421317 574119535 513476604 344857561 499310647 303891681 748463169 541289376 366951920 9315111 850463630 950256049 23720286 47853702 896979251 906348441 937703424 318449001 485128884 190948641 786251264 161724473 628273826 59637776 340942179 396039334 215469041 117758001 970514440 349745150 166777966 588080112 292317531 905012259 162947201 526358080 953808454 645616926 884217095 443868249 553489360 955694080 446443073 816853473 12779121 547328640 128108730 300592001 444028811 476389541 681931800 520970655 61477089 411192501 834003769 91870716 372830129 799135413 862667641 155454001 992112269 843805228 95606251 381167120 169523760 320778417 764982740 745868051 999897812 230358986 454056375 876246901 162543809 140568881 534948417 220179000 248671756 848344064 800724705 797962449 206103741 501153945 400383200 464603648 920977579 342681417 142802553 372093632 615345630 169138785 815626801 665686467 166769710 220465794 157794683 277618400 717084605 89540851 418240641 601281434 832837241 530930633 485319372 251298241 803436488 314193386 770407710 534660289 393237600 332031143 606661728 112669393 10982846 727951224 370734337 554989081 786955723 582468651 870631201 697901824 810418540 334368320 694093361 901624321 432407097 563649284 981706100 297375811 815917304 548676741 748088772 974098777 268673097 142069080 337106160 983423371 554228801 373239669 424321505 874156582 663004401 86556925 232810561 416631146 309347861 475471888 900508133 295666661 651648705 926470913 403233900 225715361 844889873 963824528 435728481 682557276 167566801 235311280 699192384 148661361 353245512 359122400 775380233 206554210 238106614 30998308 371414484 548447031 168829500 187317746 535482181 518943736 233998144 888991696 960376100 460583265 881220000 12379548 838242778 180732336 80264423 408223001 15949956 924163180 571117905 527923301 119510977 35448633 957197710 721614360 297687726 649197504 645853731 361492576 124587201 105653760 650113120 127337501 784786800 867533036 610503101 850834025 321012650 330564426 260677401 725835378 113780193 380998191 810826975 5134369 778176593 219061928 809220849 780310209 697221935 64379613 308550340 827390913 330600200 207149254 531720401 273471185 28370783 212567000 913616888 945491201 437483900 47731184 538712141 587028929 635835009 673408231 901548101 680102760 457311030 291332851 798851761 964493325 866168820 549529401 115378801 617537081 969385170 468152329 726845425 9152751 635201040 827609616 347169588 303960720 5260145 53867872 237419696 197427750 486702800 230447681 465613601 175447424 701332545 935477360 322715201 56240328 548628281 325596598 577549201 59325801 516090601 889675477 273024288 954306088 28458930 106486460 650717301 385158400 466974800 322213435 795457657 159572602 900890329 16526272 479728929 881403286 198867384 620531605 161260700 823048033 879397320 693921301 436460001 873481296 867310656 280883332 974071744 724008200 286916936 502788121 148722771 40074210 359079781 910159161 757819501 990137683 888576696 975773051 507410624 101992349 752152651 224850509 120236151 45297536 594142041 532285122 887033688 156468593 503864721 580198400 822778001 215392776 803768097 512878320 40284601 860660861 897883760 474085692 997666802 454522625 979381101 191643871 892676705 576527040 818291750 582009600 231039608 635567207 14472400 522582353 991170751 537667448 400879376 680190529 571151329 385700534 894420220 49131972 742415395 208921933 233363836 922812297 267140850 603988993 947783053 864660310 259750329 595258262 142479855 470106491 256669056 227640750 900800700 667585000 227657558 579950350 645442807 776384512 561853716 99616752 721788075 322265249 642020832 545690752 135345794 408529060 587280801 963545000 728437500 401784562 844925221 68582700 439040001 203383080 628588561 732994825 402271504 967308707 181983760 46342201 561405816 946572364 487609750 417760733 592593554 179727598 725686160 352151022 642589265 762291081 589148401 381117558 435278920 557912864 116146864 259945073 991985521 167050500 176279852 714795955 649258815 495342407 798447496 361274640 462341472 78717249 484863617 850667291 662622273 999507343 333408771 312992792 530504532 811295161 999219925 502948543 667651894 929550720 122871741 228543336 234449927 439910771 813847101 396262917 479489980 579746976 135991441 295012680 355372992 176052097 475853945 578247760 941728350 354458867 255006440 425902715 810329820 774604353 281811690 806610610 309628571 816362310 196865160 267680618 644510080 748481120 718267816 80863201 55209314 163227940 909224960 944393200 852283071 173946357 157737301 42304480 315387600 635996790 805728001 503243857 385137700 113490401 164044077 999988057 108226961 500062512 870839981 23625157 669598752 151786425 669564470 695568960 943274901 35586280 808892801 497788800 149033345 567012321 428602933 173916770 174688461 31360040 844755163 674903550 299795626 632566651 662108277 796680049 410667440 132632381 362384000 329259721 449047301 847045504 436070668 52807264 948819251 679255857 176009905 474871030 343482924 975175921 602568800 615678549 457214183 615348439 582685982 684545254 584915766 623478599 690994000 953727665 323205600 50966273 908674120 638417220 832617464 286265350 767383010 801740581 226910000 270671424 77848330 400628352 728179201 857296830 958506721 803485791 153903242 995562011 91712614 301874932 886696554 195010000 919807600 449686130 751744101 562982805 261764397 236888021 23991433 220100516 382715575 3745221 866169377 962849780 352654289 303449830 174807200 28472280 181073918 132538758 588224800 19197841 773445412 656785680 655244941 462917081 437920845 805762164 951253001 344850001 280232000 279134801 222806160 686708361 936081343 909520001 297911560 713824464 758683210 924457517 136029536 359057921 656664961 259718636 928982991 132635801 49245760 228856664 53550411 32122865 148036100 605817754 92276155 521138350 578514906 504734960 584524949 890606705 549088001 835070831 683994535 80589325 965417728 923734241 769662752 799481560 471642343 211522116 674170384 489282478 322727605 97483842 190502495 483792385 258009280 323298816 740535040 883966796 869221000 888273280 674703961 234741441 505765346 225103477 283218011 974850048 673612271 957843550 352823600 335451992 328965921 126859376 69991208 340208761 391752874 340983920 604975825 922869356 647188049 100399060 557063426 108225977 600935281 864900827 653995201 82819990 620048640 320051766 693127789 338676180 37574161 317890728 382792896 940965859 279326635 339488081 627324770 879749054 892767899 698905362 272958966 51805240 109162151 568266821 26669558 783694178 226904339 385441972 408063859 63009920 360012345 787498738 350491221 459621351 150045480 149220464 376715030 112418551 158145957 320281000 251462720 465781413 837184272 610730990 377025920 601037663 850120277 908483921 165409205 54307671 341783994 547796551 298680033 989955440 178974841 26047925 461028801 289389856 910313751 552396409 386131366 734986700 452974871 896682368 527162000 924205196 69515893 989678080 133544772 242564961 393281326 569940033 882464597 504177381 584106641 594955520 890979665 324865776 425311685 619411487 54030960 133495065 395337298 696066881 322427905 378436000 253270381 914841046 875053585 355911760 465086448 314230251 399381625 453668931 311524331 29789661 900761472 407665912 474652654 148579700 726996624 982401768 233473484 930390969 255270016 294386593 378082176 411131210 92329687 751755870 32226821 350093750 502686361 394133420 748011633 12063507 473875393 795076961 266808294 246187294 90255491 642157344 260337816 568195094 775673900 133647485 50400928 3680000 865917441 45441310 132495361 386313700 926197701 942781199 249310220 276941056 766429104 438373123 80724900 983597062 815550448 796632161 464391810 422237440 243463902 88264420 57458700 693394360 509305351 999500417 914771541 107500680 441530412 636060583 916075021 140232586 433844041 565378881 887965470 875192001 944147259 565829280 553366522 588623001 943914871 881652436 566181401 754086364 608804071 213042547 680036433 838763600 196308952 226199451 680846724 849265313 238714481 864048350 543773425 208921134 463701330 578898064 656635951 303320907 755160304 924163385 256902591 131395521 553271985 965687941 899088208 222188481 680892200 14959835 203911281 895644257 491157964 593660153 346001261 392970561 532544496 483769148 536509301 583227856 386810671 294186083 993924080 475055521 687132367 288211968 353609251 596243460 683401792 299163470 13546221 599605540 768426837 828210945 804996642 775046881 909953825 933985281 927960224 341400411 62224095 499007801 546471461 512929854 877666817 827735120 111730856 660364796 847399421 16519668 35613626 597237602 404514862 228055751 315740980 567574604 201352321 487510461 365972350 591657400 407643781 807297041 198364353 130813617 840595670 92245759 394914561 501050860 685387876 393651361 901202609 369895861 795183307 296996268 58252916 718594433 484635513 446630409 692770766 970411988 237981735 933560928 689385910 223162708 252228305 71972940 635763557 163118821 335649024 23256078 949957392 555076974 250526981 687106393 341775501 494755235 741052481 380504432 702998226 748022144 574415543 790348250 258247201 96337064 410925431 641923684 475776017 785724720 501978449 472189568 138328753 952333312 259489216 87214245 925840151 504470858 818230761 183330080 964371029 554256920 127940241 1840256 393475341 586199521 195357403 57269600 173755089 104411366 940669816 472830801 836590558 630741109 199482481 459285872 952899441 305257661 918699366 353768209 683908416 12386714 33094597 958488320 31094837 456244250 660506721 358431975 849913345 464079960 232151954 900764481 185288753 356917800 596842965 867945345 717193177 524794790 945254759 359152816 198841471 667376000 842503680 446980000 368272001 39704345 504089201 482388456 630718853 832643552 65636100 565129045 310196188 522181824 456807600 48858520 728231876 841871088 327277002 706475104 970264079 59375000 366633592 826428151 784625494 162534641 442443481 704419160 9602311 783578009 72095392 757494561 307594641 914714920 797377300 229818960 278042369 437617001 284469892 165308925 75953610 361099101 536235561 710239040 938139344 103872700 18158185 206522880 767751600 743105403 358429799 572239397 211146432 825643720 593150369 629393665 739846500 761263937 916848385 509527191 54707457 525538800 868849800 693188001 223422607 348097472 16061160 699311801 864663700 849818771 598939510 381733402 251332611 805690575 575679553 344082990 433237584 333401490 253844705 506502680 102812361 372150145 20644344 11924600 778722625 791367050 843702957 650506465 179978233 325961400 594111745 538583240 559883392 462230640 625228545 656880752 849653576 34520096 102659380 720081300 522313742 559956344 409569950 209194272 989344168 587919485 155318820 223175003 113561817 185234800 135518884 646642195 656796033 133333396 512316736 17305821 352123030 762204480 199746800 317050788 889611553 840148688 827048669 202446431 69465312 379665501 114861991 238079681 413625517 542736609 234924681 254162065 160873041 650824600 183038900 346791166 717021440 15227862 582866574 107417542 272263900 839935449 548895082 157597685 512559464 951540540 800704290 649877627 988714760 470642742 556982000 469423480 746321465 173090050 458860301 739050480 729084809 479607980 681783381 207412560 800847357 256929375 66101414 543916285 563282291 117172849 169008321 677354914 286190641 573915746 661246593 955916000 145268609 453036905 151641280 553687160 964239886 165191841 75692835 610215001 186657600 707594606 277599001 406233345 658881105 507952200 87109241 667612005 948622466 300251051 45888161 258578472 718882793 665759489 211596348 681962545 516896286 101982053 860164136 972283301 781451520 810527441 213006020 473046128 166677248 831559600 96194141 573888721 328288961 844577793 610596001 185111797 509003872 121568952 485642167 962561037 323080790 814499249 195351091 980723696 850053200 739625785 385229190 70858945 499656929 90947131 358381075 221588877 223340001 789057270 546061026 360864863 236587667 375036320 556926017 119521761 425805881 811629346 417650065 949053678 498218196 854529660 766516733 51165489 773255249 501441872 304715258 982423063 572756008 295274330 183488385 263837761 55866710 591023480 399073812 497637076 152467233 796786297 339625720 541318996 177132288 367263620 214538907 549490601 395693831 14944360 791972373 179453569 334604374 926667976 514804667 352594095 404839590 731187091 595322820 161621708 358805180 805904151 742726244 79262065 359515438 129599922 275840649 94669740 186530416 316416251 553185929 101364968 226160414 442684722 855503568 785576411 524606530 807339987 95084668 252054201 801668140 721371657 260301448 568410880 17304460 196109000 354408451 666565000 557178262 146186740 629028529 743574868 349751292 986226212 824843429 29502456 49114840 228563184 826282497 28253681 160951582 33059936 773203018 855339680 536442132 559503569 40780577 74551040 827406033 89851333 702323632 593578501 406256221 844381133 437953025 721214548 886670826 525512067 567674757 350264661 178879870 820995092 351346096 300692225 745097840 613307679 614705248 836036360 904100033 822082281 907194850 780795761 912191029 779550190 511466545 364954989 94503425 4637241 106891847 665720290 620161001 615272960 554580404 349546901 380210928 359865237 850650671 672154497 609482490 387704000 214320859 200959802 371030201 31282233 949453480 394747040 653476671 507942248 542441277 346762887 682052073 853252456 799648957 990891165 176751561 580360481 55722847 875793735 448338779 423133384 116887801 691322649 70870090 567671480 169047450 711565505 891568736 168015000 758526981 269337601 668521473 682149276 555848220 922679296 489554940 330243017 947200776 229053601 14459609 247557041 38860081 328680177 715564700 514086645 395940804 842351065 553270576 848948281 986276800 675583800 734184224 548717841 371316337 876132000 558221844 170450921 685919144 371069792 60562433 498734227 579906346 127581921 836838156 233173245 966740243 255119057 608726400 413692800 850884404 220444376 452650401 465076040 797729142 516883391 972905401 836952901 992114627 141826753 232093212 809381928 648481042 279215744 183906849 104008268 799423960 83656821 121553041 114976001 212506238 187447844 889704800 821950180 345065280 9422001 234913006 592279073 273363880 697013601 978629873 353827422 636791701 979256490 583094245 626073271 795738356 2495226 317393221 436019762 699571175 823102351 240721809 620307613 708300326 62277121 963713848 359975009 45667712 936669848 659031160 281173280 672536290 90049440 258116431 377984361 604060601 910647698 506287760 213014671 831638306 241901803 350584851 468975651 74065450 66481684 70978462 627644672 626373337 366178448 296164360 643832320 977196423 69338672 786674060 693960190 835665936 25366105 52285535 626224640 999966401 643146411 863722351 119219430 443226886 679003601 780553233 333693880 51153297 796938400 242293304 153788864 669583069 804210177 732513232 812812005 33117329 173902970 437808121 856320211 316953071 615980320 711322713 284387265 398307689 689824961 449562376 215104320 242950301 533302401 269305320 999315296 645711650 908625686 884849101 714111595 143411400 925942708 906808934 536114416 706115932 732054875 294894140 740194810 930599880 637849001 204928660 616052153 960971231 39652920 321746236 528105510 388947986 951391767 310171936 861390251 18794165 906316891 652839037 383148528 173015001 764229256 152721206 737419648 623548801 599925840 209759848 820193519 69389841 607041003 851455727 321657724 14574780 141020353 416776800 870308526 265193657 959735602 550766143 26756879 928563960 290450809 16836401 383563425 361648545 836463681 455305000 216878389 453657580 151733551 94941950 287792520 954303044 196705396 103524502 152083100 926552001 435354621 300025424 293781388 689547635 714822583 21094080 855761249 606262433 322300502 745092177 476936800 76052001 825410697 536618809 372374731 752139521 651577945 26324384 616156912 450520961 917305349 798054129 209168118 541472560 457514673 379897132 155163039 103940978 334424217 713454951 792485400 342623768 823018277 442235821 404560000 498212726 569950481 307578600 475826049 908694209 817475680 234647840 90238976 217080421 223728932 489602470 999177792 490059390 295822976 680136010 912065051 693948401 59444861 948311201 18422784 55607856 498749275 374031791 550714497 32584705 442509497 328772698 604864132 527363660 434933400 498338197 456583769 458409801 948145601 878848820 442241408 773510480 440525121 720835105 235181685 25775265 260665149 606876950 453041281 471377286 879740569 140421564 614363700 144277230 541057088 400806625 204020800 50898837 325830000 311974441 804298276 713215198 798697743 75645393 809056305 629157480 727688026 266592430 264161105 463252470 999847888 681422500 472212691 855537690 188035561 187541301 894055321 120676288 446002000 377617801 203083391 72429440 895014688 868100000 65005667 242218196 386467200 455383825 612365677 601187000 538693461 329293977 967321181 756064697 443908448 185726656 95902832 75912736 37291800 976840656 375870756 626743041 52928265 815742845 266463001 85651513 336066376 614345466 521441516 743956001 998572067 483506401 354231180 955137940 575010325 579491088 69814408 706024704 499258801 363184816 353420061 741312025 451129172 352944997 233526184 645256187 290662640 599600337 321123788 125047393 160093025 751731570 201185040 548620393 717190200 245289605 415552592 78435352 972034900 462178241 470786864 992132612 45601620 15844420 580462526 475930021 753337271 243902600 512695241 250016964 103638001 117327676 430454371 479329980 108262241 805785952 223459792 253919550 53841905 26079264 129466500 753957911 746598785 167758804 749980001 343231047 736170625 941918437 528952661 214169750 618098188 494758535 161974960 74117808 463033024 762387140 408443641 340583894 378204289 678016721 421939624 349840659 485539765 896286880 780813803 440917532 188859740 698748600 11040640 232649280 677936411 312106111 977729256 419076960 344130751 325463809 421310671 272427706 235981376 341250793 104175232 484980143 94720258 162254725 230877643 735338213 875527394 493584401 638468503 176754801 346187400 902141376 766477171 354270907 225493811 62068304 128599724 782735622 649382785 510468931 735488140 881357127 389743072 986409712 471760453 692140801 132120065 210351857 444273440 132296681 899855275 87737260 612315521 815486066 928438054 971618912 678188640 632373608 986105728 568914001 220282001 466261654 482942377 999915991 885712320 388752832 459222616 173840945 146530512 742237216 384743280 126477001 436479121 388893416 115665572 709011366 574877721 701615190 802231848 217507040 747744612 437165424 652145865 82816825 190113260 224638164 34596740 927571817 31475051 822024829 854900100 562759520 322529 641171840 380062608 758834880 828922911 583698496 239613826 604240849 890848001 929435281 779470201 173316042 655524353 444829059 429191392 174612848 178795521 103128900 696171424 565507460 296119093 27420177 744896216 618731520 525530215 861055065 738678701 515335966 112556560 613654500 696953860 154395820 370825080 186179585 189641384 820962021 698645038 401115353 958405651 466866761 599157849 271399300 612128035 401461265 948144500 792453171 528595410 498178825 190461006 86724661 889372912 797973681 384380281 169389740 810171759 188908736 992018560 449228737 772807041 901725945 247132705 957826157 376891857 214257473 737357832 785037265 236396245 267348061 480833853 319458669 516445596 22335133 8803856 12195417 434187985 136532810 495312257 261776704 890308726 965407530 262741405 353284289 505834000 496395681 363994610 328803321 909574625 682549672 63267647 471136224 344366352 57932850 577230596 185143026 693266641 511162349 886492821 220019210 639034848 182570689 145822000 148266752 471795653 45623960 672316928 285995200 774810000 26534528 71635376 140036322 775073753 188398441 282819920 100866405 678449681 274312697 848927140 610782144 696947201 97626876 200726208 938417870 794702959 957936302 886664704 951133419 128234316 586136756 32946001 309283504 600449841 600719316 189994178 390139688 648342481 806988180 530554340 624004211 969616195 414796481 466688892 294134656 938353185 812100532 440684417 641395801 197484418 844553363 766920751 35159749 156125761 70417281 277743766 848582385 412425281 437683713 213504891 435006725 124402944 115570093 282039794 375536480 212113901 854398719 138978820 373378215 738827320 863910344 967846984 961794062 61107415 330796091 994931393 354116430 668617624 892348351 441396920 254272240 161094653 41040300 936820917 173771262 480669776 362576001 503779761 614581491 784787275 737325552 557065600 529159140 874161601 947576126 653184640 748865181 782202744 943458051 9036016 226466401 799584620 794467440 410191833 262207757 227848056 72723932 947361232 547692581 808478675 949962400 709755624 11234560 194340694 980977784 465358096 739055120 501476671 931595125 829298670 373723200 863282773 360680033 302701440 281456801 6531183 208172841 661940091 43307360 486671701 607916952 308593080 584751680 228423091 643973145 752754642 678524920 816661616 20520359 557042841 462620161 743190973 859441608 339489500 659411457 886065697 134785097 995129968 999705212 769537013 61999957 556955231 396872204 773483081 742857942 863850139 110464000 982812971 608610290 432738500 853182465 658729095 771770130 5966449 106947073 972012971 169383601 245642010 702887927 548534146 849965841 919507251 11320688 861422650 660101424 790319265 591048010 444016604 698313841 727730241 701811190 388337395 713504640 320944473 63989153 763882866 636100209 383185454 849984678 765395181 36958464 343045225 975930989 725106088 936138344 158274409 567626450 843782441 859891582 630910790 976087168 92642712 402649040 791002885 286633556 674668289 341252989 998538784 772454181 33896812 277208802 8634829 553248251 290758605 123837520 780612636 942141071 381312020 186297889 753681793 890377520 917211209 323556801 111774105 49292480 864397345 908609055 550048150 150329120 360685661 686718201 995830401 31837305 212996164 182033097 828283206 320562284 370506960 444052705 288115114 685109761 305409040 577384640 942172200 242044288 863069850 609133041 439823097 501044306 502871801 167264401 224624301 46020065 887991701 886584165 131450464 547577301 199378169 15107500 179974401 809568865 181254198 741349276 596680960 445697087 193723800 249711169 970005100 144807158 111419556 376673665 668988432 490950856 879523231 139133137 984200610 493951200 421658589 689092304 206468144 264525760 560980673 798680961 267898650 732179961 484320185 997737220 743853525 713416670 446151741 402311896 271305296 652615249 813546580 618012568 404365877 908527873 101500134 950370488 20850048 110788005 188924628 344427980 494489300 830672176 852312525 608644811 189682431 255954240 336611940 20805387 615427613 241155199 97671368 383698600 791900001 759601920 28184689 852460363 351367647 873725364 554282573 80486384 494891911 283536320 703755977 648801525 221874337 146281381 668337240 928360372 858976353 194383787 884536241 401304377 851555316 378816400 203671801 848214511 453767507 304055673 369925941 472661621 360027060 294409761 852509440 570442149 826774080 896468117 629516128 611042389 666514881 186860750 978061808 472849810 998552505 358692496 858839904 8467776 953529430 755820107 283820092 887492417 386811701 780605400 683517075 385469184 898915325 643322000 542097174 517277887 843275160 840436954 239037921 848535288 640684289 373791680 20104265 664480832 869726000 987322601 828707186 167495139 157000944 564747000 406543094 221940819 254981777 519135921 567796961 705670049 427109400 489768201 902413969 341109601 888490537 555653880 647306320 136667390 190569843 115150810 273193931 591347640 872924096 131307276 145524951 149785329 338913280 82044240 317060231 667409020 514928484 424403969 643400936 5645392 874227517 681467601 229252821 222815590 211562326 768570793 158692951 419417601 726920891 656790056 517719360 596360301 566215131 983368750 526570061 164769240 47368549 798157931 447531125 577744420 687629061 94163480 505639101 139978532 534133949 828634817 521629760 475440975 840305680 721780731 207621661 736337088 317602155 2409577 969742696 138416006 970171925 113325218 128280080 61130260 299495803 731288231 694713601 807762291 142678913 931405056 700562065 27227600 795909718 972309110 555426465 749507201 677815681 865478145 183497080 130847338 910871488 957502773 891382404 749511520 618925221 357919515 953576960 806010021 774450980 809198633 518562061 484511052 754217036 581443104 743902560 911743205 24880845 88027137 346474085 878959263 400923512 455712917 727817680 51049160 263553237 693503261 343257887 481625439 492221940 479906558 173708513 242521833 377531775 102903921 177062421 551267317 61899558 887412121 767686401 735576001 853669161 681337300 634479361 857493495 445607161 57586694 615318393 244195296 382261785 291195001 303084344 25865820 128020106 994570426 724984930 622936860 581498201 349103340 201652270 201284150 420475944 261899373 121920863 499802872 652955145 265055201 783385807 556098668 140521401 987739795 660625944 470138048 808699361 48627240 633303886 11394488 621248965 612191591 87964832 517410380 766416160 567806641 823677468 800051001 496759264 265916978 320672231 674785520 832173115 13097268 623038684 455644160 654315001 513807161 889355264 654217135 718072864 117255232 268032678 477703489 587973901 602463520 314358761 216485510 307190936 201700181 881475400 513261200 494060041 212516533 643720836 926470005 365776900 978322935 106969329 768070563 651576065 405903630 864239753 274514836 591580880 958478286 53525120 227042319 876469451 692843361 211294410 439394305 339322742 78214570 513177580 896735400 294037982 90892800 516815241 595534385 935873680 436467843 865387127 328124801 739505026 153531221 112547751 607676472 22987081 174636384 523322140 980064114 372696577 428247424 962203230 128772020 871073081 68510505 437576448 667017550 33275880 312367213 180617440 710981080 464882948 983687957 947387347 283413890 400991352 423898675 915929376 207206985 84597081 989474098 321937088 648277140 734060097 617910062 350741500 393470533 147998501 183413708 275759345 344584745 602547501 901312650 371073156 927785000 265340332 84058327 6902531 873968001 567766320 819034001 247905393 689626067 518965061 171888217 953466569 758460981 268457480 347390961 497016800 189161400 848112321 977381480 833498081 809937229 205767396 624512990 118605376 351634665 993710948 995281840 247698256 332149184 163464531 901219393 236558491 493754400 128054986 208394721 397085000 161728001 184062713 260876461 507750088 731346560 970618729 439827890 426754770 65584169 346610400 240215089 602357460 135416165 929251448 349967488 989477381 954471964 301418543 696260001 212806017 195896423 811131665 942917873 407124029 504974334 891214366 857485521 572166400 36559098 457797960 737459064 540343921 284489160 341782989 450807040 559936521 660787576 235477830 868018532 233957082 262976871 902038051 723320044 17232694 12255280 208683485 769353881 657374984 13967736 292180997 442328013 80302660 377803992 517162452 915220844 459343601 994838849 617728840 311780800 529443541 880853050 920682004 769357418 404389665 339485190 476247278 335938251 770565473 499350438 244976417 315271311 70400001 299974632 981389901 592755933 158882040 797206640 162430080 839818041 243107806 451925000 628585361 980880226 520645897 42870605 117016095 51374145 93814105 780998881 258308289 278701920 768495929 807012590 958850524 158198190 599529280 813413185 847866020 445213126 904848043 382500672 271625314 235377957 250927321 23107923 636274533 771091281 849412925 532626451 529845745 99372801 525446600 376399554 55047226 597279855 801560767 334873631 5774913 42807680 46655617 689851202 110359016 717031824 237547916 860734505 286212690 535340902 877341301 742507507 535263626 321766977 267035857 401625949 942948241 429322368 586709521 166202524 437493165 75681305 989985055 188166026 441300993 270998726 421436280 947213270 667758821 281311681 906990450 413645016 816530587 252346513 630921985 349990720 451387121 953501250 129495136 441541492 284552751 10949351 143766320 432556625 559590980 402981120 994764544 448595583 553160352 840702400 875037343 521152745 109479864 442555648 493458956 852839374 794208335 747087872 156838687 486806960 488238328 374879951 402067153 751900901 245886960 201764096 611130201 269440040 176028301 785962466 175517765 923356640 777416457 363447071 990208432 532770240 842865921 847193375 977282081 204866921 3464960 411910157 814532167 905499240 64531393 167317348 919656880 771534272 251933950 317816457 454054451 824298720 905430601 226023322 808408841 173934454 585658368 379968700 407100571 671066424 998457176 800377467 283156421 912016960 922780537 310534496 353031300 622938032 418120329 651073808 688401248 442271693 824971000 627446236 309433032 390259680 994018496 16262766 561904425 36626634 670305306 819710239 490537363 969007072 478715305 309413921 891394048 199558537 451392096 49607843 66974551 413286203 763252376 87677332 249693990 208978944 688541024 311531104 33196270 307927850 954003192 845316930 802794196 365518212 472396428 317970080 186550747 382928801 962137120 908201382 249864501 642296769 397190311 996935473 69260961 983120406 386608905 846842993 842248051 450213175 91930432 387387940 582143476 235529145 638841595 337677079 491875520 324120920 373692911 937240850 188191905 340715045 606273432 370008608 284826316 780673437 280980897 529607514 182716801 263593216 528999553 589732225 572390913 583676032 822104157 354081300 686131600 400896000 54187198 567587200 300661921 841689744 445820626 562595053 782894081 881675692 761998107 469148276 755087282 92801508 305970481 48037612 597361921 910781641 125058833 415407000 316822545 816982896 819811420 339990601 323587500 153967841 316226570 526854400 843575515 686628260 343126080 931575552 433827678 659342261 841470721 918776783 279101640 596797570 825067241 229687184 647710097 712823452 608224171 738118144 684220529 777654527 825586025 383334307 855170721 293876014 266673823 222202400 621499581 531207040 484538705 692591221 500041848 133095972 197469689 912530337 374093871 22135441 38099585 557365564 780489153 593360384 689224775 546978561 697552780 96851788 766072850 511272664 67481072 509133841 938684168 567678581 522646520 918788026 42211561 982310521 392069281 129674180 22413650 991026615 551149001 419889838 698728471 657202035 315905761 599259013 516224711 751554861 454868569 530431536 751160136 631316251 882181239 483092987 798438951 34479040 668946581 842937401 956366240 846594336 874461328 904676550 844288857 58441793 994034241 836044800 248081409 976781745 722552260 340705825 637600054 682205360 602967337 523715376 204147691 272157022 704053626 762155913 92595460 493098817 148737709 100269760 826460600 815688001 140615593 101739751 589722400 573699968 27433360 454784205 266185505 175694158 684174377 993700253 301592881 474881156 308933200 303856188 321610881 632698881 721175501 452488401 747438437 119698296 512232241 825104001 238415248 786131718 285686400 58026826 75733249 611812001 546832481 88916462 695952359 679424289 711352417 280139296 426609841 285707609 797747601 730425715 564961088 52759415 276493220 635649061 328906354 510193571 56764156 662801600 40247680 80502410 115537088 793018834 463669025 191020945 46472080 959346921 235493308 271425216 603047380 140832001 27740030 143344857 249377280 3705943 705571481 374474432 134849250 946697201 670770285 491737799 152327839 355833526 660855669 591044532 553094153 786360512 632801701 298274575 706804881 741409640 106333711 742044918 992404780 122810941 814515568 649803310 792495416 91344555 421129217 229037411 468414861 738272110 975842052 32050305 878001977 86776503 700329568 764687019 199189020 14879621 61636341 745448800 672139060 546287200 881514493 708751659 96592784 240697078 200516311 479000008 36545001 472744620 981968064 449490887 922681232 892963872 758789776 238963233 557082846 440681177 293044705 766336705 311916007 499585160 128861290 188376874 699703800 32558450 122218279 133324036 147585250 428119341 71402995 612626248 184367200 269644425 733548320 936736329 712621689 595753681 631610510 238360577 823616886 855276080 131459121 139018224 862287840 85196150 726996069 485977710 598275225 925476800 808821201 123875056 302825110 389560504 554817143 405758088 965753885 312408140 254857019 332123940 379314368 816030368 509751721 750055179 831216576 529749568 718747878 115677546 536762120 44129921 907789341 586433511 113262 622908536 7239000 89668097 356907281 104300121 666477281 516706301 502662048 30135552 54908580 848176720 816232070 143175060 222170801 70537504 708559660 15759761 5691281 302484770 129301737 696396913 684440092 34507631 555651700 989604793 85168691 825175166 811890456 383133312 402551233 805718656 489776527 265780176 242138128 86747851 486259890 482313501 566941360 468302953 680749920 479522545 370567890 663922517 699641001 549688727 219462529 675440051 811674396 601227993 633407665 155628500 23837017 631844224 247138281 734921600 616862125 684250001 357986617 454802280 103560275 46128717 301103041 420143681 909648289 285230002 848282665 684023400 812425371 426886826 125119750 861883681 877903932 250289360 526019504 265511326 801227777 23162828 990699881 502084426 255164200 310204700 178126005 874796001 168021969 655169792 610692681 676465640 800750061 735763366 979604930 667394353 348819165 242681148 381531321 658391264 619866388 673997760 267050648 426615872 117491588 756066224 849691985 7447433 589017690 731429001 604638200 328577204 138375080 808182400 531425001 411435420 350054080 122246080 456548140 597647901 789735981 402839680 454226113 822223718 639655072 177362504 397931827 673308650 484024750 913944640 302572544 186733760 195152740 915393912 626752490 938116392 337502720 191783217 119808893 362172481 767739111 194156101 905832001 906602096 995358600 541163210 734297544 869965849 567121912 217405921 546830850 956372801 48387086 432734416 90476411 444110980 950161520 798341710 110510760 55145633 416102238 891113679 968797300 215586461 622015665 564624750 610830840 622632768 266127457 478471501 722712380 245986826 190334851 139747730 877112840 694133093 3727913 769382401 827896410 544470789 241202028 627096801 627598391 832403941 343738628 600450880 291971439 366447337 499418240 59817974 343630840 973243676 411029600 880777841 501238000 222137599 213251017 964099200 580604576 534721281 101022881 572650961 371154656 188697601 460560249 180150595 101086001 667887851 522171781 993407250 88394452 821831425 324581167 267665136 948204501 444840320 859421579 74061276 260358156 383996129 929604444 546178001 592475239 39492401 776534145 724231856 966159790 395614625 673000049 508699312 424531200 376258463 713951464 57181521 53616491 68787300 393053281 656847080 276477445 745774043 863235360 698741945 526048559 542467917 317730080 901713818 480305590 17875841 130549125 114600001 125457521 516633320 608292255 123090529 832301825 656459285 253315940 76823965 277189497 147928233 711556251 109731230 4939291 876216800 614744394 6909932 662231813 55212634 777770399 298067968 966606831 243916736 200716481 805455149 303158385 930264120 21772001 385032641 403874240 234937500 65400927 474282304 869612785 256776688 440520188 338521190 16756080 45664301 427570688 947769412 972531937 466061128 890470384 134489845 519826500 783322433 484539024 847823556 40896870 64250901 765924557 290082997 27096969 606752031 887730681 540571457 841004757 601720781 680145101 429419535 65288497 711840167 669434561 970195201 353163973 961270181 805935600 409150279 698452881 818253561 758492544 626333038 753869241 428182250 956696360 177934685 785504673 243134422 630056829 933336961 410748660 15809536 768817895 434709572 156778526 763106181 193497856 349481601 51568169 659675892 676658170 451573640 600578500 259919192 246914184 643793820 662563391 15846607 642306588 551888063 969619536 7536825 542033760 580727825 767594049 654690869 647547137 170067025 499185153 889373444 532995257 743747961 224768849 547197744 241263360 135832337 22597949 16442320 214454271 485419744 930529201 230889692 845023840 358501630 921782977 704819468 828854822 141096457 999239961 929518582 278421440 978748200 218300250 281788161 425181380 881104199 461590320 71117401 831711265 390092000 776000875 729523553 855467563 59928325 10078081 347749149 535531808 5906501 203310280 477331060 330864321 550658745 1489350 344882200 797345201 43710626 588296177 895421991 322943872 216542058 306572064 223331300 427998440 442944251 516427585 720054061 568907888 852265816 584988365 576464501 260154336 329742521 586758796 423672041 28805281 884149586 959488400 553713345 954604224 244139033 932358401 724283057 504563752 826770204 580869246 248295596 867065950 720061201 118053584 964649597 407196206 140581517 822210601 555153122 732946581 745434246 641421657 961204757 909954700 613537760 476211585 353618081 833733088 685342312 399027940 221225341 579017192 955997441 649495780 735211250 510552501 644510684 961344465 279938529 679470016 161238225 171859172 492462301 634365801 973936626 505875368 156847317 418712267 957608761 826271525 436501457 179288709 340105290 356159600 327405001 348102920 753013165 674656825 974229890 239089473 199973199 107266466 41763717 866453309 957287600 262963545 407082094 804835948 995252416 469805980 244719784 589508411 510091042 812251608 445025056 667845141 866646080 617403193 299624629 272453651 808359296 967629569 262202904 2564656 598082689 860679298 128888065 294318998 155806632 177400201 760988468 492654929 661953578 446252190 723700150 8478416 265984181 32767067 471619400 565244073 486944896 424646720 400872292 911952261 7696776 955121559 421778001 144131361 326638449 85084903 259482016 920426100 846067376 769636735 299457425 409254460 32463700 250863776 621942241 758421600 237784217 112240297 747414600 724384768 192014401 260951651 743156736 681326400 817186321 766524646 536363350 513163771 677947816 445416304 718013140 436853680 704790820 578298560 144693101 945280312 315157697 177875397 847364801 438572501 543307200 317325831 392346354 842865424 214904797 617152980 724098713 876795441 861258721 570817060 430588881 596299514 397067256 807603349 975755521 718294993 599587886 430574362 140110076 494082421 989370125 548433153 668771250 977283706 114100736 263723201 55954501 723497269 153827060 720516540 120405930 679720493 425924038 677323208 324511124 194370400 848565101 27127866 966879739 232301257 870566169 736598213 309178625 969086000 120294201 716520967 15274876 322228516 627813760 226241649 330885264 393942449 390049521 55008000 358139229 186905201 670915597 155293185 146299881 261941185 301908525 266561129 555811485 83547200 666231248 224398161 806602449 731927501 608780576 117916921 148026401 778452001 633753528 869514060 871921326 420431176 438643804 729559440 498966701 167826861 375405921 105888545 360281815 732523152 624980201 869542551 996580941 79022069 839239375 925295160 897557285 59328000 527601131 922983671 657068344 45439617 736108352 982581957 508827983 880832209 902558558 391667240 669200586 533060540 225451521 181091502 441778048 299567951 601099916 952526912 839022977 327428896 467296251 741075740 704941160 466606377 566827311 424224156 197812543 523630879 208770751 988912065 449337985 994295201 804279261 166225526 206766376 447495401 26081120 53930708 854201558 87397751 384143084 590327647 824749329 44335233 979605361 581588591 393318824 557709857 545750400 373465375 204410850 698756481 405359578 528864000 408490709 777852768 517968901 81083745 872731960 825730126 612118201 637633440 296697964 654721000 134168000 2675201 138899926 450209793 132450804 455563995 441765905 355773262 239160930 391155011 684997940 899743656 883239129 154594724 849576521 134470458 904805785 490571500 212504392 855349146 87074838 671040501 728317713 369183245 256548352 59623067 559325771 543466251 327916626 225470225 302247710 245348660 898281084 642245560 521880554 987849005 664308800 606011544 961314801 275325740 478001281 595715664 853779227 857114001 996500001 786554927 589286961 107777424 77144000 327148721 170181480 463651828 267990912 563531193 266613216 779176960 850561028 761528610 905416577 894740677 103307481 496992129 588373750 759662473 19395301 946970210 492562433 923686434 342789692 129018036 675232177 721574400 713747467 933185073 793316580 130024602 277919960 553129585 293780101 768750069 109377613 264450536 225941504 453321011 916997652 45438216 50422848 998289115 379789520 593823551 271586400 368580104 595315360 846889912 853030563 728985521 631709341 164317429 550956705 737430540 811195376 759353160 645748050 33726025 942124051 331575857 473888686 810382970 78446428 403851300 683087813 677327751 534025866 965552097 188558701 284134790 618610885 936813058 125581416 780210953 570982940 8193075 598121560 531633144 372719780 941316739 582108611 125510400 100157500 302772553 126380020 417293941 576538624 525122641 856048810 542739701 29629207 455836608 389314950 962825440 179864513 247358016 184150814 278223428 131413961 840432056 555883631 52930491 170408719 71479001 761679996 117747464 306972961 207395922 298455521 888995073 449371860 473257185 757383470 640011350 159160684 282268576 832000233 648815358 78148553 813269824 411571401 395760112 838629144 283176640 547017501 418168281 925825521 702118620 260328880 753977745 484028952 279923233 487673942 270372601 232046138 730075849 103415921 129052105 662863511 464636482 625747013 698411720 440903463 906122945 805894481 534184850 566544321 453793484 410010360 487139686 513081965 161953619 417344277 464037540 60335686 352638535 193595451 995979451 938083432 899243510 451831461 925896611 151929183 430693836 907599681 557749096 770486784 146512256 470961716 454854437 470505001 818512920 690784280 274410360 382488442 131704101 891369501 954945800 444479521 210196552 122207520 722662181 350236706 77630446 167054255 200990420 305034290 530056081 562470442 903444567 38850085 458038441 821476086 211184280 434854580 406215041 706916900 831082399 294203201 461581620 189325628 375554681 227836801 127534336 531448861 534043971 637898776 415903030 346545313 787599316 881663840 774937728 614532424 655640960 117749851 265055572 556832235 762176338 70695386 145546913 61654080 488413751 750272860 760653432 661628277 29833862 900716014 86477346 758720896 251425521 725406991 79671527 839533585 188703561 118510330 267463028 865459479 995047960 657568160 145657305 663752677 76682200 763560736 768514221 314866622 146948976 485729726 469351888 282912256 567561121 967383201 73587950 152222384 502790897 820042384 707679401 47103697 465513989 869959420 617605121 742456539 830227378 248779040 266045765 480973601 552018656 170917880 540807169 622706161 829198944 978931200 623809430 463678216 501171923 903412705 890632241 281567393 292202752 796979691 19123433 323037120 427958801 451920001 992996916 963943824 67810281 84890510 533513569 595180512 692162030 334161761 354482901 232368148 271268501 624158721 857528130 757668977 517922415 26237144 460585888 877327888 95121703 163604081 596352704 816567297 825794688 279003039 60704245 735809001 355031562 285348320 401238436 777150689 160052120 39031306 613142484 61840050 782924451 610264765 237276672 97330336 830304206 35324432 427970172 608627176 582668638 588025708 454175556 453040643 281110339 813276300 82618029 197535220 265533529 609348232 649967297 523570300 518821065 166515718 248854056 977175969 555110669 303507302 464823495 537439893 330089216 345452801 665261569 47858360 311962753 417119034 520717820 342563171 94079057 828905601 613377396 959015513 741142048 525669358 284190081 156307769 5428847 901562641 432623439 956238176 230287808 656969396 352940417 334276800 549884378 59322467 10321841 609868825 600564451 274919450 802977320 586755120 489011960 119806535 231970085 581846055 572360001 493898270 201026544 33176964 816043101 670092008 263824000 786958328 927858536 670892273 341120985 237273550 128567767 161327389 275374385 451825040 340623232 633668001 516089501 520451420 991640469 264045539 379961985 930642000 64612800 367339833 741570776 434859880 556987318 137912160 77735732 69870280 642172657 384390689 410872987 379568381 359735200 324187162 492780461 85990716 917894400 937705731 826800520 839674961 244776318 803201771 311519367 841770971 538614193 30309861 615424680 562660560 223529400 48099801 518800508 36890553 396749837 675476748 662840520 775996363 848175841 415155500 747671491 858001920 223011813 951376775 31040631 892898863 811920901 12791290 138331232 449758571 418322331 974907285 25143856 305246248 957541841 449710149 74098800 734402021 505234323 818742937 622410512 865508545 246738751 179619441 684412285 17677990 23480825 726490544 496983245 416662665 249275591 213226080 735098295 910295377 77342081 272453899 74393776 829643072 542092669 808700416 818937920 803110308 503080280 596676600 444790401 627555457 841737196 267547436 933260577 972263960 309230352 440632023 348862790 428412841 473889001 295895352 112590270 932339016 12155040 309670600 822627072 362467120 902923000 733890891 902572440 670512112 487134865 750080609 271890391 625577625 802430120 239516360 291360052 390475725 210509749 581040705 836669271 65662176 267208491 386120001 288334915 517073194 868753006 113083888 720946660 947461636 953146341 597342241 874698928 649896800 80885601 806496156 570986999 315968000 227897830 962851841 882677501 803607841 94411681 883640872 717186545 208159521 638685222 817903613 453171904 858593937 636946231 199961561 231143738 729943760 947299501 190363840 484457104 909431713 175778201 898605365 341057500 3503793 229659675 159297921 768210945 508752400 978134048 628767255 614235430 392279007 27043416 528085460 642798951 610435712 375900592 147727064 473457670 374206528 298859228 780569600 203976097 615099120 761718977 6384265 945041791 838647045 531469645 573097270 505812823 477016161 976792693 901704692 804897765 705753358 20205569 475354624 547605395 653996003 316858081 945451360 105300400 343296608 316202272 712478161 848637352 968031361 86157096 320873937 417926144 137851353 704071327 958725409 924821360 93205280 861100337 524133961 342588988 66947392 804845941 397848001 893849428 197861812 870833725 900797584 407936608 479969921 614247091 876446465 106297772 841318541 409775141 650040251 118406400 72409801 648197612 418254234 259674186 898205670 70493013 348908801 396495751 823706369 605401364 820505000 694744561 82861248 784901120 592069730 746598976 916541892 760483782 641745660 449802096 571684827 40958492 442125600 283838901 536535536 209875057 753429001 758833280 776089341 664715604 704418504 381899357 336148513 18197589 487623416 664214992 759268891 61511177 456575021 6445192 435521162 660722181 323124751 68124416 981967297 432066800 14616564 154206601 897547024 844838657 828151959 921105632 201089591 289041611 943125248 375746219 763165525 49081537 301049197 522113473 971838840 882286656 395358341 931434840 5449750 961161308 631449773 940441856 644997984 524797616 939476529 623049497 153883092 82688961 359103176 570207569 166918509 980108460 252899825 638693201 253047776 81658925 980011129 434497024 542230395 427877181 620751567 397533366 717745616 934409964 67519015 521255242 623321920 695909016 40411240 431397635 697240032 905859580 13874600 708581133 807635426 757835251 641021216 967786955 613531511 551370636 853542921 564446651 733221191 83163988 702958393 611275300 681137072 692693760 550857526 2483040 327816800 912761640 471031361 512259876 740116103 979354241 125922432 977062808 964918833 151876407 139324506 244352320 943271125 277123712 818095131 238706721 398700376 2564632 709621994 530210960 912999690 709677842 30372281 43053681 934603952 531331961 254927046 930290480 137723550 266450220 698301345 701529589 900969680 946939668 722328250 452630808 31789588 809311680 389321691 507149229 89029065 374707661 474975601 44294540 481872601 31282536 690167633 655496092 244257401 745163053 768325286 379545921 238572047 312276517 437875861 161587137 464314859 206687500 581358940 151182465 66916608 413713764 560030000 77784577 704063836 168647487 425931841 968027520 383110752 622407861 153542821 116765050 750110172 308678197 596486999 754688600 20031782 877002115 430989119 494553750 468925057 241495520 952139989 976089120 11508698 464022841 397859377 981324260 474750488 676633473 787326041 231910975 608238241 9590721 497753960 748403465 486670793 937003596 873519440 832352401 429327889 469331048 488917792 619628690 177113201 766813408 936578049 585115546 291404736 538639161 380944001 58567147 753421709 472169670 582953424 992136360 547236078 502385922 980891801 736773111 92495379 141870269 896901998 227038720 826543640 663595400 68488101 444133825 847822900 837112020 709441977 967982480 806207843 307736834 708164560 123769451 984777600 331127041 841756160 38121088 597681626 345006050 102962125 634189400 699381245 359008005 780450411 392517009 934346288 290786000 468821813 49206940 791877521 957148040 143308949 366532500 875437825 267773081 475972630 817341868 224339200 302019353 339783041 231149281 420925601 467523215 503660113 694175241 329867801 793337232 428632471 54742636 558697471 723761136 136019260 755926201 733648463 207568428 229311060 761354000 678315537