5775 926432
596574764 199611790 638738617 469633689 631973094 663852864 191624780 159689406 641290123 48134355 550937756 68373054 881068219 801037191 889305582 293218026 845459558 804929058 908854263 386567106 842248351 153055307 971610097 566095720 823134581 778811777 889069079 155960970 659578445 232620181 127416332 196275738 773762432 676958795 580131560 605657925 911246546 626501933 843882349 119442818 98907014 42050354 240477777 355119539 688144510 31578441 998145737 280577056 702590509 113134059 329974406 496910381 261529867 712499018 244424342 861716780 429693311 771610214 846439325 853788629 611095826 294839952 309636967 253816929 933909230 884459278 340211254 729884711 923728073 922585681 510949086 256456161 869449593 596152126 340744815 534297421 767606630 853481461 48236609 382666360 359059181 644703449 706923744 622789238 749608462 699535922 696946934 396168753 975669272 364806554 952981510 70819970 497266796 587497336 524146978 615896827 413434644 375181538 815536678 604106570 860370530 680736862 719447246 167513214 471366832 955802352 499553979 602539980 147199891 987933008 509017015 339716181 661852425 451736838 754358255 275677405 577867798 975725749 640008149 556764405 271939519 137172677 661899912 568556149 262576226 666640156 876461242 720177883 323712786 928936422 988663856 368841942 410580501 944162181 713580580 985518704 187684752 36714631 217998767 541653131 680370048 543474944 437886347 420416925 736824035 745924138 658798918 864153803 10726925 451696626 852456033 228365769 310381165 710065744 626122947 389927711 582485718 829976530 958589797 775652779 935919633 732092316 692331998 27324266 402025717 608118733 934534932 973852580 166559836 533613310 451690380 159782232 858349337 736266506 8763692 449265578 895934511 904022346 307124175 232561332 611042137 445734016 687159758 477395464 428670269 296660554 560595808 70960959 1514505 756211268 535943012 79695789 350067411 365768017 251826292 790285390 794937519 297632062 694506234 479250303 821898442 378035511 143680199 462653472 706021441 264236416 946587391 550757811 500073821 433437858 781430115 321685419 999436805 941664033 37339180 462842684 529057495 206111816 741534327 737689168 888825278 88695452 127350987 319498521 523229823 620130296 562467534 259982721 590648027 189730894 952140335 551459650 609980384 813557274 750993841 724083148 224832434 254584694 629374378 741870241 612428655 703044407 563380314 740198268 546468409 448199577 69045760 940493420 856728251 687016623 617312589 897435214 128932232 916834351 542245341 183919266 201863380 887705114 742965641 439208291 531562901 369776209 38070037 184203882 365695845 844463450 870927849 579312038 226232798 116810136 77211817 82318050 652170810 902541443 926260817 864213122 62044035 602647817 613188872 813049724 403947215 230100840 491447305 300552515 949938033 445992487 842105237 962157884 741374928 291061735 371225900 592826599 102132557 905634829 43731604 328868528 530773531 215632155 718662951 294264266 282399384 361680018 307653093 679356622 867088626 215822965 511161298 573057573 781589908 161989733 383685239 461804051 216420372 159909418 278388373 615324300 365617856 825014257 168821063 779677092 189171571 772132529 848441149 652076165 737629438 22494724 607999486 554828013 52163944 37734415 916298561 611604898 107000586 229902945 510129795 710675325 367195328 171796448 311352116 373857448 908146619 922899713 207207046 890934941 602214485 336031131 548801333 91124938 754583342 922197331 850386993 287819370 670211656 993784888 421697646 370249722 105425168 772224368 380700439 488598714 962092208 683650941 734851072 748633573 299168197 97997540 889210616 628202292 134009693 808546388 485829739 25586795 639377368 90149947 714968471 575654179 343136938 821027702 715743794 756111301 735685495 418241555 74530409 320740116 591347334 26777566 141747772 22629353 309170608 215812556 687952403 656172630 351079546 409131487 675574154 949982172 212951102 81229664 14916532 748868564 808068856 451410858 414171089 649998578 126082191 580858978 861289100 521318051 128184728 512686074 687851205 771202768 551800574 855795293 698116440 640634589 264728706 415860804 283810111 432791659 87113673 282942342 312673767 74068800 266032927 328666670 904150252 963943360 944323473 918307586 872201816 671851183 345860678 461455061 444834649 662612370 488511259 796565620 344429291 118519417 554650739 931871472 926678958 351013179 375719949 71995718 538734955 821074780 727077473 313965262 11031021 512015630 963875149 937862721 977910921 868385351 381056785 762421918 297758675 249914206 528746664 235757204 328510264 687731020 924776197 922284296 575764905 736003777 244295679 278284418 470252766 724264418 226677234 283242526 638823399 589609041 90059145 667038777 58841495 947919090 655388747 652355604 850201416 49375185 673435418 297802063 326447465 335797570 699847815 540655060 721051651 843091768 821850531 301874967 48212205 887985375 695275534 854261181 874041527 416507549 217056861 123728903 649472422 710140193 998882109 266664636 439200666 341977771 502109148 319364739 760041502 483338921 833951761 669420343 160306918 670771120 580222589 825089703 399375989 120702397 743987959 610876416 448897474 390882613 237958988 632372481 314166629 182612989 70918379 222020583 489033852 429035472 637466450 966084910 799726055 247230273 774289885 723449152 527298473 957192102 311154381 280086839 295876894 678520451 234497926 438139375 642305767 837802887 228031339 817709308 557450420 323915169 160438535 433481369 319482471 679491283 489578774 328189857 602524926 92732041 960779674 179924481 649708589 166660979 524057686 412758741 194793510 148520760 323823464 747175093 580149212 782097520 769253393 995230043 964889733 717250484 54670354 648238916 452940614 804770895 153260464 402227031 326083777 371944845 226702651 334168583 729368261 702232877 72820425 867792728 581436862 122434221 623213449 549829926 314422646 517813710 726728319 247144219 504674424 130642401 167316711 772543391 756287056 464292771 451453623 201395228 974380976 944470462 781053033 605543752 634231210 931511031 431767710 632347336 108444135 270200337 690886588 134444909 678363905 970708465 811930221 383630481 816974484 256822197 84639025 128637606 768938448 36413956 766992040 766412944 709901824 796458066 589200538 952363614 774910136 319447566 20731976 137114570 490591349 494549097 360252324 441632968 959262827 1775065 919297103 301376096 298732504 170137389 226732574 330410409 496361897 841805302 49424688 777980386 986711407 786317659 274499804 720698937 989343259 215057452 271092766 881768452 585879370 602032140 955804499 796441290 28301835 906346380 344722141 25423988 581890002 20369142 609486197 432310348 66212697 132130470 101060626 350533394 989782943 218203703 11835137 172060864 109887312 78961814 867899144 531777268 216423023 20049972 677045830 802745949 71854701 326555644 770177300 526883110 167475104 648337062 745622040 266980830 126322797 511030519 716371095 606300091 241588323 712228810 981360666 239515961 722051008 624953289 878400439 522783627 648425901 675448680 66048798 624356301 941932002 83752519 434404017 247450622 144990839 404952703 233050481 610083673 896622726 414906385 158632784 23931030 428294430 737273892 652086519 664519085 883186523 565426435 587412033 206116910 255837514 73793173 83600125 885887669 201533902 453144668 353363692 643436269 518148851 219377486 770198514 682144182 411574332 544107022 958965900 286425842 300666160 839410786 120260905 493826243 497034823 45794878 65761314 7943933 675874810 857957609 655809485 862954527 858493260 895277897 246994931 753897021 573560214 695675703 106184221 243029086 738439979 669895369 225755833 334231459 734852758 370022815 532430390 454486904 622580738 439923052 557601522 290130184 953101306 580910558 324304584 681576295 843934286 236445004 645724389 896716152 470716346 131534952 708533739 631026988 933463606 330175855 503644135 617185590 708286776 279828993 912482804 311898514 523089400 800014466 689328004 466984941 420909092 203185389 303339169 537662534 172828941 315964925 897155373 980152027 634428257 840474742 943067005 799434837 210895810 810507411 987765575 303054134 94666158 149719643 259926069 312534908 294340971 647589888 453045852 231159285 484441067 344863410 764122762 421601286 447900563 434983639 986562097 563665063 288796143 721392690 45534214 607788655 151446022 253566099 324760995 433123031 754133098 657270398 286570766 386175190 406704131 272039843 343437104 782149690 177426419 178017453 322636377 170030912 945931072 226999430 993412580 171570569 625013349 832338670 71238304 214682522 985453885 112287099 434671119 10338620 759411906 110703416 746203870 382021830 447836880 373235648 523519491 979130424 131724223 179151081 92585000 77907579 964487902 761173019 711038205 503533694 406600512 92838282 833869740 255861984 833391573 675594941 906178820 920741808 29435799 271651016 826425613 898571387 431972629 93321101 684218938 581327765 947967099 15557594 455008305 901218411 318777536 827890323 175486256 290086020 795153703 903170488 157200829 357080824 702542307 689076668 339873083 54587643 869551661 171500697 277595179 917685140 670221809 896300350 112220084 84312877 467897502 185073332 447253064 905873128 340229098 244691663 857002768 83533642 603370906 356622802 716255989 840783177 544721824 457810249 239553195 158505067 913903410 574173629 493665768 305591850 949386287 999812271 928697461 868968423 361298422 388986892 713922514 200910450 304271219 925417479 398954448 644963804 44774668 453686631 91404882 493606332 653340972 208758643 44162806 735651879 948682638 857882788 691947596 507766877 986086058 273286834 66095253 557205414 784226992 890416113 712205745 45021747 328236210 269703150 793216251 618907320 530295632 25681902 209862315 442595816 46102216 188333520 758891218 612008415 175931451 530804591 534098441 463215397 250531755 379091658 240074623 111685483 804912860 290943064 461872974 601822701 429540079 370000580 64444087 684561446 988952265 606828375 236780987 373282854 30882863 16794769 73846898 653079935 342479835 474788070 201691291 728677654 888408361 32123953 789928042 337851424 177154437 850154430 399078632 922039062 213353615 284326546 351510443 223356784 602035311 49774594 369169425 557451290 861347289 201557748 481003959 756053950 833435008 771140509 440118690 68873677 428029484 749634363 668509797 395721921 877144212 887105375 55707540 402516064 952890090 740191710 771708864 847259241 241426645 746735318 855447629 593726121 69861771 341218352 539383758 834851767 916543707 9996680 155808179 288326244 903017330 858410563 996736052 93985397 45514239 877811824 456904370 365151206 804826851 644335604 660238958 806910818 940567584 446547167 546647061 102053759 67722619 774725411 982499601 86830756 417426067 297922672 190866944 496402271 352975766 814989789 142407999 823424680 869146882 261064920 681055779 56024138 986844457 26277605 397810806 341138565 60794142 630363850 306093026 703282327 927636683 194992690 845385696 363955408 789115254 50211372 503890292 998829446 658858499 998952986 352823441 253837631 743084500 252347419 729948385 418255891 749148992 316972856 109721909 859447955 914142727 482105036 487977225 920773833 848852256 641853282 753556137 675377685 677789639 542648523 936423457 710634108 840772891 478872755 826203214 751604929 426599678 916338184 548634706 48626730 151333072 649745977 803299539 544869161 307198935 612276949 784527664 748051421 500010219 27783655 311631555 290396943 610803844 493850706 689291400 633074467 49514180 426208075 703427305 50355652 165083011 86138957 217274835 160872432 583645331 619748462 47453788 356192086 862477608 230604118 592147568 62507930 58326135 112530823 791425608 69698605 188768012 357011479 72953131 962655129 860371150 67029947 579527481 736366878 347115711 826982328 398171288 132250750 349874365 678086490 194652788 26034491 232213398 683357734 621752690 177476093 144176503 182423567 719392042 837543050 249308146 261033871 717980921 119707141 470372017 680889731 950015451 577599071 460812084 683264414 94897752 740955268 438455324 736527722 373272061 247624280 153283853 863684136 743482314 519059438 845727740 831179261 742926820 89408449 224637458 608192159 922792866 277631970 343173350 36236531 240571623 815743424 260129293 519175870 498189310 634338996 385245213 391709301 82121130 470412970 7492616 225650689 311740033 617191967 233674259 274245521 860074029 3112208 381732644 613042221 50933307 292364922 507910026 517245763 451784303 701985657 305935526 663071715 845706953 661688934 76338132 500260446 297575310 201152890 230948195 367501641 26000603 21290514 844225001 605842238 432770978 286420256 404642386 561505983 68333403 545662105 743978730 443314294 886377113 667597697 802984398 667405177 886539150 99049393 296957190 385279990 20325620 165771198 792100876 367460913 821369987 722487631 344211782 523792893 622727271 616506266 764676767 674369534 247480591 203235772 287099121 19886706 892617288 170835770 470309211 331353172 629002081 713045903 958756250 892685700 634560123 650480126 452772061 59041252 602165470 31824633 208697107 774993981 308498757 836193080 52282251 910510793 257217736 847779613 490475945 518878441 771968476 612429669 385722655 800595564 374734487 82188984 261938014 238304828 257249519 686083440 708383215 181742310 148652101 760000902 972048898 695131171 362735531 917874669 331836213 458128356 599086741 452446645 64026892 836219494 810798276 751603361 525043967 289682450 607127413 433944905 101207627 69702483 16849438 435843700 74856658 314539635 934292016 261684669 573309384 138487407 830349654 981528784 432768429 363671539 767287833 522402181 827061587 426477435 61352178 533527645 230408457 937064346 314174357 66316891 214003035 600031460 447376202 843074293 565411807 580354139 723515167 946587421 342931259 313931323 246224086 702497776 600218432 964731474 336720928 42554944 429898261 849586544 951381005 962964910 8312730 117657200 219163361 331453936 493141239 999886479 400190505 764914849 378570198 521416448 875923763 337686424 239524322 78709589 354781358 990647545 660024559 125161947 888438122 923799272 683221490 61222598 997011879 5556175 423955481 316599090 343822552 550438773 800289910 476451154 813255374 907426899 103522726 856266388 857196561 781211866 488993502 52257254 111680728 568295227 979944630 87980078 982867769 983938682 501660423 63783100 151535276 149153677 747937227 228852876 911686942 3882822 518209782 600635067 772151866 752611732 65856574 592793314 943046115 489339334 877023193 226702239 304601867 792488191 84458535 191102138 394074187 996433303 569991549 467153316 452590577 108188906 270168082 912119313 885053008 760542588 631280732 848772017 665390299 507208911 5516251 237488942 364662619 842059560 781176488 919884061 205328271 137476780 776008886 364471985 834045214 716100299 656703691 989162360 603613031 562438785 142337417 171661232 236765213 557597670 844687383 56344681 971267850 80394298 178903387 545591960 355914442 178825046 524434010 849987283 511887580 465838887 222907220 113768698 800268095 615587475 388621255 558479238 235311451 728183661 160143434 32595839 532690685 985256982 393313177 678626134 676288381 588382846 911181435 439595107 514048572 758922506 23853642 595261800 93612015 184542289 145040050 617018451 360771331 421701588 634555059 984124088 604094092 868279806 297133750 925884926 42909684 947721907 669555048 544650202 270264610 76040225 379775427 399462680 306617069 472728176 717921333 678062884 178109989 222710095 625369002 389815299 395263588 541099666 270044972 262039283 549098196 633450099 69575791 214986194 397188718 298452385 268629776 703617382 468097446 728560831 434057950 397488368 695179248 136711537 150815401 451602776 755390692 84796166 870667061 692947194 271524126 755472659 400581067 265090149 160668974 131892709 575430689 257309420 716514630 797884135 829076356 769667796 18206930 129496883 478639778 900301156 319133022 972103934 382616344 614356681 698379994 848273569 154944382 458432745 802751450 896617084 477559571 258486787 278739604 718007041 767185289 7406759 941646854 818980202 29746962 395336635 464770137 691004418 86003658 891432846 824312506 856039782 74741764 232592229 980704788 867333331 364791898 181870925 595998012 879425555 818840744 534929781 536307743 296111148 313897664 263030732 66250070 565139547 756721242 402893868 163233303 343057435 415616042 482784479 307069041 40697866 648294630 968898660 662120973 44047616 658529146 768184762 691655247 740633470 29149393 621415495 337398127 324843175 673507079 501750399 254456157 312108721 240065132 257878065 766039663 245758128 405727926 729021088 466190321 440844101 903283822 958706901 432944810 822236539 324634827 995024768 161752638 332413327 784814302 752273037 835185694 47295118 599468872 223696388 402539248 706013208 484992227 487414437 490638619 161645642 913179424 365874098 93889231 998874225 706055356 705543703 994480051 184870631 565156078 350117876 445405837 995062235 634239807 555245372 155497159 353280354 993448751 101155805 109334908 712200984 989674102 543402000 581761375 39197751 142880920 741434307 438063581 779741605 277033882 621370307 424197309 795840023 120665457 438149750 482620298 243063442 387479822 184007949 510974375 582846518 890501159 211617147 949533870 428299458 68993416 994852568 897102489 701855222 470950786 243537257 757235793 697978441 128458414 490212013 506126200 486100738 506390391 245135826 406759705 955123000 19010719 764585352 589008590 471137919 273477838 504257318 141533151 807055514 488731627 614750918 984180023 976641286 491711720 686003970 522204955 85317571 782229285 872321217 717199514 585428173 405647645 280630169 576601690 722596674 197656456 252216632 283494200 459848739 775377921 149329657 407953121 165094904 825903459 133580481 550844661 934190891 535153937 952876460 548057370 880819646 284818684 449280186 656616795 732947908 89490723 917842257 60128015 967856593 762542776 554441062 273500561 866089590 961060698 131344381 160187777 860378877 794649442 64915752 135788593 913599323 582350833 529313530 516310950 803991724 738024003 268032645 479877745 694749490 517256269 887770023 819658872 751951394 189876691 959028349 647403251 109425238 51456294 354080594 126009391 264135828 207947571 463430732 474057465 681294785 652569210 998383364 27850012 527914463 647003601 66366802 825303479 736366343 169647177 374296941 725685487 889834825 688812609 921044956 241636145 88736528 320040811 284797629 404951352 515736388 667966658 359376427 165084800 138196582 903238209 822315025 408292723 786930597 997085246 752238009 231758076 852565282 894432152 473448127 866599053 195724362 36066542 739052127 780034956 913144982 749211581 610882850 138115941 917244936 94804235 543780460 403859090 337326464 813072728 962609955 267618744 941484405 218381310 682623815 304225413 340573443 523861264 913899637 621254757 884785244 822953716 100738787 777697733 813863214 108536000 684451557 287971879 108234966 198211874 684909369 275274758 143166797 459730047 778708989 625220118 693457025 980167144 200411445 991926063 851246014 266275340 840935774 451027147 159806547 415218824 121553327 889098065 119618594 450212009 764626681 212460062 928642650 48186230 316188465 794961534 142314710 42909955 113203583 190801317 920288520 880285381 85330158 253697092 637368232 676461913 440763804 672498556 607481488 749216857 329286069 623594421 708954640 466127932 725181558 889865168 630139325 700476945 311437476 817013776 30063170 653204017 518304573 827192515 892971523 756843963 950560359 326993790 947753715 180961112 239781119 942638414 523830708 156992037 817285936 306343440 479765566 620238178 72411819 496762383 960505280 178364594 624459052 232379831 873108284 476258132 331102207 874585752 808380071 983119893 125106375 775636561 854669029 848425495 997046347 783782981 906353142 864660683 657779862 250308940 771482236 878635152 497094 530006372 742828187 188946021 204080660 94264316 506563707 161696418 555306522 690034736 180231914 996748588 235370741 139570805 304098058 559482609 735854283 152322920 581640523 646488639 5834767 233681754 622629950 838852120 409981790 637572592 378496340 146180492 798762938 301463382 9241370 329352748 499055938 569199677 769871254 516132457 985964807 84213791 250036033 147011970 552933500 698652806 346076086 452816578 732692659 539764399 232140233 791650971 745431185 774067718 791577024 834668570 463611795 327434613 618877370 366201871 701028168 794492558 753947847 632286302 551847719 104445297 442450684 215630394 674102803 396973123 893342447 925076974 257141454 472913567 388869789 366298580 970946372 93078406 815578245 111726452 80172314 984404954 225085584 7510025 558768611 216107193 69089307 380321867 549880816 72004681 576554154 68648349 873839892 910013857 565422037 617243134 221352434 129465408 749795360 121735277 369235567 541501548 624720331 405728653 162466643 789665585 790870056 222427559 275723306 819241747 992582771 786851315 665191141 232439136 416901525 444481175 381851552 199829391 584696218 368697466 423646720 144905896 407802805 443758842 513673876 359220014 137181601 448320577 475287721 54232511 43778518 938322474 482741896 632598743 801053552 168737178 312470949 215972371 987662623 61464921 572981989 117324406 343656149 212853817 368860833 708129320 631890330 252486454 911781492 56043772 154126387 508253719 896081061 803423388 367570951 841002814 412689410 30892307 224566306 423559872 845727257 842904202 406753563 852244226 693869103 623502351 340759484 523307637 683483979 348582716 640591914 727525791 725865247 778493000 230679305 687783102 664737719 341659993 87829813 271466645 80982058 861495926 230600981 262578467 625030723 963882482 76739237 45581973 885615606 715416051 999116590 37505947 674100596 903193802 906388884 281193935 576471064 200501337 193761674 332829051 847511851 990795967 362682830 180747154 622887253 426452328 857212000 406954927 858854822 123638148 862622663 816177200 238538380 102154000 734161053 305673786 489088152 482225779 183273473 522177033 979993501 28008232 298364385 339318508 710029118 270785076 149043864 58956275 544806907 743460354 922817578 301426683 969900273 835836941 486856189 925343088 103725790 204431936 670255971 953461402 730331587 543538337 900480942 108448045 897632222 899303536 920295550 514958817 199455132 451752680 723510286 360411243 566845426 386604206 615993131 205047459 19159075 909468113 247644125 893706989 482911037 819841727 360877482 224976940 475993478 595413477 755539920 176993875 209933154 898418196 850257529 170817998 474657040 244062989 46974284 630459749 52857820 2924386 595785061 556941718 491291785 928738323 120576975 106399175 879453044 958109929 828837415 11387863 504731125 410159716 307341381 539054124 907619062 191549713 772354523 119899854 674313729 262280759 464013490 955139363 700031450 456339466 748162856 892641857 312864142 173403772 21744781 717373347 996048424 946139207 103223685 660646976 927257760 164813297 355923255 482857960 537017277 280132993 536242009 116794146 150661083 461877900 326366042 106249465 369651361 671795317 122694095 745549108 285244207 931078087 628672060 686712831 284624420 523492051 13707805 54369641 396749575 965525841 104462247 172599494 878562451 815450116 517544580 728679964 417034537 87200057 574662719 405136302 721295575 992704917 662503929 922606703 782433024 356337448 792273286 628578623 800242501 163635005 459452655 415707834 284615585 699627077 640172322 416722317 35246485 225013946 124583973 200823055 353677375 116149879 327591721 984972949 923107135 657900007 141854523 890144366 27463156 166551296 484343892 355373293 911818531 142644215 187983293 492124133 814669384 332091312 119314338 675875594 745077483 151533946 607664379 364907280 788963219 254354506 202466634 557273879 104952953 957771490 561666547 17969271 100547744 959890556 13789305 960949378 22244191 892216618 18647277 458470161 126848900 780869203 875758831 104198732 424554718 658016528 394673692 555672401 367354180 605640795 243736643 852188889 979945409 369821875 393704927 249785346 76094781 744198277 436625312 317718102 41298286 267426000 576554633 877734793 893634119 388361742 41424897 709444237 852506861 663540307 16760075 199628737 190319638 27006218 969341139 530570339 549353890 45876801 274418283 830411387 835169001 69118064 417562562 259083418 708749327 204045043 435263790 966246485 37861577 705933032 57255723 25912851 279721456 944558745 226807674 462363362 466264605 866050099 567876979 877818315 406244724 617539697 638079 359959716 406500413 840740819 536073934 29515291 176172170 760686840 975453730 637839810 586941528 352313028 809817863 378194197 432027104 270631212 960997238 739128132 184217272 332263500 505949738 649229517 56981968 932337825 767553992 531070690 90229180 477163930 619917631 787998261 41157338 865243244 564541721 623789697 251946090 689600914 479867361 828179801 246692709 295369344 650302425 285111623 836704018 344603663 225894344 825342651 564374878 641889615 475397809 405592020 28850768 723931361 464470021 499061405 524339234 77792969 822021988 13922840 240216798 350389720 158294216 337011562 445408763 379328096 39148068 658504323 797873011 138017339 419085637 142307137 137982974 7687885 639123599 572917165 270704316 673343122 676383617 115225934 965219461 906250767 304979003 622984737 315352532 687874853 886510163 943949643 420143261 677492346 155434952 777110111 509709604 324969605 562118701 701403863 673506341 158450318 441848615 242910878 489816432 888404385 570518064 211607531 441272734 533557298 502845319 335949747 66872728 75225154 211552024 411066992 635210661 492946937 745934217 348187534 633457562 45089164 504631975 693874466 509508961 294497863 993304145 831721244 194659618 281355939 355407751 940442537 982000331 9501415 811043171 890700070 674245156 789142772 607521920 987721103 886418611 672411791 466168289 896811920 869692203 769231182 467932148 932881714 630556683 148025111 482771844 980937021 272929391 554173438 837052622 676168497 815572984 146208275 677432550 904161201 420807276 215669047 582526669 173165057 408660856 525532562 298464904 982726746 743828039 176898774 316924532 499786777 238172598 269890572 389702503 302037602 614055944 416928204 740819591 986761174 557647211 944655169 432391822 174691465 301900971 195475739 775502159 318079009 762186389 707917077 502582486 207692243 487928091 633569385 589225542 672398123 444569244 184952521 33992353 636994498 315138984 207474581 537441212 701240388 618741179 611227824 996273209 965481904 784869363 201578462 908720253 962317629 263085115 274388799 648345197 979383293 798674646 429056562 242112158 255159780 771654507 565749552 106659123 346983143 267080541 651434577 904565719 972662409 771622457 534142505 64420698 652843113 928651929 207243335 320532101 341165342 818546163 807071294 8156082 205454858 764134558 690409836 630590975 265066701 372314850 293992206 824011449 215243585 248649790 278031342 993326548 901863513 395785111 16786065 860747112 934512140 745706561 929802476 906637193 900681722 13195951 983364268 620700256 130609869 44132601 208850082 144572106 634780983 578406405 994771672 413400191 320882356 613262008 532479020 171257013 996683739 241480786 325298276 655604526 804150448 510679335 235283487 186023802 513929890 814124395 760121825 212529060 54348360 429655521 785749903 47819197 433688834 323206721 276869786 448570538 751961421 346345752 281304427 9863827 731397784 593983760 112428474 119754319 847969194 320373457 23402292 831110485 313547902 759948047 362128671 770068625 182886194 194847714 266351735 221157070 497618249 410197134 527097782 257186451 38856632 986011115 658996226 365070320 317317602 171756178 334638953 853078934 576455117 192375308 920349380 701091890 13028216 23730774 114369405 9661204 434797469 67055735 586615943 865765486 918666919 621535359 710355149 907962960 405736278 103974117 516630261 337507279 702143345 404867141 510594893 349540031 737053984 745801781 855525503 497128768 733461658 670842867 8382161 536065762 588333614 534198877 58560252 905676308 245774496 782830220 847388276 937356623 690400661 918976065 325736695 198733076 85472600 611369651 784137177 891077339 352093880 316824909 351247698 569348315 534400413 577136801 235893081 811755233 955570531 244862152 267274632 433294026 524121458 676598477 104420913 631553143 179130015 993749523 63910602 265621233 743190033 746588085 406250476 658772012 462017256 312681487 609789775 616942798 411647070 861717143 94560001 298588648 603042270 970586809 972068615 771409797 682357495 987907221 597709827 754233443 77369266 618304789 946131230 125886922 268442922 247005176 172853593 521389224 355994452 898735495 388385256 779243737 128536342 556207700 197453158 288794248 221096121 383575688 497568770 516169065 460021831 855968240 491384868 115539285 586240182 998247199 713041634 473735087 776009626 345408323 76146649 807372928 716604216 404089531 842478754 390727584 835376226 429728094 388000109 146318140 163907346 778352770 957676849 142345689 111260960 936366043 289979944 483049777 260891023 213929849 413036596 155486124 425813918 783830195 293532019 604700387 584592915 444106676 26601841 517888251 462705156 400951168 269865040 927548467 519106 846343011 338846602 646951952 87775972 969825230 396392520 407710818 848939673 495597176 456807951 58552031 657075982 34208072 336952303 951952141 814350612 811216697 369441695 466834917 919934998 716679760 646773714 681122335 531271201 870354496 612975853 576962033 422062068 976100778 857425415 204815521 31623664 434201132 167607396 825249453 201484353 288789417 307022253 177308878 821635992 309730193 134606117 203517211 881542829 894557793 442409675 364562222 940919075 720943544 125944013 222059148 416743217 140896538 47794205 44648757 703727835 688630240 550441468 655629119 638673919 30533196 429437718 839435232 73114419 861156691 905299944 340019801 317884703 904138267 641377181 80884830 439688314 706759022 113808143 199503069 866042398 168615333 196242404 211270377 11095864 852299087 94228839 226400579 123647624 882907038 210502240 348552397 471319521 566667145 662974070 70564757 9579121 862961359 305013010 434676301 408643466 96180674 297172764 57472363 344800391 504074703 230119392 166491221 586446521 458985739 514680602 747049164 883848196 718011950 258139406 72015378 835138895 713194930 91325171 161905173 234925609 180725546 27746909 46076658 231818845 651000137 234797552 92205948 919721878 635887721 550409777 448948879 630839436 695485172 578614852 97368094 577393379 714817404 547865493 675744796 457605501 218562479 286692204 713441880 336506014 45193025 20874974 175121302 224186140 804879218 748909544 895940946 874994231 572914819 252823237 948732091 454845595 212120460 615997133 456182909 38977274 89674116 689847420 269811303 512608349 794796560 960823464 628970217 473240789 961279463 47974343 72920447 190598944 64611301 831262535 714960765 766778874 999334860 329196514 965425865 578673948 970685164 526939652 38280302 906911630 353118916 447919831 181623867 444833303 427012019 953950551 729985538 633317414 523089401 950599169 176842497 966373545 430401867 903345425 468931216 764290983 640608964 247209693 940244177 269552 737462067 717157285 859660334 364028878 793938453 338920160 8692442 902849097 961510061 309225551 628059680 229121084 857180195 39143178 777792979 248154719 755935137 629426613 188268176 30435216 109757787 896095538 854784652 894921882 12085788 682152054 2792820 440301711 369478174 555241364 729462285 384548559 61019167 313766869 327641586 501313927 117737973 119538340 317074806 188310287 879709650 222998851 189331781 691880613 944263452 303734877 633416723 109482356 687305842 795698763 413712735 288050694 139607489 397767612 328169896 271020556 566895503 878407523 137176646 727801941 568584409 596059322 452036715 75603572 3272126 994053871 249387260 758363608 9534992 821236777 131941928 604525898 2476050 55359263 143007451 266825198 135356209 772780116 271278416 698220151 846516914 60853272 16317911 669259026 123898251 963742656 574072116 482117988 195818287 219870371 453579366 202823981 434696759 514207000 360168726 593490570 767983541 578320773 843214150 190217328 399037256 252664555 58897955 875270186 304044720 458803540 663707829 387372174 661688830 635631907 269219893 431877084 11928431 81814675 179131856 762544999 374335364 294014346 122918491 844278853 547215750 119015364 253414637 92552787 499651357 35139655 687767131 852211369 390995337 355580246 554285516 388744830 769312937 853527388 252502856 562526182 62812279 980183419 552798594 936097805 218849331 958280806 61455 835391679 765938487 257164004 625848445 695082502 758595427 737407979 997390904 769104563 262927721 386481318 897812394 645415775 311717597 44365443 7027444 690815574 18260723 904861991 254842465 253241639 234696514 767257872 160594171 62839731 483330956 673123030 128386879 814400200 206063125 999656578 185434551 982914638 64732628 595400902 78196862 458538391 619915646 307279325 165095396 910167802 71824078 331385425 249570683 104587205 724939989 781789799 970307395 654520509 54603016 607658275 419524022 817948749 320698618 432792777 695733546 237393635 74977364 794455791 876028882 121057001 741526041 304140067 588079526 105607215 661092776 170637638 574152260 262010663 672635940 603550621 739477992 691940217 293353966 390926692 292600627 569860788 98637215 174944261 98393147 67746102 257293737 872312019 552970700 351807604 45421472 152011729 508718628 752117201 389498575 306672940 276679421 89030415 294560707 393060644 415600679 243390298 295472771 22908002 495239791 830438556 183750616 955319244 340657447 2305451 6877212 135882885 889210556 25567176 177239676 268307623 678426747 70026016 717538160 225541688 201559759 763765295 40118006 31375392 972840715 743613930 261462809 576298986 412831651 986670931 777521438 886538736 383350643 182540731 176568377 217049871 644070930 978881457 568455815 699494158 515099113 596102940 652931441 403188349 715489650 61161400 713239380 11223653 869572301 604157904 27841600 668466426 367616928 994745147 706295994 735491234 343068705 626969894 873438095 97178412 770785296 320806431 739802351 112477833 220268419 872202319 892145260 819940685 839442837 870691787 795505858 187684033 577459364 440274816 179751607 995278489 49583299 916958157 579882643 275803883 788328096 102324894 777656176 1201693 32987535 32482305 951695160 989728687 139646382 190136440 717099178 948795412 802125598 771281263 653557097 31333496 117770919 910923528 546193929 27358283 208979471 22861839 5161013 953108124 916557208 254696702 770668038 268456839 597479145 145388838 340988549 228151214 885035948 186361333 819673446 922499313 75996851 873615905 739407558 878211110 911842840 296545374 810704822 483154303 536673805 929769547 765347695 484715399 87917498 510084164 311050480 642185288 994601437 824187413 825978520 845943758 902277650 555032133 970969714 912691629 163600406 664000201 181221860 480822838 419362485 11078543 79857574 888471726 753484312 257469774 55412443 33357583 63274097 785982665 120890801 547850620 387103365 878785415 961168031 457758385 841220471 5620305 550108436 348833896 417914458 549524800 738534108 191634931 279261585 268831053 520042674 787730463 705247099 657725946 254383698 100022167 946559049 212473766 67068379 83911122 841665180 813792573 610035865 96855670 254512445 586965893 763453421 455782648 672893654 498188933 403889655 828010827 286045182 41872523 33363977 342299381 118081872 749668050 923927865 181684116 773895133 998061617 342079738 935390650 876055659 210149348 167133217 537434331 439785760 620842835 370728110 86479279 574023913 362230202 912931526 104117049 651450563 560291244 631147737 47587202 945856193 744397527 602420176 349842953 835391556 774715506 295135655 383305408 313211514 533913585 534137793 904317146 402443841 696375610 791084564 184041757 72127780 93385248 242002900 572825127 665524285 633334916 363716100 792938784 148335549 849401857 4220314 642285273 261442365 421697682 83890369 751779690 907821620 396814137 90219584 887716158 577665912 203638032 892587263 245204682 90975170 353794755 811575174 991581099 870055845 401546401 203252170 960609952 469744331 92638111 946567665 591740615 614370125 314770092 385411580 279089198 721956641 65487227 24345309 257722443 727944420 648758695 729463013 116446132 23762513 807564701 140745119 769690868 4862004 921476280 133355768 847614400 291364581 41904841 925657393 241392696 734956042 852453121 925996869 870137005 665179942 889170192 338644514 466135209 413780698 214333760 16993764 546674293 801211488 59213531 746023052 675487614 103828921 953330352 784804665 120113124 518553967 337293462 945896300 975810043 498580044 581995085 967184318 904733850 409642073 639496684 764947898 560979618 339330337 817955507 736360723 434075855 887639105 949944104 356029606 507868120 447333835 721254013 872894551 11481464 529593413 951392902 168768141 900530103 428612834 708577665 556172474 864067079 641044209 180670168 254319183 422039148 471929950 987142247 511778983 767069578 204250546 319712385 363492334 703520706 74455620 121402945 851440503 107316428 892159155 740476047 423825298 453661712 703354820 855879209 815322837 32642748 346261658 319384571 472374390 705061848 17321861 438166766 707273516 822169275 525520262 894346124 671254383 455819086 311722338 271989269 426875821 771048244 781075656 305951854 487152934 744610005 553491667 270054483 443244521 882854414 391243417 483112193 906432108 233964797 501954632 697356633 634003744 365026696 119051399 781987389 578203302 414617845 643873722 954122083 413937549 54845047 941675558 155576873 594500012 89164895 109968195 986996925 388476537 389591397 135478463 625072878 583022074 560199925 907295165 46774188 333393012 886560422 720701636 40556667 245240789 554490949 761023933 193778234 615425835 76003470 452297052 188345387 469329813 903107784 486799488 13066001 488486164 690935341 628968584 352582146 613999513 848169299 747832176 76169096 979551120 33236380 749356243 16720946 133490783 24415635 339344706 29037644 392284142 209532015 923932795 49693419 504109340 693640560 674792889 599919378 287248830 562784933 41415764 105655254 162745902 722136778 819627008 944067695 959738831 27414880 579030009 183533837 844791070 973885052 411322769 682909749 372915271 970046392 208449324 177333639 916738906 979065168 61160462 975810201 152277343 145685863 45171537 18650972 882998441 273705053 353546986 991248223 653781871 487978748 952872781 335894629 582726597 621205800 699484361 973865296 82995617 364577808 83452866 614877708 459173212 939428024 701828292 813379061 804447423 781427191 218836848 568902776 205629448 149858714 584232520 479907139 89725122 57582782 646799900 275344854 341013086 80063972 710826028 714644163 937003794 403631407 705777390 521642667 683383990 849916319 441664301 166559570 309869831 132349144 539822048 668780059 428891009 501572947 513829040 635474022 789136470 799236208 231095624 660868660 163070605 64373763 321509163 828623929 395170936 177967140 499726263 225270695 443033203 819522386 340593806 782114723 680929212 855092923 815106104 916379773 733404763 598567689 599994547 778459673 852517140 295663356 799969990 228245273 934121657 778585887 777777405 644234445 627952037 284191944 234164268 57568046 102378560 268414911 354927118 167220762 516742031 462657730 830246664 499029431 600793463 859237435 730336015 217922528 514519429 101467982 471474867 271326528 473480452 282692025 659322301 20666776 157698675 684432249 397283223 424485281 392877212 989565948 974120868 976841710 848118188 385406563 480441062 186868407 447255718 212888149 382808622 165504466 865462254 214151997 995052272 598505284 958922168 906356020 762332131 118257822 529377587 37452815 345597525 323671224 382301729 596105615 38963738 403258124 141636839 912819840 471041372 931528824 626919411 388123942 403953416 772848457 503510790 979183858 831696216 996057676 98793960 195894775 977965085 929586695 41540372 449451571 734233839 779381658 58515355 736617165 328333285 900222132 470600941 370200648 459802716 315096804 707246119 61450412 253111283 413604657 211091898 612179662 897014604 322907953 850122831 468002882 786388005 148048411 728242270 250088022 716865713 950386158 91404021 233459054 277666050 761822709 632325844 289323284 246141679 471968517 388839484 438592664 747021017 312680469 578246506 391165711 639469652 925790064 579159042 653453352 181662646 939172852 77083562 310854705 825327973 899238560 565556009 931677019 966800695 256116701 916483917 392648762 985094552 593988980 790897769 487799726 581463278 699082897 518449983 835097029 926976692 574287153 854341535 262120731 308029173 810200284 597803692 807788691 271470947 418371547 359898165 693918179 12300653 566050349 276846501 921192313 733516170 381512149 358021965 381143261 432623382 770269316 294824405 767921792 860321208 668387895 297288024 736475286 591851703 156824278 226863221 859539270 801883855 968383172 733053476 353322863 352675784 671304894 207150787 298426395 893344840 960343719 800821301 459111180 770347331 196179080 90352700 657451182 649712035 953673026 8566764 905351373 699538856 753232641 651107464 147131224 211242202 39927709 199934688 550305177 522960562 739491500 563542081 152540468 857074036 557280096 246725778 316721772 785353489 374489862 884649864 749984643 509942723 872115157 593462599 183725355 802341446 991066254 141065251 763770197 699393302 129937373 91923770 969107430 503542984 302772125 790651521 736953474 804767037 596732132 993778302 442109906 511311399 65419817 352632052 266662639 709192117 181882246 325136538 105898427 46710622 618618991 235519803 146299333 480681310 842249032 798777273 185402775 161683375 541419427 430693742 896673010 773453940 543805515 942367148 189419913 196453208 329209127 453125542 948915576 272857106 863820719 424877265 633323795 240898084 203413426 184295320 647000949 239540147 120726077 469338132 830816870 296642943 915251984 771319174 105589998 497498387 78812555 699183430 706732374 467349973 293822875 147422322 849901155 374916863 298312045 68063100 67226452 838322712 199527083 762349286 462283712 340662503 789791222 594072092 974903174 389612929 489517673 85771709 614551041 918799364 214025862 986781403 537428227 931396724 140874411 731011893 137184083 192045737 828365207 395993969 391844353 257761547 971173913 547460600 103071801 177508058 149460611 787279806 5839314 70437533 618932235 243803183 572795378 933222884 511297174 501140344 569507303 985403967 414086173 712262157 209078369 300844868 31660005 758924387 625564820 863482716 182933420 141173133 150245926 691612754 835066979 532171527 132541093 399940406 111924973 388509995 709436797 542549458 68880653 594597579 406101129 555249349 857710402 771190528 561778007 426683609 62362101 156107605 585396009 125220844 766673485 471266451 837605284 615104253 193560322 362476008 406543262 669493478 199469649 66422980 169574252 804578275 206538448 27535351 528657972 190254809 425590577 16719718 761269007 815029528 140462828 72573767 106837570 393677978 411028588 914045388 34163759 875402808 846866256 870405957 655365068 786148806 63510859 820571991 613232500 64994801 533694486 728207449 114340284 325807895 262393671 698410555 396823270 415896500 111969523 954098080 89666375 977258966 553390493 955378037 137970826 125180533 269837258 534261861 829898463 530266030 365652992 532589727 784265567 466426634 751020239 415633613 535226501 818034259 987130000 797362939 4609093 889917820 470218987 518532851 445015321 331146681 356725262 154824641 374138716 715946954 707062383 314535392 854188874 559659624 184324108 697137438 646527483 832747860 442622688 557545002 642469733 884190216 568453224 519141541 760007258 101605526 320529919 472251823 498482088 599319261 302415956 712497327 964455926 72131175 227268132 872443339 595591154 95425602 911301142 336523889 671240882 361718464 438138726 614007420 702939031 758673922 70557126 810819766 938491175 156739045 346618068 820095130 155103588 489489112 281142604 480375988 830571896 348530622 861453743 759055116 651917391 401451690 999999790 319180875 876298212 425054435 504510860 998843977 283434610 54998729 261167657 97814797 244306751 993151450 274395761 772449378 635663601 480062076 38344837 990990136 910616923 549511919 738073043 134604306 101471425 551661061 817286456 177247246 733320149 242876582 917357631 591597004 434967091 640258971 125865236 509150956 851894713 227169839 915797181 935765336 139445261 515857304 577455266 821154619 402569483 464083667 248243947 644139321 543082913 832608570 625458935 693277154 767998719 493377993 201848727 330135183 353078872 523799362 1520237 225895954 576913180 759786051 768708218 401292852 992628730 6997064 703391343 126664142 158228902 762364887 344657279 685630414 62164480 701425037 505889228 340646528 286599698 811757377 54696670 781236280 916913941 353277159 964791938 842683269 166354335 713858200 208096487 54145240 315327728 748990837 255793496 879214286 354759729 604650850 707476671 767934925 692635589 73849949 423423469 125380464 92155185 902835592 24864751 171064173 708016921 562500659 920076358 160096156 196285814 353391271 340483821 142295407 510135125 65306223 487279655 712368145 109906826 291738942 940087668 932606274 720991877 418304644 836256000 174759650 453141170 371227720 941714976 614387230 670792368 172085024 131340413 295994791 527901586 798524150 77271034 375042437 185815403 441187871 849924982 298089662 742993393 353224430 654893328 602552233 413337635 604083282 956139581 804416843 241744229 533530766 429633688 152454047 503702991 996250424 45652682 661697683 697733289 757691115 835978338 257128956 609795132 796896972 75449846 869988603 101463765 365017270 113841459 414760744 373898483 717581303 990801667 397406763 403895566 994660268 670666291 374848139 307982747 359808363 300307234 127255525 576151794 709325270 364909993 72537819 462632984 926114906 972891542 105596012 394005403 96985828 211782104 37045423 198330193 333473385 125496574 415832777 640783071 502247511 27134306 810247647 342877381 681140427 362614708 457372533 615232011 168942891 943449221 839509493 933038965 552684624 54063280 552023015 997238217 999741643 906171327 805766103 353996340 768137725 70582431 483764052 241041359 333256633 767810670 283521193 551503958 620196328 689324601 426088109 108177891 290860437 85155916 647251806 563816604 199834109 67576079 682963044 43262200 979290562 46817988 926641422 639772686 981783130 951238812 141505678 791167647 601343090 202340229 709120578 801225901 228011135 218900991 869392743 635728432 51761049 794239504 811561902 828921550 973863633 526633864 69821688 881638839 258791538 524733807 98267676 279606397 388387586 800278780 324642852 790724057 80553336 544251475 599539119 119190513 757972096 35265060 292409077 125219642 503422438 572869677 549184826 725645678 419447344 280780276 287131567 922556583 246056562 311867544 768767770 445880779 139740850 463824460 823040004 130906279 926984555 758178414 973085280 840106259 364152745 144542929 146700602 6491648 145834181 710794645 642499755 767385121 250785803 294890858 125572653 695390165 260837141 93567856 921542971 901208462 98884689 129462520 641680444 608998291 552906411 635439465 800083479 114315338 926033328 113794608 929518944 99937921 764524368 937100310 562396403 562627380 892685645 885482141 802487278 918634586 539742411 235722926 933181708 323888889 748821535 804754189 520681972 648321920 368744386 101766584 894262719 833975906 491915457 427685362 83783050 775391662 254603022 949676850 18150325 306066515 500269971 542727825 677207109 892540247 924596789 523081147 968386988 489038952 382776330 847294932 623851246 89505474 902686511 917616116 744831606 992997311 505837659 858318216 616720353 400895556 587192964 985161739 831084715 935119940 143407513 948418937 146508424 286112765 623361642 685476105 734097211 556557240 107831867 491293287 17616625 308833009 186396854 930305519 810742561 381355748 745776968 428592449 488362763 550855264 977644565 565342204 367452617 688830856 445560901 905784190 297041810 98339560 388218818 308117837 348311364 542728777 391084876 677055211 913676367 449661810 555581132 924257328 611249007 973687015 536181167 233982217 593615346 696387139 654939004 490561191 52369108 827005790 475098119 592084876 664555195 111691278 868515048 41145800 765267089 286354017 535294258 532515674 351969576 192888814 744558171 570634042 879528318 357940936 186044317 193818499 274069117 54964150 463055712 767685929 590937252 447129519 924567143 463887814 17599156 801639370 76646421 81330768 932589526 851370800 13489348 499254247 614514967 959346448 503498313 795254805 146180958 233331221 106010325 825230374 337785352 298045199 748805286 545775631 462398145 421256730 616316402 935466212 518737483 560614310 400823418 979395152 822052147 73626070 362438560 651661642 832975466 816861434 991335025 848140785 569318861 334193754 461547748 418285662 775924340 169787055 315622556 203795801 484175805 270791307 464804951 896565124 776524526 311999280 716503743 294172408 320749606 60097949 655876554 244904836 77883576 83841472 518878384 704409367 971601129 424994397 162101681 432250183 7622670 598973732 920834060 622782403 173305849 702675132 202399749 190073759 192609858 503490197 584078349 76552566 960863778 253356954 646164943 305582634 181696017 88322198 806808665 785560391 543588348 255737671 176618359 235416740 379742278 455167812 79479804 29563618 963096804 281300496 353181879 18379344 583856479 764992056 835515268 179607380 668315696 122973099 692430640 683249215 813379134 960445494 321221180 710036305 652638119 739901573 35150522 577428341 69107358 665945046 677847323 644159933 279756864 894837248 140863920 865809408 948928649 403565765 366656092 920526314 635606573 573806682 830813106 476879075 746519283 650650787 4361199 83246585 669014768 747080915 149162434 388625135 752003914 642553051 623349567 101943926 890971148 939513139 90652687 216982427 958060396 107741110 857734840 616025572 820187912 223127588 574724045 57797263 413133183 250934516 115939310 856633602 361117946 313994724 242594901 737067040 652938947 460280103 942692578 985360525 943236039 262872513 8019896 339641626 521845280 279027588 41297476 184780354 594777952 117821789 765765365 709062970 738183564 778396891 848361423 475682982 435935244 187783429 443202927 620566196 228524429 300966807 306635763 26204070 816878854 226869165 188275551 691493489 116169976 31873634 858718237 507426568 333390184 513726983 728948021 299320601 96426836 584251091 881499777 851695355 601926548 908754237 318512068 681106138 163548783 227471881 381252228 899357511 325101890 852521747 684025030 307444065 597113404 578908921 471504085 82912606 609138402 360148530 916905619 258942074 718788252 72560712 855370480 555876220 724841420 545715520 102518844 599404516 352234046 643211681 999050768 753712244 53345099 153627830 948042437 986532093 500267731 460644290 21289210 462798122 379903568 462453513 658774899 430014594 854248947 573217531 730761601 767826374 435310701 515694748 141099868 112175813 80032340 241757994 391857765 733961896 486048571 806968211 974927585 870165649 959020693 425409129 439675314 434593135 599614430 705951987 839636984 849902365 845462142 32534134 122534798 161400863 860809259 829423981 726760410 153184310 347022572 366114893 713231657 83741055 467523871 623609898 637741880 612198579 554699475 190480583 747684712 831068276 513548612 182606588 310473387 958572998 982892111 166944172 639957609 886888706 378256550 324978598 296957892 621847354 777307139 767919762 188352681 608741185 712700488 214886074 973803251 577878120 938044796 924391090 616182295 251144232 233204515 8119295 600180180 240627580 737604131 539669208 77842341 888436595 563013238 864403398 756072140 861529439 914416576 843454713 21868741 462768821 300403354 362408854 781291426 830448212 240218248 454533938 217223940 792753556 540618556 713778118 317284988 650718994 928187118 372290616 977953992 214043010 289240430 308654986 694946942 132736809 511738180 580280835 397992047 675533374 31088212 103565052 764690099 85363102 110263512 526581191 664862320 198140202 24842587 234570938 716933031 64442510 146121601 121465376 251644909 987315042 343186890 663900320 768670214 56609453 156978937 518560650 948327858 506705194 497762700 789289727 543746690 338559155 963073174 964066382 321364117 306304075 822369887 79654693 460692431 963921660 93816544 70934850 184212030 859600009 429776381 644173488 494687791 307075731 709682251 987161080 891741838 729051641 461937198 321679823 565728892 489251848 376151059 190997287 950713172 310614999 582556942 64752983 325072472 791163613 531365970 370725686 988758199 303850321 58494278 138216842 803446391 742596673 710409868 536148982 251920199 218466444 633001448 428376364 443073542 107071459 541840722 114810330 88660845 835650005 409766734 836508189 2086580 422707493 623155000 986030472 282215954 28564317 754542882 70321349 689638512 542988787 662982492 879942895 656272565 879719073 214816039 251168598 443888723 746530252 945711838 101578681 839061604 790469469 555513628 604775813 241640344 970062064 900532285 377565226 947589098 556426598 860194356 734391778 677220487 798504932 907889526 23451156 275168397 622573654 50990619 842422261 984047076 256923490 807961440 861264867 227071621 821706538 242965212 946745913 366792055 724628305 894070101 148647112 524161018 716908513 798679116 825755749 682340464 855121891 869923247 321345134 966291649 60734381 658142270 610738148 750648790 320718870 207898171 144278075 528905357 569212409 71926965 931668263 790692103 805000079 429140316 787472379 124452810 725036895 62910154 514190462 58245899 875421901 238730470 723155927 336159371 984694118 645524281 652132338 652715657 276609479 197298238 781523162 897710025 826643378 537268366 408930634 465940074 186256350 410095671 796773338 527000142 317494591 238443284 585281136 530740228 122475554 933681495 878490933 17094421 777419502 993958886 961313154 601928752 714337002 3603144 845172962 554056471 914125344 433438910 171545649 861092543 119348705 703195660 862190530 876312593 553631967 706931282 5982515 929623516 966727662 760898082 748036791 549360886 321511306 315078964 300795755 24807241 299979671 472040899 421096607 957454519 373264401 958340596 957870231 450834247 304956014 787935368 657891971 483488554 29339482 453208674 658304380 507060829 143816769 206839624 691385146 137733902 145453009 850895910 865986726 420282768 430881788 915992497 167552341 900145981 753396774 303160040 390669725 894948358 154874461 401655442 353549868 338086126 47650739 535911915 257739315 753389367 524262434 827741156 316036455 953844291 458917883 93444536 542160604 109215109 981679805 882349272 496404278 627027363 67615406 335518890 86000792 400400332 64686876 726738049 254417539 712358199 879934116 613200750 195930514 52402987 710275533 197474770 354886996 399768814 619383185 66900761 401684799 127968663 502760119 296942821 817088135 854220858 421319765 176871534 821030844 728365276 873321506 957008822 198461282 887568528 754273586 385640368 348917614 830788242 926402104 582304959 282891639 347297921 757890290 840237619 229572370 734510771 291421306 436599970 511724393 657195391 627654446 385966447 324666606 413168724 520593760 384602284 90090492 391805484 605782170 524136325 190452345 301133788 90804887 679452726 803608941 956181045 885135602 88582579 966605989 194409220 843162351 398925434 938092781 161457831 141281785 386220839 445889454 208896551 450180507 735541626 987461528 328680068 36081284 197317121 119307314 21685960 557832990 983191721 515443763 707911967 307240554 921299837 529385330 530957375 104915009 793626129 655699001 895175589 915065213 43150026 663197522 335426865 806800044 16772626 271109403 77714572 395421928 298191794 855473608 493943211 145226802 205504882 361997938 623836606 191442679 417201769 881367704 610637190 542206346 699903086 330840140 437273782 390592211 633063644 335248791 76143350 882232580 32771907 303538949 134873580 642268760 128238327 327105839 321568452 632248000 629522184 884506151 588354398 936646995 340905176 138987286 975491740 289894623 750163000 472773313 48704894 371440563 196482935 280621929 137508190 310738691 20428564 255063263 214806389 124896 98881859 23332639 941828480 394514504 414584602 577008925 499857129 110855653 262877166 860158507 14299707 742508478 936902603 738563663 285320501 316591955 147485230 406000078 500910254 820681291 20560798 759978753 680457965 357334072 68937869 491354683 422869737 919730400 644824790 896998688 162665104 181317402 247510120 54093129 964830893 248915106 179835862 669183954 113333352 111551372 85038123 826193575 745607582 965957715 939729175 327387472 504292240 405842076 885547862 849083171 939800248 622358823 383822831 219038838 185673201 39157659 319524309 365435378 450932395 272480180 987138408 641795260 897134560 850247491 19401147 484048383 501625637 482105217 557374791 289599747 990065019 984634527 979743651 986804368 701254019 183091231 735591089 944497382 344982851 494009017 164927036 793027489 139461028 111897196 334568820 379062513 588958713 993661646 336515916 849780219 505410784 279671067 285765446 543366454 300426479 553673026