1160
915994114 850861022 969813585 869903371 397641029 781285768 23949250 348341562 416731024 125962063 972768190 401024248 293155770 658669154 945020914 895369813 98311797 679159909 493672999 762830543 114009895 322638111 611751928 420469133 878157765 267440045 757036433 759138086 220580068 276169242 730970574 453981718 615714563 811968822 193239105 133040701 83280614 921810548 620565975 99615436 190495103 333255014 258428164 689089747 157641932 983829727 882012463 879195191 643764821 904232711 240481115 103013414 58677231 900866093 571094520 835090031 73050263 126646015 722794601 721044951 668881813 829328236 920823983 293156278 936735351 715867288 3562753 236924221 698071658 329403038 865058267 782726536 453066628 633520972 524579652 94235579 101769854 147956414 96293780 946058366 230406669 632522760 898668563 980061086 30293046 628744217 663971808 840796182 587307750 726293094 180793733 320143830 781964710 282651882 366739515 254328392 804491082 708087910 426951192 805462263 785999064 582779855 141394802 260794715 319584068 909648574 48302776 563559215 829313117 535887931 721384424 15277154 252393426 301404923 371057894 32515132 502064282 355557697 457278746 517462767 645235606 499907022 214153208 360396956 114043293 732190533 477176843 547407400 700224078 368033650 916721453 174933797 139339157 667108472 289623463 81500702 630893925 47634558 434925363 454804579 727191010 105056962 469719970 950269978 29965103 12343038 320874283 548041751 279384912 690169724 119797962 93096386 693919231 485516312 652234192 573235700 277315722 881850549 408296476 787151873 984098970 624564346 41126332 920558963 426148375 834833598 328517228 24975849 756254405 85300458 46055354 45144526 188859655 751644682 153103494 965085280 239012276 764369537 235222448 114200426 273129747 176749640 717062250 987496023 998352098 9675837 498934366 456418772 836724021 517142705 267145051 208275809 713348639 799951338 529434072 41263428 322214680 213952898 868920794 423263603 632586876 121226775 582615131 110003865 536359287 471497182 67629172 935813797 66664242 473481156 800994614 449253412 162399538 600738295 555944323 637445019 272204835 608925948 777907919 172690318 554673559 993819537 948302232 263489339 18976469 648982659 808282993 391284269 481596199 193025738 240271554 984099914 555526567 210419004 230954105 773865735 425456055 241556858 150471923 675322933 432315317 309660006 311255122 31339399 409751771 500598952 396998527 569893402 211329130 350479404 575499410 97527161 261158714 293996935 397764831 909472074 747014636 241407671 417028491 201630166 214280580 581765671 734961588 615585153 595316208 116050271 628533637 619308376 709524233 603939266 698663280 130682028 78714082 269432797 673203439 710912870 882232054 143838768 21499993 256152948 271029914 123526706 369551132 273345394 858554024 952526 319099685 301365687 496961562 153694033 667793229 106113606 397825468 995025172 826853433 882284571 151547510 184097646 820894931 255490870 547570559 338985239 961444957 859260130 895215414 282331040 165890357 653642166 408574045 2371280 885787444 466709491 502405846 605144838 271429521 446065779 174748533 237813541 22650433 300333452 419183821 982420246 140658153 69048854 348217692 487046635 796042397 580526453 981618272 504480885 227055258 147003300 503020112 224167943 832685862 138195624 191123065 993126258 656970420 933250334 14234471 265717169 140335125 748403339 881739361 965417723 102374971 242823966 396000735 178449767 212872855 417750467 168992780 11539172 951998799 187362840 695028599 574597926 814859869 183720488 916149529 654178924 420220885 235994399 5420170 103463638 363933035 956976066 804697238 503690328 949158517 354624908 275873070 372364520 127413426 359260453 6216539 664874681 288950291 95054675 802554594 827110562 971448628 282497189 168187292 900410321 620796227 213802573 698567272 802473456 906282109 529842946 596322154 484922076 596539210 302456279 562971340 852857959 255726113 909635493 726351223 339548143 824435329 171626032 140178857 628964310 95523416 537703638 805511842 289058378 236567416 780128230 938582977 258055792 799491886 485616858 837689308 448906868 123959761 109605450 792700386 140255819 383234716 600995339 229445121 48817042 808328710 391341754 125285411 657056683 555930064 940737522 501626030 277241613 915189110 218253949 625410252 264572709 195850527 118919476 657780071 908407531 3149551 286694054 460727486 841200382 312602317 207573537 58711541 395115982 613381253 530077441 88081345 71350738 790274951 316036019 643397658 235874737 72029901 171852391 912744008 319720129 43568772 316335917 935865634 34382687 172733875 640095836 753809899 771649115 533197068 214129326 198730424 458225409 487833759 853225139 150222962 639820956 864935091 154403445 803195300 832961336 155466331 446828732 11916236 697706659 896496458 217125148 594253400 25347136 788124208 337511317 573107519 88607549 47055142 468247282 371568065 404024057 927651130 871350732 75540835 13737310 601925603 40078310 126464552 783678313 936954261 150071224 396567223 815736315 274334219 786859298 326582093 148643929 336917558 902998800 61332857 92405939 92985298 262726871 936950416 838526916 670813455 684442413 277946249 420943142 55059002 553758926 694435707 680322934 221893391 709630386 727571615 20897200 566939970 528847155 789581243 58161121 999806108 63744292 287513205 103664666 406965341 364222443 99633385 789922914 703550392 566791994 675625394 274866334 520654204 743002926 298418629 292853410 912243901 224049161 664375978 676520795 563616069 828719322 574661602 209968256 662456476 281066880 607630344 842615091 754524622 749009645 957076635 287975367 305652607 61595159 229796481 454480656 570230299 874300708 300102927 922787178 27085149 419629352 401072242 987006613 555927841 929982683 309632159 17481889 834512195 273216923 980754827 991698496 755619005 294590524 192057406 649982032 310113283 76837078 359711028 534532573 61576872 86682494 335993415 936831299 46356192 938515984 74167173 510882606 5243438 124954776 919667685 335436860 835865625 602220911 942757304 956679315 885470884 95730965 855763834 430542506 729041501 551745354 612613340 747403255 791786970 834857924 793485390 543555259 684066151 21218476 341520081 986852184 56650280 448979069 325656696 541986742 302147827 225753036 475277177 903685263 595769329 685534269 80954332 265838393 530582943 216329403 68100713 685215365 524401507 564968790 849917088 555394988 5668937 850088961 755559226 843151876 662558118 552340058 98262871 145016388 106719640 783247231 841155174 180490156 490524253 326939275 494219212 263794881 414138603 680644659 476284782 347198795 137745336 431191947 464773617 15903125 629823950 375641121 258697558 242311839 513056400 166166006 941380980 686305588 52945571 452771440 665408236 486227688 441731971 355710497 349438313 747611999 966119014 921891589 375045170 242901983 441810776 250678080 386090918 748804844 686315185 497541222 563483644 75765924 647530063 514305250 775074494 535491235 713437588 929559428 890188133 791207033 161772272 541126170 674493572 416934440 221113827 544254117 248839442 496115058 74461198 905927634 504772888 855205467 389021044 275876099 462764611 836392581 659441616 899462758 766754044 507778138 250066153 377489627 187359445 476882695 875690670 93558595 138269592 226901061 132295932 970801363 283352413 368456536 132086651 618097420 250343201 385888463 598073827 737780332 273230193 776023500 683344360 905124401 462087843 706676781 949540263 603520924 836496395 901268352 882861141 915930287 78391060 971520432 5589941 690333373 609796094 276512499 918774988 472992587 858637779 184700296 758004442 298425280 380766019 712975790 463076430 809797997 107866790 748645462 301307968 975230673 57778936 778814860 359976186 237536612 752301993 493044300 406105302 325438164 963759420 347507495 500983490 482068280 5737490 443029752 547933869 290392743 263528900 263371659 416051385 129314135 654069779 541810222 295535788 896583709 369931292 287356322 105144213 563762852 789285986 151035032 620949138 685592128 469175120 279754169 100262711 636646525 848995489 113815 343794943 687360861 751071085 834541545 666112383 90342034 831502038 886317349 379253014 327810873 165666112 709488804 234329784 931725204 395130400 855070667 472321631 243046862 253046662 585400387 225505474 195529675 7357625 589215723 979923839 362060429 455666416 567737223 168455880 77072020 746351130 540762116 332799667 187084468 85089949 170715110 447900881 850385152 970763922 280618820 86424166 595959120 775284679 874242710 847193288 487340915 181958945 740342707 73678990 474764900 507317171 181038224 48344485 238773631 630903636 112794948 554927823 896044295 839546111 182055370 11485487 661353357 261814093 999606347 707801833 695737445 391678144 68708303 778092302 668209532 174212977 245043157 689523051 661300368 821087407 970290383 659001805 817601694 217768575 968051640 214323327 639531589 623847784 857821408 763731365 869464281 289087867 807536180 3892655 41732642 854042440 479394985 174482628 848945105 904074916 327512248 25413915 189066000 27000151 200803404 908611891 57222378 607269616 175623804 65214320 295833435 512488591 486010762 307993713 824327373 133713218 654828065 285659063 716691401 755775729 494397991 141533698 279153313 21683904 86948270 790620084 381945910 835076663 204887607 659408626 168889477 408072426 235765246 141593802 470351017 907937314 634333088 695152391 347324369 259075236 447130303 255714693 579676779 689957802 571414388 61238500 364033831 548182550 804119199 997084621 624921176 473534131 650898096 671289519 821662495 224430738 879564105 951491502 356013604 208283033 645418994 417565878 495160817 666841515 740991476 404477210 97640213 912915173 807499096 112652406 57946942 865097111 842142328 794142129 578001007 337621524 127341113 631792802 897065694 47727545 514272965 293379704 12863020 104121743 218910238 795474077 96044101 171518618 812000170 311979407 808531061 799874714 851875413 755224857 469950862 5204376 454696687 851303480 549967558 706587450 672142593 859701313 91017427 169126324 787411742 785154334 576869917 413240096 778406087 939909747 48146336 547964664 357136347 231002252 300348767 377355868 204884851 141435648 37769110 233920626 745161821 40450933 637272459 129240518 452534807 587379035 412795304 963975354 311174480 583557 66255650 318724512 795839671 677925512 9938282 257876860 184686287 310677397 14371211 911334745 719444498 94419259 545880004 838968840 901172404 740159348 53335169 283101399 940877040 319044151 557100120 197882233 851502841 928404497 533965035 142908218 151261253 267202881 803837948 450701264 675775277 996369479 310641531 99351460 752392625 201700380 587720929 434336585 474138605 348090206 728864209 291256158 549107170 194437844 371882348 622258810 831350363 232901576 319652876 631103583 255931945 453468278 963432726 387262634 779124599 398860416 863010752 949204289 45834099 466290046 480122159 930254032 643661308 664928870 556023767 97288125 83325729 594362140 366015666 941587602 930845586 543282424 235531394 136091558 233778689 622140633 134720577 350325895 607319847 762899513 79454979 443038987 629548165 627850294 51777414 100522214 510051506 217989499 987949766 876539940 51491404 604111291 284331768 230647322 269064239 731679467 655491416 273506391 64639240 287466525 575205816 774751368 539236373 806821329 446981909 879905698 667772922 149622203 902990870 152243358 44229765 942079906 863757765 432300929 170645435 799462345 738306358 
268607442 959041246 322830270 378165299 253737790 716436884 729539605 322182550 925322895 802963684 9064839 624971390 766670363 61780746 268430564 186793429 565686235 8688314 775643730 850430004 772319047 39243926 791874094 275344569 869758163 875102599 440265553 118455988 810402721 190456733 479478714 667720486 209859786 95883412 756404404 302570674 854068530 823647587 259850386 765346344 268334424 860024675 91136115 66607782 3865299 482656229 602204817 572698219 559609178 74186944 153812618 300423864 103895672 238799216 515895228 485910615 7802646 148848831 641662064 619717781 630982777 986727060 424181330 243869648 590789704 20414319 367637632 575435123 182550918 354788449 238831447 947814626 25360067 723294142 154235762 655723988 73274785 600641587 834711804 511777155 284195524 551952525 897440564 788781325 423063535 102653975 884587266 103123104 529222116 663428699 717948052 829041483 448491870 315270567 171604081 903175020 127579165 575698846 637894708 132901595 3222660 7366648 618163869 155511758 72292349 115521738 863619049 813028210 773929667 277801049 894854544 503564897 972603632 138844773 174731987 976267580 46099199 792144759 559726220 403481386 99924159 984921718 943780987 645177260 653533147 120980118 699263476 373803606 652302179 195477571 478223391 537448107 600017825 827350728 28183930 913559341 90430779 955852028 398541323 836151397 125502798 796977149 274646177 876603852 100981579 395799519 546733356 852126270 144684556 66706783 130472619 484796719 753783494 358295471 365611900 929475156 589239185 457061854 501320973 880953085 742897031 640175171 119939340 594867247 668208838 58083130 118719663 401148291 547395840 334429546 218478078 784151330 487874448 556567768 117852093 226394922 895869364 386429580 582273957 470734515 941996045 910549687 786096903 420797076 577327266 793397752 223998683 53638424 434537683 649728949 474235092 10099584 732488537 478871917 679462296 822472240 362620542 483553906 333562844 82943112 523015950 347403397 432215152 882470885 169134879 948339834 940092172 791239578 158820373 594045349 129671543 96421472 925428757 408166771 281153989 869640287 544258081 457168940 78167714 83974133 819136757 678940155 515190043 780700444 359292036 293495953 957109016 594596665 528585012 9129155 658507363 37284223 503642083 114772467 943247627 485879486 911220162 454197278 96247431 33277208 574444629 979108751 57086591 36590439 689767749 740334404 221352577 300585364 27526615 811904862 103055203 150733052 532860573 310421199 412321471 929618819 497894606 812889383 973229001 563331846 35453074 178542957 262422668 131280923 127819761 460046398 831954634 103518724 942688312 718732264 572927290 123973354 188510584 951176981 270300301 209446320 969580550 666257076 462997559 830298487 86814486 642303940 634763320 973251249 455388767 616310613 322858540 530200025 643666360 262821661 70278497 899439824 128860544 830139861 25912045 982504770 547200474 830021389 757423428 228535082 199053447 243364814 355651939 180699292 21082830 26561624 870824825 291613652 951177375 35370986 780438367 405754408 9424886 857173612 903517627 243561605 368220486 349454361 577201795 64817749 165850858 349694151 296635283 219178519 103508354 121964060 92507968 952919547 8093631 796401683 632868440 407113598 437135095 604196678 630720396 635247674 770092766 998419143 34156936 16173708 759066811 382710347 524871542 522793011 905076617 247496920 397564040 988418631 913018974 169693303 806572942 939879409 109435898 605299857 441308372 542133799 839231526 170427729 886780173 267873795 789044213 268241202 75803313 714047789 232333062 522396261 293019711 137262416 337893396 359808946 725804389 69756220 20925343 482926431 356209834 85801892 12649683 23136649 265606846 84126620 363810448 57004359 759628403 656434486 869197631 251216815 113448230 394908718 892782156 984208812 440738045 285793464 438283810 686907835 41339407 869870623 728981040 650227113 176904927 484521828 971134411 289077854 90960324 565529493 933851997 790890051 804707309 219555384 77933559 657396319 615773464 868232135 484728507 615336253 581521081 307534088 661580372 608578763 845595562 302074374 212457182 376007931 181916338 74669002 118013790 105351106 385254399 645349481 176714652 202640689 75923543 522692613 189018983 649163506 338803272 214202599 507406159 816486264 545609770 112589025 425813684 240679022 420048438 99437337 228061399 193098365 535398456 443244072 872474596 412567910 896366876 697834594 93823969 953915201 728767565 491050229 780216706 25308035 453830923 88369677 657200697 962930646 814063024 503677638 481803787 177656748 768695657 127476953 130328179 208378058 889628458 48443526 268635757 663309813 961130663 489338034 975545117 578269567 361898204 923457740 331214420 236559115 147548200 944375046 632716478 611789513 443175975 397951429 255735343 335626003 468066745 671876154 416022473 954902412 94848521 119495821 965624419 121186480 788047833 153118284 946750802 102089621 909557145 106804350 284408359 288042801 273831782 296347178 140113300 784185401 353505824 536377826 694014414 384699763 581562778 578644442 144843892 130442894 841142376 103002792 785037651 874621140 690301047 125228258 445455134 505349338 958067070 948872348 41527818 129936293 538669955 332759271 639950689 189799664 959672781 750216018 906134044 102512720 552359876 327754427 165981816 252163750 677836270 627414606 131939982 194665909 632347191 142504650 733421850 409702883 377641689 704652026 621841619 860659932 365775768 986393627 995652020 302582761 814525335 121358301 76691274 746794531 903918124 76330210 792656599 790482183 684536255 728850396 211680309 551134908 124831786 201608962 166788641 762633854 434664338 81020803 16512941 979666094 311902224 359356560 425519692 1164791 218247196 35995846 521436841 986511318 296754431 904358232 627219830 142423016 667696838 936406987 115820925 103831279 375126261 250251950 658582070 68732779 89886028 154426414 900067888 916996804 455050109 903181978 919112492 134746004 978063780 526311248 745516262 931088761 237801459 662869107 370466128 414327073 832306804 327491259 558990321 68903014 682141673 417945603 508904009 181753294 295744030 537882394 387503681 294584476 798469156 584253887 193437587 342438332 122916594 84711941 220163242 984914796 19175052 456432225 948056129 120762650 289581959 278470148 23837743 333061047 650448262 543099947 796872321 79638147 81908668 789701982 438535094 122652272 345860979 340073096 14024112 388691870 689315817 691945341 645334639 194208029 202390470 338289931 135877648 720299085 976740001 400150156 770241836 844570129 766982319 376334458 637209607 13567205 647233759 447507302 834326847 194911998 404365962 115731545 228836656 590816581 132531351 954386368 136489545 731006815 522540002 503127862 260900848 104307581 301333383 255080102 156583031 361791453 970756150 231170208 567487420 126328056 927729399 103291450 322699553 162856670 631876152 775838999 905469879 503203098 552941389 613319812 127341345 652196131 432130962 303537407 742684414 558051936 927195323 439225404 23398247 189428737 695290444 409848192 367158782 450387715 512303177 634195159 846316248 476477584 243135631 176327909 113452707 101902246 771382860 59326964 240930957 550996018 956487816 904832669 538055181 736482614 177921457 217851605 525831748 601912274 375125601 993181385 889202422 284214874 462790632 969074668 562342280 455915709 394127558 518912315 50241152 683629198 504043552 88739957 481724301 572898192 320680035 860565995 6428407 208499044 366636372 495641863 494820390 447504449 254235036 726078641 713031608 40089610 706935634 804792710 264004218 749248581 116634932 527253037 329304679 364698849 17858189 48487749 947697278 139228002 650545954 682634606 567705231 980989084 284521892 194654770 948078273 29795653 966076573 565048965 312048471 3977503 809297060 544747719 204235815 542762913 846911422 13162393 834161029 254287576 37825733 216796843 616974674 543721064 188779110 517306057 111186024 159276418 472640875 52766120 475493456 19522968 484047894 874394720 228421524 117610593 672914704 138632934 625475349 177269763 939296244 475467511 643101294 665983875 47048036 843128460 435267695 632134604 392173253 213619172 456233723 29059450 708168214 436716650 257393820 347659600 79577446 728722590 622821035 514400190 391168618 564616294 296073774 63677827 538470801 274067268 532488217 425484198 267504397 488899336 161387813 276282849 250085417 6628617 307411859 889569828 147872855 601875734 880008157 326055298 30736309 358326975 154199314 370317110 912853956 263047324 748985654 330164902 45351390 542652683 636065643 480016566 344685673 605196467 762380939 759938603 856907501 415738756 979788758 576509059 742801363 281840797 137970115 307868011 485122133 187267475 63579025 148506279 112373855 96486537 229218894 645562102 905573904 614606414 92760049 163972491 141912014 172532842 28711105 659513157 871246497 4154094 529246048 187912701 213546061 96832403 56511553 693653695 726672761 321618789 129627874 482775005 684169003 600628304 129490629 632275240 929681816 161392973 928841613 733359469 209929623 952278793 460209054 263927663 613356565 333909700 601243706 370560174 315065170 805214230 667197414 745972157 593489752 906643444 149990171 325651557 59590343 526284164 193179327 542959766 293768677 795355025 589903311 798483387 239895069 866934909 145355157 396023774 501279418 5648763 141896077 830477660 709109912 170404476 230784500 995633928 964708743 21383738 681244464 330423650 414703277 194131298 50617493 519000282 121097654 921225084 9607465 68000533 265717018 647191146 375291903 273281335 95423453 885162925 535337609 937772087 103770800 289362083 409060894 612437559 793361906 16581303 841615901 214822510 224612401 10013386 476823076 197911589 184264262 873313441 649372918 270373723 700403935 678537544 640288589 11264365 591587997 238520525 84341138 983506017 412822130 799018414 597689822 233238948 626028225 452866065 501689266 677097897 808087678 486800572 15619419 708944591 564747442 74423736 492108698 788904277 823579191 133613040 750513161 247790515 239175560 284328387 173626585 288865050 28585151 924401287 408109249 847667740 721334381 552436292 728901572 844985719 33649185 463281514 823743404 326319513 375517149 589436494 171990133 953513682 92460710 450241878 51019578 941868290 426756229 182674608 300571463 41829151 632630849 31984344 974866084 119239800 684467262 397675240 185481450 374818872 141309742 755044491 745682750 663771506 937172405 74822340 794415459 904521132 932498317 551865472 238396696 969022559 178195527 916197746 713485900 30906125 806207143 168655122 478265523 858120746 79404814 290161663 787625146 600928514 142450691 53364123 424318879 335947708 500151222 618741457 186087030 548841747 790090389 950017456 995156191 142861903 92507312 811661795 335435398 883627340 441034674 99677480 241109782 112064122 21225511 713740205 581890840 404390198 37745934 992385663 59011742 879395000 95380522 14905297 179581199 83147566 407404197 80793604 912682713 642995578 672633130 481787194 709044114 173683979 674176832 280843073 655705414 921441017 737960819 899438032 174260249 824838065 625592774 442330922 601657018 626881568 114879988 608460088 365440089 214925542 291044432 800562105 888559753 837466969 249274603 389472349 376418213 339188938 537474580 648125060 421692975 330190570 868546285 848987206 310132091 573150050 428352362 319474093 273393168 47912338 255695359 252345405 841390627 559072295 364953297 763398931