25000 1000000000
648497220 701369541 957047003 196403109 65369235 824257430 333066651 372374720 814865823 183334769 909681449 491169496 71337213 917812367 572998514 78732122 838579442 774815056 740169287 657528203 992705229 12103541 974431030 642748084 252938957 612443983 337832291 650314288 704247071 524233655 98738357 391940890 302035949 749411082 931226835 775653278 530484066 170182246 707539299 265057426 997296200 172909326 968238225 15048931 779710913 346357434 574076187 415811964 307916134 437685027 815800857 352706231 360933186 781434710 177708465 357396445 516456195 517352076 169955612 764430335 489135940 91447735 338367259 57199279 343739477 114311630 254351577 555902948 689540789 299819413 463454047 513219067 585850090 906945782 216600037 773368407 554271292 894531854 685111166 3889416 57497481 797140622 296160695 614199593 97096719 562153372 410643225 460596209 3469282 895731479 843975092 742138759 620985942 226860205 191815942 837901293 329355566 383689790 880005487 344862848 993082889 183463238 851579779 294449472 137230679 462368977 824452032 102480674 594872515 855820748 30368832 490938396 312288512 467439444 831174366 437164514 303983038 203466322 816909208 150234138 715400222 995614161 691761450 901167335 124996337 608086643 608034787 79273493 433726641 306172043 126187355 400597065 86831326 920094865 165923936 545809945 709630728 20300397 941303317 919652478 580252265 521067238 850642223 601879143 221875088 930047047 202671744 558426631 546235211 766185831 365648369 634859573 208491708 695876503 161792718 349614756 521124968 726388904 908427038 962937500 470497827 66179657 594947570 582135415 733125149 47963989 795805705 130117036 831924242 980599281 544496306 447763645 658703929 134275938 658100453 849766370 934631296 701721537 718172510 963868481 382353141 336047617 991566948 63387949 345584581 743360829 942421491 798155870 188094903 797901859 221292972 528267531 614031848 983781809 222918180 349180178 308290829 295271528 164924046 403229896 266420889 261849955 833021970 109511111 461605344 41146649 56763056 848491626 784156362 929695630 110818283 777124660 297814500 789418241 566411837 433101535 619517989 258772151 534942806 841882268 644641728 754706990 965986958 123694852 774084823 959737739 539816505 336480891 638261513 110293416 757509597 742205272 24500845 532600926 493709157 731603615 425577444 85172538 22136325 281321076 95634737 178465767 611452697 885265702 176430501 560184749 486547744 645477032 958339588 372352180 586423718 492409629 151247183 465072210 968743088 738075121 200123545 333432281 192754110 410329577 460797187 135538861 430961010 984728452 392253621 639025418 976511386 385029129 341113511 435725613 160191550 70099868 139699100 686946507 780645648 772329187 142066373 282826852 910059218 721712686 389455373 745593013 268044236 93715661 907253324 862532229 494164535 418893106 915218089 557225868 968896038 10432792 648386264 254391867 713933509 920174956 21279873 671435690 815333298 483706429 122729233 495222014 694754656 537936027 563979927 323784581 326664519 244213164 728069710 11750315 597024484 664057112 447700225 422218316 778104661 502704824 57356083 721554933 971446161 981943983 861044508 43319385 561941305 187814039 825258411 127875418 501192277 894372505 193040415 756775726 975982253 438073195 490682723 81418012 913983706 159671353 748832423 719646252 269490169 981182362 927194242 624448989 417688124 487188111 441524175 660672961 987003619 95619643 280839747 531234240 623872177 694815986 919093163 834654615 366217430 409298573 562075648 929944116 220115679 145286431 308665037 709314439 635655174 436865343 498021429 677923424 855675123 35893469 509159446 33062424 768109610 493296101 919522589 691932230 782681175 486776442 771151086 252870330 169524999 589491961 496216297 542590200 808107955 545162756 675209317 683561648 424419060 797580763 677457570 607548345 878711505 662812316 456469615 248870249 855714448 953515395 418773191 598332294 584617889 732111211 533930557 702380792 796876599 261947777 712321756 781239072 600885700 941376127 920720141 242982058 414678050 884762922 855379406 209459684 217367763 159371250 989143778 51639938 810226963 747171487 490698619 60152113 443185053 962419020 118887353 422223464 766400413 244508210 346924919 517721992 444804308 654467647 959449625 3665497 704724890 396567395 118190395 679664022 718233300 753045045 568029004 15461239 287239936 757450946 196237778 670925545 321294018 556771081 733295866 333292164 117612432 964287777 454023467 803620839 135823645 669822244 795965728 565843098 706484905 959366689 3716231 600001575 767187814 866946426 625556757 648473118 776689358 149116443 339933202 97165614 255499394 76220192 186787908 661999635 185628894 206130536 563836270 339949079 161643525 104441926 894309826 539504124 187297925 226580232 284768157 941947156 775456012 321894203 292873159 800307672 383034051 477827503 365046594 405424112 915988300 626061316 959256256 406215568 990567914 711917066 828443535 441025654 240234692 857161223 131591314 571517662 492098180 990669204 729172433 746854721 66172651 357367543 673139932 915651046 782046612 961125950 827768893 529190890 971871797 208454881 503499809 239898999 889021112 520731722 309526087 954958346 248837373 921340465 589997440 836802239 954952043 502806265 136759621 640094051 812864739 162081931 131309305 119974053 435492252 777363340 914472412 158770146 489455557 525314129 866315038 11341534 28910603 305184894 157844107 387257589 192073258 966924433 187999705 893455720 303142773 110854114 316399258 892650490 982371343 567674561 709312769 621020224 678287763 916396463 654821208 910025710 379641982 632855749 459999800 539027892 164091531 793647434 550538845 784844413 715564478 402198911 17313674 991795921 585776579 151212948 582805650 316389239 232138273 222719969 618985952 177081295 648185005 223733377 67712485 808838448 32101879 481373933 121007036 461292922 896262220 549051540 856109297 603214591 240817190 151445088 829285740 772397852 46694963 918103029 679277829 877744522 407895101 791950700 422340126 626531569 554103250 586971419 544517298 127352547 498160233 227596623 73395734 363052544 206820564 427010565 821287675 74035284 204679127 949981011 866133743 904596023 735346320 524271822 428126792 124096944 720966827 570766244 599569208 432662322 768085815 781625697 612461679 538648911 381600257 634416863 957517477 215680012 314070301 835246517 246940980 491206439 989223287 348949809 172071948 777636175 586672614 681108592 899134470 408322208 443276203 815610994 55302770 452691866 307896020 735935997 419818088 84834133 546835231 986193131 124208936 61997513 135435156 813493284 7773984 455951063 758566748 469816126 32687560 821487341 128677806 560941589 455870533 622145221 546906682 923997838 817414016 960322768 26964442 961551215 248774905 735423448 12166404 781222005 859220459 866996137 885475479 117853376 777450167 694548235 575306678 230381654 759729277 512166867 497985155 246870094 478719933 83198244 866598963 496138376 531510493 709321034 5966047 936054063 2670963 235396269 756365651 359867325 745659469 607783647 970813088 57480214 164941891 841553408 126573502 802234063 305204049 878405990 671721212 120061559 64646280 105262579 999285312 326399758 183715097 221366981 303231340 788451438 911970304 639321671 767485334 823614017 101095279 392529862 960386266 680114832 558883824 800709026 680281451 900736846 79698222 844593602 509900037 610323937 142988272 691268435 817050112 747735672 493657215 234534262 755127706 994430175 67112092 790374891 787264203 38687579 82843839 529418421 676002898 275256804 311499166 918283863 647647725 824111366 384809494 865132611 601264784 787698432 740074268 954723983 367444870 828287539 549916439 486949912 432548472 577165062 363044854 131278088 465006534 447840379 243610445 961947587 909754129 415400000 631469189 943136503 322183128 357242996 951999733 400321650 759647055 498648681 465700457 756058782 85266766 472698515 21651492 343728005 345986555 606162807 227599817 715494679 703499600 350198798 67566751 554660570 43134609 790144788 646534056 73150067 532434285 801993027 132639812 248548409 623982211 665495393 417074809 870063266 369420134 191860940 135727938 349663185 845170819 327572952 929900193 602945075 982562200 648367866 422352124 396407058 968359073 737623986 845584940 458699509 734401120 990452798 689288713 161659035 148280946 447186360 930147423 68410243 175057503 499665111 135272691 611236162 902824951 747607289 89240227 457584628 810889437 456578939 293005914 782763242 868537871 919050384 826487865 965506303 185028687 466119588 754550993 852693662 939237241 410946668 159802074 138999196 639184726 912617710 184340739 134822193 234511838 347594289 4942673 507966223 949519865 402657642 991898410 617018550 302468806 703759429 96785420 125931766 53630591 864896876 452815121 505162548 964698001 217555866 873685451 53226449 360193903 876107569 80304326 390073698 716788264 856996378 887866376 293749656 144308973 107206792 850551057 956443638 236542854 370667809 151762725 684085479 177919545 463940319 605144150 840528257 890916502 910842168 415953359 615880175 447968683 865169658 413327488 321419524 388665365 387164158 769174962 270850468 241473596 325649578 14886207 898131154 640331179 994631541 771756212 148072909 927594351 553913072 711454035 865095043 392488034 795043582 4732163 751554062 896287510 135782441 470837654 552137658 892975639 800841431 223888895 320329091 311091126 112864414 123850189 144815584 572706695 660488289 995834394 633371345 90302934 225109219 800456812 302388381 833694147 967993079 826511803 575393663 409354648 614909882 982989303 259933923 681680392 705741134 448460838 433576737 32300448 989042495 364383447 762866240 247314650 444664918 94608696 812453854 976267167 936440082 537798485 478493836 437400814 678554434 166562681 610934357 345359660 333110274 739152314 951875598 390199744 280566826 693204564 729158278 287882271 418830727 696515612 637066369 883472985 466940584 263144451 4523964 423153409 768544089 836054502 722204710 11863658 245714802 419225306 484783952 625850812 276287327 973577231 671560327 844803577 172653679 108011774 5286600 779928724 832278715 734505279 477063797 494714153 297044006 799979651 754533213 665038174 577225706 851302835 90373284 148033733 873969510 113334997 715518143 65004490 85389623 360908152 11203015 326892242 315448258 736880731 962657660 606962218 808720555 846863979 636327383 370370638 940424495 746112530 299991986 889398744 89066550 201700741 23593011 296650043 591030914 629132470 947749547 684411080 606828269 455238962 954080066 45580312 642780485 293886066 499518787 980633441 941714708 220107941 180048529 318373601 247300144 50736711 195414126 837142769 511128283 299313657 436585643 429707650 146733651 195674686 914469181 900813599 302132759 372123971 324723291 58393396 418385898 398223360 23425727 224945744 81089718 869533060 230586449 584692958 637812531 580195626 640632682 153809342 400176853 43428383 548725354 508379705 171512674 961341112 856982069 383301131 535264974 486829846 734511678 628029026 659576072 670789822 49667564 256965915 504942881 885447823 464829330 843845781 528839330 171333797 590945446 191696651 325622549 430485323 748821921 327114069 368306904 986663871 147383674 436191745 527018861 994582388 60756680 59163353 699101827 149904720 360253532 713106905 720052055 232276595 419016618 741614956 746177021 434711979 699441291 99930349 386410516 10158692 138077880 4264502 57357555 768347996 686786902 279889579 967500268 329227026 846431943 160313251 12005660 712216288 579655189 857467899 385083782 730796858 693281450 583991328 325883717 847881029 834979300 402058517 387008644 496654402 586676698 845435310 928481964 945853934 122415842 544202649 598456526 901509206 492111939 528893107 756468048 935480416 77396482 145929500 73395921 305582812 438175653 363015174 610403833 110667802 97444802 889531636 580205027 594383623 487892719 805699660 747114291 85104191 908312636 418788914 714387668 316730926 746936166 961908769 494383872 138756953 604892084 524305821 644793994 573751794 575264267 344510557 519615081 893684432 92178141 14823261 626229174 249661672 158015316 746690770 655575897 802645376 397855364 29925070 425139063 331888783 552049031 624514837 685820373 695522028 657918079 758460281 121423331 538348066 35891227 283656310 395229802 414252864 354390074 719811108 428231408 829639361 65863679 990735132 798126013 13431375 475856895 877286191 232537940 751882672 597514622 635421122 790752181 842390096 224315573 996112592 504463965 669171506 786585357 834419672 258415738 525050858 134236437 241529164 412082083 865351596 79583710 168261420 760971005 772937295 444254403 563306649 92125590 858361523 925672603 959273376 405219033 94693769 409020421 638485211 140363924 193631643 273800500 456752739 467439108 996915796 834457871 815740804 598567243 533862030 600895443 468229670 161809130 981399230 393190525 318494693 678103526 390427294 961643189 865632511 993710586 411398805 128388280 965774513 466626434 360810133 724511108 896229195 31283770 57249785 920349062 107593677 261212711 810548202 324485623 846286791 243709860 829941207 829134836 988477654 805454053 83868878 227363032 102481170 579687844 187942678 628447503 814444292 189638700 832973869 745319183 12570234 831061919 694121624 700535611 648016083 936284400 642970974 312769620 21187033 680016298 298473965 652485477 795295221 436583141 477226110 191234447 312810476 258097522 636697779 26124073 362432450 77247215 678652880 812359211 150715663 206776132 677350873 495883250 888693628 607335051 885813688 310858380 605927727 544986475 833140677 962932547 24484836 860285717 164556883 292389921 729534634 265512020 821615283 617425588 923489077 641978485 863180277 373580281 367152911 999269050 834052873 84027934 580486481 627528645 169897746 704053150 360988457 491886962 22143286 45333311 442130941 893409578 723824125 764986401 20801539 293648557 642745726 405950844 830543959 127774447 464809220 232025321 826913587 94246515 387527775 239076571 23476216 975790500 581777599 520891040 948657892 758069007 978885187 754232872 383865134 415448613 592033014 655650254 477367163 299703267 454134518 784084306 602684648 502613452 226654616 761448567 926071112 768607704 709702214 862827497 791166071 836728149 713376828 43168107 998017390 984907290 247541729 185039583 144873374 270942252 451943159 67393193 425483769 212451400 621458341 901412644 780358166 49008701 494020668 441855892 942714654 235007689 747304756 186361812 149871845 910838315 109831603 121328595 188430597 86686705 591439526 121327209 921504678 419825931 866132086 520164277 6421646 748319650 653009408 460738755 200008787 503873428 602468821 917020098 740601401 58329706 999598935 19951382 124769503 61780173 803295827 773954255 601257207 441472322 135552311 710688285 703116967 759080313 801102377 290720103 68447669 17480897 77440004 210255162 184302520 664939427 221905278 707988458 610127622 537055722 654548156 519311594 355176466 918119017 949435681 439069886 926463978 847728743 399305061 283680257 181719415 242658285 905946852 533671118 994029655 786025984 460642133 386370579 373640252 344024512 58611898 576426251 10320378 280928962 275291482 521385507 769651807 580598870 99691452 542781679 608296497 253699246 450248442 435625675 435281733 434548418 988525935 344111203 471970223 633078209 667107993 429995830 450621447 20810411 206538781 688704681 639925867 2254858 171530645 236034922 310315962 583173243 225523629 867674483 949385686 979551299 727601951 815505045 71246128 874761348 409351757 84229862 391647751 63673225 288257022 893116082 115669958 253894465 302343110 471998734 895614486 283466156 972514791 408769477 180443318 374102663 402699243 86729628 138135985 701243543 612169827 210125529 116977621 946415752 335662245 856494984 737497186 55176182 209409574 884295058 208113540 970178665 754011400 565384525 354639714 97311953 826710053 489736322 353426678 189416610 535555600 843284855 112167110 754167380 720367925 982880663 195989350 323232597 902612892 802650506 550681643 421025511 506906384 777204747 65518162 439713718 116432801 183279259 370571195 17889939 122296754 832609461 235352483 292784276 441256245 554242379 444364251 784646428 92794871 550726741 336238279 315517887 204387725 24083337 245965685 820516253 811131161 489751792 636005435 697098555 653542416 621153712 27085983 862758299 772315304 355706715 903883696 945472375 494429192 950198229 823327402 631253712 788623969 598475192 64117765 647149778 266441211 247786238 780067843 303678861 617561405 571982695 530727049 842324901 65876293 17556766 592993264 569579274 954121963 581590219 476923135 593682282 796260645 246069206 139567438 464622940 686979456 848882229 581940336 804670973 246682264 543151221 579780027 727303189 413549536 990192196 613765463 93975352 166480118 53259948 695790616 27033548 109579677 622045202 210098353 881487465 697991523 429947795 317957852 89724018 779502587 730009867 357984477 804414530 190698565 779422727 946197337 502039842 590993132 434933571 765704366 925427123 78905291 798026985 711600065 700384609 682074648 21764274 194966856 440827049 295426946 723739672 617694073 559996997 547437937 681679576 810793637 274421485 852405118 923604245 541003147 687870149 146117630 112048974 31036903 765351490 202104557 203452249 163482874 208789560 699446947 314843267 179156408 392424848 13054837 705554011 506444257 877480088 690038382 643382923 525472731 504006809 775659758 377664072 333755602 735295903 955590034 303793605 299757675 841153051 881948777 192391563 963359131 750783812 921072419 883886561 70441365 339115871 642877163 459456117 481116202 614903331 115411417 218027165 280930652 189269041 589638225 853069244 549181817 589113314 615203261 224980266 41986433 133347733 313884206 643838450 300284624 251895594 428834148 791628775 456830494 606791582 234862199 664321199 462009916 373478134 36393908 481329957 281523279 36294649 97429212 282084797 322136255 304030839 764122138 840906194 159940704 913572004 709876988 806021522 483344159 126503354 759232789 247501295 604705662 638153604 847728864 864518714 918965778 848983391 555931642 368576363 943891083 69552931 864943606 597322848 350462848 736858515 428508462 298184141 369609814 543049077 277947421 577863376 135220480 570035819 231300357 823734207 969114165 260597402 736301830 23857598 418925059 473279367 899905617 276535947 115216093 550409191 566911918 767954108 298364096 331634909 787945719 815593318 193962956 407099541 267807758 925413463 833256350 754527323 775534423 699975946 444630739 68117655 287694608 725012074 725825349 81778525 842919400 144850400 295619592 486339629 314219556 324465355 941487936 745864319 538280693 39145772 399330350 977961275 181926233 759027454 729777165 524772439 92807459 517127419 903084825 313176569 801231736 484848155 85629778 553897286 377063323 305564360 367049524 604445033 483589273 528208006 334681999 887300122 369712867 470669222 113695671 135591585 153980923 269570272 335423744 679462582 354091713 346496899 336583435 175104489 913894311 50406774 86613211 850657131 689625375 849287710 852104246 112787286 79840519 113740535 555390372 708253448 269840637 893373858 50743647 716848602 982304944 92503557 848752555 579395432 623227685 574144386 321292048 838558665 896556297 110692357 814199513 406417814 243813699 137180040 822810908 438602809 532541791 44812165 948065639 286995079 923118572 98377638 139424097 531457355 33945263 172285228 56541419 831437446 552388985 195664444 721153276 93513768 185734105 872690045 899893418 782346156 903329016 221669000 100488321 719359653 555600320 571904652 413758753 586067565 318702805 487753733 601967127 507786379 763985601 793497944 758733322 738080724 150665430 991081175 965490114 168457517 70083216 2939946 828896648 339977262 516903387 223754596 772447688 715517486 168240283 476235430 52486113 225241043 494350803 181138064 14263875 737539751 427372749 446910220 855461749 297411787 862035746 335104922 155493809 103643071 539570155 503930454 660166137 889932433 728751110 440868040 945049954 987083960 698035822 702505682 605733521 136208556 878791231 267111428 625935157 310079962 350265209 819918321 727219526 382080636 626762957 488367138 200950618 539304374 527865262 344834257 322773512 328710420 354786431 570665947 94802515 297373668 600702929 379039624 798455547 78746585 185837417 459882495 717406697 601082747 315609719 265599450 862657177 144108255 339722815 865623043 331815146 164727621 805049363 860477612 805975444 392492829 83875643 873367109 549672043 463239740 66123065 791243396 64050155 277473709 116076683 413068164 466068025 375946947 878778810 168607726 743615504 126951204 249298657 822405882 670475059 997832273 705695517 273711519 210490297 928959992 870271754 647540572 571626381 73904218 470790306 999165557 369114173 67415426 736908442 741197010 954147149 384303489 480337010 5980826 335337785 445050204 888152210 570406861 368932786 337723472 443795995 700097476 442864252 592643200 751322835 584910426 430671910 290313443 270644999 712294820 966847401 719109652 496670936 73006372 412080515 666721101 168182731 608857538 416320964 630602044 55720985 29915331 432747720 378087554 114406241 763098112 979209818 107927493 214577272 686834431 952139786 112702903 242491846 333333973 559439245 645290632 713075339 803035943 749557769 689671651 433761475 843553037 125607773 182805814 862667821 662818510 780724747 636173030 438776307 211109997 823824576 804353126 266891986 102955347 161481330 274051325 315203416 299955717 89610265 758618088 546553604 580532183 569148600 419390134 846647579 859072755 286452269 980983233 757794793 504231268 814693478 788647956 140993476 935815141 940551582 156455224 921152843 779495749 378320769 634854998 614855195 555814587 478252229 132752798 89579588 667703221 650791542 453838176 131320317 933288748 167569046 923850913 993188464 498313678 419894958 465469774 188580170 931685355 233811717 798860275 937603343 721376383 931881310 48416044 609256479 861944359 739833250 713392531 787278721 174561919 101131859 7797800 813286147 656155505 814642420 906565287 775928249 227076937 852007056 240730450 789522160 330752091 357079506 703832947 723751241 101095263 800492438 521552703 273094494 96056324 820395354 751795563 857383203 997750271 927015078 873123201 611733200 758024602 42254266 228551948 186254562 778798788 259211498 467462325 499764929 733370830 605544725 522820381 428509567 477540569 748765849 533565411 568718754 17173908 673042731 308026079 525050326 378410736 208347505 922555597 265990508 447581300 117249480 360065847 67555339 195546186 629814367 630178205 143655204 730423389 809911984 461011466 796551832 50067210 641869618 926483037 115374013 538154628 303461539 461527483 948696693 386267878 22731944 594743921 548268274 38913578 926345642 169004936 418530191 431185449 551088289 481807959 374600755 521536422 605900743 956699872 874112980 135375470 878235070 105997591 30466482 480994875 594945065 447541527 385894749 52658252 576228945 779382885 502532578 605385456 994501607 77903260 581970255 936595174 245256549 194939131 299998171 751530102 69083880 925575121 619273686 111896832 455204514 191023020 734152246 549812089 497092817 820280784 59437749 823565112 351527870 721312615 414102400 402909363 480215413 366378239 217606824 467559504 951581744 906299098 27855620 853926402 636673904 979615162 656126480 921180491 72448812 395911031 645856983 236992788 807154741 591429797 235966533 455528591 809278433 725142754 81334154 587512427 468091390 974848007 768374586 702917796 173306511 775504136 512974586 488460328 505365906 854894153 553176875 430009464 664769249 650454839 718296615 940244394 479337043 987093490 229745741 25556801 18880256 43297024 401763060 415186199 416883847 297217749 468264253 974214310 290080148 520715399 836077670 223987775 329753124 458087683 785602871 720139259 578671852 579380001 318737900 337569051 269431822 937770631 643876647 340022809 953817023 453786860 29686131 860588869 694417431 234368742 199979920 768655946 248090827 11963661 21706335 579335213 485140849 163744978 908070369 239982353 860988702 564725022 901472597 440183454 543893519 192488768 465231746 638462540 190056187 509133697 836805152 355857048 638865978 784460389 423297936 262000942 195137881 806746001 307053706 588466440 69610514 356990908 673990102 498628811 615127198 994538063 495131647 404917354 741044038 468587499 557899327 935562789 780326497 510581966 828906432 374405176 534009711 209850068 438087289 11045693 963169440 724764025 169651979 36285975 457059446 222383848 971468022 660087192 906104341 466697210 468804000 314324461 527557278 947427740 713521171 576238222 856290880 181088403 627681890 91089597 810487287 373129318 540040360 950855366 715987100 288033108 861707856 856794303 154249581 215707112 348541446 234953686 598908712 418819036 8909188 276572503 296302880 606305787 6438670 750343331 985409400 15241017 542429656 780779285 821632283 957501489 291060022 192085539 829309450 516963476 329497811 327997955 158897692 287349053 796348772 578508025 436176941 324824804 26613136 70988158 461392756 490743775 693802980 97483168 782941427 593420024 1206374 461764125 823800595 211479731 804890199 718896107 6468660 321071778 951202045 889262263 861772124 519492628 646513946 472505888 24406642 199686741 781221742 868264758 427811761 739357662 882596738 359742289 433107009 14375684 542570283 73279603 920258795 204726847 733542671 60576205 622670324 945110618 38160319 542298623 278872364 430518502 64769885 861064578 570844483 985504764 574030526 430162434 125455951 894419586 443501159 681507700 252770226 283290605 778630705 18257888 115836408 815745145 413922534 365618796 548676901 811933652 321235506 890790578 699147505 428621599 969275097 592156019 721512982 375887216 308186699 51503435 64523917 839759099 309419863 307821620 898648739 903359100 483340530 99359794 943799031 304889228 392237957 382599301 5806029 232688230 430000908 537339283 64138614 191772771 339597366 253047172 467226887 477703236 387784892 963186704 383192204 944294941 605218943 742010233 563375165 135050940 630241226 698911927 436585841 628795429 912075635 975468783 453537396 21854361 264843729 586802991 400753840 265255879 831561302 556292278 368819916 401396627 240789093 342596372 461511666 236562347 360786366 404169813 889068960 205777504 241435849 567479427 971611163 838269732 863473235 640538785 217842990 466666494 539068100 809824165 768396082 894463758 450354495 239553523 983177594 418416989 947416398 631829040 185183578 568328005 106935679 916965143 617314643 55795102 48961021 865680257 938798267 848827546 357405661 93377010 163443095 984787920 961343614 975405944 968283854 530564100 103485039 22136550 883402405 879532244 423001267 379650720 15910232 928262951 93283739 762636656 174120982 948186685 621583336 410952960 264268546 352334470 926772859 366360406 950136876 231005092 13245728 500252518 622655904 469718851 320505689 152853074 732488576 489658369 177741029 38955876 690065730 656837031 76143353 519663346 910091828 836868205 519931655 428494371 954932936 635151940 895161201 757040562 352499031 921092385 620481548 707033763 892229155 936941020 969228077 957253487 126892362 567660355 894405970 94309482 380094727 868625439 877763787 6909182 366544792 676322940 891019047 776004582 894924918 79009470 447341684 376563481 166773327 379201790 550652791 116205832 396010057 342719020 138385025 736070138 327748687 43262935 677945977 90575609 150965905 381730910 967816581 501263349 972459876 561254136 602978620 429118694 817505240 293485813 688015931 428336405 847001611 562682697 697070590 985084021 276097509 427427081 327307386 929900675 899510603 102689431 265073120 358574020 985904152 788678182 270696569 198278020 731072747 703590833 329446137 773501840 137704669 117786174 481719129 421409659 207312441 667990520 278274566 890740688 52623405 5867840 703127672 141678037 606797086 301514492 184327164 555822738 890422520 472848313 357450064 79717928 869383596 198930108 19138046 660200708 391729540 607296199 760889723 327521179 977409129 853613720 423234591 779632721 479895322 84419595 923618554 301060672 999060145 577373611 130856826 650475887 650808371 260868507 934384879 209114863 756731874 772575919 714266642 433195540 66980967 902366534 842313187 977632136 278335820 618376417 472507886 58137608 542820999 131025947 777838609 859450025 118309704 813043751 935028689 88310561 847685097 151887864 689621381 950692189 169354351 851887960 972359544 988503854 126842409 584129172 376715418 879454255 846473924 82474493 629921862 64214109 914463687 951758221 631592600 517427364 216695653 439878193 68336636 881169464 178348764 28619485 542501128 514180742 410035580 268743222 43195686 472049532 50169739 88596943 784009690 177636774 418331746 812690400 17940959 856968920 678127428 7737732 316593925 383523808 975497539 165816689 115165507 908670486 54273492 655790457 840143727 520608670 26140340 195315233 1066795 959230294 756277244 980348490 854739262 505627087 231333413 50107941 160722320 476505130 276591741 472382516 935588631 435788284 269563748 569630184 633513842 352135877 694527081 237441191 584733085 719432929 520618299 665773472 689169011 626090151 37911754 437937077 483535689 391014927 313509253 265591459 334148444 696481418 998380926 520970173 631937183 461523031 762800718 704972122 815928882 422408018 327497584 379078010 543231618 199244139 898779321 420644043 381808616 466538744 923912179 310321775 571498082 50965122 149281289 917020311 266161980 867767943 47827926 95521026 686182819 52749145 4966408 194154626 64401423 567041774 69643769 456534742 706476910 306443854 432389764 496448433 497584751 610375310 788208519 107103928 61126054 314774952 726251687 627960653 231305404 205168022 451528934 452352232 295603235 904069401 381061142 711311343 387707654 97261133 868860302 777386948 489344520 675779772 196220200 647441385 800600015 299057704 625471269 160046534 331757155 83765674 162761983 934484819 845712943 326130202 687577012 171058678 996188304 66030521 166194511 396604075 282722220 461688883 756501592 885310210 640169318 251917880 786321662 398462432 541969606 645863597 542984919 650215618 930324616 117453243 122170325 284415425 788392439 483861389 86815334 99246688 487736531 690550156 355889951 83377775 903841524 662090787 338114282 730501839 693490749 430772121 971718098 877157985 114101645 466861315 805965445 711669112 725853504 6903778 435981128 72447291 998795424 404581120 752509308 438170584 411944401 996409044 664674826 664614095 902578955 701529626 991103812 503962469 317451511 477874629 387702233 272976705 227291141 501394201 160671045 219847219 662732210 702213090 435601751 472872396 229930392 738374089 670964582 490096217 723553856 880550874 345253047 804163680 494624474 819426458 346057288 337312792 236045868 336918897 294974391 375078052 750792087 336396117 127714034 418973022 625238378 256590999 833763405 904600937 577705376 809114255 439834534 329019285 243287481 822311636 94904718 716815796 555175687 319537402 491133474 586907563 279263492 141423335 637096989 852413341 143621432 290291865 483640058 806475412 846375877 838814728 290881181 318320506 393655547 626570298 415855784 142682391 763105186 867579031 540404526 991163725 933633375 564291627 90330041 571826607 706274489 655798177 499084805 118209847 675650577 970518498 731406527 123371753 791493683 686469521 256280326 478947969 849855450 393105905 271027869 714742187 305810016 876004880 602454583 40766936 765488998 938424608 165857989 348868366 413962951 508749959 377810019 416475503 752962253 294148983 737647131 336300013 158898101 841759827 755779504 882980433 824882795 854681311 424297632 365289651 785003734 373067738 700463968 560043416 466988257 122820735 518580182 855176355 146724232 427189085 797277200 544497224 829546204 224970275 689320977 509968217 654979063 129649087 919638393 142045525 431838055 976133385 826051245 901074168 157236040 733281089 690091547 57146649 512172186 742424480 79203874 830138136 605755949 745406525 888482200 940659785 936095333 876815143 97864160 607051943 687511116 45034568 644939891 71857719 579249416 806797191 647124771 38051906 977166871 951347036 777787712 945107178 590046300 694954457 641402144 535324521 670874816 267816663 873365360 591982384 865869642 764172360 85723241 442410630 997930332 27277091 956583110 948816028 383713102 327837482 848616423 932892221 186712888 696105396 71866329 910001216 563043054 279483243 270628973 946434857 143870157 532680016 986662665 355097415 957671319 900299145 757717086 404460420 167208638 12132512 611678637 633901410 156352019 935210460 380697882 909818660 339712790 35874435 901702460 955344673 309761620 94358845 319989782 207270429 390169188 418218410 451383055 969531326 24639952 589037472 542217623 242963857 470397382 450993831 708423012 838749927 786827441 708833490 289834757 12465125 908831166 244106908 374785026 760902318 595920621 472670676 908167154 318004460 728634506 175776916 450049480 732202309 683330993 312921084 773521835 837225016 773952754 468217915 668743350 28215271 717782322 681657146 692850766 651234766 662493116 613596044 294377623 325498782 554161189 934549100 625090309 892672091 920542541 68596015 903732581 165757843 695693270 896630256 792224100 414627128 178581076 357234347 453251926 747184940 386842105 89084291 742679662 330854024 370260588 539987819 7363910 131375896 409855572 853270211 736565252 136544365 992524743 35151721 835347632 818361392 737711267 844417661 799260791 4490740 948894317 338102607 591661759 16310060 947845720 205760955 686151902 555895108 426445052 537906475 936355535 209851676 292910807 48147901 823619085 676900690 435519475 65412372 732613603 785869953 434311166 107330397 803821343 762824445 416923511 84544681 30075292 505627720 222638156 881595629 865950024 343354183 385783668 783751253 304389126 304419810 30171284 956285094 601518878 697388553 967975248 809639043 30355541 220013841 472249676 470592630 817601873 860401973 215604293 509680321 678062482 273470196 898870372 127057339 693734398 17136901 361509617 782327348 351897507 620193274 823486522 383006952 541966034 651766104 218677810 640085497 831353449 957922389 613398988 852192256 988287194 776161360 500264589 121256369 489559417 869809849 409917223 4530042 979746654 304119620 344262018 376150424 650351805 38199666 516353304 205583903 278931130 949212939 904795224 472444456 64959367 87111941 662323961 213204705 916398098 62448 215655837 876857352 399880331 648699151 533950823 618004326 196706980 693309133 470661996 985389262 389292171 663654979 464265062 818516905 600140125 321018407 18428904 825978041 588420975 135304650 743039155 978230899 398608085 119853107 572256878 951364817 104377317 17323283 147583377 3663505 164869456 131263876 170122675 474449797 968180634 734870176 37397206 55825517 944838449 966680320 223809079 183527791 994348610 275830087 18655417 961857087 985407127 13937107 555659356 943737312 19049278 250976649 313618240 812232995 506429837 125030882 794652751 167380652 735972157 178401756 357215405 692674035 180538628 878309577 345227319 106339231 982197082 676984379 736463665 685040322 210323688 661630077 44506962 414771596 934474186 246490035 652730215 218851058 257198232 354386105 48220842 301147245 120275291 120809363 118263984 400280097 205222537 868950778 463975270 957836089 143153940 889494559 522245996 549660580 185354228 756288906 961275758 261456677 280997569 634057222 776261169 634473925 248089419 398120188 594730413 956909643 130059843 753108811 325096435 501657340 140753148 919313991 727611070 182108194 671264159 963913975 656797431 944642888 693865539 420534171 979067796 791990060 880033254 920884464 650513885 455549474 579756727 521871559 577983281 173143660 504782141 105231564 11784276 980527907 665104817 990238188 597600324 518129358 257890465 141264791 850998689 201378993 305286515 251645014 877183727 232717829 118136734 90745803 716027956 154993385 315024000 484054095 577442094 688567260 226565348 201642956 983770218 524815301 811747419 26690025 501158951 572993494 668148074 570042872 760588326 520040978 276592777 933749200 201818126 268412548 941850507 217924167 665046866 457933458 321601122 17292566 367947029 28316699 64591651 453474007 852468572 246503890 869340931 925229302 639664132 443662834 954519137 893999227 66931184 872941067 962585610 546305129 123895857 181466388 864265021 145894771 857695216 844806212 316701221 241658271 539419403 773712204 811692841 73759168 693072729 814594269 450277791 267085307 886693613 660218093 787706695 754243462 391967187 466647927 782489038 62766439 412856443 544616084 848743086 857962691 786640702 492613479 961230138 613068937 628606554 472719971 261697649 591419654 163040797 485606143 850701249 803542507 460824746 331606644 591179135 401660556 504870348 705812773 767115042 661447120 505634480 588064823 338746682 454669224 791424734 935063732 837712281 797439463 994906590 734290223 564891546 295313373 760254148 848908886 102306714 40641234 206410500 204710358 574743452 779616472 212972621 617577441 996838286 517907233 299323110 762383312 521174794 305829110 92861032 548253867 590642434 962793416 899342838 793579191 52184114 758401304 99753769 588633051 986745231 379043564 198829493 415668229 631547527 840356209 605350062 395193209 952001321 62677434 151147764 104383219 599314480 651367250 4343923 91096492 393300858 426993897 603435458 583295447 97428573 431575058 449052905 948353724 605740479 230853886 674582170 904797690 714452840 60297910 196572911 81136566 747676735 576029565 467354488 11731723 762947175 535148329 557965244 738278969 672235777 874119120 150169930 179970829 330489646 568782407 158286660 818312491 245128561 729333129 707690670 43262744 543477413 692658761 50311942 454030560 762302925 353961013 412088125 841497891 437185281 122118445 498934937 675789794 995424665 190693989 421579966 250963912 954431273 172350888 243605667 621023779 350362419 881702074 326307798 198304343 266502124 118837119 448006963 706550265 792882455 509232812 174262948 422644738 330284453 354603113 495226920 579118937 777702148 876291829 52742974 328200607 410917011 817396351 645995321 358216306 646393305 939653457 867689952 760040268 124769871 158651582 489889614 52895629 613453695 386991487 794526008 8830087 862939575 630895608 748358254 468000005 249832372 614087465 73724521 843413023 966439631 933387092 567957894 748935466 249511707 632962678 84279504 333761083 175651691 153948805 908882628 772514888 637417754 996744645 85607074 570011143 503413792 38286908 684712402 141037378 655451350 371139042 397381844 708018366 288150363 350545111 878168178 157344687 950359922 105979808 116839798 957123923 953750842 358480773 274604414 871333211 167221496 390976211 773506331 293880815 876188223 123829117 789987939 32621310 906615494 108458505 648323800 561646210 300678078 613090228 443621756 765126868 393102807 301658582 349848065 413508841 879372310 9381653 543499321 853681062 649889496 804916994 942246495 156604319 271534199 487365507 419539874 624740377 113286955 861644004 223132045 455305986 228400774 626381246 12136668 284980282 852907558 951449379 294373269 65009887 692410405 849750579 664918450 397894560 979917407 716049069 950058519 286292800 298860689 135852131 101229992 156886009 770541459 559619065 669810964 598908401 967535642 828028399 203045092 531773062 966520477 331421589 660632571 584680220 462544451 818545646 549185849 485162901 775297006 268137308 579866158 398299777 124123620 144320917 818219182 98277718 231762637 315091466 984672359 650240654 267022628 560854855 694473571 903865900 550497777 900593445 227775422 886794863 207327579 998264666 388500228 390633325 680954548 140198662 483692738 849454728 434857579 75639562 513971672 926919227 725128249 878636518 960142138 914392194 126028991 939547306 278824851 748213476 540542413 775749947 809950469 99726293 983026851 999354682 518229395 78883923 516440765 584629798 752313533 711735961 940456247 955937035 391487336 994707675 418700395 577787700 776168988 389380446 215537928 653059111 248211743 906462683 940519064 142057980 319268424 578642579 864072648 602879163 245533936 513978191 229827046 982130191 442540659 532352829 369794140 328520388 374702256 38567169 644527020 615914063 800611149 859854777 384656231 16154609 962256528 862769869 850847697 116016116 86280396 31482613 514170072 982438214 840084761 377311869 547723064 427418789 453852272 62381934 989995288 149644476 24356352 802252711 547145795 118318260 328228161 61392133 989761125 976161211 466154524 607517437 880175781 323539139 500910978 481801623 748984595 674739661 185233946 607622038 910987764 543609173 698578876 73238621 452437242 892934897 634683531 325570919 494214484 870014490 526822201 622680136 893252724 748149057 525132354 315841429 771844253 369858691 166177445 653866994 253111443 353282290 227070942 82042284 573326908 798331026 339596363 347555794 886181584 860837813 251166116 744226867 44819271 152782321 212599522 515352046 116111849 710959029 877618028 363792835 639590874 717095810 268390632 352725733 98722105 645964224 912018657 892948047 142200521 717738173 815130373 65668566 371454926 803357514 834705013 365424488 954883364 204584778 534149738 405318051 351383416 391839 553273310 154167064 879450010 957000485 286858010 325813768 187254559 126374658 282376902 814745624 754019050 758185836 408911831 643364758 631580855 519499223 121677489 331215577 664070909 280452248 82352531 190973487 523554557 555818570 919286826 159166790 993903532 805451798 769727811 567284475 652433046 227041289 679614247 663478829 705397910 397187254 461831911 941576806 975898792 863192116 672453205 226317144 493356296 329777872 658833976 677089062 32208278 932226254 356461336 646540834 700685124 943965327 504931310 955812046 381253453 99849319 264233448 263855871 493889548 804700658 396695608 62685671 620729337 25043477 185569697 896780859 506833916 243177684 887686503 654855055 629953830 346599871 17544925 41162257 167394620 723167129 906967924 227217503 60669198 563109232 278573315 320491627 435461708 969920752 979842811 193146458 727058600 520791549 66915229 991877956 625848360 507327969 988764423 853903392 113972591 111292403 113031498 940098600 157320093 895459485 935071223 203359396 170236062 708491522 314117325 379128643 105664936 416371591 622573990 18404229 542918195 615091216 195653363 767766276 281560950 458129705 111885392 686791579 931020386 903533768 885855743 546934560 213029649 212897196 639539528 743540080 293330862 272169291 835044552 278000527 955145941 961822649 153292721 647615719 55697571 426832169 38729320 600527349 420863765 903069493 761146345 645108740 956345339 765564708 185471957 600316241 102828121 803148247 266678974 122475025 775816665 609441596 185103613 470871442 480069453 659450318 165536246 266537614 784280395 178944652 654266923 247272861 262298989 738529683 44280666 515270685 686251808 596494176 550717940 126789893 605205589 982744466 666583378 651253212 404227676 926850459 18086147 938714024 374507867 881939929 568231122 242716873 739687504 333372843 963287874 4545818 534166833 29514762 460783907 148004333 688623229 367599882 344148868 25712656 784641767 372682878 887245805 463921201 62092925 937130864 441945792 739800855 366171302 782509765 380793066 209231726 665156651 823003968 742851650 605646434 195014784 619228891 562216477 177149280 392931196 315930010 74361686 894989608 387745958 470406492 103373996 734624990 209314031 931535377 573659349 224141524 156228681 547729134 968574375 145109475 950197486 786338859 351394674 360350761 931639092 697072497 633141278 7957837 773961993 872994149 616051075 954164815 903407879 897540577 434691134 233740075 544887161 688179753 984177823 923459043 865453052 397246471 462593791 123885013 598519970 477346431 736270475 887633508 637723370 948704121 387035238 466585537 48293712 514658648 941941230 820208083 672374850 875673942 543018518 283211310 429825920 985490493 314705734 985129303 10132517 69876388 405441301 687165855 869605351 502323100 915881431 208730410 167728012 861078123 31666872 709640986 300134996 625787336 791837254 850723880 798348300 967070523 207750177 377753342 408358344 338511794 865936848 369927661 70337024 101009872 884928211 679074179 567736664 375593876 981056521 696174004 903237302 445303382 115647936 413197894 517518222 908760695 151210796 288390557 860757034 411100671 248705688 881293446 19380454 154592048 152063635 629336193 595438793 444804850 251046452 368698860 855271357 559032497 201049401 771758611 584287521 713579273 355757057 640191884 978750281 844762861 893665655 811073522 916681912 129284320 466944912 762461914 800323780 348952280 924562567 542186435 442214876 443043593 290651067 999348163 914449684 245928656 825640231 249265532 401577650 459238975 799485823 590995400 388022681 614024418 54788637 995375318 14489826 417494254 597358429 879808056 938004257 632258127 418808964 109286773 673145779 627968573 713155970 59628436 224959408 839456492 208030103 212592919 970225056 277531604 222347897 157853876 564945140 358868367 193630653 975358188 488969627 346227235 504403510 24375247 534941380 672282249 626204309 567408016 49292705 744713290 163079817 679360268 15525139 294890994 691188310 447538900 562087816 127419122 188386497 986039887 764640063 738438071 314264766 804449609 306617077 495322475 976353818 439848834 693373564 307536734 2323426 568312589 921087265 846824845 614009702 132032998 328329471 158648390 712285972 609571615 17382232 616777093 532349807 585736726 559969161 107892224 85852667 476878412 191865752 904912270 333270489 351291145 66320808 446553731 8065658 651175205 447961811 561819190 201246187 99981843 165921188 570864114 241956942 680004282 476512973 214499758 103506070 280055419 65174473 297738514 298425291 96154542 295333089 990314078 810076719 35210020 359809040 837134698 739438614 527756118 467128366 38645611 821472300 777706389 573775856 761565652 700502686 631709683 222338447 129177411 265355714 396053065 423815576 249362957 346299509 636760415 453645110 691002813 261053552 532813642 945055672 75580606 611525184 272166324 846953610 290494075 982292130 519274747 875955657 572356668 474606346 502530325 172552089 739790792 502425442 304512559 409311287 954953026 130901858 358973406 909081178 413893670 429582863 310903250 103183476 609533779 370470336 975226652 566633971 242743832 839832989 403127121 10596820 290405291 68676828 316632457 311924715 835337284 682535292 170473672 926122387 69146197 460627629 993333853 940652506 163611719 109562938 918169782 841320368 938492268 6030957 381177867 643785342 263686442 114073851 39115093 422960332 110579591 367348409 415141449 124563200 368985493 984908769 793831873 196011286 167517820 61707428 260721255 714863008 762507779 625551917 569988793 126807626 843765341 344993032 527045671 55212187 217142387 370252219 120975396 279324202 229714996 399786501 876689104 930081118 654942394 762562329 918244220 135061520 427437531 655001148 181965868 933483796 976520944 79145688 433859587 356666662 939691017 29471486 570628673 185932258 838729509 628104591 752652514 668051522 255203774 356698404 490995738 488127049 849682981 238687823 248001157 871315899 731400082 813894074 444102485 56393634 754441074 883935348 224719729 171614879 198330433 711543609 321614433 907841182 46094046 663370970 601094292 717752190 41441137 589622910 945268716 246795531 74323447 974758362 186296485 204972230 32056384 424624745 488553573 565821077 660175533 45971431 811437271 63080615 484052827 65233972 700132522 519891039 104842084 290271340 968666174 549327569 981717591 338231051 217071446 718291090 301347345 997849631 125248085 43662504 524935007 602170522 237005950 840989439 729563455 193674916 517241879 704182227 151892697 92439648 233455069 734954133 499409708 38139102 711582497 176070179 962145678 776579607 718436 52816090 372829986 426153847 449749550 216153560 907618823 679812843 629767337 415102239 281687201 609128213 358118216 533060810 755005869 154543456 466657831 234304941 989128494 50098579 464427865 67849537 481427123 324753242 105787131 209960432 40458402 499436687 447892782 57682917 531551110 54203561 672435280 637366117 247857932 262839895 572664123 20441527 905475919 262322276 954995416 894001768 382044422 988498012 172946820 477440436 593656465 614072027 517949442 156246873 1204215 184011945 598089510 415888418 9847906 400804154 72350867 510160329 148391149 705914051 777390279 953129560 31352303 442831288 975765369 933030467 159989323 606586553 791414979 230329059 973748832 535129541 610440010 632982253 723567769 536453506 526206763 428640241 584081569 794540604 887365152 55775321 22966427 953988651 925674464 655109753 606838091 808202218 577531413 950870289 822609787 589567372 489509156 184980357 264416693 831923382 15029992 95703784 85191978 251974788 950475511 630443800 941201456 532380085 117405725 691830744 502356263 658301567 212874841 487561797 651485941 112524049 351599673 165791882 480264849 123585566 566518801 56503548 936244036 693336795 668043087 745434741 699751203 891155364 492514981 55352540 245756396 93684866 658471279 1691793 996011613 805676540 693635845 503388262 406265081 283395699 74067622 416831894 12320341 638096345 181730338 472913160 83396674 379987279 315904061 727333208 438862868 707166298 176345375 429317831 923102425 154310938 722234817 910749493 967263319 584361641 629033308 368646125 246591682 692788534 643470847 726035330 85621631 485152399 261461798 980248808 788127352 299500013 545221225 872394896 230842894 440935501 833107709 911717157 377632732 307902381 785099107 489823846 358970823 86015625 198811997 628798818 845737468 497279586 584175968 807572449 218767545 647747934 711458466 817703051 13432972 570498268 73042668 782589627 518248855 583961849 436252288 396713957 846431397 991128162 370004678 817325873 346956852 699846102 477416720 457189936 706392124 544732443 306315097 579889253 602831340 262979336 929995902 707240606 322923935 326552056 247638897 562966985 926804068 164831697 539200885 938690659 267656707 847923410 112496728 889063787 734237422 219069489 179963136 40546495 995894105 564932878 612376988 477418785 697352189 337961191 621106116 542912037 818490491 379027307 496209378 974558015 379728380 504119974 290359591 32737799 136245669 263228158 411151024 406848879 538753238 353714038 483873935 662028244 666869856 854866995 99271971 185625 753576248 720517175 523105226 812099828 44651991 214991401 863119620 959278497 986269495 695385875 820289654 370129696 204242234 972284970 185866615 963586963 440874901 683018944 699996839 637169792 407928941 905519650 229862836 254205613 235370342 194352700 94440255 122769333 230732787 534655915 132397395 65493780 918009485 342408295 498720692 377983407 838112653 986180289 912796721 314683258 794056486 412770750 582048401 49594240 910289838 951485669 350192796 117908459 492419900 261660259 776506539 446756452 600197450 833960474 848402084 857053247 471823860 303763827 961207460 462886864 812715074 225109539 966484271 446498116 268414096 628566395 732770938 278759524 955913890 119173642 832828771 939670398 961618026 413165690 584505460 288203361 22213387 625531778 710422585 172808818 407211351 944050073 531618851 687305099 628449157 60746764 166104960 260656268 536775986 611966512 113117288 177363157 28744007 666335787 794559037 39395132 707262160 469879257 253984239 759886797 206063387 817511500 142335710 383359855 940504171 918765739 816091070 215094907 580504074 101615536 81257668 39896013 337398648 386405911 446727799 887532417 829662725 906065036 623991073 403873291 916274286 365001354 843028844 540960144 90555110 194458505 59906273 239424475 470405492 386116879 943080561 712072297 477392939 735503292 353114433 806891990 460706386 193017981 468301907 242721690 748003711 511059674 345143441 740065469 274862274 806523788 220466334 244373325 517346825 253214265 140746811 97087187 773869280 272569492 503053665 137051931 655650542 65164907 484984720 172689302 833700494 229676477 704785730 845648883 846639889 432333352 588863781 690784819 50691704 769640089 891361097 393249610 41160509 574568938 116935273 254438258 830219682 388729592 642686714 176400483 527673803 938247682 531091775 94864577 284278055 953077925 869514493 808251607 601558116 728724440 295826861 904539648 207934476 133644663 761875985 735734501 593055278 825340761 287595536 858002178 201606209 281076514 419978471 690346890 36185653 963236649 654074991 82372343 707887067 460373683 563212982 666725333 470622188 257168478 165065169 71596267 495066589 403436838 984902482 29732750 5714334 687422591 98126398 624912577 164662701 425216282 110526518 68917779 961856757 722238810 981345799 966052852 434454035 384163051 887652433 638578839 933888788 482841624 113117452 409569739 132249900 492438539 115781224 222672936 929048695 374948698 530674359 785866246 407706334 143213865 340410628 667390431 631480271 84943556 507457506 702233965 383224680 30516916 519386551 172528071 242036748 81427748 923148255 448173583 192112200 287676751 28484014 982703071 345627159 835402274 504248273 715055000 493227142 195029450 533635669 316632567 249014765 557325727 61283242 431598597 109602261 640414489 896804644 193566420 813340542 267066690 292756997 101945527 797347512 376683257 973289673 532339642 995433870 789708756 194387753 703506095 889819861 519047952 605873702 844338316 766435398 396838917 69177531 386898344 532413086 857743152 874254927 712697222 741301501 34657495 19894534 124978273 830124019 648909629 327310686 591671729 654555408 308625313 839056586 571209776 590615998 691904216 586749871 909120144 540781063 544518510 699711005 777755049 603021003 510585394 428074470 862439693 260327115 208435338 805689989 46518364 266948465 95309680 783160055 253138571 923752887 964059039 423592340 61907999 94604504 291722336 469702064 778354188 169278720 515281638 770199437 367835693 737504309 62715652 262926405 781003681 89203784 619183805 362991820 814808087 882689471 624336692 827484572 247822020 282200431 655018989 45441970 144080591 518285545 282850403 227080834 551122242 682236137 376741917 472149314 44576076 396385446 195424213 623392146 177474107 319253856 943274593 34988946 130401108 807103398 489221380 213041748 887200371 946262167 917800584 228103030 463493631 149905480 830659603 130304663 608355781 401992852 712567098 84313376 388352932 998644568 998715384 248919569 28716645 373817024 534304803 342354542 335467146 714871599 418422727 587140592 428833565 262537110 895523744 657210877 691502069 181572520 258329319 700928272 91697054 450829053 187690910 536981871 642174932 519041394 800261694 464095164 7134914 566647284 97920843 291934053 283656913 36354619 543699330 241485409 821306517 920005334 866140199 947349666 656932554 576514939 966283482 658562332 577675505 626694055 500203103 95216555 370196600 467204918 77924065 506214330 616345469 67042078 16478261 591605049 463178890 900677453 407829926 807268130 196820665 32377972 645849251 481634138 133975452 955142058 958911417 878376896 466019054 427673230 788249951 497991607 884978389 780553738 904986279 417416320 686133200 544698413 333991551 136511652 302928712 723803186 629888774 780361474 644211916 744312256 655402355 820466774 8174247 962442635 464805781 119666159 194243822 933638757 235101048 229933853 907811874 340186506 270551332 959485714 118997089 306489300 925282151 741747803 260325057 994056126 674953973 972696699 899370184 62635805 615740659 608083522 197929327 792441517 19007813 3180032 893442903 823640003 825914045 683392458 500410930 538668951 250480478 865749596 844238318 381707311 312145333 954598181 757218243 62606986 773349638 738362599 869740294 925072019 198638728 432658893 765282110 548961625 607948801 931749646 58111110 433684029 84650213 811478430 733430833 626852045 160832819 422756498 546014062 132726898 599610852 757057376 520006851 342995251 523865498 107967243 994950122 23769600 921673983 257791267 493948756 482549976 916816475 955220606 926004604 755614500 2558739 123914746 119952119 110972034 225616206 975231578 444645120 151213130 639395092 97417839 797316991 805127695 492743217 677180221 526806048 335626276 89251457 386941041 814085524 321414935 459445964 382979258 60742372 744487347 44049943 634099384 651322544 7282771 397011178 803086460 413663133 661273989 326416499 365725822 292749351 294987950 722480995 909755442 450617129 467620716 169623907 587016537 311839988 533698881 392304830 540924051 575515542 867946879 985380058 768093719 162608543 661525019 664837177 570206308 506796275 247986276 543543776 733763645 243642202 273762677 93113347 119067652 975219705 557044678 237658622 205291006 641549076 86600794 643299473 168235830 109548613 442842708 137139034 981849943 194845781 927930158 643924886 660646728 353139798 434196834 539456688 65701724 670513029 915651641 525396979 979968322 404451058 298821900 192171052 951613592 776701072 974371743 187083333 671905272 590268608 946874824 694187628 501537191 804267384 787675674 255576546 845881099 463034841 537909398 46839357 418223195 785202241 679936569 207909755 369103396 544482982 312833059 417691850 440221588 243747337 44524291 333730981 397538591 662174381 428549684 515277609 543999285 893801670 871403580 253638564 383840549 600319008 524409788 220359076 558122794 678255382 558092377 623428520 515293985 869376242 350310329 485936549 247890808 605137048 141050410 220382520 644624349 262814063 591521617 674426141 10432276 779776952 188231133 817951240 135398999 828212787 737145508 393016209 496231244 663054452 788938594 417453709 475663440 874979990 534426052 436197471 455885470 735360348 913719678 444646767 174971990 912068944 102144425 391365649 519861286 145020203 145623793 721938703 704883836 371485898 135972453 196735590 258957123 353475313 152527694 759486694 916109481 843033996 818432005 968248358 17097526 852533809 793343633 439858101 832547533 269852170 876473402 703887043 465613231 223706529 600561817 221105023 665101282 573946848 555305075 468747167 62541856 455408454 74911841 245146739 735627435 227233474 922887584 530198093 566336630 313853532 192736802 522205596 683518234 145922665 132599096 562464589 367358429 145424547 787342334 896698835 354907343 642548130 639127999 650008686 872019583 456612507 507336858 451937445 742833749 184146477 676486939 299392328 71630848 995224930 700608044 676820313 674511331 940055165 871940826 293364789 331908038 483776637 673231851 807954298 66091947 245433912 401930312 359160821 392592698 112939639 696351761 989415192 1619346 781214996 640672396 975062235 234028482 835973457 269019671 448792452 33330925 410881048 85359196 601375364 570724895 159957714 46346897 375009557 481995438 677503349 563180000 182623736 456475184 543573727 535022150 741774292 879878438 914945636 474683159 596766966 671030283 767867423 766747503 958692769 745980493 839572737 280988961 210802307 857755679 244851262 656347632 184599670 556498952 205509029 191334070 144592533 192406960 89522569 22591589 395089463 638085594 308352927 293540981 58167747 131614197 190651280 295636522 83805111 865123326 559558984 207060874 577157182 885598002 207359411 218261108 712780376 370927819 64762828 909864266 167293926 315526642 399323241 356466926 122012635 667899008 802932791 936499126 4711368 586379348 223369769 830887647 548225641 103130863 986405481 692654375 537462669 43301533 119842274 937602749 704201448 933966192 874650572 13838839 305916382 518311380 911615633 577994216 583594843 497634969 775702368 143282092 401761794 818483904 191571845 961380640 69598781 82819955 217331703 518322793 140733476 564160923 9677588 957873888 62345073 441465826 515378962 729584078 917441898 845605788 500147858 119448749 571437422 231963913 408216246 389212521 544786865 467415830 718469923 904356063 333931773 45940524 819954313 539331796 563609576 352919831 874275874 792566452 544221329 596206105 39700043 543445165 675311579 653425430 493867800 106041103 657309510 779309708 758127631 468755747 502513307 402868977 390336824 186069653 52269067 103448106 901299552 115998739 229575054 812787065 362319650 839265588 395181106 567478364 651956366 179788780 311801414 695773360 938254591 99765042 868783723 134014941 432415961 571051433 911342966 488435690 222847348 237945349 903163758 218126637 854087899 858212784 638624803 149214248 755052808 133501705 976789182 221058336 66361390 167517145 219519072 288903008 28741618 232436891 392590637 989734797 201864370 710798934 364006526 320480615 47276338 545184723 365728741 591953069 333801073 517757223 318845498 634834402 846090947 216938247 988686026 673969261 30715503 972282829 272850193 359201289 443641770 296136571 24349729 523883729 733243843 733959566 857638310 580482259 370846976 745483355 107038555 374085503 501361774 336583530 296299222 484160363 734786650 996010886 870366139 130523741 54421143 633444699 337786398 342592764 980550296 50750649 960647024 61911081 427756068 145628673 531666363 850741395 913975677 341544987 655430097 24249540 710440274 927397092 27176552 882861925 636750256 75461707 177940573 685608580 257553112 633302040 330211177 431209280 896776885 871551292 526915590 41819097 797989547 112101743 463154628 836648838 118966730 374608702 867708720 145884799 944614982 346541296 149604175 222287465 434770360 767142072 393250002 390920103 238487371 727588490 160824408 822847851 50898769 173414278 962244942 435933550 499976001 659665624 116141174 744236717 466477005 788617632 417435851 727837110 862746792 767965857 391993286 901501280 368523175 615849292 919354194 16367473 644498060 848286460 86002613 264019442 737774193 927460782 672920392 355402807 753918470 532059726 29435651 874363200 398555421 43395581 494803468 444708845 818675398 102982024 686875807 832763890 328738094 382776082 305171181 828676306 533129588 543200496 992159178 148518178 426466720 890219215 384222037 665767705 4893321 413313254 259248478 780336250 58628287 493902334 17520488 932569952 503210647 190096805 563946532 694059881 248728157 531485249 356604563 842515820 74490681 811229510 864483720 73889568 998857285 758879823 585970242 370742749 765095059 472786269 370128397 585021893 862372517 175282046 856624463 668437966 688725938 125253773 727824324 652705013 434689416 881298373 918142482 560064591 699776174 772604002 386796403 95887204 693928085 211126699 883974768 25326644 837840854 330675003 517485096 735258216 472663085 436561495 194953447 302757019 884958532 903097789 961238045 738784176 872110601 752043325 401281201 163988424 576791171 698133509 209891302 507200476 30811260 729791500 47818452 860553968 636215049 257915317 51608528 774770621 32354401 440913444 268085191 774354255 259677917 407743702 902407981 429920981 242587629 502962059 908027211 413430389 273861449 283345142 667663592 330737329 951186084 250862286 421373801 495612341 966533560 265620274 198412993 652846789 521309321 592886110 763986118 582354930 748924114 355368319 136840504 927369953 222076701 294315731 588916723 607618797 827061649 426450130 688289900 873475008 884528210 959170231 674538550 124517434 105466023 397718517 877850374 284885136 654104290 98916477 270126506 173554439 621122117 967143371 562594040 205354755 440473686 278052646 717282624 998201370 773457259 779529054 829692579 483605752 194005478 859223253 758892649 820312850 201467153 538357679 422720482 474347466 162960589 693004940 338484531 785124556 563455976 795286550 620581346 887321747 310969165 283764827 823522053 755933670 306162673 747855768 706518013 569414002 615701649 263709807 299943167 239334323 909562232 760016558 830136444 347721966 631036363 417330194 301892241 656405816 706320812 87963517 809991090 505920411 582968550 803506701 119602654 420225731 890646241 363025176 61163899 961335073 324999770 862126503 368860811 128030832 205934835 347340175 150585628 410035699 829314074 777114250 763196397 45153113 343070402 673132509 700224076 823598633 330022339 770489790 283811689 207222653 399179853 252661579 526761901 150155354 796549919 563193107 227495527 713605702 344416866 551010829 319881003 974503838 176833978 237440543 194002224 686208339 3840609 394078017 164492733 16083822 407370907 90539622 417170903 147919106 420793872 568979426 390661661 542789922 508919593 553695563 492385918 109657816 686006667 175317784 833646258 933671066 892328445 236552711 444605872 548478117 551311044 6076305 49059016 635946844 482914014 597653377 882456444 898447866 312987380 801541990 765807242 596506346 461223883 614371237 335648481 35125886 915382615 816358083 533840168 188303346 804858275 864321615 724476801 569698730 679105776 79153247 122209713 854443201 293952861 550894581 826266065 277580275 268236077 325836944 118039662 817997892 50171610 831084965 706316300 930207943 409840453 990711758 571712567 334139982 491428935 265845118 587202327 50939211 802053427 632440237 233904880 657036695 56906605 895464139 254565729 804011619 173088977 196620776 782106890 853722268 204940205 465262363 411131701 52971651 389527258 23452609 482985311 93810436 687062414 241096876 581358881 799151374 123285643 309638182 903747285 448706975 334005762 443635557 406649470 895170009 811659545 977841252 555482470 877484993 255933405 580518795 418339349 539404799 857846006 350941196 721606430 565138527 330005479 434272481 539867001 239781560 553368397 869261420 756509643 783750431 14306795 817065623 237952307 285702260 890926838 963326623 671919097 513314184 337785012 674147765 833172995 168344547 698685005 531226935 736395104 957850418 157136579 486804686 895774964 451165190 51014098 140231362 368161046 816322733 884599891 562216567 694948722 139856031 577316100 590929218 781523709 420256177 501033622 585512793 350207715 957756899 552145753 653361726 933492500 202656072 455335570 592668104 199342448 207400215 376503870 49237973 904545238 741138897 387425290 322980073 462984850 381424052 299070630 34451276 587727070 922405479 665914910 581271444 824595561 456057784 23253671 177212111 564399347 924432735 294834724 254238162 314709568 100129950 253140782 226762083 619960502 367294719 280180564 420791814 720513694 54953676 863500815 494776831 507365769 455596899 572952697 717651269 319676038 665069776 381972048 298448468 661158779 108672771 187948955 776788773 360984472 635743074 695422573 769792119 958178416 991450491 499708565 742423413 250215589 512701776 806410440 476335572 186926558 274008866 182961108 263402448 357818174 681440740 679174786 545340036 480419687 186111614 557775117 866327644 261679202 89886424 233244405 520108482 350642590 675089386 895547428 387012636 8844606 685484459 695340102 62701319 335706544 81991975 377706346 469014435 155633423 204266039 894450125 216357888 142579363 916523188 90509885 196438927 430139036 395965232 618814295 477450244 65306657 238677467 675691148 252657053 972162025 941304864 768639139 380601090 389619137 581982075 343316296 8163608 748977771 431435656 275543123 90455467 3591501 480811689 501350443 22685792 946392486 579142020 814177041 919962512 397534063 368452220 924368380 432642334 271247258 53931772 216758186 895480517 605616797 871202132 680941791 662055109 685424994 946262585 488597868 66993164 638190245 723021812 675469387 993662458 349340893 687702757 416276173 151056628 463936097 308045464 935952020 430444655 668385146 723772025 33272234 559709030 738980248 933849940 341703209 481112187 748103559 781705537 191355038 296400595 735689235 865842766 970556108 533647372 319115983 272320502 517864396 330853759 881612326 567264749 683055336 733045712 182668037 857820833 316580330 673879199 707789358 301899340 694565910 431802021 714405400 436669860 990464756 1844868 938128196 861623236 840678656 933573094 3757964 796085471 808428274 761655992 477074247 687888391 38784407 716908666 108604285 434672162 351958102 476146185 900291925 544392557 987496810 414602622 863974616 572738719 150795466 365544715 572413170 656170126 106310252 549475464 911217438 312568501 71499146 539002325 671765770 446328178 250761776 869413606 404946728 488472259 133670727 828494079 973423850 749669808 880766428 473390981 938922460 868562069 361021939 221121154 949328920 760045297 256307202 734433692 790919535 945895574 594446643 381832107 193340855 698764167 596110587 749144463 215693906 815469304 780107086 445288430 13958786 960833612 531766719 662513382 342082216 39164636 806179174 497460724 881487479 397923626 823303709 516281898 131623469 797410405 796760957 289909280 256864125 481193756 638211772 786589690 520554964 506933889 880320550 626972615 83011410 147405530 683091476 171578004 837655305 749040817 531489138 641219979 948487963 273885652 545597447 517956934 535962584 618268537 86754024 413136763 384639120 596458610 210166213 388127088 188592531 153169477 216318868 65517384 857198493 43277721 167539404 567339619 129406176 1281967 763073009 261825473 465973589 811929678 10194673 945251259 326964215 130631380 125895124 391808511 861904063 877523511 632473239 277115910 53982674 499765273 486096337 932673494 283876422 206281151 59364456 74732772 697190206 585341929 140798415 884586453 342854141 769236500 20627 724217486 890034094 540270421 702124806 596704712 462842094 244151778 685503773 68474137 75757936 465743621 991941904 591238725 375207348 348836355 161900710 336279773 754097667 197028228 900019561 832706024 841263119 746517670 963761809 468682703 448432652 154447754 392447261 198446521 923214763 836845218 461519439 423984263 826956133 807790680 928393877 511560900 686663529 580817683 475863167 459071404 582614764 146311451 946878160 818631933 386921050 582096703 975370761 795000278 197838785 838741969 386644035 455327729 270821340 561102420 523268476 58415218 73178822 999896235 162759889 885295683 731558762 907469575 655554078 934791636 998502292 542628060 699500908 541162376 503517048 711691575 554639618 772362862 405934521 498667992 877720716 823314165 397840475 602120636 789633834 122849228 813834252 358800524 36602763 826483182 327207906 118470227 2820765 707345300 975373233 551630254 297687156 964419626 128562052 282681472 401200850 454937006 451823036 184759289 865010060 952678979 569278786 593063028 589405401 728329767 477936612 354230169 583399731 997615012 38594737 120482093 797727102 547466407 31813018 885142166 164437911 447466088 259805139 139287363 662576311 59748966 867962658 594743126 657844997 689033396 816460766 87446585 900610118 698036948 799203297 27496966 584322544 551279658 855253522 690739084 430219559 265741311 105850088 973304260 947366383 893355840 110972848 509848524 552183773 901447866 589816755 165265167 299217971 549462598 79665372 626149120 42402979 432237694 949436448 989181154 995479536 911191128 540137041 435079007 101508690 215924538 186211485 446663007 183561966 497017799 597176626 992209409 807427958 547103908 384555112 147290314 99141283 426390961 976300745 37239143 224878286 751713137 379354859 284904039 903646224 534427064 343635050 473206957 777233210 60937904 468894796 56154961 682380546 451193939 266086697 557716545 28448659 903941020 138423299 250290527 85562218 787196833 931936139 582286881 612359469 403497483 932509792 556096238 873830464 991860641 677781075 508344898 76530973 271583485 772083662 579921922 392904777 573995037 191145952 881212373 216898239 919475281 792848605 323264131 972084836 135373454 613054361 735797666 683065355 533926351 933209150 891660423 406517223 416151750 596038862 530038230 602192965 857226644 381182226 310026802 155502986 861831474 23846456 100616619 122911411 53618022 757437316 540402027 456979018 702150938 755698492 569061406 500101989 505009936 39863920 42241029 654828928 231053808 243073791 739911026 399723316 253574682 832718005 597890006 123560986 123017027 878923959 772086534 795722778 7903971 403373029 650528711 915604751 773613606 825542210 759601887 229129122 748545950 694274802 46678776 835448014 548626169 459560880 792180000 208359305 511988968 572351106 557268703 313292700 501525145 918033475 75702975 748037902 179936707 804576509 39885541 108498152 620835524 591452623 872897299 199146303 844267261 225559250 986270044 120160596 288083721 889301061 573826618 287866153 34235658 662567250 468027958 488013029 364861686 408872958 130974367 865964015 628580917 666365509 145788643 948243641 919898673 436502281 517328430 610404788 677866401 674307732 363462117 63636558 794292218 603938489 313018669 876818475 905255074 213417996 755315913 814671690 55328075 675419078 994559733 427287172 846224034 458300999 478720229 779199277 35617388 936803418 803872943 524765440 479874909 388897770 279789177 760403836 905212605 548481700 205642869 402565803 644240360 618327385 274858120 287779667 225651048 927839853 543081963 632237010 69893527 272804805 163458090 992627797 521563727 215071392 556739259 894259324 813372469 470736977 35189790 119460753 409693560 671526409 210355138 183055568 339204779 585924637 870211445 597114941 450091897 567850702 581586509 418728830 405462879 27902769 171727671 867876118 569749547 44425512 563938558 29426828 657973571 922751604 791350633 690163426 244609144 337867048 503197475 559651152 483324295 893230453 414371319 830444710 703049678 771070121 58117337 956093079 665381715 773846400 330915415 522837115 558559096 269948070 302468479 20759707 323990328 802895361 916576473 297468024 743013428 421005943 56319442 459549104 363409951 727894678 488130380 959219995 370694344 237443787 669532366 376587077 206405328 967178038 389668350 298428435 425030860 562225856 421792224 680511162 803849080 994532344 620042802 76448335 569603831 512163270 135415275 266960223 512054498 808026696 143814943 33713799 562646494 553999818 46918594 955903529 175637820 275703868 895934085 180502763 938172965 136827823 296892331 102468940 149019013 748260190 635954623 817727421 904710525 494875867 107883956 951539359 934531337 787218312 414110072 473947447 28236455 59475859 534556260 719017371 746501052 973706152 544500520 405023739 418034749 174127821 296086840 346322132 816099996 35768975 575283883 621305821 345372145 770745832 30377778 446189223 718867355 74698366 673686216 386993925 929402500 663630198 150311080 98109757 420943863 664273526 452125361 992389328 81410509 847431817 827475522 539410274 976434066 352168799 958865612 799273863 710757967 640935777 194075962 791478239 175794591 958248028 760228444 703811527 413121480 695982203 803774193 960384817 16230829 886032790 600010002 195020366 816249409 855386370 971869373 277011640 998996155 919336105 31431409 471829634 8962811 96506564 318932808 298527297 703828551 27941947 436572815 812730442 984384940 384766004 684037330 286130451 318698902 853379493 28597787 302318094 351367013 500084062 117344911 827478787 983891854 320874588 328248201 48626717 172862472 539937006 604385525 575930011 630408801 750599869 579425441 177274800 777342072 729365977 225982167 773207466 490906366 516351625 263903282 916106611 700853022 441732919 315607885 757024889 977022071 804019795 327286873 196916729 67253503 384917292 510532256 214948480 396953696 634101006 67449755 958408695 451682812 313874676 994118753 786514021 359060850 979460118 287144695 992108992 482478372 344163300 778732175 64218588 255332317 251347417 169962811 754207306 125151013 190187810 468100260 190265852 950135922 285779098 806326041 320256894 517093476 682492343 818025161 195585489 973024066 229597207 142164927 838468651 845847287 203004013 877572089 844476964 999461522 341319804 578574984 609180420 901060502 849245229 831591082 498822494 796429224 467888057 56402787 16876586 381820476 317537055 627595944 639947012 963069326 419831370 825122195 245885982 977668307 494454679 226678432 596484261 942801780 67365064 801856844 417584280 490213100 492082543 723051411 121659 779724564 378406134 843633089 452922932 561193587 670714349 461100304 809247820 509443068 117143760 441541429 642684954 440525377 709761884 586288069 779896882 789937231 752581627 348916590 56159829 884509299 423617812 23288036 767455022 540637456 792097151 624536349 533523645 11703496 768343396 19029510 201649287 46984606 433177193 738141604 238733942 463619105 422968511 342332608 534384586 393124095 203301503 854475141 610171214 57221988 548472077 283127116 321517880 941246422 538747682 394830102 824548892 820367404 370507535 346661434 584675295 890471022 81502012 322088253 316607945 695084067 50655038 477284318 466011435 175057268 387130736 613058933 860285608 40225907 154652687 783933278 588235063 664041558 710663530 757246618 326129793 182370748 896566682 475802760 274356091 914682856 719045065 148246995 286549716 738190100 597403407 117692302 219516662 588573498 156159046 568123507 478375142 860868720 263579150 13442808 664711665 128426850 354973630 287816575 467223271 45879777 27278787 333762305 594472357 331664885 355585153 752759390 959559118 894064192 128337 158997031 732351388 299425094 291542183 187118031 53178835 392756104 923780326 373098376 265381696 572183878 201232151 492021735 866011942 965986102 70133433 667343165 391864513 456400077 938304198 439808424 544442320 836745615 901710792 153435892 757171479 125917151 767723334 71395988 876765414 513809679 803761625 98235531 960531976 17680789 619919712 612932316 757139047 962011703 466323635 451209178 190642478 264069832 585905392 260751354 599354386 685385916 249932467 117409902 957354742 61827176 135484787 790011734 221996469 727728984 578953579 145204276 9718812 211582546 491713159 834693952 496317346 786411965 254446626 237761496 121769498 939434572 324676228 290469975 431542479 560195435 371894991 425206288 813624168 682765609 515131209 421708036 660793195 279189354 758929980 913397400 381818734 580802316 220471981 249424978 585111597 698778275 636206224 144557983 349052398 621653139 399008096 646827921 41900345 745894900 234176131 876438446 896419617 180952746 113075517 211667078 199701221 579013690 267714521 816361675 26749792 734629142 505625833 842870224 569297188 30021822 328572463 209401996 717960496 920470628 40234366 841218716 161213182 477562297 411704886 162963936 659947732 268484247 249403634 861407689 342366229 59620175 129562716 760078619 547222815 509593992 713213283 792896192 693011279 190200911 533976029 366206488 901163520 851331748 526312273 69823151 40093710 992902961 926457369 732033093 494285542 974569385 9473000 478725045 933642528 463130272 773964509 767630884 324784308 961999074 611402209 364616956 81763588 51859802 510639999 539364451 326174995 70933366 759043103 107612516 752652866 390366300 359095822 873679740 600210773 450001703 67996596 970983101 654731923 360858870 682685716 191303130 308496238 643343617 994860581 117631825 962030344 241522348 101186531 743875352 902745660 533614195 759942898 841783854 872344925 984436114 422458628 937115961 421315217 324495809 63795242 815378404 324338101 643186344 118084090 839325241 929877554 492827143 348358585 948340547 377387031 582215384 164637886 642337647 762497883 491701077 437289985 701350454 828776338 557218258 203577009 756848725 479298266 804955172 395866383 967737675 922495972 970177754 814997833 748094261 666331655 440551327 818480139 161388011 925059033 912724641 463276379 714259278 899362217 407086195 526115532 991365855 31227153 177726640 471534061 647049497 42123233 580596029 951261799 621401002 266670374 912710650 695725580 472838397 339046637 805487286 651309535 537349102 477398146 19193050 78196263 146162849 362040114 822085080 63962104 226962993 276883840 924129509 550930560 331810755 303082938 349952862 706481810 782176085 772214992 154476919 936784503 551106037 344609289 967246643 650133515 346924428 844669043 780537724 58191133 103088379 104746867 602865556 786154625 402150610 262155801 215189595 389417300 966918185 815495959 890005602 314978965 379864266 301963984 257734656 255837866 370474709 698110995 131998767 563932531 231835377 779755421 697706019 149534644 668269516 46276122 721657100 650792528 697329002 77912086 519861519 829119150 732678965 29656115 223901945 800385478 703287349 671848000 94436172 720254271 514974447 395856787 18726235 301256287 782148893 432930779 375120784 485609804 673286790 5557915 387054833 609006273 307010005 271862289 365973935 650086372 283812775 735649910 182771447 600167696 271577150 101734872 350298346 690334178 91866030 178076587 667050696 988942213 660318273 411543267 451996662 596570581 309821646 83139594 781384889 283111185 166625524 568821514 824544919 834601725 380468415 956136348 761402599 806858707 716559105 773905037 357274625 96062257 842109292 163356504 740100475 99841410 464581225 141522066 314275786 318297817 291857315 39013595 346202565 499413751 752431298 122944172 546611453 894851616 879512987 988614225 704649213 871012214 239361077 149168284 576573920 365434392 523569098 851211488 637159146 869600610 288689592 125190578 958742136 92242828 220773221 123221983 141961704 571632686 324420858 825591095 167704258 673106975 482884365 803802615 436052568 446173934 736074902 368872698 212408165 57183800 724096720 933378062 634542092 712269829 328970198 677846984 24998579 842431279 188177355 503271102 965524191 505677225 471937299 997846386 689521260 675622923 571107083 604725632 930874226 674936722 835575821 347696534 282952850 792388583 369780496 111127095 112081013 139892244 392983009 578442640 955354087 353445472 515534704 916760136 639134395 934296317 609525059 233510716 495011782 847591132 905922090 843937515 940718231 470629252 32345000 911301492 752908357 426113656 586516955 903652457 773497269 139658334 819315452 495918430 714329378 204647815 213640510 110779350 516706766 642093290 347613975 729941042 349891900 934994399 219020353 795937651 102001955 735333465 351180370 104491524 155128486 674217788 563790510 543337186 824747927 223297914 54085349 431350061 688384897 9244319 620175966 739969173 55797254 637851942 690729789 157621235 818681056 772928230 723059025 3431895 512563562 120229495 846407736 608456015 301255152 277079422 222783100 762616016 432607568 549292803 54265578 197101685 892939294 732204706 94905451 578909784 711291776 567846448 251976391 187110156 308429416 550713726 392825228 552968763 796642702 689476264 523023985 490966177 857217460 597940552 7204259 299812655 192499425 346100714 905254117 289965001 190841486 269162142 244636626 362853349 347595739 885448004 394618365 12024146 892492916 561034155 551105310 935256221 994674467 580252117 183073193 165573548 564448218 867940286 836736068 595838997 859761670 953154530 627662392 286798539 205929067 322280044 11582346 666834652 92266150 397648367 376105659 358652860 962179769 630441492 346711468 855762785 610446326 138895694 454831843 474361107 841553295 770972877 114461055 755456115 702418513 123963425 745556105 646395369 244548464 304012677 9682948 618325766 180722602 110331640 930424561 831049482 852269521 400932645 86614522 896788435 20053243 27046554 208799839 114316117 515316082 891978506 140620116 254527735 103266746 693855844 138633968 165522085 825364172 451443506 441630771 419031024 128810775 115219268 975998952 297659180 565997656 661017770 220854313 343677011 326913453 378105138 425001166 582204486 345108121 675557908 795139088 804912449 258155225 721346175 155195134 150948488 667553365 248523847 382494892 594370364 272089607 880858041 367036738 2693361 80258681 406659040 279658393 221292327 715434804 304591668 559432839 712430280 271430430 383007074 454524918 18069220 156592783 144903615 914729991 345038422 180056598 589631139 133981039 833964457 897046586 575027251 185941619 471681314 339223428 267511986 195055875 473664260 196692853 682319959 633753964 826870463 461832236 276091172 506115893 293492424 722374996 433846901 17236612 94460340 712132572 234302244 990903198 569975206 826801621 631033525 665862365 487761684 77702299 224519384 446394360 825359036 546754377 72295190 226187837 31516193 415813792 825006241 166239442 143787898 376912332 600220780 433275219 113922124 341773623 361240802 661973299 896278894 384764891 304620487 553159183 699535553 429187772 68161287 17804298 87907794 257666196 645167242 99930247 768933123 513758700 608564987 398090829 127568444 475690438 958594191 561029204 71702483 926928134 476861125 54488490 573700433 14820165 244748804 743592685 864300693 613380361 503509217 246084000 962164512 687213587 614777328 964278328 409383030 731413298 710626204 505305085 613147216 729652783 840630637 192965226 798475203 728869655 705772555 330708798 940581467 483872100 290768735 841625506 465734009 511156558 929070622 929314886 709057347 10942862 975045833 249320470 39558025 219077077 765648654 6795305 883504358 295367665 229903828 572172712 893005969 716506394 443904945 28728931 53457606 237664311 199020335 54831762 199081197 382860384 400979676 344755231 603481002 26393081 645052489 569244969 412774482 326977953 63449015 743983634 559405971 253863134 699034172 417984185 78236353 7932821 289722216 212633740 623106889 476278734 777820214 881960534 178117347 828056180 401203189 962470753 890762567 853887094 658329209 91644771 159506099 543444634 817544382 356706185 867137015 765642666 631114404 537077382 629143376 354242823 424144257 521392307 892368328 542399408 724589989 675573707 915138021 805762484 962357221 863994691 763774434 163495647 182161227 81567919 902030005 748784957 550988129 91282069 678417957 638844278 294835077 136311994 612261517 793500544 695547812 599773294 522847719 75208100 215336941 331842606 447367175 514354675 252102017 288054187 784400788 9204454 294836704 867879695 92184656 900457727 581970626 657871665 27546537 774843352 781129885 506882137 407168065 42469969 450080497 359349070 16871436 633534521 271224837 778857771 623702087 301937609 202016956 266778825 945947791 513396554 196898461 552266232 389519101 428112295 432885028 661186079 473424649 844666343 260908308 501715251 526222999 839777685 606962897 128491857 194670541 7368873 510387668 699029265 103936378 638595696 794045606 177354467 615406820 873020306 380932473 723007557 304550568 132457521 495511881 350776648 958912391 253580238 706968599 972446389 132787111 960916944 836439218 621405245 836700449 527077027 682580004 917783745 540169930 126281409 731252031 156974479 70816156 26519917 614294080 788834085 435588953 555192903 347991044 824426974 6087357 176332290 51616465 830053526 423158502 594835139 606994806 213717669 25672972 481596198 554019413 595514266 914175586 775839153 400421716 383479037 514758459 961560300 705590855 131118096 687553134 408084073 222957668 748780793 60529980 998579460 521253378 547239068 79266288 327587889 3247738 843734856 702343514 398080326 850861694 628531902 250853416 342077428 161146797 726356667 344658059 24435728 469968348 321487206 428600888 478553712 138635891 651876138 307903919 531601920 617002958 102589346 54980133 725019823 469076627 770949814 980376028 195798702 260074903 3504360 158551395 782351346 416487765 25970842 46930763 710133389 354853527 977953839 947448529 885071254 732608235 250256752 514998465 833557089 497635626 224786399 385672347 535478731 495999115 380616988 829224492 35748567 791437248 217363855 111744334 220588153 630400224 795226498 318175828 488203747 515087129 680178584 779344389 168544001 936045637 581524842 496076407 704676234 956180426 1460914 599091922 485992678 521070651 296285707 640396795 521175508 164596197 892906623 549441599 782022074 194981626 369414160 99861505 170585936 738353539 506618174 333250411 945874051 677056662 326445010 376747324 630389041 890718819 582684205 707473415 333771382 213966347 354589589 40736917 894078566 453059202 563522388 189215137 346015881 360938124 176618022 208012622 441284402 427877855 681404404 373901027 985004431 892886826 172368322 924291537 657269149 976995678 449316056 464518685 402150221 684984118 733052894 893274069 779424399 949590049 426506823 63726829 923284280 132145010 139744475 231318161 628103731 713006573 603742648 789676589 70595588 788022016 344914843 752786069 701889948 479915522 599816963 472330349 11388601 897372911 422136816 844044378 993319198 866185054 293589990 966840064 296272716 649108876 702113747 370704868 610945008 461624503 935744883 54145014 445935059 720113348 967464477 507000824 415064764 912333179 585022522 768928081 564855006 660594612 130859421 166616491 491455957 72998483 760364681 726555744 599224253 731600097 234916812 281783017 504166664 94134236 771156209 974861113 905389888 770059594 280659309 687269497 641275120 672171377 356206741 675481128 854733667 738318391 170112494 459452717 448090335 824574803 822910783 920736518 231225340 336678649 59752843 4060648 317641222 258859096 260408392 100781954 649916734 456240884 579893068 587382552 458274203 845872422 220042514 821233998 931151884 67145289 512077417 485210907 248559693 52343516 451718147 824408473 369599357 587574222 987677411 546129715 789414774 30914755 484505222 201882249 281702536 489643152 928892922 837923765 60625622 595320226 969901805 589713643 937951372 195519693 274165468 829309578 130249426 872605872 107737851 79761190 376815773 832767239 61718800 317559369 814578482 655812058 794841776 635696491 816990041 958815334 492534235 552254093 411332118 259749995 926188922 159499736 225261797 108566228 851220395 367489835 421035882 187291438 761488212 747485122 828165477 629395178 994630137 455664742 265069537 97014508 144179785 505801590 596275245 738042116 346080436 629060708 423916708 386081480 45696272 880774995 882821249 22110378 702716123 670017172 295410109 356592849 947853719 329828708 434596609 242425597 594261023 524029758 961629472 895621007 152447696 614540798 170266416 107815770 736006332 802759032 248764690 545596015 645663355 604753889 51320265 944889105 339069776 854007495 323929297 817523723 38838349 243409667 879022465 554237679 609309466 744993982 169445463 904985730 214768174 649347790 313260228 567419839 218058831 291169026 849498009 750546107 628049478 942537608 21528756 715598458 847490579 381255694 995584518 386927098 969846958 235015654 352212399 322545317 482891577 287136262 277566459 663438379 148593606 300930231 483547738 4969767 139785216 236956699 41229511 1893718 426744775 246040445 48289127 815466511 817120423 228480410 510481540 865952634 11781657 498270910 25126699 479499969 192266862 366986663 326692649 952874686 10425591 125407007 17142 865521080 625431111 156351882 646849128 432258224 236019481 387432512 34705454 765393181 249472487 712004465 701548509 228617072 206200198 320224205 928838572 886979103 677688258 842961973 211136741 711197848 164442534 248714045 447397810 691954092 746038383 929461961 614404596 341850660 392853359 659569250 828096517 400498611 49830654 530271790 243567753 239302683 961371878 833519460 744634018 684116612 205769155 601307196 554478359 320982440 509629274 935465838 828597037 129435395 419457956 136857697 625539680 163617454 132267830 579733490 435683261 543217750 346299936 348338931 84951040 683751379 972130635 935791571 954721952 145089649 338686131 859342206 140730029 966680205 665616901 762554233 214790053 648293048 883898029 490139810 657797226 10075340 148218057 878516216 361282412 124447678 129020385 2420940 664370527 337906412 833887286 264484238 616164360 425079979 12715572 527822264 845790266 290468350 131290674 199505469 396859387 633504560 805492136 602227272 549774443 725639646 336188601 941566869 697085978 316479748 868611778 194836092 47178942 269824062 788407039 146419669 624986117 899960582 265344033 355829302 861249115 553858436 361332728 612131887 478018188 773821035 786694578 857073981 964565748 980310126 341479260 160384682 876903975 277905669 770800955 854992862 907437512 971132861 550394119 935135289 465268047 334026188 494683234 328135498 857841135 172722855 899713684 612000020 984528189 731083700 50741292 576005312 867320161 669955245 662628225 121061917 955443961 82729384 559070556 590311359 726993686 53277880 644443434 271957005 509439572 145651419 502823997 692162625 73044410 433460361 697865774 752271366 642400514 782354617 492742171 907223903 32329745 754473249 159128254 441218751 821423808 583687097 24909367 823236236 653439833 41944254 298944828 184633049 188523445 913581973 367128015 727048372 193930409 197147458 308650580 632306400 176827665 193290973 252936407 235545516 213885350 557654822 2499612 705024847 757330725 478952679 616907852 896458634 421097338 398256144 422539021 150405786 328770740 835805653 707072110 782986058 191525271 3569484 770322835 198251689 204033570 629457423 446663560 180350557 450488556 63769746 731477744 354442354 865117724 403165530 65186861 507302694 632042643 660208633 334002533 819170059 277991189 956262261 834619743 831575534 767714913 349358222 689380019 63976446 810843519 353520498 903284872 126149509 501802949 947355202 486745239 467951260 134567778 980938659 124504653 204350770 848437169 854645836 162889611 454417012 946750656 696485252 267623902 352104372 144976150 87362011 342365210 577030687 849421956 425048972 97115807 642430510 557247012 45304290 905141716 606120125 590660723 118164617 336874581 88011474 724995309 213844255 867722141 264677192 446841189 826605314 438067821 3115150 765651410 297657253 730945194 330792488 916321539 976336208 824298850 365133847 806162317 747339887 23921743 495004772 17179381 216487356 942337800 835814286 272328164 903594312 828143564 402096230 102956943 956822875 258456894 875481678 902956000 900684964 712209250 156366361 711685404 326997929 627195362 801465830 145923616 241946385 484960631 266224105 831609862 431747774 239709492 453039244 86895440 789737905 652142326 512338821 131903515 919168722 920893989 980270762 303928161 307614890 336001315 491913406 359813723 324265542 928674341 937065743 685547210 941579234 82280910 976865657 398995907 255661084 66413305 621685276 220602924 323626061 422742819 860631684 475992416 216148506 440530867 750118566 801013292 891167909 803922893 154001638 588675551 20599473 232726097 248450386 738991786 360768640 990873839 684096970 307633094 526396975 424213877 594429655 350092884 260224679 295138813 654829930 447910565 621388439 528179007 524596831 194618182 660634977 271332403 544894899 476649008 952087005 175785443 347375055 365932854 546037966 474437764 77077736 743230937 577541924 969280912 901489972 233566923 135535461 732466721 913669936 100824892 836752071 954408885 599517260 571671890 603095401 159304696 67628499 21481666 49271603 363398909 65265318 729754498 143750150 286593980 611085249 545841694 980896925 992467542 185407194 729173920 659947334 694465539 499848624 195981458 431292255 870281187 162915182 852489926 430871381 599102411 2992662 457511794 758594208 593734325 90131785 196330982 260281849 152759311 52519794 939835403 216455091 91642883 465055257 367064241 10499127 981904297 965075564 915625250 29707199 628918420 777483149 556232682 376427653 991252179 258217890 143716747 790343352 935567020 65767334 423204583 589165833 421785028 616913355 705923397 874246424 803411059 622281532 126771217 880067137 172760098 865290111 744973626 260526387 118437402 500784257 636738219 172395788 457126561 612561312 422617266 480542774 790684892 51936399 91435364 50793426 426400707 224507411 367126095 516306840 283352837 200505694 998507852 129119176 455485483 457578697 959517013 86410859 827419442 218985445 856929407 425813044 64925711 91833631 346463405 102009510 162930697 594814840 338313246 819628114 612449432 552430464 853889835 521680799 451189369 524774324 366234746 515690205 833752728 804811003 253185900 654419601 106136052 271178910 311447869 430091907 907954298 121674411 505042904 269537202 727756302 308255544 732738611 790392441 537972803 956439856 559304273 545887638 951722252 995287591 268471442 901199898 376454990 938569154 36279035 638120391 429000228 730143450 880893670 117754711 638101858 323256556 611422469 833064629 514352790 437206036 561072019 347229705 512893906 304739974 515589653 436915277 948492713 891822023 335142025 733734642 755512936 976852100 501521563 991735209 359421365 86684898 517657202 271323467 366642897 533969869 415644957 663808164 542469619 199327277 839166532 571627245 252859255 685193561 957425338 122640165 413747189 978295221 388078864 632310978 559294683 639506274 327774318 801609523 947022805 593576419 496238855 468658511 855685142 433270298 676270822 540824561 568117990 951243570 476984030 977454452 886964337 718153186 366698551 486955679 261989504 764647251 876250619 192287907 716882527 23779471 225371271 480678746 214195087 491734729 445031449 519830627 469867964 223691506 975237744 220692663 222039111 356842584 738527381 58417031 690212807 145835726 18053887 975965304 921257104 566957207 661763927 363194443 197179949 594955150 545164724 341600224 885328211 841243995 333278076 534319943 92044153 801693121 877795107 72229311 330849880 544191054 138622523 525400334 45955224 491999631 15221965 500163595 269707513 630860216 716348045 409169519 419491526 659387382 58666712 697862107 477366004 575496910 724938105 694775460 960332001 21058788 113143051 350099352 860365415 152508159 332525231 958268884 975550255 550241609 83863411 216577241 680668664 867579727 69257262 989252860 578618019 595865263 126702117 944892094 705892790 761399135 113116575 120060678 603670422 979399015 201573115 819097686 7917930 889592928 264100989 326634644 480259272 872478950 874599183 666139299 298665653 819813312 59663371 122258640 461314879 942612502 578196430 440220437 486088409 924724270 915812351 842395374 397471631 826554523 427325890 43035258 229333671 220188753 382437800 792633649 222550890 566386534 984582645 994786042 236989926 426540192 440948704 681128233 869501676 968818886 344589086 672394288 835932664 487557969 89501976 685475544 398319883 250138156 274931632 538191947 409277965 290285169 445790572 293047124 250248520 154659133 601428999 601089094 936573153 156896735 189233813 169615508 71923966 492840395 34625807 976729683 244223254 360998168 690398612 478650677 458833410 568544818 665521082 554816232 184420589 60221669 531716533 647447200 36349572 662713277 826629090 441261485 701209784 882919195 816124581 716153718 615249201 779274104 773676104 474539280 672801876 118805256 713197067 541468275 25000158 759090331 732419109 768960409 865281970 814663323 267947295 354323282 851946790 88056999 788203969 56408602 466910421 836502072 986075752 432377989 1297783 629544438 499304905 111903431 719634328 178092754 640680677 29277752 575061642 529493963 822877710 68634356 749798311 537707556 983807716 517069949 932413564 385635884 289840401 746312750 302144940 321474880 658377702 181991514 98151817 845574738 13814750 410950974 604596061 548899370 433136691 25285183 607738867 746998051 548690732 574699182 796219920 881284603 362367435 513878146 760209675 78823944 845694312 64328104 626321604 755901858 478207120 376042109 821830291 203657022 820159469 33798268 609951916 425535077 695982591 847675952 518210192 278239820 455734317 430429343 7454925 380131956 194376950 498076181 39331256 592518259 807126127 841739467 308184940 337731367 217674733 821783850 615859039 239095545 99150581 392401830 279790569 97352543 486137830 549155586 768776118 970499995 609976594 689301851 585195127 126272527 49640133 663690356 448201272 104866567 952493546 653119620 265684663 86906409 918414017 165536483 929600106 263585705 475325018 604670372 907110833 436040881 286367356 873429690 84037488 69855529 537173609 692982183 375337323 883336690 708812750 998260900 478089808 210164156 137144689 532504404 344640786 752212154 238113376 787949557 141186626 458894706 746913862 787997078 869867524 345952969 10973133 446266881 68035535 645666280 487815915 392690217 592875278 508684307 530486481 527815971 511751227 49172358 595828386 235084633 160933253 391071592 146958708 163637176 568878349 660293701 105271290 637662101 778861560 776184327 154064691 138570527 706472065 840950654 273972088 196246685 573256414 864475378 310951062 184140966 264461151 83411042 644577769 627687775 666268614 180316007 584269510 946806546 984162288 982334285 242615290 447931653 71073012 417312466 303697938 641937126 678957511 678760942 690206504 574701237 724093611 938848728 154271318 709074291 554629177 915714121 677933572 454670687 560448855 886450512 387674055 740719088 431444105 322624095 988461118 71122024 963218590 442577576 228866661 652545061 450860923 225216519 168247420 30389222 114434212 697410877 885426362 269469425 359497226 683457267 941624898 488900265 899978212 198695977 56117688 728815726 456529859 392448846 66432047 222767359 599600308 524810354 817080660 561074120 256879706 755192030 581774186 52283028 952214289 314391243 778501875 334167849 267253076 844154083 55617090 163021388 402671670 504380256 837455449 417090166 944857365 398377386 641233522 135877700 647962473 253998922 773143536 616696593 348135526 223966187 367101885 878309669 410615347 315706949 262294505 813149609 95412641 403466384 537590288 901995582 719844739 398180157 656348038 72139183 314550966 560985526 277372034 244565962 953799341 577857924 947815714 608862514 270550031 888424606 417887949 151764888 635870954 238561105 255362219 761460603 915652547 445576191 683250306 521537506 902212164 911200521 520814912 422986145 463640858 918472221 188335939 797718147 429468697 765130248 402848019 673783435 503205257 882519030 802751130 891421888 337088791 256174586 863525134 559193059 77714674 303156391 776444588 559480928 886603936 42934750 717037175 103615831 170189723 370780988 664220608 93668112 816775868 419099336 401107698 794390665 321555093 953759107 618711839 884635854 535320929 553424611 303879207 28959185 391402141 334288364 643737461 658348136 446447559 549950044 760861316 99627094 679467837 844749154 911386344 944291621 388384404 870281895 437103162 671508660 348336254 71791645 940088104 361892719 569619688 973729722 414407078 865348927 415218904 106754631 134758291 342560306 661677575 569798069 138164842 921943189 988763849 322497407 873032864 286682107 990951800 750181405 776644599 128403013 858570353 56225164 754766689 871863067 596468575 206567156 705853665 5112496 674488387 412210550 538468550 582691693 754830113 66566210 280276288 657667851 828730325 43843339 729475742 900818077 829016594 163524059 953895478 507950934 991841576 828308238 48050891 536968512 47919087 905872455 696004448 554704743 896972331 545901168 996139400 715242714 853513807 488684900 149164647 936406520 128101102 568767023 954142737 75187727 870667561 142782063 354131411 314088914 633728126 997550749 861084479 727815925 438095180 738227154 140179711 229462255 247287353 146978976 45949649 514374081 138086467 189792036 500883062 527882313 405380182 710814881 678656140 12238601 226588205 926760750 946678439 579497507 429127037 483626643 242378510 193524804 18535686 25275897 428922470 138449301 880068160 419751471 695544808 51822330 349784062 913317894 534364567 332391912 997771655 696018692 356766091 773788380 936352922 206784172 218995260 980989000 225259313 987540067 186085421 540391112 159370952 105991277 38864554 921728270 980079809 272014178 730951858 153516760 750880048 327973918 488663274 747731172 233812261 922797825 665734199 813086086 461462115 554926054 904580659 229362847 768147247 367885270 815240647 332714706 68830828 145725663 639063153 598168660 560817934 146678731 769342096 310766056 105344130 576743280 450265940 400089329 642094055 851340119 936143280 760303160 190407536 825671609 39425264 571249598 683843466 296184672 736377526 260071112 15809956 542098774 270040838 850735312 207998125 417781355 90132951 178297973 631910289 293604252 56367169 582411482 32076632 137968619 206125721 70630067 31415487 72067394 12777240 570404772 901099909 721785792 717130816 11584861 124798049 911872883 912633091 643644510 692860299 253255658 972219837 910916098 500322433 905822550 314145397 793173473 645120023 939842786 148769995 26665875 380979266 678151974 869534369 550995356 855138409 654471495 744368516 23810021 5834290 910274693 274879190 869522529 309995078 75038536 387595020 597098049 725133666 293088667 100374587 110589873 532678918 148190020 176544353 576762816 682577156 520534532 110296813 368592633 916650348 214522186 834437432 53890804 73358350 498867532 18610737 757611425 826604076 566201446 594026189 556055003 806966649 235083647 571576224 510430895 253539306 101288109 687018288 381531394 579353984 521946944 12851911 492362172 593291852 152280009 43769085 382939236 554153477 418442082 480222423 651334818 397518589 82919357 961109076 19178971 84201866 32620205 703950439 426429298 414200222 314704216 513581909 916963200 169839572 199366522 770921079 495072986 802141778 630426133 697816323 884264279 852056656 227053583 529248164 361173252 318646642 273760229 611566168 24287812 326290177 789211437 637155472 286968608 563122733 307107832 75944578 830518865 654788223 174664960 13880633 917147861 887284184 770414387 163443925 375627607 417777692 980422957 718995630 966287192 842762209 416659660 24313262 175425890 616271886 710633395 484448089 562114620 320381279 132781111 901788159 821782316 183233292 904153748 701164888 530071286 664734871 16666105 607837653 602288259 639904380 647270214 988080424 108285031 184449976 981305488 70106235 248089481 166528892 860642844 936414677 501338980 494582319 869480776 573622854 812764490 712963222 20484384 358655359 2803028 781651659 250241828 529046757 110750046 623049200 778181 906422065 577485906 230620371 853804194 45543347 990199885 31185147 118472964 106199613 472562816 534506402 101348169 554717111 175875330 950001499 548043188 17842012 955112372 602324590 486289808 769908701 585397563 908763575 631915859 279542563 337464240 221631497 865342175 668628312 909116711 994897044 293360804 132303060 250475173 685884568 459332422 320697326 294067218 949418478 459826375 673792228 171338625 835942292 876995762 477494537 168751917 408923694 252148983 954998116 823042117 77945336 552112208 370224704 361913714 372552614 142098998 812363618 724090020 363913234 821766408 518960521 594345699 623748698 769258011 755132574 94205257 522638118 453327215 972918178 788931228 107581562 816797297 929139921 154924485 278070710 526700061 150886256 1218116 890611696 293071516 452251659 404798187 58474203 508492580 308659528 251567583 623363176 566280922 100627070 55045943 743055915 358564995 333292742 607111516 831972354 348839271 849141366 506399484 972324883 42608638 642394262 3696494 718774306 25409684 791489547 75586194 311497429 779115686 799913243 390857209 837611736 260023206 942261834 589698076 798609277 761342499 617496115 532065220 958516448 106908695 470569164 898304378 840448089 371094609 931963109 99822828 219545401 778929542 669927546 871778094 174013829 511127969 966509557 669733553 519850683 453190555 736170034 195498707 442113448 425860864 332843437 193895173 223682452 303444539 356303216 980375254 176547026 834925690 972738216 197167282 940049024 104811916 669368603 875707967 971108978 743906701 821766674 853890950 750336836 545439880 635211418 441120263 578139574 101306567 64833252 408373498 765289157 95339173 139503103 635913940 637539071 899130127 767630767 600302472 359791286 441854770 103359907 592914669 298747699 163899879 253418718 236693859 420621907 335604884 980003660 250865794 21385266 507038417 891191653 580401173 51691972 781961145 973087762 763241657 784451990 123895768 282320598 830722969 319105955 857763319 314087999 348059576 809069768 434177417 985761725 108997315 885283888 681096810 43450036 857944665 324577669 827744288 300279870 61968758 37911604 760137212 860958198 393699536 643381639 260469065 972889704 268836361 515362644 668147026 401878346 279322153 55385775 725091546 641860591 348704218 380716144 665515123 539496020 492232372 421407219 401848272 814362909 672753737 517251503 124700368 356671775 911494558 835734588 831600763 700481817 571162502 932444226 862366165 322540082 818882058 328327515 996548112 114953497 441353380 555738608 356806497 492829735 56535392 348041734 75854102 411685933 325210405 253915257 736811495 305672028 962862845 73168384 977669848 420715391 866401188 543778434 932358688 129705123 360809875 608749237 905171990 754671093 218386747 886304404 592703987 106340937 222974753 390727438 745472977 97599604 550935619 250032203 564482569 246692119 127449680 957002726 922456473 77317787 382042341 212967113 559470131 502790236 283272379 656256271 407338563 855012713 1529374 139279656 716207188 272171703 80724601 65836642 173714163 428126098 113581922 110491203 400592997 187739399 510063212 518856228 661909177 341577845 830647621 157973836 422684233 418938486 260751656 79431894 772513622 325716614 716725054 228397156 273377300 645294081 778535408 54911560 404017135 407704769 721836008 762911569 330735542 574161895 403187615 308055444 786207155 882662785 908905413 859036086 279918590 428597869 914213646 19782352 860456142 708432609 184761156 837583736 576475001 881736359 377731066 917080555 357689813 404302203 580505018 232439863 223151339 468820459 36072462 843517703 325188304 662870269 395207437 785451020 577436240 703203024 671201004 81135105 923710729 338025143 527819184 87892818 885792355 747813435 117836679 348795979 761163927 124864218 573692020 25896021 877846984 286807792 712955015 241214442 639218120 881730147 766659391 956914271 697949538 152040650 533361737 431421737 734759652 857304697 644234194 699430338 338297211 778458849 285996564 778730459 162032098 845099087 697829982 417163903 78913615 29035004 333360235 870352849 525679024 310614456 70108959 458571697 256343806 287415239 816243830 563958871 703507613 210607852 860952858 123804940 583411523 885301431 776996649 690141311 696570186 648473215 809527286 342696454 466377911 858615698 910203991 532862780 153060116 720462552 490211386 118912000 478938497 779981698 107353774 910444894 310531764 345055488 946266813 492561524 442751047 202936937 914663156 820511440 719752880 702161301 401758796 973844935 828356889 251473992 311921118 36579800 534895375 426247004 959360718 363696417 715308210 994614857 316238475 319831491 887788710 807514281 984692221 778637250 111841085 519392086 166474130 729317085 939154030 175757474 434830092 390916605 975214140 473855934 993703192 152466691 94567489 256455289 386048072 376168776 636067535 985701606 161490254 194296155 19115580 495829680 910069181 425874464 833700400 135534120 169164431 596540698 928407647 226858148 712018138 265184395 405160166 892703999 240675727 18363590 239658044 954683021 253931363 332438793 837499538 415681675 382395734 204667159 457224834 603094846 592678765 865265362 723510216 581927083 626478102 530251757 133692087 780363614 571067399 217369586 709182099 19979284 572045210 115241921 698980520 193866049 13106075 568940053 757179606 88660201 610653727 199868742 602524562 252612378 929171085 714210602 429416185 250860998 884000510 447078201 318775219 440701343 764057456 92751392 987245567 32463256 432881596 796541413 688840466 558424991 623069554 523066986 907395258 184638565 436504184 491157383 472800807 106604155 502292813 72323923 836312887 269233370 442489301 95177042 137082525 459671066 882550002 526598454 330266955 112211487 583517992 868996296 342107252 786601189 135074694 99698978 487517548 469748507 80960516 432126673 871376322 697982073 834015262 493583533 892066072 265738252 774296213 778187059 563587829 938147389 267847429 538244737 118684916 855478027 342188836 906076915 791967775 879532153 291462196 388562874 85852436 548542291 986069484 66302541 987898534 205659470 541858286 736290848 693136980 212503102 177356245 404889525 992560889 756670480 812508294 926525626 74172127 44227023 648906208 256654373 394177490 841076095 339628660 441577244 379557726 527115753 719336734 863513705 625565202 186451754 717959964 247096013 777809740 131015670 61986123 437358503 72814831 997295374 774611925 967361952 213535266 976310634 292622514 59312366 95870957 805341914 973733951 346236438 330880533 760279582 935463143 321216265 251450245 870229054 442509062 386085168 479086305 871195712 175714383 676798399 854122060 43056718 961364655 636276920 927944735 219475563 418237585 918496594 150291144 555397973 893579990 873001695 768582361 640752801 590280544 58097959 196436904 575252500 746857872 425813135 701880628 13011324 31686218 175740085 28567666 999212819 370510061 199807860 455538808 880750641 748168241 844951928 557123684 17275317 652752442 492663799 591773895 656248055 857920909 761163206 441671204 417663707 549687301 349425776 68563505 485547807 97300331 320187731 30767503 811965381 586197487 340010192 228522082 852536819 777956778 402966428 579143825 654623252 257292963 238878621 471552595 366208401 278897472 643314354 431023951 321562794 22779207 423244805 313891677 123007086 322080605 204753118 688963088 959539011 522388433 419730353 510866342 449412945 186146238 327767382 369450568 966979412 14868210 276848385 267475999 722397454 601737901 719077731 439466343 431943034 59586199 365680751 161694251 134425627 502315560 214419552 666692609 419523401 94320032 329269562 677192526 368362247 840385929 777311941 304987859 385525684 151915917 293501788 416450246 764268131 398020699 478693858 202633395 993503712 783323847 323628777 549895692 636909298 549213520 538239363 116731052 602596465 883413716 458788334 582032575 873036919 196227359 35509826 352010957 28445584 594580292 795816804 414550542 61484932 88088843 637993106 112132702 807316957 121724319 178319345 865262297 905625636 23683568 58734431 884397493 670592811 395048501 661990353 198712202 828214768 114662743 654210925 887287679 631161598 425435298 654915125 535528744 383085547 620276982 364652948 103921730 903795236 971661730 922481401 953654848 337956588 184610399 489332263 456900441 341681972 857104655 297482491 700294736 772875252 183220474 357534022 608957476 182296338 273470335 619725529 6408848 757883984 908095679 60333354 542662538 831039723 435850778 1324642 169188881 38964485 848781649 368669074 656034016 344078029 439714797 836067356 509317030 509087851 660338447 33238631 466663889 613766427 833761615 470572616 341067947 156498259 563679743 292038262 580006463 55167100 246607455 142869864 872816653 87803945 14926886 651167644 174499864 992656602 399228074 752530182 695288803 974658386 506722149 795863533 716925377 794848397 245843341 612781052 539061499 937078912 73433478 279909195 214689039 757635930 699260266 871105443 686547165 231626849 168180291 885601572 867929516 777316538 127149517 959562578 576467956 995849248 685870861 202473964 973180376 420009536 734404628 694778734 137167800 46802729 782260399 924568661 541554696 369657108 192429273 238018262 396071986 116771602 195991733 950409270 792868615 232459749 67328682 307972917 467295742 915965987 285488397 791170787 378219186 978692749 314959874 863283036 6171555 209878266 111256337 503307593 156642722 717684205 66666804 207552373 836456688 718090703 651824129 586741133 979735970 361455135 193752735 115219397 382217403 5088809 119113759 953887133 527829422 972922809 891795031 68256013 464658217 482714637 430662350 310057060 986421952 13738670 285990517 196348616 698535495 6756224 436518775 73580325 359697414 798012204 906374585 131191307 271444425 727596192 47321095 491774826 178375690 128168171 301569124 981040482 264673686 936493857 697379845 672586466 878237983 573811498 362885702 979028609 172221455 899569193 332428015 397545238 756473770 876652691 348360831 422721379 855725694 413991720 13275171 660579958 887995433 432080380 956108499 237753090 858697515 997364027 921245101 471720883 421778495 260003702 246659360 379094706 402942543 802116313 411569666 11119868 931947021 911771785 243037905 157662616 969255754 595389466 974321662 579982419 377722475 514045545 871917037 618587461 661684744 478292571 203741905 738593641 868689351 88029723 732126848 949753729 580300372 442734296 275152891 762503808 904309883 200635249 448476253 581456524 703923418 585861252 415610835 152225288 667643116 559567624 533878643 660147742 832408662 102194154 674164114 179164026 178819827 729424754 750981095 417412177 907664856 647233727 394518952 671612611 199988786 991765104 880226860 439381048 424382298 150499775 863413384 418683684 330412131 318081877 438832160 307468045 283740267 919517906 619965210 839189326 639482138 181624889 306682353 397242592 198964189 228390839 884627478 390277501 385675335 275771407 869433818 204178757 279247895 893738210 904512592 254930900 295610131 807931863 943863842 35501337 347689255 62662113 288164530 968624429 960571859 831090454 612376834 346577754 33745323 815028783 405376066 810110887 183956910 856113728 999333255 945922880 726976843 238372178 18412836 468310800 329597134 880330477 880670615 660605592 464016901 450930208 811732972 800060778 486512373 950420461 12645844 569876915 749525048 716027745 937101662 522010258 238257673 532389019 457322064 385915412 977122321 150463091 839317137 579469226 585942996 435817263 760269183 907555408 647748739 698069403 454974145 463134315 434887688 772436359 158122691 783181467 888027914 89829079 819570557 919149114 130862346 625071828 497592982 294925129 636189239 783019537 526582021 187195949 544928680 591196369 712826081 551668773 786890428 280025343 109472065 812352444 315499885 12720898 23776528 630636949 125108038 838230943 164220350 828728204 435217793 749201364 817059802 49862230 297784735 730439086 667902730 600738197 657937049 967133115 477074630 560119105 628636532 521428196 91383654 567140741 985120090 613224864 423136275 767173432 356849061 165931618 454545870 347098670 138548856 791286476 593242592 37186377 141762353 574680893 292804798 619950857 803773998 153566168 120730131 890214153 374824077 412489094 410067538 214154482 195195454 931505626 994738918 574362429 514897808 613942912 841265091 254760301 149465173 352853850 341892821 290928823 779048791 856275122 119081479 180855265 792932225 6512175 35982131 247654521 736464189 824014408 89977681 530351939 33468233 391317265 192519097 392068031 394577361 174206820 449012275 505279988 135018844 776419608 840671156 956065933 443616292 34752502 285055604 440175674 253784002 535030268 466723627 118072990 225817062 266004747 27133679 729699047 305312574 983819065 445329983 412465866 399541592 279396512 259195809 818791190 987311682 270275343 273359444 325252710 202434550 372089646 421477928 619692080 216152685 534445575 714248901 632650695 617588913 690268358 770322041 828171749 760313048 686457923 446339364 783108898 22475976 323695483 622291848 986080525 369570381 180500868 506857038 708142156 955992676 389820884 142544914 793908382 265667664 574723887 792665056 812918068 338421064 769558630 630017116 551554262 667679929 57052740 440098290 965148330 655631558 34458938 871507269 576138754 350511853 69235617 310601665 489267794 844009034 735072567 103700862 569211416 583301050 126530871 557895408 556878283 808169372 643618061 248565322 867218484 242200294 725137733 752200692 441473805 458490878 621236129 616879153 218248578 126086290 558237141 136581226 895392895 172547430 491616567 982827843 522270772 35267578 918502581 676251733 231363490 247026128 176389364 791548083 998319375 772901591 928427262 214785724 417671573 329476308 424137717 206324482 561371984 453249134 666542907 784044122 921058371 629799835 294808893 708605865 420623966 507859073 303823608 173455183 383116671 419831773 439981590 344026350 700354532 996687530 618922342 205839080 8219342 248498559 940229147 965873698 764747307 496414625 106861385 642559130 227928242 306913730 474934456 503401552 979925822 2340458 321233132 176640130 325902500 183319760 914907971 162558179 313677638 701751769 519622007 299092057 682639455 233324418 125405182 433613736 62982495 137902539 936049080 352346046 958326826 447865849 114163320 902129046 355219972 232148469 769225056 891421009 788724233 392849711 24379797 379744440 514668521 854944182 867775413 362435011 257055398 661756516 511840017 269462903 486059980 814193952 765343101 373564905 93492661 147957877 566499185 357374086 665698241 522543915 821662093 370704301 977389222 632925060 363383554 724109605 161619998 230264668 342135524 922550476 170563873 795880519 538475910 555396298 402002522 842260078 760195398 948857581 629890450 266730199 259693506 578959931 850599861 668388797 959873370 554936458 322639531 141010798 577120620 126529795 90126944 579859999 240826018 538165424 301399823 360226157 11023413 951913264 207094890 335468722 76858989 23316338 508462792 583939655 154835570 56589816 252297172 100986613 937476243 988423974 395406929 69520455 69321944 641643505 424258905 282311723 197400314 959604 159052298 685280093 310306562 757077457 828242738 553916388 125683084 317766109 160138286 510242621 914080316 222876452 69742977 926676283 630125471 99978927 380332870 192048502 973513133 236560958 60742739 29532478 957061574 397256257 768314902 698313737 601347059 828166103 156620136 15131458 122454090 901580254 76771728 174468909 221095055 340290951 866688205 509096100 7984009 158384851 51046483 485275545 688842253 37743933 338309969 804450865 570725530 492018063 810629031 948509534 190397353 537119497 303171288 619521792 506941286 310587064 432944186 605122037 505323860 917524377 773330128 384931596 819406940 271269365 770373804 320352226 904467748 332865093 907564727 711108215 467873949 925585392 246402884 145828139 305745263 723538018 203167065 777799014 582209353 221856727 824537498 949845492 387632964 657582676 541391455 13140987 358483176 347899866 863582608 265176882 274307155 128996947 95969555 39841186 804594049 885492216 113518297 968454324 884542589 530497150 72988146 114936738 721548468 886617724 246207781 571555778 944670983 301572295 391039493 781565063 877217772 459232567 73458437 185715811 234753069 722314030 371201408 370855809 383526894 141002675 621055763 73144305 776852308 541264095 379398787 784383268 149750400 863829282 13067683 282524247 574659807 750481304 949470779 56691232 465604977 742695102 986480349 670207948 980700503 95081741 470069911 446409214 527562801 379625698 764112276 516009250 38192912 260055309 727013905 416839142 981748042 941998687 582024147 885186584 809069512 9162693 82575034 265238116 98386568 901608015 123025162 350904467 143176227 371189409 164608014 278270755 222081617 658077354 816345664 596183257 693555012 468074504 314832443 727791779 15909880 288688089 793058134 490024510 451131668 20227988 436913031 5115835 394607952 898579343 446223092 879586194 124473359 516202360 692845445 789514297 496292008 643643448 471305058 908530332 146885557 761847901 157965105 487452931 830671734 286557647 140433699 879961253 827853378 988314174 9380651 340191456 991132064 725032312 645742519 252088763 388559034 138138106 401984035 252052473 186486356 763666769 660118304 476451523 303047499 468573303 986877796 758112343 854052242 903253146 831095789 372276002 923547951 976602044 402606005 58603279 32891198 692804569 115981852 190888957 262092301 271685537 463885493 89560182 385128620 300296169 960392265 800835745 519812077 536187379 454072516 877494876 474904657 613532440 367276391 777199360 499191393 622140028 414352652 345870549 224508053 651195709 780395365 161209732 738349213 93257224 976408422 326727020 458118334 899035393 927592924 525539940 602289066 651344816 990321189 221934010 559915680 704362099 697610963 154290593 970089948 804144355 197169615 899402025 911981444 138247295 254900374 814481319 843807791 231821221 642436903 744644921 700461796 655764036 236549240 288956184 367175004 328998357 456521357 461810740 363035020 638725946 555025057 70252576 132575748 165981276 789969362 534060293 507185956 403001865 999939425 476811164 282306643 223672430 640501433 565864788 192376862 150070329 811143812 772987100 876202451 895140237 399232458 875842943 489179099 964493516 37245062 36056992 196388179 632800325 933930083 203735840 189637623 56229458 893837098 593239180 493958137 522657623 506926690 718417458 345720158 892829915 154790415 727226889 413247543 274617166 831092134 342895413 138091561 827891964 695803397 610704018 828074824 909679362 285266824 486972932 785904436 434754347 645052981 448698068 238036811 286226490 873838876 380546896 708583168 16336163 378488300 245927770 298731055 459466802 716076919 733622885 416767279 295009237 72620022 553088827 865998081 319944629 583303344 752408381 639260924 278369022 520943309 348588535 190145496 32117104 574514845 993397310 223921507 813912880 952939660 702392928 880508204 688482545 128191074 930644471 319785637 350639298 911569185 121464391 676383009 722207192 174865511 484157484 900024503 410100159 431532122 439025074 564848719 40549954 752056102 958054325 369345055 327239939 474935953 364253396 451787141 527944773 25576860 666225523 721165730 788478180 389904994 653032086 304902933 312131411 870458422 852568949 452184553 496443151 6164849 921371587 828016109 57626679 742903178 378472506 705618633 715302411 844638773 953838708 158124469 589893924 581765795 735076262 11977826 129704598 633302500 60099688 396760191 990515055 21021789 331006519 420149421 711841188 45940415 59057062 60970797 492116650 935976933 362666705 217562257 56941218 490969955 120656360 861344295 959377505 110828678 897928827 347791280 519021877 668004022 462001287 441097944 978628965 592560664 476545594 933578113 82564434 655147604 299441252 672235043 488268697 767851273 448730594 332755458 44043674 303269785 995783623 57008250 380906493 927649888 871389236 954896025 529769050 430779471 166421718 417175877 642455678 730877821 646405678 329651827 540821763 354517442 923841210 995690324 83683880 88880710 271131245 749207736 817747390 716325747 508196199 536668307 337465686 123759844 812927483 695570865 532544056 664084423 778911535 868118587 755520611 242623800 867627918 414416080 586737828 177611633 875644601 348680603 613716337 830710149 660251131 515755985 263928824 153184621 280471405 665753103 869605960 166549251 534442225 98149992 831086059 805611333 974256417 670490281 99691070 476750417 391316956 847350012 168037194 578208934 361777977 723750634 334463973 452686224 78712567 319742645 266223163 261694317 752664492 60088928 423617486 673557774 637886669 123317676 922134028 676431352 71275173 998748426 758723339 823232533 395814033 817087757 232914298 968087948 955409171 490708842 880184727 310612312 454453876 310024751 926164420 953544718 588061936 578001693 633126432 485950139 911367333 424651310 929921817 538450452 865538540 143630592 758977673 122726341 478217307 628302366 738452429 284091999 370399557 160028778 572588695 528329816 384755153 32651959 479085664 691814388 578209816 808623616 107355826 329636504 65093047 696346075 705853369 599811864 373172129 52830059 753291335 954575274 586753820 951030019 868615782 317978510 160762282 141758260 501309551 652462512 328269758 743819454 547183899 39235906 844990567 39535517 581729120 951719238 160475891 764492341 38274775 990513011 648114922 764134848 594194559 477170317 679363394 788935897 109446721 657010224 729009256 601217605 487459408 594998987 878014740 369483122 241502986 427161289 939199191 300073466 290928979 306912185 165716828 539491065 480518802 696576599 266891078 78429232 817618879 385482174 936369938 62078231 737583816 279373266 271087886 13614630 48716537 958794830 751222671 32340895 478895467 145533781 615706843 340583186 918103648 481822275 909577749 962460875 663180191 493647614 431844299 25681204 130516377 865060128 666204599 984430965 150502286 533360604 983722492 684091570 39877022 863858600 844777602 56900932 736618202 369317080 820979156 292134402 553969798 50457959 927626814 104245292 788715803 309688852 204419895 398482184 953969603 199032293 734188764 718418273 976921393 446964298 957435497 527394210 154632824 653555338 360435367 667759410 688083170 989599826 67853893 670274853 980514731 304202661 260954585 457459781 438471130 417415923 12231598 472864410 383780600 496620052 775918060 682170967 707829746 340376220 302241236 683645870 394845690 77664850 905107663 555769787 888848317 322941769 755048801 737414779 897938753 842410135 45176406 329213318 259510875 380689738 883001567 54297196 105765750 648475760 658507741 825492074 389252623 61590634 666972103 819932769 316650660 782018779 265048874 519213701 672115734 483669626 420114103 936729182 930887526 86189580 116580145 326709776 880068922 334281324 630769666 597565651 962339503 230317620 670413012 500258831 306665080 266252060 589646576 305089913 3502649 377695427 248819130 307448011 773419689 230672826 218966376 4890063 763125839 183027295 335578382 184786081 974186411 120880773 503695512 530378496 888914895 421635624 72289783 858376511 791284696 388183925 663948389 308316470 31925911 282012690 822733308 530268424 150028078 585690773 384488475 33810664 145795493 674397236 13863533 151362036 439367768 337425441 269107012 582626180 690243509 802005457 954102840 442323363 865759280 861274658 166064162 946420479 787995733 274323738 620938045 597241797 998385291 139204092 609943856 93989163 93114267 188359902 971120875 726530113 699763195 377094064 596181815 354238614 558405383 460057573 530375544 243238605 957213338 418640054 303798513 46577042 938866274 783180563 431138923 877029145 91324099 521483856 939684013 161319981 817291314 423615392 307907986 906483203 718332319 104836981 861977577 360782762 230223490 164990381 661841606 947571788 715444127 407714588 320090717 376791716 693067626 831048606 455676684 530563275 19333114 988092126 535164681 987926255 575134286 945619028 156063859 932251102 66627802 238703538 868986394 251074889 66799499 894039057 561804934 454810580 815580232 413560313 839037816 26891890 808279883 625722909 869003290 371659188 578606489 264492359 379228249 798762998 875701748 583269881 701522987 354692314 689243510 562161150 126861611 156204677 545619076 169774443 270870028 110431998 660117016 129780642 472730197 450692024 842363172 969838263 110928961 465391951 20015793 647594942 457023659 701556894 391548517 704244641 795073307 352361161 882519611 352774298 312883869 250249468 791162857 536014213 776729485 78466649 192018476 951713224 722471450 811244433 569379404 525329241 610455543 452348029 875722601 901172485 967523751 281394795 186003794 590861102 837490404 195746895 421490725 585409617 986901391 228252990 456700157 626334891 450489334 961094961 617202541 190300306 781860785 770209818 557718489 714269130 621066869 689956074 916544611 707438814 128336819 460772089 57045784 386218510 273805701 201129434 809962055 584358351 762237199 685187679 605452468 253740819 239055137 768934732 612046140 775464128 667201922 34057573 650318269 770699324 819712094 387145621 162342060 71464792 996053009 315155166 904066147 91511770 449833187 271973140 205616109 971110087 78054573 763908129 406607581 536944424 903106730 210537785 695288966 40142789 516416600 209735810 827274423 518717216 125630271 651928286 674326884 519768995 518441856 240174976 514853192 249691141 975493454 101218054 533400400 990195111 822664769 756503076 926652097 667923018 470150307 468486779 796574985 68779982 492806533 574657032 101603283 225693964 975726436 410625401 716548112 785658169 750066382 347803023 626683010 671801387 127556748 344877890 542738599 301109921 946381433 302846438 607744605 490415239 162483843 669779438 427489504 939166004 121062696 173359684 478102296 336102512 540024436 348052249 367259985 113586488 275827764 362845880 644371561 657031380 487485241 707330737 701427506 234927628 247100346 968550043 289269843 502773473 224372125 127225477 839698907 58481111 90851738 589811600 432865139 194338807 364093960 405638269 331235089 953816220 360419371 577115252 271368250 211742030 208185570 677162474 941053718 642363297 421178109 143660172 239365647 657195520 321676226 691177653 101143014 540436457 653552161 127155507 20149347 199233320 64413425 967758726 602378549 915811842 505021261 475919948 694492432 615645078 406034266 769839 506221224 122973277 508566700 780600279 484255690 829480488 596381796 817896957 739556976 740208392 597350667 675455928 849769990 948451190 608571909 406165540 548380083 812789642 374758717 876086225 194448537 966624442 712522794 206699292 811609603 128123087 880257290 105175694 628739617 968482849 826519124 719064717 815446086 64312806 482917074 710991154 122046094 323537745 944786950 924502462 685900580 730591791 368653559 958862298 2686003 480994077 364325645 568144995 369936869 20395629 941307310 230248323 952608829 699179047 582335874 677875678 578931584 865389192 681049998 986611518 173867457 285559832 79555181 833826876 903934795 976771934 628931843 727525202 572494472 35043884 604629560 475376564 360874710 915474700 291557027 876749461 72684982 682083994 331752669 551275887 670468540 783274230 633482198 436032418 995826458 845854572 3264529 105583765 670367516 46171091 687210220 421014206 600854182 42052022 405652517 655894273 632901655 478753825 431879508 223168275 301796434 484827067 394435407 731655572 809470708 289588212 990832251 476503462 530071297 893990060 684753529 274523517 298606958 792645815 310320000 76924776 436289760 63532006 267067528 533467538 189244166 689888814 763425074 782721470 802843108 302007574 599510901 308486520 634304145 553289769 397879990 262848407 538930397 566585877 488076724 918671530 875883093 421070999 833011288 255812662 241782151 997417380 746288189 64689214 637776372 962846043 829725303 134926263 501965884 297417360 136963615 36291527 792872532 842928168 741844787 730717964 468881691 889854624 636076391 224792254 771974146 933850777 24594637 483376779 258116030 868680297 72970793 596958691 361365279 572549086 986233989 730236216 426692481 810838408 419713859 206645606 395649690 363087014 289034549 707352515 208309177 477603115 831422937 582247235 684203196 845507627 625873439 725196547 559952155 837823196 621686741 444067439 307586839 36322843 687648084 105114170 648852109 770193906 324741053 188526795 94042411 127262080 970123932 298077025 300553901 107818848 499152391 586657244 838190715 599609458 473933600 648051686 962052419 882942471 714315819 350207593 745809725 587759962 367116258 200654785 542552226 766188807 424855273 863369603 919677992 198992170 38496760 42734940 114594227 239087856 385532215 307312622 519021488 615273751 115429538 562169013 907527974 580471998 412251918 783287981 284320561 814549261 289305880 159852021 195381081 7133649 243512222 354605273 227761044 718960438 33197583 167168530 714932626 265493959 337883401 884403024 287672531 67001847 748678685 480076122 685085478 716202766 123888048 919041633 489972444 629457218 531896776 54381527 905328455 560321224 762193571 430315359 995617838 723813173 803847109 4117288 388203802 757022160 459482918 800872818 32539773 744410951 889007742 953092575 728321781 95476718 498218136 774070144 867656779 691766295 587853964 597819976 210072127 601456113 237126519 330223064 54386019 95083153 141325731 886973821 283974801 85289683 887600214 857792248 751586796 346314814 596806871 661390591 134854345 117926497 392553403 555090677 818283739 156101054 421003385 371623826 332597539 643562739 30799942 705585894 187193916 583537787 526822405 790311639 760139322 98225397 255198969 619924772 91603180 707454753 36344077 303052389 952806429 763869945 444740880 945442159 122454218 685213073 305999702 352488672 189581682 566431363 583646222 147739790 897734276 370654969 170665310 341432689 713767382 275702155 251058830 763518120 948312569 784219489 407306315 776065871 268689324 115870287 403683695 558715511 12856138 639766776 400790793 881502675 959584031 43029919 563102821 231815109 600232336 855032498 11180433 487396585 446152237 949580480 511292835 212419614 596535936 871293386 79811867 631885090 571665667 174195517 928917699 511660268 9678564 449031664 406107399 932535198 656401746 171223314 441848878 151329399 946461036 816613480 284534370 334243226 730862692 81750787 205744050 832598052 109307172 671119449 134911067 738293354 59071257 73637762 805390532 859629519 223205609 375518894 97703000 62854336 511096725 838265535 586248475 98238351 766231623 236726705 172436688 126076060 977032199 80707442 518673896 187845569 556390011 861499754 983085629 239395794 293746611 688571588 391572826 485376907 358662104 657262055 557005541 288764160 775308498 607779919 957713002 919922367 226111198 813130945 861468835 225806461 686563187 283576501 660129056 276078709 30645083 352354808 999253754 490395597 451619478 826884361 936570981 940350754 188709435 414392125 536495697 606831119 986306586 816924766 216024412 13329385 569078771 61612754 913296480 112545059 78975023 772445805 359160066 924410653 176748355 64253989 496005741 949646297 112113727 76190006 639284883 362282020 193189618 125358386 1232700 355191254 802511528 805448250 190240981 303442658 333950475 596923747 106477101 739565955 548162826 367808099 32091008 497614220 640656203 358202026 542595018 41901815 123720325 559439157 192457008 841711950 246690878 139705230 134123321 646300023 269588681 839364323 146141839 113971131 555587682 941401668 640893951 616005134 496628134 268233380 635814823 836800671 315034395 348974810 419092188 823235847 366305421 968787262 952888306 923149397 997031346 127207859 984716211 675006244 325291724 173279711 974305839 911971668 333715172 569048623 894108888 417149816 794850702 28483737 236164284 725242747 311951300 209022755 951217119 59070172 146920189 226974690 54195949 61195361 90595187 877983568 825785563 237855134 398072425 216551049 195082697 776331276 492195730 704555787 304380032 998756015 711237531 189478338 242172564 191071408 440641264 511362523 488332690 625511501 971592205 903789041 669028409 514328803 873299995 659369442 615159460 168851732 520365188 314688903 259262141 374797355 781446885 844473918 419550237 239858375 323523158 662278354 491316135 169313288 62267656 775628531 855425825 317675803 746056302 362232823 91917089 336157737 822759232 39665111 870837750 376821723 214428102 870875154 21946903 109465898 900618053 284488395 690929010 272242542 486153896 44134634 468694593 438396954 159724883 79099057 694054789 754678562 3533094 437832730 560646372 82519948 331594399 665470676 163938205 323521820 228087137 82558745 908408886 122241606 345209623 938281265 192298514 970905995 95831268 78447005 376707557 475280468 479085759 506736690 305022816 644821194 843189677 836564310 949534007 255593985 14019281 668070537 987806818 364711013 240117505 274387097 868614665 945356369 31618809 469513703 637716400 102989927 263616676 445200143 530889050 904534762 115898132 75273007 143303586 824639307 876352128 968207529 76138751 730534776 968325093 997776935 339823014 550613332 884254798 432760052 256855616 56701256 555449424 502140718 64121477 826622305 172784694 23575075 846652934 353747352 81430677 381722942 586859093 210994123 46538551 784702489 504484838 175474315 507017516 351942435 131011002 291816505 636787639 534438758 782337218 152596395 158462739 193831826 845784419 532210113 119645916 47992452 886665872 79357988 84633643 496509294 678579651 969747271 359907246 72447367 901673026 647350816 211156721 968102739 5542963 7942511 383061978 201382855 717671491 253275579 836557810 609941935 688063590 427250743 757304085 518155994 742228390 93305874 498501815 612753864 746773889 820572347 174834113 883721119 426269193 601054468 574565304 551077361 361831466 277965659 61381842 42561162 618747616 401062679 347272864 797614099 181059305 2186297 163678192 42073699 912020112 641091794 462826600 332933932 598618138 884242520 494192441 511550360 909681718 270320586 714264377 174604935 76772570 543363464 304468963 79510566 77189583 715764985 914030458 495195706 22506176 837073737 340256411 461267657 451820357 991693774 884646830 163690177 765649069 315257831 936087809 383553589 332284754 819273912 475991238 356993751 584363880 944706860 578173137 128498230 301369324 524833686 686675214 198499271 895803441 898723533 644751652 725934351 888258783 68492617 299124526 959116659 418521229 101085899 474822807 962290292 16285503 759755274 900857838 749378194 861645878 120774131 483374537 540785805 133849229 137254963 551420494 289226146 894675170 657963885 424456274 417375108 839139650 40519476 527098125 143695263 488667674 251946652 604598388 413197095 149341381 249097303 120772117 343930256 339078676 947711051 939907464 81527523 549918993 101181134 98995790 723789214 753625530 91882260 815230637 106069523 422435842 155747691 539520454 379854292 41178920 918101647 406142415 436832219 533351269 364840122 776736995 396042247 910573175 925070338 150721329 283832557 547523662 550554990 127792863 876397358 386122322 447832493 957937445 135164378 912826939 419234992 656240106 524175127 57689417 286236603 807337531 511863398 974711540 840072270 502678498 809468667 684848295 620099855 222908924 644774833 48606313 922694480 985234571 308749857 860899517 382721256 533424654 645690451 334061628 195729286 543346615 317704034 408032918 141449469 168346240 802866971 479109272 1025346 917138971 713551104 770895743 853283408 907831706 801615729 351970094 632706916 211901074 281778338 1598786 264398737 58880137 475662844 148070145 290924551 296642818 694279462 482386826 31364294 89121416 69056636 556620653 210851339 782669610 953288315 645328789 101391769 978716465 699357307 986631064 166492514 241608693 118710014 85209332 397607353 134622831 671216672 429147457 709442057 75946327 967062193 665205848 55255957 930394930 882187899 662944189 223775495 385195817 17454907 173661553 459339600 470591445 852705874 296779555 36969926 433149992 393021554 625072000 407051451 518633795 20430398 506966071 117242225 909822168 968366780 159580851 720764934 591988390 848155039 475435455 861520136 837487870 736911211 620534047 223454466 752900795 292440114 65457577 227700973 70766977 735054971 435503784 751991744 491749779 366963189 790607721 925211629 309757915 466984913 670223478 617645433 291392666 935786862 202186736 506716503 611273821 117798255 364328884 19046346 387856868 251391941 235230204 115208027 828487437 960441540 481672753 903801190 810297565 781688379 245261508 169794373 390438387 31732658 262405743 30254919 989895525 861516264 546952109 11524272 989753917 768096677 503984269 873872152 366020146 867348062 251294318 739855944 808875774 172586689 846937356 10326553 521116783 901438734 614658609 72797177 821341270 9195663 95931261 246698814 419787388 162682663 808337986 314348702 524282958 705547294 298170828 546772187 66592044 405139877 650062480 286518287 178741610 652302847 195038936 928554198 849157861 3255529 682318126 348666661 439386090 159535634 250026267 95253743 900299546 484397135 44154230 237645920 479780505 834855040 679908189 465210911 564440498 407024374 900804014 362849362 225484648 746076382 683261654 42109297 923738800 526472120 475225231 565480529 399821719 254602435 293137936 517454468 883087818 730302787 957149017 251628241 246870808 780624359 154839695 607068678 417656753 753535882 81902584 620183636 517735373 940271610 869163341 26499689 554453560 38071930 935680075 236412512 749411218 820979185 907992411 479396806 669617660 482810641 422113259 632492603 141848997 161826693 625997513 848430026 614750655 903786586 87788258 819975060 80084475 289953153 498425010 110633746 864023600 483760164 530463932 428936590 672156670 435062579 889006454 8765052 598465457 599208822 6291537 319134689 188596785 253340557 583257766 275430295 181124104 406127048 960562770 761597877 598602957 111444062 297229872 21102514 782620600 376203904 35158876 545633994 426270898 971708812 387806292 128866415 191041655 99329715 539061249 162256722 525218768 254500385 755049915 50708653 990017667 268294071 404131599 469228713 704142244 397636162 631929517 273968642 100082537 653705158 855726254 944097914 239856245 308600950 963177108 278487989 235129672 944318998 392316265 270598830 688714898 215940971 675583056 515879583 431009174 826823447 364765616 876983540 622729306 119286896 342029294 447336260 566069122 544649515 672117973 282292055 412554677 177636672 972343321 589479154 911667578 873416569 858387627 381192503 907988635 71666685 919459265 371490458 767201226 707249333 577307805 283310658 466069651 720895018 266542891 250804838 236916839 597013336 67745587 337316593 18509538 897240204 85546506 593063122 858827227 313787243 394393368 730501446 63275643 714925768 859620223 712116638 316048160 586867766 961268362 70171801 551129621 644112564 555533636 406843718 408620395 881610510 330037396 189212510 357523225 144888408 974066140 449787538 398258090 917664182 586044563 611759780 53717617 853574823 394152569 449032725 585766983 457395433 615652290 49212182 511408461 853373262 771430318 161789240 187511291 409082464 256295484 242150346 893326536 328997905 3485687 30009805 190157205 10874374 51449808 665035132 766276849 36802472 426278495 151084446 731494847 54655523 427972967 530054866 775196714 624580669 209211706 428444399 572735986 498214936 255212120 671116972 909262341 121199467 374955206 41881010 229891561 335909260 279400370 729485755 704717473 573956535 85181519 705753169 962076995 794563207 414531477 867009272 166256990 687990757 438973121 480284647 522948873 415540920 834449303 49998875 153152904 712972994 13705411 454788271 200664410 958694180 759703216 730165942 554712218 951601822 438380578 210388414 331865954 449647065 309391686 650168826 445052800 521660634 253867192 108635303 446592188 653570548 980317177 64489130 714684516 900025813 74937751 371295975 37237244 639053664 512385096 988567747 163965644 801068346 549820216 42307182 499585728 194131649 404467630 754603877 364377743 616150706 779159039 31784883 310609887 772689088 567676715 297993676 770505308 717825411 63183036 747629115 713772246 158931413 520751722 251757449 331871569 204520636 407428435 719387778 460910102 886811288 819993386 878732205 92397876 511409788 727780433 135701996 760570139 100648724 765875452 82819040 696665993 566790133 471628198 592741580 711710893 385489152 251155401 39252613 956414683 225347826 859672518 558643477 408114198 619669691 876673005 639537647 204111593 273403876 744223707 290553674 13139463 78523251 828385642 699332205 179827236 355835734 51038926 717313283 479811011 195486595 998387603 645787169 130100649 846249299 785281977 484507909 259370857 692444446 842163292 737014417 196887832 393453883 731436777 602625116 244452772 598194761 246351296 773105472 294055287 835227765 302416031 53947294 462020243 734204598 318950713 538735284 353463984 294501648 351478235 77727550 947177059 398463463 421471994 18559198 680950074 890413980 181204299 485854370 157658738 965216537 437777205 53193345 542956502 768936999 83033674 412651141 486490887 263713010 731080272 22122156 757021782 750643866 322898500 840472722 30215070 32512642 883485854 874894173 567385006 315701122 155271948 699829764 666797390 651230895 523175963 771702559 142993946 218332587 285062430 714867887 126599266 377497782 343620293 538347466 786027067 20595582 309478588 821425736 56916904 180994535 447675679 842068342 137847878 739788329 402116728 437288376 679538565 26673824 286787956 851780281 219057213 821318323 863165124 637801960 433331258 493260109 381753818 104882076 841833714 329903322 819313046 219077510 315831307 178041964 55854104 945743735 697550338 691605124 706683055 416451300 420091877 701567396 852355254 189990934 805960747 869787430 890167336 199500178 810482835 725026876 345217771 797865243 692496963 664882519 773703355 9931423 602247292 810674855 468137548 900074776 915795592 402668319 771675845 563181572 944005799 589011873 740112448 83335506 709227914 193794040 463716386 20442103 806225724 316929828 357808373 22084347 750867693 20904311 788676345 87048330 782626279 706250410 362990925 667479811 411620223 259174279 57644493 555095786 505961414 67170189 144101240 570341360 440519559 913254678 320783047 555855657 375139063 624438697 726658574 33352757 900855845 906353010 264306349 800335539 108284368 770691025 2942064 629359477 525030385 905124627 962829175 401921130 357153870 254232626 201660538 386074027 396483210 294098299 830446201 175053278 629377893 230225697 682131774 660834963 820312047 499529467 429843777 142318326 887515961 359435249 553297636 837337827 144984443 800505717 840381208 922411041 953265114 488519438 732393609 601217787 547859946 731837829 412649587 213372175 161301050 583479434 535314206 747807748 843171031 725197049 463929132 830491761 12773583 837024629 968644559 57540001 383659451 460053344 631189744 141764981 333634046 415631843 799960002 60821504 243516592 127308011 832258113 161307841 812505917 256894092 394314886 607299949 90363887 133370906 977461184 250453129 585939760 973548963 870625632 976197007 952622867 7576664 483852669 175633830 239967273 662339910 545368778 897507479 566667055 651189090 534448530 597349615 507942059 533788853 431925622 121314463 564378792 665310952 86682317 895030122 710624280 372798091 280569177 175211561 536219254 689549296 670331295 681255163 317053281 774823730 133317652 842451341 322876960 616550214 377179056 836700130 938674241 241146841 454258317 219786759 57783106 857454510 283967871 614225243 79606644 899960781 365023371 878492826 903242893 154062691 408148787 125496888 647150781 256608769 414718110 482541489 783965888 937685548 516692715 839257842 614037783 592408147 181705220 165100805 668319244 654320103 96768926 703263547 371813836 636779206 945386817 491810286 582861663 267225442 887377506 689485193 127176594 327512665 471363393 43703067 959263248 822505689 158877326 951632059 175271926 401990384 997986820 203773862 638084743 889175305 502066840 909910514 520661753 400763165 688747566 727474239 121522037 504696489 669537530 63231072 555290892 856582101 738713398 100933221 414392989 175213456 37703934 82330811 971260737 865016529 253835864 229851345 943058621 281987434 274855605 770329469 826522224 952223143 158598925 25124022 140008610 336770041 427229375 565682445 802532484 253379608 545538554 117420695 697975865 373043488 937485126 250593 518661115 214599003 523458573 633760267 475371453 657953383 602025263 407814419 950458394 642931291 537592489 427716684 353854146 538703983 699296574 174357126 484538159 946092386 20415847 390878335 461347443 897318856 945070884 921999637 641901098 537676786 453451324 187442860 468987330 831832902 985915460 394980011 244451212 279746634 457661986 855316011 231593355 85262931 276698137 633981387 680247884 828912963 803536079 910373487 371353601 882201213 621783081 736030823 574622059 887016315 635359783 339003235 302993855 143299576 287580291 671424211 482199863 48710741 211699681 107149215 27373002 836285908 400352986 802548661 939495553 939180634 865720486 975840261 301891349 280299496 536778083 311818091 646452076 846732238 116603414 868498656 250873488 185311195 105575787 805909412 115168320 605786013 403082773 439684504 12927404 753829747 322195390 355623793 590297717 393073745 261838479 176832181 172670869 531067132 327408219 237608072 633600213 203317793 404578581 836874721 237938465 791202037 253837158 187307691 149273758 165191797 687180636 283677326 699127650 795535923 941073483 916146891 106474859 919025886 500941782 871128 828090541 586674941 661483616 440023359 333140237 638381683 706090487 314745183 82410717 225979631 335233143 413318043 403470141 605637511 804277958 974141571 93529401 850601688 665775080 564228878 321978211 497882951 130924907 49340478 394850378 702794155 561080377 529843203 225372692 972133055 864317173 847439352 538355235 514814963 997470557 854487272 495244141 344520730 771039068 147880679 842795345 797394031 60728903 399901164 718906896 126701657 601909893 870055417 377868696 551537572 250923726 48879393 762677349 204645899 481174696 436276194 170592929 755770594 525441587 740233627 203890272 190044022 535356081 288829381 909464418 275596749 795297669 412118939 284564019 884882641 29065080 543719183 552666656 56187196 117795112 115744634 149121150 95906792 109301085 45472623 397035441 859612336 652699327 972329887 307328476 368364622 402901977 232955408 719116368 100435125 683757187 730802658 258034324 389143336 688918501 567131200 568510487 710375029 731339339 930446912 727973038 247940855 865917758 287166713 661497110 576032934 107007850 360564308 751001050 578589011 672778047 605983874 371029801 984503490 111833192 113101557 488842258 443095721 719679078 868635838 811610106 389884804 852638768 791094612 871017650 615803206 298631934 42379987 186212228 888532324 149492406 441868246 495533988 898211260 826264425 681474873 356218253 616989918 102838683 565600125 731008194 313604800 912255408 739191536 319770201 556537561 247540898 659503522 802720764 776613546 951269824 52486254 359016539 881427980 329024144 375874579 462526996 197344478 31789794 378481127 81172660 248569525 263942750 267838898 638110328 641040626 69298269 611322040 591837321 988521156 308861149 398285263 834269688 110646751 30851093 358859779 496403249 157207465 442982695 314851297 239521525 936872233 214517224 853056651 855706982 106072987 708841908 38874825 234422674 235376422 86128182 424345568 169610403 472382845 637030080 27768905 244567739 991356672 620193655 896352386 770515191 59527577 617699492 669738953 667818147 344721765 963920019 860270054 629755578 786877153 950763040 304443910 603094734 502241364 825204029 835170228 361410486 209769118 880250397 510935838 166969665 920414781 101621472 597207378 854192773 373108369 22560794 988036897 892117868 641818024 937208505 498535516 404579299 568348886 433365180 178154685 136539042 511991408 850850500 608702062 901779697 149086708 488073710 124625070 631859462 147091658 906909000 135519095 717660321 830092674 27777301 157787702 775597414 951852284 486547648 812852243 791148619 601108995 766738257 441365945 910040381 309099180 974075044 981401353 476228259 308600510 394808813 443071537 865838383 98711763 371199989 291722214 40320101 289333636 713401864 774828298 128357232 617807285 213511090 784114714 561494045 825021090 501304925 952136015 317718684 580394015 750158265 761824815 747643726 595358063 192871214 22931153 210114838 569770323 40100618 453554254 660347251 577976883 626504578 396691680 771804509 960385665 232906702 538860008 353787613 931796960 557875483 667319527 156751728 702789903 824754970 277365189 768480214 249463955 910107127 209871258 892574220 92026266 864363647 901539266 880379859 330151590 746253640 167569317 295977091 181919848 895029240 377246031 870102932 266501776 949462128 535816726 51630122 420694047 693276767 97519903 846600043 303831032 884799077 581424627 786172403 21729373 874088414 528079474 223793768 682146893 688533376 895827807 46236413 964502303 654232669 592261903 85986017 417153759 218170785 648821334 764697440 992620257 819115389 488468254 614233767 401012839 726740766 479866040 100961435 473331977 543940260 653752958 768030546 600095758 624802647 454988784 552914054 89573878 539217341 396754207 718785838 597225757 868160902 875014396 406070206 669965655 10873051 922277025 557137732 742843063 467927218 268149923 5231747 788922833 657816304 272320468 730801780 885187073 524298373 974681759 181646668 727000361 41476952 289297914 539618029 67297754 891021149 728338659 209095921 647784737 360388593 169686887 110190238 164645414 287115418 644088729 940643676 802180892 613860904 717133754 432276318 927720346 42191989 792204394 605236145 90206573 188502354 649833243 988154073 812333583 97001678 774239422 500133999 946863246 192803350 684364858 411657622 703796842 992622898 962879427 189120046 671934976 982588162 60011000 799138605 34573185 552859139 151335826 978342416 591537387 233407791 611108969 519354295 295369617 870366898 530958088 271876492 18490534 593653635 327567935 630513079 627460308 55962159 625000216 621878540 530650479 602223513 879108042 298218887 81274679 15401865 337199432 541114064 655089410 443061837 71303821 781610136 416914954 859572022 593627607 894544484 147582085 370342226 691278998 775225357 944822952 935709693 521630040 956999208 4071676 746891396 113953339 757789183 337061772 770615907 255789905 975994039 553686914 766264857 105404135 373710648 593473531 536831476 250680100 102310564 411386905 650281957 15268953 602549099 808284894 585006600 329121077 287384164 244227721 366047385 578720709 261810238 958569302 343688837 349428930 491620303 6366019 381483149 52613234 293662151 928003926 7005233 849426052 256590800 913032200 644345354 584004026 107842344 739364313 906401290 952057790 121724522 76427556 922023741 733768188 77315880 178843149 358580322 820844181 31002286 404775766 417162724 615079416 766679257 251406439 907816200 243663862 482893409 374167428 736255145 873109600 902791721 543901508 399456238 790291474 513864999 923379275 749213524 840024721 107102776 37254966 827601412 432138701 971223876 205844403 829550437 797408776 920140203 661487211 147452443 905884369 618967471 213908490 236811700 691454340 99485035 453535487 218235366 685115634 362527073 148902479 813816202 399469041 44667736 9199479 468892162 178991835 428977040 691565100 820151447 516356116 985398101 396634413 339159405 944238594 670928699 852530027 541327797 681451076 554183909 218091503 714095355 281644689 969031889 288802438 656730335 502638810 436132590 108181018 239444137 590380559 78836382 482582972 904981503 648993008 280798002 759478311 320326127 578814984 641316028 80924110 819186934 3377226 131416841 280628605 444387713 61197659 734786053 658979584 391755894 428964616 792923276 266907942 671919376 764999202 329475317 888111729 546408429 208694513 383825081 833224508 733541427 514107224 385253232 866103330 396933071 630286376 105733537 984834769 527264621 381329366 749194159 140757472 813959124 659662376 695020067 556906491 689456837 683880196 113243671 436448447 122314976 525445905 967082370 226180323 695215738 116855308 715615031 960885256 697521158 986835083 854787465 978588419 856916728 989007445 942365621 317293882 100804798 737555011 772413860 58644247 847526339 331873687 583795440 498322807 579242578 511701080 794004053 914744482 480574167 244057358 39781447 806849252 502854430 523247660 610057201 126471786 235664010 665064147 191431745 679835385 928869471 157774706 45857887 791291064 939537404 389531041 743209225 685842259 909719496 813097321 448841327 654184917 86566253 430396723 111932408 925895530 848242057 162852887 483120972 108448423 12637759 857859497 6318330 251427663 58466763 158800298 197353493 533243039 534663316 880204421 417014007 129197204 809541448 8055837 712014517 220569823 447982008 238449830 763637356 625196700 882922768 146098330 85222809 169893032 413463894 707379191 19559814 48615342 536528262 146322110 564263039 597516530 393828188 293007994 207615607 782439468 126196716 934771163 437100400 670120729 178982772 943177975 129202677 373780079 742404531 185888048 629253553 31670918 847344839 182016929 346780816 386314829 144305385 202260773 313120222 602033374 933907947 480371995 822204461 896501611 217672446 585579728 636464587 837712584 832695420 970179270 149906481 58253547 749240851 38776236 599075209 535648353 148594192 377297282 830195454 249157899 890222245 782454605 449650889 803860039 324895704 798450312 247960654 410590703 818821776 391390071 406307965 187416327 250018242 588908100 318576937 441803748 427426016 286839134 529653990 762321438 258906733 40844163 202422027 615291946 943429036 144329517 947462819 153491559 77116787 120316412 569314135 568229406 688152683 702038835 99775167 278260484 951318860 108476649 620416544 987498156 559521355 521547999 201363718 494379400 544903891 485908685 274391308 116504888 169890952 9829863 217741328 404604280 987213956 689244635 308381826 260621964 14803751 981487656 474973555 841716444 467259457 103071753 606483854 91190825 743164576 94504756 516672512 374303619 812605840 585378548 873670051 756359270 994046493 64958339 905988347 637601357 215499752 348006401 100714693 959198598 544132161 567253295 290480458 10020421 575096026 416671287 848913398 770367702 645813218 765906054 683089350 737471732 631253638 949658107 269793796 67237345 979726270 235456715 437119302 411437423 524747900 135698869 937240315 803236006 67330757 312155378 557757751 838284459 261146792 797561330 481605064 987585940 924376168 244533768 137804028 330525364 931872811 187309064 798521808 440230558 782756548 684872658 424844648 95624625 914344512 660377935 492385992 259205038 668682130 362599986 567877251 713624222 534970039 464790196 288202935 908479643 428795288 733462552 22324311 628437826 709292282 358901743 474210013 61467260 755948703 798639061 355662812 350377964 955497136 879157731 298703134 468476976 936147942 80011327 497125574 992857117 884083507 940583565 938142989 896824984 613442008 635737992 15413853 353099795 502980704 98016146 22480226 647560273 87739692 170382193 519327352 390029900 356167261 142466439 174409926 936123294 13453768 495491413 391027586 220345239 815532163 55734651 968770330 445263885 416862560 164047537 94011933 492397474 952271508 643341780 264750717 607354336 98403269 116226749 382532566 177421884 343842093 771967662 951265933 830976078 542060587 513703375 294237240 828516614 471350328 968121051 763141523 452302252 767426566 824537090 831529116 564008611 835183886 13729547 509748622 898738083 291304343 527668509 829157991 435734656 577707417 81837817 471160924 762938554 404629757 996519698 954929229 651675571 958525651 584479669 296207172 663951775 299760836 355362083 838716235 844442188 675230463 36973514 216979726 682535506 592765138 135245523 366505568 646754488 753700772 773288879 240523476 243326181 634691860 786582664 291041157 72759681 892033511 600053486 250946588 319909894 292281203 292417570 314614858 697624030 735722858 757326268 550225218 485484534 111966476 740989803 804375726 989151865 294570755 254640920 788763741 785181490 390871512 359464114 49153114 458151072 730753186 221859828 552382930 380028112 939362577 414693169 295684946 951823245 80789580 88403269 763176797 257714770 299136191 768815849 577024938 321586547 214077913 632999095 891529331 805757250 616401218 750754624 561599656 98622966 666791888 621181415 268167289 840877095 935678873 679912717 292618497 917729792 990744687 577505193 862369363 514700082 141466835 270696396 204834153 539238731 107629707 407255924 558826020 981654715 81459772 566744480 26635065 599845372 261659119 224705472 749658629 4504340 429696119 150352276 192639052 89698126 662129478 578928096 429978945 531359670 261014728 392895459 924458800 948075540 168369956 778577222 852706226 865510199 171672625 615725889 760962347 570166162 845560644 159308033 332517370 947159581 956826435 428412167 656529835 643668436 807345081 225957313 604639378 848281033 605430780 736540551 126248489 30566823 161220098 565239380 841153039 166858969 798090616 603095005 85003008 762100014 424542543 120857422 662482397 735311682 755370055 339234541 689956496 543919183 763989161 658803859 189029238 598510900 800548200 342804686 542624489 174477934 871030699 253009612 560517539 904412863 5969366 680888161 473337743 718402433 292713146 698491668 823467076 216810780 980325208 588260041 390145589 67567907 386500001 619207802 494619239 934513071 786949035 494167085 632798291 729102290 352185588 907384366 490644332 131553006 119697939 950638083 156052468 94653415 540872513 785174218 460840047 293129878 418922411 269580736 681426106 928176957 500681758 258757604 898834636 241015719 313443388 135342939 601960980 552677204 566360672 647936669 918640033 709457323 934203439 628249759 318311179 936969622 800930689 290528982 529177180 665435376 917636402 274234442 969690969 795381892 103968519 236227263 366019212 505278118 209467448 375658686 474908676 164586302 897960925 706353855 383372669 891738095 932619966 791024616 6881859 2453694 66693572 780224467 197085112 223411329 919870299 795300749 84221358 828926600 511650454 617623399 697170007 180679356 901361986 862271392 594062625 923050962 796969235 166358122 5380620 267691820 343486728 409204178 265747778 536991526 144138141 821428716 414731618 899432909 585495369 559813830 311969290 185071391 142618988 143874354 268245200 650107902 873854747 958386472 812518495 866718898 553350193 20510048 951967737 581070199 321847935 149716926 103793111 737006986 404969749 131721642 96275910 914531265 201238646 320653377 206191037 76401297 967935088 42361511 458006498 856092061 427988234 602984085 453671516 585031264 554452776 864688934 323638807 867636987 174905571 93438110 180869900 42131649 834826575 225676745 331141488 823553938 128960196 414985458 367192693 266393371 51840990 968149243 531856792 683637540 316551771 733776739 483352781 131655745 408136712 232793176 676025783 637101150 992219146 177462336 192894532 118464062 127175121 136200274 818597819 529067559 820449707 608961310 438257609 816313028 649997820 589936717 173885633 89862707 389735666 386217539 346890841 981810349 762556128 31798635 695552863 967830652 194191417 466907403 690604177 886114608 151925835 621852842 810593860 568458892 588464510 734354212 100031046 650695844 483829484 777347571 194991334 488122266 796392530 568359962 235266045 478403566 365123027 55601170 487959326 719227726 300294305 668686854 463614996 955208009 365831746 739021001 519376550 839749727 691627614 158470311 186653 474223739 413436419 905092358 555802512 479973070 146970236 880652932 376983716 827168261 426846527 442791598 479140147 236997840 952230853 539684309 298536415 222141868 689344706 729615485 961657579 625581582 908353149 529970660 36429712 869789561 695613779 425090628 836931474 227153781 831711578 621080237 149098945 564950979 262245114 663438771 591492712 139041015 417393265 133656307 91436681 100931431 703313850 311386485 281326379 442311797 44591140 722549590 439658403 127726394 123015419 314338649 626009597 482381273 578558758 642639926 962752729 67066608 393221691 266801648 909033637 836583137 339733565 850681227 126799990 694428299 115582949 861675936 273838817 827134777 720815538 960005241 844645838 288219342 631699729 878449885 636925519 732773920 196627378 503588293 212358167 713358647 985304721 58067761 698334842 701507804 387772677 469911802 821201700 662222792 59288434 210556144 540141272 275597081 610817565 756108965 7726251 958285381 20052553 805526493 380541655 755654337 453887446 222920049 170954618 127030848 717325667 809245968 933792820 146696036 201613449 402557029 100412959 922158842 436578680 180848204 500008701 433361944 176494980 865572614 716947216 820167751 225392788 658652677 674252452 815636958 145716087 371963034 371458105 336402109 152472455 49006559 673701307 159230619 413478026 326068704 983323186 865058212 850111181 383875091 86271590 495636352 752297842 157293387 520354080 621024253 377619910 459138620 369833073 413683206 247151300 972437281 751894809 389554101 393428269 33868965 572288120 522030885 676918632 513811502 632816303 574537522 362964083 6146380 483801328 477455668 749025147 610260847 902690432 881313710 274377506 630873170 241250894 295803662 980730107 630593044 500572417 841009120 902427846 455176970 523144086 400555165 6768929 616956845 153737961 333665290 518519727 288883668 54323433 223933098 329192750 993020572 323672568 454309417 345908926 611744737 643333541 120009310 381427782 421375947 399666019 944902055 470206599 763063238 690763824 432086677 253091959 726430671 330668395 108219498 987823091 43299202 124195013 364043094 924791476 766877119 644194574 367370015 252278490 342462018 417485995 140122137 920206962 956512138 977913346 815668333 57584572 978722460 920127556 634035189 175566860 685872064 216694113 89944952 969736707 720187978 923067620 984897191 812887438 289739945 224223533 409403276 169539759 732882267 558609591 590133283 902867035 644285501 349827352 253731052 207191628 431667741 785533864 474004158 622463505 446532724 292699634 517483450 864594224 142610487 237684834 996389887 832640040 713450964 641281520 62776538 914275771 123395384 776853569 871556178 819307099 536801582 847415906 388945019 410899469 11760572 841704786 281958237 406449750 147214513 705470084 476842960 595869523 257163428 202509259 882095851 893931084 368137930 884528698 343794050 450186084 381700497 184853149 299802620 619622395 463171465 200476416 944048396 636569535 427887629 105037220 43105448 946491466 388787995 50165601 688129109 736645604 852680248 563740774 799915957 644886856 198318044 658127323 878718996 890878270 133738953 758288553 299314482 630565007 581679686 835072660 893226605 563104984 674949277 806043444 145585048 478393619 156570990 361457136 706341501 350705024 261903339 381836950 321127993 650957894 419705802 203343588 594030303 986242547 608082259 284479444 274813768 719022491 962357302 427376160 735804643 206661005 263269082 149223086 156050789 55913498 431425417 725449228 414487709 383119585 815535087 769550376 655253628 11240732 445779169 800773277 2090177 457137511 588870854 16336766 914108791 855543629 379067753 383203125 447495375 5135307 326093947 110497270 172795350 114117141 228726112 416550906 158977085 774526508 635745421 448933029 611964405 165579806 918457605 555143280 612502028 705325381 849172813 17972927 69768788 166024624 54644978 969327216 369855866 258853858 585437687 349899494 633670285 76949121 686459959 940199778 371407395 721773097 95184714 788733918 849283912 113630873 811719985 977297293 756413592 971145523 692504685 921987606 391393634 93191380 902573949 278230922 151940687 437772768 96599627 96683722 737932869 654221501 952221750 53652395 970516872 88605666 84014826 559451627 315807289 351230566 671188391 635158791 967387828 838104041 997727619 1747216 562860439 424000330 735852174 782631889 773978815 196035891 905579411 675140231 122332969 175020583 955521335 99942394 211592852 161167152 920842125 30738217 619295903 940801422 691521042 446637245 495095775 23855596 410684350 677088061 189142652 927795316 377615584 137207242 319090117 534631875 890262597 561910730 220580429 968307690 786186975 326945903 957193500 310958503 684497672 711112068 681756687 93215702 521607394 400633240 595473652 317918667 912987874 214092143 32848856 569363247 916851490 588240872 22625051 722811907 119060656 59231600 492892657 626846433 368833207 767658631 362143643 417194254 401208991 584565458 620991508 774966009 968752071 56096074 336059459 655628545 589714140 546108802 446611583 519652516 610565211 503173951 519807819 249806992 891237577 171111769 159794368 754631766 759409122 174409769 137636432 403821361 448666641 719857154 592924950 870646337 784114572 616791244 630652600 173333048 418541122 169727162 397912011 18419284 655332741 782881225 478627854 938667472 128460208 738380285 378430570 399200906 76886134 991622277 207200935 941791821 738582367 905848693 389083372 415014051 307504853 909576137 557868440 819683327 414067780 105755126 927742452 471750301 506155899 268745136 492205383 556266446 851610909 884720874 929254928 438711969 784197121 824962511 319596893 344034530 471414882 927727116 372348938 568432232 358364381 519884915 70168058 459689813 314377750 467289779 63531625 443630295 90520711 793842669 357236391 656441196 305751204 942636942 959956677 258686209 257804762 126017977 682457537 759850905 96703840 210092621 12991685 58385057 281051512 361523224 675321695 212796574 961544836 731653902 182909256 183042419 629289906 47712366 431641757 457878205 281151271 386461086 433267146 360132034 762209135 304460802 615775551 737454391 459808629 440814007 740779688 39965973 101910824 243033251 610782391 17358901 561601980 879349370 909582783 681348972 432027306 580839443 64816313 713566181 569745672 889056822 115372835 816148031 815210119 930987860 818374269 688282864 295234671 374096194 362264412 65975408 852167275 261659762 735213756 472771193 283122829 543956670 236710488 21678412 165279663 134603019 76457661 969296356 979020851 832506515 158844167 192584056 94448438 279149297 61001727 881131945 710119057 557841284 493453637 355722931 992411059 855491323 663736478 266596346 596216680 222323348 931757143 685189507 734755536 445615671 262224676 332214216 596537735 165032463 792712671 84862573 798020178 761041607 263647833 540317111 751509960 821861896 795050960 327513188 659634065 720076253 754856188 652844517 826846264 353737863 612946024 669901359 854529874 594008731 70024038 268686265 380274269 33905835 793620093 609986213 216040881 255430058 924215403 410364629 575523805 556507809 206905024 823255957 900782971 934040414 169531327 254680323 216257122 801638190 92843440 926099558 538325686 496779081 918152151 988434556 957342498 742221102 476864003 636824432 547862298 318883359 635697964 950760244 195607089 619974022 308128085 470585299 994979061 317813260 673938881 979700275 4504036 581458507 738315877 954873868 946578442 430433158 123928392 405029110 225441587 925124646 13995848 340787104 994721895 677928384 773401889 855976746 803372598 481842554 47172575 826171416 547925412 144685234 86478318 160881934 964366113 445671233 240512001 699524531 272607623 496426529 685273335 631899555 769220720 913883602 713869827 498760679 971816433 928329175 917157622 800396085 349238980 341317717 678060981 315209612 312673503 304529507 845625585 306445760 391611955 808244496 643331350 667743008 227032939 151470571 178768437 113453049 910778862 262405282 78251994 695610586 870326917 194859238 464603202 488664625 240550243 550888592 676763785 322357223 124173033 542797710 575950314 904758607 514471818 337620724 580052958 394726150 107514338 270185525 360001181 775173233 260417753 6864213 815285656 850273932 80913281 421289836 222224340 593789727 472434775 775268877 926264042 404767010 39565415 671558630 836497245 499423455 566296389 297273025 242447355 254042573 961066110 987038774 995107937 700135897 308829278 865802317 247021115 593412423 774979653 257904002 174639129 102689175 632425364 174638141 229259458 424509997 225372017 371344332 227223361 243086491 217328131 595475265 859369069 84358991 217103779 61778048 933266656 44916972 423527127 701098465 811154527 775827895 5368671 934555144 928653820 831732773 291850012 837907743 667193988 24545548 357812554 588828221 287663115 828601948 3348447 611166115 278114223 439133123 117405464 397842468 595384896 118204659 896455708 352716104 193580202 885323808 981710820 568930965 695249721 161945535 144254781 321128262 122788429 696455058 770399103 224787961 426660163 128951664 142643995 426361252 754124401 83344121 111997670 270719316 769624663 508221824 143309592 938438315 150676078 861999974 531407970 139846550 163610958 768035576 755019198 139214602 767527157 18567562 804057502 29379883 33501492 183674927 448281478 930463580 574401632 325498152 590428220 206786160 608731688 976367758 661944918 98140526 462938710 41357801 228806786 616799312 455682500 596388514 214984532 172488613 697842805 958165063 448815225 553515389 115722850 281133453 472121434 98661722 197613836 973998179 48074657 729278215 827554043 102888651 507393556 943866625 763656358 827066993 907138350 618128980 384303546 682240955 985117944 710308688 850054565 46129571 564055824 951575855 905498925 348292970 360057551 103974511 310192891 887420170 983990040 852720509 787748155 722334533 222929291 115279210 206878215 229137202 365040788 223344648 396380120 515552502 699210241 711276774 555895203 293572592 337045405 979374087 818568320 896853588 525239423 830941117 133939588 899205622 860511986 518742764 832880191 711607198 737270809 210710053 876509963 895789155 651916471 974650213 466668660 231801437 848418366 142482212 355207717 535197638 304763328 914481647 456720233 112280747 420479798 733803930 350570732 475180826 115958679 950374840 974656042 38321749 446826006 255417669 286384306 900105225 165779211 981795369 903837059 225734155 584549544 533928109 650246071 178298645 386134774 616157297 276128072 861642231 745958686 773242368 285060210 788694736 440728006 653563372 242078141 516706002 914458821 439461033 114370813 300223937 616486449 927323923 741425976 719393727 401190984 146565537 359683678 546633486 333605086 575055085 659621162 797564633 832365834 701072455 953178847 212754178 204472607 77358895 731173365 672384117 599483708 963079114 461245407 443472798 30347791 763445346 632760622 323749589 696618536 572764637 268121267 40146021 662527052 820781422 392907122 936974736 461899414 961490086 384005240 294526318 298287383 220731884 984983685 270190841 93165691 225876511 449313721 656349103 752532116 72573857 16437896 243426898 91297547 329575527 125395736 950428273 424065753 342492402 66401498 779485116 509987392 109325825 373407654 646106999 907406812 283784716 904101897 223076095 402531039 712177147 146192063 663872492 655470848 599210404 429137969 37862394 729595703 465332935 526262447 672725164 718936093 677192833 603906732 485649937 252250291 952268632 720397628 167536518 530454234 579749625 531967907 231635347 756112559 591729547 84111869 818035524 979567103 484951900 877527777 889494847 552774669 194778889 176853279 317446339 889964970 490672936 460678883 506655717 303398778 780181978 742168644 201860898 891418814 330516632 774979376 964529445 975650128 907604952 346669277 160944702 839240453 652274675 394674529 764823972 708257324 625401555 627600328 78851267 353337239 352579633 380101912 222988428 326981412 864661223 232353882 530429229 581407358 609662306 593292117 521199591 322410146 503286741 906236208 909806767 885518704 779439709 785137351 229553670 628475596 703927459 805727733 986616321 566820750 749891810 182067936 260622401 770039933 946313005 250018025 43270778 627266882 933855684 837449981 175054706 600773596 374152298 974625924 914567010 4264298 418782636 785063177 442053066 392885809 240164971 725578059 29004318 807421852 864604794 313791385 882848768 864687208 119416578 345884663 777171298 19803676 785204948 81055807 375447631 533441556 853911469 157637332 491232281 823121159 318953606 88431107 592748372 237736041 963158744 529189306 849868629 402009248 721758844 200932777 685025259 272601620 30649597 738952221 638179295 983643707 370292846 763778534 894734495 776935047 830310043 345892074 791294435 859938423 357670770 394656855 363208787 716375209 378751973 839568057 310565691 367096633 979267071 620534964 397701720 300612868 448776450 466914403 431133575 600263321 998460027 242026577 936510310 695464803 412575782 276331991 700446674 792671572 419418139 747153332 193815370 267198972 590749916 917639319 656969993 665176235 691831323 354142577 459691477 167552175 163764717 908277057 170451405 703327520 741972156 256735223 550338172 970759600 546884501 882871037 384789668 314611477 311076154 726865127 556065959 433211945 310968644 644625557 442456570 604559954 754178421 718952439 445228239 525689297 709942741 94430905 383681376 356837304 382009915 901794515 521121169 634134458 810846805 387539764 195878396 586543069 659836730 892036461 80138334 556820631 751391636 864322025 67798590 313416256 705505165 763152234 283135532 380210828 625961342 813786229 399162327 259546988 543995414 117366189 290889496 340690825 308865887 671269046 451860693 628281783 506811064 845342041 265317908 266468532 197582994 883661645 725118792 603337437 989546182 725721886 370986512 711651036 296117315 229423982 714283236 436876923 494480301 313250704 61565142 442657068 484951922 373530555 497820657 648658557 495674803 893599426 538299309 555686895 173021931 865624417 246309011 319519911 144144107 878964341 239649639 456470806 377848816 701497700 176755096 474114680 750828698 469022595 338710627 288219550 405881455 726666421 777765093 82947386 520422916 587763829 610140966 383334787 19859887 132452248 969588956 371635317 200594810 297235544 543565528 851887565 935944435 372000755 554959706 926864449 304889922 150507626 630338063 287982441 480742323 871100940 64614881 10234982 647364594 170341098 755085719 901999014 35276091 177869545 122105228 147192729 284252630 530976829 469758795 923145021 244255931 234352232 238741422 521390953 126431186 558722088 220959866 555037711 991130404 929485722 588988499 655513943 186981115 558125974 323920860 848532285 500770713 297800404 561398208 946909426 253729608 55436607 669420344 464521640 721591927 805797245 706916198 394879350 73416796 84158201 980487262 162018131 460384334 379986186 185452453 984177849 236729073 129158998 167805345 821047864 995219726 115201126 672222317 140694890 521294834 565457695 772825359 607745506 790802622 903125716 272650767 367015759 76413186 598304645 188878409 399119768 171399321 153617006 933147732 629054338 510508689 142498514 789416854 480304541 955315538 248096253 754502518 970250448 740718579 300254108 450895709 910259342 76509347 170458145 860656194 664670880 396832282 849790191 558423470 295867244 365623085 391278497 449023213 846014407 881482419 376725008 475864763 699150563 552851039 687871327 945107080 159266577 623957249 451100692 363969550 748346869 258964883 630999894 670040722 607665396 296718460 763625432 321938003 274193730 371977218 121191863 984242549 978178956 588501617 967764472 675938523 327127887 338917399 394463429 470674838 895621850 544639275 802053594 157801589 12636084 13886803 196721856 49492463 147093083 351080418 315366163 410776773 862791425 29594405 453299823 472536266 968924565 623312309 389607107 945406325 612696976 937111646 745979467 934606145 294556228 659872279 957671537 140522068 688840260 854021260 897804810 308554917 66397765 364485383 977300261 557841067 441035521 597584348 277238776 496088262 668745534 933760803 225734400 504388769 910178826 377821961 661242239 115299437 834121256 675268218 876839253 625582355 918652892 702474205 649516229 618343376 310252810 650141488 527092377 934098572 720734892 717760369 643387599 777047336 691138725 482403197 283433856 486675190 932501336 774464996 375947289 74030674 697203094 865092990 637657421 900491141 759411240 753692023 888460972 237585778 192129350 526685595 96955440 263273790 647767649 893300146 481222525 617786372 685126755 243317690 504310194 445084319 511616358 648290690 908526342 502390142 397982718 896917671 426588966 549247073 373154814 857870864 276512324 512546681 901464334 923806920 698597208 305756186 639699265 769219032 762529679 993056902 147007046 983897420 79932463 456074846 170170474 389023049 77732884 815555517 32507480 768920888 668451855 631072009 506177543 486757067 242816430 367370986 172878394 371799199 160323967 547688801 568368507 78388669 829054681 965037591 22079614 807899678 634256884 513836340 998850657 454645118 781069623 748137033 566740528 700001515 646431927 485537154 921104278 64179078 643614318 802337996 226557339 778774831 464480507 506450999 749860248 816243034 139870493 803657780 645630282 545622026 603189395 275103132 644666754 822312333 840479216 107625893 588329612 160165733 663796917 231883326 187209318 123069654 968203314 223775171 524510460 736255957 772726606 111789322 747183131 81357451 697676046 213974616 213320018 832705370 790969009 571005217 193563371 501396339 173360239 982067761 138931463 203154029 477490615 847464107 418129731 368609810 945660395 966251297 150387625 843624388 643113437 652694279 116496993 358914083 779202804 446695348 331359339 836269538 409104342 175815280 427791054 784117085 33002089 307986781 709314547 242980702 158141851 692720127 57421586 132349522 608251424 479750622 987659969 878245994 949497475 82298884 41792161 779985682 705760548 566172258 470222884 778957307 670990147 716165433 619961137 38407501 876868223 8019114 215218082 366843017 806742784 564223863 47611561 65536123 453202022 767667908 930720441 660545156 428931429 55726639 573644950 114826848 663019845 354766362 991943187 583784595 87794561 136738320 362721585 780365318 408503367 677182658 968207304 71339328 929990655 83043194 484209360 50031895 572100129 854917323 87562504 763919139 431969719 682502642 280420028 696976553 713365871 762112598 953793402 605713512 143205910 60442982 289192803 137080763 825037791 33437872 856183889 285699143 546930071 344548441 460023395 389056370 173215646 642728327 253158028 268514349 939565578 668946248 915425341 306106888 315386279 10451039 951508511 714191120 404031914 527672968 127565178 539493583 832708960 369452066 711274771 13637269 852338058 156429784 120245395 375987608 672147091 264826917 73504499 128962375 332234645 621904097 847785076 706764866 115048805 244776252 84518771 244713763 357469708 12529448 96371848 378823348 215096037 257895651 664758664 967119353 719849809 11728716 220200711 787543367 473297063 903969409 441124008 803358775 11615944 803267866 175590453 220634296 853086885 717666166 365825138 839105000 167418815 711345615 953103535 36063056 839744790 131760930 827855188 75485609 858428437 992692046 387453252 512417686 131322424 496636270 703438259 248670222 877804994 606877330 126447598 745020083 650896649 850641338 278913998 755257484 666718292 463638535 546531045 39618843 682741762 515858538 425911672 299848066 818642548 659437449 762388185 306878612 164201531 218326105 132642953 11009841 903755178 982866912 513172617 915397599 371173134 396302029 275542176 769555333 462798009 990146007 122489377 756240777 708046583 590746251 29441762 676376938 275630399 456656739 285321512 267628468 666123765 418827043 458861485 625829171 238427980 480188711 440637373 397705300 885574207 32086896 879501582 659871756 994187645 382271943 365678252 900359861 418267043 294424293 68880101 907164814 17368823 396234106 64436000 680817157 971032636 166441432 69191310 326401667 729769065 26881053 565338065 677603437 818017305 88249092 148239266 323528523 283489994 483306843 172357003 583766703 788066363 556424825 105037288 833280552 407493582 768710219 461226932 511898121 854277368 478536509 62626240 383459782 599911137 792130739 30507870 892678973 719796563 391735719 390840558 753964505 469189821 788928935 589958826 4897347 88389375 18959092 927710249 569885966 710145555 901709299 238194825 311572770 985780212 891414845 824819212 439331165 470273149 78884720 686700518 656509797 283977233 472462625 546851777 423253142 360145058 307169354 29081710 949536246 480759937 932772188 709039717 851588382 848953816 743191309 515906645 711718460 663223735 467647178 749324507 135724524 835123078 181729238 575917552 248955056 989075559 489420739 966436893 418870110 626698332 247450449 72061959 275948593 857943292 397866849 505931097 582962637 52885342 149032900 551184133 694423158 149580035 270960024 834179241 705225657 608094049 225558102 706091341 770278318 599435099 198469548 482528240 535170425 948605360 223266209 330015036 507934603 887998917 640249242 356766016 409648221 461238896 165901250 83442978 788545445 465190882 523781789 496665329 333279015 488318521 53177468 89908147 105284157 234570485 698082097 544689479 250203460 703732221 74684533 311331862 882487297 502921102 210799090 140614247 406059786 532020968 566645613 939618777 575513820 851102358 913058551 669104322 599714851 374162700 221504529 216713852 128966099 871869740 761182639 577078459 371541674 401113411 481258849 595810623 842956679 330551958 495104245 106700052 748282623 849318816 487893306 223282710 171316741 570531277 724221513 764929669 626945576 459645545 359591209 305177969 692304301 594462597 666555851 556159543 390714234 228709604 436109376 465123718 107192242 266880379 803188965 997533975 661706312 863754647 216989649 505031665 658631205 698396501 219384203 79899039 992117188 815046048 561782086 356012866 517418590 609078792 119099668 633471146 606763419 144321248 419571359 319515898 586564103 379930630 547125342 682535245 244558544 609508202 314828440 554421927 907579870 439912294 608279942 129267473 524184050 265194750 496301496 968290731 624682691 806339838 625549147 555038248 288808270 70934924 27482102 395282373 625337777 513798309 796509694 494817274 205944932 628056007 483805617 846446817 602669790 150544968 478778036 98009385 687447154 929826710 663369726 770669410 831323096 325865852 269250943 850638729 923774597 242571120 982077091 670745856 421073504 230683607 418098034 373516225 82565383 120241753 642706749 224419262 253880375 69119206 511979363 940920169 440596065 794172003 203014999 569195977 875966080 552344766 482559686 732865719 319953787 228976260 498882288 978808159 738184394 570123615 620549942 491312528 997133681 57950110 523524049 945369070 819499072 267915980 8846243 984671176 978698338 580988568 141510059 440912358 663881153 958227516 265775041 669767206 32953654 846074460 636694865 386727774 814966772 840757893 708569287 674217838 734419110 118981494 326746620 660838382 207876843 542256181 78358596 360817397 257921637 376294980 563485821 148353112 710749834 285311328 158669838 358679737 443127615 847789591 983614255 668186241 56750906 155671617 398582085 956057997 377853907 172458095 269676150 606643592 989088764 668064805 368076055 335953061 220956197 733653620 575665612 103827455 432871329 956677208 303571351 313167852 911166637 828569273 652388240 733402180 59807258 897593532 506987070 62816732 497461797 595599312 476792457 579340969 78486055 957171456 416765547 257108654 818639764 336848625 40487210 376322101 327144631 861041808 52875239 935216745 631247993 650045478 592440176 333404457 286131404 750256290 914950622 884226557 829528578 940243425 362551059 124431648 178858420 528319766 319355278 723075769 461961583 546598632 803500964 385246139 575130723 549263762 139132177 473030245 863870068 956266326 147975846 213146472 719178235 499198741 267724956 303657720 454596761 349923389 9160263 288770711 128410057 43405636 558395123 499120693 37412572 309346394 535568859 808824429 416715376 273534017 668093551 306481839 481120278 343337952 311088161 156544675 628732680 784504808 989603224 53241447 546958153 280390184 475982776 540353894 781990089 931668520 77048911 427737032 14072077 492132156 717982862 447497703 251627776 12950637 380044787 598125758 820561491 879672579 515388653 883124958 546105519 136904641 764636130 81044324 996366766 143597835 840293816 709228983 397480744 993585047 106169676 207325467 697744778 584984033 835762343 11269044 656376899 323372706 109400936 947175551 166615905 348100830 31643958 127393491 431691022 771721747 208248395 327958431 532515118 323431119 421223888 399731461 727549726 250707766 497872607 909745374 104432975 974896255 570144546 372451851 519302583 990646501 363358691 757929484 504415211 759058242 871265252 971013831 933606989 752745009 614559854 597224514 116828190 118083399 209975158 617754509 368782773 187404773 499847951 719399363 580361832 663834322 647310016 29463999 940457117 312128299 189133290 393984374 404060032 383444047 55011338 366675432 244421150 554228809 395631771 272845676 695231269 803548628 508747788 97818958 405221565 999874844 753838900 64464208 210713941 659606059 391067497 577850199 568036977 646853954 623661706 73486740 766089260 388655575 255735662 246530630 506208403 784677461 315311374 160324138 454856976 275764779 998604075 909211183 670294607 309065038 723517719 763765901 254512436 726449751 807663723 9821188 192442489 942409186 667607110 581639315 931001530 305701634 167472978 918268634 916685223 865258059 999126356 724055993 706600133 855007406 551594441 83372356 768185159 330926326 551652038 288618903 803259236 605192826 934146705 781980171 332208470 955718503 943482386 732138072 290691122 242426449 762594948 830856596 553081299 608691649 22784857 943578854 898854046 171710894 23370230 280220946 817362818 19867981 471933093 570705618 87909707 906849067 322298464 124405898 130414509 993498692 849302971 71893891 905775759 816780703 902929686 437800803 8453335 853484330 923940345 145546803 353999189 724039231 167762136 973072059 659284601 640551140 837830574 897102538 52626547 993420395 780934752 85368953 129137221 77431003 82523106 668578600 952334460 56818173 979381577 116522541 969120998 97573281 531135056 658417936 916063313 635211427 254781752 964762449 50266749 674259861 203725372 303636715 755912230 212551277 600262306 633008928 937212897 391413887 278108406 101494760 84061167 819259910 322530625 114800708 135787444 992475441 98376739 104945921 285044738 530577405 405711872 886997362 514791786 699840473 127294341 129106965 617366642 488333589 389327727 756797176 643081682 942134348 519028142 705393467 541008486 740355534 536202045 473521438 691662350 932889446 19965230 843957933 73399690 975454786 920925569 405762780 320662533 572075175 93375703 417850017 411541177 183329819 737058973 544079278 619832809 697204733 884988941 319879318 955876772 332903871 790240464 901036935 933083334 836144919 68597979 468256798 264790520 761430962 96143382 434250486 615608465 950967142 587443127 97073984 61626817 183597295 790332573 586230814 969992525 235852504 878575753 309104205 894959248 294070568 875266798 545548828 765879179 352404978 734326915 449562654 541987453 9703210 486055016 233428854 461904129 876097921 904558070 875055442 73914294 759467684 263628856 145388226 632757284 103939745 490814748 263005796 527761966 73082154 804943117 595498370 866473221 189045233 830562570 446548619 220771122 462662740 854348478 318763302 904172919 353793527 800923679 603731666 608417957 159153218 424303364 843275002 172114074 542143631 557808057 64621302 229182144 897240897 826888225 415457826 303507865 298613796 954637539 11648843 168283809 486585150 229192861 171489135 260157221 210925152 572917498 799157855 448766749 571643809 381886460 654752586 991835875 169462751 45447789 87396362 413924785 122667231 891239381 926976262 298409062 901303878 178183796 605518402 312550093 998221450 717197724 78241849 559521414 470596228 621601508 109864225 964466825 242394277 913984227 654586438 175107012 651149697 387878831 587330836 45852988 71670924 358940470 348110840 508800682 278971701 631154241 905570829 328828922 650803847 281581926 434686077 513757532 398450596 182423181 861734406 466051933 84988176 504376121 637775887 973956786 277135601 488122379 453583919 425936064 732457160 961873481 83258141 159636921 935306921 737068794 468580049 715865568 137471156 580399757 457075447 256049668 678440686 205645266 171414868 651854849 677141031 770017636 578984134 773294060 901305259 733988277 57797395 281009192 877234846 890119007 377293169 472398262 380103646 332130567 543990379 354202 701342814 800338753 235120527 171021051 864764276 456108761 472851288 531541933 48287657 620955302 949665485 466180201 644631301 179453988 282674492 759692663 863037624 612015686 376627889 601286689 27357544 614681357 993397425 987641898 950648166 996903749 395595822 815806563 800876038 644028697 547351398 816051117 538910326 533043836 323140522 468911172 438844463 306242244 878665212 183767825 152156032 896411447 982678202 365884380 147535545 924677104 435951596 589651834 336156850 193190972 844212259 58744921 565841222 181996741 261363192 431657624 847629345 207227867 602074780 554122722 294521263 140884890 113397382 994758264 328515717 217205365 855662509 730763275 824630431 618574362 506625826 960680365 62598450 932212603 356929795 792867366 111420283 532854078 185854147 405533267 36098975 281907316 480570075 609676167 93935564 967700557 416489147 228821894 225869645 71697375 517174922 333422856 72197925 208389797 737576710 949416048 169685738 740845518 513169123 18772748 549545978 197858179 603282423 920372209 361519960 997463300 152223503 98354917 75231802 441957883 272087562 571682787 413181172 176340549 377403773 172163574 779721918 128797364 913143008 627956531 137016134 52694967 461526605 513534202 370527202 488341329 167631417 647470976 453247164 861778557 418725523 753991943 642228411 65971968 652132928 28832079 562023874 117349574 802769617 884433122 938496201 297543898 735174557 493713807 193682437 983605564 914280326 998689148 673625784 431501449 353144627 254237439 798143181 164069378 269442158 598311802 407507472 645248306 605967579 439979820 542001044 86590312 425836440 992277275 76599645 181846750 568889572 956898271 629848252 394794638 969007232 91368763 522333918 693316613 865052733 969467283 854797227 751986524 375049803 824556861 29073961 187747399 452376655 939720098 519589025 687915790 195019348 237961882 38229277 144244372 324011490 544861252 767207863 386745800 723878794 294704578 305794708 810932349 922483033 398991455 526545225 776848540 283757524 308207536 225633610 761081915 264487173 790264747 595164074 375110426 928199041 463540143 4137123 638031209 802321509 858420850 823260594 120440067 204335678 57697606 982367527 670721767 713351686 912830284 390819014 368728995 783399302 933108079 750881942 884862823 738445194 248656592 960077600 348565622 521435652 991112353 737202716 290086409 251298716 368462597 205914312 750491408 188895144 477680510 66031649 732928431 34228337 84926539 56337935 105187212 447606237 303298339 107177074 869773791 978456658 121471970 573986349 850909544 204399129 52200581 60180404 729701274 181902219 426269588 970440995 829839609 811468537 308522142 232528610 471668976 430587858 191864526 69742689 195411502 752328110 309672728 64776524 775548321 644986038 298246781 246507728 752219624 685159459 965916094 905761970 401907185 264425876 664195466 511788255 231302224 254548210 243338789 941603572 600107786 141716941 342460056 995502223 300321800 292620003 189907252 846594858 327203513 617353220 494278968 3132231 492729900 281599160 495879772 443484329 406594515 8658415 87884347 662283106 743649626 478857513 18638005 410192347 384003450 753270101 8559373 140302143 630374542 198837122 853111789 699849575 121566096 126678304 475548405 575217991 20080915 981882308 861346174 333030620 558360755 3567144 109420629 755443166 875725067 362839214 689392280 35958235 329523573 630901489 311793010 252919286 643832389 959344938 617479765 656661709 282603349 716386396 989208427 138370084 539016593 804055013 262339249 78508382 820222453 816496922 655688867 290161914 228005853 131777400 720006818 819300040 328625119 360346719 631712079 537218525 285014863 23651721 753250057 77486352 897139178 871412078 750667602 1378088 331369421 757966600 372025234 806393182 348997998 855428821 206405024 678096134 927659159 96925225 842305889 633605123 334289866 823152559 923325582 342726767 279201199 891218169 565548876 9052312 283997828 922231234 510519218 510111691 429615439 733321870 596351756 766303164 756425778 771843943 908393180 737792172 867756761 216607111 885619858 528909983 285734021 403631312 740144440 768435667 657846325 735558811 387498941 136784204 205044863 15696304 277098494 327756562 707710263 683746880 281840195 973291009 388164117 732986589 658003738 87085982 111281759 158921372 261827947 249967595 238484183 258120264 724158658 18788886 734481999 116242273 12466707 25192830 588886749 980407048 651000697 59861578 422219692 409540870 22661104 919599214 574419114 156278247 350200049 616580595 869876619 330502201 415621457 265208472 778724566 191087571 228263773 245762163 462696850 432312584 803665754 83951530 995140481 236245862 577766465 978002828 505753569 113301155 782299366 987138614 200220594 336289891 878401880 631911843 705323515 411199522 547664450 958005996 509788980 846495693 566816046 588351963 588826018 776510395 908251136 123358258 535022717 972529556 999618244 803163342 871450107 925913199 528554142 447293830 218481684 848603098 445803737 909488329 58345601 784239266 326220251 16575392 899709380 419695663 28315507 81355994 959464300 414476472 785022063 216968278 799212604 845615039 248049534 17024815 976775628 221119961 509794190 70890671 343749406 113229934 957932204 367882851 934923269 28270203 164615687 20408429 706138133 394305176 459039861 210934970 74754476 360335645 363700099 566999325 233211842 796928291 781393457 715204668 944398173 288255619 135589262 928740864 784469774 930672800 967132807 177377763 105317104 802514991 242274111 297658597 431625928 128941781 845453748 300920749 548550093 282159585 401191077 955404281 914763757 861497513 863204317 750433283 413495926 965015185 954362285 917295918 521648128 259786505 774848307 123035813 217217787 19085505 312077611 649241621 162903524 549945934 750472875 570574782 501871373 99861327 500807648 453092955 252668754 152701708 856897746 719442943 895589214 709499505 869891703 417485026 499537082 491069789 745529685 398597983 787672623 176164864 412941444 702289835 325620591 24725347 560895226 57519420 317428711 681174880 609960498 368875476 507515832 596141855 410023441 884308886 795684671 338327681 332744412 343038092 163819264 767743747 69401504 946867734 740816188 575835342 112984314 472368713 687063202 620801404 962933518 124760935 621846708 189189372 153773371 429974979 357083864 428772167 782645496 877291781 428609588 517153840 863385505 349308125 970692545 615596782 687187253 447343632 849284507 811491085 789935175 772459214 72097385 465134548 157453895 775217109 914269043 850591633 357972718 546690827 188165398 761967160 699113922 852988543 446828540 309717779 179258936 129909652 23616337 773418223 436139553 576057035 643789795 783527433 623860409 356502583 456186108 899318609 570149068 73610472 22856717 950624834 70345573 227166522 175464494 154819286 250187965 852308155 213611420 556008549 96382126 453406559 435279957 869190618 571177212 163904415 114504167 528831866 349972613 658250538 711463470 511311267 461988026 12808808 51584393 429442309 200738383 336947401 90863316 736056282 801056863 431606337 249857538 812787016 251723015 300586264 195292345 337599982 904673824 427880891 959692788 536216428 826756160 835376394 746110548 865412133 43783819 623267946 242327303 29861945 158062695 879396366 293536094 989635136 623880682 99022770 741874479 728895205 668074267 725369940 593184546 326422183 370314353 13874985 685688723 786135179 711394585 263232334 74126752 532351180 260249009 520319040 791128353 448983594 150567629 894657960 979345174 667652133 557327136 816530044 138518872 580049262 440456532 397036786 853745489 366809519 568348080 912170538 945838359 487061952 135748323 387607668 695584082 245304114 574672053 499106147 232431733 882239491 333083778 697678690 352521660 984748254 985596562 985123638 360885535 682027414 757687583 629530121 969117135 885976760 960554891 321354052 909972045 87080747 895299625 600100616 657984997 55080310 527345051 742937267 849837792 434739074 33527561 559348684 707345829 290460080 948090028 229657189 545883095 749851058 2392552 946811296 177727098 37160790 543005106 401345130 561864054 505566681 699662485 38874225 749605403 510030761 321611554 498639127 68595449 844070183 952502009 965143396 15189060 805001015 794192906 9380441 364661161 998061280 517745077 183224983 272913487 269343315 593119985 561455843 82426879 878173288 895318279 526727934 641122617 428836789 603878068 533603104 154309875 448144074 723915314 666426314 313323780 19752467 946478713 526686927 614978126 744849382 847407285 549652439 136408418 854148287 776834144 919062481 475437798 611819921 285310563 838805276 267160019 989839890 73673277 927654205 922441105 939292330 823269164 568153110 630827534 339575266 85342075 555199108 311877544 83853808 885013671 389793609 57070561 885797828 412833065 504522359 336253554 567763015 203967309 853542122 298269329 186953646 579690116 670899219 10652995 98224191 594867042 269135145 15595569 558039678 632486555 636333022 572887531 210676613 667369878 857842343 219456710 786208637 359568327 677135202 909553550 703597849 145469845 571924414 212212080 244649893 58868015 473673089 803754173 66032015 978455078 301240099 289044437 393513576 183172632 365817929 256905666 119325663 681313655 606550763 12518884 737740152 107980759 230638876 17293826 887447906 842043409 69167259 431732072 377362392 85441823 461020415 814756607 340243941 366570102 441954322 90865401 441868515 931311883 302752687 589573177 692546873 771749910 758749611 236659568 47636631 507846005 69009506 104295699 906279669 736317056 885988068 504802904 485025678 56480365 498899195 449814255 282809739 794567635 554370880 393613352 626996593 905244154 275814266 303862872 669173899 217142097 453912705 848671173 296570439 527096808 925917174 423185423 717024625 642702776 125451643 89779041 98703679 258524037 618697393 754331429 736483445 579460348 888061893 911114799 319954898 448086178 365867747 672018252 759197148 4391241 868377254 7203952 750743233 647174715 476795530 569483412 137339509 555843069 140917947 771672972 47644175 730247793 403905552 405582884 855797339 508471680 232766064 281306599 807313612 463335680 201924373 896308855 126473844 886726165 315312035 640873671 191781066 409338134 715297708 747737946 348587440 442836273 889324382 535163243 896177342 939119488 594926059 751099525 823974040 726505155 683736993 120407619 389545695 443460233 494892561 622953550 573680030 105380448 930373023 820163550 811398275 28241488 209202383 415263211 411397208 517086789 165277603 192689249 258092301 158749875 431559102 161834453 811579558 355750117 442255784 439931955 128990852 642982422 940394407 257007706 161566221 790741431 176541591 84043931 424198715 146032039 168139701 439071750 746218079 563248910 397797548 980270288 118629606 543110809 479585974 920802238 306353359 74664281 18382501 641720483 743278893 757960988 763915510 590751073 573166476 802272584 194477435 980635596 730661566 480413596 14855733 680700157 490739605 923705295 744127472 918509641 498094001 814947722 313205445 370092250 172816605 47696658 718708676 101882768 335152538 601187358 446963938 675910333 79287402 444393533 669209347 615822757 690436147 5802271 404746272 216346531 688136326 776583054 458929112 622174517 954195457 806543896 506549360 86068535 763450776 833914921 904920075 452615303 664343881 963407268 324930327 339983857 325730360 627402664 828941321 775084223 606571772 588093137 648841489 125373687 506437102 137645581 850223220 651921051 693110941 454225834 944726872 367565576 542492156 563902145 445170051 1136501 156419277 95970612 414920092 351124798 820317063 188847904 304872349 996050742 961756504 601279074 520261657 723835546 850399507 118705342 457506930 263548271 815304899 143017094 241616031 412438620 879171920 801489091 413279212 511099089 396226491 249540893 557093069 111171712 450939096 766545160 658676380 745723860 741266222 614882090 66340304 392665959 108992910 212580622 961598709 848678422 88324272 396248859 774177476 522710150 292804962 822450342 776090821 224347327 410643089 87913761 191987767 396588976 173258701 45788562 801616519 87626942 708108548 576383990 719675371 304718551 572402966 250520545 889568337 81040427 970269417 602700225 486046288 250111556 139798737 188391677 203135613 557865110 211957487 538060305 118153538 59391322 740183113 183941640 773611885 840346038 997064933 448073143 573316236 349282985 175996687 450288528 200890834 969495043 379393518 894369689 706441271 215891552 963579704 837542748 162178917 105710165 107985116 809719498 73754260 377609521 198374784 995205376 560178241 905854891 444197401 366189127 913999051 105997854 280942789 663910282 845196711 401970300 298961750 940842447 97426700 848103240 544116612 684990430 791492247 332715291 188677697 189920425 391320394 667595723 110629075 227170353 245605724 675465572 423928709 136489190 709046937 717426227 6752697 140959070 577629291 464813742 563729467 464463287 931589409 702051339 869524107 370986942 679899243 533201808 763092417 410700778 591185182 846520455 393011679 52217612 202037201 634743076 887083156 613605024 910607386 367718560 216925827 409290957 904529404 3760996 96529109 958628235 802415651 611169240 336747131 75878419 124673669 483373638 302232008 945096149 332751873 549904781 185465932 354772827 881309626 395557804 292124762 347962515 952950617 197765546 346901347 679669766 530890502 283051073 64466415 320353517 283985088 137220295 176752284 33648948 842415267 122183630 696317333 552799104 360148457 917142795 614491893 78093844 443517893 140040152 686184445 986180132 428188574 962474283 491334416 729901049 862124005 208710376 609886291 18348498 366651286 450235230 877390579 843309431 264822663 896279054 2755832 502376389 551843703 715537782 396741156 921167222 919352800 476294180 247254232 256938724 920921642 663477101 285870211 755646854 915884001 363851806 997689918 423222303 826055152 933066215 625459214 468695474 792540110 804886514 228954283 221609882 330917431 247523821 773274144 466714911 130711358 115048335 17229417 9695666 63548928 174757510 625161100 856425818 963252528 254220241 496787738 688881202 411657264 867165917 219284739 828991999 410247544 221821946 373743881 405644450 274870116 205603604 903572268 237191016 113697675 958250411 874010075 350790053 582895753 752127353 510080547 839955998 827605171 163004895 959574133 687864142 958111780 951868869 354722947 18878692 228691952 451234297 550677627 703391310 322258484 598471936 13588197 157992497 264356623 646081262 884589953 943545341 705094339 710347930 678863288 573430740 59641501 992780914 563546041 376695000 738976711 46611214 229263988 324463009 658837608 408413987 427381354 499393292 334994358 681489146 290258739 538640201 989429311 276399157 206138263 507020236 478494467 544105784 832955963 801655400 575867607 946060697 951080536 36552542 61737058 613076087 630974407 426226866 434986832 703776366 825754423 844114797 20024897 402158046 665313970 346710390 249320427 488234824 139574281 30504058 653962779 24048429 411555608 340837863 328500774 656758273 797550797 170831663 665086655 556857669 641934438 35013786 391213731 828473741 639368623 577205633 262155975 41768574 550321132 657170193 669296259 416980018 885484128 297694404 779625165 470987186 836019682 574181686 583388640 886422202 305122424 300167520 389089177 61046887 254261236 38012244 808296320 659360451 582084338 933008275 396897909 801083602 245330113 667235648 339872500 992982341 832683831 971511138 277016133 406103663 794557207 927625901 186494819 60074158 94209095 694474444 682988839 729595741 71882874 558954744 910562371 994627195 417673870 646117403 147999522 868745498 48808123 672329241 571159766 284474884 977800122 363568254 446223441 256150684 899924385 972825931 712843205 442910468 76605397 824545654 268687851 919107411 702787548 999797611 337752658 977807842 16402518 934422542 311358394 946925472 306049860 288733010 7403217 984935655 334215868 985854222 504397813 998455146 525068955 219553446 622868455 339137225 769121986 193049311 935686916 571390864 768125586 313600908 611355717 568245211 132027708 803686848 537896027 809573670 675125449 536705012 704772787 952449275 653419902 642612287 724657287 347187219 687346921 527483225 334689603 275793384 77813353 994564051 632659554 626081586 368838824 864325971 33478126 787842950 482987558 712531879 593302556 730929250 993149443 707816362 884269852 135466329 302732830 668734229 94218168 114859933 386447224 236604171 349452033 858680338 173066587 222154214 142132169 692538820 694035031 712051159 966883279 15672028 307310006 178707694 838069107 958550899 158415711 966287986 324780628 662121785 468209455 685546591 795914091 228261939 782367821 657480099 959449580 985442199 186134760 2243595 187809131 634220464 981794388 924320120 919743864 125995440 80855665 460050034 67689552 752891770 316517060 561968221 83427896 461400021 48230580 543244452 2679182 611742856 184531233 827630003 950194314 991760095 951634296 726012647 160396087 160018705 866132484 97575362 892679904 173214114 706282533 552222023 701089469 290689953 177013246 530796983 168557139 395413781 160831166 946343716 909255328 911624060 736858394 216722196 279374674 315387423 144939905 269534079 617149783 412411256 574410702 993316658 570009062 907489053 802090879 769604599 84490001 574689486 867814497 246339905 658822585 956769328 230906864 332394548 178626590 526222572 357686188 675743269 34445232 471513867 297791186 397140914 399094579 302048874 290983274 247354362 667675557 271889137 703245969 847851436 387416729 72327554 926943767 10099314 584809916 103585561 990986689 729938888 201768942 116039243 621677764 44961486 767415251 424153463 992160521 211330709 711596622 672625365 863755830 581411261 272235102 744030931 81602152 517355494 950456981 533648271 286803697 792478010 385816687 160157729 401978375 573782928 826612930 5842132 487073384 362489012 889433359 228917868 231492182 240132912 217066446 295115752 148609515 410497422 681871816 162347276 92973640 886532535 354845354 937373308 658725120 730587070 543425695 99788606 217032576 518531050 315797243 631342801 952499227 148214409 909959406 58842655 672159581 740711621 29247527 330158067 482495590 883855331 566760391 322176054 982759682 913182957 531515256 467094204 813494028 805695036 91804272 21732178 687594393 794749182 163169516 882919243 538015394 996249098 496267236 411282067 362349899 981003843 125924744 343506725 408426010 955755203 160747549 84821862 819082623 866604149 682198792 311542315 908838093 436569813 186300416 573252625 717461177 964886320 366479473 873873793 718595946 773725349 39114063 597880184 660083175 155996424 244648356 666669322 200799460 997645634 526804212 705711121 220594679 710964108 228752381 550675431 458892457 550259070 258618859 538238163 825275661 882663908 967022019 343135111 383217225 401121149 812125300 961680334 598918080 947995943 341085775 712279547 151720551 490241879 829532759 321819043 722338199 629139426 431886912 295590759 967935111 104824554 470190529 967129596 454241945 505269327 701111430 235870921 448572900 718976444 177687258 483217558 981078766 141612321 349460452 288060897 894136182 724609680 346121656 508862987 644060374 244684389 773389511 953740285 502962653 406701964 943270615 489262108 461942685 227289425 435420764 623050180 488785362 299242617 233507400 727506578 869692169 93599095 467764495 72260591 805663294 567338565 568901046 411299952 355784775 386788881 255313924 36452745 629109509 373619085 523330673 644770242 330038441 708804250 848172584 19154725 804850063 724861579 259035674 450135320 698435406 364294878 533901109 361962366 240413698 783114274 461398 762501358 962589804 886783163 561630240 475037517 298782317 103058761 608483775 193844260 704882528 363694568 540935735 398240012 71313281 480441967 465737289 442202451 571711675 646925409 930511955 949171584 46854874 633035274 868224858 174546190 899205432 147878583 107499513 31474695 617498389 782956803 953860027 604230088 158313966 585021830 781973153 783587236 631208874 839484088 69530641 778540132 576615618 427053607 144189345 322122241 275872139 339121292 595870685 33888281 304051080 978179083 507580946 189324844 78611968 385898146 570087431 512316079 807120519 538773440 154943676 902180724 359394685 978614378 309069624 244454028 6467663 693145048 72254184 913170142 944191187 611146059 881046164 507309700 551644267 416894879 406167054 274886218 422489803 656302521 766524619 998648009 852013603 313929620 225099786 710960779 944137876 574932626 749822674 114985073 483220584 860033092 826234832 934900341 361183518 796270589 804324644 934427928 776979618 887189031 622786838 828466521 502587735 470411806 2963635 1213319 743879099 253026264 379935547 612481409 152461157 785162437 392677327 71542582 667255051 150154325 690918666 822041201 187582281 728642297 8632317 435344200 207698612 997239421 300599565 725515533 948949744 923281746 891007027 78000602 260033906 728325591 278891366 930555412 565508359 558738254 548520091 715897056 659930671 781480744 923550308 239902708 283136579 228073002 4514120 363023769 969516559 146321495 740113732 190354094 550218556 33946529 225475307 799672664 86886263 980892776 537441419 429121178 146509636 279920063 792326005 677243437 384722909 304241063 53747950 482072323 41535499 856303386 350646891 234807138 983630102 782511369 115671574 769939965 197100020 134736558 65385643 871769478 612020753 920714696 400650075 999354098 15072747 102771866 227681997 315013578 791825155 139843597 794518387 778016523 467155089 688224770 79833263 6223413 208870598 390281532 277542153 604362731 792264129 545931928 654927068 977525324 947275444 244037414 245958593 810395035 840200037 238651281 81249047 140841799 34428376 259792750 375933629 553339593 487833179 196827541 568195382 512917947 713298774 626042786 25735080 120875137 889887742 631734038 25234321 596929769 697491368 216533663 569099681 613987764 666735982 603273191 833256197 780010517 532926881 162121274 237611991 241988989 192210639 410923144 726048086 530824373 340182253 253846740 570932616 896380769 456409581 775937184 586101924 612770659 142925779 208825273 704716528 593715500 142096991 725596119 188282573 391695978 374858954 429115644 178303848 892839375 179531513 549553020 368114058 833249922 504480516 86647022 381860218 133864536 641709438 193130395 774113729 149929024 69343473 853285426 565747841 91159663 353696529 160868366 247597802 398339420 874164037 457672010 421930507 643657253 773256006 293723610 715580939 591314404 912081100 834017098 523883651 552279533 161568866 904836446 937502016 968618978 815250533 257929341 971801944 453044308 212387883 292711813 949597173 639240221 157631696 118650800 936458467 731037697 472962849 247524771 326337946 628192391 173841188 53518485 611601031 388522296 510399482 661523537 646905192 650800394 678262311 470792215 136529590 769617322 319486604 163033225 460528786 615309228 6694490 921509456 572618610 390858755 107612838 575115601 815109896 525976746 243110452 443043478 861973001 441953165 515555517 469109438 839485714 942412886 690389049 288601126 794275212 641575324 263645273 20441484 433635535 189390849 353561384 485340934 716515823 125822175 499825317 281769180 844918335 407950636 712299122 276872042 167279733 734899337 209762325 508452002 512844332 928360471 643123519 724762394 303202681 149249242 545398673 790002663 479515743 885058378 975976132 309910116 14916530 687902725 441829590 234244204 630657859 518222310 767770537 260494783 791319739 650249772 120554803 812319813 864060129 128568881 989999185 28850274 624997376 463806518 938294179 294214649 583497223 387110602 531671731 286984873 528271032 302874936 146921927 475089844 181101767 531640100 181323915 477008779 904531205 290247331 782140533 424807570 886824995 962587235 949022377 545956208 881821611 705522974 130566738 115681911 594426653 191820213 371997424 409869057 337793873 212091320 541870182 654024116 742857569 484887982 432873231 539728044 205740576 877575082 20675274 880385560 808843925 481429267 883883706 287640929 953288996 683521852 125602275 408016162 899834094 173558725 803493921 469706366 182466908 230707396 787752355 620533347 275567997 765387642 776218110 228071645 195119245 65601840 793278032 875140745 169312913 308448493 20198959 620971854 993842340 261380536 325813679 667162183 732646873 724079773 615868602 81108841 651460367 123984800 956781552 708669612 816356381 562855083 724407078 59677180 93088949 465535103 911411258 245782721 701516877 758784492 998214064 573070723 225629287 188621853 682347905 457448268 247078793 736234679 448904471 330418218 596108267 621322425 967139901 813597586 783789379 256112996 949565376 674562147 123161566 907532792 667565614 54517821 183928409 754953918 371315225 294933887 731326177 218775740 1121458 359925011 698076205 368244548 913643999 282871901 382495057 682482619 151181949 170601753 737251534 566410568 308049581 170808193 116051892 761521198 908503883 880512976 590610088 695468397 716670624 898684123 502866283 582692945 407956953 301034095 971479988 219647259 317184780 893322768 666831555 113051529 870046951 48951036 738194683 643538866 743747285 228685759 844849702 302224840 40558027 242040391 649316703 940973691 294649130 474283593 607526900 617198237 480169915 373887007 502399384 121531495 56345639 125506565 586597245 491556992 597574923 52553530 805385001 223038323 146611341 593680825 795404159 677754783 279601402 825619014 741581328 899742941 860767639 373429129 37288413 131440957 299596158 807238054 619989741 391014067 747931800 282736970 350586086 423799978 636567430 869900973 503435248 134466581 139622046 713172457 360530005 41156739 892128642 502389864 643165752 750402127 466067203 415681483 3166214 693530156 627789491 424126697 253637777 455033997 399121363 269619457 819384228 584723555 442527137 454630207 955514911 577198285 412238739 372369077 752621414 851918861 645109353 259675419 173775429 531632553 280853075 264252566 213262576 19958928 123724699 869693591 312544596 125150104 362252816 475793095 479734401 156458413 617148737 292565268 182378477 644033673 788725065 61758186 771318829 247476926 450177316 622910220 457113919 216788442 133530173 52788945 845374155 261000338 760662201 431541536 527070630 785619013 965261871 739792924 155434367 593271082 522232481 15326452 14874709 665921861 993830206 469261425 889279250 928672532 475588290 674099028 312983453 770777438 118503303 120751410 818873755 894464915 681615791 368367504 978223582 143734395 785710531 214043534 416725647 944616082 286906239 415310742 135392362 639351992 431109290 789548200 141719876 522202329 45597456 145649652 348265814 636429921 543283465 90070433 404798496 401136235 354113904 297766074 534547539 803366137 707950347 359018459 195437626 141424783 540047217 93754334 421611482 910255592 342315655 587318775 469582701 374345441 907624129 992084621 611424674 475845260 30349977 829169664 175802604 443374065 594071858 451807178 460628914 586626019 743861150 28228074 978465720 212555038 785933032 999391257 221008713 407311122 347935982 49959638 556905765 675640201 99998758 250858001 746480147 672390343 670255647 460600390 62959647 941035116 671213958 422823333 989518924 77954893 635773490 41270673 884551948 599201823 528915604 82932620 563476893 886805544 319268520 429878991 979246389 745292542 874171925 227663616 238574738 12326044 444418879 309459690 412584446 982204565 648832990 996709948 774883876 253419561 552613012 995317340 144314099 334451897 737811339 839649487 884315389 14353236 450891686 96804778 475068370 889653467 204517334 85122657 21102568 980437759 677970779 334180270 328078879 539333841 949500217 982083749 690698700 172018975 517763989 424187889 756135559 716209789 671462842 901156062 126216686 255214405 245942743 106384331 342205841 812256895 970853239 817912763 770784294 395161451 100284392 536337453 808422674 960711561 165318866 464662294 135860003 905396388 660384844 363468146 690390261 844512193 383450591 974085427 68877563 935369572 487446973 959174833 108474659 962383756 145905803 433943659 205071177 994269921 636000962 657242992 543713945 262240832 782160862 498339100 266721200 289347834 940094490 932220390 20474305 963641257 733118433 145517948 165249739 984093487 449127207 545352255 102550514 209442165 73583844 502267325 303262439 83338336 504403744 40581288 735890130 252075601 145581319 998392204 995664534 309675912 509230350 244304104 382921449 503827927 865909609 319585848 843955585 483972016 315025733 634531735 804809320 129960238 67551345 250146768 985481146 99773327 878489416 544727668 673589138 415060709 553036108 563731000 203574795 848632853 556159860 125614847 523663251 805550771 884131788 147863314 856131411 846218685 611495408 556381760 456750503 518789614 401252796 63203657 452712267 680996518 724395973 204953732 258233479 996751581 600518025 435096083 129377466 433891278 624798953 751173844 317728799 292626444 968075799 748860152 745996535 703281033 26426431 309407142 162967793 114944117 249455364 178898041 641650701 232339636 544355174 751017538 612441751 327645638 860773291 506763342 546783985 594096251 903775392 863854272 411711436 85658624 7896101 630169564 157595393 994275870 113905044 713003817 721892037 163713244 436303288 316058195 129684133 804411112 417328138 938660028 568010495 821448879 648200045 410182013 670478561 250991734 292335250 853248440 55985285 158867771 475398688 832455198 855532115 206841882 389681826 817365770 996008878 107430659 26952663 321722698 473108823 268403704 23003189 863046923 512122248 259599265 202883476 453333078 268291935 183047203 922005137 476403887 381798220 230039110 918128072 460842727 885875751 114954178 662118289 108941176 28212178 727495197 849214166 546126633 534472817 702332134 634199902 184424474 82807903 216067533 831450719 48755953 21339445 181176432 798614795 622322025 928218158 516343209 692668329 458089186 571494762 952822745 605996 183960584 930224607 596457193 374146805 249871804 741643585 565009023 957421649 841614634 632386156 316894142 627601043 544928651 820279939 226759129 458756594 997743936 419978909 293074432 449242423 795950674 185369768 872192672 562924631 184114641 572631298 775704120 540339387 787733095 164138336 902121264 165789501 776850528 247151800 56450294 729619483 572275522 755985854 456041607 450521257 346027427 703346309 208363958 188727267 981784060 972142356 103336620 419068590 312057531 950852727 898137308 155290069 777949727 665281728 497755329 696011199 399085999 674900003 552433799 459293939 564121698 773932632 197522065 584349259 807871003 117759412 574183774 63070098 47501578 465924286 793954543 642581377 30652993 137850254 296371600 889830593 606161521 272766289 825827828 43148978 806523511 587895744 533832304 90564764 895234138 272455381 175930172 959506111 674481874 728564757 741834934 639322383 413509363 910219794 501910326 807403192 460426777 669263568 247061401 656644092 558661548 791831344 876385891 740247456 582201763 628111984 365287932 432719794 464196479 386852795 149527529 27047144 909359970 166567551 584414216 590569143 21579299 628320622 570805269 221190063 49813199 958611931 6650631 796020300 606056443 800100518 267152373 619366423 969102282 206634810 93800947 980888441 468665599 260491608 682899049 423701951 148377346 507035733 791011832 851503787 867568656 145841904 319733167 926157148 211595602 684334962 297954262 878171380 386754884 283722576 442495941 902461377 989534451 691336233 445478703 353890730 509654728 876874567 979279635 937173751 84406504 290949060 852338069 453692757 914364195 743818478 586100022 121801602 472227784 314326508 585478647 920022692 84408090 458021217 601396359 637081434 978550888 98896151 596497250 398221756 506562835 395554514 567168802 648805266 326267221 115510605 194584354 614167561 14512108 889216011 830585620 200624910 735619033 551053180 584196871 582161109 187403207 854590951 120552835 311811421 808931861 453718540 501661820 597051519 593235543 997779691 615100460 401214282 977354189 368612948 153371194 460725713 770082666 611493541 772669289 491046530 544053154 272397663 679350817 6389668 184809882 627080300 24249428 361709788 66316309 190671472 563997230 228984845 189788231 492304825 277800238 706498783 499054119 262575675 494749965 703012757 920490692 90423204 696370963 593730544 178317131 669902142 906593806 757635992 563138211 490485991 621638728 630135653 899639654 886504822 433122100 709105816 831373689 184764112 267445637 611178765 182071805 387949236 363265603 11541309 983094403 16520791 882468958 350123428 165550296 312742673 7382765 923920439 275120456 800527252 530033199 174297027 813684517 466704151 527937454 765135077 8256905 278669338 230827626 785370031 150400938 594002204 859842937 945260961 210145766 535417773 640795321 942878518 682704943 347294837 805331010 471753173 310566018 315430145 176264389 335226545 567280720 725531899 375665377 628330226 507930963 320997099 373234562 588699762 920752755 947528256 65679659 523011291 501455399 459001852 885896596 495031280 38349817 9527163 130185217 876599768 243703077 769200880 774474721 966417309 466416195 759370229 715930059 72818727 985865366 538412081 449613448 304235897 545460168 620021835 886679978 644492175 688327163 426654802 418574082 871104917 540941442 433140045 668938109 715138370 947761639 19153188 56641768 859110127 245754223 966273571 663817764 121975905 14472330 848835883 512873162 94783830 202460170 185436429 108505098 46634175 5993126 385425475 874910629 711047538 170443076 970733341 381078172 301545173 358905182 897551468 108936732 903892590 662880954 846501718 622731062 560608642 99861268 446195740 125243176 647388277 447501493 808043678 875865127 29918786 590445000 169872354 12515506 440323962 392791307 200610789 36497617 113301624 723437116 389913077 772946900 523990007 964825117 830770073 90000086 971456800 848399945 713793137 78387391 623368392 937673422 284382736 224575964 958077531 747296045 617171698 522521723 732728573 397464160 39746962 27950761 816535012 853877647 31635529 655385306 349694094 484137254 451159104 983396264 368219647 913673337 872791159 504299074 67938718 949439304 418291322 1455804 425860502 674731693 241917686 16891312 146211783 543175413 722737938 645130893 932687295 701652367 993757678 722024220 875941419 733599943 547300814 982397887 966954937 200152929 937977931 701514544 367608235 105286244 531632398 606075954 681984558 275157271 490410269 442346084 744713154 696730110 72275745 898907657 463218420 417214739 976603656 938324804 213772176 530125271 745038607 726479666 291429175 199099033 862704122 566835167 562762473 454482317 570591254 729165200 766279071 993808477 518159337 54050439 909143289 175483807 214477988 952766018 920242977 5019606 323777023 353941720 236468644 81183231 582388911 843223390 490313300 685604355 323750329 104097668 368196340 579917195 817721568 44466159 18041103 186133911 534516790 149275173 97408788 371843536 849010173 400033462 911431677 680415963 572091509 87939950 721886100 919292587 188233065 237093344 591442212 270105596 173246058 730038854 804115 172668103 69909222 450389922 29880390 794994651 982085032 451061170 435409043 467655489 456794343 841431088 402699809 762213170 462433894 190032999 487906959 468396226 319382034 710987725 749797391 260517460 504368160 823524124 329553908 607009039 310954437 215945264 323134164 520420104 981488480 575285607 76794744 527106698 752974965 159031197 43128418 51484771 857587570 160455139 3906994 926689608 305231757 758022190 772946905 643691665 61028322 832771339 710679555 393107917 298823972 138236169 603267595 611342492 675266615 326603482 227178205 128543530 637857430 795043450 812101098 686196713 603108613 638906740 105238693 56609900 109189695 831054605 859237297 368804072 284680198 904263927 721629761 583291624 576799384 847326186 409790150 802740960 877889848 234780091 487181299 272743962 977143269 565207835 567088749 578715639 869536946 169173621 423046806 323424507 503499521 105476006 173128234 279629311 781015864 241738501 776034420 734719240 407836878 833425284 14776718 604767808 546895364 373305715 782313833 104753245 305338120 791966595 350228048 352353678 299653672 825583089 941891475 508212470 923745416 902622329 610813797 32327756 639916925 74189880 547568396 325933551 351388316 713024471 776916790 473944166 958989614 906390004 434464901 278251296 410345335 160020362 371921514 14477311 916837547 618050755 375147640 658538303 48485076 400844087 385525928 629773845 47422766 544918487 242359678 892303785 619149245 652460145 159578182 538149315 213406342 215689061 321260980 794334504 230798214 974802547 834149635 30637569 447381727 130308143 804064050 81555141 141106876 113730998 485841318 195505793 479344136 112477347 664188596 806304397 400868191 994348637 831432581 650748252 906725152 189316623 486362481 771269015 960744428 951355889 837864541 130698519 216592943 616087803 306832591 437686213 634823412 736648788 876516470 765275693 557277693 885113926 506647433 623263674 630828401 124443555 775771915 316006387 870283872 827623507 776389427 257162264 259989775 882488406 232144016 93716109 28531059 915390677 713375403 410656188 92130281 384287210 95257285 707391089 402680346 631548265 585072705 599930265 34934862 294580315 988744732 997323007 748822447 307313254 842310370 174388123 784883514 499646944 706060481 154415369 945029094 974996710 322859439 410457965 902114945 255653782 791812687 430752482 781423135 527866816 575029693 557577162 167910934 219904691 264815198 235567665 986299469 707978402 8920469 681593716 360369725 286527382 832054100 768185802 515958290 76831817 814678806 848481052 177805851 869083627 17569140 968991542 188465677 148045527 647713523 921100296 527005341 528719442 167493815 829639289 985172637 348643378 710877741 720139164 834265250 537139160 125176329 668643075 299238795 872846267 10884032 624425391 36790398 757995660 42238885 601754062 875840241 526402493 607468206 109069192 662699579 675672234 888676433 994699292 602088836 744676871 686026030 802807448 986018631 436984196 531676228 759900056 643001167 434713804 90241532 773160279 700726633 998474209 318155150 870416266 265526487 623161500 539581863 41787156 164470309 47149962 883327524 864546183 181801823 466143301 558215705 371681068 520097451 295882796 279291078 663536711 52367230 526551034 957681112 909450097 976467463 161512917 934674221 149929356 140342917 87975844 283355829 502444388 376482117 412885477 168228969 725082281 796353313 548602980 538540122 409524582 2672668 664305648 288659080 811538630 912375362 157300003 213792591 593943266 360646576 598190934 958356867 717420945 549750240 763860692 760825278 617349753 901873378 400030279 7171698 258075253 899425973 817848945 807124684 725756561 762744502 48657545 808083946 784826117 405502765 637636156 909317134 178908237 823504382 243294382 349039310 67393152 896221961 581258688 780987213 837127832 475631017 310705917 902625570 530611720 138110730 141115106 702529778 309350863 452622667 791992039 125745479 285168913 433860178 438888257 415676753 250973138 925140548 88907187 199675266 983470707 870878103 34903963 902965778 60880875 872805059 160836468 991608646 814888802 346689924 849695554 682465152 970879283 217789104 654297081 294906684 156436926 301099858 324448164 913164139 439350312 751666426 971162864 592036349 99535850 622717702 291534876 404603451 502069141 241721133 542778625 452653619 761844594 512609891 702626712 145491225 655874691 227130793 182136410 168465253 419386375 190416255 315671898 653163659 607153821 911037993 230944764 902139539 102745744 158927904 905492756 531179544 323145072 68366288 879590825 421361972 737683466 386636672 522905698 348031342 147985241 399184682 5155043 430134110 637086905 604630319 63236444 220952919 601014933 125342848 285457883 43409742 483257590 713249847 32891817 81363461 665537032 759750458 166466377 55422067 373898754 744472627 931091887 475938117 283463400 632961507 710309187 187309924 567657848 528717286 307626315 566339352 604424135 287138007 165415443 535120343 816984460 358998366 912966818 666403992 579217763 870672778 39190411 520468949 780686453 398492659 718927373 560479799 78595090 804054237 933666497 23256158 50507481 660836988 273014249 739082755 597617368 799641483 805954351 900124618 260551540 635466607 787845544 949467845 198827625 732483196 147031111 725717013 356085783 105271023 948450733 791383957 196378532 382986319 369053115 658331747 256752777 38786526 663794171 167545718 717206893 32492603 403923234 190970463 851765939 425501179 413595324 974603507 171131018 945388702 476567374 468486255 850748314 897856566 951884111 770943413 174314813 135729533 414506129 153787849 866863002 188820938 268961197 409439437 721358989 406347790 118143779 735583412 712995211 783359103 553431464 381518671 940166374 671838637 827981836 221997571 788993625 788727487 639233177 613365953 274193833 731633219 925944936 287658537 463403164 551516614 287552587 758580795 885412047 291997971 669608704 829132291 802547084 264672446 164424605 464225619 423672163 371818422 620213642 851448144 822672104 353896990 571424524 911518380 382829290 206807127 636679569 281929223 865396783 131270363 79603952 166857060 270080109 549507012 568803498 530388113 122865780 599186725 982434969 631371067 890368203 966894282 22942193 177806267 694601993 943692055 159055440 236287810 279120316 735558336 762204085 102343122 637128839 280515308 705952621 42272564 371263541 891772474 254216837 584717884 552183743 4504756 357283033 490954802 509929099 917151453 681245199 637103056 80946808 891728184 608713146 837037119 131796264 16258901 356667585 735299940 370694108 751459776 822817981 883786687 534325246 750322869 892489893 909294957 343156783 569105543 556952295 844283037 445566819 735908154 388441103 8242211 668660026 250979934 279540494 848990942 554084325 21233939 975686947 381546023 275485531 418966321 930109078 439991286 718023300 437899040 709534035 564626572 72693933 312002461 346370280 707359796 142398386 521476011 470279972 309393242 948391113 753301555 369301751 666471151 278853227 610522992 996825194 519380241 643314231 429778111 875388172 28368144 384494059 779385788 458269014 966927906 595560779 303701277 404481530 449845873 80304776 871767736 246162057 955296109 470259007 296845632 867174021 485165722 735042857 675642191 766232953 521547796 59293644 743691874 366046268 406371909 577592077 851475960 127090411 216662227 223788907 626942319 773818550 362473658 697581554 675895758 998921190 334340850 73501022 240244240 548561455 47516474 280052194 636095952 150168701 459551283 532646083 735349643 864244589 280847108 844154427 550985252 982644305 54735384 976516384 999962853 341500883 919245236 977256345 500705850 25525182 137190814 27218511 949156852 724484183 274847022 447785473 869971366 791326864 93201717 506642640 666982447 683059974 499743488 846672550 522681783 685498558 206051949 237208615 842296428 348026205 872173802 844645125 232869952 497020526 598410977 659509652 17477831 989668024 243425085 195427290 488712669 276502742 134671491 176976537 612868436 377177579 310685770 430981435 174879816 88396919 622619116 146321104 849889382 382650121 50748237 270373999 278364434 632655284 686809286 897743047 321194973 682073255 791290183 412410546 342269908 324288048 82660485 780691763 923150464 482125396 516797577 735293116 970214856 326318298 888147013 654807062 223127149 681323113 433213617 982957018 306611597 21732017 908863010 769589455 471915601 118457861 186268638 51500391 491661656 460788076 968061380 859534395 284546631 491842065 728894045 368056372 308409171 62634594 820345514 487539947 903577629 869938703 562964481 771770180 889273239 388888948 307428477 420002813 297763953 423367104 172911201 596660828 789912380 451044636 161391352 418092813 698150869 922543868 401255722 46579344 403347008 359812961 59827237 642374397 986202074 659262105 404988661 436663657 868030315 563967754 139021835 302548764 867405942 250526340 698809446 863478448 566612572 4981703 896519788 121690863 702627969 417692285 700593265 703274645 947507228 118153869 332613998 534307980 258071445 444851125 293858619 226037265 195232296 70222577 742133109 629742276 749123018 529694069 537636384 143921241 875596967 429280044 47101337 792268549 99942659 660916971 213929249 612215921 267121320 365971086 978991626 497157620 669088186 481135651 172521748 736654626 619825415 833949900 376164511 79839257 282486544 376132319 710158798 325325234 723546673 284995347 29748926 66680861 230551919 493359565 643732765 400371326 349750771 340780550 628150159 938240931 504962578 103448029 730135762 215442252 410683700 953340207 995558238 828341141 811325929 724847938 288063517 535805877 3921237 2318328 988018899 548607323 33737528 714862560 767824181 533765343 648735501 16329817 697499708 333447753 913712197 585507309 887731388 628347372 40273453 967500732 484686765 465508526 941385552 787719579 484940311 121084800 983308767 774987997 853065449 826965635 491437457 639839982 184871036 364479492 925947703 796884401 855244161 755658986 937743864 971837742 492289738 136578176 953679452 8051576 681423952 677371203 895489550 598896182 374021218 512159805 914488756 795832448 4409323 110363164 907232437 233084880 14810289 635750068 390185669 989830552 71074974 524540785 587465180 954281873 675378096 585284536 120736378 245034460 590523908 541739671 615706100 665918972 815991548 883164888 566622685 465984564 56028447 487587156 954852810 202462100 976408021 217282757 673508735 185808366 229350347 915175057 621569255 676826844 779629051 199523526 104674831 543202653 687601721 377699129 537284025 45735770 869856077 983999300 67872735 378493185 694410962 14129733 249516647 534077467 317481209 129064341 18062890 139383882 863509832 479989488 293456397 50005983 56212656 877657074 879502907 103567278 616713268 989500526 261860368 256456560 761342910 788477838 544795652 637266579 82759939 619410273 955170997 21781055 525335466 343865790 480056160 93870020 358414808 795105901 656146046 597092090 14817059 364837078 673267208 229540594 400229320 76123867 86889474 975795511 195671630 585400008 33686112 44085914 895450753 52613823 735169873 421474895 272684409 786746167 562976505 882962809 296576055 351412897 722856044 54305994 209424145 704458388 600624481 510724613 285899483 202581225 526131379 653945297 898893114 112414495 488424894 473882203 503130751 492123883 637678968 117854653 978734906 217561770 235968224 892306851 929726275 947629952 854651734 440568687 71585169 9606945 887492220 979087947 402931917 864028356 659252512 667371790 76203794 397039758 761704440 954197465 385840218 449645413 275417940 952487796 956177894 416764660 86269417 197629870 651995272 194688438 934310946 641833749 583145517 746446835 566562479 762532033 597400664 864171905 908141625 731716368 241959036 687232569 112054822 283954172 244587722 528351663 875070848 613875383 780694520 151168753 453105289 508661889 919687331 545728352 781095755 895660428 458782349 636933596 983788470 183894830 855572793 385039186 209896493 643092774 606656889 560792217 171100813 876064170 461584003 66830300 438126187 142817459 615287750 115288588 852935211 31938487 246877430 24511071 388513271 39522045 51724145 944701165 368610130 740973504 604218054 206474250 293594584 224650921 548821334 320107407 193972991 658701162 968640109 42980905 651537100 451647508 28586242 502732268 627633353 788438408 170921696 63038541 6320951 373074234 549768595 525072125 242894903 889587612 908399555 464599838 742534289 879579322 404308151 251419130 287892791 593063716 276423513 598766937 588350836 505074350 590323708 34226666 670657151 702793564 282452556 867555904 747319014 764588184 220622522 493485139 296860781 485898416 106562683 47209201 842386936 35559035 334495968 167875731 243839270 911555559 754652562 475330592 420626494 424833788 316216558 924036194 187881667 709591848 347313614 395544187 376567614 601811734 716461939 577205337 111030725 582753952 620684727 915128825 625179140 483505981 588805710 260766259 659580086 850469082 240121803 874608209 764678194 635825983 430611698 316838135 305395502 940621904 84500418 674197796 629128247 893333500 71126221 700196012 620935142 18849384 462523352 234413079 264113695 142721544 163189300 523913251 287686582 803038735 60945795 381644812 640865413 34354271 533460672 488030856 627581072 337066283 954588386 368903139 641834779 245402963 707101542 329742292 346489787 657327387 265200583 501335090 884335073 947417045 853155674 124817048 897762232 290239025 632217692 636455455 115352391 922079711 304927938 545441389 126253539 941575487 463983890 575204076 959061075 37586449 477721297 275416094 400443556 130668366 736894876 605235101 666791484 635167439 863297828 670688532 860975736 6391587 809764837 586053008 872795870 671730131 533657906 161681551 766461000 280445343 811206096 241036856 516223200 302353832 89491402 261899038 463774277 733621824 209082765 814163415 256358458 900977930 782993268 564380785 687331187 260966257 29424437 301827820 275928492 277970916 827654359 334995291 600794014 988003562 197505056 395944814 936310639 218332637 734316120 630355531 226939896 9039350 868056612 761975594 76312560 595328664 991942456 561519359 108185571 469619296 820557298 21974475 666060583 891515568 322293200 511868019 200910147 711340804 666732883 672995453 748167045 430010789 755695049 231852728 865905288 611100860 856914030 773007997 967780159 654363109 413778748 863890358 79187904 828681178 887007169 901209141 418590495 748693826 513334243 611803261 549880293 741834958 822867103 801004750 655769242 409140593 700290415 583154739 25732767 634888363 735904436 979707245 800141413 611181471 827197210 115147096 905814723 563469644 140649536 550809937 384859529 229856432 881241983 539944697 942942491 27492263 849376197 860986687 76915425 218329801 199703237 237771710 721756538 402803886 411988249 545778778 454487036 101519559 596538582 103818784 637346987 65673965 95330997 22908320 232841366 233284319 963092745 925851513 766130806 84081736 298032646 750168413 799478560 307565011 635825696 510731945 286754529 473891124 804258062 48507854 803509355 960050801 213577351 698897691 970467057 334853748 168278851 552718684 467758375 778938266 814137946 17340605 817325455 144471334 273522191 986664288 221822436 597537824 503547061 999752330 585962439 483930405 671784589 474893107 866017305 789963711 341717177 412791213 968395829 391084684 618413070 773589703 955158826 164157699 443324455 565838675 343349141 438641101 686780573 591802676 864750416 149661562 565083951 301529317 939722215 160240174 484982426 726893173 297586460 224017830 741069624 248213056 324409206 171658913 31652078 290555350 583712366 206795118 125658586 871994319 830283800 596000337 98200720 800825749 24215041 834168224 224796305 239610534 533525487 352461928 205973528 511219897 495823697 393162349 172737782 955730104 856263024 651480525 196931622 658467502 910557745 920157203 98410874 291021123 374050117 474588452 485208696 536574429 194512711 523955801 765515220 615925917 590771390 338354684 927665635 126538944 907692359 128491220 853934867 635150449 574558515 40457349 861758776 688219693 59509174 578016519 729331907 842260742 826409713 675647350 3251159 196607807 474359637 5656093 980805065 806873623 460653785 674348148 915053438 243006638 850637398 593302475 274335488 648364981 473617888 188483624 508606153 747799125 480277189 920762830 332673006 804697020 649426231 346312059 516829902 168339509 27725743 356816001 230305994 471313058 305910098 938573709 548267668 487670236 44337983 76905113 879415638 942335372 805384321 207884103 579851856 774570366 158918091 935601025 195228986 884135705 38737778 323864550 415957032 85589133 799424225 771340432 517610158 588793368 167550102 662349272 395384635 121637243 464761125 157081331 684996346 92831963 755823378 476762994 662103822 494108845 278422560 659313201 158038445 82153524 373286524 924672061 826504684 742588828 578892712 896714830 394166863 357543611 676195257 154579774 512190519 554979876 715030828 388833005 792143359 489929825 337888702 402595493 848068304 874386677 83778179 411537676 375555532 909047322 175168734 782472145 147957108 920157438 999128814 974201050 352224740 726688439 753893857 730215457 428443968 545173031 740318270 942398510 980455756 849846749 726882026 128198430 580810632 285029524 341633820 40737833 927447134 58986426 803376028 485768164 631064306 433276041 380300328 929809591 906326284 308165235 116583735 647566770 701283741 678884416 152491135 927389126 173739073 292871110 787635492 49084991 337117997 403197773 150382056 868309029 156369415 173374162 862325511 786614308 998472522 349589058 144538062 869599177 701706715 999655950 355256720 486317690 742845599 299454077 191805866 421221662 36705885 14536450 710610664 582890518 335921729 725664078 35459350 221585187 321732752 705465361 204919533 928916208 813142393 111402888 442364276 431530430 279808779 370038418 862021446 899473129 678696474 304910670 385703277 321509596 343442594 823603238 936815031 553621737 794395236 712190481 630565472 767081166 738039387 919224616 753098922 911293392 96031087 404529675 986339225 674413142 367911135 177293033 495548113 835001597 648007968 285576945 376722077 590383770 1572030 373639888 503293745 563539402 329555794 952256176 505378326 731916833 795392736 785452155 209636753 663162049 438828242 696330766 248834678 538946055 551765890 302012593 87918074 534059589 896640081 543846712 827042198 953026499 515029804 575420526 302201365 944735926 538196350 329500361 37359677 642432853 938630500 937311749 421174884 536450604 311628087 287480045 329778125 160671487 794629875 663681684 684133018 801961675 798130179 974791710 746423147 306860138 479798021 358556175 276493611 213966191 848806685 555936959 262727134 554567139 360815773 528752847 370850035 702706885 704550780 875136290 665200597 149486384 988439598 736457814 808578247 786218204 82518069 383122507 43725788 500011050 586704221 963906209 173634711 413967256 148960490 694892426 682035216 362984471 844628349 87066805 826422784 553608257 214238801 495596663 528110691 614936674 425760132 446858111 681273380 533666083 27728093 36041786 488317590 479638942 322759091 975083605 167812256 819154257 871716362 593350167 401856213 530461039 481431256 258948215 232153969 844735073 956713540 205278551 405395911 166445383 706917424
