939 902688344 975293788 362745395 586709568 785765824 989872218 756600138 833350497 867722046 873941435 868861139 978734068 375985671 652367462 786292205 902758207 879369612 925258382 381360987 900797014 90015467 587447114 372318369 424045488 503306989 860581337 629318270 874001605 811579679 991039726 605075266 616374181 532523025 698708239 254510949 406978142 766832210 961865844 56284093 569115242 802682478 905427909 462520386 818351950 514290410 704938101 708419818 735469020 976026242 990450824 939866132 983236319 927605880 981108544 250005317 782337257 448171629 744882265 482525276 688494662 127141734 748720122 538084046 741544469 240542279 884274338 762727187 808451775 581155898 596794620 914763994 980118917 576240521 731354444 408189934 632760304 262282630 546771068 535195378 553804634 518819252 715893819 744823551 992108152 550810157 975002455 401756456 604660911 549714965 789951722 481153755 968188297 710431429 813252479 218735440 490992414 355946684 541013697 293115924 771574165 910408737 985813622 432167643 917971462 611219753 900745414 784758019 986264453 734763218 865856742 405297334 880979789 960974039 976461870 126263494 580766020 507950440 855546590 194972871 607868067 510966848 592385067 462128317 975305108 56955843 98671994 53511742 973826992 232517930 271441891 763801527 856421834 927252712 954093942 215284547 355229017 276621817 905845573 605532149 667534073 27602459 67791280 286320865 793609889 24550498 33474504 64201394 825541438 284439723 964155903 853488500 961301588 846350078 858350057 952043950 952105519 925768465 972909130 60203214 229346906 730748851 745955574 75163123 930592497 561658962 856184792 458074027 789064811 932021089 983646550 195894657 498614516 590401148 998532160 833684413 876139293 379364894 892209135 844830934 875257239 211206456 845850111 226164774 582695507 979417471 987900299 775848774 836698022 504492172 773275594 991467745 995689090 454812773 556924680 473905227 750082653 28700035 195712950 110035512 660789086 185363075 729368705 270292655 935448428 676253728 751152237 314414913 706553070 788356838 945364205 354952738 841124626 798546413 921359626 985995077 996252603 48743302 423846928 272464128 827376407 516036437 683474943 848982097 887369244 76015409 458598301 289066547 428788994 345128580 483497030 625613637 736527523 43812649 942171849 600726542 641366991 909158774 962552586 930870234 996555250 597922000 646943041 781670094 932540809 722618413 767010463 446711139 883312385 72144352 247789051 459290362 837416995 516437587 593865329 732795043 992979211 362768461 378906174 138004526 601499588 831260567 899054399 107423095 379852765 721932119 763173353 74546545 792379113 227524916 589451999 994565245 999412677 679013236 892289598 173501245 904892654 555107693 833400730 624287521 717483553 922862940 954059248 648693119 694340966 266835503 883826533 329473750 927305334 894588538 936319036 743927044 960939411 572195887 593663254 266657469 663973127 952467028 981160184 436233931 834416472 859705865 945417069 84052502 223142875 268902224 900537355 594862017 663054454 40252078 315275008 586923265 885335965 460200882 930488257 694592310 997392825 206885911 366626947 863929421 904434968 463231193 577133507 786535057 893554341 769412616 838982917 225900149 591487710 723239818 978161471 170012386 177701484 227536333 613022201 333223854 845086592 271585251 904274400 403890854 470798608 30715386 317424612 599836256 667695123 581469702 861586351 274595828 628936130 207565294 399333200 858077095 932478750 29819053 790925069 137545396 984343338 783548939 899456022 19596858 272098335 533378885 774254964 351875486 663461371 151382687 528521199 460024593 865939384 158989471 550603720 68410905 377460326 311196005 712670202 726029237 976887238 179243351 318328956 271815914 883927600 935797930 998142835 633294557 747864593 681978753 945385165 920301149 964306319 734202100 801858904 329202891 831290989 989233001 996757844 239746663 493525231 841244862 985792607 11863500 599950723 415776980 933153938 911145020 923009002 675532078 980163713 224865736 395970138 967497494 976282003 813288846 837407951 625246096 840941159 971469840 973776027 173156966 951360698 42274143 136499141 758635385 893322645 545291630 799570596 380496800 525411679 74622499 599047885 421183076 475650217 523041452 574785351 560148973 986069765 760951879 893994119 920437255 955635133 15561240 810124644 537442863 626973807 551652981 848887493 596831606 758624690 623815211 665893236 426492853 682248112 674530749 839795134 142595187 799604571 461135110 894764419 13028617 968943712 86425594 930510333 394946465 574184877 181629893 255585255 909162868 978795691 761426834 977491572 556924212 994346916 564682573 997918946 951013448 964887842 881352694 970021325 181444967 653610958 249612606 718948473 479951375 799091995 759823003 914078451 293844276 380342699 826113506 933810112 951295234 964807858 507559383 871486028 771279889 942415762 906748148 958415737 611692568 831820098 334058000 802300016 258418376 748882643 909040978 942216413 56145929 167407367 127950909 762265604 776067349 950437865 450939306 519926590 573057689 581593797 905669592 973176644 570504478 661685659 134269940 584595930 766435964 988694271 892370921 897892847 716275193 960337839 448325246 557215896 391049354 888597919 800787543 805095916 239030372 531765117 273006298 746066103 632926142 797667720 714507896 830736754 739203736 843019138 501649050 580848629 452945792 497063333 681056546 956417035 307933187 552590706 597477557 820818327 871143437 933920983 331231110 882645009 57686983 595880766 276052132 323935047 118126991 690892164 236142269 462776819 15742704 471724375 339748888 855694789 861004081 957020675 201811422 948219874 630998307 721971288 187622756 195313898 602577403 626413310 457067937 549419556 100176579 992462496 348003709 595331150 629697854 969487248 402200150 477919857 448455806 568979707 91741347 295839239 786217390 905712961 359123387 432557667 638657456 952636486 737583278 861732243 392663681 494316567 204249485 306909323 914423392 935100794 299982185 916376193 815779877 829671020 565038355 603566378 25803677 194326816 223366059 746144472 408816521 431993060 249806151 387168748 302134630 954495857 137855115 156263105 332724065 515025185 658158492 939199170 176636967 290218057 430226132 797102901 892194126 925264657 782730917 907189151 450312199 568534285 788312925 897886536 468118098 901463800 293880419 595001384 447798596 843123250 573611494 834629006 66016595 234807332 595013847 644548041 278574433 753219747 984357117 999356935 899778557 970546676 598377402 654079303 381808319 784451721 11046645 824235995 159060699 792141615 919703304 923256798 67856798 228989694 512562915 731253930 516265350 887300412 598154967 758147978 823120665 967222071 745530093 803974519 189565396 336712863 521577430 578994849 31033758 842650138 246411516 324431263 610424625 976742442 593482253 801845883 238392396 701451063 772730299 854455494 366807686 863712321 688593649 739694396 135392604 473063432 755440867 976415271 699623875 893581148 360248262 758431930 573182518 644640855 169087079 938088310 782688369 794145607 725289353 893681238 202210460 960799880 369043919 533983824 834840665 934051012 113535489 986170987 380070325 992784617 337240456 415706405 285892899 872336924 992156179 996432534 390909990 699097808 492907574 912605162 129267544 551691096 166654275 374064298 445675895 920920992 534690197 703286760 752298953 869414170 514969746 522687200 495750846 529176097 821329551 870171537 632743636 777264040 170581239 320944348 154345928 716482711 114245874 642850134 188737966 605478552 71569143 870903847 947393219 969249387 372420418 596113844 206395629 911066280 816662957 818179953 491901781 930505197 306134877 683486183 336788973 890644213 737103612 764533590 704133610 729672441 69424428 124024783 822099689 829706460 638467362 661418218 385715229 945363607 664204648 836212550 461193383 746469575 696313486 803304976 289163758 933451401 289378436 836449714 784954499 897772553 513604673 915811981 463933573 732297468 443225505 501704883 307401915 745942953 845558779 949997336 575420193 771006745 203342218 384246362 12629435 521718754 508920253 587905477 697318898 874955911 726951082 752829199 477799434 729014455 658167868 693883827 326732607 550962688 715421204 907511930 35744620 884196621 515671010 817643779 973796761 994858619 651583210 840865450 255687778 302730164 902283400 982658170 634622969 659211965 300336238 458058850 774301311 806106042 240079334 277704074 110804667 625882265 13875146 67675640 723344245 867905095 264376217 409030088 572963788 736038816 696480549 807035384 367618745 730447732 622973950 839261905 176421736 977966209 679238912 892556787 895439733 923720178 720037461 723370328 767277787 962290644 799595881 971032585 268597765 592324907 390326865 733772380 160911834 569403628 173562445 726982009 937021003 938899019 828401009 950322759 478175185 890395318 603248741 937962489 946056517 968428734 220429474 507480914 245999592 947982299 676804499 730738775 853150540 910378753 376123617 376321299 537567767 826299838 565615773 842523722 352457341 862175706 676658143 712342420 444229554 653569179 106170948 974348100 332327062 844449077 129632797 999289705 555993476 622067104 590339293 649598380 704646256 924001546 867270259 954804740 630738263 716237125 730938499 900597864 555999647 852782644 753841783 867585128 670300366 787570113 993721151 994093226 313960439 561103138 745283210 864314553 454814499 703809440 845327021 902451603 256438292 502788410 895730990 967783961 823511360 938713293 807294389 959118185 487068133 817206183 101772220 819415513 708561440 834868087 139430740 900307793 946337318 974408167 515548664 546960553 376724596 832957841 988295071 990777988 300507966 982221315 732534842 783338375 107177000 962151508 939218877 998898481 100587493 805405669 890121445 976674374 884718911 918562171 339471389 394318523 125587956 432554851 613306521 851598703 204955326 854912762 677655706 819440288 197660535 812230244 957310135 985791590 549330334 603644860 352021457 489432694 654804668 778298000 970072704 974222914 383708236 387975772 142856428 178590049 680466599 690300477 322129096 585100106 954815726 960770932 102312441 430556356 678909204 983075778 797741251 885001255 298208050 484952192 207608022 911732141 18994527 985234768 838339146 841713822 130800628 173709954 748726366 797648698 233210513 921257102 51567855 585731955 656056471 996021137 182067580 523080333 959829389 971320752 226463803 243597885 916982629 945591322 427327041 894323402 777224056 838363378 606794233 997973764 496334398 800785651 644845451 907547848 528655103 823015233 291684334 489840758 606194246 897291055 465659172 494977445 344337892 726029837 912094615 991585525 344552609 372106837 812063183 906855587 474014389 532964356 228144280 700324730 57155462 741907052 351479239 820059428 128447675 921948262 236935710 444967049 308180196 948247888 188059558 919760782 498897885 541478648 974849064 990264282 649762020 874410429 590996337 871224845 873617109 974943075 884516376 985963117 436516126 695350737 749881805 870579716 532289799 797664316 633112003 661518796 987370659 988502376 277680739 662319630 633058355 778043972 115729950 718983486 47504470 477798053 139008812 425751604 601342919 984297920 134576611 927914999 647403912 711659912 48234247 91567900 682394551 702840753 886557022 989283530 324990969 583824675 633722548 996453835 64262678 498143813 801400696 802305065 628663212 776057116 247366937 258392273 863654145 925056121 860120229 958423804 866438766 896215945 946889134 984887581 88781217 826195141 137186293 522554928 378666380 702291202 471096739 578660213 682764444 692638450 764075562 764889761 483496151 838522616 19407891 973796715 211572764 425659696 878525635 952362077 68801233 173346217 801149882 949242725 443967429 825967232 708037552 937237376 541999735 572747834 287464932 594611372 681369034 937886705 237678499 710057229 902368650 909489725 757827000 800453701 94487242 766839241 260215770 460004097 863205761 977673337 321174224 367286438 171869148 717461898 505667620 702573352 141323137 352732409 790947953 853276900 887154563 918365672 530895459 904624926 444539656 555370521 615775583 632916290 767236543 918674867 458786986 776764839 807844179 890635394 217910552 745882132 981832145 995566102 299766214 718640891 393947570 450022459 534243128 726278647 29378274 705798900 16013523 213237785 995683395 999456239 576497225 801654875 931594723 975860151 922325640 952161331 881788618 969759910 974882003 995514925 552025909 645044384 374560973 561945616 204996623 903265807 485868017 641985632 377286105 654707997 602913664 927357418 943466011 946419764 144612462 919635577 855935021 859559176 381237375 896398691 693923511 944221423 446634174 591172879 918970776 981845286 594620571 647357562 393449573 662458913 494283762 559393833 418765753 554669082 321198242 379705784 698266090 804328593 564148249 902451636 421790533 880960870 250559947 561428675 728559937 942855181 51033919 215239629 401261641 852252244 495141070 619692210 936697189 961268701 319726166 550530245 459371101 680930998 722679179 857087107 765863030 990111428 237877323 886709634 625970880 753577360 496627685 942916488 442448089 613707705 518290885 624692843 95194915 971661718 299399577 358375714 379090964 674924537 110314709 512985173 90460697 96152400 147347002 483679889 888528048 973713239 893718786 998585777 210136235 710460749 116697889 823835451 286912165 359578962 539498119 727495943 261853801 982839899 572638842 635338760 229307049 978380661 308983170 384948631 217275909 859517756 151212595 225575007 193884786 539549543 10939423 404109109 478026996 643345823 465201916 584622574 83734468 425264883 337644266 739102939 526824900 851552540 441090632 981915266 203555684 845556738 966305485 991130170 658375390 731153963 832837922 905716629 762717660 912089822 313511000 638959473 69705952 268359633 828628028 894923092 650538585 906995822 915806727 932793371 289107173 647978316 595543184 769014981 613043182 687973437 330405944 597885727 837712101 934433322 290203677 333532884 62928659 162017334 703168385 834787893 39730720 252651612 298032928 453662930 948559620 954724250 127131644 700689996 473255431 637325403 199066308 612226292 252036576 450435960 38007303 377881006 650614288 991544964 904052356 937969276 421960052 939959278 875226122 925236967 781251571 899999396 421164337 706496709 366210936 465603716 822462980 850421218 591192928 987061550 289549352 915224753 802582316 981035291 171915535 383628552 376324813 836602907 358172442 649911087 489852263 633820730 509413122 880960651 810186354 872478636 197024222 284752285 966969499 994411991 818253553 943471403 925841638 988348285 440551388 464602847 394585502 702391892 86821836 362284369 814624122 831234728 80980913 881886335 887570548 990003740 929637968 993951929 413611161 877504911 459440080 547004645 717123299 882912837 691311171 698653115 393720125 771617905 458406047 992761804 997561501 997860103 755346565 878375534 84263329 939850233 329428987 767301959 923968045 985498016 25199929 841616488 122016889 686706377 596106028 609326223 209721566 472893636 454988670 784690966 965427895 991836641 870467988 892491545 371552968 957880547 91328580 344098119 775125371 944279694 190527837 440279884 725359730 793457868 433661768 540675913 894303439 902295751 117723935 403869868 457367467 483407835 764941998 794176622 991523148 992762931 595642520 648176065 915204670 992548895 208465848 379778424 121224564 630370740 626126607 967942640 238388946 908929865 296584167 580375723 716122856 961359124 192521596 469888405 611945497 806645616 715587961 913104698 980785799 987776756 587402436 615353232 399533733 412919639 975494096 993209141 33858948 358454403 810478183 919152361 65422753 562202467 270269437 967351515 577342682 717948833 296059448 701612661 913448954 917950274 482060664 533299678 504509386 672037417 388396510 835326237 573647740 633539980 787287860 977202639 251745655 736549022 962096139 962921580 544413656 606655647 197982518 537362626 490389471 840731417 664769452 859385454 870617755 966861724 672173065 931148452 291849773 365313041 64574568 915275308 499252127 877981798 292787198 311177543 540119336 946799286 197234957 321534588 467570383 732258120 774673231 792814054 706237892 964424617 248101556 870147743 474874451 721333042 684179752 771321427 100824042 280754413 205252381 714665443 741906881 759126076 824279945 921595974 873802901 957874380 503658204 691850679 474843594 555553298 190614976 436803014 315458124 386914575 912043575 980396878 83712210 861440899 610629589 769857282 691508414 936013563 772298915 890621299 815826226 934284743 425559448 741152056 22115611 473874163 813101977 987049990 184547733 563416318 366985301 746311917 471889158 546952063 881513270 915488724 493156638 795127862 198570672 236344573 312816804 560926817 77577395 477987257 951902961 969598812 427356854 438855022 846633459 946749086 551978133 634341467 778097645 782140535 342657403 900244042 516017604 626810015 592913459 617698205 265662581 520184813 529052833 975760920 886890831 922905770 394186763 857549518 75205423 350373544 89473475 783272168 174032504 470535772 786412900 898429433 84950356 172296147 35726940 775661972 322625094 584845008 96402428 389870567 697447010 971511556 895557696 967463275 304420355 722677749 512975996 826203918 525602016 695556003 102405293 267660324 146918369 721931829 53426702 801878298 861141670 924145081 491350794 571470965 308378811 662306065 472853602 722952301 435722172 961728747 868800290 944183000 339978204 852105476 192088313 358946796 383867829 733377947 330657117 574647059 146019961 873684397 126333481 747939414 347734712 797936853 849093266 995201228 453870281 926550585 906965030 971113217 154374117 836178055 169715308 256980980 474480442 504594137 633089994 845849325 799826165 869274802 737947777 805625453 807448226 877366291 475330140 954612897 281477190 409643256 415614776 459661496 846065588 878356352 716510069 817019463 662054723 956919032 400362765 570000001 152086776 198822531 516650502 576575710 617097253 842499929 457341527 512960526 499086093 799688023 302608708 941574343 176203917 532733826 313468637 490911744 225803368 545335916 873891863 938762406 496452239 576155978 587227933 643925450 35887698 277722028 527237935 570894219 421721261 468619671 93458717 556232787 349215941 496649864 332891628 891937527 885717494 896103176 37878533 900380928 870141197 949139429 823009772 983919435 10246672 339704218 49140314 326119962 85125489 932885647 873492474 943207408 994033121 998508237 599298972 841049942 994433512 994624603 511091600 881610476 626250819 630324006 84850224 432366836 177113183 618230490 558420591 571080621 206381570 356245606 882847415 938470847 530406581 709921671 745197975 857844074 197294673 425267353 391120501 672297940 395479098 968926624 455024033 518028863 744057031 944143658 333824265 897104144 373272236 863512925 698228233 973262497 519522112 952312827 378128673 394313398 978551728 980434440 497709832 937591871 10144962 646164886 993701980 999975803 990032619 995075411 625130899 893860790 634651067 690568832 17127412 299602300 436349230 637962549 79197608 727634475 890472383 999517680 485922622 575194487 397576409 745226951 806846132 890593574 11360423 857908711 631624162 657104170 701127066 827849686 68759992 845719514 995484618 999947956 479467643 764414403 671469611 917945693 349494355 502914701 644313319 784115072 900658879 989219721 14781259 920575406 919761399 952491528 12508337 784046715 872492084 878102523 280534888 321138043 251739980 398797270 677676557 794127157 553079916 906797196 495420937 739706783 46648499 916349463 366179200 573907460 765899736 768552540 760634753 761671382 648051258 862664488 909636257 961572263 83586231 319251279 166712196 826883522 512918053 863305331 217517229 575209394 698291024 922070653 227270397 521517209 816216228 897826757 15959981 329185546 246329218 903814943 179892252 962708952 989851333 998056634 150410173 438802529 436685813 617015271 378365421 717580232 903728170 959932515 367594891 911109322 995261012 995493615 974764592 994276255 392674437 539709383 263518275 598463007 87770132 256033892 925103818 936786043 403221744 784039692 941296005 973993656 227560113 840572753 273223714 900726041 310391898 498743133 852444562 881744612 51539914 545070965 599205182 886560653 897430809 969868832 238150532 652378614 543330814 694629539 386744209 823011871 615864399 923780570 869708805 994925915 422609284 669619419 268133496 879385219 845440581 927287748 648136638 925287478 524984393 951590615 953662559 981074244 877465530 977530846 112711338 527421679 174028784 900870131 608225637 849512253 205642718 611815325 445195108 532360268 836001472 917562293 170862720 178205467 614333914 694024060 785852985 832955951 860038540 961810307 528757574 575608982 347315842 373394201 89322359 278079113 185599081 445557095 693911824 984237914 276583677 329170706 201084275 395373624 785110171 885604794 551886789 594058947 525303872 673003657 371872242 645531943 811106971 873600635 117809751 978310669 856416195 982773436 451614522 955421559 14477330 600239901 525412015 737028190 245940711 447620606 956149528 965073708 78927277 874375576 851283584 882462242 282380347 381296715 635185235 812445669 728227356 928767617 353841436 801555583 403912201 753329642 448648135 469554894 817301390 912310753 282965806 570855476 861551949 898184418 124758478 946124602 747484035 872629267 31338578 398499373 182596644 856206732 283195043 680655368 503279489 745349880 216568514 903350562 346538267 422345107 838712624 890345219 670934216 755963487 200559801 602907039 114882045 121576142 179869265 310935717 901460280 972616574 181762465 460393729 376306136 944120183 513749339 853422959 772306171 890451535 858168938 929331987 608328987 935192482 752368406 920018492 386885087 514412898 93714114 131946031 355162859 961585097 802226668 952194673 707447537 949393576 118925471 428480507 853659791 929673188 149368221 783180410 396570624 821133739 956241152 968637455 798005506 812942033 889643312 911036792 75253865 276719140 427988325 657762982 405087463 406496008 822775671 951260607 221070160 888969493 928548648 980272338 277886079 790874332 154707471 579466970 489245230 619416383 119875272 735257410 415418778 472127838 181263005 386522945 585118851 642042398 131100921 911786005 630017253 813937580 354616853 488131263 909402889 971594918 743641911 824567670 297148071 673435475 212466569 921598739 709109643 838740814 980096844 999367475 522856299 654779674 309785800 670170104 233208825 559988552 350972801 619911148 641908778 837925105 54728575 858374798 683907091 826148160 167744933 432211791 810768675 833535751 191027395 443809534 477107454 616012895 15575330 360541657 457387455 776554246 312034403 560637320 642164620 761658034 131210563 473270293 804683388 968294614 850360737 971966230 376578922 993225142 992764366 996436157 944140256 996604805 656666759 943887216 343013500 481259211 103240473 613623390 752873264 957647674 461833335 744268832 119456898 487450797 874018953 997841930 266201115 413221478 530964338 875644250 334310529 568651284 439530498 497294880 817427531 881197719 298494599 912480554 284615613 880621746 747309239 887645424 77925653 699603532 757930313 824636180 520259162 853553884 78810649 474954873 266951040 866450920 448003384 796060432 749379918 774399375 936198320 994027647 662432804 949739837 358909103 892034669 365718277 433070658 931014580 945931479 742838192 771210131 710264005 803596111 858315761 930647444 905628783 997596836 613484100 944379657 494427957 656648199 545639372 629739347 89410571 744344422 692809213 956968403 503899658 781165814 954317060 979569644 103066005 725936953 378792612 652784481 656416783 827163543 987805256 988561492 180424734 828015030 435665715 629779491 376170462 483224276 419030752 847659524 241892637 937959972 739931208 906001845 73043561 902871666 228814805 496608264 658296848 911295394 541989177 999299029 516581879 883942869 438879003 950485163 485998760 619321525 595886895 603633392 691150340 850654542 807675579 818246512 763024954 986013302 864836379 883866429 381387012 415319707 748985068 927468906 674043714 714280000 362099990 995663277 630032074 914378695 455634972 754379470 616152145 826695491 838067862 895316728 290180697 905283871 915513989 973173580 517242272 655731794 861418671 908866813 279673663 480341460 15815031 581932235 96795727 162661556 755807264 960155837 900925424 975841854 141153236 661817875 508667246 868325124 915899267 944842635 887248966 990893651 628065371 766176440 354333529 974045372 409972545 792450223 491187535 689888024 376989071 498496436 280289748 486321962 437607083 912914987 149521918 351331032 100579658 876012107 905994022 921764602 522080779 562866848 275805006 302524511 392519146 660832799 65382622 592605611 106832445 739802465 872945861 958256413 713502255 755942691 709324841 932534325 226485037 882601670 280704703 672283177 391593239 601388048 192408177 769935346 506004850 601450214 668439643 680658661 609509929 813765264 902292906 973145368 78407891 754996826 169199524 897798901 176384160 658119916 980074454 985580620 773806225 904446933 195933942 535505439 409046635 644773594 382772396 904251543 776636352 976888867 756955478 767396931 562731337 741928967 274194852 356932546 252855026 316069466 999391458 999797445 233966528 863270908 517151845 679941825 425121553 662218561 749016594 785292313 489590888 952105116 983388519 999865262 365997044 791628012 618527017 964583865 786446747 962065625 76317894 166457310 335149154 512755485 30653219 609099197 274545175 450198218 295370596 505476999 90240026 764693425 24532162 557085955 245292897 284210202 410672600 469800232 684426087 841965308 570867941 809669202 992691963 996685251 531386365 643273405 110757861 306039247 968566117 979202006 448323578 775070294 944255576 989339626 808850166 893102898 986384995 995569675 993603404 999952875 85697810 279965911 989096743 994863442 768598620 946575828 660353342 847114382 128923206 603559207 79565102 619912197 498300348 923689644 488628361 773268249 822806124 906544545 179803523 738960388 167521130 668194996 426359886 650722858 563347611 858746489 521110697 883045901 622754132 790116237 988455968 994838979 728129989 832934808 706918826 764506432 133019548 153992367 595305830 709712655 395908273 942889790 904346477 958619149 186045334 825388654 156283404 229164605 865598076 951823686 545054674 866236737 782338631 924549763 328329257 903105600 356549688 845339051 136007271 780234570 546079187 665030682 63567357 868839472 557356038 794404702 254191510 826076942 338597320 497434575 767984850 976197133 428483793 432457553 430201991 488760630 37385588 918871112 840577795 915498720 792462469 933407112 420928398 452703083 450323857 721608595 661180161 805512002 492125036 643505144 980141665 999947739 476612265 701956209 336294581 380968604 408778143 676555569 458342311 663979507 273257796 694015928 374183791 727649428 481473079 722603093 427560203 836163867 330205403 513796146 463921810 869360100 970412482 986963400 838637426 986891855 876740141 940215023 460378506 843320524 553211064 766649097 329001574 539106875 28242083 976113816 609427036 809610095 818384202 987321001 770789234 878785430 687035209 704724828 413651496 519391352 776495189 818995783 696145562 829393448 784661278 827431522 723896900 787525791 41797845 216159725 237101464 919175746 168603170 416724444 51557012 645152508 244919966 514941065 16509062 500626372 626035297 663101025 662515534 921242713 331995824 479573288 502414201 696461066 153959060 850704144 232911636 996007724 49991865 229787389 595414238 988543214 44190120 544849556 632815559 773999311 861217508 872094368 344777335 370588040 966953249 993053027 482072720 705828139 690121977 765459449 575471214 978402319 288968464 365284749 822455980 862574483 386795690 990789776 530561376 669399360 38823109 282502619 615048236 846517639 465992693 918984608 80630764 427852343 770846259 978391475 750818928 923152883 642458613 683711486 133070598 976454228 34842052 758876829 203390053 617875645 928150015 965775431 868141694 891341110 24269886 423514636 14197353 764271657 27581771 594415525 874635219 957126172 616666357 683732386 722322746 836647566 279502874 470118519 19989837 728134629 964079426 972774410 540095802 813260009 267376312 477006990 811878828 933714430 59818473 616038091 502690902 960129709 828471223 983335642 263501306 506005618 276366947 728446297 746206905 855235810 551841100 827611570 106710718 661070424 369216228 678382521 85040760 276136682 506307058 587677340 256195368 334612215 161909596 230388687 870502831 954257982 944399753 952180942 145890004 338950117 716791986 937726938 877603542 954303553 586414504 891796518 373904435 846484199 450787841 856430736 825028831 895224272 278801364 683679932 493823218 829447941 702377847 824110500 374117736 844602549 725399911 958448270 483379533 600048998 20331605 857047189 528341197 871024318 443248371 487033359 773607544 967448119 937934933 945166261 375118443 619571500 294059473 688203818 160374023 991387218 474047851 709909845 304097170 478837946 864574213 995926000 522209066 666658012 304053181 409759852 64211265 540090708 207573172 494201550 34855873 805467748 853383501 974386486 547635035 626359057 476759828 573609882 68982993 173165886 408239473 477658103 723798274 918027836 991579434 996063929 267777682 815651071 103673079 657477108 485486534 889610765 331525062 709924939 754558037 966035617 488211713 782641967 321840888 569043736 876850035 884324914 64732522 568730884 648509148 724788024 144725960 970715201 961202675 997656298 108559714 631439968 49625960 67216589 210738884 518525222 747197710 989483163 14849222 377149668 469394013 830704893 79504951 933950682 204836179 900700250 505905145 887247253 392165118 798671707 69312125 538131729 79931189 926841146 955433708 995543734 52219860 265286982 370879776 860542261 550515176 631147830 709092271 842391461 611273371 628595830 258390803 993496024 627618649 823829937 555939363 569382590 141997888 182719782 393513933 615040139 455646770 465833695 834587981 937237901 499970021 824535760 275776208 878634421 672766551 937238212 351569763 540412763 703911505 736148629 55319851 479552753 944139753 948899506 722219457 805665307 152332221 664445447 951650343 989287038 825740646 925896171 779940173 956860491 157220889 418901840 175119259 598779704 221995651 383433259 478453773 679146456 520799563 587021243 847259346 851533148 920722354 923603525 291401088 327149595 886647673 947584531 244591303 941389492 525319272 952753091 73779040 293522973 601631507 879513229 316422506 558523490 784431447 805193878 106192732 641844412 182404334 396784334 848163919 964329416 257354119 292803011 122884669 442658527 332594615 400742278 420889235 840235946 753204259 970298510 86141690 615676117 967073289 996224861 562614396 666731297 755838929 805180321 419498274 950825922 921526464 988093834 289271122 409636817 201427907 771319138 904215773 904403895 433972979 571174089 241240679 326536917 513732010 852368164 516560650 819584968 314145954 693463973 721950773 986770743 674208950 801849074 581508742 697137919 808010793 908763492 984618544 990756514 827111957 959380660 177854195 898374255 274408639 965416926 825199997 912067112 678504976 846360506 175477249 382635590 107707319 626132744 917927566 974017287 78181430 327735872 45824499 72263276 450475198 859995204 110905018 313876673 835735687 961152471 202081174 788879528 678277093 918274993 245418983 372640044 168998933 970405540 582774366 876127696 376159057 597537607 314508353 815157182 671170696 973391841 600462180 670844252 206712719 419419805 375749187 810045329 445162211 960000762 937586358 958828647 320309338 888101068 763167742 887885803 356470759 569408994 56337751 498159716 859774856 923833678 371485877 613180284 686413657 935284674 348101404 979896133 722560725 784085711 166291551 281902120 173381301 173399522 498851260 822777379 581655736 669709406 864325424 953592068 74004319 931456587 964032158 989055654 132575446 948517742 307792358 877245565 340621209 683037993 145674635 810646358 86677798 311080668 382269334 779136616 607022113 688670571 890244528 919026696 92512486 116843501 50897075 151916531 873452157 897051203 585125959 799768564 91576654 193159090 813452664 852279498 644464299 851028239 74732096 941818215 79478326 549547034 79715319 272112640 927618915 975044360 879730429 967617324 560895949 624329043 415270645 758494454 65094699 309646240 575174915 998219765 888531006 929193833 50729400 916146019 40986536 59919187 58378832 526804766 891159229 999652817 296541761 392086100 932943381 951635395 495836341 939708295 729751613 873198317 337334692 554580522 827850490 848394209 121366419 709498118 825060997 973138692 524645668 540647183 997273733 998534163 999156474 999347562 153382352 265456604 889450650 917676913 143404822 516229467 704958989 777410044 676702762 764095982 617796457 958060303 743888625 942358008 788753115 872938822 708738405 737872774 861533747 941442067 14510124 27484303 739207347 819015858 715339078 990866029 989760065 997345533 661285249 768982216 352617909 701170217 47517174 392622662 904060484 964745956 34204006 62471290 395065280 500865780 724538734 843904180 446099403 909565003 68240106 225031280 65895547 756214611 315862919 447313712 400782482 494775194 511483065 749397047 772194602 802212554 884416449 931486276 109471135 760504383 562399565 569536851 283201607 408931351 338712048 461459244 782359485 989057429 388514367 927945900 933795389 963689267 339278067 470512192 796278509 807335877 74421572 841723074 231387712 733899646 713751247 800277656 827976924 988143671 840688112 847532837 52673839 470900683 865824240 911864507 216519232 553456119 217536113 761105669 966093759 972360664 928571702 935172442 161032839 442192892 879423434 997646037 401259985 591816874 430487048 828382022 415529166 848465239 310077372 630731079 529513390 903855984 968036272 979724344 602943537 751517604 340546364 946621020 163234566 168103370 991242709 992689812 190440514 357628804 768190537 856124725 125602640 273981656 359257475 932116665 609181513 965257776 415710160 682866526 678930883 914696069 934292514 988777493 243836243 545651690 962397657 980633376 972461030 974692501 992370065 997174504 725869862 968683821 920544596 938044798 877198003 927568608 855669066 886678614 476077661 745359203 294076539 963641711 683970516 913035840 916749554 993618217 117897535 983355247 681911476 863866324 128707279 541059207 618419041 661521575 43107496 566960141 245618083 332663394 506252764 571320420 264477569 944558966 132522609 833211015 898444624 912802092 18225379 375791720 538594279 554712235 298667543 841371381 637117698 929238776 517756100 522122432 617770109 788672556 281216658 398153549 241444028 683638245 243211699 906264318 464756045 532044026 987257331 987889553 94551321 167555491 532538663 907156219 220168609 251838890 132091297 814331715 930855825 997668822 100949974 361833853 951671434 956342060 116746880 379517657 14349313 213762976 389644161 645781849 31133645 666184769 594205522 793637821 987865981 996977714 389740114 996890891 78155789 207184774 431966737 592386113 445504804 931855451 845793641 850350503 225869503 251830571 818704201 833165336 198814401 877821292 626614991 884527280 303659175 578854665 340367597 489084769 389109275 577374434 181317338 330019329 686794465 983269802 797754444 998792533 663659981 727808115 113879815 273764124 340262013 874189893 440936449 641426676 578823751 682779985 702879285 787489085 729289426 906225407 625465688 783157560 521794161 891599853 564331440 724337446 338936469 982100079 896720897 969966375 127835363 371719591 651526779 872712120 749468128 839017855 341260845 528649872 654709943 996076956 679166288 801481119 104908934 634025386 738809411 979776645 706468912 834282482 455294598 721855666 363619789 719879512 455190936 748240550 172329712 423432307 637640964 862024481 727601643 928738577 937175658 941873726 304232862 340814666 550824493 932827508 533558695 742939188 352902773 430763068 957523734 975668699 695301797 753783110 131333112 564113277 305319621 600792746 799980395 980060750 748115948 802592869 310020577 979064079 940297765 949103848 617388039 991076449 755927041 829579495 768750874 832962211 906788388 979349998 133094564 563807761 189292607 763121364 317428794 368696396 418429219 625669844 959308800 989285281 966327826 976321079 824324586 975033955 743020856 786277603 293698934 601272447 412008102 677403307 938440453 971441449 727499343 952859311 842480432 900108562 52023449 968233197 100909542 522688136 344832694 958721125 124838718 337835192 711211706 758229098 724516239 933751954 284944656 313986238 37635053 480329367 441782363 466257836 787710431 895136831 584754918 585172094 792459156 929874876 485050074 869723595 478172770 505487866 255621925 946423123 659281122 879555774 886987675 901665441 698163135 729097151 656555468 714456904 941316630 964291249 957446331 990763288 934821879 995366697 705473060 736496859 696634442 719190699 173840730 667570155 974941926 991579697 69862440 237932811 280834222 704002690 385658193 640230823 910753961 951478994 634182112 780444568 312298589 962722641 574480137 663647610 844438231 924079413 197309444 967220100 352487164 954782332 923936922 932502560 985372462 992925429 939748307 981500517 975272296 989483890 738689236 761293986 556552567 640317510 282479571 804897385 735735071 771513430 702462952 930551323