855181650 191340271 1814 181336613 717318673 427250157 984399427 568054989 9334295 161718979 318805404 965586684 363200992 192166321 806151113 743761388 670077152 422826428 437176106 194257679 616392661 257438095 215507960 605796474 870961193 623126670 798492164 694355555 494633664 438054898 18147106 426823957 862252764 990989536 480194740 739435240 889365005 617746721 30454056 448297505 156755917 562883515 176099245 659578629 408315331 800870764 570305545 104289045 487769518 590564086 180042660 726304926 525668492 632627613 206840356 842942321 270580994 119280229 297772612 334750629 184308535 363904957 926691085 54027957 939193986 40135083 968129789 654200141 962024010 398084686 173857991 113627845 833353337 536666453 777109605 416530941 126253512 658916284 324154045 75539089 410332797 352042462 397256287 932136593 611195434 619804168 272413339 660346096 166801801 784736055 794819966 206731812 585847535 739592934 440863674 20606404 38729512 439186778 928888049 754412363 637335689 339092791 500353879 659279895 192735971 609909328 670143114 596309861 79916837 625678269 186047988 410272973 914051567 12365841 705197520 354937040 905588607 135829168 625787594 987622121 773023069 643270198 897502302 126424490 858954216 421920211 494304612 540001388 278240961 890152697 848730008 519756985 62537252 348241024 31962657 640182497 88620391 37430858 34115060 606377228 169420049 779156595 810132633 634935185 61059714 511289867 529944121 616048931 803242522 164025198 989480181 995088899 320228690 275203849 353078513 387655548 928768517 360830521 479930951 582471885 543721405 921907685 555812394 581193945 397020954 435348109 958404534 907315841 792639537 160493251 765191212 763300506 664941740 544186704 31875563 919743825 520081730 358985601 114842583 359557609 538751411 88631471 389124579 395235087 241941072 119857629 73168291 995008618 421514942 107811749 666558852 872836565 156145484 920452602 856904510 743840579 344070343 188458505 732630766 892301739 115633260 167430227 899963178 834569856 469735224 214294040 746681054 426601550 214839523 886276594 849383234 741057648 255328500 28696731 475417757 665386564 74377427 368394829 138464254 613462394 345201115 137396738 591654730 767346052 765391423 918396695 222604284 12406542 652804028 89672428 833291064 100467390 357677519 30917838 271469289 408341053 598290334 619869800 723857801 311254792 405453649 355135474 623022511 712846468 974110350 182755075 869873237 756753373 340600751 861251336 702173229 54376608 534208968 570683468 214915533 79544821 169657972 298247637 180330318 794091205 19359106 477453375 40244921 124146415 588818778 203767924 585938170 692908448 686039564 178718542 214106371 296114948 209450628 425048472 509307993 972477340 742105531 163264759 378686667 658901479 226981243 225503677 604147984 120406321 225103987 502314112 480832395 545189359 830562987 94878315 558380704 969859183 949989027 404300162 590828101 202727669 984153405 563107941 609237522 574298441 34564662 221097661 838118254 755701893 297849942 268560079 431886339 87932633 695063381 3754786 213579927 50983777 260006322 900880916 474765673 799655023 758804320 535868826 699753323 130928843 660957409 936844741 412790593 367563262 710822787 853951470 781123754 754922506 719533022 858710455 758216035 126689557 586369927 900322471 346109339 666007291 697550635 892006161 822497972 852077341 763865728 493213358 569909943 442156823 215363197 243566421 334434077 627310709 686413855 362763645 246774555 203745199 500256866 76602559 640344568 817354582 66472105 112845329 678111693 244353662 877460343 105997716 695695662 357577756 682451672 612313985 386460082 354448680 596469793 94911023 513142694 5271048 854304661 528755975 498054339 364606417 729199651 680175583 514691380 468214239 967346568 465542500 834676792 331800419 484522850 733756871 149566296 563989923 79847080 117603906 453216881 782340560 907985013 947416208 550547210 799652302 559650490 104500829 274573217 324578070 627420484 756399862 839120719 503305745 132385251 511996917 975209797 205187532 68627337 979169640 278905363 140921858 828195283 685467452 103064758 898678712 834115117 440940127 795548709 120401585 51042612 842910848 407953900 256918999 627318458 512170678 767979448 265617333 409885774 988389593 571871799 284240096 622631823 81348697 88856120 514649327 816216470 33940061 619308978 637169947 791529673 575229004 267442013 726955231 833894746 513992813 382948592 33783343 696925066 239558835 222190771 690428838 834979025 546649260 329433092 409990856 581777192 265220484 125381970 735742876 314958937 311424881 680982973 667673518 596807735 347188092 112341727 302270148 192872040 111341903 196542892 175167990 449939463 636288410 964686086 859501516 958238838 704166686 538152532 244677938 337237663 417174810 453308358 4088688 928702228 673575684 783125709 47023460 855524871 654910443 384779995 949027371 832940666 8585603 410003155 113639319 686511868 986342703 665989092 184004526 75831865 501460798 127233011 865447686 298858413 231313178 438619831 268535993 539630389 841932089 618949151 507858522 665381966 145170308 133179598 995839878 312635049 413585302 662113648 581595812 734876413 959630975 498185397 238630407 555546711 202990281 984272476 697673317 598025365 254689274 366777902 875404889 960718452 344565612 806654662 996906940 643989869 872012297 43336102 763092227 214343717 633467205 209724168 141998453 685267778 90088175 896463157 760083727 822304431 478213295 723000035 208233351 130482101 326025001 28805420 279439368 795061944 272310375 832326808 879149366 560647059 126058355 854836916 402335850 712559955 315406117 15416662 388705032 183425567 197098326 870083673 440361505 712676137 528248319 464332408 198419014 135633795 348771282 90855563 321375604 979209489 727081325 274938824 626259109 878440422 624596840 17846644 743597140 951660366 250118755 8561633 313110095 553496993 37585957 137735887 403990433 707780619 680634733 609026261 142907550 416426581 891145332 152542780 568256594 638570375 169608336 80592527 857343592 467225940 51852606 465084171 43152375 53281197 171369717 879091548 399177608 984989731 748357596 907575491 284749874 687344643 715143631 853920695 560565707 854082128 450028151 439724920 52727662 211254623 646013513 305310545 554869214 54390703 112342573 258277419 716827201 833045203 471929431 489660770 916572161 579347553 521555831 471475500 371372342 144262615 582175945 545915024 547960322 655268146 113486634 420291637 668083748 769237689 816420074 547355347 954561462 22352575 536029657 249549171 48981297 994305772 461122887 532930466 749816956 121730832 202944932 601715781 414771758 288996543 263174966 358447704 889989701 738829516 890754188 15456140 18894509 281063593 942724974 336502133 678959426 702417352 848092237 997946186 506379057 351687886 815354538 793023853 105542840 653779008 270631794 455214408 844405502 556755127 504949204 895512266 892948402 38529313 853034524 605669588 193794496 840049127 565635486 517500550 671289290 984936544 701578355 209066130 974417532 289881693 200657203 382806599 351746264 75266794 397711178 708594675 220428094 172168553 738288113 593339529 539047442 757401130 841729894 990091699 738964584 659703117 88821267 270932910 79794940 143340964 361952550 785125199 217614495 478207692 398199258 525973427 312906327 14758579 130505265 764241040 779545398 194782661 908734432 504022579 590735813 687110965 437381372 624210404 210894980 702973836 203218867 591954732 455956928 108138919 241469806 752659914 496011398 396747700 828101067 110260395 936617918 288871479 172562892 79712689 503615354 290176869 159062252 210860714 271645584 633558773 778963395 556509700 86789298 559436862 650585425 329295032 878664618 551178937 448491801 979876628 482066869 321282843 70801826 251001577 513166485 42196983 429211804 459037529 820865664 503049056 837768349 711849624 176846596 739254328 297010059 647688119 338193455 377180519 113051984 50368318 93941116 981493282 903529772 167821214 140106991 393493568 282134674 211752288 134867063 868633694 877135949 122757284 271636537 654222206 846292238 477839719 410074387 17316611 455666866 760986090 70956265 336705558 324335500 570230044 482993143 276172497 815989123 458383407 231330558 535003570 926721172 352343762 708895849 692674441 384938939 68100049 588535016 852369576 32960198 496011531 845124577 855570354 437596268 883455986 191621906 702944373 690492084 377012638 380931720 581581236 475065050 468503254 184575040 871871819 561067262 956741720 445523056 605110846 766650799 769549099 774561144 482896939 938427917 164016155 264762398 434796204 237117833 880973200 472123291 125311241 971075925 754384458 840591756 403401315 551931225 558291703 507340600 404594415 690782186 301805620 120464330 17802788 240938837 605438323 520892416 822082203 856618847 408779744 422479376 877691091 709822670 714800814 817327418 957538363 282562956 717352718 911302285 70289857 959393139 820805849 252423934 608130714 946768368 293128802 376025298 57231974 583763848 266824019 620488764 902338480 162195647 977093381 340945862 688703073 301622281 209049915 803416728 726492602 658051696 795890224 515032378 51076615 448818090 487949931 424833177 7753675 614405593 893379811 423249422 631434217 781004090 815560755 897410511 849807260 995285700 564804960 455508271 486121574 153981031 265290543 646850123 879308556 186149977 465966385 890139896 280925103 124702073 848359772 353014055 293745832 58043359 53804948 230398048 942616670 840330770 773398983 917530615 532266184 287406665 467381631 465623439 621578598 339042748 243819891 886362615 614390994 733483629 301252168 549502624 816575227 522712410 601284597 20816377 20016515 243498947 533187980 29281907 488078198 655011738 78378342 709317058 873433665 496074716 206261472 701389946 450557141 351011527 649681927 227593881 23694869 451418089 650954863 771013653 195658834 464511797 372426016 31118964 247940759 521810134 567009423 391924649 23009336 197959185 866932559 855254864 331784090 303472824 139898919 822457089 875275773 137817923 579046678 14178043 938684404 167403564 126929063 225126665 252249337 266281433 456874878 808531282 415735589 179215445 858794104 332250724 663190082 825680932 400789224 337259525 102547810 487446844 161559426 107671576 417011374 152214009 91311503 877057897 922528330 942931088 378531569 577543528 22874881 314259956 842642175 278287674 443084108 144188225 640692863 290353934 667358804 622826297 159050808 310025372 336109600 367357146 497387107 337704724 849757411 345857643 764892084 840109711 169546524 894889155 152686890 539183410 275529181 160286328 245877054 134709829 906426404 294865952 537563199 723432190 255791019 973743687 58052169 264618450 277761902 880611137 654229499 55199313 535640679 635868977 767272330 884145642 133747224 537897603 926434411 739998780 849702283 578825562 20043035 50088377 245038623 802287886 945469183 216677542 136270414 487253790 578577435 347858521 383956051 306176411 198191443 366178746 764603418 211706032 154089623 1626079 252728113 372602847 433981886 168101679 680871155 512899499 997945345 759851341 311804745 684602744 522534950 273102857 880846219 583209140 725108312 288349653 84306705 822078929 792499832 850241522 364177325 48652048 772258758 143730174 846573005 413219791 799241411 376387561 577191813 833793171 279552679 336801685 891335709 172448937 767698377 235135196 353143779 644813792 261688892 396320974 623292082 232022773 621524070 675661569 168294652 818418347 589595538 767333401 48754282 590744736 525774055 319071256 376535338 749175073 683598414 185710691 169779298 692756181 27542259 444628984 167612206 329794265 576718554 612691989 126308134 248964162 922862014 249238337 980193274 18662340 756290907 365800265 684146503 813168037 643896680 11937112 467473865 514592937 720844965 21453219 556687910 481266185 422912237 484610421 522030787 39211496 628911119 889083686 489973627 174916022 264461335 275217447 78189122 119900941 773756801 602053587 739044465 763280377 680062943 308402429 583149961 457384371 512370310 801065933 817875418 478592097 650500420 763492370 768245031 802380204 24278424 230625452 828070750 254160460 386986532 78526489 716907649 972031382 454630914 695963974 817300009 293921813 474309962 437023991 440753423 251208689 789891593 692203955 499118950 173526145 10898279 265766097 905665016 845750865 930831834 58347566 48270985 24968600 764918843 667179473 348990827 652452348 740475577 577582909 282271747 62102802 111269213 99757289 96392115 952184272 705475656 244660599 970729709 317818579 354491764 672737724 807442778 338322592 406077058 675505726 987345654 90047400 359505836 370562509 778243114 440505640 545163965 989944800 934654209 326508238 927505309 313781038 880790403 928496311 355789602 347357136 681713926 959297898 266310783 822768173 728528763 195582918 770922531 994633590 955586860 145882552 647039092 268386264 407319057 778273226 988819001 547394236 437057125 130471248 730871332 530825516 486596790 39329821 908894845 492730976 139854608 596530099 32955507 18151648 531630766 337787921 902642163 309241900 547204908 645780681 767992964 775006460 627866712 88333875 64770764 327590207 49690868 1842202 212278814 697438789 147280566 831758752 335564006 683993592 187040440 339418160 401380477 669222492 714353442 165886522 943172266 983504239 46219901 891162721 202420794 897612439 202356497 650242416 690054556 684171669 825001237 352699851 253160357 671850889 324139297 794810639 211302445 917119062 525812835 114955910 780047920 451677605 381453242 15538956 811328929 390939408 263787194 361557905 764700049 469606048 81208552 646779875 405782340 478353914 643698979 369048135 66442797 191979240 311741517 93542603 796517388 784276116 340511637 525029254 344688378 345807069 120997656 126356339 799096272 16232120 163868894 191622626 883142279 176920176 931200766 288848233 404254045 762245229 884195524 191968044 135528574 844507495 178415942 917737139 74867996 269435904 167567591 890320905 411749191 183465878 972509567 480236209 844614826 143527645 349208854 500060100 765480021 942776176 297424523 195574189 229098363 82656540 992169992 102819931 698482538 369114708 563335554 552000572 695445859 253911196 814190165 867029825 792354770 587224294 103912567 341292416 983219042 44361236 650599548 576851429 745221003 719974990 199527838 894794557 20698665 721763947 753870912 211508576 769810940 782215510 196084900 430207288 922562565 517437549 638527773 686368582 21079525 21127449 920911245 530639176 445594857 481309030 902677604 114139033 236045783 393524535 972694264 738792759 509905628 161534746 531331416 306021858 619620801 92403333 668635864 643394520 711186301 731552982 161396891 396805737 738627860 813468498 920444282 647584424 664150527 956610346 816841033 919109509 631537969 763020930 738453486 3288800 534574526 65242946 616564154 637790589 100637448 181310826 738225613 431766558 549146247 417098842 784156844 559447277 945885383 252405695 795755910 396872737 468285378 250300712 856714690 600404009 186060349 912905726 995591748 709548575 809226455 82227361 206692796 544529517 114652284 772548930 400253758 847925823 357292812 691596458 227688148 331062765 192510835 234783518 169712706 33008585 671843282 713721931 687200626 795631833 621694655 621853047 8729000 30547570 813961474 280365767 105402096 883527358 303280295 795736859 484942458 267595041 635098320 633201561 183808102 531212064 141705147 497232114 811823688 194526178 197010364 148131614 717567490 709548555 344992822 967359077 147104905 680432222 952299968 88158335 580730062 955399020 87797094 278076357 950144345 466962396 486059254 970715551 85834499 846854562 564757595 69704123 160897226 366555983 100709882 886014596 735317526 95315947 295041523 584748680 630075633 876305222 39728422 812430515 506221432 807211867 274726627 411504846 501020121 679691022 911228716 327270944 180145460 227713525 681948293 148963762 511392773 963121142 787506892 613144710 34920324 156695526 855465726 216739688 457923705 236099461 242831284 6634290 175431991 145186442 740037111 463949652 206414290 259162654 894721335 429403698 708674971 610437699 983197551 414752743 23653581 838788539 749119323 655106156 421005907 492326122 189859051 428902241 615955331 94935173 72760005 609439125 142429866 470551091 783230391 58757256 175696800 848487633 281868449 209153518 862149603 887002797 207377775 273744762 748978565 40021714 340635179 517163031 196448906 822853041 440865668 76545772 709807866 706335665 761856591 947130132 820299315 294858035 135461263 337587640 614619477 597534264 183413365 855209317 718075517 652844866 794380817 960709355 938180865 222552157 31957396 686928803 697584360 796145015 264703340 323964736 59336264 625254095 241552659 208888585 616128098 780248548 824887234 884862797 744068436 198935972 71318238 114660088 42390701 710130888 538182557 586220166 212921542 167177847 20044837 879838275 770087519 456870136 143179249 178618578 175233851 836109375 210926515 931843724 499783094 434151775 474877592 730121837 920201203 231208707 447922497 156670685 26894978 202595595 979170686 968821584 169497456 825817644 792619931 148192370 13165172 88655172 609971161 708176511 279635539 333133993 535934477 51135848 680236103 314548877 625120751 67631742 857944053 274491958 918530887 933857709 385050498 23660296 419169166 344481533 906571790 651599456 361961062 623731215 800485047 276479549 831368375 868175530 293244962 282350199 49471851 426040718 591441053 335078056 725276734 548497861 916921640 406863204 868636489 473030126 535164814 866921710 732753214 518086843 526246091 468391208 310353836 577477790 558512256 16358986 276697632 32202347 933116847 816805190 692807773 906829394 720433150 333699172 281137676 612394121 565109321 832953082 413332312 931560502 611121706 439736649 582185328 600500336 621870282 269607655 922981188 139618038 960960553 37588240 513437655 215564367 565101091 818229609 108046634 381723678 258601548 31880705 302313165 525982301 311107805 177181630 690986271 70077151 556047395 805231974 934300162 428953210 539489939 174247047 780561901 640626109 31265474 551971110 807476698 1883168 777842584 783281729 863219340 635276295 277523885 809906635 202018743 535475915 653088214 269663596 161454595 635766164 663001352 28062131 467174544 679862551 974876239 342208973 595912776 548026113 941756283 275162824 636585671 799382085 142351535 907070201 101942390 177566057 916074188 717752744 794028965 924481285 684616672 363281018 390123316 283434327 292310191 284158216 821802923 736673903 951030445 731370806 428989859 840973890 460340205 136808029 262008057 195276086 918539777 33918401 563179533 203929917 120427131 165189926 79800149 667896229 101916881 695596529 696609926 919885944 521966192 942894106 732266339 131999845 654642769 913503589 672048889 454629275 667965342 329857471 517434140 104035253 557984013 264980245 254268143 982988487 6212667 45327702 780000122 853114370 685733408 88122696 253290881 217519460 777989027 224148706 822502453 79436567 659866585 524087350 421513809 355460974 865731030 310605238 213267096 220137587 332361622 236137489 501060735 555607352 790644011 999022321 411383924 788662797 201000606 638753272 989402893 247562595 545968887 570639494 537892081 645009348 506988424 221356593 602633036 151719096 592774816 281835051 458728441 743454391 621063132 449862423 116118112 728792508 248876990 176852282 74446567 464990625 898409616 543384603 936921314 425747004 479899589 177212571 783434274 491936828 982117942 88171007 263772648 634312709 510906688 432102459 744622098 837892728 776542868 313877100 414735750 908213812 260422473 38958292 757503056 221675034 410292782 173404116 778424119 969497013 446539982 155606239 496272532 81562773 110636182 156278233 503145145 633018293 368140589 318720680 866025510 569866154 387138475 443800189 852482437 932827309 989827135 432869 301666872 679833136 274814429 521175621 727850255 619378080 919416529 32254714 496844630 463406263 891479550 302046803 672716360 214732308 422795671 894419901 307962363 602898170 891233568 95171853 103622215 501967642 427545741 704992475 617285938 674047212 107190469 472751701 774843091 474448778 274198381 972976289 722540546 270787223 306163030 407202415 312916309 297873703 976697397 72438635 383553685 647488405 454055351 961527564 513468384 644502359 307910928 512448164 835853685 476828152 259974193 945275068 789194990 272175170 263660741 12051034 299742722 396370512 315645190 815864835 149520522 684470958 173274479 203163559 52328281 142196787 343918763 179631707 194382570 35677638 801469173 330416690 949613289 704770627 344023487 975690283 389735999 384371752 724239810 803248836 719688014 627127761 252974667 592524597 786674100 98097857 969478620 467390707 233809620 610957873 131891770 17579551 175185096 433917383 113255276 781557303 898765427 464320869 860438887 683332985 748309141 912019267 944309406 858647232 695834714 647795493 300594418 108604357 94133559 600032289 3556170 56393451 626662625 409504176 552493414 274173350 772030194 658899556 557186367 657173538 340870666 154832340 47321986 299964129 342597294 701380654 951925981 111147751 177594850 536301052 360827636 946962280 609281393 159503421 222930809 775262072 240301913 442116108 574582829 942924871 591322491 418935233 254157954 403811536 269151851 82105376 419914048 440172774 389660511 581552322 615411067 461804941 783330930 285929951 689881743 181587511 445321672 267164754 989177876 664112519 858627568 331122489 362234915 140694088 58125240 796060417 984159117 357975597 135227 724270634 484115640 271725012 381693475 736149672 236284118 38325398 619613567 637455148 5166807 13318458 894730150 66055559 921884809 108591793 851076668 142468856 238005331 342436147 237575475 826401989 988170115 663766025 87740827 271560163 897908386 376544413 216955206 347008512 725085120 860179071 463659847 54656858 925327280 59881858 282342228 770864271 296824703 452560883 953445822 371697457 510261684 970588246 726055836 739096198 835279789 743533216 688358912 883960958 206699367 964765544 993072583 49655542 860518038 773213896 77079653 217962682 730026477 808163301 843144012 499813776 340324386 858162049 155923451 750474790 338625762 172037801 345242997 766042054 26440973 121304001 23356998 967305841 928497942 255503838 517011714 777992679 359689339 7568737 213668078 11639900 925198917 604531786 639338465 790065846 8178747 99558282 944035625 36129112 631788441 734842604 828402474 977048637 777304569 838628496 52163565 838469338 360857958 761370406 771423733 130332099 657094121 670473359 967952111 197460876 196878688 945389265 799452281 276249387 508321040 698447432 933583513 526041715 329758884 747878146 920963506 176311908 72412668 540501703 611368628 324262263 538441648 556011305 819378971 122160395 918076454 809190742 519871511 950346449 127876357 629551136 314841183 781794285 852439389 947221843 483667545 411726187 514952783 227870660 499732407 714754122 400327493 494450781 12168465 623470682 695957105 933877324 443602330 572280221 779098732 866694107 691835887 717298391 655592557 298326544 974586931 149806192 388432399 723818334 130571896 687654935 270877453 312655811 97842811 470639173 939788672 544351618 261868357 208509490 345161715 389713944 548098590 100013138 630831178 557018427 462444871 421504468 490187635 620455052 712951960 8004086 432578497 302589839 388267881 853322941 299461288 268407744 827300184 822456336 264676441 163781373 819553201 817696774 608048818 123755955 20333171 365540928 861203556 920106658 867792102 33924379 635943729 362553598 430689967 166647220 786954165 463283028 968254357 339169983 566416204 639278749 527619518 208193053 811981194 44696001 102632541 97074224 905687438 319525654 939914068 459039723 880346807 458428245 716639542 381454086 969080717 984315417 844770518 593550477 414502740 256512243 667404185 334024774 663536561 507159466 329045323 300007439 973060644 99665441 577639293 211402079 124249754 149524116 240096247 330953354 935505371 333758131 262409616 770120083 351416849 749789613 904212584 645334105 352570915 271292669 749772298 274863391 417811951 523428402 294823639 723565700 900758913 982185714 959900043 123819575 269791363 837179215 455813536 5840256 646283934 471483632 290857655 588412398 940646685 191065571 584878084 841818433 70716564 958181641 829935848 797352043 35284955 247039664 211197801 328005153 215990192 180913761 8634831 169336359 204935371 980774418 28363719 432428395 7180172 833738073 457909745 112155520 301381262 868166572 338297893 604820913 479610599 269212255 988172006 714510220 937172279 347089604 575898134 611911962 138581052 265515685 708584257 129385941 846913649 127373435 722431697 559366759 506998169 326694428 562555020 542519420 36331467 86244809 706845247 342152156 711569632 204997978 379070847 278962925 494412936 834018660 752211494 60055282 564097317 578804167 188268307 331104397 329090383 506416154 231402240 431942527 255447200 810528900 197616933 153915716 41475760 677407618 797924733 103228383 378895828 495211056 678542842 411644062 371093862 777969441 649106682 479083724 898785477 919318861 327033734 75014619 393951938 435351660 89395895 150876829 376023201 562843859 6808487 600037717 152348869 29332543 250176917 55938865 917738662 68989918 203463283 909360673 514394524 862959212 789772075 154812330 337595874 109032853 892112568 431807359 110315348 230102607 961836674 467310737 897592479 490963201 825664604 239679056 63839889 148224884 636340627 481342245 935260145 957447750 632347814 758738907 635454358 273935500 460789316 488165183 290266889 531888325 189327073 695902265 592762969 769175838 461641674 700241974 15812862 609708508 123528982 198512546 338761417 650895274 516527279 873130511 124788593 986574788 605600607 719754347 421744565 401337921 578963637 213503649 473303150 361413618 687433500 682440710 108446282 918007020 757076668 404557385 569675103 935155879 226951395 934529580 714631269 694649803 737935011 790581364 829942969 482771885 362119896 506991597 797615700 338090958 670061806 312055561 616592334 862676935 918150445 998087122 656186186 317292446 926330154 822638273 39362179 227700682 859471847 465402405 29687029 334380931 93748221 995231709 401373730 448525302 873919991 257937439 277264057 84415126 376240434 769391169 636960387 981389401 834980537 666352044 54430645 408885785 621268670 283744216 447353379 808911483 344943997 576888198 667718414 901422984 770939186 290028863 207888952 559994302 886164905 406273037 25431609 201095047 937980596 243144594 22393155 443996427 7370980 281461875 714567733 796435114 158582330 922396934 621360297 724492232 768271118 540465553 518237995 276356951 443428993 923012433 572751885 195017174 172629212 473717884 852155785 77897619 147122654 744088011 611540288 144249581 684083541 663034071 753474747 672604992 386375537 157857165 717282423 871289449 975519484 569605537 162874111 375350192 841501580 291440068 161394161 27969271 314929819 876743385 591164200 862247286 579054864 165197968 709892483 905733091 757214074 772591282 304727549 73453549 869625314 380838423 558759987 29990629 482518256 890627972 712836472 188810942 854321945 186395351 138489966 805859942 519349674 834830658 170595345 540921278 720791871 561915550 864311675 976921829 87306336 611521803 784030158 622690618 487011235 603461491 729270507 562495111 476267450 579900862 321769688 177057506 575487187 471941903 107817370 422142360 153006358 617927991 778649857 307761197 646004220 919088147 275886444 494368204 827752443 799551441 351415786 300419541 750719950 305710241 732476745 247597466 490165243 614300682 132797446 159558303 324771565 872466640 287626211 75021391 714824350 400889517 773712516 482475559 997115380 78281399 477627226 312987350 990695667 235150881 862782390 737117264 915610492 943756470 901187957 553547147 128241547 846015675 998052543 965320062 694648119 257285705 165680710 837123241 911907161 672842275 524499858 636713177 441612394 275753252 890093586 686547344 580199636 19143683 772686301 349513434 10258503 530072516 77467150 847984032 925307279 115933452 761031250 840928265 747821517 501027544 768871454 277651558 619030681 971381425 69692926 175452844 326332762 940465274 310487020 197350041 79354894 548224718 883884604 527222244 844960433 11787005 162853645 309791206 63602799 441514738 146692121 677640342 63182838 514647677 394723330 492429061 88557002 918622786 469203965 590683353 848597333 833705453 893500484 477818701 568214685 288032136 76406045 991736739 879540271 341888767 527009532 864293097 320829677 990297885 647449118 879328408 380146523 632257192 171841334 337885541 122025630 451313147 619822252 409853417 955407454 192085775 994643841 194119475 864871376 625290048 252405916 842494014 219394581 448580837 320603544 347808586 454849378 286766642 316478831 685753819 511298851 510614497 873357552 433096057 21747762 827183480 593896021 755547603 890930571 275698066 385417029 873648991 64341782 137434661 86238717 656560918 939327888 589463541 503510980 706312934 389322415 766387196 784512223 295735527 898798826 579763192 43333906 929070941 227006810 112001450 509819897 352686341 908208417 22392374 747694516 13381158 694922472 860259769 367054970 741157167 971919720 191831104 20207514 546103967 484993934 491711426 803377854 356093588 364127145 128922360 826261927 923124095 901501474 176609051 8249553 303519163 731813747 204105873 409542905 462529164 187962818 621697770 872296758 618013335 857540812 817736420 58809367 284287314 24925788 743034519 62382206 760227120 713610523 479046029 938976580 524196501 215138805 430842599 613384413 465535226 887323721 53045532 400814484 388626390 65345976 834306176 972837543 500227114 927961576 421133125 889217420 909472112 499418654 415561660 102514765 551402397 567385960 675378096 409356106 408248389 363807616 882956516 770140923 328678362 198227977 654474016 888448417 904927314 70554156 790661673 235433550 572189532 940899150 852988290 568411508 186883609 124865025 463226562 955015231 517611972 152576927 509264299 998726027 906160679 593114625 406859397 614355334 275285382 386686481 168945048 314142448 855177348 125880944 92778916 340334749 118620694 222898004 314792101 395463736 726916577 816382792 151867398 902349896 765689163 52155040 617431535 113490021 619900879 765105905 828045193 867356309 899363007 201230712 14223757 433654259 559280217 492289136 14080008 286131364 737156062 283034075 88295260 788907062 296551229 208670676 49886314 624639971 71623273 11349418 622683588 728728485 140288086 998554852 708146908 69698315 69849193 188641528 814332334 809067712 127360360 635026711 322179777 866734623 141271583 252862741 398658657 970259005 158311418 834852006 631364964 788872470 56836055 169550149 643754836 232869676 222892409 852919060 511469245 44990355 33640556 445126460 115999480 889503108 735640765 97821841 15638201 395325368 805866017 29786886 863303016 909448797 497872483 740821387 291187000 295408358 654170023 453801419 482414686 659064977 162112360 453965560 175321124 870411187 774027714 170006828 478219478 242652844 69002971 539946473 253545872 776526152 624481793 980374137 574001829 86544702 875107063 650658382 203920123 369244944 59699415 105857272 446125236 976096336 984435309 817820478 49080110 116452485 419822111 256246802 843689219 512452104 381081996 502046059 655279204 500888042 489137875 921780404 89373635 881126160 883820229 690447812 508124170 173514064 50763596 132090947 455523494 59477109 674413575 453552760 889752437 17640981 645431797 61555375 364932073 118721267 513089326 763054150 820496772 572012105 479367367 953956153 403324294 941059245 393619561 710354865 66666675 343137156 944463192 304965548 226114040 551990724 615698773 80554751 659544514 267428853 912962686 793966660 914569351 878441755 488778827 903963564 506696777 162130089 81887043 34383798 44421595 233132617 359806469 265200255 532783510 826928269 102440491 972154479 719780368 132058908 852985526 391888164 529084172 406562952 333607916 912018968 1987447 815600887 854089414 162403328 231095165 940039149 703232547 454438078 636203973 422289721 107292857 871663183 740287056 127164248 682161616 821409605 873688500 846662815 373378262 601024388 484098687 557063968 505756843 821793762 404156612 77921188 189813730 854243944 116367216 875321061 712473996 690871387 474139849 511266995 849659052 530637842 288784894 924179302 910197798 243687738 47289594 507413806 660607834 186797174 606821717 552116478 482530391 966995176 38262853 625596737 693452613 205302613 745466249 74346010 855993434 974479561 908812533 987309486 16243003 136720269 451743717 599192050 427609666 250119965 606460114 574518180 149985704 971039234 740424568 243606653 675596809 814104376 674663087 391805910 41028054 115462034 432579343 614961940 639829577 951908444 283016019 292803608 803545859 722696134 4762894 981285241 200615464 130720719 717860431 214284346 642892906 889397183 159310952 758599235 602130440 89687177 76868000 709511109 157334701 410995863 619371716 208567559 41315633 337831930 343292915 169330465 832124351 747693023 64969454 505303764 977720286 466679347 242976473 863788793 514402904 220764575 81583254 516569958 714179611 411464223 289343407 248575761 494472752 196781875 828568867 333542260 857807717 953101733 737590182 254166376 441572958 932105162 726363831 26204019 55736434 722716533 62759732 913523482 978621613 264416648 903264776 33868709 452003514 733795505 977324426 167018916 253583461 231815040 370220208 889774950 547500955 571293619 406790082 245978695 762765640 678375404 552006352 344727244 549105339 842134148 167508514 21799400 457598636 972613824 911639165 263601068 732322280 646854221 807660045 779672951 8990135 802022834 262432387 104725881 267669028 131284761 971430292 943595981 696866431 872629680 103754250 85869772 678358994 460948079 962597586 426092164 63690439 554623401 66963115 552626704 136284513 576282683 853967614 343946748 590082904 30087427 335465881 193986643 995274698 993810841 932922528 237546776 826644440 823903365 436432555 707444299 258954188 118182269 236001660 591124888 392124272 258224092 645966537 838775011 249583295 872043796 80095902 932698675 472812373 734337827 393657087 292241300 919372806 882806122 353301442 749360170 790887638 901735632 804845842 950115812 319483250 207884586 323208781 26038939 369988564 659363465 998218589 689401956 955880649 375308740 846336610 478294921 231917913 742369490 855027960 368665756 13145408 849989940 363683736 104018503 365873487 986024425 521512987 558776249 257798658 833170411 658765028 499258853 860784004 692367595 236076802 620802331 965659856 918817594 552701488 141873196 387338849 158773197 228204752 799012339 860355250 978082998 920319024 690863368 344647664 783122553 722591593 262621108 134160789 928672086 196894018 642595171 11738420 512062380 43270317 237845910 361198206 709135026 398507580 148205147 202992120 747401698 668977803 183937055 493490038 584818672 366688255 44359966 559672279 132172252 412924308 603730207 773524799 193615172 566754206 63653647 664274247 955837608 415723616 234096492 803087264 233212204 962132118 478716781 807123871 777537174 482097458 300571286 804621097 923752858 238531342 420988203 491782632 240288876 635342084 970280969 81256633 683941908 242133817 873923271 52340038 310746720 26665875 241609514 440373677 362913931 461933873 163084300 778186740 421210550 345370190 117599296 689486314 461815971 232143311 585752655 925645111 78849332 585840752 501003976 818604753 117648693 298108326 301223530 439542272 973269158 842848782 964180016 6476518 296933325 404688948 8129595 103300933 528989410 991099025 21980826 414098873 75415616 427251936 503100563 270481551 959126300 514650178 957647163 699780049 898575630 74111279 674685353 456370128 516615778 941956172 607459827 97686970 37078157 795880880 612363352 801977008 197951267 947615338 885030336 950881569 668467330 193476226 585107939 481838576 173097275 586548229 802479173 990664317 565100884 879550793 79219107 442507397 415972444 166753025 857932363 977290563 103570611 631161059 765944337 504687549 20169008