924 720520909 959460224 76592855 355323590 335948648 565496075 592127010 935250798 353359987 533241668 16641661 497340096 652759470 872081495 787983934 935610071 220482138 918934854 120238924 219769950 349399321 916809953 929032366 995480988 968881948 976934963 609146232 768535261 650445205 903549178 924558606 949595862 613017868 930183043 139565242 286008143 400486116 806341587 100422565 659128789 120687601 846788505 528445447 675152790 921320896 991791155 881473766 927357788 425617489 820017558 632951406 814701444 44758003 323423212 283227634 837245249 249999197 858927139 410663261 911065572 632812101 734849003 198337944 604619310 525020534 644299371 743428690 900810859 38920850 539566575 785550492 844191722 326445700 982752081 879572722 945850377 544898855 767390402 841786584 964759669 134794833 182188079 754212879 928302490 526194528 583809811 578487524 580593329 454729696 837876522 962328960 995655190 863128373 951509444 527195262 579279959 344576931 900070568 931223036 996674873 638773980 932669636 417846265 737412842 692204679 706003897 179815445 379244374 467606870 974035265 157751389 594651527 283504300 821182263 908698558 994674713 627297623 978561658 933448455 970025964 549666908 843133965 789838525 903484579 767998233 857558760 769462611 890201374 916530552 990745250 421125102 947798792 606779429 941897398 439127758 950473560 380047374 590751288 137322142 434093399 596372525 685327979 867873720 952500623 578177774 666381251 677229983 787852782 422470539 888908253 547836185 886615936 799911021 872401787 960672690 974935070 315121164 663550707 542613496 575914831 479665086 979715210 517550049 857868944 745592553 853807292 695297831 758014744 603330837 795943734 892662250 946341674 165012758 631431897 524024703 836823040 100714020 691004272 698181874 773036015 612746635 739465242 987355914 998533851 882573374 979784339 11515719 533277997 366022115 688286914 540825939 740531514 449047650 913577876 483798604 584857444 25740877 636522493 807674013 935945959 561986240 876303483 121075049 201902811 238213341 799827823 448078418 555946782 669099336 673979367 711614380 784464791 535280543 968833469 112124251 757298323 423220185 645895835 706150648 940630040 131633397 177958547 425398361 487795299 131924771 314964626 869254680 896015402 29710179 68754154 211479062 764303349 42198998 278833378 106352885 744181708 116846472 894722178 834593439 893520131 380847634 888275838 921735552 924811305 831597968 972152527 148873595 445031323 111633293 398499716 65506457 965831005 380298496 882311138 396663439 854490679 792375142 806905100 533087993 954465475 632335040 792642354 487982110 820229229 289859458 593673909 810899851 913476344 610568926 805581666 29658455 851127749 738396554 989099007 35329960 126439623 405021285 944397151 334271274 972445361 72410687 350418297 704835435 887575033 441696184 461409695 306186557 784412249 645945161 884866199 320722292 571227487 640384500 866990109 108336871 419310225 885736302 949443998 729491065 914524619 333335504 552521655 928126956 952936709 961066519 972418890 154648685 995765784 628327648 817747496 714257921 971565092 475203348 614919765 149991782 341690377 304046692 389281281 692343807 733538261 17940434 93791988 589159389 802922857 714447916 789893347 979495766 985901819 720097054 986628980 886616597 931117715 637305801 951689481 794476709 978476720 677789869 805842352 88082080 783063667 848003294 995637547 408528499 443028050 312630997 834000439 950274148 971408714 544474361 858652477 845336932 874670059 290011077 436721377 120609201 717051688 220639758 663436980 567116307 634280606 945830569 946080138 14246867 835973657 941943031 955918143 516443140 884096706 596537851 698367617 191665277 319087920 373888428 560792711 625481861 962754007 619149228 670233581 27257963 412069072 842060035 941951691 714122921 768002556 317287471 432812914 579128185 921981284 480656907 918038894 943963063 996268405 946700420 987694534 51853115 420698513 754918105 952102654 417749516 941340106 779124303 852956843 600353258 625536213 185302275 851575386 410195022 413689141 506972582 829070622 441649593 581697769 342544915 356730704 437286389 613438448 689308108 707888574 617534003 914165469 545717730 595780338 926051977 928984060 859798068 998318742 509405623 686422856 336382818 597836035 550938008 809009926 128357863 453163425 896355659 985938719 705243785 876924895 546893106 609943767 777116897 958311530 492729891 948055313 429969670 646601571 832392456 938394820 86954516 182036969 125893908 259073099 869523910 890658982 29473992 866702654 454006795 670490484 158892860 184740085 156201295 918795562 394524828 412462338 62692896 490975430 707738580 877660670 974338777 978363188 670542841 689005272 363228507 579828849 604949613 811459265 389869072 658615791 679765579 774039385 498178449 966432482 123794703 810085803 820554041 966076303 158011070 570310190 87124485 689620644 781652351 998544911 69411763 785062311 266734238 768462527 532395799 666626656 388488182 418396652 909400906 994359969 994104689 997018574 694649485 815802882 393540674 393613476 361395194 454363192 984806563 989764701 656408011 821555681 220255743 418623897 99733931 227650903 803132122 845644162 12524417 493825422 792505514 842404361 998094548 998698812 648656798 733070759 729155087 763319580 975966184 982464863 103861763 800386307 353399959 876031281 491506820 689637642 738125221 749151839 801934312 855720544 423825901 924315630 575140425 664731709 185023186 334938044 537785223 713790134 407517076 902557050 584380122 663685644 947141805 971898585 270350525 547477675 232998902 912342667 711509743 906727555 72268344 150303427 811823352 944011819 288585140 783154250 456608806 540898970 325035650 404035667 955431157 966265914 176070690 398219398 609645642 919585176 111745644 680359518 793227936 889748116 56262323 616159879 849316822 905936829 955633062 993284708 371067993 844904314 200373001 774068620 876239396 984481157 901839161 917784715 675207876 704037335 653314519 850650448 567400955 571968762 141351027 304340821 54937879 645048826 331392612 506417053 496073010 676129783 982667383 992908497 322924021 926985375 536103269 740442877 117449993 141244909 460886000 680981054 665804211 817210020 796480009 910895805 210455228 974015743 598087913 716819811 437790390 814341391 279998755 768070392 636142696 770362089 635157857 874593129 700692677 780892644 333644466 639946301 424926163 500134217 758303832 910442173 895497564 942878581 908412359 962243227 234241961 900832752 680013273 768952129 949756187 952969393 788732201 997476812 392883201 645715299 34300463 689275319 986760176 990570614 704268148 850200924 215411214 384951649 425725320 524226961 533938533 811595641 768646244 865995419 506189293 748028156 789578696 865758956 93196925 488147472 839464703 950719835 201685704 499449868 833681698 986808137 129428216 844860066 670519864 672431836 21458863 986012829 113928866 746163322 462629907 562864411 139392316 802010930 600973223 959408195 910757356 961511799 987886546 989956697 977763702 989267687 338545026 639199223 739695092 764578932 387520958 449996489 729095530 791437032 858352309 990631924 814869659 890253566 942443942 971136957 806569651 866309540 999816602 999829297 533757563 749401188 196146194 907771973 536294517 750930062 559414857 955343520 590972791 615657631 897451109 981204414 30153864 350263087 443635512 724225355 990575001 991917205 995423996 999817502 984729092 997572523 369455550 448740895 49422384 665521990 267134432 581406190 494653085 977904642 568107744 855550037 679487082 848188825 50702107 87846595 431695749 857936957 748168284 823252142 565643015 999750946 201032750 877159163 346631584 719219254 963530864 963700145 644221855 958509647 639040398 773740134 104755484 554470169 138331702 654023933 411069527 589736451 508938415 523973394 873459906 972033457 425553200 565374146 568594835 838917029 645804959 733670883 617380202 643449080 722047843 870344150 372058980 477857144 788604010 976008485 473780670 620796741 590514746 694545807 183320387 644960487 775845646 947921830 256266361 351083061 429369797 848583871 425001595 880931229 761396828 995279646 164959506 811904400 204634092 750632063 79433280 433540852 465516505 898447493 402493105 668470228 363379496 616803151 226015476 691235429 856961351 974428833 400655736 441854607 58422856 108885561 443903177 975433477 592358959 624521112 964988381 991872858 752716756 789688966 778884603 866566057 765262762 838420911 319709404 702261227 144558559 975105714 290751443 493862151 348113375 386361916 850763925 962850166 422716858 765063374 951091486 980706242 567799347 619042733 714910296 856496227 868748199 997956404 265555632 766627678 641978490 749067096 738270780 900808661 573235061 768569462 775139860 819440868 574207658 672629366 260981029 353967000 771753096 931180974 820629368 949109818 156695647 973569959 278364883 630716036 89457881 610166616 531851603 700684011 214426232 849388373 247102869 513975789 282630591 504888265 389168342 646202803 263541540 282770587 331857469 685623815 440370794 918459359 62322412 259590373 607176189 930108998 487372246 751217032 871974132 928546307 936411858 942624577 391041653 721252537 294427667 497761396 137605425 744388838 839260828 913122182 243802970 514685539 766813746 940182722 810737494 908211484 514817300 683596396 466736017 687284712 581252933 761296570 832332070 968279779 654600892 724309400 479269310 897546490 500297366 692646464 381954755 502377115 636767899 638142172 478223051 770296988 578213479 800437214 689897193 795081193 866543210 933723458 815476722 901513398 300951837 645739731 926906432 952387961 698500466 949279238 231126296 247135025 519011714 805999532 998835803 999889721 775259694 871323369 828790324 842794062 195643235 460074353 848220345 888280887 40073172 796864523 466418941 862651552 981133508 999320205 290909346 926589429 983279936 997065709 521668022 525306500 298175761 977889788 972441335 992940038 933497761 994275160 761824487 985684764 15287677 907797154 574405859 632952197 24253601 109569217 266374727 296196035 442050680 585898746 385524698 578765914 564510410 625557316 49107855 159891862 133764125 357769413 878718118 985510797 714053765 800598654 815596685 926403160 883975390 997028099 300484713 703190077 178627617 649393776 135112753 535903828 987498032 989912896 97390099 579876681 586800062 921834295 800721520 822234239 889688568 976503604 945711853 975790910 405247263 782718218 761417714 796009130 453351667 599458152 525135155 954582338 896164765 966006198 335243353 699803901 185359506 719160192 275001590 948482342 632327209 817420134 615620015 999585067 48412884 485485564 719936154 759714355 244345283 866023750 175883266 319947148 244747166 861335796 225324672 704122301 785654002 856863614 657173552 679412285 930682892 955796074 27234561 601349230 690619991 736104346 797193342 952823459 932494853 936708485 996905272 997340183 928729861 955288939 730829950 900727483 298096535 355266500 639383083 988451397 60080906 987966026 923633972 975291664 714735657 826671261 499970419 852883559 640512722 707652528 208316085 985994104 789704661 864978840 822573119 850142327 66201559 340845947 113729596 346459006 13674323 687223952 473627358 789385964 776071216 907822452 386492403 754938020 205975266 957263904 593039683 967635823 989071069 994730297 305031093 812722785 279105933 591561807 820879558 883613777 70170086 346124722 686411910 835055654 675085298 991308102 717875379 886145992 774873392 984526772 772600499 792363171 764077848 894491693 837390082 954190342 111328830 817201194 958559375 989658304 366639745 773894363 99351703 549948856 438801914 622578355 230638143 533267734 853793825 989423325 544176292 669705215 288428602 597284087 767854712 900451046 263555269 990924823 348768468 929322491 262474227 545723854 674338502 915903353 15965556 218664614 432902794 590877577 789821390 960947844 654399317 938320364 721684832 974661251 929613593 951111607 195948710 729588231 235366572 590729545 518026009 943437541 907381253 950420752 662529583 879799110 217988944 449537689 746530668 812708409 206005833 544165273 668589350 922196517 396549771 928457038 868935635 963262897 42696446 466538221 789297865 989911636 266646531 667513696 758405451 840357538 947307013 954910157 108381819 518171602 429850044 713891183 792182835 996914749 293903799 460261195 964749411 997840334 675482935 688676661 628652695 761573477 378656971 976144060 992349407 995538314 536785108 625424105 28094471 518728665 564674416 644135671 351583144 711850757 568698402 597787215 339515544 929985621 973106697 985202530 325811553 788687245 560332089 781133654 508147878 798219577 566988705 779136678 225575682 576548763 479708590 645809753 256190598 766971531 90597779 720262916 139124469 922319049 697520654 820075367 863048158 964575069 49894811 619167019 377569919 825835669 248983089 317023110 763188178 906969135 590018999 833512954 348532166 672391931 688357275 719298686 653927765 814511754 366361125 742632142 130953380 410897803 969459474 986225561 392540076 952870095 483599750 846487847 518952553 647734492 554848265 825786833 197748833 344877754 227657527 683251988 788621962 894575595 130133924 729840742 227471613 826850891 903970729 930630539 539360875 907823876 820122308 852639999 537392924 999278864 988191782 992606645 485920390 625817674 804412555 867225065 461033379 466427473 848871300 932265018 271009873 550991163 196710616 711362098 155511353 854304894 836604238 913507494 913300384 998357992 826278755 868075267 637397380 990429990 980232304 994846084 312615199 722603965 682103019 827761875 64701168 743474853 405745125 461311113 833634779 840406408 280611189 318886723 966621895 996280371 918572327 952510654 203715177 740077167 866263403 990268633 505595296 993449876 34760650 945593210 741422309 828503533 631524699 713607818 361629138 859975140 294227710 714267496 929833094 931787418 214625945 491341515 395471658 779983182 786369882 941649829 985927686 989771672 234400527 410391842 888940724 982441868 900552798 924260028 862544730 992153930 466132380 529536535 791771703 889312286 242060700 683233632 383746208 983138917 117800497 610829640 153208805 613385022 730120931 819435580 222617740 905688681 877095291 932515692 636541339 658910327 703814967 705864218 29447201 142171690 946932757 981711633 567971416 743331315 636293551 873426465 85743086 692231082 565127964 686638790 888119587 984814060 330896037 666546340 934569394 961214205 671485266 873686769 943100815 948912539 889662767 938449650 21908718 685519471 823148404 931668754 53045558 579435875 498420141 817646498 851819178 959786252 919918055 963094190 298403838 996442002 762196737 836039468 70185292 113628836 811592481 818617830 485663995 529962850 948094336 977917746 681827094 969237853 647629980 727245750 909357933 982660270 345016467 843654695 681504893 774923744 580408995 996983580 504035899 789739683 544668392 807610519 585877229 782213083 304711989 958697712 896185697 994532806 924402171 973464725 286214814 689444508 913163988 947524216 804487177 861533812 908147753 941201364 29228373 174873610 33726244 112139012 445158877 845805420 307930262 432584745 786112257 798635232 71703526 906989031 385986163 665416184 355027564 519472425 913826344 920153127 866140610 933809345 811984081 819096840 154295496 807357947 640627577 813668216 796088958 912381011 200032322 228256122 478086214 967571618 14207801 761150132 732744924 740196154 892542902 977110627 54847992 839910125 920241955 987161908 747721025 960252002 63820570 860230619 430301290 434241923 117823537 981831333 465005280 894712335 573238952 721681968 811612306 836326199 869331966 998959895 528476870 568193101 910267714 943461440 180294902 340648080 700943100 798222019 64088723 777092533 559632355 888649071 627405882 778084377 471467105 632816838 330735430 546458520 680990826 842173230 358370477 825650798 690994139 848859442 857973888 971779133 708529789 945977522 574666438 878265059 959047822 964317076 140282068 412400598 39148784 359868127 583222004 740895298 915106703 919258609 672284178 972137521 977801942 979770050 363616753 427382506 766659464 986754000 233151724 764791549 569578398 849742225 839569666 862171686 74698302 375456232 85836015 628918999 742481270 873053360 91038824 501198089 465476827 880634612 750072240 993074084 113973438 913063300 347967577 939414974 722163084 758871075 598120560 931341203 231104543 452679916 883588215 908046271 626881606 762546479 448370410 839866896 672921350 686013825 783981153 882671497 367244447 807475923 121306478 449029264 348628165 419723429 462727014 846642708 410819806 845762625 244708634 578530739 788924021 847606471 138097108 508888438 386062302 412367228 426180798 824588731 826593850 993577532 735848802 968744117 592525942 788436797 228939350 899209145 430734641 554443387 728734638 898631101 543614244 626821105 227293687 366025428 323119341 759968322 651404721 875807288 897781946 930736537 757021184 903492919 851097398 894012672 961447421 996223950 562480929 803022157 424510367 576799734 432331837 749497039 692070115 726767355 939414248 951728794 765386596 928737282 280247732 955561549 207671065 896096293 827741711 948521855 844722253 923657452 426760824 445159908 804999901 897586544 52543245 95061313 662502619 876394487 259629334 833797057 922007933 942629298 830274629 953356251 735293702 758689687 553052193 799358346 987594387 993314334 475321492 722004530 656841603 824079087 80471806 646536348 721245999 856637566 219534664 528017463 346657031 824298167 122442024 953501050 301462585 804672205 34645048 639536819 792353419 991812725 841885270 986227370 650004812 987542280 883384325 913707757 793225201 873566317 673897647 933849547 47480861 981364779 548792307 751642674 543447243 829494827 475817512 694838076 525124272 527671245 679578322 808098610 185362398 863673887 426914651 827115759 140128852 882879909 519421242 955813418 702711054 859427911 101033958 496857218 898125101 925713975 949042800 987194526 233527419 248971328 617369386 890556384 647414392 701596933 477266067 852290282 680741256 831903028 971380989 983109504 521305285 797927679 121004270 761487380 355682454 882056755 154396077 329846790 151526758 856764376 215859849 751532722 339993101 348508086 211279361 258797622 194834971 383566592 283674396 598827285 357144513 993964769 155886245 690350189 481568827 882062987 437897609 542059841 46820601 415273576 523894139 618941380 665230731 770189322 625037919 918687063 63027538 469861399 138808632 566600773 322673182 523160674 107467126 750773717 825588919 956376230 377841322 398539354 59409145 718038130 426819797 463431734 617336060 918849891 825253022 920887056 494530918 684345902 142691796 802829089 259376203 698916364 168172880 658804609 800894966 940478792 315661596 680765913 892370640 967267822 491034726 545258253 855625362 991839324 295030814 580717030 201004573 203496806 379013958 948395179 922443166 955148597 598783307 714991610 796705628 824433755 571882732 661458177 546350662 975487543 857450475 864169622 629908273 634227403 634546244 957979161 94750310 601155723 100915603 967121344 451606170 727525820 766041653 961971372 116574831 594406182 24667870 653012899 372237575 860198743 73113993 105892583 444486853 860728969 854859405 935045314 268869680 467408177 429808599 829512046 686944687 871388767 229606907 948597543 941734291 968962131 274087792 894134293 939690924 975721614 566244941 619482506 360408444 535755278 893625375 930520022 552022278 764929444 259146370 735705115 782839776 960653549 102557008 728064454 19784091 488918706 687332059 723729125 548483796 700618245 957343844 984720918 935384205 969038318 784673849 831037174 335811191 576285647 546283993 867258749 305706199 444615791 50268096 76363994 978767613 998686528 81544162 620609726 613239062 850198079 170817886 732266273 198139592 710923735 597658357 837592464 838234865 878140645 815232003 909754945 145524835 298647724 396111810 412289952 607415267 753991513 421213047 445478976 442148546 623409132 119139889 683929294 643646472 646806759 492109511 969913149 976445316 994434059 443078920 732121324 665663799 893492891 89142078 209315722 221266354 513239050 11468065 237255243 686969787 798370005 948078421 951732462 734782337 984216478 500031859 959670502 235614328 411992200 786306806 844400693 447570150 658745242 436960233 979906165 617192074 709680003 481711543 686078223 627120871 785015289 425385483 521027874 157768268 768046249 895275322 999866732 955267950 977362444 442443621 697764888 458882039 813125543 634854125 849418906 537102217 746680905 943673836 997403322 121581703 483264709 467040954 799907837 521723082 705007376 577442283 669936177 699395574 905515228 358933357 890105776 402346952 732263244 331792377 850174206 855519398 985065094 512840872 723003182 92958471 642035046 756842276 970606131 339443856 644601041 315036723 545525380 944807178 983478124 230048202 869843584 524930805 805483411 301351359 963707968 849462669 880761099 524001881 864649147 827669654 859680896 273768535 370917144 347465797 765420348 524147329 601480412 832984606 901903243 218475396 906060465 902775371 937980076 722558470 858114119 406533856 929190062 508951125 915774333 546381796 805235427 224580470 671521915 525244789 972922305 976050977 982306443 800844355 829991059 478290680 936124181 834095585 924855189 688816776 946130417 585220558 790854958 70945167 476052814 545889724 878504089 841746040 998772814 344797076 900701393 292206385 436205458 249600398 390387539 969053837 969745694 790217173 846795610 546860019 698074323 175494453 498767946 248700468 956318676 948512123 976795753 629755911 903248675 774524442 840055262 927370930 997896462 466230415 727785451 148446435 828845150 641271881 991904033 345015013 466565756 789301523 982423244 981258234 997022253 885844726 909415519 492672378 809636350 895151736 900032495 662750053 687775600 117652197 954605829 838633290 936403709 166283798 915193701 314566115 623388848 388068994 462804294 479201452 515866116 806151719 825472068 238181225 715371252 157789517 815845246 750213879 879914154 447378555 746935238 707799532 847784640 644865948 681994486 606486367 928720803 517870177 674032494 884802300 973512888 917093075 939985214 426464526 983435787 216965296 913628133 535719536 619359459 204668435 500847650 171623250 864059657 56512337 281411876 953817619 998858941 861323326 979979908 216343037 436417287 642882268 838560815 27239392 899915313 117173788 297350501 807188704 877594424 981753036 995488512 769387810 838167732 440047324 451913482 219697201 687121310 978974139 991891985 965564963 975909729 294842809 822898129 658042232 880519136 23129784 800619462 766882875 988333790 129140588 213030221 276592933 710066316 720770401 762668059 73528857 654207284 816657011 955535796 835144579 844613476 808944053 957523635 804879829 937154225 109176304 335863332 170934181 303749503 222444320 695959755 31553700 756423032 410794420 800299019 523470590 828942845 66994824 989550293 915397984 996122700 779444781 941904194 105228935 415930347 853793678 908704072 289387045 678450587 431411652 599166590 981864026 984662021 386463176 846420512 247456090 741785637 507638640 577042573 621804600 729933333 732950710 935512045 681189804 978365419 339196176 806658897 938668480 985726184 586186125 601745775 867118027 916829015 982590351 995146996 131313909 990607677 348661390 348899579 346881344 420236396 45509488 79649897 304507959 627321053 851246652 937532439 691670975 722621477 622935347 901813772 718724573 965035370 643100994 856193737 368916159 396992340 325585569 904249314 22931998 86627814 113639220 776948780 587029055 834124864 632550380 963696299 721339413 948686542 886809713 913679360 190175183 219098570 623643789 806687490 505565653 511451347 399986336 868270797 503618821 551296756 772049670 825089687 678194155 692785288 446337754 785059309 787801001 814301796 972327201 979775760 151763063 354739089 618876930 754787705 37138665 635777321 952721460 958489175 268160810 362787605 427555352 464733381 509392630 803621838 167621517 780913115 95987211 502869898 645168896 849481115 301631886 420899360 685328626 834269428 128045263 145902195 308836309 352196298 364616577 482921078 543506399 975273764 662761058 769919426 439447258 611167790 754166304 927872984 496973321 796045001 528787315 989544782 726489974 950537735 715478164 730423491 219829238 799473075 243404891 263540404 374967525 831972622 62978785 641361431 25819098 412733913 437874776 761977840 316470624 868377354 532009633 798660042 897516512 988618035 162266437 558363955 213622477 685101033 567920123 776811254 394338857 858181437 826544594 983566184 287477766 417578368 895489588 951401569 755759201 901419948 324163909 533269482 459379971 588681442 316440620 521448533 610942156 613097117 602699247 643043940 428557106 771524806 407091717 654822146 494764034 813367166 632332361 708984852 36324767 543304367 938510770 993595459 129656727 249574470 684681912 938590254 935627650 980530824 646357602 784861309 928699943 993960866 784864165 809407365 912220343 942319862 540239122 613934269 324494971 728737494 982831513 991861994 451378763 826616289 352648679 378850685 590961723 938755408 416604060 492883788 266098385 874873623 146157649 635595250 188511721 497225551 52626004 681924955 937632432 942692148 945942931 979555210 329847171 845790095 540312926 683185860 500823555 726807119 505836238 512347300 889132734 977196515 686609335 910836886 330312026 501837297 48852415 618494724 865039507 984885877 293071686 797804349 594959013 854447541 754819469 834376250 94882188 808666971 525196859 614127648 558265258 608728036 834115457 911633066 947656756 981028254 673698808 853552323 193495289 971995867 915193442 931618488 759925004 829467919 554364472 702978847 912151544 959047200 489512035 847241123 36466723 411012697 791109227 798427120 984330858 992804614 426345827 763217949 194905754 705220819 806920726 867808369 105844172 291408551 466024675 960054900 22206485 607922778 408347944 827632677 659185213 769104627 434121398 456618305 381135049 897658850 784728216 792260568 983418995 998807117 731664324 913961121 25456390 783673832 588730264 912949499 573691874 953914769 520312216 837772668 379770648 563607676 269933930 645697414 79392173 469956805 268677845 711863422 226313433 793852298 554620593 990548096 778262624 947112158 478200300 938004547 399320864 541555656 232152292 477039134 936384752 986751346 74283750 157303028 748295379 753024933 274467397 317937313 606804995 747554358 895066536 919903654 257374300 513992492 475710438 821043186 466859127 612770782 554236220 847777974 631936850 727842633 976805640 993213982 226155536 934840945 590176499 794572199 416465133 722837977 692783689 804414230 370736881 407092030 989014223 991830153 730195438 947995698 444210251 900326158 30793906 900751190 185821522 186706767 382607293 422734055 253532648 541592457 533980751 815876765 57684246 992366383 697781830 896973350 372458977 620379617 479805380 627033236 100150986 921846192 477694744 632691024 90245495 135104623 478048666 864158849 939224394 986138124 305691463 783440918 833316949 900331573 926656722 968967408 46727018 886408218 185168509 363027935 914984673 940719488 600099512 637649015 836303326 864487282 11641545 563213925 261486599 298235724 432985872 750403239 252979014 950093915 341449186 766528250 793639715 809755417 191458453 369135939 684753472 799310087 533690108 876678458 851579563 865053227 643055026 683021263 870240668 949828091 671002776 736412808 319990932 472092754 723658092 906975024 24690506 412560866 580460275 721798453 575969833 960060735 781371695 911086932 303438052 544633504 423805223 997417750 18049980 630314263 408411925 743334193 316295113 721133253 168291893 759168303 838860165 862285190 926019231 950432737 661697397 916477871 628618292 961940317 590024651 794936274 959432353 971521439 134059999 385231399 821784367 919249413 591467221 898054933 296389490 836302926 217897277 627115483 749254719 791842690 906310406 912269772 944426521 995190750 706340945 706655394 16354492 683480437 765492783 817911255 929008690 989450563 987412784 991106603 609367736 660969986 809199734 990779404 924810468 946419941 820116526 924883235 852716649 955492321 572005674 996507291 760543630 975779473 966778922 986407615 829929117 870325684 344001155 454687036 203326141 705133659 984010479 984316182 498407599 975761473 933229039 964588390 35981478 577238414 919281680 977644076 625173300 823351412 222002576 581822172 281740840 326189900 121246252 981885577 971071769 986107829 589279036 722964157 23636671 110906990 191464777 511856107 531058873 765102633 80321473 491059358 546275415 891550917 199209177 240694758 537451264 769472578 746119044 921129053 683808186 747917811 97114562 705787462 23494311 536864902 503534261 917751182 668954787 735253617 610264219 666038237 832132121 876809350 126013010 614621085 768918437 833538854 840042232 972853692 174694538 388868738 111769429 823201726 931547606 960949388 540584392 686737383 749116736 786782905 717059803 966161781 575925815 818354497 260824038 548158451 251376944 653741906 294999040 866609286 131263564 421639788 797224980 907426872 142636873 412623546 435505490 478898794 811165893 967760213 913154587 994610898 81355033 922998818 951092512 984040218 903633888 998712081 430091582 510271268 862364484 980891695 359724252 621201928 798434153 804022323 822820364 927667460 604295035 706988545 736186396 766342687 783128125 955094739 195349593 955479358 191817509 774327283 140866746 352968704 348358062 533447814 463634879 951466168 594001227 779511476 24116155 404847706 461199808 802250985 565156351 823577938 822576333 922370714 784093126 929687338 330486343 356979774 624969316 958621514 19241368 779030591 876177687 955576490 876679689 912412481 709372003 888644994 665185959 991661366 394497411 809072428 859763759 895711948 623771863 823087840 637286275 705256725 613764836 947481734 559461440 692574545 986639048 995961704 503095993 726140448 721862303 928535041 642889245 758757875 816827271 956843065 532889850 814249537 865804717 905234734 661442516 738531096 54267996 952555556 845221685 986505936 50079417 488579228 715043896 969316458 842197279 884977571 626607940 972126263 291544314 833014517 227924560 817142305 746284283 944261063 469918038 712290793 954815389 958560183 505083813 954402686 895725382 991470412 588821418 986856343 656497445 747115506 880536165 965519361 632020156 637360599 885553454 959165588 355081134 979498800 874433920 881271171 60298394 785123904 627717513 988651952 812246814 955460683 343598436 349325857 772083542 908863547 341718580 897804164 805089233 899509436 35149051 941030608 795262090 858688837 509014976 971256933 355439862 646610970 329750595 506173888 931756968 993721960 759575498 933173029 615685449 879106856 309311591 372753473 588594018 829692967 302548070 796735515 584717527 667498526 663291340 848344509 476753927 775516281 56674014 186672840 403940345 897197932 182618194 988388946 111160663 646952278 762045091 901983604 649859604 963779597 361582173 483761248 802879079 951957100 748715981 787987409 497412672 516332003 88365099 211726479 257614386 528465640 81315173 237758086 338913356 600551829 194543339 382462767 730480556 939872812 620070555 628889352 309652972 468373313 998904692 999299019 377123394 759594930 536745578 786603742 127304965 394061319 347231411 796630144 149627344 399258243 621648478 991381498 380909231 715304887 357720018 553658088 53604151 905272322 829712166 845969641 415630975 695711856 139407466 203629418 474280146 913513863 821911348 949613261 911143591 970032105 231208364 596091195 902937113 931001411 580744501 639584703 984347238 991832279 332939327 864892157 268750138 279664776 172409650 750430097 909907901 983961572 520594334 550607847 896088057 906147511 553902458 632902554 781522942 878987785 584063799 766909674 942260450 953990137 977831298 978559546 198277595 442337708 14032946 524572960 158161914 328303902 31113674 322197843 71436695 316473261 183891079 466192704 415564568 623018188 332601054 358485376 815855535 894212396 33946248 701814471 949324948 976473125 13370119 386049341 266547856 727249202 61556926 986572230 196839793 408215539 231309912 397963912 895175312 903975615 235189386 935091289 111830051 392322964 255379927 440728587 851602212 966502411 275991824 552927903 685262600 990642589 722992108 997656379 564598388 829073934 599641910 796809552 14869321 805561652 394495114 901917623 308934307 580634201 576333149 863903053 518608520 970238361 735517352 766909749 303552322 596379010 270555557 913682225 59270188 257432033 870229413 903549610 51240513 738612943 878581060 999672987 993662417 995251025 325776777 673650756 70698976 288937019 399074760 503431602 260279825 651607253 244661670 998025716 52954747 290343278 909654776 973828286 284949414 758284008 854779141 961677416 469933809 620795706 496626807 774691996 162396831 170872780 94323116 942026071 278661177 557029473 374112418 402639775 946858404 986412167 241364429 773908841 176135389 577967424 964148896 998740020 203702945 717976182 413698507 736502432 684520752 884764127 661008266 906353065 613840614 741726304 790591024 888240632 922747072 989317900 402235921 715432852 141498513 864898760 597108369 718721591 362652919 495940782 957699657 982643662 804449159 986422203 38142352 874409689 670102733 853688062 921595401 925765288 517061985 996424843 243032582 347991215 543355003 673953583 669339257 920290717 25248834 136018261 962416551 978084093 229378695 500882062 57211565 859885237 230871157 901764691 219681765 922021387 941808251 983413849 84565605 105094327 895644262 961333953 448375337 974601861 207001643 380962567 276640056 592753199 563990758 977911644 586003894 773382764 785628169 856208778 910813294 949228432 319115294 565894189 300018195 320862580 162113624 721230918 312315560 467595680 532704831 753291043 299995082 985772903 690897114 765213083 42544005 587982853 754065896 758114129 804426413 868866032 503480265 694796277 903169945 971443292 842011624 894749913 978732132 986964349 618043789 834665521 478757266 514660167 859531298 977592757 907935566 970927059 32213035 322622266 264230957 463137727 742355414 768594844 379924950 387857699 455514641 966225784 906366238 973105039 49257531 942665747 590726240 888801423 573793158 807477391 316767283 533902950 769796744 916699407 274094271 824520194 786229609 807793692 608990884 931610098 296798339 889713675 19726454 775212879 770829288 772646002 296038924 958885936 451872830 620319050 709209855 972360610 303977197 644019052 308941770 776287937 89382486 804649632 411934194 602269479 14078151 517840609 27512050 111039539 666534355 832748001 284565143 918185544 328120433 498273717 195738814 851957195 95583263 268952526 226386534 701989436 131552493 938512761 954138266 980845771 719004187 751447337 846541729 857808965 766538937 848055924 933999588 995116769 710328859 830971926 958208210 960258249 388302008 749054656 622647068 960915225 758499233 862285840 904099362 979712900 658074879 707803794 261258972 772961668 863650961 889747524 739018020 988701911 780150690 907995417 733809598 791254801 497560985 783059779 301784132 882842566 688413117 789845206 946445355 950484040 158794756 373697932 440455907 496815389 872232826 975438760 582860901 601477707 974507028 989518741 600231619 928457038 535995167 900561661 451517744 847920683 12878406 277492134 406999112 653458348 622861413 815733966 992745233 993978278 146918937 352221666 75374551 535480330 785214846 934341838 230788327 717556929 866758448 977123125 535074808 881250293 652625871 767631716 770571393 882828091 450493979 832598712 779493036 956530362 62715127 72082025 587412011 719929902 542951077 795918760 274924112 705115605 375730239 855269051 283268199 455356755 163796759 907233615 778114504 795563559 90164046 231257621 540593597 618284731 924020207 924380697 164778144 879695873 412422966 927421165 328159372 943450948 750190166 941194164 586706737 636238648 183082850 731161171 806892748 901796961 830367153 853463950 53017222 356305091 92079126 107026390 989693269 995689007 903310099 960373085 350510376 636176309 570317712 686891760 265858929 495920978 466964460 936952506 704230469 824288742 271163452 555444699 351078229 585496484 65647405 551248354 608666377 751097933 114050815 287674942 537300868 541566189 381900157 558357943 740212908 774963659 133959300 770769274 884064582 895322488 591863002 776665551 658126973 676608578 245941297 839064636 578849294 672300053 558027881 610339418 498348881 867054014 727482654 874819511 950282407 951934895 93076733 288610634 838005563 940834205 798364371 923696182 307570205 935337863 253709131 517260782 763506960 874042976 720555806 908003185 472195340 743965031 669620862 875974839 62156858 989406793 273039623 653825760 151204696 351910158 777829138 891951366 545166163 762756036 31137765 519915095 942121276 979608427 705866270 956195685 951496828 972600019 489314073 493944665 373315201 454611482 717403034 877674289