23797 1
935681099 484415569 434966319 783280074 256793232 602663448 19100462 983061149 283931279 952657455 48799891 865618567 138830225 476193959 328893518 979516651 416950264 245057715 11808543 166341031 621675793 457315259 323598284 195196147 581103606 616961844 464439582 385717928 5621747 449809919 274700759 140221263 90080414 466049177 621978632 77786461 136938748 86990829 794996515 915734073 511547797 64822773 731476746 141384250 209640359 864290814 203259241 875002189 751971833 104392930 765728190 940422413 775761219 666520307 799549427 594467154 329115090 30256252 738267179 761585242 509523137 291261210 205323955 721341775 647875625 454368678 246651351 440029355 219291839 356801257 145193585 9194413 168606528 726278399 368550144 480181356 60576803 107699416 402638078 612433592 997223755 19500543 795671050 853473500 362713210 652322878 824007674 729476857 60615114 114663866 894703598 239371420 999621179 109568309 6411485 608394428 982735028 65163010 657678767 724879365 413280819 258113728 968459846 777326581 696188200 474767090 305209029 965247141 123737429 454722603 563195324 658748977 325030543 71902548 967031442 202606670 775008785 959560041 869185694 623279780 911623845 535147389 545104769 840576880 734218477 772002257 995743901 626247963 930815109 449932992 777726327 978734768 90962326 839855668 455063615 938375719 107420603 345370780 124201745 788184486 767487204 412521460 388321318 227863608 538566800 880064045 522622627 83583566 697501661 572390715 823653751 348943609 886382864 445586307 546623805 260702995 237787852 959707958 735131454 197819662 485900529 58368742 987964808 863081558 444621056 534325417 709932808 160542368 407532012 776109475 762428545 354459504 475697847 839428497 124428918 701996441 845040733 966605205 721795429 138309141 164473755 139324070 900775663 471669730 330875239 907155072 283608625 840042495 222954702 906694984 476104558 198122004 270487514 102514097 269437743 503791736 677903546 47493945 657412257 332330057 932442649 395940392 184023964 64906904 492229299 17396574 779434140 920411957 523408224 546671947 103015779 628372688 561310899 362802518 424157233 103257481 20719552 236310636 746924126 752728419 138599195 855535193 969406046 685472036 132854493 182360205 947267233 75341303 900792182 38007361 316647205 740413545 155838265 499487360 854896251 433950321 871375827 271852730 171798299 796009815 108733970 85174215 319585279 557036622 694779828 17024174 255448960 145494331 991971018 8865858 486212234 120754625 445024135 83884317 500264447 702144809 113303501 504966011 811099138 157171410 938597353 459276897 302827804 468460833 40114919 64388552 18652026 617345171 238189899 206893475 80516142 98769549 733650518 799599534 624685838 406297229 735317851 308057159 145638497 91701365 713666624 875437693 94824125 575022488 989888407 686061314 23581333 113607786 355415267 37655980 555835593 104037585 691043589 307514140 195077808 436118628 917780648 667192193 698579442 738937695 355761226 502794621 160117688 947119638 785515595 257789660 149905826 210058140 977049715 865406571 344277768 219268698 178970381 280756771 998400705 104798041 662372683 998407108 48073259 784812658 624788224 479542008 10812013 121797214 24759464 964567147 628409536 724731337 862686321 973785677 166907441 136240191 765122596 497073971 994649838 200190052 366311812 509127298 255814241 721768861 408823614 856002058 8427329 280272612 738668906 519204425 897310283 781349046 921585486 359436273 610968362 898632608 71218826 230507909 19268111 578173381 739706327 797832754 723680753 424604492 260668905 95231007 733588441 493333889 385052902 501042425 843200238 72056809 248777312 544540838 189016026 931314118 59259180 699620188 330329504 519618381 524439849 366932770 85283124 555950938 607904252 579268842 164956521 223846986 448461146 422605459 199514533 84576009 6797704 598339430 47021035 6193008 124435953 932826822 520765470 129463966 778414784 833235677 842747823 332847294 485345414 955318948 488105291 597955968 309953151 356246237 991284951 671800296 609907184 895572543 377821903 971834224 973110888 230009853 845471198 361913255 383673847 132964084 484871327 643554154 752455115 990515763 462085079 900466701 824276690 267465674 333085201 624355655 2589908 545486602 503955017 903848374 967809437 335175732 452529020 397797661 17263383 767366644 833552247 881815318 755988574 277452139 694842641 171581240 350809469 942842451 931928089 936037348 653788713 110403038 454854847 474476574 367237207 11550799 771759726 407822550 951670114 642408465 149494035 11473110 879516013 984380944 682770276 263181372 86697095 737131673 420288766 81432468 597884143 384647943 684493382 837139741 180426076 370012907 304020080 584275330 66906852 242908967 324328064 122382915 203700666 770750703 495207822 411879826 139700078 854005597 200928482 457790206 897674091 405247742 217171381 341219593 246774479 582809957 529396657 851851099 707519637 875974581 614305712 318670727 170790890 788365322 758061606 745198842 810306276 458782258 12351013 243644618 756263864 741462993 835646003 643605121 529937818 284900660 515228297 585870760 1131422 895458825 46700139 565283841 564992236 314256485 835989029 848702984 281092203 789103629 382517858 825494114 920439362 653765206 67350360 57805395 461257547 985439523 404787475 112684775 911951735 966707623 639385986 221458630 789317561 851778255 208603533 173331259 853368853 933424633 70157540 968193505 944741343 154319725 24018835 740210860 669421899 521340372 998808387 373996419 634544392 929978467 940345707 829883975 362211143 668709778 344788517 135860819 522134722 81144781 840177574 952411318 388637044 542073929 18681761 909898627 926626391 429912922 705340724 400262309 651198786 788581761 168287313 480418976 515380393 126595470 44984203 848140736 76215396 828925107 77890812 448081401 668408555 555362256 22428664 407825607 931844082 689446626 995526232 460333132 183047609 848774468 644085272 884602101 672006640 806205404 116584755 725773554 787839300 74551495 275152792 829810442 316418701 160620491 280359979 369954319 825271454 477318022 853719754 549629847 510360562 373856898 968771114 651293543 780913542 368909649 387633544 196330934 532042299 140601687 14517047 372584501 118411962 389130393 935414149 148905019 92343371 6548439 432543295 245083296 69548908 883416987 537572383 792118299 225844902 16446293 263311463 14018739 839853166 755054025 767180690 332868073 676866823 103906611 912786051 240693103 631170195 801305019 703642059 386638980 228934420 88939341 489283889 800034977 981354321 143654332 380063924 139257551 457197752 959913776 314244204 970182840 940770192 391652205 880584893 86597811 456814280 503005430 724558721 6683598 671828740 399330039 360383100 340720143 770092071 494317890 794457050 455814729 923136428 144216747 216467451 369153975 910774829 424316662 209722319 945399984 11101830 935527785 951174802 284079538 178139148 226163874 636384381 752099209 628607210 938258164 137669268 693170942 945350753 924931821 615942868 602018860 13553590 722397478 282780863 963536935 236774435 977797316 323018039 92352214 540304888 370258469 703541339 623503521 609625809 548430467 996931382 331925978 257871305 902837512 701804028 431391897 543651319 348215427 86471803 959287477 887867624 735175054 941287545 6971761 745575009 334334929 53952097 284156960 595418069 686850914 270386829 741472423 314483071 874721280 309939475 390833820 668975759 296681145 83437806 211951138 133789332 708289312 422314253 827737654 180483844 548585436 729435279 521968248 749829540 284395803 451343687 739203197 198974721 682398635 970636012 30068126 698747104 287879212 77169315 429831285 618706912 976403291 779589727 31377762 319454356 265206310 613935271 157159782 899594375 47537547 778515721 405971211 874355386 434632851 631447454 836111714 772385041 830120387 571166180 611394063 455024680 87254392 271093879 866797610 71390462 31175802 599330767 213839037 289737550 678925640 827491798 606080963 106777389 18368208 997256073 633133423 875980757 239869177 237640207 805182052 691432579 679453800 851069268 108868120 243681851 819618101 123790072 884113813 466250051 906355270 747776789 85068615 168232921 987822094 695091297 87739564 380448883 355905656 700035232 676852520 572839871 444816142 233349801 550914443 560177846 803329964 751400293 793460430 825627802 976204868 256496498 682210591 583021994 228603538 970008498 555596390 429571723 844405474 312979561 731718744 969463300 371085693 342922384 759637561 188211 685440685 692461302 197333672 924287949 23222697 656608659 696557212 336857969 575542365 261952782 190488424 732143589 24137664 916943105 648147307 123945590 51210491 95392318 13064865 330435859 999923039 925562705 747409000 239912574 463787133 353709058 234522053 846335484 859299920 625301561 389374594 370687506 387121472 683308066 101429990 241583937 701205596 778983063 658715023 269475992 89044176 896221629 51027508 23402780 83087829 964326333 871675555 155691212 497284125 646329472 653071380 417715114 446760795 466888573 355819920 919442482 538279187 813782944 555550957 905598227 451136496 880316743 462318858 439468067 194453576 279876524 826078878 317526549 860341457 92391517 754192984 753271709 241499711 43513056 452175865 277603392 247993205 642077505 424437230 848763729 971129782 752590971 568869310 833079634 412131341 137298283 492509465 907108539 522187241 329794085 450380876 923604972 813866023 709534807 779741756 123741272 703148541 827868539 773501926 167175018 111044246 809705818 299995446 430084032 50477528 431075737 505783981 705486600 752798109 224196272 469232684 806869282 532056912 416753132 45558762 134215436 369390856 574472285 294740964 989462133 290320299 882565650 736076479 195163014 699459177 377271626 925657370 475012244 612163909 364940481 246790691 48548264 927298338 62575715 814385069 603270792 872955815 483386600 759467129 240195573 52865370 326738288 285635868 241283323 204133983 701990018 517522405 372580766 386773917 215838025 992467753 489916258 207029076 880232198 65608675 80889089 602342306 27504570 371531727 664763687 319022095 744943389 446375524 88216690 963589588 989517445 500311594 304472457 373571487 379390471 171727302 426620753 994031090 276375973 654932028 187258285 298984846 954565179 513867274 728523372 263367082 97454309 533772362 131479610 982304891 50114940 80069110 506587863 801636314 790200911 436292246 482631719 40176745 91300768 465250265 578710402 530337440 441379715 209287420 798433665 970467931 812907508 368022084 585504760 412191069 564598104 48029196 151462912 232228591 211088491 584665587 81436289 108145861 442739684 852102809 135348930 51795237 128476048 728693488 551525086 425472573 432574055 869247701 518184488 802150548 125468317 562450427 941540451 932791871 535374613 78086970 411435878 584986100 705979719 370634040 893237980 630135255 758491177 161084152 311353877 289041836 711680588 823375091 194595571 562549651 205728294 172158426 472871982 406413090 493556000 624743322 229910562 747063134 519838984 472210994 685908873 552702461 841355301 757288676 159271792 644515434 336245392 41854341 558530205 689402469 381988999 56914578 255910703 264562660 991820071 256378788 253427935 61120516 67471615 220143043 973207500 244842313 447110438 636846008 514402370 517253882 504536515 962730516 137259262 190968272 540432110 895482802 357734655 700563200 746570432 952358312 871129980 524608970 961167915 780781741 74817106 294525937 141880029 250193440 115103451 487490789 699418041 625118256 689910875 207991665 90854893 22953643 768651940 914478970 684201720 123916984 926665888 19362784 629288251 431352589 818741507 262865542 980021161 710076133 161849188 414617553 797066241 434989208 363594064 326438631 510120489 223170641 873486245 623336348 165849871 953425554 85739375 958613882 258699171 183547069 711560883 301806894 403839965 368538359 107072219 233755515 5165193 588044482 247653597 7003967 812670922 163181833 575342227 825198304 928517217 539384591 959929545 429946665 928410754 634537215 2229176 771408447 592905994 520684252 9768930 42701560 221624039 207904378 520811520 934359007 707103869 460286721 976407961 245597721 57304389 830721327 179153604 377160341 805668989 287887509 863405658 169679549 881320957 51697528 725337000 619074713 567051999 693395330 768494 628029833 326818422 847240808 912254809 75379823 681360725 668764827 24735616 669248090 837976986 68219910 271134235 62187977 508830187 785550873 431642540 710521830 940944405 22557765 939814004 54371094 399348413 571045307 594607594 559168344 561672005 293427440 822837040 367939349 389671260 801104709 821443183 890503774 45732070 137881028 517343794 830573404 341501323 879504642 979383371 821489977 547819232 371091902 817845358 273661477 225192142 457178260 42005116 861178998 770509239 198980373 352264198 344262403 164018820 700573176 927890276 345268105 989477635 964074773 366908955 132988680 106940125 504553511 948361284 283543260 664162134 810330383 191711855 146741356 207152569 397192944 542217743 14616417 147409690 484588871 122764275 225144391 876657626 712216475 635063741 443669829 924414464 710697261 648354457 667901314 995160130 848027760 690840123 63203040 930083443 894708384 815152942 416033101 75755888 947212299 249663610 165903242 500433020 781888661 618347042 329601525 429311209 960500892 305618647 462651302 501917014 833646127 684464359 3672943 389708677 655544845 647146882 16826129 181997849 267357362 990298556 330744248 608111433 322042155 373349457 202357591 233592884 970257796 293027960 460119439 212730843 584159321 111363868 837429874 970303028 827145535 859913886 116436641 36287365 119730614 233610375 694739136 333695264 417637769 820505816 748177077 757724273 108157926 76880837 736018338 168606068 912263543 128686363 345441988 183533808 238181529 896901452 621019081 399286757 492367986 751679036 886699768 303380770 625956438 710246854 936652854 110944452 236253695 177526014 620111000 220802064 254775114 892708347 45076810 589140466 392047942 424730308 878919867 991714675 452213909 649826081 548363025 882099917 437699346 283574440 564022626 822612587 494629627 767780936 543455866 979501983 435460131 202791152 762217929 220102756 748747184 519973132 706796447 355128407 986574863 979351447 689885933 984084135 94966635 815931100 220464387 827344699 821688935 388468622 701454104 330901954 578087530 661937566 885875954 957344801 704734315 788086237 151468346 49359294 478800347 475582177 42650610 346402924 608996376 447485170 130418521 553703913 545049319 372421026 956824954 53177882 105178732 946152193 395181094 569784530 146408222 533821194 462700598 886653557 671076943 380238062 189792233 919354298 731376238 706062537 698522810 410898364 139624 525290977 61739253 5252990 190617252 483782293 648737031 931643919 750661108 312795445 345795312 32422158 376606125 947130018 537880923 1825170 669587093 406056728 357568042 110223025 170273440 813527293 655532639 25365964 16635161 294327825 89564138 137305286 963443227 872682013 415197666 496689610 532306098 500314554 659171375 579599232 742952370 214244868 640493423 388372862 157388553 181676204 128851085 799050947 440174594 745058687 638464930 857297485 359337190 945961395 42725150 966515262 589212695 717688357 500859297 436193209 994025807 370845831 242505383 292043700 536201571 467278555 23032019 735664333 577163281 144933261 270026325 435355473 882968818 506089187 606617650 356431717 445114368 392027776 160233456 326012457 290790341 615204228 394047272 537782315 308121049 856604464 8801370 31535101 470226364 528076403 489452865 548758091 592703743 44229244 406167892 491023172 639068140 411323280 319178310 692566348 884130047 165245824 47585832 436406633 176381228 636829787 250934176 182919946 681964019 795372346 556029213 40797734 25909531 767418537 314253399 973522023 758809664 519862631 682077179 401457834 527702127 847873402 871872858 429506219 781618540 568498447 501605809 85588137 569107503 73094064 861043853 532436651 144934800 401030642 283447563 370435692 245691424 137234767 800607980 7642860 225369542 482797117 532550452 107060569 229562468 580262391 722365916 812188987 282234031 660458060 973847208 134894552 150949221 809252389 194512957 856318344 748047329 437380750 739857383 693038170 673851261 754189692 350717794 731173414 282793962 140019784 719649294 810779078 288021616 415995846 188537500 433286364 53156942 692887631 822110394 832337164 668264134 709462938 479868268 647732039 122329327 400108201 545934237 141534801 57332821 615248868 532603982 862364216 38767537 452027570 786719633 226725254 520932615 201738492 210428188 111106064 53708737 313718873 912664580 193668805 716964692 883154526 546622204 194227950 372108646 557604783 255969259 701801481 245298217 356882387 495312148 111496286 917378327 957747880 38210671 938014202 975031818 920936103 834764592 293763602 668692313 232024110 306241360 398801446 309197318 413188623 287921347 630306192 43544000 949652014 652073644 685712650 691152641 143582019 242522718 245628065 61188579 542338694 526198322 177912392 767087408 23626158 542917809 235365815 374274789 336541533 378886575 454677949 641113477 548577559 98784240 44190061 5702897 339157689 739997007 938070287 165035091 132863445 45037339 644556769 205871383 642556842 171992334 492603151 290619360 725755680 115351420 99236289 861746721 34994585 224191696 675635836 872476983 521783889 366187945 246265141 449094711 688749634 159429740 494837827 18104452 48970019 466991520 69798138 146197969 806682878 965320656 139304473 352560306 811069028 418114812 750437310 338971140 729244930 814669610 981358816 692156250 854424855 389861394 686828174 477556403 777409272 720722260 606530179 860615696 822185400 681196684 636552413 860068022 237181870 446663551 53064060 362094962 450752372 96849650 901689547 414189621 153100585 535308343 481646967 758896648 712378859 279281848 425198062 368979121 890301158 157372093 252060491 336906087 337556927 227819329 45077583 546128649 122760812 695729403 535384936 208995061 343901833 258746565 848127537 729578287 661706611 47488280 464085245 779965443 164759139 513903243 976129586 507938681 419535317 412629905 625956737 742653475 991560254 494837436 955792493 148619037 222728217 715952121 981385696 313332491 282195590 916774895 397309588 107539209 705544020 308059393 169108796 55539823 82780294 349483900 192697053 643093258 156202908 710878282 358182046 700615700 886852253 90057753 234721168 49180533 880332186 587223010 919184795 204245878 183954531 253262171 921097106 708346357 640972202 809423780 541313152 855269038 953069901 427595056 978469800 79814738 511454003 168229042 124763404 901537169 351730920 968515285 580836173 135538696 194057412 401987702 216535896 227466336 545756251 808373175 797223470 424291443 635858395 762225042 168340153 248735344 836123133 583320850 251934448 782642135 701152126 980501716 255116210 227859321 812903845 237661979 977898816 83032690 99489843 259488089 893772421 688865376 144774304 188613657 725866604 48007215 259795596 113349385 112273473 714615736 856117600 609593829 650723169 483465176 92642331 28899548 219053536 224773829 855246752 913591757 967656843 139307664 774966347 660845650 643276535 172867338 590219971 429720321 934248042 432353299 2458908 617420850 879545047 698201200 93515346 449469943 423605919 97833840 761323804 199251955 375812636 628217193 9900672 869091370 191823838 765547653 217604877 441916985 977889885 551949809 200375166 356642661 528242210 295347529 299598854 635810131 828059331 85158730 305799104 630650463 471136358 717428893 560493150 140326981 784175185 175055625 361479324 208502364 350830316 769022670 308693412 214436965 591759508 369724021 989806014 748459444 645490325 393028280 27900833 546968455 568464086 355813188 970674248 607251681 372459426 226142874 823191893 791857969 460906167 372736132 505009030 343305778 642428898 238932977 342442964 510755866 754020532 343592867 813270598 972774581 417758874 854347781 768153609 726995335 438154914 485001760 688438770 151020624 786989345 929984849 162598924 302674261 472391512 959307749 601901168 349142533 593705483 479161780 718467104 848793412 722051254 426183110 428818840 786831430 52292517 403488063 890139189 846227034 644161158 158513833 583558426 373811804 485593223 584916148 260845989 10929567 636290333 82151891 737760938 720487337 466041773 532269574 191685073 351592659 683883210 562101699 264241381 27308947 595621505 385081547 995445113 409661883 595994978 678173616 971183126 469788901 694996153 28049750 565398765 278197242 225798299 94596064 708334113 561450376 311995157 802127007 275974690 696819355 567962246 372012261 946954227 292564911 811246650 616114158 411252602 791167301 385901834 535167706 325035782 324609219 715957927 912275625 232996993 421551451 847638995 242906708 397644967 670655199 552663303 992958371 681212812 959570203 586623700 435671994 611800102 735297605 492325695 158572669 624807160 214167030 853942488 408972103 253387353 145294119 922126001 188556948 449124547 461535246 604161052 778134581 501150220 60198091 68518434 657636120 90045995 689926555 90858295 52382544 819717431 434352312 131836541 99036597 607513081 360999022 137045061 220694239 961326363 301026198 409377254 660178575 201442689 653929408 184870353 105812979 392213776 743389752 254798553 31312400 887753945 133587496 537357088 464368536 388692927 962932148 222957821 394963404 833468136 629782130 397308292 311594841 241641638 388478510 567281198 910358922 317986197 455209790 579431557 639894083 283779115 365595794 620753302 805315180 152934939 21254072 870596058 712745048 919788573 951328487 88171406 447851637 225391517 307500247 990660671 790210329 13064492 749917003 772166868 776375151 41645336 262327820 325522540 801722907 250178147 670765623 125367984 858043847 911147518 70725305 464285483 191082000 568580114 929316676 185003719 467945970 737687240 50242919 112129071 789757990 675584389 257539461 750135725 797025693 222713731 194001882 567880087 295534027 715850970 911143532 953630859 140058974 534251013 331262066 569197927 595975413 118752835 710209682 47970269 529586117 998368712 636491758 437075548 850879558 297512443 719574010 837705263 933752197 486289030 272317370 91439691 648828949 680898464 476308979 714634277 362918893 923150319 42772708 261604064 367357 316720478 544206596 648941873 960968112 444972109 801679211 507501427 74819106 771051226 930200327 973056457 199256807 863556489 546991792 287748707 150176315 299701098 195913890 269301232 933571051 884405862 199400605 856574334 106021116 871700254 16114430 662505407 677465796 167771857 831646780 209361558 784467525 253514024 510134642 747050990 264661383 935923205 200342994 927656209 394051778 859946464 143820859 107587758 455057366 820020762 538044428 205349245 564928755 314949667 981973459 398336281 887418606 327201313 726650260 310372345 848113134 281532963 802228279 897477148 141843209 482728968 47123393 532828955 786987083 114920649 87837768 936699473 446476281 995191205 302406179 151858729 792513961 456252809 38039046 374162029 220868151 400703427 850867725 495602021 757098754 437660576 623870716 655450509 547532826 298575625 810191879 687671920 814351203 361220964 595869531 215848741 321994008 27090574 201204067 149901800 920482465 669868202 119809408 483671450 319105747 622590239 710384949 629014254 545007953 503643891 157867959 739794461 264962983 825481752 675508127 513383233 582792605 641541185 931251425 751577162 523181210 319088772 117727569 311615193 686632385 660725955 817235252 373846819 980628288 526232142 577792881 328544204 93371972 133015550 246108861 13555141 788046827 877750033 777456585 2744514 424045231 859214208 947885693 126173389 954982236 124180001 21569898 437589736 556532956 669135958 980475768 483622613 857019069 225202449 478040443 142298737 705488573 153765502 175398046 409618552 312416741 332881434 831607930 157655002 145328847 476356872 449470902 767256839 242974714 184226987 187160243 200479402 621772013 994568308 301354057 310791453 150423299 488411145 346066873 824871544 891200113 765292307 132408901 55984594 52569471 35289432 652903406 128642660 594310837 104539546 65043172 388671274 68585600 470629851 657012335 67974986 981009085 804512877 258488636 259986168 649133744 37798043 901842982 421860890 530160158 548415746 703380458 791422728 453919514 860622424 583393960 95451650 526747325 506196805 856057648 84057312 538245125 474823740 855929217 655598006 551951256 104943054 230038451 815068753 503807339 568354905 834556602 695169147 890835544 9835926 808451269 854457080 228975213 412238115 449060458 661980609 542803262 439361322 600637781 466928013 124307400 145166022 59277564 54982693 258705172 108946600 461521540 87139660 609702881 321340017 17515411 556531951 510109811 213487419 751849809 10940674 512698305 950924604 601193805 908134563 52594175 228476028 499025548 113820558 417238241 156188241 373206795 982844160 954420211 830757346 420197679 569511384 645606273 139097069 542964360 363955089 348928323 39428515 427341650 326910661 385434292 458731617 688509693 331281290 202695172 799894521 268191371 141907088 422175712 652730880 539688869 668987587 498590734 470960794 856912943 903583781 287205202 37987347 239488519 231958784 467673824 448880568 594758144 545195659 925518396 30383468 409822670 464356719 119730524 614532528 148531500 888854126 569326565 423328554 507242983 398017232 984101359 85549693 556407224 729820217 991813403 708179027 691330790 35457255 820870445 24627600 168110363 401972135 442225500 372378892 53138618 840121018 997301873 522068391 712694428 86940063 233844387 195191842 715452654 353316642 700580465 924054285 807032997 37975225 508486787 415359807 327329431 372829889 366570561 453751166 647486807 318603449 229067198 144980625 315948003 562227412 849313460 645554112 377432998 651250763 941295891 248894361 473584129 975528001 234178372 432741893 252958479 343879614 726408353 269162588 314410241 493793898 155145561 515016584 749006883 774506458 230008393 924804478 465692917 264899115 310282682 327731300 740184974 444090069 645687637 413315024 994284005 551148409 704781960 891274491 327141738 782333060 294706451 597732742 189516560 966220224 42930700 610671856 229601509 119925572 429806714 150939404 887170737 339191940 472020473 375794210 647044800 649242270 584799249 248632610 298427353 191547990 276851282 259104706 535136130 531150238 904896056 183002510 653494832 223734905 498886106 428482363 338350000 425059000 328426861 321483502 392282492 530921729 515648493 682969204 259354014 284279572 586912271 353070892 351841630 304602416 206505751 878323141 259863115 292238405 320025385 377679623 271954688 529547916 380276580 751987440 116162915 291847319 347025466 908465124 116823101 130938367 490576524 52422953 887307489 164633895 883866388 887353199 225997004 580745501 125541224 807138017 442872855 380627223 963310632 663738886 230151658 340551772 719757822 511424703 188192959 359100669 391511700 361224887 645452734 254759353 696256042 750105830 442762829 29069174 770468873 835963293 738984629 431382591 286838523 697197077 94270858 496812010 785929941 428659384 61471962 168377836 833735392 667413266 702400324 652820528 598925920 927336730 465760674 424131805 327224452 8695346 854448934 513273902 726001479 923448775 248143224 752622948 838885723 801063946 578674162 998103446 647790483 644096102 390919999 544356534 98654394 533053897 878674790 368427603 215582447 511730397 760011058 529889497 844314179 701270133 244604245 355281543 418761952 729135604 862230456 845276251 136930384 966516899 497370355 897633184 543917582 376656373 748183569 67139318 861182554 571973881 405171999 465233144 232544821 111725475 806202782 108942055 560803347 202028931 65749658 499811092 170765710 94108104 436332210 679730361 347075138 568976252 51053603 984867036 55674837 714246906 895777068 271533201 936637355 77054066 11364753 647597907 264766164 812366926 598284512 173574711 508683023 700104179 834529826 695172930 10057777 827144467 879722852 115497230 665150345 841468984 418739902 361590748 623102279 781935562 862673378 149764668 11953045 475982897 759768320 763399271 628326914 975316038 980208130 643199863 764878777 589838914 112536161 385516146 513196266 998080848 765344039 852783539 160702023 863843499 307584541 568849711 435067365 906124270 419278183 900045593 74067080 619878653 793639445 854942510 401265482 20660313 380509511 826879440 719353508 155506686 390472321 923084937 284542844 573110451 513916813 296126354 509542134 941190371 397376043 402716783 426220018 671317906 213589722 528087518 891585776 542416666 930465394 556463617 592319202 480655695 935484628 548522781 288970564 2302279 942232135 437208187 496141393 997973909 82731171 255197117 798673546 951987461 208885568 901338564 405191434 978184571 625163536 143114571 559514133 751324294 749510201 154367506 726197960 686884026 400959615 303142233 363018179 752737435 223665097 711942247 772839211 488927764 281658217 796018628 49125668 689630847 518863636 429516859 425689346 989732216 896320840 958594314 298774513 249043270 864563917 444331422 718984744 995708881 904821184 175439701 877615529 430015524 438329305 805417683 707304390 471624576 364734815 902683235 263592112 53099228 105810534 122281301 601371969 432775083 952903260 351539319 588273716 625168188 422851642 419927785 53593085 988796925 491736967 912836010 889682541 598039319 240047349 305868042 776823429 597588643 148386786 744728447 743560543 394002657 801022340 887933638 644902495 417232149 680954424 180645794 653158081 82808841 369391185 384368326 987724572 706586352 201590725 981533417 918513263 543351128 803349407 576706632 778238632 821760451 232904542 463911868 506664922 468042326 41308524 417132541 67523701 792296476 234258400 706619360 807128449 174980042 165729403 630816832 7642744 705519780 998748989 181664779 619735603 465234699 77475301 167266607 62439453 525055073 625276154 323887091 457124604 595448305 295931857 431383921 898582079 354611678 441893011 945795928 350190401 858604639 295536015 448126899 474719355 497690121 594110448 982386887 166417527 32875748 139518193 641138188 12411734 350058121 71069512 750113207 548115393 641155726 804554236 631513943 827281424 977618742 677625904 155319657 632209107 839652242 813113992 436765742 448160677 188387325 332217641 205504521 494954399 473550219 157599553 623023181 177485972 602843511 611740627 310710243 929414788 713625627 833533236 912552250 127922705 329132291 637007827 645865951 829057870 878823461 114468273 619231249 732796483 149479080 321068427 936845671 212787399 189623167 703443264 678420095 882584945 324805117 739787197 704467702 966288871 558220017 767261159 496132608 163031532 427667678 981886176 241478386 189911083 818971955 14230308 10363789 822736771 276293936 982232907 245354654 877741335 832187071 466846014 573532352 188096086 207552021 268142213 845008182 977312789 433984153 455549123 159837195 714582368 936120734 767906793 221074711 173341277 39139262 53406108 547702011 516161952 662528798 268703606 95860730 153211552 351453689 624797476 185775376 92330996 94371898 171329797 442262556 14101028 912384727 887127161 103118771 558327064 984222242 564028421 833268720 484072171 291333829 286851585 561544176 442666959 994243633 870863708 308474801 356353601 238562294 567595093 293731006 247639549 707896792 155000040 940674713 161149093 338831885 922429304 383350008 228397259 627168242 119764886 628910264 285580781 871283601 543464468 885558800 693741465 490736715 206481788 186851128 161696674 929892593 957395426 94706450 173809251 80552206 650666610 898469794 234778721 62534556 962931738 731461147 991407931 411265141 314295451 470245494 827227764 624997758 977943 370120904 442184661 778499636 591099582 536167305 477480131 126804631 180921142 748974355 890988301 626572283 501441950 526347225 980976893 496007084 772174452 833538891 854265868 750370471 986055659 688158661 752832825 741580331 735173181 574062382 33668243 99339292 264007079 992630050 204466748 143507183 222752629 443016477 677409240 70904048 584037672 832748723 654475887 292466282 90027810 621371852 413766494 303093041 354621067 293972580 269960633 477545926 379889079 992879501 837004966 304019215 508125242 173110387 41001289 499017122 641572413 387635433 971182185 636423284 398628471 584886149 846263068 218928303 670104244 909336487 988281535 414722803 915156038 333857025 672361158 405745676 957753403 296127205 413495207 709083148 592046837 593198 806119470 22405989 296108425 539014357 441512240 300960138 636623707 110251178 821671235 153567680 701429648 241854841 953427318 184408905 388741629 648783012 48820011 638660901 473452311 961449734 893068559 445126890 124244137 521253092 734299210 471121601 378373358 874651741 310961837 603783635 110557981 177533553 540175641 442171702 189496896 401109500 93582156 229924658 945464253 175151030 788700613 105488629 596008539 534302462 408734291 159156610 347780892 273602770 827471618 158393568 2499249 922772041 130751111 376573473 842138501 482916666 65426623 929549556 975057191 204306785 546648288 260354975 170704005 91795409 944503731 105431050 95015205 483622476 468052957 314472593 525224638 509377766 228165922 280768838 588354584 931643097 590593842 921414846 257023177 570225083 518515864 492689349 171402075 213457637 520056599 507202151 145115676 952489504 406686245 73680811 769550923 853341825 507890354 593460067 629949309 697584340 882208857 889622954 183936997 297528314 123931313 790277627 186569055 784171574 30436391 483293930 173795076 932265458 421706766 472472260 482590243 817679860 814801598 309888598 928852722 7272970 940089841 677890316 603660119 825961309 983659086 367517062 139722830 287300062 659801346 272996086 747429935 179910944 134061500 261261654 746079775 580280350 974390299 123400444 692220767 827899740 791499096 88458009 768581785 398698003 248348291 240354477 67805810 412843571 255218200 374354234 554377084 287202899 289552176 784618319 364877873 875581543 774045504 765837494 535460917 269115851 704914260 455413599 808992211 753531125 440197727 603865797 635027241 957259754 282092381 274533726 698181680 722590208 985121898 345535277 794422090 775542247 228622328 167453252 840674699 948027939 421048579 627187016 181548109 914859863 220348932 314377478 109595572 580235538 336924237 196178797 770237608 576313274 792888865 269859304 482365460 978562727 627834107 22674273 858187574 386079259 500716900 671851801 437225100 681511646 592257720 249751675 990627121 291438481 246379217 846696390 904574072 490922755 18255033 979572872 808005759 337576584 814402795 199564889 303493252 715545586 419890732 929875413 466248746 175868174 546578899 82042832 745326830 397803979 64855113 91111715 197518221 716876675 1986245 710554043 304487706 610551021 807971080 490778898 439468748 762150186 135751127 760606047 110347264 148053032 748388269 188856864 830693780 320740814 905025075 592683726 219761189 644317125 195144759 158991136 793426184 390631533 977529753 86401026 68799520 868045307 568486989 457921814 218910487 702872193 854783020 745783186 857659194 101911361 250675935 716875447 423243699 384810187 92823779 890342599 44743205 246811898 250283387 35801279 847040554 544797686 705597382 34833971 260345906 191973062 23916248 832155782 376664003 590340254 427187434 30954663 775277806 67531381 103588391 328356722 563830157 595802032 937641273 172031863 796153239 181620518 849760807 272386235 626244301 558373194 184052239 778708491 850267910 212435163 48787166 889766841 327675516 958998041 523748094 950553304 383015297 23519952 761089184 205978884 454871444 89627738 230282209 886150359 563357231 291303814 311406675 245115215 567250300 614944304 245608686 633146643 455119112 768937907 259940493 544148782 370878758 447703245 454284097 992883168 307578969 890292425 636904646 774650111 395077931 578979004 66333081 345742597 747350235 215010467 609522669 176524198 192107115 316533244 89186239 892938947 238472159 37835259 60075013 476433718 494254871 351063906 803303660 516954069 517092076 341267257 667478022 572018040 196617520 139084642 841911335 930933536 244287135 599825829 411764806 189395238 473010889 953780938 606505783 742669495 396686314 690067806 871326391 122870677 872749903 435526044 115174437 184505988 736137690 105506545 891041588 154504528 560947302 780347991 876619001 128323225 158970715 423099658 50386715 675623851 297364640 389643038 212378113 143347475 555727246 45053223 691488729 103133244 128285068 568280451 587483375 809883876 11459999 34406178 130074155 77248475 302769412 794008049 480721136 629271425 376579824 736424196 441795007 110809941 996628368 295958491 278117753 268947378 960684638 807691624 739012142 579262780 963049610 733000287 582002371 691024015 606992551 301242391 656778816 800872225 164560786 224981513 166963238 264897290 519293203 155616140 314229123 810916952 216538478 827009842 313965354 910759696 641783381 377067021 309277280 844083814 940665502 862272974 710680451 426465146 652777542 458133201 761658012 660258874 218866348 162264897 699629729 542900037 259751566 839302342 958287233 42846140 114069906 756134749 971945294 965323896 51452301 68596274 686175202 874900863 618579101 274357280 771293989 785761933 596140356 586864039 23025340 673612904 593648176 310686650 342597444 4227441 506396429 906457877 934352696 210296135 241175171 760751922 430991987 49052470 823098291 392782076 881428316 85983746 268496976 167691430 305652557 622476428 795370639 349927281 382530762 139824883 526865795 979427339 745565351 80425091 213051930 811477793 795318576 850723304 252388431 44124696 954544468 81290601 342392486 975640078 57624638 565982630 487959189 843633452 422210287 539133471 900528219 680586682 819881096 469006175 232305175 887747785 273538538 155417999 758960870 865894271 944007795 456783919 399586457 182791708 747345383 360516772 735714773 226006960 291942890 821303330 644300771 549407319 349362958 932768440 143625573 123510942 191723846 221619689 75570629 519475837 609819784 245256948 406910046 338374390 498140825 610252048 387017348 104490366 491691413 382244083 420132611 372460639 255899794 817363372 568117104 155766795 502154257 56894592 35823552 616954136 783406293 800262583 692539665 516523030 328169690 560945880 396725146 694416039 30796578 676253374 104277480 774538351 625625267 293553582 790480567 90491931 356676536 664742382 498663480 457456475 738673758 907200600 825092326 154241849 947277742 985161012 759308371 62722227 462372392 800908770 248498739 88514825 377971479 510626153 967285850 906567064 934352689 229211389 843780024 365036141 934763551 302747999 416206731 260890838 236712708 846241990 786519629 650910074 24779969 310121718 685098935 683703306 390829581 751618150 764260620 579651999 49551395 710106705 951313343 477642058 885801919 375381501 191724569 150476846 67742605 75517964 570572990 991777847 849233935 580910909 591858675 823503392 315917464 54725811 407978620 931284258 958247652 364698045 749713416 689221300 780353977 635458628 916445742 759547508 275270432 6323763 993843946 431603724 663336163 610184188 722212885 865388195 495810504 592204987 17998223 854741535 931405743 93277193 603225089 534849543 227925079 487431169 319505208 808712753 366614453 374228479 616048547 111675698 976555565 648314179 579363723 393729949 803178160 537435694 423597132 54576420 855750767 465997365 173638993 192155144 869110175 103956192 866599084 403339072 46051100 743019041 345771491 337194010 798503127 174263048 682688611 440155571 41795665 962668652 368883925 893545604 606333442 22033665 366258508 803588691 510785633 564360550 546529921 901985170 75757590 359169164 197405724 319378773 263319232 515994004 750162847 312090096 891603469 833020394 640436860 16081609 209781658 290484335 569604963 379146819 517389961 823503313 546233476 269744444 579076419 409793256 780266725 407758 606820397 74612008 56992510 677104604 125369345 709488035 493933436 939275298 25786635 906835419 328227748 644156340 608375043 949637421 520792009 7484380 47816369 180144830 302864902 204607666 920431193 672379103 67170061 319309965 34550668 627341109 95618178 109519942 449826413 606310550 330523945 325087731 342134451 777867108 321453004 590187228 354626507 259008366 687465086 201582989 535837384 798467321 829008913 394393961 824403948 463323500 294238472 11905450 221483488 439769466 499259877 631587375 84163972 560868473 540294092 290614390 247961959 880763215 781936738 563798914 666201560 323005014 668696735 538629987 746280756 514613153 573284550 401105560 532060257 941565333 53152484 376205665 739561788 326575027 361345922 230643172 362068898 243259456 3311939 84187263 731924733 126340119 705897602 648125009 454646144 35722449 612601146 983740452 489525368 696735563 177256206 332856151 794276060 197028278 471081389 33324916 737077688 301086861 761411181 245695285 241768526 453415054 161889450 347059322 257365377 917093 431667923 868925801 876079841 920709061 795398533 303791023 541415350 462029384 853881510 605538852 826499579 168758818 135854863 347528784 279849497 256861509 835378869 487868777 945330245 849517114 350432195 900122147 933713076 611079929 108179607 971666800 194401301 137464134 714361886 655530685 782325111 1704395 579152184 335767769 409921817 724015616 677410259 40238001 318101934 323425219 685411579 539050764 706950249 803041693 263798700 54957268 434491731 294034304 879669286 689056555 641747664 395300011 862785023 898356222 702461083 541804278 871459106 713438605 798108650 20255501 705245826 538534285 164030144 631349108 770456483 448228590 448896072 136786007 941819894 866957396 854425266 442844170 28887124 416373466 341856345 568503317 224458600 200000084 475175996 256707349 175619950 585163499 785278562 838313150 172390780 333753650 397634252 958590235 844578752 856667733 81112598 866304945 825212818 980756588 995304204 310675980 13187358 886770756 585532660 895063200 895181617 44801213 876559158 506040908 448518587 132894923 956402387 232947227 33596178 959626154 348125973 868429390 266172947 496634740 510100895 816269879 888210928 226235752 662289603 510244509 300403973 497028572 937136066 94180795 140662572 631384513 263009893 774905884 952644102 93720590 264650028 841563696 230822323 445903839 432344170 128391311 703268591 956869940 123179179 697618769 37879597 835890874 550039353 922402966 53943642 969748911 743145698 975735995 52133135 338566525 957016999 966121173 488168290 420605415 576662016 295407866 211689178 974853734 509902936 640812320 57908359 996167579 794210430 139030203 948232473 757138891 805320417 268868613 748727546 659900600 689928312 177586668 276298062 238366806 511257590 496839202 593749946 743797970 856438582 927701480 69131975 727203791 522270904 696999224 418545526 233389903 707501780 500261179 23487369 675845211 806446308 726157864 337297589 135122679 710563433 110421497 811335657 534775880 211329352 855379564 548104614 659842620 864818467 409736087 89052430 132422427 27482637 777143473 233871221 342554769 744424384 565676326 639388817 561606656 179508020 12794187 676282549 180672417 427774304 333329979 802732378 156198991 593791134 923503094 298931195 604085676 961989034 759903242 335926966 59221416 454900096 565041393 239721308 95776596 95393783 961054993 554583544 389020235 459753542 561899522 343073777 400080753 84933359 643099781 396102542 384786340 473792585 970883988 628885933 854545060 776088872 452424766 653478630 600386503 613077100 431941651 374448731 418629166 781070353 417889608 944716587 241438491 486716758 541251328 466999491 949268384 118658280 652617654 162179371 4561572 704519672 258114118 827610221 609126598 705058210 363628710 34025459 271713506 382283044 940600515 454967067 963970565 246701054 143922858 478388139 923187288 76697353 215488253 694922438 328363913 541557681 359674568 129773758 223009941 6772795 521950532 857365294 853111667 44573770 911724121 519652891 33033048 113609352 525558847 934854701 311531754 753649619 952182252 526453374 107786044 922809717 159780622 837211835 46676590 84552105 598800380 296515521 304137877 123603973 683222736 791199593 165683052 354201295 585074107 645239956 20485809 314490920 137399194 782406610 591134811 409207551 828176635 211769731 436539519 194039756 570305764 876605587 969813371 332665955 56990368 86369368 245947123 403914396 660174133 247352881 846273439 316473213 603247987 640766822 130924458 408504060 980766090 480565309 242928697 247540071 908191912 663663674 952063717 691881694 370269413 248853063 701427726 578688746 433528192 864423187 801697788 774590297 609791845 878026679 398740869 413074214 976427429 524411458 359493977 275212302 667180027 18680816 855500443 272509869 528479386 207502429 579396988 411079492 187988425 557400244 884684521 256651932 572361369 500784470 201377365 334701813 54356096 342671755 817973273 605257863 528376637 633641902 675939294 584974830 614392400 734061202 235900993 300445674 901850597 119211761 233033653 490275145 279577998 544337295 624690327 9201646 833168449 850399662 368591958 738100358 604685424 541206283 511643772 326037437 819001825 650355431 19117858 238001014 375726931 375561406 332364900 777165605 473379434 999192491 415988689 821176632 940093064 533304963 454163394 637558519 634526419 733944721 963487515 632785796 702617032 451540887 332205232 213498835 170349333 207904236 172425580 110394151 686882603 350620704 216986941 515812210 735867217 937502424 28124446 116978879 24670021 459428306 349378098 303673291 960937893 228806115 151772816 941013913 729450891 962754167 848437212 33647540 315124975 564334983 269309420 259990142 500990867 197325888 891140817 138621469 144753975 933740035 892275142 439052274 454056610 962026351 825689603 472818287 2134110 579035342 557286866 89675494 97138138 851598247 721496812 690869805 681101745 675763403 931234603 66678386 661213136 738482320 649366539 708676480 568685641 818262902 670318516 773062440 666058561 183118503 848061648 343824903 587792417 816969479 33580098 809260179 326386343 645851446 693140186 326451869 400941439 345955397 821474655 731643725 182793530 794077216 776595968 323964439 718044587 969179255 513331076 114673670 605477904 387616618 733400549 148466848 212917139 605507044 996038607 773524731 224761296 778505924 644005375 697515891 143610130 390722355 710911477 82859259 608063052 634482397 559136777 641250479 655997539 437480744 167825379 753767275 931701784 59935417 4814404 27945175 165263970 874183895 763095852 236465235 393410908 143643365 394062925 160822260 699931785 330004958 884086242 47166194 352761564 414582423 333888518 117835671 642918550 108177018 91447444 125089334 289044858 830118235 483124510 173373753 568661191 953327974 664203722 487820974 804735833 14525552 795203879 870510759 186911958 526454985 420630800 947913536 761508755 661215796 264231926 266950787 557121247 486318922 208196801 629763073 502785862 669737545 469744324 62130388 736897124 346828950 385203650 274279909 321731487 143965465 316592178 677114109 314629461 947647536 239654671 445932654 273040349 183659683 587370118 768831068 668751795 123897061 703969473 57010303 473864599 813050894 889128893 702702935 169743146 755992372 406199503 533813493 210735217 201172870 157955151 991715382 171733141 709862851 864436663 868048977 146570294 964738044 385638742 172099863 681982136 768327269 962507339 594413397 316019762 736195074 903609281 807087435 148158918 809845813 749337126 202465436 921656827 407286122 354369459 467247734 485084960 607870259 645560201 684749326 932899100 892153815 534807655 310975027 378183489 232532332 850718325 52764396 538256625 132986191 463407455 860895955 295066343 258347564 881929784 432115130 639251250 270638344 83859867 918630947 649730018 251122278 265040709 354343148 630520522 143518360 45435988 733761066 741251856 872258211 983101984 428984450 930168866 113112025 86091462 202824688 412219979 450514246 990021744 439806020 962742883 669410769 442251977 90547414 665867434 879978641 788249425 662401000 773239672 587592928 354641353 73730139 182107831 346031053 16150499 286250765 678593311 211519707 464503857 182472342 93945988 301694153 559261062 921915104 620425466 419196655 634812888 896816000 967299159 714174478 315820421 10881886 814097546 375662084 536734620 68555261 296763684 938651632 180021071 557578290 868171954 468550619 250710708 244571131 865125563 141038573 694824094 231763733 901479071 122387163 322098609 845244880 339234635 879075766 471715157 333797986 975723851 640871657 413834544 791650410 978586817 87610755 321554341 402866363 215550993 471448259 179833327 450048145 158872857 592851028 364257352 274042690 516069582 987408060 869003978 172247741 881916531 1049516 675507361 630428762 323139033 989645577 471176199 992981994 59635753 173883948 52498166 637521112 801422512 170954686 563447468 177503723 300681859 638190083 523213199 368934768 206085349 299745794 669142954 674364867 35645267 109665138 116104537 866693250 359448186 341768426 524516727 364303325 478965907 381063824 752380340 598030198 193357013 852939645 337580420 167064415 401709828 385511586 535562634 507278599 653445345 564655431 254295898 851968415 404712088 655527235 370093069 194538253 868989566 856400566 538134000 495704420 667347305 380666964 686237970 766376079 567462925 148768818 711906675 341152282 647878668 197264412 16197814 288141815 152807692 315802808 163999434 869647509 406774298 206965032 12999764 288657774 440444101 128387200 98564457 728857665 161275107 398419423 79989067 532478260 404873381 480614992 28667221 925521210 253867970 68208960 94833158 57011150 409938111 894662066 488962758 927266501 449904333 914562280 1439381 918887591 33852006 828143370 69720205 508037249 446181932 613878814 2700550 364353947 866468008 200794967 554426590 583205955 598674099 878003433 491336556 10544949 923228238 184107434 713509010 298417368 487571931 151109570 54064528 951674797 228068422 978594716 716480942 544530489 204381 704554370 584938622 478585664 389754513 784679547 328798384 979551952 912263991 100410103 620439553 897401294 226572532 609336740 694124869 632966223 337328794 968626144 269221762 90721386 647798810 829197807 118259074 939928844 708212607 706480584 11072186 321977172 236432517 296218913 920260497 949549451 90021170 787593068 841163815 661027651 274071063 835657275 738077209 491588104 711926737 861053857 740392316 45913376 700191980 990278848 24505833 594909996 259678622 511195165 50606988 45731480 464986023 53382554 79780789 657607441 299403525 668223471 787421773 784699628 932034576 768325209 93742011 84837715 867382945 860993822 143247127 459539977 650001859 759604668 357352322 429563075 942533134 831090197 133501879 676358586 258623027 835103650 660298033 956345118 639160825 263388052 431648916 615241400 636269658 239778823 397732749 93144098 452360019 872729010 870803818 106703850 809408279 111065761 118625589 870538446 171762512 727737634 957456153 636823980 233421124 119927317 899154947 87351733 177752919 466672336 864714606 190555336 43277969 9335777 309770967 561989086 210794352 13824224 222935381 517153048 770935902 497511024 755804379 471448853 614438639 983183902 833580834 501350715 961795846 242983314 813524673 668201290 847545160 701444051 386496141 492854633 420388726 611984117 644957684 342738192 279522608 428347004 995031376 785850169 869185503 3333410 708944731 992032987 130639280 603800608 243411004 495386894 775710385 798881949 1662342 11544444 553036841 258181757 758369780 25991967 949002280 793367522 205987513 236853510 880017284 146337990 580046493 878866660 666170430 370102118 836891810 545484522 938585139 393667374 464405309 5904811 685264333 502554889 485323279 600478545 297494819 23071413 108177369 904498716 404769045 793464885 612926983 221412658 850069210 198714934 958548245 943167140 4529796 680047763 225867411 662775798 200522174 538693897 978887288 6883695 918993761 914860786 527833357 825309290 721663487 532863040 322981218 303043852 478020339 756932253 48111242 379804104 24788143 283050397 462232924 779964740 286737769 708816645 612329039 161345693 196373410 861497084 395203083 896654332 255885223 675326905 465875804 361656992 278548540 309824476 519207421 804290427 699941418 517878915 958764922 711137746 676881661 986717250 179457033 456312129 492004709 389798790 51847449 40516291 592227853 676008447 600983278 394037848 801822760 650751392 817582691 913842831 205221121 608732561 190745892 332750046 7100125 976599356 818657079 545911751 410700548 834107945 572604072 982653446 81683936 77457620 60205621 336200167 634072081 237293813 93228591 859191637 595941191 7396601 320644448 437911320 3772475 817552504 428919319 383325862 920137176 563336350 631309805 271756642 123130821 138314680 182512096 139607067 277396138 642953003 277646560 727191301 827061172 872312152 998206417 307727381 407464366 366609842 928206214 110830679 215241524 86128007 322264184 824677745 776877225 401714344 390780267 74836528 611813903 448890179 670224461 120727714 97038422 32664628 683014860 353948560 39531338 391225890 937837293 535843768 794138132 150337586 976626420 923595442 554923827 718022681 223517002 998778253 782098507 446629900 336483737 495479622 771933673 36269269 331574459 952593115 549012957 891120298 899674836 745671294 287396170 645277531 93817632 753684187 734717340 724882369 132331343 27334359 998476094 407146938 88371916 847570744 247680950 40851381 642110224 174964511 837113037 69993966 741888434 899743101 34833202 864760197 191977687 144497949 331757817 98816659 314697221 846734519 287362885 14378846 78408115 45374657 867415901 532024914 13187976 483723726 805429664 338268979 491270248 614413937 889600376 422831219 762730373 979082262 319904287 172752668 920612382 484570418 424532122 526329498 812976542 131242383 327873505 487627948 341268910 479260914 657546890 157850407 624319785 569389243 339624007 67838421 730254161 456914192 599900494 398221856 553947137 197667079 89393372 876077499 827600937 517388101 467990050 441095266 478448553 568098449 774381321 339252116 276188279 512816818 282808049 476107881 422657868 253926710 351901258 161038067 882853378 730329780 10029957 79261597 799891869 493880722 993007007 538774263 254907972 465761844 105639238 760861468 776011759 806734096 413816827 20105730 114829278 270065692 135101297 16238563 720090821 201531195 809979161 453290146 902435288 689220509 601727680 953124414 869778768 177632326 108375250 978079178 458826762 485627370 202475331 589100799 119702932 227169199 174218494 301267659 170091205 768927743 681630751 315161567 566286021 556035816 308817935 898563365 904913286 381437426 626526229 881071045 323262731 89559776 191819814 765634176 54232321 554257696 240558356 361478582 604835189 895544395 701664814 549081862 693843257 326515749 804021001 470921016 116028146 525175120 156387028 902971047 174405856 230658156 379610941 379976687 643742130 878533785 848622323 100790325 324744019 590699248 835169753 969672204 468753834 212738365 755301999 434356221 597566183 582718310 124142885 202444276 562509513 899947770 263867848 148962658 577394353 425925089 604434867 370745544 388280853 304962478 149950273 149223303 265891528 874501723 612285371 427155256 893221399 900976459 814439852 955207737 282204220 659966421 154599241 224991885 350434732 792682057 844807415 721813798 302393565 160924607 865380463 65165001 252840499 171538218 706053616 678549318 433117454 395571557 294395595 67591560 306867541 799797770 14273061 381727460 282004000 654903404 190554819 250463788 380243402 216773485 732914097 573231510 677330975 704410133 266875796 906003420 173144374 142212594 844366800 53441663 642899413 427393415 97836547 941878374 882490566 978765511 626426147 236460708 666622368 685106999 624268311 696919865 534010978 719533778 468658007 88804156 565655183 317827247 301048177 742238264 936321602 665198359 460425573 823525113 389865131 901715780 670167909 725210380 137992926 214979452 808418446 70294028 829912965 63369418 716033360 658023946 174255232 129712267 523044194 105675403 272479552 576460943 722480852 144661120 375328760 774146253 654560860 43078577 366394847 568985566 446864715 429220008 950403364 397548054 573587080 246006975 740035735 452704588 563442919 810200812 985190148 100614026 241808528 558336405 452151835 723224744 695184183 280550767 446425014 107845953 509634666 537571845 755143005 12675849 750684279 540381301 522172295 958029710 471671869 434992677 794592626 635384672 979224165 213079070 246936890 77099739 35080023 307095495 57259340 715094193 337680469 106595959 897836025 941066368 311590397 273885304 192423561 80138458 851365247 532113670 122036682 856552686 324630580 698244978 448995655 699427588 901928500 298381652 498720901 344565555 571787755 504466201 590433821 715990116 160686903 507779591 46338884 126471585 154366112 808522636 360383741 483274246 320330548 285572044 711064662 700946423 786818181 563337441 273062473 53744980 922055591 973137541 697068444 621298103 734398006 670251330 996893441 708948866 223176525 864257287 953132809 425422926 828134444 152902502 842994940 292682121 189889404 236131958 238131257 717718330 91222124 591577487 473911889 379037239 414738120 253374726 169758720 641039864 27431346 507310750 341157333 148524600 5323690 829351983 647723126 359409689 392938802 356738870 5312095 720667256 719306802 560382687 594954446 177933667 708075040 923544237 759820389 256203525 227162740 102629059 555547342 61973015 859671107 706844610 80808843 376454451 720660506 593653221 623277894 363760714 316007815 373245566 354769722 502731452 442058493 414799883 504344218 620118135 832858002 550522915 47230900 563698408 597299351 496665640 779191931 638664647 912127497 213336769 336133227 384656100 990652381 649971963 188667756 921665353 193909060 966356236 790656917 589823573 590190635 297864244 801683155 567283472 456945569 841798939 280264363 619614064 195510772 602000977 649388234 181681093 129634065 693228505 461310131 164377883 374787147 104868678 669283000 358026010 279849213 753799101 14559140 2712869 147315016 986008069 571343479 98797013 541188487 66077705 666445106 756849424 946328740 727100496 828041220 954904659 600385257 532190936 26584021 233263723 25069454 336362176 834813926 600425682 647766721 631222834 150616424 670866396 97864616 522213155 549239886 834961476 456464711 874937907 309478774 943887995 781531747 621852816 148440270 226280849 233518542 864864644 347204914 626521269 47137105 408045738 803941407 65643357 745759554 381133919 597391638 895981255 728004723 840026295 956421449 9492213 620779364 228352188 945670998 362654321 412216793 599000641 524174495 149409476 758146085 57621078 8538187 865289220 59453993 972596837 333859174 136081166 963571570 604367398 126571370 545110137 592671875 572850681 965705429 784553852 350435356 39833371 693013829 852693954 927991670 320257613 917012574 776365377 809383472 169370543 955936638 726444757 473581992 78295413 973722145 295080267 498109177 14524509 903928626 273383749 227281343 570246106 272268484 461477937 461660840 972609372 649680831 843855256 243053038 638321682 985137012 331289577 272291178 5421649 665899682 181979787 322593433 237000787 282342241 886811273 776343091 242464544 148765624 595800580 759925472 475353693 214368599 462444242 53129530 296767166 171302260 988996080 497399785 310033812 722557304 899759999 390419171 832045984 580965045 277539226 323117519 389528630 669999695 403303228 457980387 887190237 364911151 735956008 38401788 134318423 265908624 527998925 360093217 474932119 597830924 522503239 361832761 473736933 754991112 83423237 9519538 510444233 563248346 55953156 219747197 144449242 442344042 763254340 20629517 712832905 566121047 220895916 577324463 433731947 726126145 745591222 744072522 141500375 521630820 656118881 663457129 585105394 137965987 298874780 924407824 384756957 549426564 37712107 647384370 8729818 632537056 56480309 2906921 898301234 504230098 777278369 360418182 314746452 599498861 908733719 626643538 836138281 691216550 26946193 527195852 739481882 832144398 255007931 232467540 514824820 998962175 605861537 390777601 732857783 213449149 788960860 43520059 60133873 443414257 656680252 92730954 854031416 176608731 750995228 106262465 487517649 89055255 926536995 643253472 732538739 749234464 207234905 19828104 925866067 162364735 442176037 912997711 920980374 933322098 886892541 362081534 564814580 146100137 530167319 832886242 266243495 652825565 410461827 444745176 733407992 959262404 251504454 416436294 31183976 239084509 252960130 886534647 865083809 912188425 919761367 225960168 685074715 845015504 415924027 252389948 74843959 444709350 887343500 768636976 74735601 256412991 850409986 645700476 940719483 836643678 977376420 533299158 605068876 876391886 158303672 349521746 356054211 663471616 859252567 24237681 237656190 904191072 719522366 397488043 403948716 778449025 349631392 445596551 716879974 934743599 696619940 836715282 643097767 743385561 363774481 705213076 30140425 401942382 363633982 121518298 371734583 214440052 62822771 987425382 639569470 637927038 373656701 76888305 893574325 203397786 902694096 742817587 806018315 309670053 666477494 583056690 617667414 731724615 328397156 281900601 936282252 519729927 242268962 394697140 929888588 883306693 612850290 229070598 877313316 19100736 459773490 3571588 665123615 34487765 676041571 610983137 482116521 36701809 617800370 428874552 45204119 474071764 666134560 745351815 316935827 625864712 71820984 41085554 902151433 601521069 206176611 862000307 274869323 844440482 876028854 10233319 374607166 496253675 607356917 619447915 304756151 415633760 667416630 420526447 996957454 318539928 221172397 268506192 12654779 817750128 460908152 16518416 814975536 639105783 12750386 672413001 752695721 937804862 143449352 315380141 894408301 556204687 435437121 60598346 796141203 487578830 276213560 763286388 193622405 161322180 178248726 48289858 168878311 996499182 34211809 455603150 484326722 739923559 615535655 144443072 629585495 747830894 436686938 865220197 851434858 771735866 749470061 84910305 210129947 205618168 540846022 656261657 183621616 729499485 772377257 28341698 85772358 898583556 134146624 356380064 157708298 552366948 553681559 952402941 822693117 978512664 799079736 746078489 20445169 863596268 268841570 49470387 493983056 624677007 197446385 102087313 366750886 928297401 136566874 296070126 682373090 26603082 910435332 209973637 979650838 725304302 503075246 77942310 303828189 82525367 316354201 74148393 649818523 529050060 795592545 566445439 227322361 851693846 732451126 248402887 336306626 38997917 95430286 946173908 721079629 493851866 905196365 19380676 374064835 484754525 315358560 523605609 742089056 466612784 949682755 982021649 825195012 694485638 183403970 326963899 807409480 620309411 101728737 400586991 142893231 684305427 919244753 644152726 326945541 611145440 887619972 930919846 26558301 671856312 247472607 653906826 247196292 264177240 923952959 702998844 467300610 968547289 253414600 187576497 370582516 353586692 764875611 55791160 79019138 438430732 688462046 399838720 564819811 805238879 816178984 851973357 467651790 77602382 241767664 939367814 165568173 414427573 469414410 758502345 925545561 621509525 58603387 184160097 890687872 679573956 851578985 839216938 649691056 559191103 642800230 976738613 924434339 363245366 654020074 248391739 512050435 149289064 440714961 322761657 235959868 335764916 434225876 377120899 707845693 918282834 249749018 575188230 290476407 196312260 509735601 151239459 699260670 89612246 623413265 114001916 257971403 514664250 255175698 125476006 165204417 407202867 644836815 644810726 98696997 62022830 924931523 593878697 769279586 507434039 46139139 160967867 18070503 477984584 958976160 588677719 643888718 86202951 863172395 18572163 826247061 430909803 753381366 377371883 111268091 908050968 713215358 89768174 880278089 259717417 894119291 678204118 858970776 801871679 146454273 924418538 508192469 987532540 939614764 210932245 657804812 421288878 61439379 121975537 824943965 223117839 68841264 710063174 795162316 897173998 649722801 322333383 836358932 684437080 900481063 983492110 39993817 157814771 789507131 407742969 758128029 501040205 866378462 364618231 387949373 251530999 733442242 392814462 127538657 959639544 505934858 801891223 559199561 395111125 742399886 245135690 178415818 886382282 164238996 234089599 938729109 655917683 464014280 138153183 545301307 605869304 578651575 287923474 561729050 632410844 656196439 215955165 584140002 531785816 103944407 834960540 100675292 575574484 565013744 51116095 676071628 960418997 95781875 104996579 282099131 643313612 865922386 379764613 542831851 353284737 819120328 10443669 837491554 256063417 592177670 637819671 175063005 861108742 458908171 252665395 344544690 794050852 903136695 564580392 153353873 861640908 934880678 972785764 562523664 534002402 885752628 150311799 153213196 289738060 302325082 106905204 429372224 510617665 336388343 147674167 328611847 332381653 197676630 207341070 125814695 287602912 988881869 929491478 62765842 898283806 857878660 220001702 848148318 185160074 250309808 649237425 5204663 542162659 896659641 955322968 750800279 614855352 824883945 287431470 89553300 626471108 334115841 490592691 578992815 604709694 138475703 253197050 775690368 544836903 818007559 234666227 696911774 981122405 26057524 118563019 771569586 647107564 50130777 521038218 874206872 616938120 404217599 420148488 635900427 797185365 474975328 742058108 6882855 407422278 619248151 736667715 108380275 396451532 662139519 998601595 942273154 116676327 716646481 772122851 449695971 969330142 461488460 112828453 381578678 733616633 245694850 774081578 13628840 624829769 467363717 99888765 476782238 567172081 691036359 18288817 937513297 791069865 436083171 737573673 561826566 376668787 710560703 854578347 648361667 270019935 402949998 577206660 741426249 546430555 139170648 981632813 705527843 75139824 431302015 481169586 371133562 748315523 500052419 716142271 865098938 828483232 142397121 507697518 90357614 514212381 65528859 128947711 534705990 87439074 339874344 940631603 393582149 113624918 156671143 723634355 967135960 902936795 963193165 579663141 924693508 951438205 105211035 593561679 527136883 910193062 225636801 999200601 74986615 598431185 405712164 281374130 805645434 364274211 34481868 184562419 510337811 318071792 511287870 751775929 447919647 343090354 899275678 585095625 883664279 821206241 395014192 916057777 384419098 486878196 875121925 844685070 446449059 832715130 965942136 874463961 421490296 672903591 326564230 507144048 40679296 779026236 17746142 416304529 499074442 643995674 629951001 380963475 139607047 769729372 692341085 405416589 4545559 704187972 691174317 133882935 94841589 986913655 534346642 773409119 97852186 775335740 289694754 471263145 148535836 347089017 305037841 327814115 992846427 655587687 199756318 586428562 305384025 848302472 193781231 261769584 139372385 983694348 618871058 376152273 66453012 717251561 721614107 562663887 96685924 356482110 635017581 323538429 980133186 816228462 117925140 361519888 57594836 930589071 834812510 47433782 240453838 285074901 71849554 602707551 161460923 946187879 818188378 871313777 557432531 899095656 610833879 478253631 861748250 745502055 533587670 72248434 701687832 237170939 523874444 382944238 303209593 849399087 562437052 898105969 294962800 858351877 180562317 379827382 369777820 57016401 206382725 526288953 919932123 464502936 660601077 880987433 210746652 200811448 103750736 18427877 834941587 845187815 21558927 318101504 761919170 449951215 642308763 962180996 929328221 226258884 233038813 203118023 555920189 596704875 104784512 265846068 55948702 416470991 725653481 481788043 579523634 673365627 931208220 482795001 323259031 187096020 606932495 534496464 60180653 317474844 823647492 80381192 781856437 188159923 55921250 871995791 636271884 837941365 132216735 630548316 118657027 520200995 514304032 748829822 639263010 504737174 430783430 122036293 330090982 549590735 649113448 352884564 290360159 695226172 269376791 20731637 34595556 337914555 362420422 437621080 148861504 320845245 410608241 977784455 180387578 837106041 928493641 947093117 612705345 822964228 485896701 284615676 577059653 929464959 799057304 215762866 785279923 917657062 171489510 514953007 370756547 475665275 707557027 586702130 788988535 565001306 168280216 221006979 341646444 226016368 68877724 517755781 636801768 193415290 240254931 449600120 561667803 588093043 752478029 885683038 895416937 462000022 477098877 596926378 841523187 748335848 733860222 242470304 783866767 249671990 916657609 446654173 141630693 45705724 307621249 43434562 319542412 743667224 693062343 105769934 42255508 505301952 541705001 150334858 822346928 327748462 251379107 542171085 366242209 580232158 938115449 613335888 486538599 653282574 654830644 332469549 453980890 488160926 417952166 267138006 309775254 186859870 4856214 195005812 382386009 869523156 610057810 175817795 422984004 199718780 538293715 374062552 772266025 399206903 368402755 394054302 441384896 524361345 431456747 386799551 218125602 704593368 238695176 248916704 789972298 644628410 908933591 790693494 660513938 601819510 339791338 197414530 741943417 716924301 268248778 642808181 766061982 905115867 881723966 547591514 305462224 279151326 885227783 612143207 573744316 878728982 492000989 333896 648334724 769492023 898811073 694659715 682254682 762062232 656801229 817308605 616186816 275806998 68067624 740824018 985856664 851159372 626075671 249064011 405246130 776497660 59854729 414901273 146452201 334352034 585557311 35080412 316297568 725978027 716186573 404458448 84820367 887594062 495755614 348418328 372420144 470365366 798010320 827491159 475181446 500695048 767066736 388103023 999354324 16591898 144656430 452348510 355336314 990869068 379361917 746329700 69444052 504631061 564678956 277731406 887518297 374175896 842490203 921629789 179161032 377398889 770626499 877043703 364726490 190575649 872861621 964227674 95393947 997838837 288703601 265391873 741588473 628230067 568263544 394961900 861268683 98723507 593450467 777163256 464278372 854933680 889919250 669474994 410754145 770055844 214983137 403338860 649312810 859996849 381483157 826782354 574343065 487204424 520394521 576813949 901790143 435887900 801306815 951421204 691570386 239073086 972912993 834280521 642901821 181291558 188056690 925544854 601336598 290303520 871392916 355826199 548053082 860637533 282012103 877209223 705310499 690046854 58897836 938766021 570173307 627257304 637316499 732683724 807319951 851813393 291166707 516780675 394308947 456568781 798220569 254561185 463100244 468317489 648547050 314044690 361830387 286474460 797845752 384752566 888641002 727890848 891858416 50259776 911110387 563268793 846805244 352210124 971927668 67910986 308841844 789827138 329221274 283118544 710227462 423272054 881219046 491246229 519096729 109588389 559612831 755774166 282743118 21725010 636289299 528100908 282011737 964161539 907434888 23398420 778419269 202761491 985997041 661084997 241467436 749705809 858728373 454980340 954150906 70098422 483618764 125574018 860680614 512442125 227422582 327144886 243859372 656994881 726165272 931515957 256919812 267034641 764512657 38711136 36605995 344436339 20761393 230971275 879541238 954245189 334376787 556652250 488547306 796166759 695599180 512716780 584727867 89092736 381796301 642046596 45084978 526270509 290346890 557396670 713017113 204932542 794836694 809750970 248072027 572533339 997362600 505574127 782879792 470326875 981095883 890786542 248050511 329647983 178999295 474152825 605537781 515964939 709210251 740472380 487587214 508197430 771802058 150436087 550167942 688422135 392385431 982747108 298219941 944395555 101045040 133745693 836113095 727004701 352219578 322959845 565600429 528014222 453870064 711891932 482635336 651707704 694691609 176308278 79532017 888514003 236209045 450587144 569695468 239950377 484903237 402486281 785563645 106539790 113450006 361405325 229902089 932476158 239054600 203939281 194764972 925568335 827620117 136610354 34935170 170448232 888005877 996545804 922976602 339321843 386970028 264234540 558342960 632825191 104846088 449452069 49993132 139563741 456556063 534361216 213026115 200153112 198014123 197257487 405818836 131528001 243700318 972387379 943207111 324216363 848325032 353352586 314459229 549200976 304726211 459160739 712826677 943371490 280561112 690028488 846317850 11971886 432357198 148895252 677428095 488811724 869521056 351125035 227154710 100780615 132767257 763092003 991115411 790084922 392891604 76515282 914090982 17832716 292743674 868217191 511049892 117718312 801421087 589476202 967248754 752175102 812183990 940041753 697549046 878013798 912477133 241735736 375994088 745687664 253320306 631544699 530250890 206383126 676164260 686679780 287650034 997960076 278817289 994510269 941874142 342369810 327355383 997590694 773020846 937301503 806051039 211756505 309615618 209472570 760199320 385153037 771631878 555480469 872978557 572227800 798315233 519456767 847435668 546820184 876651844 506105018 135697136 521592968 830265429 978600254 35338897 591790343 825293064 797310654 290120569 876201232 444725466 84442142 29011936 860243826 456210934 966086256 440549124 188475920 180076211 335096237 10405404 37285445 368030522 782858175 545871140 936151112 671575379 196581907 887115032 572606413 358240565 100126810 290617209 896739407 832099926 605614297 80887450 752294676 839947254 403427115 533208025 707299122 254448790 295293637 980289257 749559591 579419923 615299505 236954020 710476656 55583923 380460386 716828745 487954210 13280634 961170276 798739287 758674158 228049004 387907425 916063980 867601137 179198231 300450101 332016263 206590338 437135048 276541716 497350027 552606403 297427997 515052220 16946277 126716992 894018882 266809793 817341967 479489615 445020802 143804745 108540495 159551352 920527557 614672452 193638448 781169653 112012441 563758317 928519400 132561696 954229767 965045884 572876567 509713981 173439389 821850169 810861430 288671209 604012546 263504270 952085741 617166052 477197496 601787545 351773672 123628795 367043821 514658703 18343250 263763573 931918667 308234874 618462419 598983348 961990970 713704311 830039160 30667062 301012955 928187981 267863156 221315264 270197197 883233888 850336326 968717757 187678665 833420332 989241053 951083666 479802675 785722978 718143199 201913451 758735556 907198824 254124046 211349217 783732764 326513564 241267383 300241801 351356566 462832304 340435972 816477592 909610894 488346293 519358494 790058585 336059569 959178976 293018553 139565002 361654493 27418246 727306452 982744676 493936212 187219282 750032382 40305021 373985066 680292988 865527236 779859814 533156651 208144435 423039096 809892657 447937803 79297939 442342930 988838254 716633883 566158782 638123663 817462060 806026699 31913006 327314746 986779188 97763866 431404617 496750230 584024677 601711351 454891698 376980158 448030817 589155385 321349379 653016035 602472044 791344331 699277975 124409263 551846889 4782534 595597305 332700197 670557654 929776319 125464483 753741969 488857341 750755748 391908420 780128698 497315836 646915195 848364114 560184328 105759134 780077043 272447857 42435824 73866 724673546 510000430 141524614 685176078 791883279 223386256 848418453 894744652 441022189 719188846 303158491 100348432 189246873 600739811 540963984 46689647 893279683 965938193 614229346 595750059 485076160 801598845 200946285 640938800 746087587 656888648 76668256 849492814 675604913 161694533 520500301 694830647 234222693 11658656 958683875 265591741 836181951 931197965 311939924 306461147 779116519 683788600 507555407 606077542 395636187 686939553 617016752 271075008 875696761 801662426 65654391 249509714 799961639 82596648 108818880 41043171 113340781 385199230 761083099 124715264 333859469 642067374 359012750 962441310 239303277 362304255 876189681 251700820 368469012 74717592 278465389 505497361 305748166 87326669 433104022 29490478 618175470 898370793 806257841 443515304 703867169 637291409 569977187 435355950 65655341 943608207 703455059 911083746 458953153 907771943 742795008 983930824 175153717 53073057 887941718 909100948 781973598 696651082 793313585 791039640 230416701 869036119 382868021 151306640 256071168 340167778 140385679 214034085 885005919 858382579 618783727 586415892 982292435 373274575 306714198 340816260 205849281 111909942 549224995 630884439 398609272 354396940 395373303 809916391 822862142 145412330 631780834 627841091 115440364 411080520 49177507 828926401 56155011 64391225 454109305 843819700 481163041 505375235 722970973 491539995 258947308 862169955 569254045 384024562 354866664 579403970 549238514 341352657 340212589 581955430 507316607 108166987 214665339 500047606 63640340 54346578 659694106 410768973 96905652 829278014 68309384 906161281 723178734 734702135 284564632 612945486 413750447 690838110 432593924 360236831 174870030 521073508 845136312 956836530 477237923 372440843 782720778 26496854 434989486 556731267 974743678 804282387 20527060 785639978 127953152 769934249 458001360 629207210 226420638 901972524 187555368 866916680 769322956 561091236 867409041 34842050 56941230 533227598 386987372 185820068 878263937 183661305 495136193 421825424 884769044 879350032 786702797 96220330 983464221 876877565 271579576 819089106 230535182 761623595 969741187 868159542 831934752 763922547 626011395 708780222 458189632 740233512 671808803 243304871 182694015 832430362 836461451 832315611 280173409 835013477 258547369 331750081 792708617 812091816 861664716 713385739 607754997 516533050 368294870 836887843 980314116 106276655 811639762 982220253 886995351 694525278 309963454 688805593 52762798 424844330 484708012 927231915 678259183 97879139 601179308 719653532 41287969 794289138 873815756 85995641 995656446 600293553 3860413 304409372 732192034 386926408 855968598 451112843 199510504 614680923 845903023 824165696 637878842 982217202 931506517 430563669 748507756 296035945 985797919 240923177 751947326 67660746 203539728 777243668 268472466 752796167 763248795 791923382 812674007 732270295 344725665 949322795 191126091 209169010 840024623 991420403 363851852 987514289 119739944 309726272 691211385 771166154 248377801 674743120 883742029 504481891 25784580 100687049 808951245 120144717 198854202 351232360 27759723 180645250 650170460 306930906 15930828 106497646 995525891 304649911 522258345 694923942 174694519 708825372 564877968 247441213 224917099 37913045 34161411 171888813 46300149 845044291 148633787 923418284 261927354 42355926 553259108 535683563 775641207 373618141 123518672 483720892 128415972 777528180 748964921 861378139 72890900 502189520 415112386 795054575 784497264 475763283 472525719 715223008 518438990 798773626 84683238 286015004 451417955 851117900 850654590 346359088 891780739 59239920 947514361 875561307 635100368 917937489 557095944 193764276 996570402 715989185 165817403 193436419 386190271 687076739 345048768 988019248 472122245 602750656 605818478 2549583 543503497 7971357 382163209 376301565 368198668 477508728 762116911 880571445 576835573 687879990 534967962 855487697 633476288 132005534 862191504 337940925 619565837 240805444 642505656 406631950 621407200 721221423 256204902 517614882 905675612 326590574 146040920 272317182 698630432 929890617 838426515 932617311 507640635 561985313 486288268 553336548 465005010 679658601 540244324 131313347 144075626 459684512 505565214 161997853 88518093 877682362 722358794 432938226 216544657 907866411 17126078 296761501 622009867 400082408 394067005 167918304 162969059 77280622 828411599 199994644 307801713 303460278 723414206 922157033 258122897 644346412 669078683 704516488 255155858 208266745 570483061 200947733 62437079 162053070 244491148 373360119 224623280 873472922 75197963 434046433 837328291 303977463 689945021 116008876 347295076 708246275 430642529 322102336 317472443 507104256 234842087 167501196 840072182 606337567 86573871 56427870 747619128 302991121 780660065 851450773 362980164 188718961 630458631 858922148 489235427 818940213 790916896 91416668 263855720 264990193 952001674 291314805 48754362 709936341 580528130 808740246 768898249 23398212 81860428 416423837 540974356 599419649 788581763 284318313 70490785 390372173 513563115 652678107 490594438 853507166 765700634 560807154 642986124 931739964 312542279 366545939 175311730 172160544 844537258 914180567 831164088 120551062 441348253 871496138 233830981 531183602 175620741 602074 307000233 535785288 365603940 781220537 818930507 892893693 161664438 659431032 935228458 648639730 179199687 680055890 284009103 736534337 353524432 493027524 680054857 483152664 428224822 671397492 887900591 107743189 370860827 772216977 543135125 771139570 698915181 620081249 865831917 341295556 840484336 307523649 281265651 251128591 678464826 225549150 76049382 425855056 382787665 553182369 220074519 653950703 519102998 3669000 388774441 761907776 242069272 983638787 394831894 66071026 326621291 563634065 109156370 738430166 242670313 481389528 497877236 159347506 864971532 731019478 847753726 13821007 111887589 398394279 714845214 356830784 490163847 547194158 926803525 688853355 686630135 666042147 370489577 790650911 301063419 94878492 68465036 765989126 51373209 45843174 838303962 114157710 794897011 54586195 365580075 805414131 428675295 790292558 684321364 95408501 287113981 675727451 737996649 741570557 756363871 437724761 700009664 407157007 284292958 754014777 332673677 10658497 434475037 143460674 684764198 91585705 720745993 806055000 772091089 95867306 78178096 788641191 483251895 158402543 380849274 786036979 533001290 477398377 254299370 359714284 834836577 658934134 866336712 20129156 309610441 998443663 333217236 412827444 171539227 398342169 93872168 738437620 937992552 261393185 149872693 803669288 341579114 32735831 804518310 19544671 5935816 958587147 926489356 442927706 930959581 104030869 248493797 804670549 577984121 107752950 768705635 440341459 708174267 627526365 716043249 764054348 513204893 985011307 814217133 238510485 928172119 258550421 247077338 217753009 38013419 804505760 691150065 938042415 78232283 911293755 287958613 614270984 606298328 68443605 225914635 75346946 739106497 61065152 564781250 367227063 653244008 95101093 801188674 474917439 496923941 403754238 973197648 517735901 543575062 242948975 88652330 411067118 347134054 267412976 292546781 444460203 422161716 61492440 892626168 658644929 795222970 284558665 875872869 780043393 94632575 706346528 544746874 191334564 728103422 416599730 524328924 458570840 571884314 141976892 438105564 464323999 743494886 857909004 627972993 6031936 272194510 234206823 250147399 477070671 561044661 690776022 866413760 53035347 734790368 627766363 169284232 504365234 402498794 452589336 898202245 996957564 743322616 351074698 908516642 964190487 96870556 238185519 996531953 242991423 668876087 55587372 237635619 988724608 364348186 851383134 340207127 360004500 555662096 533939697 432838049 840413780 904647339 230313056 350813649 728964834 283859398 739638711 589706572 785130846 507453982 729704039 552413699 754291450 574710076 651871554 708687877 791510445 829786436 964933817 207165683 571987547 857915481 504901816 505477529 533378767 844838506 873943759 197558643 231323506 263432207 628399002 787446087 758310227 812146040 631961064 784451269 250892449 344622467 679281398 824989528 276996592 814186053 480973142 181974381 495565160 380657943 421285794 885266602 846575102 225489754 248876650 191631824 224180457 371465359 572966498 981673895 136356738 534920638 375660346 774408289 13622921 151337661 805486326 59878562 645470383 142866349 124650030 395337833 758186427 657399134 249966080 479969150 867433208 456478873 48571883 384417811 482566890 158003819 143996171 501981092 682795397 468698809 351276661 965137452 68416688 298215651 262187877 940627256 962542330 711225527 843943254 226222805 554078569 703893294 834659119 527238646 284337821 910660645 726757100 38045097 833385671 147776060 476918500 623247633 528317840 491443571 494804403 132076582 811714128 271212981 617080075 868921840 741443544 176048183 422374026 11318121 978372067 257696310 307904184 616272453 554575720 930152397 428258926 296826293 225221766 415063572 748175985 586643416 856648943 806680308 899627781 541891968 953058309 881930077 468087679 744175569 558568960 415712328 681511095 643351369 269763457 116795221 123763515 947889559 837902779 825862101 250262247 976476782 591665592 205497500 194561666 822370214 258606372 726834383 686924982 484342195 297776873 315319347 58046091 511083009 304385932 515348766 565905803 569304185 343174161 608041521 376195417 904201770 256755959 333592448 192095632 956673237 152884550 529627628 781461681 506642972 861600142 723712906 402066963 284224056 153713089 186855071 877229694 288658011 534590100 182603603 312464148 521195052 698145393 911834350 563462384 880214109 424272165 746180072 681782733 17885620 109718181 923972047 109575199 989148976 483464149 320186789 261191373 802492184 531199587 347778834 371737896 990935560 420513897 371133613 766622957 1979038 242268904 305795473 636515243 121343969 863181122 881843029 651611105 982206401 76060871 101482425 143962530 500121629 28436129 56889756 109107030 44936098 237657660 348802854 312470486 837660731 570866332 129711682 73765814 644076218 196358667 728941082 493722617 916814348 851555692 313643500 937706488 618887123 756452191 857541821 302995568 882023795 332531467 718823924 849168062 59876082 830774605 517577186 691569088 993672927 603355880 588762638 500380323 371117505 810307817 281199146 126807069 980171053 630890551 896125755 309169160 505517884 639337069 243386995 687791764 249556807 544556241 612786143 782275981 753572342 685785951 486522639 82942187 697925082 377934150 992352350 208152400 241221476 781635223 953310653 691618910 956379747 78509850 83240782 560957156 330681514 17111391 837618019 141751388 332100056 109747890 767062518 930168275 763907052 846223074 148501920 606699900 305549736 526166725 769190705 441262535 854824675 58186540 266909781 753217885 535632036 596130234 506274268 771929681 378479320 676899271 352955239 571923863 331451644 752403884 133406483 941467182 65496058 184428394 38934976 659553202 750326891 388076857 600206809 969351117 537511881 203142585 581850575 920014916 421811645 350284483 469038062 233711296 990989644 291516199 382661540 792158558 76592682 499493547 271397033 32194092 840758142 789951649 627901381 99537366 178722106 342899908 249832766 5226382 173376436 310295824 254142092 210129146 112733205 588951343 773059351 966329169 795385714 839346344 600283870 830067525 515527115 615293804 888039767 504591861 472958517 30316913 363927263 266460738 288629716 931325879 85703474 744949087 438031441 430312214 307287065 136372150 666174444 189652967 880722734 313754160 393672694 329899617 842281799 918241481 562836069 115212315 229087762 688562392 455804489 950637694 277214058 326682257 93558055 245491456 531341505 773576649 563404997 616078748 18937917 71705585 655997714 88802562 859920378 629453590 739914658 276797794 433602044 714758903 540371347 498838460 797957909 845551561 76104366 761345163 34168875 563374391 619913769 395093830 740045114 694341812 818857689 981570314 405027715 921066502 806670170 515524443 163032594 805518964 751512080 555059482 479072180 958714695 469525471 282504284 917375619 165162451 184497893 473627873 301585408 882642786 960781699 144052002 666943566 969860203 4609201 923659279 991084003 847656269 567567441 182666800 980698897 643114515 667199359 794207939 198873337 859632525 583167206 718476883 686272906 348470988 788547183 433553243 499182501 161457894 16909409 568418268 993997738 932936747 153644993 879565869 363084414 910945929 246242400 427163034 851443839 585955760 794170868 810685008 192753841 118288966 816964546 137553052 176337893 657755397 664826006 124907399 373923000 810999107 383025652 807492792 641805451 1629156 20457981 684660380 205661228 17355174 182465193 314711602 175889973 82266345 71580997 869383993 567750734 207622673 720629056 487847810 48624058 49828870 134794098 51891213 641677722 384036785 623327899 623500337 299736622 611867425 217293824 9253719 515771376 160758905 476640672 342383812 597770714 823084023 308311214 828021828 877641718 812974843 639663664 122856130 88567736 813155502 960320516 125184239 751263622 492548114 772803642 345484088 375677562 176414258 542472927 192084424 816692688 862915519 419756025 978052395 898019656 103400679 539216081 883440824 556177854 534637040 92064952 555807072 286525842 895700974 635093862 396668649 794778462 493322372 835059728 382622833 439459587 684417303 610330611 434153079 310016695 273896738 917859412 926148649 368563348 343162742 25667247 185465964 111793327 356589421 550652778 527335713 990630384 536592901 252516346 446485041 930636828 102457474 422696438 455657898 503660006 885435877 228812143 714460353 858919454 252196474 834572492 582977068 667488657 462132479 24007563 700534620 102093381 564993694 792469385 804962973 627977184 488315590 144482657 41819646 986589482 990875291 934994187 612180070 893283816 243477002 623896291 229971901 944052122 760223005 998224628 236495248 466250429 979293718 127069747 597326984 509270157 933863830 859969997 818825358 197999122 942127441 631846095 538131261 496347447 443956226 843419272 848111218 141505536 482733258 606072560 611098306 563519892 281252871 444976747 109850590 7803110 220353564 748032297 262270587 151571065 437769634 921921365 530899281 493118018 258614999 322361051 935591540 115975262 131549581 939715669 49619745 99590409 329777182 714979390 876012283 457296789 374460337 371002541 731961369 934182360 41056832 229720543 568320451 297824693 75454557 148481391 49616958 772622778 697383276 686202368 670520682 402973705 302787309 299081105 329219524 908319224 908075916 73276576 704652305 834763785 73664842 155997858 541246305 270887577 106916059 501630985 405294232 665498566 14837203 686141922 207784114 976718286 534679499 743547175 410281422 16999404 748810073 643871866 384801888 716096732 855820142 180752163 554090961 433588350 573607498 174653157 178367746 226104252 997380975 604908990 562342365 397987207 278073301 984417034 666289938 610515506 195330215 673282438 505839393 199632559 789070737 149226760 732887654 704722121 629290949 533544350 240464985 566649885 217381471 242260179 125244834 61856813 367325125 767083835 727723418 844290057 656049131 620342536 525051226 649184286 75595256 678924562 365514389 331930337 685274641 888556434 615321582 131755765 798212578 573388006 907945351 854230147 209725445 706023173 240588990 262988997 239824581 550521761 476186621 634196434 98554893 818965896 38298633 569186239 732972518 884299075 545439541 824044735 856820764 150023776 267462964 619244757 652831846 79129570 35113258 365432511 251133547 380100233 567556174 694969857 899592529 224020021 291657669 728805705 643377104 815612769 10577647 273111658 239047706 963091077 366699447 432705864 997216129 516084927 934792767 115136862 710784620 146812667 739845394 831445677 608444998 295210711 71094732 703752649 918907806 138817074 336404909 837596554 4708432 950832293 215611167 290259580 719729693 677699369 153958870 392535034 225939331 86855309 695971046 15513573 964267177 883189903 245274268 611255498 693659984 30962299 432342326 520908258 92406863 870596744 531941226 830102751 356037879 167390573 285218116 303031767 745528938 763609381 921766511 713541659 775603051 188674079 46606796 729704573 418813160 776028828 721959850 425608845 722550770 965595811 230842078 63704292 914462163 914095175 643498625 640423639 507639216 735236643 103339053 462779649 26681077 746751948 9406108 420958012 874473926 746542490 460642776 848380227 669747594 367408401 748773208 915839032 255398493 822289782 641705965 792515048 65299957 553701485 135882680 223695502 368249245 621862576 678474474 824421089 430785703 379528078 998378489 439117393 645555358 442340622 320692238 271686517 77866568 329116831 604137196 864996197 305893760 674084567 271174493 966415234 45101039 196291854 975197029 962059379 783019916 619964037 940814253 34884727 150024367 345219238 352869029 354046072 79560051 288610471 327770091 714504255 448999667 953854509 68445056 470483451 33377137 852040102 574388947 39533297 701333345 32567576 811986566 757065935 355737808 939555702 244234363 98855205 158475723 843693924 399889200 441207828 217799205 693081690 59199513 426613840 905013490 449757350 536665309 403955860 818047411 575280124 29075224 891386384 961797417 411584213 892738631 821247728 695443521 579690188 456198467 3285029 855131790 599542074 684031335 914105292 682620755 392166353 863946369 46269220 165525991 279171825 411465077 103091155 722099752 575494132 684105203 80136843 550349220 454753069 310686619 800704085 874962836 637515576 275983307 180882739 962816221 631745540 896941746 827634282 159633656 890099761 44007510 103806006 175022785 585110647 869515964 709103874 425253741 383782998 932501318 860583394 851403805 543583899 558245701 305284868 943860326 31228315 292296146 3636182 912290699 978318831 648585852 308859370 356907215 141772488 388829164 428993833 145675996 842630480 44120832 957717455 544997112 162068972 346354280 395481322 849185838 706981351 398107063 929322338 827385629 549412864 92000833 346659189 266476031 774892017 390993101 636625204 892194665 691779632 353907956 531643285 622626413 406102347 767836941 266813117 108539070 540678463 982753847 115452521 57184148 13144496 56408932 759414072 945001908 669187704 883244513 112924190 531380819 577153174 790235988 129868009 432775514 347421339 767862353 318518617 822654035 968809034 743447266 640667815 435752465 292522006 667284973 810796543 845486613 409865908 199719247 464643479 452516073 75690457 654766027 460419868 778622326 618852966 640313377 701410467 135587785 162594156 484473015 902501566 115612896 986519570 594221133 714429972 713047720 43657741 994355267 586782678 145252870 513911961 723856321 290348077 47374017 83543032 174630998 858734171 424468540 759632537 424833644 920989679 416624434 772293967 742096271 155902579 268210430 132950603 556470565 76874101 357813662 819261917 932427663 366922578 153148946 969488609 475067347 784069382 548020833 793105038 123474351 261900620 147318675 477766159 200655225 725880892 529906990 614211251 18930589 160981834 93715876 740544418 255704034 429631912 539321200 4116942 234850509 684659867 712471635 263436926 572422290 802219851 355952984 663916227 322382390 357450911 912011177 850230022 206145319 45917769 864770073 748731898 263907521 530978146 699787864 978329718 290858633 713795611 952955384 729672233 253406274 55822174 345189563 705544604 734586563 874244093 726483018 810717898 336177607 832481997 458050045 464153423 85931262 448954063 649991957 456037869 515728353 547839641 492935127 448348164 387302897 227335904 243379097 375198613 244942757 234932667 832490191 805598242 927377214 951835901 922024073 745420121 473837460 48967697 671204381 57548389 76890791 112532128 430452920 139706368 855786913 635196970 864161898 89760916 92801397 793674907 288191357 598816551 317230988 349334292 240535427 64385284 205179188 457819352 553680105 66007218 570437176 236680750 685028709 278315982 802456084 447757360 612463595 257459195 204799850 350546105 921658637 474881308 972906566 702768213 430182912 427662953 467499713 957216570 120337439 768904096 236033379 878071476 290500953 483274733 971274922 436215664 419938725 623712427 789832468 590258715 852212228 837707757 944022474 207762632 303826290 736684341 76970704 84950855 142155812 238890549 256522445 85586812 601080590 832402677 200456893 370921403 982171157 816732600 77238502 377737635 938171414 639363227 524526386 187394340 709065843 597419359 352418638 879384979 117016028 173280904 823712047 862857407 154982870 463937457 16292021 35246850 151466020 277027746 71920490 727270785 839777890 975636262 49631270 313982499 172607741 913422938 280473348 472466886 844269184 291597680 896974841 526281277 362080328 957808080 354496633 468877579 757808204 936710315 979798745 529510339 110795598 467486936 527188295 491454069 684286389 219532253 164660560 964506592 715599090 882923361 845692845 744833896 437395664 662626842 821585848 243777633 181213730 309257338 887971443 697762652 66650491 371019937 994892363 221748621 814140244 159802807 515122854 740707440 434321104 275819447 733927313 923854799 549324191 721849605 345229510 618264721 25156654 907331166 534519688 520506820 611652401 756640442 846118516 608010624 931571590 452183175 620777199 950592839 182895374 498235301 829532430 994583256 981095536 315226133 725448641 593223213 700423980 124082193 795138264 461258142 862729818 273645451 905404777 545030993 286022120 529999368 220260592 980057492 653526454 490133652 287923665 225541066 245161010 220374578 42498312 332862637 201505659 706184581 710110024 276321797 134356670 889540738 952723591 926278757 521924432 984921749 744981999 297286943 46900461 872110656 268079534 29967783 263381007 680666125 502120006 47129533 259312343 441075844 899743003 836906145 745392427 871802699 375945142 42481158 191440693 589042485 181044351 148491200 499223996 514841 31993548 567833482 402362928 760271991 330071004 756580185 789789312 261336550 106743697 722221099 969318851 477422761 248550462 979289650 873984023 968734384 969150204 481299318 344524820 595351342 561548838 43580200 205254231 942230382 637100336 355377370 339081660 525542480 755818388 460839912 675226436 496959811 251906358 525803788 428242065 421746296 528698788 389460611 318348600 966495796 149732210 307148735 932409718 666539329 172847274 719791396 361207265 184753963 36139453 541611270 449930959 924589561 181376722 274018983 780344364 572575922 171695838 163899496 478273543 977493786 65480205 193555601 202673681 507752576 847641891 100141929 873191549 840042598 906189942 346754707 734397737 86830893 595652324 460852126 9952226 985836011 655914649 427139400 635150582 833304360 99975545 834181158 722870151 530408405 181599462 762736820 68407902 597450302 92372857 358451621 875292311 561967353 814009442 972202846 639770092 890630514 873430292 125400242 704073365 316604585 676421241 670551333 418217651 466722456 846574904 282247932 391871399 58087914 376454696 463746982 298868776 976976674 61040535 366805684 683312422 655802743 329502079 689619904 5405131 469164896 594072370 395547898 255737110 247390 618457427 429798255 175561828 63575321 468403417 943348614 484227503 151270464 190657332 97787473 288907180 225063168 908967312 320063743 759788245 901795286 896529479 46811994 256459397 529752914 880017757 829475099 476919828 195522683 145864494 375591394 989091800 830310368 172538111 194982323 190644914 530458700 694267886 628923418 412161 269444584 795623058 268586111 670330273 282256192 325839124 69644185 458417607 804901035 248306591 483499432 298558446 858155952 32057429 581864107 339145196 731640912 762348645 586103650 369497749 865254837 80404844 839663183 577640038 862825836 51208374 924944209 788227093 264567836 457056711 318310822 272511434 346883799 674002439 415646354 190418613 520231339 978329804 395925396 186997489 231497842 689678171 728429623 652211063 665911577 518371954 989511236 720150245 22725293 625414795 254842142 553598759 423412856 971751302 779809502 529171899 428257661 296437387 979825831 642488103 979833358 238944062 678114164 8814106 124051179 101986426 384307269 59471171 790012485 285344250 360834585 116260702 64549554 741170095 789898002 198297523 128032909 989654155 898233387 967725524 426562827 574299397 929184243 985776317 821512188 355609341 553945438 701241108 77276060 381729399 317707140 211524889 407025289 393828170 396680120 761284860 361632388 478386912 630690214 310439296 163395046 441444421 922863240 534652420 163309539 470399118 913912502 48091865 83333425 450363689 721937111 887788117 435607225 56574160 384412637 628640393 144467036 698279953 347711838 705506248 375380480 356546006 479419578 103487668 603042176 989855646 638334585 328881903 838398976 285168994 334801937 797317577 265672362 612827226 608884282 188542430 607039363 657875716 265228523 952893825 519771455 516172150 358634721 886956010 997406835 376282678 353253777 369501536 185732091 449349898 471416198 6096426 626490942 8360904 914462937 47108001 349737097 283946016 936603302 984604553 890521294 612553987 754555557 963369908 200141012 990316090 262336049 729140530 714702915 881795138 855737952 380685612 801160909 125961336 438651401 116090302 190157785 182965330 385866258 826282546 746433718 830085090 386738468 697576714 708497349 720478694 67239230 69379392 238815170 835776922 371225526 378683817 759439729 735444293 417844774 500219553 201768534 995644835 929852617 729538307 289002106 111154907 570399186 649775184 794880034 555027640 351270983 943065642 1155141 486752699 221850921 263213334 469621724 676850881 699056409 177776401 625908913 604150869 197176326 131719936 505274157 466817921 270075056 400118939 917608030 198070991 472839733 88617802 84332651 84718287 259356376 327446752 238605484 210471113 289764277 739771813 705747846 549249412 312420002 718440477 868392261 787752690 13920222 845101261 778989105 294680524 58434680 617971202 819689868 552714905 556241095 933498432 220314037 560650287 384143715 834955976 848649491 156093369 885279600 162054426 482353587 528380693 339060806 993827664 242884242 210780165 324012815 376646437 392383784 447264495 656866425 292539644 744275880 328032706 639319996 249713588 492880060 368716229 660562932 482022257 650761862 267660366 822123085 195430718 376024430 938531631 508369043 450057494 34193616 596209830 909707048 603389955 596474181 522408773 187749577 700692076 105900834 996473295 172267267 314579800 246938459 34624077 76963647 269585945 633216561 633851849 27303184 334200337 402084245 392899400 695875533 763368824 510158881 475459246 266527786 550684652 745589179 896041893 508412622 481322646 774112598 699497356 995628838 149168370 354226936 410373517 385259563 756043801 890298681 382005714 347313360 287949233 898296833 734810146 893807033 408641137 855347409 593540582 506184584 365231536 523070680 113127426 60080510 603106622 408227684 392754542 19462145 499838015 581016541 11943009 738466863 552406133 31076431 240067013 537515641 531801841 657967285 662163607 186109631 932861516 333173246 581644340 451362863 377503351 351675249 729175058 565124746 674652645 741767926 784641490 901602465 940753610 597149901 576572608 281751459 31655240 936518661 856266386 149349282 975548181 268306862 774913316 263145101 495950217 733554306 339958177 807160748 903462477 194481030 344892460 405569832 693533472 504291248 515255332 475720832 603838420 753355768 11343132 338624802 710573144 689000604 361209141 250871549 77528717 412747859 526294653 408261256 408759189 293615804 265267445 535884908 493309088 483664369 76892317 593690986 282262940 761197074 631584088 691283426 282008897 507076539 631159865 663739470 789178567 448099282 42304378 665441005 897916457 867803040 604704285 681496408 862186101 484938791 535933006 888396662 214234036 836698679 512538176 644648894 729983934 220155564 562071318 140771353 2736311 39293301 255258312 319216992 780959466 903110217 216421542 630168221 208755075 421247021 240322392 573627324 401644822 617014281 798610238 855992966 526835125 884903651 287251768 963195813 190773919 735146235 576841397 254992402 727920174 127239423 872797279 457135537 103763524 378000971 329731520 77557632 458889069 323599946 363446591 881612946 614184351 312470494 789220592 906100424 835367296 732088977 301900762 715465689 784352042 814218758 654003855 575566621 983743270 946908446 397831529 672957075 599759946 93823715 876468660 905138967 916350816 2496021 543911772 860266449 980635756 171609660 395017609 963538223 98346132 240185849 518554994 956904871 474783912 359131513 199865043 865341199 179772441 261387618 700862239 627484172 886259375 447453368 309979729 637049015 208805388 762034512 519759987 598849146 918029940 753864035 586436965 473927148 189505499 19027776 58745061 793842836 6836717 406599688 987370943 991120516 624187376 960131201 580962075 738034289 997729662 928200193 203697078 750734963 994257844 567687932 625312689 318220759 682696842 284618998 782998615 639629129 507317337 4540118 25659790 107184164 547488908 565951958 543335249 820175436 546936290 585702413 372833218 716794457 826381810 555157150 287478893 39106795 940298263 673548240 860955778 703387708 65602078 374343228 23836340 303585921 234727399 844662124 687556554 626125643 326228984 693203180 517777477 902302525 185066256 160548267 654203309 671722264 672908076 128035869 316267114 577081765 918513991 103291318 210723220 71261661 367889538 276568832 91014460 380482455 231261898 163375461 164315638 748075364 845733368 698235004 978313187 595739345 197666749 262525948 745523009 545294490 68595892 130689952 144514302 179771877 709234643 440330278 731784368 398931119 569156685 466423502 194384094 330954146 745746496 301550861 904425052 343370889 407959246 961444273 298316747 8189231 373569014 527601213 464342603 775351882 482964722 389320374 458674498 124719786 458175086 239977586 124507695 853982415 483692263 123178944 612252845 742878370 205755054 359744860 721807789 164521696 922512556 64093471 834669556 935659419 454196139 665321775 528312514 231993349 928590708 270974136 169957134 875637897 403761920 313240395 229794539 476224812 640670232 379250806 459812460 640664008 866960427 424938081 671273542 234004803 483029923 628646631 482842776 38416145 660924437 606330479 750571551 892467358 623122522 107857740 513242724 912850778 950741159 605675067 444541511 82322547 218555224 771372743 555525943 309225857 21004618 273580356 632214715 670439867 584240771 86187641 853800003 571702349 321062430 821010493 282502497 523639691 318207066 814406748 689766962 11543340 65295310 129871630 863497518 230990804 810953708 566391421 539138858 25702677 682385429 856579724 52332012 56437887 967478131 736260860 989393008 646071162 697730985 771467973 286891469 640952339 625288410 267311871 482985498 345241975 54583978 541217775 702978163 153086915 582860314 539226102 925068469 20751045 610341694 43635261 520052670 894230865 863616223 143477170 706970943 773348263 433433365 281061904 876840289 414350068 397468997 92494985 103133684 405242317 280410960 952642387 927510730 806722542 758496602 913038569 614851304 228426189 403917504 486313108 724537780 170333948 462609332 19652337 421036803 492493721 644835418 147824382 785213302 699734406 441213135 674772546 542781973 388167417 761877059 344263785 253400694 729635048 955215278 57084711 227929266 70893496 181912310 458180541 829577027 772032726 459747712 103594771 594420420 7693789 196862188 699234770 858636044 89280787 896829604 402324782 757096918 480195120 567207037 726889671 267235475 995824744 334674321 842136495 805908024 380925387 477511604 899403610 447962046 196975077 262186887 235437780 964222302 974451592 558119733 383379683 715368861 166454434 371877878 690370871 244427024 949998860 440472369 101928694 204693976 209901984 578383824 415915832 319738550 185105048 816789882 78586428 811863721 415977074 296018594 898894006 157547972 603419571 618953414 422012939 236551383 190803805 843447337 482886473 963999811 330709433 5774938 413953135 135449489 418649664 259441431 132358505 390609821 465510564 210239563 1065214 948011661 843122170 356698654 5290221 781936871 504710733 622986272 493385806 588983378 411851451 154004447 79869191 838803612 627923558 621589751 658805565 165009591 598541062 291969861 803781813 256723427 534629141 47932649 919622952 47453256 222032890 658023976 49743259 988868980 453149898 883703752 519453365 630550840 674852609 419259124 920389000 820812876 96483731 316458808 469843550 96301504 828160110 487953739 951753534 121585732 819259424 94168115 978052727 596974636 625153238 791845489 573594102 361988661 19345156 735542380 350689077 890150877 884672964 848736101 974049546 597978291 963305580 441691599 812684938 992745607 316009957 597691874 318994600 523026635 691782859 177050010 24672427 965131316 859566864 629412768 81087573 227543853 187300210 122442393 411349699 751087824 14086435 995527286 34947788 172535870 508730100 690616736 856458585 963115392 654945255 423625598 71149640 916156171 64421655 501533410 112715077 563044101 770915723 675053228 626002727 64100055 381123582 758093827 672501544 707567452 687746124 110432642 682652763 904167675 738394465 625447308 520359591 911007900 31416477 322315530 850863499 409732800 513991871 807226418 242603256 568792744 254123224 423982998 543064535 49003518 736804212 146164638 729050013 167387211 145570789 969407826 145438789 648730992 999961060 804416746 661730662 495068236 368114147 280469369 505052776 516474470 12742639 698924381 12293608 177876099 427704619 495640759 730434664 444383636 43136399 511783955 298194032 857362298 57994330 831256488 919080514 309879816 39004990 83052283 505033748 782896717 978761865 717906864 158120586 709574490 24606217 516950075 586527140 865396204 270911370 247719471 26017886 573550781 595206644 923272461 811805789 9762554 295347922 573649846 688279500 534709038 451266757 630512531 277355274 847298278 601751590 23594142 579370235 265502971 347684444 138593074 633890406 940446316 823758352 862143357 893825271 227908380 538366586 267173520 670610079 801049110 566750465 868242019 496032408 81588205 526180257 920304872 571629503 17631774 563761632 338154530 536902851 99365320 257287910 238966171 302477031 393313395 257509028 47338567 11130778 954298330 293383114 195792232 456224771 221766909 953296332 727370766 732520412 347990583 103327193 751024269 60417173 924616789 964948003 139551790 429288672 83625410 11116931 941741834 541276975 314906717 776163418 852974831 569845330 846424949 58046518 801731126 587295595 448428476 580300046 498441101 565089453 749047942 464163975 516721294 821851602 522449131 213188364 979548450 672550800 457760687 548525422 165777112 129938815 257346835 209578786 9940432 706486325 439942605 569367699 495212990 639289871 686292294 675125516 756034289 387686241 20826422 888398313 117535126 42809330 129884359 464294823 642031386 304396288 1453320 668219847 694123211 105068377 64074156 13430708 373075463 461038640 416655336 683673965 24580032 232112778 796275206 220783793 511714597 254837759 649733514 18694437 495445664 494321110 333014945 462056131 987406004 97780124 75488716 654106228 409230333 944286286 349088216 813221705 227978404 715968638 945045718 54793586 638920389 639783143 839619570 629968732 580568291 328272379 243207706 824203610 292010042 993918290 802176156 123439505 853098969 768484917 390962785 644144144 92528748 576924840 668016635 727974990 544241135 480697869 228762638 931922930 933622874 349798006 929361766 537406443 925019342 502842819 259068081 24794641 648865824 369844240 625203444 594082293 980499794 78992417 969993418 657861673 913478862 292788464 666854103 264221816 625261497 496552047 521901786 157708965 530062047 736832906 343512265 436221341 88523776 946265767 291690375 85218907 292166756 48167815 288161744 745297071 824765458 519595065 123855021 38663580 875112684 225179339 213404431 298310563 582678147 934023574 496622965 412069394 703691226 847218192 473410310 249132318 214163845 374000675 72698819 862936172 964632947 965324990 552153228 575472780 690382656 983443314 208660708 41827586 25430767 416863998 448228147 564905796 362398457 383146303 607562804 216565776 282969294 217824209 884071688 320488063 570533136 262512308 585307723 245664354 180929145 231046730 97786876 307657815 743846328 622433646 339281703 524975752 975741573 379070715 422599902 594748159 762921376 917745810 356117494 203053726 150344154 864408384 866363231 468901297 287821724 570782875 523457915 325506925 105699410 484693793 987759192 384671048 208286540 402581977 174210790 116884521 669266745 590110245 657708003 484385375 600122900 729923939 341796399 220034528 28926968 262436814 208318855 584415759 881681378 415056587 16723386 288630299 553340042 237921517 57248104 57606736 636548367 768661939 835727718 274530638 150046900 449699933 149431236 840602550 351468939 148985910 496556761 115473687 410767628 512438354 211640455 749854048 149927901 454329584 925974346 446038611 313830519 493232599 433726169 712883852 286487684 683919192 289848657 945662728 705333291 817939454 906684451 389582383 195230226 862385175 453776716 626518119 15850106 337961533 659177540 971955162 803807670 798758137 823730057 101612300 861027859 648741102 837727399 180010863 250223937 587813213 166865027 235420938 695560350 948252617 225254454 216354281 885461708 154396821 377331106 197857024 985205332 295863633 715835438 960855366 997270165 268907521 392845239 700972655 76961690 676636163 840943391 862554568 268764503 49889348 432545914 140462132 377887905 175286957 267523044 131087326 517622510 475352489 975823417 924930958 890400434 164247304 444868880 754261425 369900902 56477337 98309959 239359817 456456046 409233915 282137775 320660362 218533456 745521066 511999369 348799206 381503404 392841313 262293313 482115278 794808752 925870818 426265550 174053349 112567130 365186143 244050066 323762113 374441755 507832510 626648290 904301779 323364754 592961085 892946374 618088861 820695617 721189152 375229839 836508938 44614106 284800508 559365341 771868715 614502118 609981621 838476379 350295041 525061732 947163568 837779488 827578057 400031865 612628167 167969344 586666893 485373889 961036384 781995990 26395886 480176216 298087893 241130554 414025379 704181537 791124963 456417248 461797393 677539953 126576020 208567698 850365257 636483368 328776303 11587858 277869346 432226660 132218674 539467401 153889426 67091678 264623969 954411726 287976640 962448922 545520623 400006857 171840045 783410280 274329298 60677175 942801469 624155496 143600155 640094745 413812465 610772550 865978289 118823448 346678691 411867790 627080733 956119539 975377712 885551110 936757049 746988682 288949574 709484727 222980218 673518386 591592264 829840218 1214539 861588612 927492885 823154655 766282623 604641650 714174209 540189908 421255965 580067718 349073093 846883676 125115011 39911585 557677112 979059091 785646072 289518529 372540942 136741900 779564478 419752553 655135298 485472483 167746028 715498557 193408060 831808998 188471400 443151542 896500873 993361574 32797457 562168205 418377796 873289288 931214530 225027842 319707417 175509313 577944532 456782014 9990929 369952090 1027563 268039904 248045642 343642239 781199299 746876094 344664919 848212425 201745513 575474039 904584750 514693161 998489534 347718483 770839260 839313690 48893589 853922811 67177789 681224328 316643197 302207186 206718357 351208356 1237135 39471068 910085921 38105135 883369347 810035898 752207778 284265256 193556129 845198599 571940534 423388125 53724584 525615966 304256292 126759237 295351115 584353067 730134416 565007564 904642666 83147527 185735425 565511364 174566179 851452963 712985463 608189533 106839724 562699091 736739484 101811958 26486010 910621605 798296543 48400301 855740767 325062277 864377137 989017263 380796791 689651994 288285815 872173932 736815665 997648084 938830529 14886327 536459462 794859569 111350808 533959821 809914376 472286354 343503744 304330953 12109809 116258133 236241926 326905647 951427701 8695459 986789355 347451452 776215827 827285866 204501340 123187979 468778318 458461350 789119211 357651046 533421664 910129054 825774146 189717902 353218968 524564394 451679623 964160888 379807079 85650191 931567724 935318498 772430107 383303224 861907485 373697627 697467653 497599944 848343951 437024403 81183075 381423565 134883655 444651701 268260605 230320913 266882684 212355292 938051587 651038206 913635499 193897920 395533927 279794250 142014719 59819441 854459105 325302183 328989002 172387824 716042822 804614438 112130881 844160784 509670136 289231581 747541284 484671853 982967313 373832287 401931987 542987002 742513681 155312272 973236512 465494272 935794102 372920137 61672279 372476547 239899526 974078998 504185890 864826384 156238065 872538419 357864008 290208808 538788414 791979747 858751247 296518030 353461081 641186192 165283044 728712887 300548154 278299505 931463126 285858029 166488720 160269539 900913938 856659754 305700661 70282059 805095903 605674175 446761822 792228183 50184410 883735452 840894045 88786386 15836160 168737940 839940471 833294357 779321733 764279023 154316795 718466566 932499566 795833796 311794104 191367235 284453622 671874122 573383775 651871695 868999921 988817832 50833839 983550141 630179039 9120045 494785007 613905016 540597520 966960897 90366758 605392452 414245965 160669655 695424425 24728465 918261694 807229096 666014088 465793750 671491701 690935371 772157715 809704134 991783972 824737458 902476539 178994406 161152933 291810538 967584223 24440173 627272111 450357365 205297605 928356294 606302850 508601130 264192745 36670500 135332298 610621441 386004787 983315638 235388190 309595352 973540065 329039904 986339029 223383226 331541085 599716249 869872738 353011075 223822211 514482224 854138461 241398233 670162550 524598894 118484572 613117697 369585797 194953932 254738759 183327534 997514708 655515672 999149294 167947885 731324652 401315431 798379327 79324169 917152224 308916701 774747003 731312692 221388568 623352448 16395995 564016757 440457130 715157775 542509546 585344857 164365488 684190713 822233532 259347549 660200302 668649751 91798875 783330339 710573368 321965984 886798960 613698060 19095143 476105424 955691031 687355167 117594124 87519122 705470925 902896263 282535949 614694626 341685502 310220221 455147696 303193229 168103927 933435985 389863405 101841692 73657856 659152308 59717743 505691422 41513571 136233958 679744848 790797839 417892603 743891960 510863925 344739141 478911143 783517179 967160265 78802161 580054593 603097649 659532245 554387150 488165589 244797768 169035729 869479503 873548511 705283075 295630641 819524130 755285334 746521136 392272976 348570554 70026528 843488033 868801394 418940065 290285707 214050516 919076569 269668563 401588459 931250797 615470857 346765270 658530753 872305811 559510342 316880859 792982290 447975089 452272457 157485656 520342596 62016747 608330334 321091024 330711074 918644823 165480299 874798603 151458943 880491374 869010813 578149027 295054453 990216128 907733076 418525596 459814441 673429969 861540855 400041441 636040959 144833204 158149714 209628664 751332787 743789141 356019319 689626017 70865154 176045424 990569682 470191552 370267040 865641994 342378592 684956999 6359193 106854059 360276328 824917207 806628962 764279717 186083244 910035123 994807032 979707953 149869282 921390242 510792266 454396103 78444936 747309239 172425065 375953822 353703601 885659728 126993621 342631495 832513025 697891727 459273235 411173686 608258472 390818543 129680373 178375385 225793202 98684703 840090615 678567320 500103492 327273030 42266702 664297954 839079950 267101412 790714591 284993678 686032557 29847485 119423294 800205834 830308351 552936723 433572995 40805321 482570295 656295305 4901278 158454524 938338350 793372411 106208448 141074438 213880556 510804412 30112330 953306948 309303880 637291358 544426725 388686929 156938909 321238684 769997326 780179948 87779469 868530615 403608391 442521148 451501156 220868051 486504498 634467188 457350671 488970596 540982733 765636541 987362270 426171028 276581766 50460635 568556677 938725894 312337228 466138289 584319362 594285350 726002952 123033207 507349947 957566553 46218708 868135343 100066221 334720912 638058520 390815207 946539457 539051282 508702940 420554767 857384067 312591231 822027741 415055034 960219041 613270504 991089009 357483848 698795292 209339493 182316845 702506779 912264977 264399423 532838728 788469329 468914505 231795624 574508693 872189261 190538280 83436597 499209247 526703174 486859088 528981756 527196684 621315189 290079738 718982893 506146231 924048370 189192650 478816465 73622413 221404087 353691218 681769501 257437329 363144595 8889227 167046821 185851696 560370412 956393094 907944403 344028087 576546700 731864060 271097832 390472708 92760444 114553766 173836287 884829751 108472817 696790229 858483950 960558323 231224151 924613584 825232789 61139498 760786741 757329425 29572020 445461310 180810684 708094908 334828626 987863199 890657614 884538522 450083585 191554659 935342974 277373114 594971148 980580483 393424806 227918359 406756704 227620653 801028583 367715592 473741491 239062797 136521284 537034100 191221601 8765865 375282499 591735355 208078960 422355546 109815628 316959747 717533966 679013167 474279773 581680299 716280697 572383192 512101160 314420058 275756089 632800986 389945057 285455705 192470805 919070824 142420453 938261576 99681121 334916226 3656253 29930180 953552486 397714807 724400034 594556685 681195015 505248078 136349318 262529905 23272741 525496625 377789239 460236473 383673580 221902855 742390683 985119390 226596436 116933254 955234650 176108778 212064534 675887194 13167991 25086548 651173473 806573056 900985073 305988454 3314818 630207188 577959442 296555047 477851505 744743689 520072984 955915267 700268707 257134386 34896782 93831611 822532979 540270920 230188718 562954549 332722651 297869725 823498762 860682508 236154227 890629671 516132439 826083145 164657907 662896104 654233019 200953245 472270957 354371536 34570717 361553392 664782188 873552633 137965313 254716009 305231393 754604856 573276558 777153289 688416009 386602756 787771664 564849000 868955635 481496464 925559576 356245652 415131781 265016426 929150540 735652076 713817020 457344001 821390980 624178427 329009125 898897116 867048677 756375928 696037613 648344855 639983753 731114874 222142986 71294843 518434105 896567164 815080675 992309974 699861223 489477177 819333736 835350563 862454155 331117606 695984513 548489354 264678749 51220934 738268912 898287325 197039911 852914562 703318679 53185812 247895908 198124560 391752414 390309413 188452299 218204779 734315578 176763210 132198696 372766323 863117793 305265931 799205488 593015143 170729956 395534842 388388046 117313431 67472258 36542464 229092936 425816726 854876285 498578202 165486393 864106376 846811616 265506577 157144299 905722629 876978866 448106253 661449245 658867734 715977522 322423009 701008391 979283203 315362984 837923940 578144831 9037965 91514792 572004526 710209337 285839822 604943208 764935339 480107854 851161606 794474430 485459056 54993339 775615489 724088230 373718323 304554222 544620896 246213566 212892573 692145672 197757789 194987720 426571753 792668833 728221162 115214710 348010806 391010555 838755195 43503874 692855439 883601171 450843919 398565832 484011793 32198592 628144438 488128797 40104096 986530979 277617742 209786659 901628498 420559458 711732900 288523079 219162529 857082356 805994658 327134031 899348265 110164731 816613649 250488078 80452691 914052724 328673844 126863286 724709909 944398545 994154725 280100577 514953946 709340159 437585414 818872324 908739814 22225547 191875151 149067062 538111489 444205048 705392435 632374765 395731730 275824451 946118544 623557643 950771020 712364427 769224080 22733503 956867280 6106551 641629780 435150905 755753968 941651761 977123113 784737272 173537587 780133386 528022400 919389262 450740742 348982892 968372212 138326535 358911153 876550183 162701068 697393909 567086613 467221957 463898277 287028082 606764051 551875306 733598458 280391811 506917618 754183412 715872954 716541114 795725308 447566931 93390605 77534108 568840713 935586721 633524519 964393650 99428994 989351570 987939599 790904789 870411357 390812269 11683043 910787304 610305001 964866386 512625112 90534433 130433519 674273466 220081626 914992501 127917469 902839830 184585406 337116629 412500127 603019288 207296199 828749038 66093 51262666 45089437 444628450 372058466 961693026 537018878 827995332 122157979 310322790 907249208 808507153 266149424 415666554 255874620 91843369 342742845 80075841 752849600 349515017 17046708 64033861 125384081 9401288 100420852 331748193 339007075 279593796 265320002 120013123 412831372 534276164 143585516 465097029 679145010 282857768 54977182 26921205 175569584 985445601 412293303 874860544 73696642 523463161 613627108 704078368 477523248 92018577 960258871 800348363 678370288 930296088 848264926 517229799 607798633 583335668 582986487 849905620 765790481 27245736 983231047 391032639 583636180 998243247 442370903 983390326 648702063 179618249 925928443 356496045 843595085 962064437 123650632 140853510 986502490 877251136 583598550 343752507 585641904 899228874 363781669 191942841 674159595 582931537 662741471 641354026 461149126 851356170 943471957 359237411 812442257 271277699 8747367 200607093 984775223 180739966 597349427 956809273 999279161 591089048 571077042 45342130 746942032 392642371 531912999 699841733 712216638 485623621 465333103 515335217 2077619 578869118 89049084 294657205 686216754 386949897 852210525 715549516 60576977 864856254 618605695 579650364 801027928 175940939 87506961 866267047 595697913 916788355 673554551 212284494 618385702 268395354 555470099 414603089 683930858 608644711 256789485 99024375 456978310 109694724 984634726 110184854 38451004 181182855 420968688 929086618 88082889 373317354 500182343 228118358 468374587 818591142 824723380 780628521 88528789 37694210 788979337 564523618 252474844 371971339 464121925 126121955 2785951 469506704 15644318 396266726 680242403 896835773 468463958 720061045 533935804 241884530 570188603 346002094 615522253 674633841 636507402 647265635 264057017 458042080 261954078 806210880 847561427 506289418 478366379 913196379 92319919 719891263 792375662 524992839 922584164 201856914 354064389 856231617 743358909 793400604 217410300 980771998 829865946 461056808 971432451 836111326 531090841 832221356 597432795 734845904 510182260 63905951 16454214 237342164 687555042 547066517 783112399 95898375 55809502 702704004 935943248 546465740 448872187 177842295 79765844 708794558 944507756 279997633 846738759 494883938 484097971 776403761 908934478 201934193 337892855 61246612 824826635 921760164 313387987 766763401 895302207 701905539 19644496 504117524 40491813 449810695 543820488 378097939 518672427 430438681 712387937 535304886 548136874 653736952 744131064 73370750 373890245 852983322 884785754 896862977 903689473 845318573 848689622 153071341 58676632 314159049 387152735 551857718 922993955 688291084 628134103 38120736 132199186 636740855 630165369 227634079 506606419 280575824 581015470 964826919 768901381 851460996 961939552 825135731 299744670 258165098 857138714 19667718 914039526 567990439 141048288 952191442 531604458 701720932 859491319 441555358 411955283 714095540 110616563 641304249 331529912 345465910 529868555 81676334 67629447 280925458 786012145 376099891 454297067 796229297 352546099 343519433 869099019 435532422 957097908 507065017 645360657 778666062 586636498 730753113 816356909 907944603 809395449 511274583 992925818 557654665 376823755 233238747 676165242 513540490 52082568 499231700 339468404 710389788 399333028 594299301 673946978 692377477 203440247 929638977 436192204 311283745 791732486 351967187 106773669 359164033 497637304 218753652 784863804 508799218 634657829 331883576 136124197 55111329 21467511 357843535 187389800 484533824 495078317 261934759 843360129 482359837 367598332 581915448 612968260 177223640 510735653 130258211 12112826 66592835 883183742 557932810 599808196 342144879 369891403 894784558 810695302 68922275 706769541 811565494 131340375 440450738 748171341 100149069 603945317 450319329 525912049 347089559 6048775 960758042 133825308 246386907 392042637 515635171 692748467 84052901 868539814 892414618 319186930 891448416 402665689 992260846 843654951 657044383 316196188 110876042 192940615 538794731 237040584 902929862 932576988 463972813 105502445 811260318 517954098 446921756 307009936 120738020 431864365 339033486 284063495 212583765 196971478 746224868 657244119 352816215 468355520 250617782 907833614 207909728 946524860 422428613 195766615 852911007 169342482 414136050 285069104 16164701 962176212 413285157 643101326 303138512 540792179 153062993 120219482 438239859 716213210 23574092 651160540 291884816 858726317 151922072 848758242 641525011 279282181 524964135 725321050 399925444 905439296 5327099 163393094 978614377 871449665 374726651 962170085 99096859 416259640 989528730 883057489 327299095 719094159 699989314 650084738 413155054 544273651 720261800 971890141 144612424 767781209 629843366 320323582 971344272 21177711 394615387 928507857 891093297 554654053 57832233 953459378 476057382 737940451 637774240 85572175 40177047 891851950 806213711 112066482 886343505 563684641 271128778 600169217 7930056 449626652 751467984 26248972 196986153 283417791 649549222 439997904 66615859 513822131 906089071 764576753 615847763 303361220 846980657 794966524 831352276 226385994 478347013 190055747 150765374 16830387 798712379 432154947 585617315 344659836 751636207 760065421 410474565 502040456 697128154 486692968 949646311 645851582 145505697 713577987 857723205 219954950 13639875 723388969 743938317 733444477 4743253 552034818 784783017 493602150 468396077 935821505 665468921 354216865 50743689 287011177 949092348 947711222 646884292 26981656 876143795 546224381 141879100 583295932 970274719 502850379 264296660 965043396 749394198 293363162 368965910 767727679 66469545 307982143 99724421 766340944 212555874 503588649 718033208 982583340 2888252 235229649 617821750 372444544 950263304 455728368 386469285 62926800 769176942 756359327 6993904 858242163 271283764 255446312 818515095 399700513 295349735 94655711 735361140 496936994 90544655 846641148 429638521 360470356 901182693 566447822 675916056 921932651 226399442 463991046 404225762 299881166 202406010 554172403 232867597 317929646 417536212 538874081 321462757 677906385 790719428 535163638 291745360 686675545 161674310 765453736 206232063 811064502 551418313 939082467 568107119 531430697 63514036 895900252 636226245 508027840 441684163 634146617 411805287 616853324 350666876 339992516 742958029 567713889 332340376 714857094 332487940 56701567 919320596 325168597 694601411 795752346 529331150 116141501 797370125 762193918 759515847 563034625 187941444 982468955 768914631 815315794 361748680 772673214 640641914 105744153 131589641 566275800 100113335 916673696 891487320 563451290 387059140 364515944 806399748 605780166 953970719 319044464 934107750 951592378 564232825 745890814 937427785 525007354 332647905 483695966 630306472 224560514 864331102 716539321 932772080 894511921 448326511 125819765 336562705 133256508 565058841 668105177 139272692 764182550 95334127 400142434 827195685 446679567 446992108 374805325 225273442 630864831 926991379 680988010 827287442 108855417 949913688 262926103 937602499 319676450 506793906 430723251 910021926 250846704 229982317 512833275 394738855 168003846 232195472 665433052 514450077 510790321 893079629 711883644 992964801 570504810 514685619 398536828 917279949 655371311 746861880 643059711 132964644 423203745 792563693 508180609 923127119 261273746 174787733 182035324 816115105 886170059 555706226 889683963 788350146 478273425 808964785 67274914 65158186 331117625 203833905 672610835 911248523 375240004 439153583 95868786 84320002 832719524 660896421 798157685 446062441 329655465 653172474 38394865 739270210 238346947 461327754 287354065 35441180 196294384 602647762 222537842 9502664 107722017 112783956 157986675 552510926 577324154 719164227 852976321 264574318 52114429 17739033 557413517 363507609 168874669 21477429 195431721 906037819 709749071 871475576 614323611 692262710 797802692 906373072 618142276 975154929 346048596 117477078 463704044 803323905 974884485 884164700 300578536 33591895 280092793 193467826 122046639 956959791 635137291 459354641 491929789 104805353 263946436 933569665 175280195 396639659 615948681 519448154 756820716 829620611 15818452 880049665 86170672 210096267 890900239 185586564 213523516 713839624 19935215 485124285 919244551 44552631 8540226 708470134 88260418 705631214 860010792 70976240 556078481 965512360 854482020 194001786 101823468 356661084 240777223 218349663 370474756 313888155 929252703 271905625 369274010 613207242 385519078 949867458 845855775 863064252 893458264 821615119 326428834 237157403 697447924 824440512 994422255 667561576 513575592 95309059 973990381 530974698 889117332 761704206 429539861 795892142 265908744 66901809 391596584 779850970 542065164 70394729 385059545 643728964 800030409 359091508 761401546 708157166 928945601 160596076 334182035 296319132 617823449 570553018 8454795 542376988 262325783 766874739 10712305 719127050 747449028 303993199 899354175 384207408 349752635 324498793 945194619 923206147 63448734 737278587 931190050 484872030 690076238 378238180 739456624 177611569 128327382 3147568 492923886 423038313 899669587 431075854 34704410 757687343 671835126 418762163 864651194 586287305 301176407 472749088 647048312 934427105 261230911 240878627 363480254 392935144 259426089 930084374 630957286 302906560 822780242 949951407 834804779 915225421 168838988 519245153 445055293 707739034 897049401 992594513 124304544 602854774 198769504 794773972 656258159 129757970 315896244 953174669 8197978 644744525 185908259 192984958 516249128 476008400 472363873 191003047 102008065 4743188 290017218 40517172 709395824 769675926 194852971 923466435 322619159 921651053 823721927 60729326 320035418 813041673 915794964 903039769 546696308 265663387 803810 970810435 173434368 871350554 340233556 768609217 652497126 3074078 539476857 347811504 353294811 816240418 671281757 974807439 809450593 207086593 965526669 339000643 845968882 611172248 232568190 565540655 578895964 707381430 661342438 862171629 281947605 324574718 956916772 482268010 204067704 913469641 366275316 445817607 99548306 909840272 379490505 198300725 942614978 630787703 598690494 976229450 76170619 109752860 73155654 488952128 52097615 353196573 740245062 133685269 654994033 256643475 277482079 863603674 625832567 183497608 454970198 862656825 725309634 258347703 532126343 8004926 823589788 93830701 257919419 946422333 409254748 920826561 638910773 421842492 388623673 296450736 437222094 519113500 711908976 298005185 714031494 616313897 469447595 634551227 237734129 719774398 677332900 257145255 539179580 159944295 808201251 227309037 197101410 818198458 391421249 555160134 646966384 834035731 911627387 784970218 101142769 970633282 683110528 211607167 137393029 200087714 661206702 850117961 382009839 793610686 754180118 11805174 516009514 794100351 498926153 331999076 90813901 819438996 186139905 266430200 234389465 179121023 260589528 15962263 482836639 436209278 318502129 772485349 64031438 55323110 739745682 909908317 180895595 132929523 806609327 976156227 832652320 593826461 250295472 341442813 873665616 261509301 519827981 555095725 381890914 225501623 924700267 835584711 623776193 914876284 899365738 513645049 859307889 701700184 337562024 41057919 136534126 540042545 377659698 941892482 902534594 788594185 370026853 432441099 132895436 445531655 814154167 452921200 419555245 678784778 102337590 899851386 942897345 217792220 876872545 367043354 1808649 74296078 249530261 244666169 78204355 596254999 313382316 708175820 996629695 633202090 33376370 429134578 987930699 204614736 657587018 783996081 44458790 763002733 213146682 18520414 385058240 183586313 58393790 139745530 168176526 14097002 72796760 625157700 99344972 804955467 256526525 55837077 152999905 574762864 874622595 459894313 357804003 428593455 251668068 600083182 600124102 233443619 102065034 184968529 219803013 70726369 50223046 466692109 900823949 424228076 494359066 71435797 758853889 767976231 790507995 822006680 487372676 455037117 173111875 762796195 127847605 170362518 731935167 826824568 690720725 868971570 146229609 428185925 915303852 455374621 663914119 84836048 580250145 206667317 984899278 88838707 598149573 156294327 998717427 978953867 561872753 513466059 493318452 836700202 873696615 462496896 745406597 383417062 219269185 232153866 440554465 266024015 362833823 771189630 821079994 984376085 56924258 7205919 314763725 441397930 53938750 688307820 923218937 141292267 239092867 131806786 931604774 472107834 346373952 940656321 106661114 65515396 300140275 119902831 328001140 258384392 582398048 255510573 922341677 79549023 697620976 752851650 687431659 438225263 773158117 954099659 696624932 309573578 570789072 669386389 182022157 902030743 747012468 164887961 685779357 51500319 187038601 251775739 915454075 65644188 576496032 980322146 155304898 188897525 386656560 676338489 999784591 162242513 208121623 60535285 395785037 449372203 293088833 64598677 925386256 675225073 320323563 245153023 9143584 909149837 286848196 853639472 214886158 504989534 278783049 698066406 576743747 83143555 72098999 289906350 424471558 173537423 628910273 956570870 485244483 324517898 680483289 97260846 395714705 57127045 815455721 124390590 786697026 287852756 395099437 613542229 555558687 794797584 302458976 762595957 249540309 53206074 563843954 408112927 585392374 200851558 49734370 985566673 429319348 491492246 733951109 512043523 418246243 15486652 820928211 814567516 716414996 704167082 738472322 993203030 493137649 779465166 977231889 53281480 232224698 58961483 372567754 614191526 837693576 294719558 365358120 295818425 2888098 294331448 262364532 309560968 951963888 663662696 565446963 765919281 737413394 80094897 873868546 749850278 938604940 216584131 369051170 53118851 991307817 217287855 253065894 509450773 957229936 475135194 330443409 529260747 284507338 805092728 179112209 919462009 458937220 931561333 886549250 726542212 330290007 551439631 352157772 940599806 312679765 39407652 204345848 524450488 498757110 831606342 168285082 163642088 891121243 766266147 644895845 801758471 665116131 204074946 913803523 35898163 208493667 860169246 367588107 989955154 502766210 453640607 715243671 452139943 799594662 875435487 89297412 27672582 183214245 204056457 545726489 629103966 417673805 782806315 123156295 807908020 861571926 842272012 13836429 338324331 691082520 928789888 413084720 693893990 798137118 220083415 142717824 109254029 760073637 857500167 938346062 976719104 140331925 340751806 633356082 318849398 508675711 228392195 185577092 565689296 532447161 705025055 569737276 962684344 581170302 250655810 498875088 153497929 401171656 971454989 377019573 636153326 1968454 650785895 696929954 906440257 109989962 952769526 931049417 574652577 440293321 83983899 989470126 700817371 414633008 422072691 632741142 660417861 371856131 221416245 270767137 581132641 955192256 989252606 180461548 985574862 419116218 182208898 103849229 288635063 985374612 296860579 87632680 332448705 266612009 723073017 519177266 891174898 449445223 337875280 435546083 287432595 357612550 798937159 381330727 689603625 757631529 855316249 159990025 560793514 858223656 16983001 729264151 714995833 728508660 587877689 222197831 992226927 434298810 113977095 249758287 615571742 359148640 294297400 327475504 528042556 629630406 720382028 349041271 275021067 299130693 961442699 901455708 269873360 660268545 599762808 613194350 409291778 767603903 758110626 952465353 28558476 187028849 522525973 421711464 743217908 720477369 628320090 848298011 442328333 981712033 803760882 619977342 583079190 432376932 468283932 154379016 80338608 30096987 936725953 885759688 197241234 258322711 991415558 215705107 50589836 66444652 181816511 967360365 622442646 778731416 503602859 135911550 225434022 606848596 879569565 123847578 975144275 133753686 587025867 825421504 513503820 693105134 606546626 810882896 776940478 586951538 826859048 743517301 194642847 560050939 188613429 630819357 901379127 819107834 409033875 436450165 751694028 530865916 374884554 158725271 58333990 771053344 676710759 68583678 817115329 833879981 12173667 933676283 100812723 299129339 424604669 267648274 325738498 882493713 725405255 502993740 695638922 843512151 117734652 665888943 910505300 855479601 901129060 42372829 200942275 247677973 857763981 435619081 806413240 79034662 403747256 271555292 913134817 553919137 641166492 598005197 58891560 236766315 439407568 807342903 139246064 714404778 234742024 382385311 341782550 487759787 352296843 339338822 138537080 687777845 844400863 11657693 615270274 886349555 982485484 161607791 569461119 966801713 228235206 455974686 775474959 876567743 973505889 888440366 190465934 489731724 15320254 768963723 22182468 552036809 593445593 430632661 907791964 489756819 931953840 518943731 487223281 743574347 296490411 345261703 146352994 108506287 428430688 709832568 646511736 528472730 399247863 359607429 801115461 852091803 457583307 477249962 662937464 572274726 964518231 262498735 992138028 416596122 708272806 560785483 592499212 617235153 843023469 297116677 283163049 891995361 979530471 156702084 105037520 119603593 257375294 543217435 897488555 949249642 331355295 42282276 848817437 27637379 323221514 672132774 798540472 895155497 180035333 244846803 528612859 612762754 626102789 665721971 472638834 529532185 737556240 18707419 846291087 503303113 334271583 389741127 273019174 214851920 564861663 607660311 404048013 328135857 588471523 969754837 563820036 243086604 583325025 921484385 14488101 713630128 753686329 647275200 133700708 713998081 112478602 30067020 850948688 164108467 150614042 114802233 379662144 399254443 577178890 848233476 770156829 250981058 536392082 183831949 282392408 782902931 77631897 575331671 747799442 50024597 795233385 240853637 227475616 920848124 339926747 631611103 82868748 368731055 666196991 886869637 499040867 312775095 811211326 414935833 928704256 234499935 466293133 256463297 64166064 15246617 986712511 433049957 716860073 695060637 807644328 778026635 683842419 659810226 379246438 795969798 108501992 785043551 15417332 854134823 917619259 122597269 543740522 842801352 636926295 260495936 757192677 692079795 415281859 341411493 608208205 476877893 793240754 993010421 439263574 545206138 684170972 182603674 813683253 1446527 435726561 228265907 16477613 125259828 876583356 80679752 738486638 429438437 255946687 505097200 621968490 765662171 273322478 928832316 570870101 355399907 479290927 805139406 811718241 919298117 889524085 508960731 505486584 585148084 348014603 244320341 736738426 353085386 630541057 465173141 542098541 560647095 181912589 421837667 157356409 515367213 142369052 136930070 319050550 662664392 588201671 521889296 369386182 730276600 747553374 941105716 410554549 775184134 484096893 525497578 76619473 448264776 839995207 122953634 810010086 19423192 564726275 836273803 994212048 896471360 315047529 700175856 799405901 409600141 411129522 660652346 216882646 346075048 877574745 586576035 312715776 820553434 56616905 698817691 899411283 322648160 52995659 619290868 87029603 689994132 123732579 231952077 595792046 261472542 860172927 826497131 678190219 747255195 274982771 23954652 630825331 623214502 933869795 308811810 700962929 610991100 966884588 465873877 810347011 450688778 75447637 769063736 684671572 287282091 73557596 50600015 813885796 507428211 642843670 173395535 254178922 789805106 548060063 376954693 397868524 910510786 445696400 988597455 534322139 775239292 256589631 55984832 379762922 998087984 304265505 483128016 737844459 454071621 330986121 30325413 151760205 110332244 806306929 78113921 69296700 971227341 676913087 778701339 184153811 847829995 33336276 293526075 470754980 618606207 463414535 891431025 354109368 133126460 942037276 553765510 471215129 852611442 798747249 271318147 58669561 609268983 250086544 650053070 427796768 407031236 985170631 598859336 163156183 942749164 563754474 38872583 111615070 680651104 333317142 103728478 821959600 101976603 144747165 221182705 912358483 744221335 832617609 478918418 234523821 564070966 957601504 548704560 793861924 366856780 186111033 198294887 392606343 689870731 87984503 984136472 265849820 436588072 171434913 754416680 940515446 704976839 824968235 736135248 181445794 491379288 605704642 1528384 410022923 661362189 982839639 957557107 497095525 731065874 382169651 513497121 19335084 792880174 348609952 798655384 416464372 900724662 871146561 692928279 706754047 897854198 301858531 799084597 324330063 542842564 547015150 700612817 263587452 228012755 710885033 28377825 889130550 325788578 249972772 836966830 867520047 649111515 173250899 210152884 30755382 724093574 312604813 261085296 854846262 812449333 650232376 479589862 186469865 820953090 949201154 171636801 642054889 701607318 206569314 290970470 183500347 464150910 777633390 25995668 460533449 522595276 107375166 101481124 678438186 159835058 10396663 698067432 520846244 641937256 492784881 494816050 216042578 65579004 202993080 76922163 494161905 361609281 713806913 819161082 688652676 501616725 153521241 525490743 533407886 130036327 328003561 271645448 648288944 4209353 812702718 214265715 935520950 12521793 876492226 499015613 817470564 857962555 605950271 96609968 904386373 72465785 448475316 354859339 757233122 895232736 842305638 834953014 207841106 284939346 715157927 306560795 384540149 11669236 607296570 941510943 391468230 442235419 302632562 381977941 318028753 204397865 944478353 499033500 277566320 163637725 35640304 85767516 602399252 126701774 80309414 256584392 743437054 627543629 498772200 120481024 394883421 24322029 275088839 938648961 960845942 844123432 397659626 627316245 400648703 978036369 389050282 657088874 125302767 529043727 150949942 790483431 76247366 412876708 136072180 133005795 849595219 218518290 327899978 627513327 819893077 301170510 912117979 583822933 361984731 625727113 149620956 375581988 916637727 685395830 358760556 697608713 179104420 417499550 951243206 128879101 152202301 383493083 828450757 329367102 596372311 859332806 422731857 293727186 171821590 905866715 691215220 749084927 90381063 412931948 890595782 824812931 669285998 833517801 675208014 757784746 599898844 90910877 718240462 421617674 362933783 241517323 860143755 54244735 601125924 726114804 773634055 507625978 775185591 826872033 523220540 564360993 529915038 475360453 181433830 334775429 944628315 67759759 265296426 728008714 952448771 710676531 629208360 46870523 861798257 776091768 42415283 654122280 75743671 927196066 576515492 639079718 20524912 493092277 90647773 769782591 317120877 165987765 774666167 32963652 844590155 817808850 139368945 718093308 443984311 865700269 254679092 714105389 502573750 548137344 664588349 18522000 286793820 913456393 721280470 511074697 318128202 345145813 926722524 432766240 926180892 345546061 555153185 946962665 211322692 854248541 217723382 476652125 398377505 976847963 188835681 345445793 307279659 785464078 362879437 510838938 687806704 954888401 53349767 725658059 354457596 912001100 925002333 336901583 728979340 79216385 65222847 36323228 508414848 732945645 662894787 204990876 632180535 208410364 504766130 61909690 461242592 617410907 598063207 607969488 206719866 640581847 858610829 277001484 565491662 327249184 303048686 87072938 314089974 227466209 318833366 860101920 250249901 707603386 327424870 818235147 933933594 3267969 729780043 823895778 781716267 857949823 111229443 891050531 768724375 802658764 751055132 696157858 293265843 579226077 106938599 13702640 991474263 371891912 906580860 202370528 709950524 420361147 664019835 312009050 777587718 306949905 91063094 647000897 36651231 968437576 276388386 539428413 146503220 916300149 690746030 855461101 849499991 782388847 764515291 44942735 173867477 196797405 487807086 666024159 88812611 435100756 745763529 610431272 10965019 828964713 518479633 358120938 725848517 655609716 172650227 808930508 626904155 744910198 932035595 284487934 941879131 608689319 427182901 426204507 374223408 362718699 463641114 805307970 493122895 388959654 247827078 399663792 222512162 963450386 598232203 691870603 715410308 300202135 194983713 621940860 752984816 858165510 834195989 738462543 800271663 366146647 444807011 575301520 484897553 536696849 603983674 650121684 381456021 143690218 776583482 435485723 147114286 496203945 663789825 194291037 409639439 885374527 783682989 845409957 701502777 317353381 797427209 736160202 687574293 961209487 52135379 829017111 694062912 921412231 88766094 71098454 588338088 521127293 310163518 243602452 225643496 471370277 671064815 280594753 196058039 320305948 273315230 791088308 222151816 869474290 124342868 81763074 780796820 64090627 80259888 922317647 28866904 726955149 821846724 314571494 530158619 857702028 180501477 595595715 758039441 610172302 180609348 426581202 888228167 974425393 837060915 6635442 745815729 403065860 121677995 138982800 733735176 923473340 564725960 346573751 337492217 994368327 318761553 523193458 923866958 899909800 68102466 77127275 7673579 440059694 546062053 686473122 497140038 766216887 62163792 635675235 892973791 219912528 547974213 784594278 410923281 128015169 497547896 886135594 612714970 881504157 406022836 167597256 977236447 983435155 583895955 39330576 670989269 356373452 227178142 474354413 37933652 360659897 397618307 311114328 591193351 111138894 838937700 773856402 988596933 523643777 204091020 818331330 552585129 22061280 333472820 427982086 169527965 230434696 947644402 351310197 940036290 262396165 813841960 177799994 464174116 314639238 208991286 398295750 992113149 7425724 614596776 518141896 756708067 623495064 153867034 428030037 962383264 837949682 79483817 15807541 705310649 592887206 30662229 773238461 200302762 301525072 751682494 830818422 83462505 48821742 511149585 175322441 54787842 447649989 782981428 883962629 865164174 640635297 842771979 624708149 958538348 427422021 341419965 731508693 305012448 405578762 776270184 477860505 394581710 322824341 810644462 626591887 969467538 644387239 550471640 334308470 514270363 931861262 175116377 83554711 131259939 40844116 128629665 236327602 994217507 20613968 458222752 722207569 781148179 451954997 352201927 4843636 185751634 754872461 196167419 863020771 70910830 546576489 769485539 797155967 423238536 851413418 256899278 739327024 899574333 49332482 567043075 348537081 605855214 860442975 909680333 613088021 242337583 955577577 180669359 528597742 498027435 885409536 533240845 594669298 198763476 725146990 359831110 39801418 122781660 750346064 595650238 70410322 863862915 513663153 312484547 692198379 64974089 354805055 605789195 507026815 912019305 427261612 80534999 940563060 422527111 639101681 440351564 63216007 577163411 975869924 215546978 547020473 957368657 66358871 363871955 530413199 985687329 898482851 834033985 742095636 904875480 135636339 400421124 95892059 935129650 102465925 151804174 774277792 921315508 448143848 849955804 275624908 229348217 564644614 353014867 756580376 699700065 738886603 419832191 988717817 143657544 843116833 727586794 646167980 633949239 493654036 863530733 966602026 248762467 2215365 44111715 693372083 390746055 442936270 109806157 736795564 534186662 96318791 98112437 610771378 340252893 550665938 483714202 106277306 901292634 6800292 56225259 7910178 123759988 26802123 341513391 516988777 496712291 718336993 974651544 29439335 526464697 914198858 389763595 153335698 935369855 504711793 842051485 406838550 184669105 537992399 31496421 966808659 129636754 219195831 936170683 760688561 925434083 811576986 406261334 89055425 455781709 958337113 891778050 949564987 640455807 151512254 906228677 923991177 175455199 12477122 917584203 726362937 812913707 826306343 542846489 685218164 342975958 659769505 606270645 952008426 280277798 886996178 219992004 399689604 719463336 172626089 909956802 252134410 785689044 644216573 395346916 137330350 468122010 276356754 520651733 901375117 676565374 367002876 554821395 934195377 998721471 132531450 881124876 490419095 752202410 791199491 601592204 524550068 114207877 8586997 709099799 644654031 750822176 122103185 86955761 499758717 171136791 140547714 480857560 537791633 228036728 698952327 363289596 617595120 430628790 929822574 746506058 21651354 46477134 747099765 330136754 502785129 181036751 168195805 312442725 446772816 663947928 965457287 939695719 692296590 592011346 892654128 41974355 529139513 933201890 138801760 279754168 928619331 783695265 783672318 90516259 68529023 987013075 842554578 270492156 574268655 879318385 284900061 759938954 166326627 227986304 223594957 476353208 926162318 136384374 562243964 663240530 415022244 30487385 364742014 423761979 413104223 536995133 492744898 192843190 175798309 368145429 655460635 640902991 470727139 162379302 76807899 870981074 221210358 828004142 736800040 411881867 319042330 560750261 378694039 658494418 257278835 243593107 17137382 201029837 349612811 185175673 618902749 422941477 46591133 770393800 110191789 69629186 259809406 52677663 632528284 981712088 40710049 466484611 48843207 235146002 549866476 475355469 463368036 39194033 505664010 854324527 993517315 701707212 16300432 366679244 336823264 31482273 525212136 62700297 92500574 988093633 305911717 831265052 30301702 934409589 841535574 476065540 884350669 178210709 95356379 785345743 112476482 89544053 682225665 280864609 107759443 931741183 988518919 797239346 104217153 677930793 427177412 674471965 80391250 9580675 707209475 710986903 676871982 438108560 550887930 644019856 367846253 377235989 149403287 995710249 496433117 300182395 902054317 587156640 168275815 46196640 889711141 202920929 353503682 577347636 573443753 218107384 331110815 2171647 588575587 160274252 792656382 484413731 488010731 127154167 617353088 398094459 788637051 685413023 99421701 126969628 719354316 716385395 357879479 304178197 263943376 271178124 760893592 883820460 800923707 269457465 428595705 974729801 274692662 778498864 301870473 527705814 989685105 817312585 561585262 257848572 177314742 826345311 31947935 507766679 972433652 436050670 656794615 748870130 619165743 1085725 394857272 490738031 918451832 354204570 269806256 729236970 348814460 162414553 325765862 254698944 990840147 866924854 696114374 921622933 83706435 319710162 362896525 863982799 790722158 329517976 615147252 800455592 276295163 526002088 637133078 667803265 258544527 60872918 173257655 430349411 991862886 732134102 589974738 123287345 692734761 220122172 341075267 191140781 854255223 8202252 716469904 928697766 500187695 555716629 769479025 912155987 802946204 332340588 786188682 509668266 633382898 203580293 411993000 210112502 943803804 397620737 829444554 615079810 311684146 473043683 98108731 609654617 644347189 152498919 627384451 764136733 921476472 596807871 557021411 546501126 955124067 59951887 422102813 614218169 599380082 991144335 826904738 878812800 393079859 448771538 512323160 803946566 123279323 610092431 995601198 380264681 181856687 286261130 511367594 752732449 347399500 202971257 196460839 455926474 633115 689503719 476888825 806898486 637645821 708525521 516956987 576042934 30882629 798260378 84185113 948054106 173575175 734483974 30737951 950845191 83122229 880695767 518798 747337812 879801117 909583386 749664613 631603176 589333966 963781342 443546601 272270581 443863769 701908625 515229834 903092113 126387515 929956418 351046033 635293289 931235045 188316688 594052493 482606299 750174323 221736661 748738625 15393815 56504818 407459602 378715960 173301395 325314655 553500666 453056762 972987361 62647889 315729439 413336498 760708619 359222345 693973908 191999150 633055760 323164421 538180301 801956375 428899405 209838201 79543954 385761860 754480440 728698858 348851584 170763914 414781161 876010370 222710167 389192448 233244775 394196139 687238108 115353244 217124676 539601157 745298267 773917986 872998495 445087650 746791748 178425000 418013154 753075638 688832363 58197895 502611099 214140140 355563561 486093500 958791136 564539076 701352009 745363268 454863366 775337643 529197585 544045257 434750080 533803217 626355654 816593190 444645527 205813296 63541877 488829907 369872807 703411719 262323092 759086002 782545122 656888210 545052664 514376012 993104390 873817621 710954854 602400748 372723704 122946002 356047971 525636976 311023064 558726456 742846499 316440298 461089852 623815278 906630937 447065512 763645148 144793952 538455728 147131332 349326541 84837609 406903480 825592407 361844062 583548959 167283661 805709122 220155443 118419928 521998420 114094941 488545081 674436089 141263810 425406169 495580450 538003567 539637276 85118692 143620307 665661979 365350969 498554519 868960351 447192954 593818722 333711594 411181980 544515099 125873215 627010265 997158946 199914555 445372785 174140079 71393394 468375801 35123642 152053212 511944100 490943584 260621145 857370995 779507252 328765883 53201329 281306428 476328137 982075120 178642227 853685781 309262566 599489599 498026937 950715825 181780130 585195471 289855307 326560804 865606141 897064302 674987938 505932142 470797046 282497838 267269807 99658889 770196026 465162667 226400706 348221348 25759151 695060861 8822468 236270021 720709018 140330075 498284395 346742719 314867713 894874285 955516961 969933014 195486073 528075055 861438478 893898670 282948591 577222700 194823218 69594130 379578466 215282528 754326032 145008376 286544266 168298318 228838085 275723289 852778912 962058954 224321247 86361927 734066236 697229445 207125293 589855582 82680642 321596848 309854637 970212889 612245973 142136029 632687739 616087160 86408608 496469397 359901015 409847755 608458097 914749588 591002188 271019568 259191294 114128664 458882039 476669203 964117871 188437366 536967113 903353537 790439650 242991721 534417887 339605962 817203830 501174100 983214984 2382360 928032159 20419252 116833085 968289135 850168807 307607551 830066678 78183797 81556787 819107959 872258015 928069110 710451823 605324704 98685952 970976868 586407822 751206811 205848042 165199034 408068806 116828108 455469998 414213062 240091136 901496249 232990031 913046942 69957918 124261723 460905315 663090646 9576949 153395191 47534350 389561499 413081675 427122822 429994319 790877003 77992527 303816169 963631465 317427921 850423715 252496604 424888545 16573585 235836769 638066562 185453146 903205952 12028195 634726940 583330401 905492035 154544441 233070185 22182293 727983854 375376889 531172359 941085327 666615947 207749607 997737063 896944907 981272370 311458440 13898818 243807223 781519271 801020376 141325748 692892808 617294848 116032382 251854600 116980178 464355932 639515652 519567351 448381208 580119060 486426745 643945863 137058434 62465031 179801804 849953007 732787629 338005791 890173755 858893245 333733891 133972090 925635043 919962737 809499728 475503001 208850545 594141257 617113110 584543481 179569083 468216135 713708195 303662388 613961967 252206675 951607179 178801223 624715193 561818845 754178045 106726244 635392931 215995263 465155236 127880432 317596605 318752046 717515490 499287939 142330207 955605439 952511106 316652081 563113390 754202989 756062392 935775172 144866110 813252655 614185498 699043070 458494319 833747680 530812276 404272256 358941178 530863211 190052578 850430749 648151627 314209077 427987535 196269695 885054179 470683766 379804903 910014576 330093841 391392953 17805378 326768300 591577683 598084793 961957672 419771183 565222297 512773211 115791799 414406320 922615428 375859820 997908169 722374878 524804637 250975800 137112101 551610839 908481786 486702608 353068814 566625428 324097626 521773414 634547666 129430748 164608086 873500774 539297183 432828276 32555954 653311823 236026866 217390515 23795554 454713993 329917526 292431594 22256545 942103799 263783230 880395930 31208980 219423745 576067674 32675291 275925486 821061520 609915414 950386207 874121712 774733932 386285506 412724080 754504615 848293960 389838761 36846674 166833838 85510627 485024158 358616396 662494746 250907533 101590670 605775233 768164194 552212004 898674290 325356051 444946967 629206929 941672768 560415686 167126923 821365582 894965509 535923269 266601296 641749212 120683803 758607079 545277785 136099469 488794248 799221576 905630683 706994430 405351970 817650714 422131444 862381082 276772736 964873849 565378915 874752849 9163866 497204368 436751038 346441246 3511201 983355177 743415151 773073793 869361276 278562414 854795829 474585996 681299336 234048920 909108380 509374457 51227758 823856969 739143393 111918434 807438096 387333883 80773033 760174578 748532317 575793624 801498752 298455263 453431727 169957842 795238552 755829413 240786476 85833437 265268942 26663183 870966416 637299540 820990120 351673787 747706967 219499946 630224854 37223828 394841743 133837736 669755935 750172151 67875927 717037054 339615827 9718789 652104914 751626409 46963147 30596057 732071155 870324316 670332189 997442095 897449023 88936716 402971997 90581086 413292432 916369025 2465422 877742339 356233832 147014514 529796377 971840840 200507137 705965586 131328030 522192549 730084101 587758769 936193650 339142848 506509630 886077441 335223627 710207953 867472696 86676936 252043181 345282804 382430081 604694589 28565680 387112004 660547459 278217932 679749093 34473317 853251355 188509431 517572494 559156540 166046851 85412614 349592950 925982003 10412816 330559523 44951106 837187986 667162603 399661863 111597721 968346411 805266541 625251460 897362677 248849929 226753279 435445521 542896035 815257303 140995579 587956690 861853216 257852212 693134737 499884942 433524617 724297042 649381496 748402687 885448335 294817829 351566606 554364084 854413274 651596217 534670751 425314304 455994137 624346293 774598744 584937962 89627693 186291293 446357035 879379462 229752033 580548600 303303268 401001878 846878034 990164009 291154142 801653925 603467585 325648835 364533502 506991540 877545035 173565308 820891534 116014013 737873874 103504089 674597474 390871073 882383681 767278261 858498519 428825075 949233748 34595824 314847528 997270910 95628247 674954706 837514259 977441816 475666689 806165477 928062318 489841141 736599206 567647558 943592843 374672168 303565326 674349285 355116164 458096597 204618247 892021260 984900524 527266178 218637600 313006910 919870444 10805062 951722875 941051959 743827405 521363810 950133328 61842785 923592307 620254370 511997602 283254789 947676834 726296294 163852247 997339735 351405728 519229517 751950361 965590357 118477009 805051599 245708883 526386901 340383549 324919748 884094161 507833542 687844051 304859692 811653260 881009461 95999522 624944251 727437086 66103654 482711791 202145598 796074326 802389902 636904047 54802548 90864323 937495467 478494689 540518319 193014259 860035658 689889223 908823799 735277811 127514868 591248771 205007851 647751618 48920889 485872421 792022728 86358700 744367416 560261634 797876858 647853651 868563974 418870045 26558534 802544428 352559719 630511364 616057228 162721284 351440391 199166400 726029062 563824998 88753353 902647545 16073364 578192066 40239616 333851197 684715325 259154522 292308580 808209259 319742738 315344760 764369095 763758139 151979735 451921502 625820347 300923949 108713954 307743525 83714548 562829747 956273243 819708979 640167104 743157931 224740333 262697414 560271040 915093630 601313995 844804860 287867997 932503077 223935345 365446801 945736308 516678669 137109616 630576355 472594304 216995726 661461472 745955069 663788048 176152045 487310627 200154179 678142136 824205304 1259122 710626935 236387460 38846603 109862504 201458862 555113148 221031977 385763052 999862135 200409503 943268503 868891403 704627655 8862740 898919494 108084086 53981341 713604870 118714798 503493314 814902323 603353757 520460798 670336238 134754306 422945631 218522640 441657341 246665076 710919562 121656370 409522116 728598375 725665485 943291436 926121971 250641742 973935786 594426001 216107352 311389661 239430751 642434308 388007609 761737866 186458994 429603623 46677791 886819769 648938112 152699202 559785504 565177947 867737896 693487248 476789777 186708486 231727585 647880483 740254278 502060961 187899221 250833787 706050556 588852370 904695984 145286968 252501855 489976533 141722373 165229979 665317816 843308703 78658327 758546323 181593539 227982300 182949379 94879742 678741130 463032758 543578186 184704723 292930064 751764161 460296679 234841915 958767968 740440359 22008010 5807666 219663120 167073100 417565940 158869599 624708151 2009696 673403502 233825834 313229636 737366013 750641116 93490460 709749114 917810666 6596954 861534255 19281374 920842791 569272599 929112639 841578277 813656580 240386022 674116609 189643501 930581887 678686253 858462773 6091671 593547524 100781561 904974786 191123534 528727269 191548996 346191610 511375119 491192221 193402485 738596620 372542335 680099372 747542500 837703587 928687153 776625375 300269627 212808474 376715248 493862445 35082502 575270541 272224849 477268643 530219325 255893563 974746849 811858013 235977145 368569681 50180924 813521282 188628391 218414192 996266522 364995898 267966534 254978425 902508737 429681589 845914299 204854854 322708454 345711410 556092103 485569066 744480273 626476037 476808486 526249729 834848915 620554334 438622776 756858573 396503926 949584424 368345613 195232936 265358773 784590331 283240443 742219127 291998213 688671057 99648704 318103763 83469496 604368875 233537177 365744293 695759978 167887720 933509674 922216865 525940455 222090736 709205868 263075571 20003604 716815382 297242132 462869219 170931168 631360843 377852651 646795156 185548846 360088928 12967806 583887779 962953725 189950043 739923219 691487354 263422777 239408639 187023998 906800625 582197278 762386958 276420550 609358237 880028827 924783723 890998547 615557436 298561239 160116426 958047036 941443891 173854653 755069579 22630602 508196439 218037425 627235442 266546870 648763973 971116289 586711031 58294644 445143845 105851993 271269387 390900197 124626234 722850129 276511497 633078328 477798541 779126074 207237554 902138571 950504596 574805276 83964379 872270275 18594803 417560863 260530879 343399003 255327709 429462461 875881839 878212195 826407889 959694420 721208647 567183942 534435923 383337555 450157597 964790921 1895969 385922759 878662313 419118107 224158462 750517897 753543309 9009417 908711748 662239322 441190990 616896297 540130774 352704457 967362461 715297613 498685558 787072926 418770787 290081014 318432742 211512178 896806183 295339826 254339108 349966427 216261257 20932688 178247851 925563796 377252698 574973535 116274043 633579518 528472549 822951382 647822034 408145619 963893845 110514517 218799938 362594271 361061620 697394015 95195116 977457117 270389296 819894936 29661358 712741485 507962308 978890434 175345941 407044971 810577711 551670411 689195167 729850330 17672601 30190580 64630187 570965927 79564042 231040726 79671774 82836378 602483472 858291214 160685865 763514268 208492665 275178024 252090520 53102746 937136362 672345207 281093875 528539643 157667377 256981313 852997995 660899967 818133605 135086853 843549938 306783205 907032680 114106620 871078593 255694078 38193519 496957846 829471868 288439882 922569290 675482176 338110463 100351693 860617809 488040693 951154013 911335408 46142086 865686081 688523302 146782753 169025965 329986664 748448682 175272555 386929079 103167645 984255241 587869374 24756217 752070121 316504283 354321698 695124317 883157603 201267912 907236980 527305125 756647472 971200602 120919324 342307501 866838220 389345819 191286751 441900246 664205483 449974858 178556144 952569346 546342602 384249078 510197701 923432011 267117213 484600181 547863731 463870464 841829499 208199942 348960530 309162217 250607196 389272946 394726726 523760700 250685307 426196538 213138506 640411014 498954818 58957770 110780307 477768669 855559022 687014492 943267835 140783325 593829089 722136069 234764350 11457486 245750456 806598149 591496617 217454930 122009197 702713360 652757751 119176699 428037170 473917592 719811216 23091036 472966689 427161405 51864561 393525348 537021773 345437105 76936330 519105955 191666684 669710321 723106785 286991348 243106350 185440680 53671895 911794533 420137927 101129100 359897162 629785523 375639798 258160462 881565615 472889740 957716809 610467122 901774952 63966017 650060364 118628018 354662517 933397175 595546822 758503913 508986694 992422736 430122114 598352980 616789876 562923275 396221110 576746348 312221096 244623278 480725240 144071272 836567655 113895481 795377736 117695731 113112362 891867703 575001692 579042480 29820522 740044534 256258115 730238859 237885815 945495144 232025959 996019269 875141719 704941207 732593516 128545689 706975620 764932888 953439146 788030013 257845282 579469157 105460757 758202961 724378701 904595971 585405209 269352568 430506486 993020634 84472872 146723628 339666553 148136018 53147229 355246211 113034711 150811601 143023170 351769627 772519277 482459607 976770883 554226763 204147386 496944732 16193362 22195189 44685537 808763898 518735793 941194239 511220894 608939792 775941560 108819603 601815470 305192167 748627862 607053767 64859411 422886944 351653368 194493532 617424697 824697203 368614824 130137280 567238121 851885800 56710218 63859199 263571530 920021531 715681615 492446508 282087682 431821342 937636523 267881375 408273522 230473894 734217409 58435567 398578507 454565016 727989298 11781647 29066427 40561938 995448405 33921755 983736485 700716497 32468017 368615534 978022167 972944706 914159146 725385425 315672834 105419783 620126135 860243079 930514490 839974961 433391259 462755367 31330234 637935885 237765705 319548697 605787922 481650513 682313123 304424088 18877520 951483555 838705659 957401490 595921611 737586372 912467628 879581058 194788221 896894327 820176971 408534709 522317522 896625074 277299647 568969767 577733008 484908758 424551351 127250137 784148588 853120946 273251444 569224301 386946357 116512277 240075719 429987562 834541607 381566658 320187518 163445911 887894663 240686987 623324390 989263793 865308912 886382866 735059549 741297465 756305439 662784820 576499635 757310610 385484100 973327140 792537527 764693340 59422290 19841766 107009193 110397795 53725637 308843837 342132464 524973356 540818528 741938249 49931852 392945336 345448611 929504367 180736349 590101556 187977437 246797712 756797882 838979096 471400259 727559770 541725625 102361179 826486756 893717783 462434213 80113339 731469465 160925132 153542738 105117210 430829669 939042463 824077742 594396177 532137358 173533311 705505508 308804819 442555332 508818508 783331099 663730653 291792650 951842554 455772414 217058104 628367208 813971136 891841425 277779387 819177396 303243851 686039717 216591775 734472725 188294532 987517319 984002395 753579617 100925565 949745464 973457446 366377271 993481614 920659506 240167530 761636940 470602950 537866467 161226624 485300589 927316824 252420118 289377064 404650091 611529686 476815759 534092426 429012932 815854844 262545373 800595321 744905809 806238590 565477262 247232755 884898271 63219557 69421216 407968086 987649102 872914338 370561739 228705159 82987276 28797432 545193052 639452759 280277337 669342744 333520317 215575591 640199612 807985178 698056103 367405844 757301516 14650555 121283471 475922363 195087062 140904114 80186347 36323172 685942811 82458974 441177284 894371414 488388684 734969747 305446284 675781727 325127830 936087773 773131118 553385883 425391191 464599942 303334388 621299343 509421533 320977139 658753880 405867310 9292508 516631098 242091803 574661931 515632886 889296447 897062110 676556469 780787685 587239982 304032130 373695887 322284026 776745905 146021809 457279043 695629267 591916297 61226601 492634916 769493838 637431726 606855606 435537474 701995806 827418038 793641383 235442379 1293148 863451807 278345385 418472869 965642902 534419007 694279367 76896273 915016591 998583046 65107394 17387366 133728296 172249861 176939744 470757168 768174626 66686824 922246198 501985884 188586994 727004248 444926346 865546109 748270708 50855877 958820622 929649615 217405947 927979821 711696576 623418039 8827457 279726301 280179409 35541965 156366976 348066442 442910891 512449568 472277438 621167036 884707855 901069782 867779033 459124476 311353339 133621018 341262350 717847566 217462495 84991909 652062733 564745896 465747716 420081372 698418288 305667174 834623538 1593972 243900756 501410614 939387424 874647572 387104764 779395298 401898960 584601969 937614359 239561433 604860472 941000529 798951818 912187564 515551904 703202061 222581865 776845808 339639517 613583745 710067684 62907570 764990714 175850578 978488137 385528145 718908317 934354714 523756192 324037907 49030389 79694774 310626171 579415636 351812000 500447041 668378211 440360040 325796550 41216795 54833589 414929246 322694796 228379721 164002721 323676893 397069314 890021038 935632504 502409606 390348705 250980765 631374868 881738688 520973986 536791033 653709027 845529323 894020181 114373283 589960057 532187201 771890826 479939780 286442090 880790539 646779048 538901555 18393387 701254457 429127051 626912377 71780836 833949273 92375349 127318564 560677446 649797927 207488218 621527250 835533299 474286335 533382276 402077595 730749338 295742978 69602623 350617157 43717209 171836720 745048803 756581393 744128220 517381271 396809790 902600689 676432214 602812660 790717817 732366234 612535996 579880258 705631949 401054639 713126754 470946653 54569231 311147141 474864412 275164437 931072211 150053190 647030872 579390706 724173664 518342054 142392430 935443255 232996283 626890067 851304830 840868153 705134812 193524763 54552857 279405372 151038472 972624366 281425186 308887858 232146921 242126062 138116405 60158546 184252842 968818470 624756506 727694064 172828323 718679955 171058929 974450174 771012063 816395040 800972137 848326755 938672801 8446224 888233997 440116391 643278195 973529237 861887788 519864786 688625337 506841011 604769221 143435617 361313942 252301245 308502291 727513981 611670964 900044786 450878615 843619631 464068170 798898743 467395208 239739142 270177923 91901172 534919847 269193216 468807460 426193094 67735976 881518307 87708048 999532278 982072106 227226546 768759023 579824056 563948738 900559885 575962282 626790950 580715273 326652255 256789462 59528375 847391153 53602166 688277878 251576972 503238761 499902033 148996444 607801498 604800225 31381549 24348760 341908665 302944439 19099201 746279502 760600697 831402125 169543192 958842534 170409393 467099756 90077965 184537971 988433088 501998547 17036215 773317725 15136483 211995172 663436825 453859630 51228085 300259471 829104424 897853374 916614381 134155950 833929143 505714031 462935907 396855128 617048326 880099712 14314322 172243524 933371578 626814243 136047710 946565492 299317576 506029643 812666160 628213132 439970902 206093201 720696660 427459506 194232364 901295375 919579789 896330706 840504475 320510839 171384754 998327426 949130920 607542157 640470221 556644093 607010316 669388719 890494653 848899808 824455266 849842059 773188522 7184583 791945864 928118164 391781134 522293871 356291636 233793714 234539279 805695032 995481671 49913906 373781013 647367586 433614083 855817804 288010069 682062151 193409438 61413459 219652270 486959614 538315864 603116315 794963532 727289327 665164571 7141304 747156974 301489020 870535149 345976648 869894184 940923188 538421329 534123545 690827693 632207032 741316715 698921749 916879403 374497089 770716135 204082510 255442070 427437612 748154807 846699526 882472462 518409547 106397075 177124416 424024927 739503658 55172986 428559921 148099204 718002602 601634002 617972990 188175658 210947535 864867595 914778852 646229799 920346858 252493744 989219904 629077982 990293300 941939787 652000206 974074248 381307291 317118246 937338640 156722092 130638272 482184340 463153723 645447148 382554479 880611479 7145349 711715803 152814896 575734875 366499103 356180475 779559192 828372672 58493738 400367060 347057371 641815962 609274702 891931660 929860601 385851372 339795985 836295215 714749794 617639296 54920067 986379917 51326375 209262253 10169943 158307526 976916722 637648972 418402530 875114565 959441498 183838538 262444337 439335224 802099271 443445489 198032240 963867595 563226817 391521994 198419665 431444215 917374248 383423603 155588206 684083260 541456914 748414488 93953472 918582208 645903186 519014976 291282042 655819121 863212860 775543034 683759530 16333010 337876085 585985207 923870739 401959659 216451291 905349851 904789632 772820943 485501947 290400497 513481075 543094015 552561713 628659352 670972853 646456380 558299545 219077342 136791753 646913613 84115161 282979504 969101382 39886834 647201468 182906316 510804850 322699947 698272238 141103205 344517797 942504465 853747193 911318272 262802255 551996889 538624094 853284505 381531938 72811058 265965462 684532163 762530801 529289048 552417837 908040877 95359236 860671287 698591923 731654521 741667048 710939796 373896393 949442730 858994105 910141053 45134094 697699932 456406245 479657924 760882971 503292660 339802337 810389092 215418113 43824628 510841738 837696863 330246379 658966565 347969549 6413424 482090115 984226470 230530488 378234771 608320609 915720116 957559582 107126418 856624451 815760799 427206688 542575023 848960866 501764218 77631307 645227119 400868519 471481947 415864977 529924881 871100786 586599252 824790379 79112329 218976238 497837033 827316459 457413196 503182167 719106569 601741939 626201716 555664078 696160505 840059614 244811001 510009195 62687510 815938433 422864213 394547060 370162260 59198735 158793601 725428333 432720357 722220541 109796135 386998077 847479236 724166556 916085823 262640417 399012561 857135538 528562487 15747516 4965146 389186746 373043428 456516544 830168106 843672236 505403973 893496947 419791708 257616678 292064196 925873907 248288553 291248012 654189334 410933152 12506825 566124693 800994215 479770902 739587713 147782539 290974339 853116465 80475049 275289712 468452065 18949321 735526697 958659426 31211708 30240907 359604873 839368815 416202537 781662943 777204626 693977074 276946833 721937134 65957964 481012810 405202942 382636743 272730665 476732465 46128251 38269607 962075939 992275054 291330312 570620330 508611243 236464831 505202303 858595565 979109935 816951732 11161299 580970593 479040841 118949046 124618015 269239685 663954088 29101217 52881788 507514648 762529184 12186014 22518965 889955432 304445397 992278357 947104007 117001566 521380043 197705311 675281934 153521553 507741638 255477434 977304675 525059273 300483620 184845929 924170945 359652986 806080886 710817292 971944874 522034057 967514641 197702701 803604745 415066866 691132407 629143590 193357594 886404872 602477876 833930827 872510006 894363092 828348795 89920004 72793156 414171675 517961881 415940132 298718153 854101232 860664889 272847048 90657040 707268390 672825050 546811144 50161892 2084754 980349341 29101109 912800087 181503387 202076732 419621553 223237223 268016914 249500023 740761734 415352932 966932328 854929175 202632236 234245649 396456661 681472301 598262716 666045136 307363047 309305427 315314864 101484570 443158619 196010573 796719991 372953443 913577470 325478138 134313724 487733439 723805786 705102268 990925619 756869859 121488052 413234543 817165396 633698123 187668244 805296720 827517030 467799963 980727512 626346083 351182636 110276122 315488453 420928784 870936144 15514549 733629448 84310701 2813683 469495003 999262002 417038193 370211401 565542676 982022228 498687748 884605480 457893655 528642145 62680054 145649121 670557476 611427913 709017209 829824790 188532479 359558491 675676107 10479419 39641115 678543841 135449166 837862100 909466033 491953642 226294124 57237341 403030399 537324515 587704803 797779996 827383126 509523097 472478594 48670557 796241686 967297020 25536126 154802531 743847653 232864876 182950111 554646333 391032147 758423269 836405508 962843881 413035203 217170922 528762866 111239740 463774721 159050937 293216931 908865565 517907110 272318548 42028809 151548402 268542160 899354367 423130423 970100428 782287815 73883197 155952770 804199820 676260697 773403379 180589060 987289901 849789068 439502710 435835169 916295504 694660049 979235705 927628078 62051611 642058823 873975685 609973190 64062416 708214481 330788509 351887774 299248875 84884700 20784504 494902385 984280285 84675530 622755391 186206640 177911666 505420373 754008687 530853084 543561883 616233413 874651208 582806083 588916422 743788725 623414558 358439823 818487896 122816302 663561485 950837611 563488280 287032983 559903022 60565962 865784645 918039776 770048848 952646688 942639815 468566371 432369218 397381259 6092173 681935263 285996910 492907500 370453533 423387415 411211112 361679639 641547303 888916293 838976769 62649589 732320952 393243501 595645099 956212388 331985830 659350148 642869841 137911677 633780759 353762066 200021246 532212809 507671006 446764996 883528755 45783215 771088300 955547013 484496373 402206857 91747189 192398311 122874089 737967399 366874343 55925555 590409476 426304800 932703948 267072700 810894433 852516145 200505496 415727405 884605795 671556598 519242245 736827318 703766633 480786059 543516380 837469082 933196720 720113356 204230915 519725008 653566856 858563693 695241605 641690488 500885856 560535123 895993299 285552027 692439473 568359060 967487860 79484986 753878542 973987499 262448891 895797076 888882916 335448937 657501070 327078892 384284100 346545898 617206721 326504983 357616855 383877538 724413718 573450912 490636327 273131100 649532269 731741336 505552540 423893166 611350045 490995812 964842366 408299240 295148739 129689137 718376582 364820264 994329190 76180691 931580160 137511621 409689520 837171024 511841176 743551404 601320643 194508728 488100583 988975545 27935056 937658982 166706254 883044033 721778245 139036864 28078382 764089542 460269416 669883115 626958797 707334175 237650479 630298786 496219806 402451475 921067418 70718005 472248968 303382283 129609377 472022630 658579238 460323687 598667209 789707361 677941411 778227069 301324755 584073085 7263094 162495862 444845688 214532173 902604447 387085036 311322080 135968860 214317652 348104494 514816738 91587095 297620066 914510808 178048471 691826373 289082208 432394489 351289558 588239925 804413063 586613120 972865750 724771899 864088571 3579190 472966956 212723784 341294335 783724507 141778006 27116698 851149433 804535065 530337657 71744307 487066810 526212294 203891477 179924327 44974002 755749108 720393692 4824353 427725507 356808036 500966039 685174907 996733599 285186864 888295338 951529516 945234655 586681344 584794951 163597884 986584198 132282843 988323008 969336349 21342364 965878715 231596725 152673065 859326419 437159137 241322075 968751570 576444434 544245231 996898890 363062286 931566817 430073269 787318912 875128717 114847975 447823562 63926799 944540150 135546374 211765932 108772468 944358782 774208275 768167939 225017503 796738070 814560676 745950663 402244235 240988503 355415834 2978812 276115297 766153102 6296398 183035572 666364175 88632570 839470226 322965754 886501610 270232288 627403736 789098090 913157738 703121060 202067588 566683692 328389067 642702608 917880447 384837731 227579373 585332667 300673703 131524461 915347355 119255233 440098941 907359359 771340181 101945199 416543976 572650710 614413801 384176921 50752919 189541569 463383864 448643489 185039313 174248114 715338220 214667176 129008217 295787049 851308230 346016131 506521583 702138762 923385651 362825451 472454331 615333521 774304020 784760135 403679592 800933262 619640414 467854057 340147891 72776492 272800560 282978053 635422891 470263507 969267361 509640962 147943518 547826481 156766059 793214867 84690163 658592668 394234080 996779743 946789967 577230189 865522151 104837498 309924225 952726789 553741343 792977931 729256404 589531255 930379073 121486218 769242310 829611085 348415258 813667364 876290950 971722663 515738409 781410463 20083793 597906777 898242112 622199820 457436126 187304188 26716875 497271484 955579935 27354843 291235318 491872542 558052488 88908273 406981307 51201601 860087639 477698079 535716614 35913395 542707819 873093939 986228974 675559378 9604854 126341248 233166760 153020763 223166066 718760165 472644178 665486617 71064983 384987580 244566497 7859382 464728858 408130799 252984035 983418444 203647603 450269825 308448966 677361042 717872051 589921675 729671819 192033753 144098373 143792184 723989620 437011984 589903588 192130077 307060870 657229682 883703331 917311330 794108485 267622925 567338355 757051141 576378012 839842685 849768401 960301023 787568545 854694564 797799825 926876197 499277141 283114331 224125809 774204551 789758749 875558501 277626895 521254767 580852327 986571131 537031672 363940779 871027311 393109053 871363277 868174464 862595513 811390008 685186535 789162424 554744140 668587320 175760602 11071660 48368090 106183613 662827275 103511197 410113856 350910488 657903578 540347212 343541896 328213700 972790524 251786070 114608197 668968207 189730934 841016449 928286555 264203615 774759108 558218889 355038091 5896054 731250410 268050402 333402220 912233980 868471474 837787702 948202068 936587727 555266100 191986121 720985114 542519996 433509501 771802989 401803777 250501571 2563323 500527080 948081550 727175419 207374348 644350775 71137787 695227372 640411138 169005460 315007558 860034624 272663432 14307764 646262432 26479581 798750007 358871656 169300507 742023311 102631069 728808999 77406554 230391095 242997896 282216136 761229592 276849450 764667838 203849158 311275531 650479167 938825272 782301289 122963088 643954608 563628182 114568699 969708575 119506802 83934293 149663499 556465871 740820228 496183743 637069409 241447820 820718852 635503701 598208760 60833640 497668872 381820085 110421405 326474362 697882269 539546754 284294917 572116191 408464392 832456676 955692495 580257625 880467916 304070523 731104092 423698173 371470684 869745935 546976492 6994015 228846771 269754202 707510927 167043576 293143830 158887543 599478173 911932460 61681778 60627436 651676955 168621388 373064060 403228198 278338688 840685462 565679265 936820332 719588747 137664512 355720420 611804955 777888036 861459994 817564211 134562388 884396599 138478878 457321389 840915469 797274050 109122140 950243866 434305994 819732258 560557249 675615873 471650390 540429903 507094142 548021832 853982391 979667606 679864954 9820687 691812310 425659960 198134704 652392166 209939914 784419578 185889411 673797174 420399055 527176746 541612058 652469473 269419431 549748049 703544662 421320780 712038085 210517236 340350982 126263227 413133436 560130840 759340526 391005388 258674314 461872394 191633094 326760388 343562333 485748052 354499979 602412883 688483718 481536680 542315578 932091299 372180453 136357802 111453173 986427589 735816922 196683628 68545763 908344816 296609382 652561738 725625911 227839222 384326054 917347919 609438757 832488888 697307532 43698277 577078141 34336859 366615649 127704825 88711458 940196170 232942363 603110622 820222102 669426556 808698144 940993295 670252795 405365664 226243004 423295289 273163170 146594286 780017451 753216171 205791065 413038223 759403714 782226158 956317694 611365193 405293038 145535998 452830703 119947655 753560976 441169319 115628054 963374361 950455 260745025 489838227 79128079 811946167 153760944 611793202 984138813 263454665 840479504 690052705 987133961 346874686 313879769 833348246 38669868 526811674 394489874 817794295 59559333 647337582 638992439 840927036 291100065 473149022 407135990 607753593 357788750 320139060 938438837 837508870 650001024 984412202 645168541 592901 268294108 74886776 383725773 595177701 865233544 151715206 145984701 175057349 338999769 36255283 995195964 717810911 97228217 246516762 520828638 928429952 471604950 655953207 103478527 577659423 511595751 636952906 78599187 964862198 611492597 428085022 428912822 828757409 807857834 75467381 466461509 483682847 760104421 190926095 526615153 491544742 859055379 536956842 284010739 868796605 748645390 179684488 329578417 665218196 48259524 819773588 429123808 873211790 403031680 348071357 451925073 713652188 494585293 990480862 949530733 420033435 421734500 783080846 655754038 308455467 767367370 106159782 937389419 313806046 279507710 358526778 508760561 956728703 898899123 224293654 418536197 455613996 522788825 695035652 861419599 438267660 150997207 879129040 315198265 898372120 413089520 791671918 376757126 488700344 692804795 756072125 811925650 821211474 502013910 416554455 23391692 16082577 346143954 664475128 139953032 898941912 721970240 267609703 371302455 803603346 729969633 605377048 265535641 932918861 674106547 57883553 484190709 850677738 915759 32410306 457177510 390141597 28555835 725165522 818317528 640906572 643205488 77782411 825513398 718310900 765247629 652441123 474729162 598251981 585430976 369998205 189598378 479994575 972793985 192902873 807295372 158531904 132731567 417471041 7484766 86238966 886861387 536922027 467579841 985485318 136865087 670559409 574258975 175710286 163848104 955847342 63515352 812271142 613462588 714717886 998718822 700072517 320144650 676109427 863757474 8565739 657468381 18041949 86694020 593010162 185090278 240492310 412019284 30889960 853139766 637581792 693060895 972111938 184695698 320859278 524886378 973323762 863019806 263025745 454476094 884627100 419715238 463158029 331578598 334815151 817300359 883839570 531581642 677177107 152665848 514671486 337786437 333185359 262805786 185911390 807437162 765884385 108286184 22551549 760768882 697605397 618267466 23408001 377742842 96960400 892612085 766564871 100637369 621264532 320658178 205442527 458187323 476665069 761089311 353200919 945478586 931369022 109603973 702732715 514792982 72950436 578930711 715710634 5444596 798602265 786963094 382750102 465416195 906623661 274496967 553928100 879687223 282663851 973509213 97087422 388498918 568356670 430619796 884755099 33324391 939532847 442720980 977140139 358202039 832753295 90418049 183016314 201544658 358377448 491554296 770604997 283893423 868307804 794859422 75683879 696360943 754757297 46703644 428736715 934564162 541771263 83986340 625433790 231303793 551535007 443030103 170936949 336416932 596177330 780969654 779934023 316038559 105899717 646583320 192472371 712560346 490335025 873878366 882858703 286676636 778693658 801263225 536083201 128209137 443169862 410061309 969993714 868975910 582185622 267441309 812241412 741464700 867340697 743218205 878450405 627361721 969483490 461424383 868423608 364269268 205009454 657903746 241052528 468990745 942431149 631778586 464153438 182859460 43194533 815641887 864066307 731190224 410045473 806356660 327140585 796846214 871197223 634326620 590177318 402480738 613846939 270812468 189780802 340021370 184493098 937610484 962976754 509000513 523530697 944098710 340781958 592363198 375318804 34592515 900378856 53285253 634860658 399434560 527722889 414935537 668611237 423972599 288983108 604391474 310461095 26878806 799618919 269859871 594174437 869444821 483557362 212982591 458004631 770804806 869524276 959800937 616536319 55372759 104420385 630734382 658511242 990948291 408476106 50541291 403496082 33050770 103528548 500988659 611961689 645093160 233780155 298290565 758428415 160960742 228312459 281589573 592204020 170422565 516200998 972129971 564328790 844408609 766036795 89754761 489211767 139128921 774085151 289426841 345345138 24549382 782025036 528513916 357696108 956017739 252677021 234974611 726273306 964033010 502210304 16055315 564950195 305083852 851937567 545870367 938305010 703726585 922591888 732333430 176558959 910822280 934162173 372816912 263209993 975455051 820483890 611932722 194910910 15742602 873656212 189341603 798248872 953416705 526187726 89175706 763515650 505103451 163282220 499487364 575583426 330822461 876405736 288553808 601127504 777212210 202993255 271668422 6428279 243922119 800020363 986790150 383443235 541103340 352273434 659877454 942588840 864650890 282989454 666810531 213213002 475678919 6928785 259041362 197215382 91785854 700167765 984006582 346825322 220505234 528135247 902872915 617240472 314398364 528991136 812181500 664709478 113711731 376362927 221569886 304052814 50607303 317394425 863329098 730809439 601363973 620807519 980622668 85719231 875484411 976983428 52357264 18970339 898448996 901973435 966390944 720261324 150234047 198395441 882507663 205782782 224420286 63253868 544543444 788904171 615797941 775443505 933205896 675350815 325284348 914169202 602452482 336267373 420134314 556393622 482605049 252227325 276415364 560141942 786738995 132276604 194241942 807695207 493800362 133506674 620339170 918787404 200535101 567360625 719692016 177709593 514747203 479424754 345360851 179591900 791192148 750463930 851994416 281260528 345184819 937864864 649395705 885745048 737723875 513951982 413936202 682097311 560617527 931635262 711139049 760840425 732995537 100345063 797588175 569258002 526679185 293453003 72259040 668301934 606596674 764242229 463069684 380781141 219005107 796793299 711444667 810459195 559252514 134384455 438840026 490901421 541498123 440330585 128396369 798978197 567975813 316254453 564590719 699159212 877620377 586593450 915099091 432071792 835884051 579892770 655710769 952942389 985421652 660113686 145495715 432343376 439717453 796066465 515526088 821154495 68302052 498365630 751826093 718910640 590850876 924297154 183704820 409353691 193375490 878794459 232350798 423783677 536411223 113876751 941319319 602286259 189169522 879192943 100041847 906317009 25987669 436354166 989204056 278062535 85192540 609719077 573196827 392474237 686664761 916224887 798562180 327910369 609187409 369951852 452914273 574196734 719546301 727403524 551045557 168126474 838123664 366246175 335931228 408982938 453569497 802763939 849016817 443037669 820743955 430504296 389826590 795607460 345012446 39190957 589241552 416625850 31637073 418300651 810602250 391815562 784167643 779443901 300937266 217599689 402424754 487005728 419934942 403503464 666399788 150277696 732107043 208131764 530540732 181489610 933076896 951505971 931623086 563940586 854894813 517656473 190109680 105861379 631316365 725848247 265461129 352871592 666736157 119106860 583789105 981849192 243824562 438684541 326902385 197128771 759653834 24676786 637347471 505025592 221407890 115091906 89966368 712765715 393500662 29297816 851586091 698267659 592678445 870587182 947255583 996154517 345057293 683788248 320797965 725705826 741028268 926124884 894645335 908767047 986120391 808048089 68309390 941415038 892863656 631116865 935344398 110131900 560141606 305752507 130037903 989452178 349997512 414326238 534016875 148524864 618468026 482949701 747801501 915779181 700049962 728237557 669357059 519725040 725968170 212109561 135878163 790222890 70735028 770773580 40805453 309862889 373509650 934638055 721247280 993034167 833012072 851973656 237272878 117373789 908991533 292037167 744856077 144881264 865395756 198497615 231835566 789392271 484994186 270373159 593710214 379388641 539182052 157090898 311066522 849670306 675265117 342174931 187797134 240932437 647108097 578093282 976866327 62409204 873002735 612912283 585251024 181906387 113841905 504501322 538101046 112997557 3377116 297398624 701188467 553454303 855876635 163002456 13064553 511325743 365925334 518937649 761679610 584434745 416861373 589489622 978635970 957905090 435937877 923288004 408804987 183336349 995361279 938071849 39013326 603771500 909218443 837991979 644802230 948632617 862691369 821342745 816807086 642221438 89084866 575579713 979111915 107065921 418306107 686726730 946959600 939560090 512021780 115570463 167545615 741353861 977465240 9403410 105790821 183984680 899618427 423310581 764838982 680791135 69073029 368714674 806733664 280749357 946066650 533204858 967888538 985757120 238530938 731388159 643394947 760275543 3221632 320160818 418308246 825586332 809582162 896237162 165043377 933755022 92609349 5315170 294408851 431094212 511967582 659294419 274704109 684946834 88966941 816411179 630006151 565380647 941460629 2078211 494962925 574866485 162534210 571318097 899980118 246617511 984866712 899379874 519043558 365415906 673855810 24227582 154815947 368917857 465403905 493494661 248563180 869970212 339563278 904159094 236729036 688052824 83805077 661279995 644585236 682434861 881840529 263205302 348147573 433139136 680829863 348914322 310168251 495787378 905541331 64328795 511333624 449433366 293342350 582507794 375572044 464791150 895138077 679363903 37336023 968182957 88734478 249843552 916113212 898898739 297319372 803354531 841038744 945261810 587284034 299333370 29823498 228814714 607030649 272894414 566004546 635618354 63460577 784346517 56640692 681214503 608063010 902590058 147884660 327013779 560110007 775985360 122409678 561629224 727676252 984307530 613153216 98896395 674663239 337586937 798501841 578655283 456239505 249122681 760399682 858397741 872078744 524937521 793105792 24199590 42309078 844830329 827972642 940621255 339661326 413049560 200498586 49949475 298099359 284689908 639167603 239227493 794590497 690673126 826742630 103361654 809338081 600566619 42602576 85037635 766323874 157665281 625989660 161498573 125967138 490729018 12900079 556575889 332858944 194012198 958599074 84620614 452903018 558904262 456284465 690458866 538623950 157085023 738532847 761830044 213911098 189881357 456821722 205585899 50254729 541561712 697689312 656358721 376446423 50253845 278037758 892352968 986282869 659724740 259758210 428053477 538239743 374252121 888077357 339081894 892050364 930590996 465655150 353043193 39139687 494428078 969581112 165542606 550609377 743697833 995154148 328141021 490721325 930806049 318133065 207843122 330791827 441618352 983863294 752538575 584251792 748201189 307401953 53875014 2602607 218058001 612015274 340370613 578920784 758487757 790581394 266089352 556412422 37162034 996458366 892344757 541473227 448023016 444468182 500309610 526793830 343494965 293891246 488186340 848270194 400702208 616380355 526248272 819789038 500748628 573120368 917487735 927739246 165279165 581407346 166238773 256295158 191727086 83375002 691610363 237282938 166627976 701339871 710381032 410406992 855076146 663481022 493753080 452394718 758349907 943409049 530884696 239453526 506051873 315835469 505484409 20905811 871352864 480595402 592180449 67740915 173977574 736491592 336710235 928309363 178419501 123725154 632856509 399078783 772273412 910615111 865986290 134232773 439800325 815201375 569372712 377692864 736280093 150208132 726487410 925352533 464143214 807654738 868190996 307541088 250705192 582856522 830324334 124537372 326112628 519859421 807286396 485754584 695522097 118258281 495770499 512171398 288961731 881991762 876002464 308249528 727197734 691936112 108885518 2126435 723739163 671411475 396198588 98124863 893920022 546015678 475592962 114708908 103361326 510272502 803497805 911621598 48330966 372965182 99736550 250508837 372306469 340266219 993593209 193335970 457568083 453234658 487051179 13232814 272676196 37378725 184270890 132705121 647295329 552185117 338872051 695318346 572201716 243838361 910785480 216958386 812103321 830996791 573133031 70204456 923749492 226663211 428873151 73343224 259242436 662229158 588982546 239558480 52885527 930988431 603917079 370324483 470580807 5365870 654060663 167711255 507798557 49117960 656527245 308831723 676541360 659853964 731812126 392514632 137651178 644608197 194814368 127721785 35234397 500075412 779009694 855431478 971892816 477338086 402961754 409492926 58935486 135375826 937483917 898418690 995793151 1567441 145426324 528555560 531738044 747120245 194307348 896460502 920605838 112529005 279593356 586576117 10464969 150034759 114578197 42591067 773079512 113079828 252970720 395875555 767217806 84398698 87760192 778936226 136958565 83423143 556915227 89769760 803203809 971817885 212330845 403366866 383252966 391029153 588724918 593325972 647003516 818649666 958228729 551413760 289716153 259793068 625924888 830750423 492338590 196148904 151692415 421523112 854819521 113701687 703218350 639199634 592491150 220369555 3396844 772256543 502193765 308423882 111708221 922447187 62453138 434113913 527964140 303170760 61196698 218798153 91649233 711899730 610538130 126907314 789988564 768852990 861088899 813098382 197191666 446494268 520089445 287200867 710822920 111168339 109899942 470128670 580797869 994721374 584521446 863897793 851067731 244934971 686537062 897608323 10996148 157666410 100306331 460025037 34942063 136126878 442287245 572803724 651719739 823848739 308336423 112897800 79901230 571086533 368541024 672112839 355360957 710900974 743317450 665729707 800146972 798712130 511577289 693109670 167430967 573903276 590448871 571327178 578247327 399064721 438295781 488034226 169589796 48211865 316077268 13923094 607245312 173281504 811958875 906270762 484660216 422774436 794435447 279408006 298058567 308290609 65001970 926843607 479170965 321563521 189406281 353006101 431461769 843231213 168244003 161035893 17132247 136285329 520345242 955762505 645958348 555037505 944268802 645977892 756116022 511337152 771259869 29229940 106950348 504269414 671682789 206937388 180130394 978000101 763289390 832028739 374978930 597555416 935221399 907984023 802295956 180650136 32497122 365931684 634885643 571758955 630665166 925065184 424933862 451031248 154681992 848544609 318445306 730807113 226181560 742037239 888444535 275995737 903369227 980996683 451102184 40726961 502364241 789869354 679006340 61056869 59942640 520701795 174532140 394253900 339711864 808177315 361611475 792394607 406329985 843692872 601205522 81553920 999502213 18257871 356364276 525127788 909959497 941025468 704099283 467201912 442306670 469758554 833211214 479137105 687521405 592889686 459679951 9000308 47753609 544676708 619730139 235312432 69987319 600764220 875340930 537304488 41985150 977360741 771799417 603368309 672837220 842117369 730724933 940381267 654146980 30087454 4208138 770649468 176311787 537463516 654311742 731436112 531399846 906294748 642681761 477284315 265373762 1312894 532868925 496152503 50996031 65366746 279201361 860086579 519294154 596750008 9851787 429514621 309440312 239136277 589113540 855902468 144820411 177609798 745562544 2350254 231700284 651643759 578581213 960809434 295242350 249701802 892769718 919331087 366488048 63710457 448324921 539621071 765055971 829421846 867200330 660432196 975291356 649815281 560863240 460830884 368527330 420231018 365969044 421239928 879420896 711656542 792938968 439872869 757397927 410528019 838197576 333439654 413241702 664356227 473442003 820356474 525410201 3207290 248559645 620573407 896974338 906317632 77215699 494064477 642379828 904015303 120432017 190411718 178614399 451635029 916088309 493071730 163857035 359869974 412093825 538906757 629367956 887717614 599922820 392895952 663129614 640834732 412496850 147963177 291386404 285034428 451995419 243951220 848163949 399924836 72629436 695318491 733323784 4661794 358335403 322328612 797876304 643519388 229261877 423452162 671023684 209126096 323316637 936809802 847405228 647245609 783972355 267344569 759103045 75127221 927427100 182572967 846832300 998191574 221885065 126243016 557832135 448904369 493942844 46712541 315908557 807672622 635819848 229366194 628074817 587342987 860368933 472874185 950735888 700377862 158151634 291941408 933695125 900027867 161690464 212126385 960821645 235943812 819350364 563264027 193835140 448863568 69410917 740486280 438754119 522838734 295094871 932516037 831480690 568876108 103027169 549430134 129126854 689998365 485537318 348338803 524908796 220107067 637858158 344100695 946330781 561601112 389287837 689651960 472106946 606069487 584648311 520247570 925202152 58718120 904423216 925434731 235839142 589366113 21883592 802145951 106529184 312880022 714129483 510993277 890501731 324457684 763261304 183861573 505811695 666368184 299870662 30084519 21167082 19207677 910585917 216194206 251831952 271410686 396608833 30854223 5229624 477546541 651509113 66039985 781712056 774787442 768791887 196539388 165092522 200688517 377992232 211248123 26496207 582497392 650155427 6670686 912194364 868923025 532061048 781371020 870252983 781632525 669313497 939478685 403105555 674107604 228632334 93754626 321307436 622451626 161709673 266997600 771141438 27049525 498814342 88206739 883617690 139025833 846050740 344951507 165588787 712968387 279760358 736785870 806774208 192654547 619738824 590034057 940356217 445543718 40116041 38046832 611108581 307373178 308701986 64951153 266968502 913443801 337885202 371633115 777673992 408275351 243557993 39238213 590944952 492473009 215774745 755168225 306965527 860087070 800156864 948442684 459625336 424837922 24923676 156032151 112412622 26154428 153598858 917156460 389753431 555370046 99603577 716397852 176781636 386853085 24154646 849545595 522283369 289643886 394536992 535893353 751296225 567934680 453987917 303951677 996683111 822262214 42651101 451593108 434049971 160225441 304723015 47549746 873051696 746095293 38623461 159344838 439822681 748218441 43435336 880684494 763775136 566473733 459407764 864260966 518031886 922550804 407692270 540219289 783671413 23729526 908762002 866782216 602146397 700724992 94510829 491159553 248092008 504228728 324811836 113296051 558655114 307621283 430813391 593030002 165284453 10381332 927055502 215049906 946050143 887812072 83260486 903009137 183458962 74266609 217254144 425974383 128382111 59352757 955842643 884724461 783744023 396165201 970480100 443053525 656534024 992469088 505332129 568894507 192298121 2372891 108251529 649993252 229404817 407350115 31736739 753164498 754984130 362894341 372383635 205555823 395621760 3074604 803308913 678148232 355399410 28619138 785073889 17014873 274508451 25478687 389043543 993045871 686811503 488547535 394241318 737499912 926167636 809741668 38073516 920482476 431593597 566978073 297718865 411876473 175597194 466355810 755564668 920987316 445497993 457703854 280551079 654339080 676261204 316371051 971219699 455959681 991020905 509087939 347660316 21160620 854711267 739719651 733563293 287261596 595313296 460409632 95258980 605383489 7358221 425092131 825769460 614146106 907409013 570367206 530793466 95739307 148250618 311609983 369723181 378124691 595748744 586904519 775857299 485084237 994024475 466760218 356228582 121275603 538522026 547812956 752539176 313158387 992816548 690789068 51611602 614409181 808229614 836638685 247931581 134642707 444169573 286756780 522153261 450688602 592983603 448232515 747514968 244637578 879506091 973402115 997638168 779973713 460620026 776854158 827233566 86793085 781037428 792581044 367471349 540266514 161600192 134977641 324180860 771659341 745468768 352654209 886262869 614071087 132896021 523336030 151490524 636646987 265831743 910250389 107651360 617813015 880929549 815709148 318098954 349226778 75303665 50969074 539305068 68139129 823371116 229451300 426409351 898554927 905747372 139392431 508392918 278592142 926411907 377355626 667615500 331188560 397433750 668149384 825468730 548392045 834972701 90394423 899933831 163099621 471017140 32699716 14501801 548486581 319655729 343513614 337919415 334215481 186515054 840295871 75464927 554594346 812917709 670807260 113808891 226814080 744633236 558026522 183709202 758544850 271586149 179181933 459908594 648348230 607726769 501108807 234445009 976462684 683747737 13858524 538395952 320462531 146752035 850136629 321331826 889536219 652066528 173254825 647073353 114308671 298199649 78961420 767605534 913667550 594502007 822202139 712413701 824008501 34572006 802583533 872355989 439744698 700427274 317314482 523987168 369344016 808565218 107651474 750736208 949604097 484541287 274171949 145334823 484265345 313271801 99260714 784906923 817218051 129206066 407240966 307617894 369477682 587539444 70759383 965480138 895427813 938675569 2621327 963076885 216471383 248952296 20466277 693764660 564838000 255525431 176620577 865320600 331872155 613943040 384414764 267887509 26227370 326153776 686842640 404964858 346692870 804968687 885440942 613424529 627924359 618633240 172278488 683955564 172370891 755097154 265432305 96792577 166956459 317632046 424707421 64097514 429932866 544447817 978587404 888937116 422111170 523070483 228190394 537458487 341068714 199908403 914519041 149404487 340622723 689914676 472370896 944761363 180805213 812280111 184971730 364584903 388823151 931345542 816810847 592543408 473593084 721826942 488120637 604485626 19109901 717648492 985369999 567201414 688251091 47577140 930046727 870131696 852021327 948342801 681108686 122008103 612538645 341873424 690626682 838458998 724957988 38394250 300225296 646505591 929274891 763233632 654078371 277610860 484319997 353703737 630077628 185505428 54053527 736088216 600993499 757323328 501793859 702860997 538580674 307286217 723720217 576079323 199561262 251468284 734112926 769228833 224242755 406224887 573369505 310321604 73912137 336742405 942638277 927592177 382431982 758451444 791610750 82896511 981036218 255658131 144260427 850837493 378431753 752026954 698595221 779547147 924412241 65986780 725462608 543452462 285918795 682190723 103336980 47412841 346149274 702880660 157893198 697911051 324582261 119383725 590482687 34402519 544565617 526457808 432761392 549442060 85458305 852776465 941628377 613073939 632305951 629230830 207226862 546149628 793533803 248268880 482669137 779087713 156180033 235915908 864984723 843853078 916651563 508511295 752843267 987568143 472900013 857880373 653001642 515944659 507835126 222157829 926757293 198915251 39617723 947965481 672091423 314817589 407196683 578075630 814669276 28883735 532348040 407330754 959798733 282453228 527326690 429115363 408520315 612451185 471170166 216000653 25303223 14931958 395440903 979874289 602532368 336654774 29906546 205328287 69472982 446851745 104566727 414230867 328500502 622842036 54353490 885844529 60659649 995291020 208948076 411554930 545028757 409485556 47745646 562332033 452807179 215827448 829350011 828421435 421650248 749514506 199989641 179360719 567210582 427076723 10819915 796435625 211124983 504670312 176734197 780216904 289875938 682548413 519738436 990296020 175722691 838223079 204541237 554370397 591273824 2335537 935526828 426915144 667860513 891157263 106309683 859882067 352576983 814783166 683174406 528921632 341105154 779362553 892828063 938588085 612418388 349503316 962225269 128640995 205247298 678111643 807830049 903493396 900300847 760793221 194503273 806749496 77836316 105670499 398799428 24976080 218093072 345306136 64210422 754205219 738063444 837524950 136406906 115949895 748253142 192208619 619507772 128626331 497317955 230783657 880025874 862177153 66771815 863327305 499219373 836757203 542773562 835463963 803322043 142576801 836235024 841052288 474958132 479287174 466210494 10058075 506466158 668374416 224809428 302706870 500316396 430587026 371481912 704321630 802164719 398570725 592670316 729352956 251618647 18611920 673534769 987675012 351707975 414862901 33661256 646453372 30860685 524079768 527344308 485669731 64820238 895939721 792593420 462150157 698221488 475854961 141410951 56949690 547971912 232318574 646940757 847635036 245563420 882408592 820878969 133610627 391929800 992064668 592474580 432146189 937765160 992055760 381492404 113747748 709538517 289295277 140566395 864050393 231123294 710820496 527611020 231179131 777235915 435096452 101352471 858751915 64442813 370973188 804279516 670383618 169836073 73462352 293433533 674347394 389326420 812775195 265669364 852556797 524449653 355252341 554782001 68652946 917196186 683356701 777780017 698142918 994666889 606379734 201233885 4760908 897087314 879182298 84619843 802024278 672091184 573138494 101047870 773458376 359626226 145904830 324359850 311389569 580559107 216323248 191139386 875267828 827384570 737778393 737124903 773249159 219168534 326414500 615980980 473004959 757278365 792143370 566213929 281300021 229124338 247665333 94954647 55274956 619968768 41885915 300653973 6436884 402797791 950253818 549698609 557884655 70139004 66740923 282935721 475940128 691874833 496151601 408314712 619110214 88525312 434444506 728923101 148462860 122371579 693686436 185930307 777690731 119583352 666872077 744806195 853450143 588685233 711364005 814404990 186809723 229390046 517512829 186407577 138986138 554108491 547754965 577286408 226806768 603214084 514524394 961243567 346264640 443028102 29258852 485619169 246054129 784698076 79249796 710966724 14324771 973536007 683610123 511184819 83265097 93452501 926644331 243994363 577113885 62319674 107921624 152964050 649138936 161356772 804513404 16140890 646875134 740595860 115926067 911370191 324389812 415185476 381628620 420980514 825701592 676619589 101366400 251760336 448801254 383368576 889516592 53968171 470073966 408023339 170829223 547890734 174195210 903305874 693705607 431204669 711751518 527320394 59582111 897291881 218952455 593392180 248442301 468847908 235444343 769983003 418218625 576953404 10222638 918799672 888280751 543997690 560924284 312670661 541184910 422035210 725539107 820441270 815748177 760673460 364039910 534716697 604994445 616182999 69067021 921098667 424458927 521437696 725011102 236572998 94990351 999526128 524241960 227159069 435100701 559441514 277293143 787239858 364394209 552238619 824075484 660207258 518616194 246659709 829196700 903965924 308990394 706431445 608355145 818247032 846075599 243075669 794980075 973569525 848160081 32018755 923807466 638551877 129511155 647226462 930529565 355844122 599085561 449250186 380429503 643176167 937204582 797254745 541648599 920775913 751695898 6438927 903937686 557499611 155501569 976166556 532889618 938282976 352249520 680701090 200182437 430147818 836294908 123146049 495837726 728709270 690011185 747921336 571786545 182016849 784935724 544136055 450279305 135665429 984978223 461816257 955390698 385669322 488035770 64841279 829786973 25258937 839697576 361735778 921141885 46903179 58812071 325548070 48913920 445594326 559475236 372507156 268361010 279512112 509426537 585023275 982231405 748049621 611750514 141562425 371624417 494155923 146471156 192478723 1331383 9795102 446741629 873936783 734860633 77093821 395294094 790590071 604934089 887656276 668424657 761192574 720243172 924087756 203920685 679632995 990934183 413154624 654370648 125541817 822767772 36853495 539535093 677398622 145257706 508457579 394030471 149938244 658515433 962114615 919892195 347124636 793099285 367465616 659915616 204863289 784135711 970429553 675898691 195358952 734082545 324246867 944865831 492084366 971425613 222535527 291290264 684526018 299888068 259461783 3632698 425650300 333847157 92805279 637597269 114947995 781104352 92923307 100504625 797400961 820293132 251055161 570656231 107219892 870470028 960585697 262179725 947851959 564362746 669796953 771070302 916979477 785535748 863913498 916725135 985508731 594214972 194460638 714094763 83472763 807827364 691835578 985317709 924153082 754625695 270080768 993579320 713246815 806264730 287237984 341887233 863254602 532140227 727685709 454193571 572227702 789190230 177447902 814725147 341977314 382165002 880804460 136526119 32917444 487771023 406428736 438385020 587174032 442033568 177741135 533752069 893545632 459942636 681647568 464738059 955337304 858471902 216216844 235786579 717485623 424294145 757677652 609513488 668836133 452152960 746503922 188489675 444317969 349900852 170514475 572796115 591525214 732279242 334499133 254415907 853873039 565443275 3443789 930125982 596421298 285467138 362701690 956702838 3047101 674858108 502408940 334540177 26494143 236759738 919846379 4712084 736031713 212072825 982822161 643058271 366505986 298801516 143646324 883878100 230569115 213846119 792508199 681707612 123755023 743967060 816080960 610052543 518600729 496040938 87263552 905220865 879404269 478761057 113942911 459614146 216113450 151496869 892987594 154968494 960127928 604594285 718173686 394284266 439025849 449930646 781925451 406504652 90053038 819589721 994860601 379733441 347887002 580870050 432161380 215150669 147886573 94981401 893746716 591121926 894365146 148939337 830787793 861442575 821764507 705846329 335815337 338043561 601682134 830618477 445100612 313416758 467014310 887189012 734783649 353373281 395703613 107087081 602265612 438137516 914964069 957230319 736702025 320090387 967063265 604369243 730509206 712394270 963664456 350115427 911593620 429399530 721877810 737422585 989485084 62568371 26591481 670233412 899213664 683930995 247373468 841502938 628592570 512754386 437833602 454067015 893854432 888670034 854738342 248880523 824143366 111155275 38634366 572127745 111327989 773463189 834721083 24592553 14729334 894793586 171490221 848076864 257763556 381933309 372240589 348431441 286999401 205543115 736049933 441952182 691362972 686599572 133952879 105116017 146514104 490213675 302366222 246424183 136851448 725548833 185586207 546207517 280598389 195550277 307052766 341013317 878540784 301391535 451116866 60588917 357608143 829614843 353486164 273905942 77245513 583445953 783913520 852641424 728464929 402085600 371975962 570100539 329779765 501119739 338861216 281120072 280463984 536517584 595931751 832976314 850797534 1777567 770514077 292637370 129478429 210712245 887307418 631930958 586777285 847586605 179182637 194918772 387336484 263579302 468306843 979923646 351299943 253608466 217692595 291562268 830327012 274339935 805076098 808423038 663071761 37062263 787617531 520976224 714154055 613747409 140480683 351676663 681264529 431191553 468691274 392462610 932560484 54140230 344415386 946354408 737275647 590215407 602879772 85925416 706762222 823830483 62274309 665591235 495710382 820952407 723501009 987433630 979973616 971532632 579717368 298865344 334520700 753947166 908895245 510937372 839249331 210040150 700162492 491032313 335924086 968736343 276936646 253980856 418636890 824596818 506396771 661446659 230806490 992568932 721205955 396790872 982596833 160405088 633924618 785658882 815413454 649670704 132739039 78302202 923884186 83027941 72220347 172381668 745185026 821862246 408863450 69278705 255939402 203643872 67682077 480838973 488585742 390674733 739299601 958350559 558818133 623715191 149327398 433014008 250414810 190655729 878486588 267144078 880905307 258550501 397755615 257960976 532300103 232136486 393421167 541784146 23124756 865200153 283439141 482325327 250150593 478137652 728968432 604353176 420810096 582446568 982663804 730097108 42532085 407131504 785104361 290078277 312339214 927059268 916321936 509030840 380943701 176104474 668703077 418881721 479622931 710937509 326245207 36700084 122431662 773253467 808130797 579627459 426838167 594410880 261480814 514219793 78080637 518239361 659886296 866433060 293178591 811768535 336530064 42526163 684409004 428881214 290595308 374407356 751822244 361603378 838283785 272302957 499613080 61089211 153060917 421055897 760997267 424685503 139375836 564729627 945170087 504151452 822306067 622157260 475863228 80848898 346884594 828394399 801283361 223412597 663131927 900915522 189799236 625267763 419316490 650578165 888049836 229510899 282073488 106718746 514947166 741374006 609997981 451208614 290142354 59522310 434463470 216423891 919102398 645491880 163040140 602068868 947493059 103859683 534272300 698471681 884428371 271578077 48578434 18014974 159683599 291763387 793363058 361744865 250888864 186130935 51529564 733955506 186196883 435451282 670939121 454591109 88230910 647903067 603660174 936484071 114084124 113513281 154587368 676412284 945768822 907142406 284335737 378036389 639545152 296840588 414982104 60532372 435234320 803156461 606090876 172273160 982598807 477043292 813881489 343644845 312792145 862848095 200926746 277446067 817118127 784487558 880884598 458763799 98412665 335203336 838183193 875297032 172670068 511210871 243869631 865801733 905711261 28159919 949421139 893452882 809784258 590783161 233244461 823616191 440799093 880574250 161644921 202565182 873065709 180113207 951230378 420497408 525232186 466772061 191074558 165954170 691009460 842216667 793052094 867201939 23734458 836200946 25905312 605238647 273045444 109115632 810493746 129256051 846465753 703437105 250348019 425479505 90364757 915984107 841639257 614658067 602758730 956260506 319066664 384379975 798333888 970397024 855426641 814043813 966523432 984584078 748996252 627675009 939308176 658951954 693873113 42110826 603373520 811459165 57941208 110069353 697290521 178013179 870042190 575481790 476062325 650543669 879852567 688273191 168937634 90185924 98053527 959212863 242959172 394776043 336296716 731648114 338614281 734763367 38867009 286854413 920882668 604632190 656542934 388069691 403899873 695093108 513120902 154826837 808575927 403973192 410841520 622926510 349429536 781892324 744952809 733049740 391310484 906447969 296836339 539889320 414284670 831970983 404875972 572289301 368383498 732215322 373824097 753326654 992877070 487147814 579063312 166006847 482016084 690594845 47931527 762173091 662331729 184245546 732057169 686911156 220416004 214650288 730932071 469801435 289002154 86515419 31297376 963280936 209831155 265814155 913373501 153158191 416623240 646930918 883848153 21572348 551819354 550358387 649372835 589050635 258282596 388503953 833961674 265603482 48965961 258188445 721320739 829199742 473723395 74592859 815517739 858474652 110695098 512732206 815957201 348894556 374318537 524788016 527329248 116772370 995148336 337413135 937321231 684392973 594953900 978490299 97597215 396207015 232960217 795317221 491036415 374235696 218428423 302181876 74295676 392546654 102455459 131660220 219522882 490978731 198750136 639099702 356603521 674492841 809202521 995797433 579965213 471532750 947968349 979434174 165361516 32241035 94262535 228566016 692970896 691662782 819991566 227728627 903982220 313035687 851807975 563977347 662987200 375816268 72390882 97431679 901446952 812763740 400689368 879744776 493574187 350442698 464109460 104266522 615421407 164059087 917741225 170966352 518831145 888903352 368421586 418320866 212754713 189367105 651647400 898180484 617364592 648410141 743085828 987146518 535219906 336855476 942428303 653001828 794243312 473381156 582223131 875797079 31587426 578415733 123675337 641982087 23994526 276033227 990614779 535684778 800320072 549704871 676020309 610182154 541306867 169996767 681992542 939518259 876015680 445233018 383356900 7316159 100253582 499038913 219913580 563661330 282774856 191148921 619898185 131514597 96673372 448837027 696126289 874818765 97210839 398587753 791416570 984173865 29555099 602530209 193879966 417055299 70001124 991217931 998508945 263351589 340718205 969031729 422362885 243819148 64784253 549374709 967722277 979439081 887021994 437024717 146044668 977058824 26340673 688633734 385512858 825792930 587875239 104945817 798353251 414247680 271002088 430021097 292556398 857540359 150126417 345911570 743578693 242593965 144129981 538880027 492046917 394922008 885072984 384079697 363056731 872767024 602853324 988491441 979144061 40415777 972769271 350826939 863410407 342520584 284894682 806628080 854202718 275210804 635903547 105877050 397821508 976273445 177234504 136948380 652222677 105779638 229665353 965187312 993675114 349624196 565975350 906332302 280118242 254499312 522236782 909862563 7504720 948147093 178085897 637017910 993548454 696539526 729457042 734687924 964145205 745358559 691961216 149236476 688514506 542775739 26711711 1317747 99938398 318717137 427269877 161399774 234320340 366229959 435401350 270037719 913541106 344975776 392546340 170728643 630293730 785950117 126028559 779111549 355073825 641533501 884923572 52902476 487558453 482896944 17766557 262156251 883362140 118604777 128206082 369992387 324845210 688562396 640994616 930495745 677706866 295084262 220112402 377422360 681094747 160944363 173818963 273190155 103902997 239364872 435914546 698776080 911459231 720998845 899797259 44405352 471635595 716310648 593723681 859919812 314777192 966039192 3261700 513389339 317563365 636803552 592105856 188316250 36262963 217267518 748700418 999073836 554684206 136689138 383216778 887023565 747219939 960300114 877851731 720311252 62806086 516632439 408644616 800438730 255284100 677607782 955193311 227470008 968575433 925270218 47384420 390497952 110110326 576396415 71527063 59902217 34382981 844203439 812926242 735991807 718744915 49493524 622121568 959959513 332252808 845846355 443224823 873101157 62414561 497614166 216070861 181021826 367260193 537945584 867667755 232143304 790956300 157640193 886923631 121039758 268594704 7512363 947005509 94584053 119331656 460154379 12429611 325084792 819518389 20949003 771710381 74042688 310340293 225390453 970483276 734025479 750003618 765272779 725489976 139422820 895487502 805879132 218522848 678189033 346100988 294401052 862655799 461345792 697169763 735647910 246626552 329903863 235862877 368871641 597672836 926975757 65568311 515054993 293637558 305427279 364811422 3938617 982630034 762511645 441453128 506387826 775473128 413990766 481341061 220078247 892154028 404101626 197384856 267373873 807768593 57527821 817403275 523726553 523725951 976511136 89096097 786555799 606781618 935045573 200921646 473371880 768520201 807633596 74725389 119049586 316915776 601772323 113632833 662040464 251983138 141709880 98665902 290515345 323629682 420851695 690742325 715563068 980339546 330873921 478252767 446189655 346429957 435458602 274761245 637355643 651345957 378513156 562153304 987824982 630063773 584343183 280767687 418760539 582301313 65283629 167048278 359004561 426036870 224585521 505425045 638706144 652843617 370323330 78225712 505016125 456017618 334972903 210731042 281197072 680871469 920568312 578935872 857193486 416049211 316462403 825398869 265184088 369397937 21958230 507787861 468973092 135954462 333112236 158511857 860844729 322330760 452596667 144538940 832803479 186341720 973080812 883198851 197331088 647297714 410329460 141459546 540473396 546614296 981909005 40296314 970004223 998201872 378960373 332826780 476176968 528630477 923006266 551708739 965736753 525058279 668783368 599429385 917382542 257035775 745553658 877883184 978571696 497055391 186789515 892423429 942991546 907286474 767838919 198085954 478455919 553764303 799123155 213487348 323008264 46153039 730835620 262850343 586030694 821515266 12034840 674698953 951497148 211959749 189502431 899303216 284358208 70230841 560633881 797089152 965856614 880597135 242874543 203331038 333879274 642388480 487113923 315830459 82461759 957845198 381876430 373726326 618415096 326670864 373503070 985190395 112136628 286048120 697099167 359932951 934562344 830430856 374803808 256045313 83766542 392186048 247180483 522156544 55572561 756841940 974211384 388153301 806777237 144230230 217393081 794428813 154542362 766815106 942987142 161162989 979128542 558503413 943672778 100871799 405181047 561759396 381857033 40162757 644906959 485060756 652701235 892141192 539498659 322325555 213067984 747869966 1933832 285857512 359454911 861465356 930636055 214536630 872540184 871842403 749831321 384410782 918078519 269294540 339087748 701249654 618623749 27810427 142582528 830174568 922601541 554613631 375816063 642993834 502410363 867420020 868900442 276083498 538333377 389964096 969221363 971562289 882683456 743291164 446595820 584952658 873420839 308478916 725725529 293965995 241444209 701620258 706386013 833435524 876561999 352972167 37113826 977366627 397792699 609369212 62648486 865221275 314043453 691214597 999261636 821846675 31890682 443670516 822587313 132591364 657505763 358555429 11096439 275906661 934703486 818600670 834611735 142727681 294950054 446805879 414070176 19866711 863308492 978847884 985770570 450556586 538232884 65990968 985244600 323721088 463331003 989782524 879978251 741533541 143069672 296987973 690619808 199431562 293317890 802697612 593560359 673191216 843360686 221191442 828474450 743649745 637048637 2180257 80252398 743868049 14667744 979872327 71917744 733613797 150279703 956034404 957986095 638306642 104458102 541134719 10626198 794001390 52549097 913445850 751140425 539633340 89444909 44940243 754662302 880743872 199323400 922731788 298240477 284719644 115980467 165173819 662179877 162721345 181129475 847448343 594873405 735116375 160722022 348490058 360642610 669448324 674849809 140119048 484607655 519139210 303593038 752382017 658211432 20061546 238344291 542304942 345306100 681370460 641279366 499967698 571234711 615077928 26914707 599298175 132075855 128447420 861816351 47809258 922516220 921577691 214566618 669147289 68650042 664475245 255157620 783180261 47956957 212705495 160622946 518963438 699952940 500485246 750018414 911604630 289948237 187604223 923235735 845730595 337238497 314683382 969904456 654238677 592469745 470358007 119787477 404686594 9964062 896467718 310997482 715502528 732383855 382904367 103391596 103766997 951702228 698043370 743158788 995919722 653842489 780652682 215823265 875446306 191625476 672533725 945200226 234330961 290963433 771102881 292528771 982828808 657906885 65062389 531263146 133725542 423115911 624021938 950075148 332436845 300604375 788047671 99299592 705633718 611095684 349909423 433112318 285444991 494872801 882126452 410470885 171213944 328575012 950161166 217673877 458845075 554587117 18242449 235311642 233413789 965507495 634468600 909606471 552882060 558023607 722754156 636302092 220274091 136757768 375577319 221582963 7331390 586132670 101693873 501287095 444996389 46560712 199179836 405458057 309035917 81549571 9008060 413200680 951718172 444222242 429329700 329565891 536536135 281004076 634218501 366561032 565425990 313350987 794627634 43900047 42531504 192151295 875208419 642914275 144298038 828194121 736388123 859039219 613622060 67057409 967112892 142193462 23243737 47476495 758230246 982791285 830726247 365935350 698072903 440461029 98395818 32171382 148911454 849376323 675837279 504972912 755685086 717587615 512912331 196106916 354858234 148020272 808917633 916677334 328228458 778175109 995974967 13808343 966935266 4972496 701931834 646432253 822971036 772419246 698747913 705116112 591036406 20052890 977424413 717297483 599500657 44312861 808343588 642079392 261889284 201441123 117171529 829321032 974417590 290350548 268605273 770391665 121491948 376085331 507140837 454048124 858972632 76068225 835226031 492490474 513194972 216850047 931690817 646550591 967911747 974692531 513387876 170236441 401954397 289747185 910076887 945013891 752709857 836792769 432348821 277418069 226453710 397147989 762807015 51974960 585713565 44927886 802181876 784483049 465321727 203703986 675128026 332131526 595189111 931531676 750073134 414155681 785501404 469801839 753208272 529296748 877028282 960765564 226661668 593098319 507747716 626328886 109425458 948064194 990169020 929165912 224691557 302869589 427035206 613745930 141311588 274579674 575153643 307643881 929597874 108444647 512337506 95851570 20090584 487352932 592770162 47801217 407727661 320555304 835100980 261800740 556169369 691926996 249803194 100834200 342653469 262429429 535443519 572561734 803601828 380601133 114153233 449305742 106572986 730088503 670824055 347417501 193628986 681528287 496435577 905263805 586857508 567958773 266871403 556004981 295321080 345885499 723172358 239633633 453432856 832538425 998984630 966001055 171800179 329050469 295040801 782495890 259000419 705958401 428087078 660952096 141541389 813191416 81152889 397202098 407936135 388537654 260968638 519696062 455508821 757868317 299947329 134928893 436177682 696041874 996757717 239780538 34883445 420344268 963438033 677404869 500806839 455014636 534371350 233762621 893875568 972666662 560828141 812507303 417980534 584219224 634828780 559231732 170830108 641188787 212334780 453555302 698688203 201092295 954235622 871009519 766760941 956422110 347817153 857714620 243930342 944989046 999335052 459987748 530874642 961658306 452883479 893547620 565139023 521611791 611978181 289885075 465591814 404480396 664770240 764107854 791016009 428455593 637837181 767912851 918760068 834330488 286647594 132373746 187185746 216659356 27746741 304927170 771381227 380913469 897908800 658890627 987755218 884994738 157236843 720146335 888406698 60473005 834582995 727483703 258380846 29438319 874263654 537213456 889770899 70164834 814768810 228764500 639060924 30768484 359288143 652226650 953543706 350437277 277828017 644952141 316896703 854240922 421688154 842880063 953371565 367270403 960625540 7238409 40558567 927647638 684857190 734655278 158763742 453895080 632764820 41533649 881910150 91582425 735820536 908333735 797974857 345326080 318637753 318084979 912969881 148531318 742487894 888776713 221842998 670250121 753141161 362887447 404816786 900945913 779455253 757267750 155790641 568214607 718934840 356793305 14040629 395508629 88010646 927784409 362816340 14696183 87793272 887410164 366956133 258989904 247151753 767597562 782496535 852036704 537277674 520108730 78780085 339809153 979040992 727543648 385609439 217886725 378561298 711531431 93829341 959021878 88946991 108367924 879373046 792625562 592078244 886070575 260519663 375206341 678956585 162005541 864021410 175319280 907008243 276696661 351707940 234255346 640558392 458054935 117705249 915843176 942429412 328232548 630102288 999262171 778916819 928786558 891352093 985294505 998653077 758016769 843155659 559416338 934787254 601036785 762847910 342663014 510709473 668635620 543299512 924406147 588307830 451620569 844982374 964658784 97553347 729333157 471819771 838418169 382358761 166852970 31011751 913762351 661348144 987990587 135550085 572183364 790741375 916376043 582216532 293413866 2688658 341483616 299870328 331734288 823973532 685666356 204166521 534960915 826063955 78005542 555242708 884149173 429106154 876003248 599979084 985379673 409734669 973981521 900771446 34132710 69609476 185380081 468384150 735035093 619764101 335892635 877539118 867435808 116504925 567337451 906313808 755843277 44200987 951409250 441326867 166808148 211493607 551620991 246825254 149950023 535836219 588682415 91513188 142542112 808281533 451092282 488414181 195299537 764961212 975940257 898718398 327890456 688691844 10374254 310367684 407594723 587743735 415809242 72514619 378129684 415210343 343334117 350397207 72044027 102820350 850897022 932589223 872953593 640208157 863138682 848531506 760002594 677715955 22832693 591640451 867283593 791814427 950881737 269994898 227075465 776722112 711103263 703265893 495216224 760398209 230417578 664090507 461520692 633839640 997773674 225708406 234319050 901873750 453040646 550134120 468644022 361368651 671939108 167640492 237751305 123037516 200103882 989457217 102499246 732742369 22856159 447537495 200750552 546453958 431090367 232235132 110512635 972056087 634908973 46193572 247073670 321842904 16708865 295471864 923714700 973354265 354542588 396508461 934173699 629999659 581792783 600799972 95356646 136281145 498729728 903769594 524814716 568368205 284957461 217481271 950514420 673520688 388919181 168447780 824664058 553421075 196216105 843794689 645667804 823662934 679965137 96378880 855880935 561035216 184886157 776685716 508612791 380671351 372718616 361678171 264413129 219276676 411485537 881542947 223145231 137665211 359080471 416905695 490025547 502025244 656481306 208547129 319894308 53533478 951784381 934835563 545704367 201163026 939531858 836714050 788250070 359110821 180994565 791072466 117695421 972926605 287303106 39306324 206950464 351515560 601601988 93452303 542144487 429019252 64677630 612118792 97278669 690395034 581859475 33492213 782621834 829828237 642945381 868200949 786140319 426176362 115668072 677665943 507160932 806992441 492827779 740516363 616263270 546119662 170453120 679221639 844527439 819846169 190482373 629649440 842683143 218582106 319479477 314349738 432233332 178775761 444553396 625544703 853408105 220643156 257817032 163366231 119987707 962551653 514407145 918111831 436161866 865712892 972998999 117202939 275624721 348692086
