14090 844039149 895052520 994548287 952263911 244990000 311316477 180740714 985859683 955323895 57794199 262991748 340166610 923428259 876313646 166361242 514712860 129425070 195085146 318864015 285389026 915271034 47495700 363588745 822953241 694965589 748704388 671455896 939546949 77773119 746421707 76542918 496123225 436696708 767906390 929584956 328093083 914122918 509527407 753846848 513555239 261847495 133316600 655203676 121757162 553879006 621131171 634177456 84078001 658162280 252524496 84809919 973357103 83891167 912104002 524447163 483545284 676510653 470127643 98239876 71821124 32047998 710231075 531989939 188249620 577012970 661949591 689752709 801001764 71974152 658702718 576360529 634716500 991516042 204562272 310129674 255372878 429525392 160889931 51524100 159594458 53250333 268620712 133949772 436584329 919996680 817376807 20333177 15803816 598657551 343356298 96748744 430905061 549315654 459076853 642900291 674798312 480818084 757257308 857765871 112334408 767896885 78948860 827406961 126093575 858581401 794311079 900181485 991785745 88652958 980564582 404534970 39979281 554894446 48408184 974873345 939645081 98914960 6935553 191800523 396406378 997536906 640081955 100311545 464429480 37331389 676772901 69264044 157881271 5423115 212503227 484651970 717870516 342426626 188202717 476676916 406528922 821266831 440104371 945217916 801064569 128432483 105673476 360588898 920989547 108202492 629680927 650905061 571652414 259138001 481454244 682417389 795016188 137376018 278259109 473471427 155168398 717513952 759543614 373285764 301840272 913372962 473184712 767820145 819802257 930553297 17732262 485815683 999868449 625081147 967755302 451633080 145554138 368387206 217678414 87640373 59465491 226947583 967178052 633702313 877163361 991611717 621761836 110225227 572072451 888804089 643730323 699242219 612267704 417733701 340338712 421815739 575717243 12864784 431645790 601603184 874929732 666147975 958760547 824803001 477625138 874283640 95107885 928777863 321479750 963710361 169335193 975583592 85486547 214044791 362353438 405971140 624023227 957642872 321822583 499782858 17524367 497419326 848766371 484879177 805206973 270779384 393439029 983523012 767646751 662947519 180834344 179852075 36986743 94721428 900667953 767839095 885217805 878972841 232765474 68331851 845110052 133293019 531219532 182293141 331695943 137473632 617530269 152788846 627677771 178420011 108525471 501515536 339742653 530211861 111414823 378616709 588766887 223768254 905419668 726014520 687942277 618914615 365726201 859024139 167322929 526725237 663135723 363633480 73784988 2074407 189105521 397721821 417430047 596751824 771542242 953840719 574761308 38627421 8162329 303636396 176899081 741486966 882300370 331180120 339410402 847227811 11349252 437469008 401142466 77373615 924642997 209868862 839575584 437219999 554382613 712333211 205572899 344042614 427721854 524321952 554008338 591770470 546331125 177006506 786376212 422227733 791186388 356115579 749412124 998346396 70215336 406036941 773726022 212866722 174743229 560934272 593764652 34581006 95662503 265144660 491725148 819972792 938678830 563562560 967495107 297242322 980599773 803514503 926516685 747493881 90794661 868579346 634275188 679109711 524977935 225816986 494155377 801615052 602158236 856601776 660754161 222162786 466875115 164599278 487622060 120166847 580818836 210660341 261099183 506175778 521685562 71856910 730637615 935099928 518681115 315906051 812288214 44549166 117651497 932336436 806683531 807912498 753369863 598331058 91466006 920375984 748878410 568364507 861507293 54850084 476367212 528302060 539558515 452432548 594262696 194421289 675201704 599318801 514302065 120128252 82446734 931933843 640494990 843729556 908980778 957624050 181248338 495354123 3115324 852393621 835981323 952198025 912648073 888013359 397241218 211551977 362864800 787359793 846875951 621651793 748059586 561298504 732541125 694783705 504215950 483154932 189567743 234489305 837012551 974223674 282270362 237634279 932505993 201758116 686997598 895220834 25393599 245716569 997380931 642429273 226986217 101969242 967820378 248462594 504895667 144910901 681802310 754085507 163008340 605110231 390978414 785743863 374955753 642413538 51110313 450032352 506012812 330880380 231187797 576567799 78332907 583031893 310456282 452462619 853579417 143344520 797022992 281305125 198355631 562865723 208501314 186965263 679784195 775394854 75969208 390678727 451587365 909484296 331579079 762322713 93196174 806824364 512617015 497710515 135063564 574681066 495454186 474120287 655116224 914964758 117720828 363626707 861612963 467535173 91004121 688110258 133590093 639599773 730015357 582963623 56441184 293229472 505577476 90597302 229835648 755618158 701263857 784184347 800845881 975997181 319047586 476652089 441157017 300434575 196059056 880015565 621275456 369124375 680351368 610852508 917498872 317618744 379614694 239611336 6548422 5692650 391591588 933787802 188832285 609543205 98592985 69059703 559521081 749817594 65473940 638250396 740646020 622861422 5314724 615419357 677771413 598619084 64683585 853766731 460077198 233110306 267842320 538603028 673353869 38030348 309671501 394019967 546584837 499910128 419645826 151655800 49406552 507424609 873068524 854958533 525453362 478158502 129826306 655102871 926820865 734876212 13160099 540940150 993260235 209285828 571434050 214899745 413630515 249011614 930195838 77029807 518971803 521503549 265087461 442182891 859439034 182913020 960482345 482857343 930468876 938506398 371705441 432593829 239243395 673731352 818556014 257542010 542225028 803002449 440610738 382321021 329993002 615659081 624512071 263690043 466997073 581243268 245944654 487546203 741895442 854750885 38554539 474307606 571492991 511793983 637314433 780047225 109864960 752707943 673517919 286721310 482565213 593964961 498497940 233693484 720531009 616740569 112870171 458504140 44474678 735758972 80431767 588224379 964773425 912038949 266448172 578487774 224673914 385349057 257616622 557620559 673460834 471435025 800195726 569097659 524976397 51649709 983483444 939893157 658898052 203633355 399235238 134654527 545535439 743149408 216505253 903078666 449158335 101465763 314259201 528291454 386071909 28911347 892088101 354965270 612062675 546024920 867979637 926382250 502772271 592392096 42153623 382647437 651176336 622419197 134054409 82700305 318695687 58406834 760753142 767925216 427476416 784739214 419170857 113949619 666607921 859627127 870603765 578827501 276333920 594386988 41000490 84287013 725125707 837185937 800111671 222581088 960238888 729608986 953193352 894212701 514868416 137317804 644455537 237180793 241762240 311430234 880941642 675169489 518872575 704817044 332008899 161195349 699179984 227038474 950000611 396465138 843352566 912775209 602146815 336964421 759014095 822798594 212056612 289655484 638857354 746990904 307646598 124595594 559572124 765148358 122241955 422190749 926717508 731146306 344305556 40417623 357338628 489349384 850651537 122575854 361106154 965733611 986824955 83900390 118974454 453402668 691411713 577901336 713711924 15285113 845486908 303644098 487169376 875969217 538425209 177820611 528684349 709335099 150776426 888039009 735695372 347457559 998480900 7242176 71438923 838107282 486548251 500427828 689368588 341052167 900552213 999178609 686390625 895773312 335345416 461522928 673907290 991135976 550656703 921100072 779017782 505836666 926721713 803359461 634634892 590408434 126731018 58107965 454628534 426040858 870342946 841338169 622577404 207800467 234487011 795324511 478655918 537132337 564121656 341353380 655135141 415623169 841137026 332263362 929158234 468223439 937285229 233016184 956296552 804695805 732685255 680593335 286448415 479008886 457190077 430646624 359492751 573091243 294946578 773501470 543214159 265575767 617963507 499805715 541904260 188611865 544056977 298121038 492173541 247433998 900111535 3585331 100151895 346933651 577189038 452330012 741913920 493733831 729326474 412154371 565449623 741733257 693228755 563282396 92990024 466806744 804824845 554342746 234827820 357992985 345597971 168434341 983522121 314747595 219382973 840973073 999712433 896058614 401455122 544271340 979617083 352238222 814536165 48384778 354918440 280036943 807590402 504708379 730659239 950177581 752225265 7295831 603717671 299299957 44328411 892880280 506258592 349805771 132659903 365485761 701238267 587563662 394091663 468975982 551193952 335006298 782048242 290367370 865776461 781576885 705315074 686136988 338479589 832508353 572547926 904222768 641067269 922838943 352640947 890029350 734428074 431759618 626404420 849965961 412641653 279349004 805429892 688898517 180277723 715256798 425048618 461487364 234671181 813616139 219176626 688881870 42398968 489707499 780591603 923157832 501450397 990914769 501214037 580966888 783393346 984041982 72770400 584077102 170946119 556737697 583070270 254984815 642679716 478541207 12853949 779202276 531181229 534184741 84291089 473489855 507958182 273875034 837982988 845525679 768058893 678858535 628159839 563021637 379587450 601262010 701349066 357319460 765873540 893947278 656404666 471487429 820299474 139471906 493422639 380390463 565097504 524556255 970931249 501428849 646697913 831261680 53367174 5821270 122609112 929671529 207024441 254752429 292348115 169135124 354426767 211242575 851350004 883907812 925747249 483281574 895014153 999573779 484075176 179628459 496043262 456446129 349253845 448687679 559123796 478683082 463735885 305791066 740653794 63682109 536081144 534832490 435324327 533635796 388626530 476254204 747101138 71420593 968100456 877390392 960462443 597429123 648670999 890464663 848523592 902705297 796193851 789311686 982440315 400453342 27015113 891512125 737857766 519737736 140539016 398106811 739348759 89624830 505363443 272827150 652501081 172133323 566327215 423568576 622656958 637651883 653507033 772803430 573662694 73563975 95394597 761758577 997664885 927250301 786940951 908149561 774492478 647424242 877327778 484097653 604115866 89976891 714069452 934172519 938576787 540267395 430441134 412809193 955353449 755296376 961968569 923472740 959282838 306496082 232954220 265272732 2778284 520945364 168423280 808712636 461722317 144740871 477429343 582319404 118443257 680680589 89054681 451838672 899035832 809662066 624946093 790898932 500867532 128382238 691297378 420904510 336032223 131770840 159949652 560776507 849205755 870619866 219554069 115862361 403796278 675658930 3497994 46788112 668741203 230422443 796942686 679710355 451615692 240360568 496534182 944369863 49964829 47634241 220461723 740619521 190438576 430717024 579344667 895115648 372759069 198930018 206573720 384998154 772592749 143703149 615648493 703471862 296395555 835479682 691639695 33037138 899305588 794486806 584945648 370822820 614522252 847234481 810638890 53445088 667538366 289795436 338608730 541834940 13184155 791064618 341866346 422386698 290280026 890909243 506631922 198727394 479405079 503475876 726705441 316269784 707836286 350018501 193172677 386938327 572977706 895757423 548479203 550449487 401704197 982961830 714021315 302183030 423355387 327086787 523083466 856959437 394601965 990730974 359727989 405100515 453551399 943925571 811121420 857911234 959730121 936486530 938321935 989062079 810569425 221082978 243615395 168741332 763391757 575998650 465056943 150129954 969170323 58164489 786127347 438574225 572826061 207196976 85973814 294892506 90016043 944939254 637703019 150167542 151255002 663117971 816045103 918455702 844917165 920967549 567010671 659689950 152171355 934793643 949036296 108339858 734513134 611266528 273520905 868779745 155830032 165178375 273469652 317458634 625859119 718671838 669609712 361577461 464485191 828851038 195208122 720218261 562842402 868268060 96977164 924237564 896899272 86635500 479088624 244370987 195152594 93258990 296519887 178409131 138918356 132168609 106279084 247890515 253000342 487927179 672298248 968934972 39777728 136822666 850004675 871285147 538715605 930518336 31758430 81036732 13390016 439637559 757366365 392494135 722074894 413609839 93698759 788935512 183795012 612844050 75274757 773227138 274338883 212601982 832450833 694356943 279637309 558996508 707802585 243235791 766466377 800205022 786276680 628644251 908113999 466341314 281137992 492342258 895081931 779414104 411320069 94316260 616020120 292554665 472975876 841951401 765468186 888133030 575369635 440653265 684755269 435801947 334049193 194509427 691271276 523505356 350934238 727118247 628132298 59633610 982183446 311271500 84871614 310918851 764801023 447224290 852732555 802960463 631682987 350824745 870614792 712456064 809119350 937020126 713776019 840234149 273938892 886739379 967539208 632511901 327150141 726148188 170396698 802468546 579520911 948184404 672016407 417653954 344099105 849741976 152612244 951965405 349786091 69797040 913728564 583101520 956132204 985134698 435711336 157116524 677937000 768504704 865105196 97340761 705378264 403736028 649100026 665345124 810963425 720534202 490946424 502753133 935766994 364816436 469669855 92372402 256160794 57093575 117179434 961825689 647474665 939015667 670076984 926503912 983184013 234557736 647675656 485420112 802384685 583815983 240856931 258934124 184708522 206570547 997579045 989267653 187893439 475792279 623775458 984843849 853168824 654554332 888461876 786046941 334556589 883453297 932338736 682861610 658768461 993615135 809720508 666143220 86595404 121005855 459970688 822479823 744707366 316937858 639679506 862839035 581666270 708182250 644725495 973977367 903746855 724007913 570748415 371250389 273826563 21083605 331376975 978253016 1066262 843874152 871042226 637700942 975993665 92529013 12831137 544508263 286282345 253996178 513761168 901814717 712926982 761311723 996161908 61307250 792446560 233196771 564700739 612532521 195835176 323241343 44932184 111218402 251927675 504069622 131310485 680878156 50845119 310247641 676443554 508283902 226842044 404193954 434978794 266792811 618901223 31821670 583861579 869004215 525563179 286568767 438815496 434119385 497747981 560563688 52374415 775819672 687814055 624322703 641532350 676339244 676887766 505713966 817439597 424734698 474184792 190626056 706056988 556815554 847952937 764551181 965720579 486302512 595341168 743470768 567612019 549751863 71771668 644712508 63727518 505118277 509864194 832663863 298512230 713267419 493345368 558282120 66684801 118020711 679374560 294718388 171136344 268312989 73297258 941009008 944950622 275636368 719268535 322851990 239936032 996515444 127667189 712658647 69317660 261302322 189480491 317391800 389729294 769247484 98215043 648518987 819240868 957954528 810809171 869640833 707991746 694033301 147126820 636838319 34955550 141227640 587085315 136388047 75143737 843780412 870256474 928047608 228973424 260037684 337279372 713148733 577256949 432167123 913557983 247953732 259487949 559340774 701022788 458311643 641274646 252737225 542897931 170312896 296333671 794563508 767122280 168320812 361330159 105572599 340961397 553601319 878665541 901585236 27965667 960863007 262659766 250066997 304851633 542214421 322524090 920141094 817101528 444845887 189647000 525784691 633968026 273003609 732535700 354866851 737384313 846740531 988965097 883820164 35867936 888193173 27856975 796969766 310617450 27508522 149412376 261463990 858137917 724298776 881559211 52084005 681684342 702550582 876132641 563261426 962527933 198362475 129458640 109857141 977324349 162687353 183452603 411573674 624267169 272302630 166531665 477030173 283728461 717141903 206691471 104968133 170151574 123885677 870912478 470856365 500500076 60465084 720466383 610293291 584297438 491868238 929984920 778669883 155877886 68920067 258902951 986670500 501320434 465701509 761897015 468753395 670205006 766071168 718115954 418151075 757752199 375491248 499531547 668612119 551688582 795865507 795305700 777152283 39243612 429804591 915028717 628111315 814458967 889262882 517127329 785239950 224229213 765381644 411713014 982092517 257159995 54682495 541965506 348966247 563703447 752060592 457620528 718984373 136560957 464210158 903924429 132012298 170548862 768246937 812122815 48873201 896387086 98299218 483090761 699207363 349535042 423733961 935715363 513376772 853401562 447361026 382039735 651984835 440778811 71247067 442134355 659723427 79470826 986761334 10884326 43754437 185387459 531740360 56202656 206655708 704455781 457110334 474836370 720437752 984402734 385206261 975849757 305363620 649293720 587666856 989430933 465269368 984084221 932786302 140409887 264380398 140466002 911105585 617011113 406500996 972026398 245316654 227627239 563316023 545786773 373878509 512329515 939886006 120453923 381025536 885341929 172930107 179883170 876284253 980438995 188037286 343255541 743013201 591069736 59777390 645333962 72620714 960675238 549306679 464489594 83126712 808389608 626180333 643265196 175220409 418808992 978313639 385706448 396603219 495424720 172698038 275223281 814332176 967650446 572879178 565546730 880114048 454288036 973307799 398419859 603337135 71388693 131558686 296455150 67942674 744368067 440910768 702270827 549780596 114183511 454212599 285080309 349710082 881084591 866707631 715518551 188312844 567765384 879158890 584688409 325755123 377696396 170438433 748690707 989362521 436372963 542788469 882533338 254155519 477675474 199943471 680346106 113082422 87204217 776340966 175750124 945599631 758836688 948315483 219478523 293268733 398558853 591024881 684870985 288442773 262026180 153003117 992191778 60320690 788723473 896169297 58771689 951237007 955122766 476688919 376121065 222551003 41362524 176427907 348193256 861142398 693353924 410674207 24244818 146739155 539857216 142741688 360032540 426606829 445060582 387465947 802338116 878544261 405839512 228148239 404819881 50986554 202950164 722290719 780836053 880104017 844443055 755297424 20684300 439172748 405537644 493632019 971070853 104682521 463684000 543667386 263457805 748790618 597375944 382342969 453350970 699055750 25572175 19216579 72116417 137718860 726491332 286276945 183062088 281435970 340086101 798020319 780797340 775540213 709154511 146042152 236882694 961310093 82053034 332077023 564270069 91369929 324244325 317395069 781303987 788795295 290738291 372212395 309771556 200356551 716557157 429305037 482658811 682781106 589956884 316299119 435426204 124925449 345739881 412082913 809273854 115531801 788404370 417263436 679254353 164747573 991224177 39806901 956638197 240546271 939355318 871881243 513009267 182910638 398441549 142402866 983017110 585248323 33864826 941558918 476793992 82425118 502477161 418270831 351846471 368757970 93582635 689736366 571456239 390363116 890839404 844267929 657199780 4876048 390448794 543084882 693844505 411173492 910474756 945839846 568384057 427160620 105220946 449566635 829462302 915023465 92369066 574937207 713683034 455851863 758828504 782839927 523935367 628595268 317413669 435901657 857779082 104230413 645249162 477190586 896802357 829788254 114923112 662854433 252037930 233435892 692601610 389833837 780567353 510928086 752298444 29701194 111548639 466780765 235181853 307142616 664256136 603848455 991110798 632200142 419562778 56068080 640507912 691536292 855073812 362895026 783641571 314442389 681445734 120972006 866452747 56891759 543566779 857912041 59589292 209618052 105659771 223766807 447680223 743362709 834569936 839315347 207717270 251199377 955697649 682150110 619023274 139925101 959472677 962394653 393992238 983519577 864071881 730659670 942964677 404077364 103673515 153082316 694425380 565538777 347147666 262010723 527900255 422145495 830777068 376395536 272602716 546507780 977475489 586131349 552085381 380503091 669304268 594890678 375336557 183567529 866419981 852382447 632550651 929430771 28662203 184044128 651829478 688805347 137614685 879811876 216560145 872381704 445589487 551095889 326675602 691552311 876563026 222051774 953936036 128227604 368222015 746345786 847869931 439353339 631080204 764758487 955515415 935805766 316765841 466444445 588760744 246653873 135239910 282188165 822969850 395025188 266070773 795193578 654321139 186024661 733473746 736129660 3274035 891506558 445956441 53449899 7676870 950361941 468595223 3691557 400698451 321519700 612574167 646408862 581865343 497327542 419206506 861634681 559187402 16512158 816182853 143363168 746990003 719015524 689208811 322112719 663761179 519719118 301613850 522096724 653182574 28649304 418573322 499828601 876211790 419164032 592830903 104215812 574339139 146445080 321705237 703693294 32455761 416075459 403180400 291868425 339317197 569036332 670044287 669200446 368724717 211150813 173235000 271982419 590821042 598712166 60137109 955599904 98233200 239363252 455219025 300135020 939033397 241770916 413450080 381425016 36344928 422090674 804056227 268696005 680239170 975833163 332643661 106953844 639727179 466891746 220977232 131305091 284128116 664211531 233322309 98759318 469230892 276031337 238074628 902038844 964655260 636487600 111360279 542055189 892246712 514887276 115171246 316929632 625597023 215877946 680044634 674817022 440910652 794619131 927678329 984248749 210808593 398873712 994153528 567891457 905096280 322341904 960172492 553634329 723714095 195889705 519627257 180907202 113408591 498428272 716055793 975543068 409071740 973398188 680033260 484872836 632110474 496961828 535361630 708693536 296134769 604840258 341746353 178530201 911548797 134090305 376985541 296799898 976297895 194694425 546532674 228536909 49805904 498088021 365613772 415243532 674217484 761948937 395389488 47371791 965064216 893419183 194221806 541120085 930863035 459718766 62952081 631627372 326457244 824858335 822099066 476836577 238820716 79117416 272324751 938501788 301692519 282777285 990071318 278826848 126570562 387463127 196486577 576914277 617145558 657686603 932018089 409971471 25822358 1877804 146425170 700883926 499171373 77453638 497835807 319259586 131054362 107839798 31213643 576427622 618022485 374367224 780671660 422958263 969352535 11528911 27126033 293283203 704802045 624730669 446275618 943078604 448934291 857354862 882127448 827302723 269351001 836101777 874277373 563807095 800405126 557304764 498477287 500354673 299071402 862673919 316427763 338105926 892452710 890072890 176662554 480136682 188640697 945095458 55342798 609845943 906665663 349829021 748022322 490431023 775263604 132344110 208146071 121209071 892679677 86453823 874619346 552171761 641123421 416540270 510785991 877528149 628390424 383680709 483456231 58430309 943147809 412033126 792248319 293643833 940422986 8578580 599875154 246336706 867233276 973568080 664876405 778263628 551623995 878377861 397529727 81888304 273298690 668154984 352405842 372745313 924757566 626626178 950408920 719419104 790997679 380361783 698984025 568237429 14632610 841183655 893141544 786325845 876570865 372894505 590091514 509007338 162045801 409275512 719700368 914160684 404720392 810066361 490684576 24051674 434423329 504228972 505883596 563475752 387751120 421753539 67020551 240469137 725517374 529515903 908044645 484435373 429311 754025993 122354284 39536657 944376226 136575736 541655441 74349336 801818045 622829096 163704837 806936323 4010984 949324247 884492743 934034802 972177293 383216353 628454398 805462604 483504917 146807206 169057221 974545726 66633633 105679853 194181505 105692876 522106965 149430946 821422204 556309696 293422301 752693749 179303697 142630194 204935571 84412869 382784605 526329892 778849546 13000501 792118038 245211279 475602320 416950507 584454468 477115594 224273875 814438327 785124638 805462268 408860114 265635280 151926557 371426648 587489221 883580943 434770393 864982448 149139592 836428318 165166334 124877543 506293070 59608956 336718635 529557221 698026867 414563217 945002888 135114304 744838446 474165230 357440420 566258861 375204855 632520841 559885107 4959217 341004955 925082538 686090344 106843218 824996734 784906066 149959937 291404478 816564920 295390319 879303017 191450543 94268316 736965894 864268247 821990165 151336291 942091658 929521457 82187036 843647303 519264991 245782343 181964448 613208903 982145833 352583638 341055208 61906872 235932228 443084435 921172260 853495286 858177203 149352950 561227802 184726353 400021355 258303839 337086554 420125045 856539880 709788283 239528318 201408623 102722622 762225801 495279062 809625930 802288849 828787652 263365191 364943896 935859628 117550785 393514054 5980176 46051396 852352876 376222135 309095922 27844168 128823754 387443428 172410285 287881664 180640094 51490633 871538307 767688014 436213059 550785916 905126814 519658206 914901132 963184125 700449311 312959378 635650388 972652377 577100517 502068310 924382451 246538391 409461425 103353602 814594887 827702053 309904076 569933076 253290229 867388625 600878107 917822919 391923591 154191167 259060360 612806870 70621401 659582659 978782788 458854898 909262465 389712419 100278896 246477179 106307878 290295452 335015814 860977798 95125111 599594376 876660195 47046038 739348251 570078341 214589317 9821363 476794860 783165311 234234632 559352813 841777504 188017817 797727749 854551987 392076431 246015054 782940541 948269343 239933981 640754923 968786534 404047731 856093098 12597861 419107793 273448158 512091892 186546907 99642459 980103260 681435124 485566358 50558584 509921182 285871259 272947674 984939470 33462174 272522007 438741541 316576490 586495938 169151801 864962920 797799994 426271844 240711943 807678678 811105923 176523134 428031305 310860283 643569508 188598166 556300644 161709620 398747162 760302137 683511802 475680049 407703085 96356482 694238150 175806692 842824108 986174160 307127394 741631021 297878277 321750313 922977218 72506768 858518752 886855999 755845491 205192598 595000290 45791168 822875346 133942811 356171010 781955588 88707777 630809212 907642615 804759838 774326922 286762743 460864316 297318696 489038794 171813163 490122484 635409552 658132478 668507991 54475242 370302326 614862350 463567500 130714903 607634764 93045398 357482770 447526432 314845010 314527744 395094097 387652306 215092786 797347240 947137173 843082563 167155116 435676770 673744092 406140274 399519987 143664973 653806430 346884601 284991418 413536701 230201150 632919774 28043853 255799641 356443945 247704159 198852579 502988682 584396830 8599217 183243235 361217455 608606876 909265981 991568271 146833697 942915976 192641287 57264197 57464631 550147237 259979264 676688846 132635037 637206341 866473837 997315113 689337736 391538265 171396967 86745841 6344609 959072003 937016301 73738138 496690986 390197943 815890990 536245989 813852960 477108246 394472093 908513755 329728926 527923404 865217380 325703521 882298344 232546387 802342958 381222304 60132875 88866374 732588630 972969865 547145585 106198455 457037142 601246787 37663393 177161090 122256219 70431690 761909358 460424538 871115434 280192419 358146643 321877903 730604327 330204319 327510822 392210479 127512086 862438294 667953527 943890797 794874834 162257437 987903932 628871857 522662358 985807611 445285191 21093797 965748552 309611020 523460106 922548573 515868161 902957080 913907549 836588003 911589855 108757867 77157020 476537093 214810486 203983703 811071934 855294228 933588438 859397740 98086297 286378618 230704342 496731806 469371862 242810924 918963912 286144642 159016090 578582965 790533665 733752485 53051803 206098311 660906824 23682376 350168564 947423598 67936011 862713128 227786746 565231525 261831268 63614094 997233214 773048725 259863445 793076724 278788254 52138072 867444108 442446930 735816276 993087867 568746198 796628463 637603663 698423908 313160616 548636641 900067814 864727452 168805683 605196972 398711007 241459794 641641280 644854698 286511191 185465872 882592384 247556566 478042473 566869442 418963056 928444417 246586454 613879505 101654259 844610388 431668791 774547897 662073401 545783377 456180839 978806081 781455444 787667086 516554602 736245579 172931752 370619435 381566135 720997501 635906736 853715917 969767534 90837632 972233326 471542558 240081310 29137805 115336064 812755891 205175862 543317207 385828587 21799511 855760842 351344544 225648048 746560390 695306672 981656528 338912046 814379217 648527880 292104494 464582538 609108540 538741763 789241558 963354250 162970337 911704051 692847379 811917205 156522443 90458111 218284394 226326886 515817130 23261098 945785549 882575358 499957623 54910433 840116619 74006372 95024418 335632353 421030981 704725589 112057508 83002957 716037064 929730892 761636407 374683290 331437880 365836246 407158470 335277374 601352089 222620123 776624012 77715101 11303216 523373164 789411057 586600528 733728192 550850863 958039940 888015444 79356374 550707258 690335519 983747906 805378492 552903759 617734465 515337185 391501449 401742602 227836055 652112805 979930274 694439326 8865728 113346327 761700687 182380745 846074838 104352364 848466115 906934363 906645233 61057924 458544370 301890040 693253313 812570911 515374554 470522716 78476356 358376048 738867902 975347269 228894196 489482367 320144001 368680624 208568170 168912697 10950417 108710378 183341125 582240906 8135017 3840886 805912149 774547469 804663645 297197054 737801068 763144757 269226784 11876004 950581330 580765805 974106153 249915020 717508878 646440162 967278328 553779538 355246561 761072183 899510599 944826909 612459450 79064567 460210476 880494247 426523084 80178754 72400335 396641774 279048140 220868780 463727114 151704847 537596161 461528003 434400379 583428752 831455834 571195544 429274336 11356922 389374695 343460587 958709242 451206442 134505427 156027194 992615659 742125226 498416335 89704711 514654862 119886145 591779889 394614556 823104343 739028769 597157173 537665379 641728260 880318045 64981587 998621650 488179856 652817573 322998449 530441846 554082418 557048978 889018018 48958716 246226970 78047996 218683065 151310192 625402441 324703592 176284735 755686893 827193611 876714650 14224075 894202040 63946749 525255315 858280841 555703038 817687751 24512069 889750514 706474156 213016747 352173149 553519708 749202516 565048564 132291537 842494775 607440520 641315338 412188352 78613451 102288501 637754565 103757511 806345676 855373466 567427029 985862611 467708448 707369901 656589619 555838463 763624957 594550226 570294152 287753260 517163877 658738784 831483518 180841636 816622394 317118402 166536133 661710870 123950189 337693937 990177805 41289779 678501479 705790229 285131228 806527886 853305390 199304723 323466542 194074217 267908076 815460709 371997952 797631143 318744160 652098794 287200492 42188360 294631778 345476035 44489056 657210101 880807387 984579742 320577936 864611037 810697602 945585538 366100027 774334486 42082835 687792202 946041470 460530436 194175091 123281883 55732821 631131193 425113818 956004236 676432050 791991621 579025236 75979524 231860947 230249306 803109504 111933030 189510959 825166619 975069994 68182985 593017645 178425823 968717424 639576269 124165161 462343090 652693097 814692629 772557458 988719258 761083415 326261583 857916654 223826711 940767235 651517252 173295275 374687110 485450970 208929572 313659939 476639571 273036601 287269299 589918276 630197094 819558919 483542803 219337780 766258882 50406452 136730766 955903385 652333020 590548998 299439087 310538662 212351234 468818018 435489133 177153111 613008382 792409090 122908421 78237473 856508887 562201418 406596871 504753637 826551270 44862248 206033031 763654634 64508770 991914301 555003978 185177634 322778170 670900416 757665442 200773160 2863381 628025089 641279393 627906494 847973321 842184464 893520674 826258759 496472581 259959425 477896917 592824429 319018722 743981003 829687249 92808726 225723347 396349832 966522515 346748844 850950794 173056431 646817806 400717597 64682325 212932624 724125188 431024325 856125705 318115676 101953463 967543227 803086164 404496614 7221957 741257538 44163134 845358512 851043525 918367936 20201099 472233820 304257195 548725273 525381003 611056049 664536443 388834131 478864330 718932571 498675750 539189148 407078774 963203575 807932855 774685410 266521032 809619238 100276132 411073562 548718369 501436073 769241120 84020735 713293613 165827413 293504548 821029557 119202972 809059583 645263243 494525812 797038297 239482226 422018345 441394045 936199983 517642601 388767623 174979175 435600367 458089302 194168748 308857830 82934437 132084476 897015293 699167778 702977794 944129238 139177932 173373297 528347264 266594975 828947594 72293217 899123769 958806677 303181431 372863083 92969368 957681376 610417766 663810361 42540707 630189295 760520796 716878314 548352476 578895587 853016424 140683821 888247532 628768225 57002894 535893642 227998449 370690555 85195539 252223320 412085662 489606861 394985903 482575497 358965497 277839099 610066519 185498782 834596522 153959572 194155348 388292412 831250294 72095904 470211021 632725506 502056233 776141477 409972882 371306062 932397775 984703569 397351196 626952468 620327578 762665458 427242113 3862150 445889018 338879696 263345253 307739654 373201954 906122029 74965542 326674096 347317980 869725955 441626300 118935133 384757267 466127436 976036677 682767892 550592109 562043654 966401046 449849744 721040851 385890360 250699690 449309375 188549100 511248850 103768925 140392678 709471573 63033377 341449542 790614637 655807874 47261829 117593978 125865399 351170675 157221129 324583049 627963369 290570083 662158283 347521507 79610827 190370395 197944143 29583829 985659140 144193251 27195614 422208351 440517246 719180252 26689787 146719333 140827546 228942675 844230912 756275467 472695607 740887559 344870423 876649322 57581279 320038390 390559500 353509344 416657189 80804307 236494240 728121941 599381374 583582520 445543828 701176400 814525863 359662007 905916478 998361663 604948076 143457285 931921707 364787208 872241976 311692477 468738719 723600767 264119169 287016373 372140949 767597302 13982008 964306469 367138491 242772308 89557320 909431818 709293441 978569724 784428936 125595148 839041490 476639356 809550665 998584691 514674007 610568085 152055945 19580996 575105846 919268557 448697474 19774102 902999232 841678899 469374451 181807641 326887538 742787442 981393400 940598681 369761000 522014589 207401833 989843957 240915865 668065438 419975401 633635832 354865413 558399017 340383977 698937166 135955310 302650845 988959828 693288865 367938674 128064076 483935830 317550364 573580901 180097977 890734531 962442126 662316124 878874539 50354476 723702048 648421488 199467821 768219386 669343769 631526867 112328597 700064658 18314554 773190479 475789775 252783526 935814106 380362719 286643487 113163784 385675004 436209551 226364670 895310698 376137255 792838920 160817871 868968881 49057448 406957629 979071356 14582509 492373272 744199361 103244729 985083389 604816176 444488253 930845049 176880874 390106364 339979803 173249980 742005698 242067422 104328921 200317384 181803796 784330227 754037843 156765536 322232749 605214253 788245284 885523101 861914594 709139169 134767590 953087064 306026801 486742798 401098682 787628600 418728981 442721394 728520613 705869508 107972655 812598878 530281039 648043714 786080070 884275042 968883847 632008113 654670936 939845810 339622195 714239385 678790979 270135986 637359812 749015497 89141320 103245635 660060871 772535117 359609844 393003932 385779132 569463885 42372292 178658306 963048410 212315251 874744354 691316933 327432480 33369293 139607889 530380481 323861037 790799161 504474534 585306219 878268171 869343397 285408994 12633329 248022966 87126169 972765501 612749611 781819717 307831574 85340430 630425602 911262355 694491123 835593305 986633864 572253548 528680823 267796036 840526101 138871008 59394171 147110029 118341188 909658130 769133399 423289305 690579322 448963519 549798933 533836435 524966040 120936448 794987701 355899386 260442206 572577972 453653272 668094548 837390807 648675254 438144815 572214129 907696073 243154902 697325089 850452094 244436775 582796719 849009262 799109349 362757958 933914088 602942677 895464553 73158228 853306520 291478012 391279461 252266439 465519643 112369675 152577869 409959084 87421748 733721591 984418782 847271349 782154388 664322857 279005607 66020598 141606709 414288011 375749856 626387779 878745396 803411707 109979021 799933213 320723334 648594041 3815896 714343747 633574236 111381268 532516076 435476089 287970997 253266749 995876034 272558711 818951626 31888883 794793702 826912382 694878076 594770850 164979671 934697569 203582913 155063853 542016519 965760592 914519850 180163444 423232247 252303930 118264922 36438158 645516293 561178532 60672956 222874473 945682145 996599351 501006014 46459960 222265224 88021612 49135361 947096687 585137400 564146413 361328450 562868365 551971737 523764547 933800290 232829943 749404373 655963447 885826382 714049686 489056433 117494503 786147723 641597126 809846177 352866910 892405043 389684409 674112053 731209911 522193951 555363364 446278999 925069695 213267991 41321411 624196126 839015593 513158335 326375342 642609309 809275202 514009171 976299372 948751453 494757469 61943543 111737611 859940887 955936543 899007031 401156297 885693896 323655718 836566692 670598993 648481839 519241477 331614124 944302465 646329868 997378253 833981315 845559011 902819773 753569078 248240796 346930353 939532940 601927316 711583255 799410907 193476918 96403314 262755569 135304728 727463486 30046182 889190881 797734030 41371209 862428705 777437078 320609312 857548978 350325212 500240422 706834656 919013241 110916073 19022699 939589139 677660802 944876496 742237863 406499245 107766602 39864162 343603672 491735245 830538691 309052628 816819073 970282810 930603892 285729150 637119022 929934783 874421847 164330086 271308010 758265885 460107062 763504498 352373463 875177364 360915707 94084025 400049493 431547947 140154438 614274906 377408822 692402288 777417328 541827438 461682398 961262487 526710216 502094634 457329435 562279224 977632266 100435655 133967791 401785456 737610310 265690473 355643030 413597857 518962786 139878312 424777587 943096884 681123733 778408835 652786791 706706360 790724496 246107005 980286749 397810695 686303174 314791344 19954108 196771358 209115862 273635676 893239617 270209775 703230452 77247067 357343640 431224219 32508035 68216549 48754272 677491932 263660916 678752519 449307651 163383305 895591337 696505543 752112558 147919444 430966098 916438120 180529577 108015361 983482002 143731158 458573125 249555315 773959510 276865354 788333332 517725909 356551903 139293111 329571244 150717985 589171206 313182433 640644175 663232663 56965160 166963435 627316111 538323543 177185205 643262989 537651156 404966294 382646637 649037589 123953711 886721794 886634069 691263833 737041887 157117727 101885845 758032977 390321467 847935768 193458207 142472080 935625240 237677092 391805040 123614983 190558150 561061069 642223235 215232239 702236528 332724759 891781634 826893655 26634135 75297567 418894274 434313238 484683908 719448810 138979085 263622137 222790342 294340002 638170734 486968313 36898276 488937887 692994305 42941980 754034340 629361476 119073067 615854290 324440278 817920224 380841142 916828173 779605832 438944978 178094716 192699718 642888814 556347527 765286401 980292748 916761184 538618373 642498445 651619913 27322549 865942938 654533055 110401267 750732592 854674870 963993063 129388585 681145724 490775352 584598708 651278409 796185631 353531224 632020739 30840092 493459833 301434440 821192859 742595862 800432243 212862396 268772391 756802903 460544326 373366332 466585756 315217423 241164485 664230754 326578242 362217815 318380813 563691830 894352018 256173270 94567054 363607893 81897213 311468308 164733106 640113085 431893225 821125222 675855581 202073287 436223800 685677292 491349873 923172729 890676859 861040300 200263472 409252595 217802891 968959009 776757663 435551684 947331981 474546157 322902674 812446933 998261066 761778734 388285717 339961037 725662678 336668755 384702125 400274090 117168422 117523118 41096667 844095928 332383578 584588061 751776196 980529703 884377948 325023968 216817877 805801647 173267348 177757057 56611036 498140106 207804348 387481278 667836029 378822663 719915103 770647296 663101940 81230411 938279643 980889725 986655128 667730933 930398111 659027688 963445048 207702353 672186719 205849410 569938029 171977810 244506844 889832116 524441047 753438841 242804918 430614597 45554678 569777878 447351618 93196125 358307223 628816121 812339760 502126493 192839837 69480208 594001696 381864808 719778595 120054651 709363342 334813215 710749251 80941415 559562321 738226244 441389394 848502515 944357621 106812550 104040597 945273288 127931856 866285617 836310205 957437283 620944972 734848691 51635120 761542385 76069909 338901405 912052473 990313664 627434570 226127173 971270575 193564476 440968019 775374375 921330334 603863521 352915705 641679059 430728068 282325904 917456347 40259637 601706975 143804372 705793609 41312555 287797393 956411619 172645225 900283498 204368352 821002603 640834362 890527360 793092522 236264667 963416144 611019172 279215345 580687470 69722061 241822867 414946816 413903853 250249871 185742956 987793097 666072050 851277484 62649236 151360273 170593994 937983045 985996797 914844533 736313367 734344244 421898332 338016436 502234105 168116293 623411509 890785000 580611213 460999151 388146268 55881011 578171349 894695984 1122136 810952541 631814219 959599788 461210280 175800177 837081716 915403280 292233230 760816833 116349974 511331160 126259965 617699893 912259587 363125460 528771393 263867972 997473180 927671212 986242659 697700307 327354169 721417384 384243246 508450807 345518017 616955314 572825843 580283151 170979865 883618018 393097932 814120238 653607053 68171387 409650695 821377389 55856817 864345842 82581608 390196925 341242054 177437648 636422978 51959447 827732293 487617998 538887789 205133965 886596713 211730297 212291975 289024166 673453323 760639941 121235647 246917151 945696140 375741813 101596318 189350342 630162307 976371917 912002116 221479645 487048415 733987182 162599651 407667777 991721457 987086208 74423470 405528454 717904743 226323445 929295605 744527382 970483660 314315487 641682508 981086796 842749905 588201154 858197309 167635276 811646315 567417428 121619137 505501149 652297549 601137243 79794505 40413344 167942961 647942871 137499376 852947805 585767114 636153721 330822188 276598853 725973006 562842702 680026212 219263782 540919210 878823113 537240585 604559685 706289911 868070878 861326305 919647111 468800591 121011318 733659571 994706760 631998803 535736547 773708192 53712765 690734589 188345663 398248430 887952722 19091008 862376223 495849596 556002503 968847165 164116227 403113496 933332427 517496694 839823625 459188596 706977664 25681577 908237773 41491018 297811083 749656660 122244994 801942073 432345157 193024383 995980009 69626813 276620486 879153731 22116567 136094837 795486902 246703995 576558783 521899988 260403075 840931468 517782004 213835479 482772566 704797567 247114237 533646882 347296083 552169622 479449714 141684681 430280071 665921382 811482787 738198849 142757320 572592004 201164577 213414547 642087754 161369319 698360574 775465727 979247379 718062505 218722906 497794837 244413962 317494450 21662746 658018581 883015497 693267539 164212995 853523997 565942203 521756191 951627720 46728083 167544552 499780919 201685392 710150795 897948873 183146664 280023346 760856342 895407349 794352894 298168714 638155909 171705885 354912725 923674745 873832365 867889380 988487319 919047670 834851900 276239752 925884199 980577396 636421363 136439345 378389175 377091316 840528847 122278229 194394656 785813312 217167427 35796842 868627879 853023092 689634593 969761940 847828800 25052671 282343629 742260936 912677085 680100139 454166809 268241081 900200786 931206398 526149378 886611013 678005155 184762109 877917752 486545088 939698460 731421184 617924324 439455432 402834383 196580812 513278315 519086775 961216397 548890549 951396089 169320474 557116241 224586114 48516081 459390655 51806915 464598682 589464251 902012825 170859714 102193386 737529242 594299333 854620447 64680104 998416497 563688763 533918278 82513616 647668951 410764669 59850495 171796339 195916459 803390499 430096961 130546714 631402513 909425629 707442695 969902994 525505749 321456206 506209569 733670714 319366467 62909047 524223058 139431329 611839454 239401041 191906313 919178619 363887504 556018108 718216095 901264089 333423164 137738196 182488447 994266991 965523379 621229143 992772851 211131556 358456711 123983939 462651445 714011146 41960748 94539953 94233117 890681004 369438159 544445244 95254419 255763398 994976029 590104136 620106640 602071409 113844430 219004725 846589427 57688322 521410557 407541182 870205709 233629249 958113792 640721333 776733762 90611993 383955105 334502963 699601962 4074956 516089101 320450446 647591254 555123837 863165156 528862617 139431478 128058170 875221406 138323708 468112165 343905172 769771632 218203043 398534143 262832638 649104066 762790522 495378096 746185000 247249858 237482053 481014371 370787774 893180213 648469550 286881113 646164007 933835657 336156164 646011276 665627414 210922781 792066357 182749707 384852851 184739823 526871746 287084286 43034823 122627414 47595999 10892164 92563302 136144220 387142727 890821323 873125459 138292504 278125463 670048533 921118006 216339027 423460199 368041278 476178503 747140524 706359895 411074490 768039034 833774634 106010156 371320273 535337035 282484173 252240574 189125103 457399417 514240684 624422940 293713598 517564715 408506571 23193997 228683273 401935830 622511681 523650863 889340006 715829824 202181290 200969328 701879296 985262128 449481615 424370414 957143018 446776441 406400844 352311415 211261505 411696813 714674250 397347373 522978873 876087103 986438499 457422221 785745538 774398295 487850547 514056161 864586820 461520415 739627060 174104424 509420009 478468742 513290711 357324269 482012989 959348434 799494007 106961401 73628150 794140784 437476295 282429150 714943888 56550501 276277226 161950597 361919474 270791508 741841635 724682643 135029090 796403802 245337744 408572384 763246770 926625398 654469187 504281753 326883781 92543010 185175027 972855324 674616917 184020990 791848312 544004071 193661144 813715137 629974056 744338089 935714154 606782277 621912658 86199668 379850094 879743813 111083012 508709621 22855636 27901975 91186560 996891364 131182665 682232185 351106710 714128015 176269774 658027773 698810744 628692270 954495316 832120414 992246292 432420009 634675614 160618304 881292641 805640052 587302024 320358134 977515842 48000543 245700953 5178082 303871599 531431472 845899277 584393804 287333448 498894781 659187162 633332277 970792833 347841260 500711406 34570340 628888524 541554481 159996986 954708484 417605030 382637139 827743530 706068593 523095489 902309241 535680418 854949314 918833425 431572470 709585114 145910540 938682686 943936791 433497013 778521936 985856840 768625922 88373791 913375849 259356979 556648933 51429099 490039012 101735611 123009210 322232488 555659346 692969655 848311072 634132047 518390500 307922718 449831354 828852397 673804214 919183480 796527696 230460503 761931129 805692531 935307531 256706580 810630582 335026400 694948358 476546587 185924647 803822426 246830628 983056418 94902110 674148853 447679207 802360992 304679275 339268073 374377053 224684426 671456381 395503428 452330247 864036897 883617929 864873092 411133006 939219784 841200523 966288128 210376877 694479677 496014674 682808096 736382183 823842902 99179317 952581171 859885546 386565534 412886985 604163836 297645474 833951515 788402436 336470615 28026165 60285218 500306316 656800839 934479639 875318556 582254492 488328858 591299437 720844540 914154572 830066528 422699282 552545385 719194480 256130698 195885577 457763800 241116348 636542571 22527615 483890774 783489606 326602715 25189654 516719214 711226617 918618470 108178137 680594813 24960504 434300616 448683127 720179316 812963451 982046613 627813947 839587302 24097395 653432959 147924140 943340056 476907933 859318771 156608365 600903912 34554912 101384052 587643254 399173489 962836668 62418661 942031056 177724130 358491159 827250012 492071895 634451588 719177943 339171458 144284486 315815228 829054596 538185585 401066943 508673954 191408920 457626857 198366408 148232790 767992920 88335848 391107060 654255157 388771777 999400151 108458360 803908728 291460088 374511795 485459838 982541228 762099825 500569073 252240021 419450900 479127685 595117531 239861716 784086580 538742947 164069171 153683258 300721651 919501406 733283569 207372315 77388223 5795385 450891368 427961345 479938904 774713368 174045698 691502984 404428676 427707985 178085355 566387671 191404431 144635704 85662745 583402378 574839827 785492359 502192653 376906015 859169525 948318828 52050123 220711482 192451789 200245501 153977637 411899663 955408624 749437253 663539257 669857177 655224409 806848289 494511247 797632696 716363200 493540371 602947471 805024237 592175158 439721991 720634799 77173841 607148851 99837909 608344965 964902096 532647855 310702701 592204379 881687352 528115301 778747409 257132259 123039448 766151148 280867158 601338948 314701285 502956399 101327783 258867007 267960630 738851278 812066303 151733005 90579618 948518301 929717783 100234560 729372818 145833009 326901816 875175584 474022904 991061926 181956944 547349228 294197093 449341205 645161049 699727817 805329674 656962830 47569783 606228048 478230264 441827063 365588726 731001909 702560709 750027645 408593908 894394605 685943056 340046039 457956823 599724920 816120270 218777115 324180857 204536443 560726828 778737000 41907340 988049803 869253938 452826532 671865679 80118763 223879559 268384633 730596374 979915444 303472179 686978237 838934046 512646255 802206297 677878634 697335795 660001234 884744591 412834857 437351978 920206033 808400277 261858593 803935621 978538879 976201474 322314841 117879690 860096187 594191016 982047386 270034093 146237762 51611444 630467632 950366087 540585845 569275931 782231008 803172029 671823996 463686599 138018978 329181113 471536263 296675759 286399746 57208487 719202926 389148019 119455866 583555868 459389630 980903562 466488881 720903378 748147965 168371933 822190940 757757017 28976536 958451718 385403175 878863187 417425227 744972119 958032222 507727770 744360142 488121734 559407015 757951708 262350636 872929355 781236000 172713400 733015256 31606920 123241770 93443601 602771377 177304701 307125214 443039275 657708995 863999689 597463950 700492496 854183650 967341959 565037503 155975997 84844030 593225405 164986728 574029109 79769670 873280965 250640336 278988852 54580850 121575496 903084318 114519337 349412404 729957603 982806888 230585229 766938531 844280909 111441082 923906657 442445205 894997918 69073923 417121744 523304855 910873425 348884431 390823696 865843900 900184830 655684219 118283581 485958920 317026252 669734852 852601794 349185031 294139131 19733078 3942995 338086516 750537863 702494919 71294783 475153180 801067205 544328480 863091853 600935810 531046218 601889751 816049990 563488891 216147741 432160330 147982993 899719834 126327381 889993053 400482319 849105708 669924610 702397143 348358491 229943057 808940527 212407518 114041745 845376061 538524942 276683825 987191520 725887417 713981007 558572992 864909087 177962548 498223387 788578662 327335836 660078114 949746295 925938032 113282508 686689777 954486449 911010947 650971853 203522370 658225291 838808241 679027844 18952439 723419440 769987701 991778296 798399198 669039477 221296573 665736958 850392401 515613975 168263622 656121636 346156368 752931906 217669190 567841518 851284173 101831632 815836564 357632963 565726475 656033733 720811538 487289252 116714742 312160185 159243732 683177517 540519047 300095290 438398193 432621128 421533796 817608509 727024393 605781378 781232914 573481067 493573446 722290595 726204249 692152282 187350890 312711394 686641656 489330913 46660207 818553379 230635112 288581063 484206352 927034740 58637502 106351399 409468002 348555762 29743112 431113952 269145444 540487407 647245307 978747846 743300012 743447784 632402831 682353703 797912590 495417888 645280867 776402020 435447658 521366666 801507139 777712868 40971863 750018206 293311177 785652348 36904898 48880619 649940218 775619402 1879770 337515637 822248207 691990843 946276733 798992567 959311523 733173428 365227976 70321876 997054967 538752756 263312367 844680571 728211218 595239559 260563602 963346663 683160450 138892840 859374193 217903419 793315865 315985411 521550322 781038094 607858562 88701005 478128004 226841232 362258384 144027823 307549037 623749084 472666153 313865436 60908826 540381632 986541924 231589398 362020433 132382691 121398412 218656674 667056373 273981863 995275703 436226758 367572578 917934708 159767652 500143900 827897601 707316315 188078485 114915740 991545621 402913571 544294913 422304283 773515760 390994747 406471401 520251640 515269350 391244367 972881832 496222147 34644148 668466558 810855435 697332595 40229447 121586689 562919368 207232206 888238764 749867178 499425439 234905517 376822023 86379076 255593756 858116632 547558710 676528103 241746785 665241064 890014815 153273114 156292063 640416724 497337748 122489825 358282485 963238820 879700926 441402477 472474490 490273487 247561225 18945365 828010412 537350138 593223354 662558617 449063327 675399432 242155782 566790310 186821059 881497791 716611897 804191103 297418359 126920295 65540971 963426566 30565412 176609777 401767170 143758695 14096612 207062740 662187429 515975017 760188074 459360864 334789744 556841034 894734480 440090476 677512259 80908262 969266928 129736163 664882382 216793703 762708303 780583119 165964520 619550276 395163984 131346947 259914506 447186528 665884308 209772468 412754983 545991641 925262772 410144794 278517015 347307197 90877395 698797661 613129702 846644517 137221740 561805792 899257593 930068119 305697165 622289916 959734776 939362810 765252357 652996958 154673136 491130982 662884547 583176703 210065147 221609076 634109904 605534699 519382173 757090099 154151076 123955949 625011428 596118754 130234558 815319049 685884210 436701369 912272120 943509984 54729097 944217070 426847014 422742790 588021928 38177667 502749452 810034638 129029768 352505106 296846077 21228565 255149801 438894595 195111686 142324242 316610261 206553367 10138606 185151705 556123616 905308562 903664319 743399659 392854331 727136561 522444553 834283307 603318075 680587465 4415692 105780027 57660250 103138465 942924641 663408036 886191308 328569132 316574203 670128745 443181343 952248150 163545123 332006597 402916910 39375345 331569968 998916128 608380574 723427733 311328590 280731582 745567098 334772940 634409122 998909698 432823536 965574880 984710045 272664941 70461066 466585437 874160401 753099420 421386930 980345306 470748949 808783871 893806404 616558246 887496342 131473950 431648001 60903403 283742650 488688671 747015644 917611514 496497570 458493600 729093772 493390615 573790537 773303520 737556976 592320175 703817060 66226497 266881048 32931746 959253761 448380164 397503660 20063428 783273972 860933283 832973250 431378886 709571156 866249580 143048436 133365470 667484101 624247732 956533125 927909054 786804175 783443881 775007305 160094479 696266309 413493486 328426245 38852916 600804902 780851007 314815506 774045317 169619862 801370377 674953737 620682671 411326841 28429882 377562342 975885049 947807974 393114745 237591536 763172477 462220466 539715376 841400945 733554113 614934924 461691788 856165062 867062334 39373393 850634630 716942343 621883721 303314287 691583855 691907558 204160478 76843499 534411371 932157265 228548310 86028595 406481397 705035247 993948239 437229186 400604751 296463909 306720876 206121389 56704249 409033185 584337011 532727136 836139864 22702154 198707490 587045259 962541435 156129649 711980402 552232340 656890313 712944148 482719067 121109627 120460573 348005337 897763529 356524435 719190960 512792790 475935818 997468852 94316024 492746174 897180686 451649108 897417810 656007434 146471784 235942631 271611151 59327865 795672179 60960791 114831280 778607881 693775244 475209895 19122172 314087508 899042522 796205168 403164249 130604208 489870154 859171679 169531745 802466716 926112044 726824854 38384874 227829249 567486412 233017538 86362357 373915900 82697908 375332973 786500061 337918121 892931262 828912223 367702154 359871795 824057565 94973764 79976655 32419936 755820286 564758289 531655070 943951476 192398383 361402216 701756396 332815351 529482752 659250252 489086952 128823318 903239565 108433853 330270137 985946943 312152727 566918846 204736522 232072606 216261363 990013587 348610956 227129039 743782561 319664755 794240879 386154365 194713316 158847551 735815721 317458178 471240724 904483122 503667461 927890196 295388545 565923703 990602081 19953930 624579858 582170605 827256438 18111388 860483383 625461425 245078445 587816059 364358923 94167030 761684343 92501109 773760693 984463055 119266425 415310611 621837854 223925045 564964879 609163989 415880208 291555716 384085797 474557867 339097155 259144722 738706877 708446130 388236360 213163268 406148607 991295796 26214175 983524494 563513280 820040733 361793318 853736836 675628161 748922315 69978801 593521330 490947328 933590385 134610893 721504583 174564005 425609993 449268585 921979398 245217744 237378534 696622881 36561820 513437963 693264595 421554427 708526559 178533043 499867642 847255851 471608868 764133429 632669498 33926363 944210431 162993589 358162080 660587393 313183859 676157397 896587880 770023519 822114429 441741177 602591931 653198179 128903089 64430383 546061703 590218666 49499671 300160305 396097226 799998380 291525314 532069235 205547939 728448990 330305447 117998205 104706650 471026403 537974544 587972224 290472627 279552014 992456904 40977814 882694030 251985681 679467158 478559034 814453042 332208915 581311587 275034262 212279642 605147236 574098484 42947866 720857267 268577530 873390007 931536271 398273743 256808347 886331548 459809503 898822321 905958718 202960436 439723709 552580923 539080695 126066514 432330734 197789185 42061955 423191310 281117433 416996673 786261422 604423800 246490851 35760878 967171053 365695268 703832776 717971252 942946904 624309723 115198763 827218886 109375713 223987531 785424634 910903101 106145375 84447103 803814885 553560456 887579663 983009035 155129170 490786752 837365469 487027939 220568036 53759370 960891471 480233023 770289453 634845159 667063338 70714010 134302219 237301812 958024861 667013518 375705606 948234634 372999644 482855682 944650990 27368493 815841634 408758664 125730083 652097997 665314924 220293694 90476277 213569074 649208779 670981689 839072518 170299672 919583767 142541329 517676826 608204440 129489547 433178087 384317141 319843587 456031916 378690883 417428351 953774816 781819138 781024714 363238120 803196164 66739927 348499425 648230234 686952284 436350277 630765705 349350728 814412837 155160753 145475877 682238053 494554710 801374949 531693343 409369180 539660655 701145532 869719370 427808613 283242101 538744980 753510682 990537393 717780504 242041336 953595380 947874657 965637774 886048331 769856021 833551706 445183324 748663366 29637309 375159123 996626601 667676059 285386819 153691033 113047090 942243530 477602403 289534382 582249445 381852577 864938995 941389275 614021638 839142214 911888397 699368555 14375458 128512418 991640502 35639318 370815935 289269289 312157062 758024850 432191738 720410203 849109473 383562598 615168694 33012680 317578904 854348696 98254920 145670236 978460741 561830153 328070635 948307286 647429091 869800993 492612675 476975064 18139745 30487788 464109130 4429949 404491951 337595104 402687983 759932443 405911751 439954843 318902902 257996036 137995500 817022108 815642506 299967483 221742610 839493935 830727537 544352663 774277228 256135955 260935509 989084082 56838549 245642052 540978054 739493897 355245914 151160930 942017427 308209111 161839545 178999365 762911071 130108135 878121698 419527570 807044410 272380752 165255532 80096937 299318727 60860837 41096642 870386513 280829597 62032279 298234669 593830225 626299215 644513865 103138322 563962967 252333048 809001888 682124695 415108714 342429297 598312264 406052978 172370418 789172621 112535990 221213066 262214274 58307763 371336462 17504078 656518204 609928645 105238311 519338268 838324966 195734239 176864408 17295387 151463159 994927499 873280285 549318208 490343005 348393640 327598797 397115116 998843107 523369532 206355048 693658200 468328102 285324302 332543694 967579469 179480280 622249598 572927277 594366055 922474848 28933628 260654035 416187797 240505797 102304061 813584690 41670093 586807508 822696318 43763295 259338921 879212388 866863034 264659408 713789768 190059282 625541670 451744372 634042801 385771878 884947774 514816075 522932991 875074962 661330813 726435766 3561661 432575318 230954200 588119410 523295302 853387256 12517470 713506450 128964176 526904876 854531725 661732785 505466925 73346753 985294771 689062073 127073259 954778698 939392563 119334065 947379518 677401214 700868967 631033652 241235920 641183378 301879911 263986814 45880341 127670160 163497085 185478587 119016526 988186110 923957098 165079158 818569028 225502528 171916433 336597717 906968567 319520772 679936393 625259210 196188510 385422063 86483945 158750593 137100755 162726113 890150003 2593634 438926374 424415353 890888191 88216632 384139720 955616189 745533385 66212801 83810287 409272166 320746388 293204448 46666685 770353309 804349222 722399761 587740770 692230792 567009198 107545943 436667188 638260779 433382635 521824596 370003467 214313734 726364376 458437272 527684429 429534987 676933060 733121988 135133851 650181731 305743911 412767070 8766096 459907420 734151318 792001535 710647347 224051342 443031333 894577834 534460620 628563162 271123840 8623409 604116454 786817874 885913994 268322976 431625142 259791085 605461764 25336328 75670308 737575237 153399420 632912287 329384900 455242217 376911281 704105182 509705553 735835541 829648634 497434563 235273309 515353524 778977278 923240412 365017004 826336490 800414073 924285557 74226844 496002711 134058152 720062301 772404099 975086739 842814191 355615013 846940356 359448032 69177716 817702365 855506140 271198101 373514688 185182759 441875571 965271101 600801692 225408583 534903950 68574511 256330840 608902949 490314111 75682584 44394601 728069679 760943109 264536698 546417717 439478013 981045205 115700457 35309619 734596380 410145254 143358530 825460368 471165879 726293514 674477744 42973870 280790413 477448723 96780030 373164028 379995982 586232294 979350751 610398675 363252032 626507231 256395963 179596533 200909696 299263779 591925389 534049390 405487244 666390132 522477684 552751225 665286635 343128273 735524132 13393781 920974955 406293091 848219524 849327671 84555925 701233116 399385176 278394753 141133663 551768649 635384269 174658585 826327247 997937904 323298276 305392520 485915785 878553122 460030262 298206939 460251503 410365110 486166699 932520456 423411576 977894986 169326294 540134962 618571847 676664192 186398660 681686049 761181874 866927607 680328103 127010508 607254564 744810129 627097178 232704526 618636137 160560969 369916094 506789844 403839179 21582903 977797004 159005643 203108214 883441066 50684826 285854734 732530312 973584947 132713230 470673815 708541025 235319397 390397872 908903079 552370482 60137788 450646453 616173626 394599964 805595009 878472801 549998004 958446391 312612756 827015250 394147478 21235878 86929302 398062880 498687955 115444541 916270825 843204501 21987695 302581844 497254460 564221663 933871691 197954102 534634208 619039247 822657032 609289965 566804792 462641005 224016952 269541900 598658594 537753707 36770819 48030012 278161629 576896492 464932261 946125523 625502650 755386857 253851486 315274822 404000241 970101533 224987243 320634496 825719794 346217348 390618662 757040255 528857500 805290230 506622125 561701619 507695387 167966438 200886623 360228642 825785129 229771724 841382210 542506168 423979889 467446165 605639736 908975257 994184490 737850128 54165614 499560744 566120233 828726461 36191749 574257029 821757352 739910302 812901244 37818481 520022969 495476751 712057661 562769776 496179076 149512303 567187328 150788025 497526418 46730654 422777885 55132009 566822742 694185984 647774653 97405578 118894017 702715548 368574760 697011338 433099287 676463102 75962604 768017364 304300738 869096343 791800843 804969175 364880821 145548031 66524968 965048303 305559286 326093566 806475183 705868144 404892802 117566246 88941897 740967424 645516142 64177429 118414575 689458855 271560221 10609709 765823460 591587471 88582368 809424516 636162109 733587434 573752762 950179470 50649151 10737503 852741008 537849196 594527727 63130822 489281721 401047983 515749718 232875469 359615049 985942147 771339549 896094544 79553006 999833693 459571375 141676400 860744703 673232979 726680224 562615517 701219132 970008384 531131074 477339585 63255973 859464526 262546472 388948561 553667320 866862485 277936840 985622365 65744096 932990006 836927988 721148155 31760047 514894421 459146869 901894909 418457613 149950327 456660334 460131183 654219148 862141182 356578981 113611659 829746617 119431767 336422683 510953001 453651976 652589586 380556975 818542754 783345511 449254130 251017778 124696329 587700014 890173995 178055877 944998093 472098273 866252578 879326074 872834143 118588339 187374143 3486208 917572454 783317664 821256054 329453055 121876416 649794385 95560610 863631311 491767522 733352256 74439834 993131071 903753201 371926567 746947674 812259244 183878484 593026852 436086454 447912545 398502924 887902746 307079079 424895489 460092707 883522166 277678677 26459405 477386317 402924745 623947728 349391598 300989762 996874350 543856137 620920436 527378791 86069737 197027259 964484416 640342884 478029308 699631954 92145566 762235150 430119768 531157707 380357953 342669820 559634266 203584658 218442468 493111342 431071348 740390120 368039513 994764222 374083105 929704270 33855248 765998171 801588229 976212008 41307691 689813655 604482416 921039756 188308359 373054768 720611391 669902399 430443344 589524488 849837000 886000163 729597382 15428442 655548481 375897838 749006379 538758058 482547159 378602025 74764860 669424921 109224518 552256373 951378472 242772547 185610000 922670836 99745410 265964221 502887007 963012896 442358953 454818421 722346854 726408447 852562214 112386178 642011717 651568870 449946980 841701035 943202097 543052866 732942178 170743899 311140746 334620754 914506443 859235344 563506481 275156715 787714794 642339492 327638892 64747247 504759359 169255126 257743777 660787324 181448697 633887239 576433812 413432068 341079248 744418475 658358975 715276085 721713154 337197044 781981448 155152219 248506828 75950244 274405373 261575941 820376783 355787530 259809539 260591358 149203897 110321490 981217832 743248011 226681669 699815215 879224432 427520343 216664246 689907008 94676517 895374668 667108087 669054589 261152989 594618205 915176381 303300058 541748461 369017590 115822112 118402666 4943836 873294029 859386096 656924068 123787617 928829821 518901318 901286124 116408760 690929214 951436681 376628305 803011036 218072759 714439501 387782021 337479443 669325271 256802939 981798899 515204110 175029487 476302510 135892010 447248176 480338586 662666081 23074412 312765412 348495731 807963929 677452191 149862264 415170826 883921012 136357776 825859371 419347628 609700938 635272871 273520423 783911775 872973204 458625495 592574040 24943528 418243118 352634958 866107597 364425587 370369120 267573263 809088884 719281718 681445063 238225677 861813868 685615367 258663335 127059262 552062722 540607588 693192160 14784544 828534441 442364501 554752544 16245056 111262498 870217973 24657136 549825058 916392308 854749735 955107321 18586953 126353399 873757745 367977325 694345550 450518169 366190351 821765623 545235985 16614552 151224149 982638080 212686218 607931992 656088690 616722977 314928000 473194918 943952339 267555167 590206158 962213660 449983314 325743744 733299135 874623851 692682750 885221247 891949099 120119695 382321903 916555462 491690115 671644897 814354472 85183706 518628502 28072076 323021057 892977249 785061045 479109056 889188267 696068395 361429889 160413372 558652963 61230260 358950515 44145647 931087435 476318898 547935528 557362425 78701165 446851108 732754140 354838348 227298156 689871629 737095462 415500218 740782571 518266359 415075790 403732375 77591114 741173920 338123710 739375122 105148402 801429042 206064506 388079517 301209118 533873437 821293351 23696613 263230859 96857148 604363657 302025666 190534361 555846659 523192943 393051216 822362218 544698734 40275741 826010856 100362385 664359090 67472438 557485108 8390694 832972876 556419511 494366195 330428316 143356946 465677683 760726716 472404165 955014440 508308156 514983848 171890912 566446597 884965699 375384663 651082516 177602864 840647700 687603248 836206472 878001250 910541099 664639212 564616315 550942321 147729012 836347809 103424538 833109244 506652151 281122362 92781043 18548926 55046978 423766267 213133819 50453244 794096958 692949963 817638087 997913245 377244167 704594677 3854027 172539907 803197446 124499591 13127970 472742005 869054853 105064147 990147613 337525858 355501060 444640428 970938121 530513914 384160261 926323992 401279743 821428465 541762821 912496625 850194283 987084987 81360373 829522040 948812915 815141106 281356285 80151819 317784510 49068845 724195938 419164683 89954424 960022273 381400303 504924660 766355424 144809405 256985361 617919058 723100762 204580539 137481814 250632529 570592710 670026264 631586756 431551841 32828848 513956299 189113783 623745862 131218731 452830757 655675865 970048354 744208169 611872281 791882532 275099812 758517523 620258138 813458077 509813071 242212534 443707841 217545141 338514737 856496639 234893038 558023000 719891886 871473636 801344057 635006083 720727939 493029651 891643957 437953778 480621107 918250211 785800417 918569298 835441226 956862690 228063296 392869713 217206645 959455823 499347357 28600623 155757684 133385654 300224223 145125340 974290532 554427386 459562639 833092998 724892130 467558711 296306772 904537214 386946595 579923962 996753884 543683916 734378772 834635018 744700923 256666017 362744421 114396280 347544864 22825525 938638615 957943705 301488342 121705764 944441326 246599296 243179608 371931154 850738171 902528025 442773489 292759469 222089119 346594614 784783958 312275713 654405336 538911621 662780147 654881565 29032415 240094734 731572442 959177971 485254436 280511348 786127933 51471412 469616624 480385397 512898435 445986406 509111425 599456847 443443949 788885716 637205470 184141527 901152944 13865994 886197569 140673525 204706242 684618371 560818988 139563706 390159762 563873839 90770945 717339369 498544380 833162480 849390655 904232365 322309717 179376595 442536309 871398437 18601922 212669786 856432001 234255196 741841008 530894282 194270652 762327586 969513243 151602096 152856571 426016945 130614888 547286618 190432655 413434887 530051723 494563499 779310549 697115631 836696604 235663462 723615603 539782247 699623770 524453114 791952588 972815875 882903318 694788256 611881112 328881909 191055566 936911220 487545172 194925833 807305063 803943509 835065891 266828380 673054910 659453742 187806865 209701660 594488382 447576258 797301010 260772287 577759413 322516887 702928701 406164390 230659729 939900471 494315271 946726627 667754166 369310827 277742879 758794819 912102840 230217444 447270214 336138105 895552761 810010925 987428805 316703929 465584033 726091494 476797632 882798976 887655749 531700177 624419305 170003628 116513064 609461942 247871466 385788910 505745311 486688088 58861021 417901892 393555816 62669165 594412589 634891034 838685834 267801207 310389909 107182454 275102734 533227518 240871996 331906484 574904826 690466033 586567155 533815607 614425011 79071641 115144218 685070503 117916471 688824604 796500056 638168144 838774933 429916229 590958337 631842852 801975147 365885212 644016217 393136853 696873912 435621509 923400211 992340651 805207279 582302241 716770811 739377899 319861452 826260018 244235183 530130809 191196610 494431827 996367766 743637468 82545645 44662825 512495489 120338865 205760426 157762477 561142960 920164521 984296680 961844284 357562844 442749099 685887742 653685045 814663301 460931457 995729240 862422354 388966270 63296947 65718464 901809478 587394594 899973772 435848968 800113395 890174471 547399817 418760513 971326131 610823101 759306877 393868973 785183626 53707798 61700194 180962674 110926119 224389083 460604153 403805480 239226261 75444739 651002770 897027679 238977717 555749276 369571208 607540711 437839629 28346762 509145414 144553130 230852489 597998534 712766657 649083395 103725577 79587673 490114807 319884113 569651353 727535801 133632408 33017182 487515912 110043458 792795311 485055372 349623387 100411880 409773654 338784067 492676862 786309595 982829156 992529728 765326372 137139473 168747648 432554132 29399201 191036111 142010391 95297500 421401275 222158678 5592781 977679094 184957888 664643073 249041318 900802501 686435750 594068135 510256898 231178129 531039244 122000860 121583068 239547625 943261597 913004306 968192220 877776864 518113731 767238896 682735974 915234950 436169773 89111648 900384543 810129467 556119062 863815917 265148710 233088493 389153025 34217918 348814537 628746720 252807203 982583486 466937083 438272726 515803346 238424766 745685898 944887913 952573864 887148113 351071488 401583062 421501883 839872105 666009205 325839132 25060146 963144396 805685897 974109840 738603312 126984199 83599988 24241770 926926343 996626760 759669551 340256518 898273161 368683955 983977175 130864482 373981026 355802814 348421330 772019349 791477034 352607372 231119243 35542050 970143016 422290053 445726088 901574594 840345430 651249349 180430930 467232481 689819264 109992014 385102533 421385817 614789362 755928689 66567117 332906097 356385520 987716002 226948505 18538430 603262241 865270682 989921369 885082108 265727791 861049153 531620773 360318489 464109551 188461064 484181368 318750584 31536733 828164430 670659707 22192482 739055168 249686679 868630813 774951313 630394506 526019406 934463605 591404679 51441433 385754268 811149485 430187741 162085792 641400123 630811548 705474200 225028676 377667925 662944841 506304205 190731309 793378315 902813835 98665869 305980218 499634701 183770162 877116767 348126438 293817651 632371471 240722500 260225519 699042475 821360428 992946882 697930265 446697508 13302061 522938945 597824658 641591187 206697782 243128370 11892991 575695772 323230275 199537723 776668328 617761295 720358867 199791511 654355310 347939667 738907882 376646070 719845900 114516506 697492724 728765073 214424969 72217767 854882349 337775854 928728314 962226622 697268129 664622379 716475660 681061397 696845716 227719470 866842025 719085481 215639855 971486834 202474656 523996894 323637176 306018115 687189393 550263349 217222059 557945547 135962870 624567200 799002138 215405266 221224167 839841259 880067304 8325654 770138514 85586237 968169197 473299789 416001489 742327232 217679548 859238877 980737946 302206395 981765165 999770921 81317303 131396535 510806576 130365825 7626903 80260315 904750312 23750931 872443709 54759262 449703470 177468232 346092702 242513511 643132212 345796560 864999194 104901038 270807484 913251442 619126720 128466710 764546713 125479279 69323730 42332899 841404014 536874571 63257864 660369536 46365444 731857243 733022436 60400374 42177409 734739358 246126225 124779425 622673956 186748168 769224662 559612698 578079624 83360550 365756453 568117541 837622646 419556972 568533423 231927409 20207205 221172788 947032289 658932819 824125814 626516610 258003304 899113749 578607105 299603206 77460341 247051287 921377973 44891219 465184456 419091055 867163517 134220767 373532763 852365099 704253655 39945810 91837067 15662933 514156478 693316997 513230866 307787272 249693419 218816707 900409042 234185474 297454460 78664332 621850973 427652208 818640705 749559785 89712562 249930789 547054887 181741903 357778026 887665231 609540350 400250231 674961643 762849975 649533474 892338326 59391377 445839423 808688713 488710459 485493149 205802336 410128436 978340665 796926499 557309861 805049859 933405035 729392900 833179894 389302173 699279739 201301846 879551417 168461408 617683718 965088308 619787243 270358336 654860618 628785330 583433713 682678013 219558824 399529108 23488895 38471611 917856301 338218322 159954807 605040365 458758921 699336914 51180232 695398928 195063198 220703021 155275797 950498027 347983542 891469753 970723787 947686791 756660865 782607404 510560108 31486932 959513214 953479360 639250182 907859806 130496788 73702535 414881816 98163756 909784420 492956362 579194427 272848176 104337633 963099430 190587266 357927120 678472498 969325598 956942287 691344493 742023024 146558351 257827543 326652503 704389484 837084167 900134609 335956936 666108837 945509318 258955671 505480288 110272902 340951963 716121463 198380025 341275514 26773012 652554143 842027976 354193376 605329742 31637989 823417726 851752272 71900878 417622869 394961936 442574346 121867404 190594562 571841385 380282283 124065640 554268395 702356933 500954605 112083371 137197575 325494725 664922143 145648888 98903306 660830542 63510474 375898220 408586273 816162222 79344066 874154275 888362521 517681114 774283322 737845563 916447484 257805857 289259910 441505412 748993075 619334152 203132658 558374016 101254883 776137496 934778850 350760719 932447338 119179068 558967326 719844165 279164502 21449546 384639325 921289966 720018202 224425819 442268796 293029641 606452418 256360738 938120230 841797178 630217439 969651901 886524322 301818870 361451183 781572329 949664024 612924894 840773683 669702369 916339870 673679445 984507682 548915922 525318028 434159394 196736295 273428577 960587383 147540078 116724034 791659389 228978802 626575829 213491806 131439426 493541508 643979452 214956626 691313805 770138277 370012426 986089751 81760966 169321404 516602190 956122164 765873703 86597138 484005850 155180403 388763090 467383713 122972232 664145640 981797776 520449772 527862007 895196147 829808411 416506649 239490671 974025152 601886819 448744867 796377130 756126927 16555130 484117356 287482978 951591724 693856627 418849903 572433667 781898719 557810013 665026794 305912143 511786804 435963747 936416993 451243591 218760362 355174076 490368627 167148183 82061030 51356024 235344568 329838450 413012646 1740124 348279875 745804557 945134894 188454775 996238892 272293125 690978519 991341812 303533959 153865635 765623396 897647617 311164701 321011912 746504761 501831842 32177184 255459020 975792214 229496736 892291653 282401432 131787236 67059669 870642356 838898939 843012381 369449930 502316473 957106358 743726121 238199208 353425087 266067317 785132791 553348346 957856436 194600037 392946337 3832119 827365977 892771926 841971888 120933857 496868798 591279046 287370736 759578143 603097495 273944073 46155838 632664538 266717990 440178668 913302963 679609766 219511869 757167490 170874612 909964936 915051702 915478833 316934648 407471357 508966387 26139314 550776301 847802656 403298310 129301968 54992784 311527796 82296830 128909453 231731296 927266504 508293088 218037372 833954534 135939519 715234182 372104277 491096783 693065734 355030275 880222543 573138699 251360638 19466715 555181164 965864120 943356361 634040418 199998442 527767638 646950990 456958881 904714524 74266365 269198255 680710121 503240437 694611398 717121974 707671405 437736658 277326361 141183306 591555565 910809242 396527210 137622697 988714713 722820777 335968744 481692102 681836881 651172525 775503585 580192313 522142164 239847646 64264435 436607207 504151610 623600021 3569129 387920138 318135087 293628486 552483690 276553328 462333200 320180164 802681345 372398878 332179679 498216457 166863960 299963735 955048252 481506964 56199942 953999554 458654776 456530213 739567011 15344300 842182204 450912505 996761762 510010349 279982466 680328389 879778109 571437800 333917842 380571770 446980205 417789517 62021399 181940054 944002794 336450546 950284721 288960344 698846475 941265198 301670670 771135913 517909656 833562691 379399521 180491960 376724293 807617935 837609239 475772548 85376173 878705862 987004661 407802663 868742525 458307702 787197069 645620866 358532366 872857246 925006484 94011625 984571578 249194438 745723837 86668251 676282120 35911350 753222734 843476084 566633373 96249344 920778796 183281580 293051452 780238194 671454111 632053029 749255716 146524745 217175837 609333805 40655494 22225081 111242178 245799470 382323634 592013505 392738767 6425236 574647332 84108371 540029181 844102022 421339011 509479128 614274963 438509455 214919618 219353328 990834811 214683077 754599428 929526537 502418220 521342928 789416121 639056256 267262965 63994106 305187920 691333131 941891556 32578314 643613255 746638009 669433192 638200060 113737050 755054881 574814419 895271118 788195301 340716141 814939439 915124321 378088292 169841003 467112568 569554891 779594959 476456716 953225712 464703358 250594487 478059924 703482150 622446391 809590592 617505337 25468111 450285379 995264163 444677740 307151897 301748616 829106958 355169514 616681588 602704740 366836284 640532551 154214472 395439390 730343314 282712700 578616015 696363964 312010158 791685594 115093644 888669558 189916123 233769261 410861009 283767182 356719608 830576347 54986583 602665151 880502128 832578023 926115066 795580446 331791049 213219485 69091372 407562935 73253952 61089816 34469300 423307413 508696407 440374263 466643839 476325028 456603580 213852727 234849235 390724259 125377550 662412913 708663370 500110744 366270176 558856031 81521715 152265963 361650287 628628304 175784655 439051201 718416581 143699402 88576275 428876913 818066253 99222125 82911957 604814076 893365094 567848290 374035517 557527209 624967003 526483034 833251532 22025806 694685687 617696851 651901072 164502242 452054386 592904533 561104258 796575634 202225883 72287025 831082152 245125632 147875287 614737640 342242360 166993715 512439724 56793657 731540084 358413441 623496277 927274542 403069616 586583501 819090181 537534424 801380362 700457161 948630932 209420592 158781320 420024202 12868507 262121870 756147818 151210076 75665031 5191105 647187974 250234877 499068742 564307601 500751134 449397526 860306740 158781696 953289699 615932726 250592097 391768523 207356611 528140377 497561809 674569437 19930385 615375848 404619504 381575521 72598449 538914087 872783481 927227513 568857212 450305452 617915962 667196460 755614889 595027961 454718404 643607734 81481049 958400014 585254542 130183834 344006992 644781786 441671760 873426379 402550976 718268062 10767465 105870061 923518784 830199603 521632388 645060034 589837549 770975082 578741116 515914139 375406098 170959893 809840412 972483093 180218406 545637734 244341431 652711350 109059103 193903559 314124328 14707407 185250619 2253427 579297305 612406680 218606663 693654398 454027137 196341024 341713098 488279361 337868697 926254350 86373991 741405038 126865078 787719608 903418708 644990445 338881160 625424087 101901293 141519926 195969907 850480316 343559133 97249999 161905127 572613176 174635552 789125686 997096803 767531322 183129405 274122940 191265816 205593277 2791504 576503916 748123135 94301808 450415347 789759781 66882678 97773045 137921226 213254346 729677995 147573524 715710239 217256667 108361965 476682072 103576596 628255854 909127342 845505503 839035470 318556677 349102726 201359923 147115923 855278105 286826352 664172290 675569950 56666784 347940213 276277478 197862299 344792451 38060844 193895742 116547989 40280409 662020913 983776893 785304126 739859124 690463947 736062174 533449240 930500739 732232575 461336334 950868252 609447283 459202680 428623926 777423512 308113774 885844356 94792556 939370024 464654717 581199438 190446101 22386724 67215338 542944123 475159798 104372165 278491973 890386420 786146551 422275312 401660619 764397837 439682961 326032816 792189317 860995878 234257157 912141532 19239814 544156340 484193997 611686048 521228751 345365649 343507184 684511051 421252041 640464063 54168371 200480538 280985590 891561408 801733643 541796030 798786884 526523916 73507923 188055902 611863407 436023054 34991312 814830699 255899066 791651322 73158939 746472059 112608093 335267714 786716400 45430691 479582498 306734343 575424372 713180583 612537148 593516436 451823603 136933586 775086143 839296068 508887689 361925021 532407325 274050973 274271965 123969182 183913437 940102502 565737173 974751364 585109491 157543200 351489417 539584043 25838379 78385042 990511913 570528890 303751650 563196938 366298893 968983636 660795096 845160333 796009710 866852998 430901629 983953346 213894567 386313972 106359916 996609414 699007082 895549926 11427897 743498033 657700263 471376106 240222279 240298986 391388820 648660198 354442915 446668966 707744455 493789625 220035124 518992346 829938601 312656334 825280033 720449142 315123223 577464059 80720720 590632925 431976891 575128381 358209402 605233422 306819809 642154684 270650099 569783439 355232403 765072832 723568337 387978891 454726006 970440927 78973399 966831722 886542574 237188166 624453471 11395237 7610761 434641476 136249011 62323095 165115564 174127339 361992636 394281344 362607389 126871807 423570695 710921835 23413951 971495630 357223987 777036496 976211448 649453988 253747963 89370108 374625476 4992920 248557198 312873152 964175117 632585991 932879598 443554843 193858465 961536990 634871004 792165330 680437329 736658639 604048208 122824446 227977336 379853731 275603924 572292105 904363137 875543998 817317464 570121164 726488501 964849652 425000537 495490496 310336929 950366785 137716035 428497599 390675627 695005553 885221214 589033410 748550235 425232262 874664685 109943648 135622195 601080580 140159364 251113147 66984193 533976621 305258663 774125102 245969129 753727458 670078518 44333436 826416016 511490036 9150206 331604475 340555975 732162442 381346838 985586394 725846546 276989661 854846823 367131564 835944833 548159934 845831111 988627574 675947042 21566936 78886017 180670281 377733657 106535888 97425235 291015299 323572908 111892801 744368463 167655683 485588661 410268960 857239072 943316497 539940758 529498160 618871885 341670675 848675597 436940709 455211078 891728544 893978937 913995504 762250552 986695835 684945129 239312969 960534192 603306706 100320042 938447494 289764771 596661728 30861390 886796821 246936728 339275399 371294242 890866352 811969930 10817390 505191575 743171118 191871766 760461728 435407253 221266043 731937459 261024506 662995832 901785086 883569736 569466413 252425578 441520459 719213324 813216366 731452821 746757693 185093241 912267698 217189750 992591912 92857928 445341051 518484825 234006796 130333018 767976476 439445661 145019540 643390985 73762326 599271510 449893673 683877718 559584715 447861095 483679117 457003811 736876112 959827323 453147311 490916883 306016825 596555139 738131432 32577249 400103823 752718529 118959507 852662880 961682625 549536895 589011830 576720465 265524480 405912764 999082686 874935171 777127034 941062350 654332321 12535670 99921700 296636586 418475320 169361971 94167580 20650506 769544830 182349669 538655347 890745015 787411322 281172255 144950922 491033385 373677367 690784133 838854505 733645359 160229321 178060347 811285947 133381708 557576997 143635781 982846688 452044877 646805811 598024223 584916077 152158022 471006127 646983937 77438540 491830345 943685281 653209751 541158816 276346795 111131584 866720353 67488982 223536686 512940165 972952571 288029875 838524859 282388874 218055725 507160403 992895449 653250755 487575432 175084026 391926355 343929871 597401354 69238092 91512227 395864836 470306062 65491487 793712315 793019431 979444620 9303244 698822402 641070656 822400619 905320420 998497912 377756295 73284163 69142938 873348090 186309438 924787911 630264313 624487028 902393438 653043961 60735709 202810166 535129411 170499916 630594242 198158003 833442346 703589038 394084249 628165432 968797914 978960905 409582595 572784657 543661565 233596985 836555579 62866295 72267166 280133039 8712189 420231121 913288868 531649509 988096774 912379034 113862395 95195728 882865398 449987840 990202597 911013747 12420066 687786836 767397402 119879895 802386263 73791834 961871279 275993541 536546880 443811047 628849147 846649543 928856980 622331095 180145904 261772050 201130683 223574821 574872316 338586841 319060520 598508637 110950833 111704336 981532517 511838423 726347844 440486845 31819922 186927249 625153066 15981237 659304656 287032344 971693721 483116260 483340750 122873683 489848604 636789899 1178854 206972001 738471083 697353063 744678882 633162397 428992203 497224180 42731375 727557691 309210193 461159698 719234196 133363382 714682048 657383057 1973691 326509535 390906541 735952299 923314970 841867993 141473883 869942194 451612949 886377013 64305590 550911582 841500835 677361773 834880376 234014427 899598893 194955673 809704384 892800357 600088677 8123071 456330005 692957805 297105661 129754141 644829621 358714399 569847132 281436408 752732883 439271164 399287529 137439562 283518528 70648106 620624479 47943749 102867061 407174835 200679932 93497830 456266325 846480275 453643336 617446727 145224159 952986883 881371604 882091012 333795560 995324017 620675983 128945704 104931801 112479850 219623001 870689017 390575435 613826248 49494640 816249254 531140551 585576182 892208334 514236623 193438464 790481341 699290176 755103514 284956727 468772939 302496193 235484327 263856803 407434328 31586105 237851508 207538967 756468921 584188230 638141555 358266966 905004927 123892402 963470152 873799457 580100508 819319865 362336769 43373692 686291886 783788572 893321866 930223896 495001529 874279562 81663923 140332317 865935969 713218321 95970107 985595841 62856532 405997977 506299812 582807072 108859985 469592095 841555757 359106596 652384667 93457142 916170658 926616795 719818320 65802714 929384848 750489769 946414227 102998574 283961929 938572500 458291337 437209088 757378702 976637741 306028996 210463625 524375106 416555849 454874922 480280846 912231350 517007760 904259309 834610770 734873280 87593927 950648401 146848124 892736340 386502052 566039776 528699200 366319603 51479915 263751195 872810931 38183548 858176042 796023179 86076516 966048119 718507038 150113408 45141012 700166993 193516912 359434991 272014498 695254156 56561731 887334120 836806242 744827210 843753803 752952391 553241740 453596264 715917219 517229388 366971066 238163658 182833313 830749424 833675067 324180693 106427305 656557595 793390158 26139620 813973015 195219734 584863666 29508154 767073409 736641744 855662624 6749944 890795184 213283818 271687470 299450130 498687793 488263122 586238472 871451082 626301210 991385976 641733043 617024930 549629835 549233047 145665321 307757920 490673162 898025900 55802765 101829324 292024736 371602179 735934175 667802383 361491416 833650312 669396958 632892778 704898334 133450047 503874790 250925186 773493962 533073561 598300717 831074636 527252551 396522711 645506481 348383482 662070064 266597485 726900822 889232203 31566266 138994612 740319184 627506596 129501239 257549970 193200393 299829970 843987307 624600071 894754619 278723202 806290715 585936720 652027110 886231147 977627475 65013995 534987342 327510733 725037059 344279731 590415595 54936896 527425228 591772251 271448816 974264523 443145883 304108955 54963238 636519962 891650733 266289600 428242064 207110132 902651901 434947760 314067470 745648630 296745224 17187782 994737289 116869211 926907655 557892750 429113202 60658452 58475320 168295823 573497219 843244177 555352254 899240046 837276448 964756485 294642521 335376770 852838252 805970800 572919111 121902530 485487355 407186021 658054924 768124114 837200537 332894929 35357328 623931652 718472035 844002114 866270915 782201062 670570127 222358342 365814020 224491780 463247533 587172063 448206290 348990537 314915024 956768192 55000364 196267752 695241019 240064806 495831290 436369749 627532490 402846081 312471878 767360229 499055564 515387071 198808860 38291650 472408380 468930264 50676105 456054579 862077100 27157515 5994286 100152476 503151409 938994834 492608934 816297328 52093019 866781676 7818627 662723709 640817206 528441156 93268038 426765461 123981226 971397515 480455675 153563828 125081874 999000917 848640275 75134166 75915013 348310822 119088869 260520124 798235234 778766841 270254139 170380531 267837573 598261114 439283345 30223954 73264789 180300542 682933223 241023559 855798239 555364343 918540028 838210954 487897671 126424543 404731959 400744822 31690099 772673491 72579316 134755469 875979844 289677418 238706814 658410663 994395334 192538535 582728937 14703675 630775088 386551313 921629518 297539582 268264902 454768169 520156555 648842444 826251841 465572076 978039070 998750544 650651557 649583762 380420248 4548770 721102724 909024022 689950504 928505736 415104013 167841186 521719031 35852700 674375538 983935389 481488314 49744097 783427550 274607906 601095470 472860540 668929380 625039899 970944616 205228716 318795948 163068571 28935177 462602304 364198204 710702356 876673863 865694378 17616156 346174609 421748980 590329116 799187545 24108347 244170751 179460650 593605277 836470091 873525692 635073919 291978336 792387257 716575640 608064259 235709694 536284271 626939549 549654185 76397820 762078280 484117646 19986284 336346615 351763400 828451904 838749519 650435990 910306829 783010165 33528612 697295738 112185860 156624610 847507473 63622550 389370365 582658638 318710439 916469672 239795518 406608150 54032055 884178763 728122588 870305490 571853580 539182754 174556731 349502864 221326132 221010219 785309187 862114039 207149511 323950853 919995015 775605834 861971658 262532659 434858783 154258056 314291913 754732951 66266276 894758131 542846308 452043769 157703895 638223487 658826272 920071150 830842608 348689024 655435478 392019143 781765768 398278832 846033992 18201933 733437014 451387058 643470113 453225712 995373862 292868587 59228441 595022889 35760731 430152059 726440222 97486695 220583442 445539939 557805006 536571406 682291536 42234598 964401576 985486334 864753245 842515709 293417918 813143995 389007778 429320076 880035040 790688129 707080149 584351773 245383305 971418676 100785154 321292834 273837528 965577574 341403717 428516609 231709209 940526823 233075547 999042557 571905045 945032972 251330374 491014304 641543511 986094180 452896053 33498314 910239488 293792621 491365289 838733031 237395266 169885157 924586345 550965521 690785939 286108481 605836794 185263137 735671388 129412782 789023461 263096619 74434059 608137640 123857966 400572398 946227706 856534047 967225503 702145889 972860003 902138339 400287322 928919521 568078491 538665541 176487661 841570663 851893265 756980464 488380075 359725982 989814462 856081624 633308137 34812090 770752475 151328210 279726565 93141409 370970378 449582925 23273053 629552459 658528982 597114703 837069643 682369829 594271541 209008595 328182679 706397671 472049742 64351886 647103801 229213603 676378093 517263366 683919398 205765009 146822948 466002295 367598817 373507860 303184008 952167010 720768254 928954271 517850556 667686374 303122810 319430584 938017467 131412480 815552012 426422216 171851935 185718437 601444688 463930083 158505225 238451245 621948954 785099224 738444946 843185515 879222149 323587714 172455707 929423599 536223645 730106606 707126578 478134918 91871646 191838218 294236286 222397787 919111170 247615387 604230122 253351983 907202742 766464156 375017396 608702458 457063437 26742963 497495349 112332233 268449675 772705592 168879432 100322091 898044348 358580659 149540343 67983662 738890194 747410920 536729171 438114454 256917587 649952531 151663304 888641190 250950593 246182071 756814283 877470717 440473209 308431971 876343005 211214155 44704189 371687369 757113334 760534426 650259511 184113599 410748983 202784051 5066481 629314955 490875115 270809365 634011568 975859969 172001089 929210646 589896851 517362533 573300136 822934949 361426008 54368678 971075138 435413935 322233398 772203100 281723536 331631902 858921802 591976740 523538708 90690451 277560361 405008659 988328892 191570414 143602139 60078947 606942355 269942292 404854829 641859608 478205322 778907839 179728973 892218048 452809197 66725707 692373668 638462239 553132640 565481615 927386386 315687511 890177618 402443594 426463575 906613562 646158008 211494904 399823808 641077188 891046513 493301875 658959034 693245556 534984716 633914699 478945408 893855328 627414681 350692275 452591597 396122077 922479530 571392177 797170232 105398798 72647211 614289560 834521025 458126758 672278449 634052685 768499087 192896294 407368039 125890588 4187740 371729652 517299546 698240960 883181456 843536556 890330705 759532454 477589192 338185994 645279345 873084254 755319508 987743269 454645651 613967341 624640058 14383175 834571781 274252211 227659369 442993260 957545124 911771442 565973397 668693315 331190571 178224358 400440861 708744641 467975915 159740075 39533669 300979908 560392703 267530563 300132773 276308675 499862722 550333687 220493029 214410407 148156120 780174687 705986379 910322179 524689232 846678373 788927128 12027082 190286043 136056053 245672289 872444325 911899332 143639192 586516959 259559203 674486023 680126482 888354788 199556446 556790837 696680933 543008456 7208216 177314728 352838981 346138141 335523943 790278333 936915077 159988636 257244862 716181047 46279666 862620847 448592118 346225081 459010588 182441366 173133115 280627675 165112913 67896814 66452641 360449044 123329155 859958610 766480270 419071554 958440723 712172890 249874031 115423550 25650171 463268310 717526392 922538406 22099357 877902626 306413621 593196354 943698254 91467227 813112322 684133867 207169665 440574945 446894781 374691922 278599850 552696785 216575363 648472712 49174585 715621107 209202714 37607992 812863264 873174317 535247541 115713421 234471892 817775197 541842777 795920054 995190637 611710979 148601281 745204766 845971223 976178137 845893052 535015853 875563044 697811897 763524870 583607113 505990143 295973102 778967611 965536675 142894425 510529961 742570611 231080268 629668660 312900323 136973355 348587529 436033615 960947323 788448951 73879947 394771457 263926172 177263999 343005486 805248981 443563114 5604742 37034406 909399068 514044865 662028833 549413936 438664210 682490866 237340944 410243660 693281441 559209214 15733818 311181077 293184556 715414522 929539798 138182899 357817377 781052996 178569197 145996496 584580344 682099724 444139961 387979000 479098297 464882359 867861003 325787719 58960575 802996183 865816752 199552035 534010534 209183856 638797323 986568541 413955973 401623790 174424093 73143868 387937228 306942461 331383932 270576673 221479037 576631986 762791472 648494705 512751422 875873273 770540260 166756235 80316672 611371383 49174240 372540643 652697454 108336553 262669275 991331756 921421521 186048965 847830630 280461119 572729195 841608890 212729448 457926075 626026894 217113414 662310754 59410352 333388128 456727321 338989632 532216186 389833191 856786453 71521096 764165986 191451559 633970174 79904930 393750159 172257620 406538019 71303696 431453096 625376520 24253307 360142836 538793522 467072519 576321631 709520159 532323768 257952737 808419137 969054566 515663871 857063477 231507590 437699482 241214822 452883313 339935270 156348844 538879039 916013798 917189124 450294132 331645751 642752773 32584938 886631834 294028363 44307532 306113196 938890605 932333490 348336725 249910505 578536428 490446186 344269793 930449861 932966552 582719694 711794708 861854151 320698356 438528216 489591545 934244521 958395337 24875451 476132964 61391299 766613988 531063089 58749338 715962616 553895719 85096440 590468380 205350582 411736615 750807530 399589629 728508551 842406200 938659525 310643887 744041869 3616008 140017657 742225344 342642488 998811953 95452761 829702563 867053183 238191841 191631381 592570881 422946299 275575134 584064242 186398573 991935524 828831854 916080645 262387290 325519621 646033838 280826905 523543059 561534619 324193713 815343541 964354089 805486924 96036795 465583878 389381604 834766269 794540422 758495152 346852136 880016087 568875105 503232630 544589938 995157293 750615231 37709949 221270676 353815425 684743893 141246177 313251048 349458129 652323505 77174870 309045621 701045280 581755793 561957765 841200156 651881704 2357745 725468707 917699114 47879461 86388625 492450726 743929058 111609111 317360350 848270509 453677294 970447180 969949341 653967199 798697878 862329129 701525648 748794087 553128686 924652175 280360102 315046897 90962764 879290008 80333736 412205121 950961559 620376030 66124863 454865878 898026503 187282045 102234283 893521769 87526323 50699970 184651129 908732997 96940792 197805374 725622491 159291221 252585564 276109392 969837130 337946202 786999288 893950874 298639759 875310159 877510839 261610303 429444330 868659099 223476189 201256822 281160768 306622498 446174503 402803785 182179973 797862794 196210824 491731377 631905739 315278913 291568765 719358607 174846885 631057455 173300887 386595858 561682775 183239901 439553633 595688764 933149573 389054695 983782267 86745271 137698550 559564029 819642918 593122403 551813836 789271078 278304487 36287129 535650978 211399391 206082646 306822799 510496596 656709992 483453462 169594792 967594044 298579155 624784660 572463732 88510963 266719066 903408743 203308344 619081511 117924652 988004377 24288482 135193236 373565793 207565910 206666056 790153646 183439702 261200171 521911767 915440002 820774341 802526450 162892870 90596433 96278359 534198688 511830740 585124016 521218712 663676130 103201076 492957676 706443309 588884424 355132321 785858539 248872481 328779545 241792503 851522436 484566767 969448270 742742617 749551035 718324537 243683915 682056236 847832541 227072674 545063975 252033324 491284012 238986718 241799599 917908384 175406609 179172818 710362029 462145595 33629043 709441679 533558448 319281316 519528245 764703404 870115389 330142313 94889526 503695786 148271689 141745956 19966145 100748684 335666236 833397479 984156381 5012922 455941392 486231047 10857679 810822996 966701607 996011773 783036157 586986061 251823446 65409714 649514243 53972238 641548843 931618978 141329381 826337872 63370991 388267767 301833496 72430190 477057663 690103107 596851738 970956333 405450203 189270835 70658036 767465372 22093533 991499769 909702172 166282555 572222005 803631527 54363592 589078626 219096223 582194103 172630468 920679142 900768054 831813247 405395413 587044137 204455802 824284174 371851632 171447833 32451732 272708071 118283385 999386732 433565614 389263804 412225012 836234462 135757005 197015988 247974845 692976668 930587222 699009587 260679245 256114567 987227616 943178257 342944172 188440850 945714497 78939195 97504232 763563297 304569905 159414837 963617298 499030103 332575106 463567214 439611223 918238977 449966109 990362016 668388674 965826489 90200301 476843599 472863465 901613093 237781635 304654767 787984838 88999902 289289410 103765733 8055591 550448224 76735913 398648341 837374464 260830033 200047601 189630200 551011201 132736198 778803313 207929915 773242898 252689047 425186704 603170319 404485743 709531370 763152183 511477737 486704534 249705497 482225340 711278957 128100655 602362567 334722 591925845 612059820 712520953 322901253 626346610 384447266 251416760 390250610 419226758 410041434 986379642 131754068 293507080 183654011 135750471 317262590 641960299 444934163 692057203 346177209 977756594 751035634 116597846 224661564 257334395 241077908 315711031 466132264 864376254 582392581 422208322 851792096 335797525 909415247 861335935 935545216 293933379 850700953 960183381 583589893 947157876 135843171 146051811 713453573 408020411 913840290 889548816 153360646 308396576 411510571 900032100 810272599 654305628 905123296 478594347 457228519 485633372 697730999 106667994 479742393 877138403 312577274 258663160 324321289 77811199 747381816 354466821 912373498 617922637 928697174 235281592 515226168 766814432 107634282 893355580 714611820 879177781 940771909 752550818 348908911 996564643 969403228 196817079 680199343 900253346 605543672 261441412 974449134 433015609 288255746 230647836 121901413 598389348 177336754 913370294 827642340 644601359 145325571 370583182 59433230 239854691 277508547 839505416 134477385 401451764 340091141 791351720 346182869 656952765 913437753 757038009 680665822 914935359 837645118 692574065 3562701 241076700 157816347 413704310 673970597 499307167 893638591 749574040 147343059 210380516 664285987 232974779 627590764 576902193 990885755 411893205 951691408 81550689 710249434 548530285 345333529 476084964 134566900 133870527 682028209 78876875 596617887 582503489 886779689 701424978 500484589 590053829 545390161 913196304 821234155 936552004 285968757 705867399 985630073 652910680 34452421 375903042 741039971 347758063 690295183 187416781 476190120 815841979 906140134 130475456 797258721 408346791 875879510 246861565 282934757 552166933 826450433 684095555 128936946 404094787 213571283 753620158 164648678 153567463 802769113 46188822 151667003 730577103 444198989 639844938 215081853 620909312 660038418 242182612 45681974 24559824 203455158 404232359 772589314 82167115 700724775 303185223 298117668 368366223 616365013 614852938 706925037 247042311 730926542 872356761 265055628 776244987 220122732 134282107 986641052 348094699 126240965 201293411 868104235 176272969 426570646 109451302 430073329 543767417 448269046 576390966 619097349 575981058 997619013 129136650 893061998 960606220 56307114 938446747 369728391 886065812 572451236 639536152 514654719 608562935 92171331 544584269 42976645 30888430 462493937 384688695 322274824 268490910 317986581 620171820 880319519 576094342 280560228 822259222 287942753 327553792 943933114 762672887 48298305 131105834 452634836 356834568 650504597 690344282 54766659 263430866 298276875 855190554 973325747 950258278 599024123 916089109 918941502 284452613 749633979 364756453 164341177 82530870 603484433 938503458 167873399 444122927 578967710 180525925 688569759 964913964 459668330 676469530 974176515 467289301 383289064 608332366 830675069 772093202 192251560 129142806 653327311 143308954 932136024 247371718 563606023 986543574 274976995 414716326 698624250 385426269 25807035 581078367 252322888 557644765 732172313 261623183 462860885 89430116 165822694 761145075 37580439 426651069 641199864 406274110 666554938 801699924 506526304 101834421 142943897 300466181 308874044 871320858 718798883 744141158 837144706 868563078 305527176 412129146 561600643 189881747 976948292 588288450 226199494 364619079 628985846 109811199 310005109 481504015 459843579 210563980 615542996 810862681 415502222 360846772 933809662 788415632 286193590 146045083 109751289 841114408 244291900 761634428 534485692 984064530 388529264 428759176 927240942 918899179 84454886 949699032 960096058 980740180 876515705 688001530 22716710 278605411 748149960 577777855 6129108 2861295 816394314 575891849 160024614 429343373 722004461 346251581 127939982 518989435 854773489 729229619 587208628 896259818 497109135 529832745 600996189 35852313 651069171 183563132 613447482 160241155 721869163 315047385 416936421 207511660 527616217 380965287 160621925 499864703 164192325 401726459 555599490 112776989 129493027 353648173 857880615 473236710 168182364 394249952 760815635 125773707 182064067 119451113 365531777 980343007 14753204 34628157 2650564 182832691 919545075 585474035 306906632 152515196 623878730 428275902 171462351 994002157 26105324 525155503 711429289 361556410 558510949 640716794 474048328 609399646 274596717 436515001 154488267 138597120 640046173 435613751 652862472 156118349 473142 177206983 537821815 82897927 6138764 583865138 327984145 52582729 972566879 743865934 421469392 370521685 497760179 488405314 939160153 35192761 290883259 420415822 716517561 875397067 466059286 73887743 148883220 303557380 480222293 352597795 52633294 464330879 231417787 568292850 906467899 116138295 156860118 706268744 897052237 40476940 880747244 152735952 279210984 715526724 309028614 690327540 35753726 703219848 960115978 260471521 463591584 748501796 571704125 114513009 682139296 530804649 878495711 298724417 710367722 722025018 339595923 91554230 615461124 670907371 223377998 405527759 836743583 697635981 833767974 793863662 608033075 858470168 582155594 219368333 112114313 361439902 857142444 535631349 681164582 202541324 86388678 808721947 147838179 355791788 877076987 281942937 293892226 290809340 663340482 286709014 430632157 250112057 209162866 757771150 671825396 457864291 425779939 247551660 194352128 365004725 961040078 426089108 521638378 768336861 846734728 514767414 349461325 845840772 275509973 827777444 865718089 117734048 940379070 206196973 503626183 614136374 527974874 440311369 312118285 631549697 542442348 871428364 638395643 932158807 192872751 68851105 204811969 123545628 602829949 585667210 416213324 249341544 806987635 260236976 185812421 115541290 907162671 873670488 507947210 698775274 707628019 777074007 412081250 268538396 813519822 676724006 295651574 737150068 580783688 717065939 596372162 106160395 363285311 301366694 335880837 878563650 773836037 390890246 991816687 290868459 556482974 715944284 110590695 762032403 250720583 187285010 849140915 909932422 314222145 490287726 647697904 997894985 339912647 826559174 969232016 760010907 837072009 882899984 34505927 331191845 630643177 940131646 320478086 799495852 992801867 890751711 117562661 215522094 929744756 863710824 338658167 332504610 334879446 890714537 540540845 806507257 782378327 850588537 326755879 521636526 64656046 224475996 384856012 476424952 850180947 941259644 281528318 675002971 587332530 6378297 755883630 366152814 324941870 56310902 705715511 259741186 371628766 878707144 484595820 62996892 276029788 582501674 804983618 290129846 673259535 670477436 423618185 233621296 440116148 733251707 393815195 52764346 85656377 448288966 280610468 232519882 952857816 411519677 111716058 540968489 260182877 871621212 212178793 679379615 115333571 705146869 193672529 187497169 171394825 854175231 626555219 970761804 129853249 990037481 530195282 515306846 998152858 789516911 385143547 401508697 574195179 75305763 776251947 830007700 522948227 810434841 952411491 571687187 696156065 862516720 189144625 821516293 59529445 892259111 458247973 252454928 440688378 648366114 169275811 951936460 37412973 969073140 840982346 109317728 133101038 330001832 63240076 886079263 846549725 108206728 549866198 947385346 700938650 55849909 256023145 626016092 885004330 493277419 871079334 561209472 326455719 853930871 600736570 540029312 369865106 37922364 294536356 454168468 294708342 17117673 579444565 812191642 486393334 561401543 75868175 230757555 669254916 93799779 7075160 116796796 514310720 675853067 555852192 787020149 272199531 315529155 546519236 56610097 965512078 863210616 822706257 89032474 325548301 500538949 249206203 972142875 849773451 681809152 208245587 711771546 716101131 887404812 790340281 268669849 134401914 290311097 144277731 611841673 462761432 226453297 766044145 391389155 21315343 901046015 329922190 535659293 360317452 167021141 248021269 728204295 130706705 965636387 185849325 958323022 724909907 56344363 428258390 536602431 872330397 648161811 607960361 359309577 929692713 465252947 695857159 950517619 726888338 644252446 877731541 465834074 576812243 719998776 395408237 238143280 816264645 709814535 591548167 328773858 890678602 429648159 259548947 22330844 528681412 405364207 873366058 390307154 571330835 22652873 841564889 47890939 179004255 976055696 912701776 787275688 411716509 709930286 215874390 440014327 101318853 687678957 31729289 554837808 368512870 488959266 344810312 516890848 701160978 764730897 520229263 500693273 274841099 802757786 700591232 566171926 725087515 989819688 624156641 606727659 975707662 761426173 346512886 23891576 302242603 505224200 416033461 906733004 687669310 163541890 976151856 365098121 467029285 277752914 144377478 423034601 782862923 831173741 853031270 765419996 344839726 289324039 267505129 108056248 107735244 266641282 403086961 804347076 525807025 447505210 881627544 875418739 585130632 356882224 368519793 916713051 481988739 668712120 596593020 742024511 22388880 78368248 309507969 397484371 431745172 706926403 855981979 161602750 680121387 255753176 613073139 576765819 410345190 633580143 728938205 890569898 216092687 291163602 291283599 403616455 984112860 898613316 397575730 772864772 437077544 842271215 252716406 599773390 231452074 507535402 523131903 24677386 425720861 938274992 964953556 763752572 365305157 101458779 693449204 964068395 35708170 609799137 618806455 486493551 889164962 650547605 353610994 491021499 972855175 879870128 994295228 619093160 862169371 648866524 107651804 491954244 789700261 651955476 798935290 853823467 530928117 507840599 732953312 603924512 796055079 8762891 547956657 769592912 573172396 437385045 439957896 380674837 486884443 30396080 451531312 662308285 742011275 336205519 846348233 604749542 134164405 111553952 873359306 458855478 662800741 787933475 749916178 111571490 813507777 966420027 219723390 56937112 356916137 510401766 170232213 366552005 402183765 4947698 685583272 414496641 442402793 571706626 117178235 784912993 65510483 62073229 738182246 308860469 816267826 875564948 788498819 935861748 841874784 291306121 462268085 181521096 368710500 643893310 890146890 749517343 725093321 818000296 255887684 247972448 336341002 49246875 380228559 772812722 214676984 195578340 915557349 666893900 778581092 668721319 890961600 425421463 496215616 440574156 957400663 480058490 329876728 272501813 182516506 630132865 758892147 610279964 557007309 164574422 294100927 728795724 989091332 468819375 226145336 292315222 515973117 795192490 760190018 229772048 325706502 900254927 139965358 910493251 61134771 414596342 466205705 160135182 521083589 41877994 184137596 504377450 419498009 362693437 944741661 614124948 675862445 986788452 582466926 880489660 314274949 445543565 215090720 819667197 392238870 857950843 795793139 423464684 78746268 996092152 126711386 451626680 889666134 73082370 283852343 748628677 747718203 606984761 658202098 30066212 948496741 729822698 538143779 565511764 849128386 185414224 387805227 761156499 899186104 416026514 239745788 214040210 814829638 426049005 811053887 11069914 116355135 585875953 94017094 487787026 986226637 757424005 376567374 2299736 664505068 342540642 730121919 399938636 805093222 275341518 946867067 440030986 26354704 692531559 378481192 786056310 851957551 193013160 933810760 463003679 179025346 857726842 780717081 779239542 752329919 699272463 240562627 573076879 432941420 501845155 323382935 26381968 3105561 194923930 166282583 630683303 165169161 650670565 282103423 997834361 307249115 38570428 272708870 195776372 597156940 891992764 877900920 116070435 880990700 107017042 414524310 881035897 997558928 565499286 186781972 10716811 919969931 655503290 810407449 176353201 234811717 525986995 222507286 808606420 471111200 240864557 42874864 492648349 438832892 881316103 453167276 281845987 599084655 505047912 877654440 630073421 823735848 135686631 924179955 504125647 77816161 898592060 183191179 959266691 482572633 20986221 914237332 77059022 516684323 994014983 823076709 602059705 747442431 841515030 949391787 230947756 502089372 499005011 517446617 843659244 710552542 89816595 964264964 211996172 176344939 700640766 710322684 17268448 414576269 425181632 134411896 478528437 853332546 523638003 330590428 579137227 13502523 656787272 370379814 773482097 928420502 636550248 777155402 9900429 251853199 367147082 592107320 872856402 359763567 474707344 7113935 492223524 791852123 304172172 303236855 887973870 915081128 143960185 174991263 615622825 432310492 141026957 304915155 666622424 711934151 242561708 729221584 805272355 984170116 734413374 23624214 450133310 693814762 411406865 420185793 479562761 928250134 368887768 959940542 177749398 63383539 166077864 740204908 430999039 288842209 928047785 23688494 369613001 345165703 586943336 325164761 512261242 226523735 945727197 907060772 3835306 154268165 573979442 719165648 186183145 709265422 163338603 168069160 373858687 543301606 589790540 866832048 182898253 829598074 881450132 975869830 951754688 909733058 347504603 214804590 49416245 78438920 984408562 89107253 983666969 568327753 366029136 657699565 841732075 869798054 49520159 319594218 364901337 372897013 248087358 995375989 580895585 143384770 138741001 639961946 710581474 935903003 349489432 386470496 872927728 893270065 270727299 841852401 125712857 218616319 502279211 655266717 98250892 731835534 348436279 261012344 386029641 343841628 551988363 728839391 748442510 278276511 126178517 741805443 207914345 723150406 421861981 949927201 178314520 25538097 293632074 269852560 590925516 928395391 998056760 464389151 839507527 151043333 568625375 217021943 305514239 77825299 908251040 39067972 880269664 332213167 958445611 459554075 449658383 546803187 684371024 871763086 944072117 432415306 506487332 14567945 933984906 782815152 303436502 510769304 949835293 237477675 332634270 766404912 414653076 696017404 832676809 643588766 907504158 355145937 633679400 441601359 244030784 967336064 369898016 209433449 367015897 314450607 788795954 187194644 505118537 691437236 231759413 197189624 539600299 343893939 926535061 444084304 860850506 583890198 331226201 110843008 544621391 550496751 166908446 949209743 640998885 262555092 362711625 441845069 716779440 282441972 544411082 49676602 43204807 159930243 789758223 324065345 786234152 193685185 683386103 403979987 336819637 152490575 787054360 65390741 16934075 179682106 855542797 82287866 526956803 323664089 154294591 175687112 355460979 444663343 250345244 843032912 830491048 639596261 538746981 168490085 772326238 931117707 689104936 341408437 54481489 528810548 883028231 515887963 624791253 67771306 598647930 905759927 617070704 424691609 426694625 591229900 74761584 95345107 604180784 454487072 155347361 738027019 39402417 99449288 47624649 872224864 780880998 186074948 902621484 954289063 341617765 356174192 499894920 909854596 944020368 705422359 752269644 943688648 825523776 576771768 808084206 229374784 151726304 318848036 981935336 707226185 187714736 648796977 530862815 526741987 828478712 859519917 490366946 399947100 893404194 213744599 552797857 771102478 959412404 879216089 804093347 63081684 177736985 763623822 42695325 295236760 175766034 171954204 777706361 841411981 402921340 711255324 598982809 188489243 990550294 892582508 315898322 320881513 97185919 909474779 163620195 567033540 845828930 995017642 979483674 914907809 668025783 345739638 809452727 610156734 852376704 748882209 585708982 945220827 611608339 47013413 827771207 378648334 566382522 612526343 437315858 121724989 588694011 393559784 437714498 788543559 44147544 934884726 92624578 806987660 425640127 936905224 829920057 733227227 60709450 774653104 545961973 370315834 996234856 345586878 453204397 501250360 498085490 125931798 686619756 90706382 654103409 589427969 66238283 461649194 696914950 48276101 373786134 505454411 917180052 454458835 951718738 478062219 688794865 564058570 298558484 364206695 351313971 964965275 323644499 790021005 57556868 925033828 299749081 235246522 813190016 236159774 818322507 502946162 30376034 337301146 698296795 305614441 5136992 897126140 867398007 93913939 593776879 618529226 750057770 117696276 684685393 921931912 162255381 396414787 207833042 188185062 660751938 339918527 128720483 764539831 359283182 218236057 14324325 633207008 441285429 940636320 539710267 679463882 312388379 39469828 867020593 565693766 406181049 512354576 982950227 495282276 632367196 212677345 902677428 170776779 7082997 463015492 437262900 104708074 919882195 174630183 205076634 362361609 799926218 943832574 883671400 227238588 816305705 860849841 862755808 972850686 500916714 31467567 312730345 476383225 355516144 930450354 743946737 312926684 8119099 859848755 542322137 948350952 837676177 660026929 337521474 674615294 466976133 855439006 385858411 87888066 432442541 886819874 811652483 872665294 733006746 521791918 159625597 414253354 927874651 973235349 419813307 815611468 283299466 741717618 170876452 55251704 236652330 68115759 19167664 397080000 256080972 742561056 522173202 831514433 956246465 132312289 829346592 68760930 335150607 193701021 474414880 501898458 802333563 150124297 855510235 986143562 238480255 37060292 389524653 955548871 352067441 385691565 235532314 918016773 513216500 967474682 386850803 867947855 814654079 421879111 702246610 554502131 317630172 575626542 945656365 838362565 405192074 552056317 732555078 588332786 252135196 887248419 699646170 489001415 179465382 574523218 116232639 644356054 615772765 83093823 893972924 869040938 575046749 916168080 318422904 755344157 360406615 224246720 35983112 959945866 814195904 694125999 539238416 874153480 515830492 86593379 464445610 98759975 83430771 300475953 566525636 65108683 974412504 39208801 687931104 808329999 326788243 905369839 274077538 74186650 940641206 74874595 873522715 203306962 369082168 857431900 802539887 316056714 29342078 792020465 514794636 174399633 314987990 852029927 985685078 680481186 118062950 949203907 720879823 836721008 397976644 464395672 385456080 898955644 369384181 366371825 901641158 993657268 52063318 905811425 742953359 978269562 215572933 46766043 3781648 104920737 753915210 150860196 370007380 42839448 375084212 819166050 691778914 577894568 705089718 721276094 361584906 567170493 989780424 764413549 106339458 677466129 302311417 998886634 251267573 596255955 863230984 131546697 411363928 666931958 807859045 617065513 683354225 13845085 535968082 29588650 118220717 228842894 916087900 365232380 309846481 401276663 172418339 389441754 352527600 387536129 401816611 938868345 118836591 578385109 92607743 578588546 128074633 583043651 722624242 680031666 724681965 795954019 509629934 781342454 310839238 250933588 75447909 135873436 940886996 691726346 217463140 902898586 102132732 301921574 990519064 11296154 916190110 634130325 921126643 361139567 425358368 858733212 251713997 962757732 213016344 311822728 241269521 415877117 975985246 200896029 225313268 733406771 392404541 621028931 92515648 962000996 138206767 76325196 778959022 12383879 873249645 362313385 878213358 326114893 544005980 403288741 264882181 527733715 929833163 196241149 215054765 195776922 163114426 643300594 316831149 392963372 592696835 559325116 893652015 553199515 787368571 673727384 686174399 363085327 887440340 780469949 301588465 347536377 482081873 730396780 500317608 804701557 561317827 814289349 304299259 762021797 842076311 720070502 492535317 918236371 370005927 159936525 908041446 916699208 175406591 914960969 980897121 966399833 2123711 860207644 353056095 341038290 934735446 615592534 906793045 322413897 650746855 495128219 95652405 916992674 265300046 708950564 527988475 457159598 149543236 569400117 528543350 26813178 986855897 830056906 98211146 154121767 599459560 288472253 376652047 685263583 243816194 250730504 744459872 293624489 849051222 321077248 174097313 211906988 607829667 13766870 442050169 496710320 161716031 625391393 788105292 490801411 894739671 541992405 193658908 608198705 985552096 283266331 597829395 554560717 16708127 669414346 792586033 627675910 91260715 563159290 975681502 177773849 659753493 851651998 857857896 836148036 372898942 159821916 763659736 904343444 704500083 436293931 711585383 613447642 667023177 940479689 140710280 682175658 221962834 853722542 705731616 110900717 945866353 46639178 764088418 253035543 778452051 979724739 450409803 392249629 647804548 796077041 573311437 247136592 422739140 518573433 489409541 567875790 363855316 75522660 970114827 169908063 781415175 33632156 152296033 722372375 207862261 573856430 440780972 454532752 238382070 526983388 626928704 574836730 121178629 55236877 716264514 190098428 369623233 197951601 512463297 139244315 571993152 70861958 934748719 226106154 107772007 587414736 192260860 140256117 437034221 383776943 595748296 596632807 417539911 135303790 816276354 393539355 318077732 705304185 367591231 918199352 696298703 878600841 340457239 830911060 845098718 741406448 136003704 180908344 493499216 572148843 212205408 246493351 476826510 872021816 95433379 702507390 528414640 524591992 160037331 214864922 357938732 952574414 554491688 419129242 381108856 494073456 560745263 564455204 846075310 764513996 44772702 591192875 880012232 993362216 565654291 512526633 716852341 51665376 101140779 864666178 183778131 877470721 390481472 333622637 487131734 698051502 353043015 65559572 836848448 921347250 10926764 726761146 775416603 62614966 632122930 320322966 381356242 462079518 479315201 359362323 622834240 69694300 135336381 185936 404637924 317330534 301386388 495065718 72362686 193970853 290661491 595924393 58732815 342558452 300186745 877860769 330272992 426971324 764906987 791915012 644041332 306207958 837522199 558829073 10188080 418267922 149672608 798457603 356684905 833745011 617565527 252112089 450587920 996100586 232147684 550713038 640968803 356339508 360774037 78208181 80847640 874979674 73054276 653443611 733317347 381401324 610533334 461311757 177293787 466124373 123315618 179444478 823338413 922376199 416598288 73374842 391823027 242928385 902485661 415491558 940405525 617507431 87939543 174552537 345740390 886822613 140324300 892945529 10514924 536717235 503394374 597494969 76904963 421816560 179899039 98072637 527068266 895586410 563477869 757570804 384229450 806214685 189585867 429067335 185834651 975811350 603123851 602005746 365537784 86903489 83611265 114259092 68771080 193028214 398071530 332801630 824836428 547155549 761047800 106343775 167372582 115633526 27945142 497352491 277675797 176721432 892175015 180802156 108226382 791123824 11816833 241713430 106671652 703221732 815703679 846763473 606976689 388817009 815482074 385161590 812873864 36364307 63970193 941445480 728300801 207394535 808392533 712278545 516627553 17984377 106725627 40203052 244593998 769561544 992089891 383068077 584691674 359593327 525054716 111986865 101525369 956811671 46062370 885056681 827042518 142720053 395268985 310367592 753553841 42132602 898206167 797797733 321623002 733110894 715217929 186122951 973767072 298764924 808788363 275290565 481332265 233980872 560037296 168095996 968160634 538686539 258757051 992299510 307321026 669333767 967123583 590611676 838596287 44159442 646580527 843897292 343255432 510195695 56339196 576673456 409311940 951937832 105743468 39826059 180002442 772641054 939407307 932471176 293006801 132607774 216030695 44945797 927574631 506130304 731381250 11439191 263472365 348756491 946340593 876754840 323076227 950980582 761242087 757893799 637098474 66603954 2590008 397776990 354520850 394926715 103665706 507479897 724169199 789827560 61227338 686720217 406074321 624369019 994461881 15449009 218262475 946425541 973772536 938281790 781859922 953406908 382948965 836317615 192089029 129118477 250333119 772522173 697295579 365933063 381186287 163912030 293012101 376372567 564256144 371772888 513032712 313036096 331813402 930418467 367958953 968020556 692921572 956790737 660332075 83548731 875456993 460221629 472551372 983186464 406686962 474820071 811516901 815048819 522950081 387142623 307385011 422772676 355983186 67323751 510686102 648671001 163207288 338937096 874606048 398728591 231336126 515242904 626236530 726370488 295742331 955469703 303670323 961432919 179445601 381608665 452763439 760159347 950370345 68678629 430915439 660751813 616970884 830414473 731440998 318133112 980964298 359767295 155475350 693996014 966394320 194107529 255481279 543017216 277498774 238967885 356208357 607340325 443470943 255968277 37075166 621423154 818230462 6546582 141099284 683779771 478342806 313886669 976437140 997662459 128807356 329731775 706220596 765829223 406845714 854568124 224523784 336202230 596034120 197521437 22511512 563811197 661698165 707944649 497720731 676451602 322511688 766549997 193042363 586148212 227006663 463312579 783477806 995691879 94959490 313590808 975154573 229279759 15363539 747202255 602022308 905210530 669580816 579133117 560649647 468847346 23363487 927044323 17554 587841463 251830167 551387207 968447515 29579425 324267754 255166204 867954051 864415944 386121920 160071379 866398624 708594741 559132341 985015722 692026451 94180031 594594245 815651890 431763562 246791068 70202027 739859514 730543881 246991522 286321674 310250702 805347231 993303982 636018858 461150040 165261633 301060173 25298255 365150978 630819041 935285212 476842348 725760590 339892921 557768145 11593946 368919062 887553203 486226966 370465728 667065933 508792504 495314243 375520073 411277362 134671114 53594524 916796714 440667722 109963645 917069774 550439236 1818644 841930899 287438751 542621388 613775981 10502318 794027395 908537476 454913906 645500484 617260108 570434118 835561776 614668617 197799800 76524911 759982031 821769623 150107793 991128393 442992157 89221531 932649851 304100279 444689515 183449834 486735892 960948555 802051263 659419822 654182250 793477114 858525101 94114553 316659683 141601603 78231761 678167833 951672211 540075467 753392393 172291239 19097334 696300053 52956731 384436451 284557241 737115114 591877495 100968913 477878352 34733183 264746350 540783997 550248358 514652337 148141583 468080224 573527042 344693871 493063371 914104568 289319774 172821728 447489239 449482507 631707682 664555904 174691357 773758612 722937691 121632208 161380273 492015114 776635506 99498441 734510439 777800657 598143038 596678244 206668670 507750552 816877997 488409838 126222312 610493882 960797068 406423239 273211237 59164118 416527624 69436041 813704083 521037951 82739140 400620623 501163858 479978275 931582006 345993700 842259048 461659460 865347745 745132 341490322 194104626 585265380 358198402 452145016 676646379 656590074 543727919 816949102 362932118 448939229 712466917 364973806 794043232 296465964 103267619 179091407 351842417 434521966 771020664 101232179 636176287 355239809 328362922 166541408 655385668 246934288 31830890 114563428 584180731 641021881 918137558 62876882 529803050 911616665 390859614 839671257 889018907 678457641 706605783 556238155 801276489 413603936 35615002 497700840 445290799 858021706 81981438 566865729 577797835 738761839 958176480 602388191 862283387 36199128 691515017 392079250 295161681 203862919 524811356 214855803 19730560 799408530 352972928 934322059 101750588 898515691 606676510 8802781 892342070 456873417 976328448 176298468 415239962 930456962 673398853 141318879 709734928 83377127 204718257 610460122 588070586 958788098 401839584 886188576 739523837 112567037 176437078 40373278 427329195 708636017 292187055 477352455 172653109 621957860 116711006 629448202 95172069 910294288 268887494 621499035 879893533 325100648 967805284 532374069 236383778 419802695 747645006 854100931 54509229 12782973 540375610 910270354 309200991 779912066 511764969 806740622 589383673 979136726 484646650 301153020 13804033 287756744 649617843 885208968 562595653 495812633 444607457 220418026 621145599 80269440 44275537 479635899 559165614 492051225 942478415 463913549 447958702 885239743 600477710 270045298 625173626 517138607 344300832 102687568 360117254 808485762 86078145 425057043 968016563 322250705 932885416 133333064 787499530 563317279 609578250 941517933 257871161 336439864 660429508 532009485 450393624 271881376 355140433 478474794 566952186 617598044 827164159 603837937 54299226 415528085 607117864 535320620 172926996 519696272 224871938 894571893 949208482 334709944 364134039 75111547 588405128 645823531 566226607 997082332 943495844 88939839 448751300 907010690 464189596 338736518 217282475 404206044 233961238 488069201 547442640 229286055 924582648 564543509 193372397 209354067 545223347 73738890 757521625 871825385 60471862 602181615 120629406 231132587 463567048 339938175 602262736 180965938 798615221 433928512 727535381 449206153 591648521 231493684 374473961 402543667 755175613 690084154 600513358 593815036 269228419 537828311 125293404 613796503 957107109 547702974 916684915 680419291 182689010 207731395 444323337 615389327 377077382 582179284 966921842 640985748 857580244 611463003 872523041 723178872 474850472 695257589 687785019 326559704 993569167 181776426 167280419 335625438 88185905 259284558 297980989 570506365 964264528 303535886 309241138 255129072 51340477 857014476 225509189 793948770 935684470 514720134 270660613 926165228 774063192 453453048 168182983 202911830 201077826 100012064 970846888 448027617 961721649 313229544 470022395 554266769 487726807 739563405 488131143 297307348 221970423 491903850 798604255 193555514 517972972 550870929 895767040 661351779 770607327 334248017 54418261 345562444 64313668 881828945 781648159 434657768 654413795 396510765 549850672 62449669 40586815 1064306 625737771 940922458 731809457 192152845 661608459 112948056 997835527 651991488 360363869 709987858 32364707 340624096 969607430 761566141 993615573 21490029 918034948 483196266 316719733 251619667 957258007 175488508 575618867 200108865 906564804 317001227 168313064 66157144 301843866 601147516 212295798 36500221 718186584 562055545 903319244 131866866 394158203 18435063 229896751 27107963 5693176 752303207 613090817 587933752 141662777 985583367 302361109 931478705 296750589 900259152 610700054 356717939 4198259 472494175 156075335 461159926 403738897 60051614 60040920 873223063 132469726 794693871 255787131 332542871 923994125 352525912 18139491 478390974 150703919 604433888 763473389 422965793 994812543 316523222 590750403 42407380 492808290 237399568 898428232 334315282 567512666 182649236 550534570 310156033 834104232 572477102 804867956 294116776 68578130 234616892 939120321 711071953 220957266 588977713 749493650 313282691 976049997 594650663 674717887 239089704 691323761 42113313 758263990 579197075 415658047 579860137 78014859 588716028 166207973 516521196 421697595 683514542 583935516 51537698 66846865 744250346 380614882 429837141 723772301 956765981 178658873 828638027 360528945 548528706 193385265 304413105 379111935 605301387 943264086 887374672 296742878 461134666 216432150 894574695 189652392 707025411 249841673 743168571 288959745 121429621 130279410 78295281 420458295 469921390 109111298 815790979 548637055 804673060 1226332 829437059 101225709 558233199 619262828 324336212 34245228 310223010 136636961 717557613 505436427 154178230 687325169 712304753 335896931 108044488 500294400 465170637 9897718 579109173 994959113 646210903 597764435 695362255 99748028 556785478 825819834 651385997 604843971 66840838 307378894 977946270 200609608 379911787 654662169 514464202 257797741 792377920 91157263 930090022 854727384 654319187 755035879 816280292 635828010 553125099 396483635 358083359 781055595 109858698 220848721 982881659 585270211 395714915 476909368 483009876 707683803 318883599 739856282 686470251 224896288 620380428 310208345 954752339 916321968 531452538 635808696 370867335 890123142 992571942 259154236 224390215 864753038 820119648 936605455 83584004 395001103 644886047 183888059 345513531 748728122 314781768 659103929 110702417 445717935 940444380 645590223 343002357 787015822 12683300 718210849 170419073 600092999 344320146 287492431 169546116 246403236 495968791 611187462 578387946 589894945 753775393 391371977 594493712 978948635 585875412 844929952 353947588 561487451 605960247 979671105 773705667 181730319 290531486 912686708 364669494 29799530 540808223 901429141 565341684 792956320 34780756 403830527 67656207 19625953 151255619 257178716 581362906 542590275 680352572 83702233 352904621 267298894 855138558 259937820 325022439 989203167 643985551 707382613 869611932 443293824 592436751 417659405 72323121 24760029 981073429 537287144 180435772 330441723 651398313 739458141 67981746 178733517 527501711 943371954 619996997 232729973 761551856 366861398 570637435 92378657 456987853 487133452 823624557 719072033 826996394 12623027 37686979 957280770 914000745 67139642 615056603 789820749 736461743 587181159 327559573 818171138 482283455 936209566 355679542 634025216 146804739 73849314 141483618 180761293 47507768 853299722 184354861 245740092 849622156 633287700 348624570 943728470 392511609 913313773 312821221 933959669 440154721 607380577 521258204 132127385 409786567 241522940 112068358 150011243 185312037 375949253 778385035 815974839 680877046 663916852 169531154 912969895 487547818 77459997 518929251 268305659 170459721 252426982 55759293 43273366 219533898 908903724 668093435 382290820 276846045 962785735 51434948 821530453 270363885 880508606 16955151 687446787 944828284 804442518 698820743 41521079 593389592 339129389 876467374 85319404 336404902 307637588 987375461 930936978 620734159 529606190 258542480 103963663 541211640 742334108 160366751 393034091 257328981 335156866 332069855 945886288 554799784 126922747 882470690 556633171 345458322 806784935 564042191 357158585 138923942 175832718 311045750 816198973 497738302 328781096 860518223 820551367 136650036 988647262 40883726 302687194 441658366 613679228 315880614 440810355 702496069 998785960 251276067 736853208 380236157 713162958 407228750 559006396 710958175 929492192 296268562 571572727 241947592 90288811 811649213 865733709 721837886 929124507 694331707 588862916 5490189 996270316 573461560 685974164 560188983 177595196 233976299 539735863 860268080 993230780 292875395 42730485 887614064 898197555 381196362 882489900 397600871 162830594 967793300 618954294 169744485 389562866 263082989 141672576 357740032 155042964 301423561 62951932 502526607 247627113 581390677 768980924 899356891 596746780 21997656 571718635 886151628 493781879 28931795 765804572 837481939 247208949 315505033 64162359 693870195 809971387 306031946 868268184 171307992 838347051 442734496 9571412 338792788 644756063 958532197 460279295 42691641 647511000 596550931 652480029 25701750 191828724 918937747 915732632 913204139 989520960 46171963 565048656 387097425 353419735 685195482 836742538 679127507 487694383 95120419 779872804 510704140 470860263 835546168 655727695 101770210 359315703 635329034 311647301 158998337 1226274 233026827 475169250 579964791 220404250 14704838 53315874 519652588 676633463 941775065 987700441 545532784 934219933 300573533 974673214 634883200 290212899 637322551 790917462 284225996 519242718 35835687 307256164 938524359 255943570 470608461 102442325 172933655 566146237 877786930 222999683 362440240 715208911 883592020 652976988 721497741 156843574 262163314 512618146 312964379 23826426 563931205 972016890 650754847 802964355 553836501 328568091 980646238 585736519 463185389 633011091 540349546 942201489 35000068 573351829 162692162 999786369 729010801 550496367 364731984 581968024 134178892 696879059 73667870 217074267 45493092 347747976 942260664 528846483 979200827 636494069 115469482 175021814 599175403 843400535 408941467 859994187 822203310 24135986 566025664 981076739 230346142 636506495 901495643 534213308 388144880 829689144 897818167 64353931 670325615 236335188 98936287 458121177 732934672 677019718 976060648 947389340 351150736 159508548 934917491 497533088 252747650 788337416 780950533 209106748 474585186 635606485 940354324 774716631 829241979 36760079 301658594 583425694 966478819 712849078 924945524 618055315 76747939 401520228 586902603 583081904 743072413 161080777 71630344 908168743 557388747 240916869 772334730 311607950 57736625 750052325 649509533 362968839 815935953 261067793 712915051