968 547017375 651988856 263053859 555193514 966813567 988084659 651814855 815462031 399714721 704079263 826956566 874439248 269960675 681416359 544755539 859514440 900074492 928402420 363118533 521205904 41094681 838387219 243742065 725289056 980965573 992389597 747598787 967688709 728546132 912891001 92801144 622274754 704090496 780620910 296959253 716612185 339229922 445076541 808302853 932151411 140578576 946508012 107908991 656996254 602432063 706310050 220990603 221488163 326485032 942487564 668588002 707191340 614287548 787812306 686076647 846187985 501102310 828077749 467545267 795197891 154755746 731000508 920846314 962676494 337391405 755015005 667718367 738325616 962140098 982134494 125324516 173104191 581522794 980586058 290709328 800936650 252076233 575182134 762847400 812516016 299258087 644673335 726258245 974093450 526925560 529956687 920128733 953394211 823867616 842049313 499013525 835787505 459453135 759925025 151432501 828240346 603959519 978221209 853769654 879857617 264871130 996511507 129852868 737282875 471594387 701654514 159303532 212999060 593964995 821834711 900060311 980058357 104547521 786837350 706638882 844998230 745320754 836085500 858544200 906842673 948054605 985405572 201685767 707442013 737277451 771540130 908907404 992542869 117230595 603814663 766533229 963066713 217398922 750812211 47597668 120628085 113199822 197000323 25472858 46947694 538999677 717790672 468189377 484319881 581833375 876601393 462644164 823260569 845304117 921809153 756158776 870806469 142416411 722211372 25017829 245760078 360027845 539952845 418072545 816491609 864463704 998642265 31022244 39951215 154830123 550366536 960054223 993857339 185784008 442558322 868018814 933018223 484050447 909637349 917406494 985918340 867872609 954885126 172870715 389314011 991079928 998002700 303098699 601647050 108016220 717411911 188947259 537008754 851693386 952320171 543404793 566987373 309125424 555840329 855754191 953689949 498874455 850560193 35454926 306517546 735884573 854068751 520161643 925433051 815787048 914195816 832101570 905981907 475328204 653100254 282822741 283185834 33941007 286814811 727143296 916037394 904656954 996322507 371509766 381990209 465003723 554432755 317431912 986205982 965627354 987579335 659694697 981060488 537695272 856366359 761748053 913327605 954142556 954964612 912683459 925783949 13066729 291597946 840991197 994293263 812022978 879664841 387724080 577609259 421487157 616303006 583379398 795533157 530750109 817291619 262123335 287896232 158549835 644605111 229565565 823624598 694536085 710460350 629653517 750460130 970285269 999910035 812810849 920808348 238245914 316833391 763838612 879596691 184014890 686396019 387336619 481080107 222098810 876560883 178260139 626166946 120482460 336044281 627639625 802460278 632014975 984597833 563407543 702821342 680053301 994466863 311143502 665747796 472079481 749574246 307850606 702723201 514919694 928496710 407695421 991778020 516430708 657537922 476208141 543667194 626812011 714135565 923123957 967380600 240146872 456567824 894884783 959553500 733217549 838701548 535419934 727403206 745227402 762506275 53006671 784046005 450847682 524243547 693604115 951842712 398504126 492422483 703774738 739539481 617043076 795696905 371593403 811715828 90981449 856154183 117843002 127341594 794907341 967713717 447129501 963314097 567145077 866359403 220478273 926165877 405562219 505814338 25166317 27102081 697685287 993040519 620617747 863355774 455813982 456372334 848579780 930850564 146995742 197740444 84514831 875451158 982951918 996383804 363561663 768733993 334093085 479191571 383060781 406487258 720740926 993518003 601941059 990706930 106199647 421820826 223579484 805708075 776547581 881885109 541584221 943967854 296602864 520840506 335675580 947731449 117015884 613491478 987041154 987741958 156676248 863777393 326097396 950629309 915223719 973479153 292868253 751271932 996475931 997398921 503776915 896022295 819847018 951152765 903284346 926733596 417030467 538919737 558656904 891078856 236292941 778266362 564561128 933237290 750200849 923555341 767871802 839249105 186474159 370374250 196878321 416995922 655946315 876801717 875439157 910369866 803865012 892397740 259032603 927977095 440493909 489080198 153403310 409775536 194860571 375997259 92042738 881177222 893022475 935482832 698276256 717829864 298392399 963586479 882241848 996608215 568014825 827566184 908401344 916962594 512825474 935680190 167201960 404087542 518321036 903168173 743594269 839041572 114085181 570213045 228489206 603237318 723736633 733397231 66037156 305438839 929334755 960907089 798263811 902332680 655085006 987860457 522450855 771942992 613050811 645058821 311057395 575073929 343340567 908832757 39275242 170276031 27744187 491050207 317685544 902440948 314007005 905685920 694169099 848124892 688863730 777111089 741801030 868479722 179465345 821914837 825061882 906414085 366898169 461169509 606876829 769110862 236804487 991159002 421092032 565977574 57288364 796050506 210920761 881593146 246524004 891670204 368713265 589950770 755320623 992962792 88574862 176390599 759988069 940664126 139146372 734374819 350478370 873934405 220766591 586638798 128180708 696102042 517751473 915332332 626514079 837550860 98581755 967419561 248771566 522943231 581724742 956848663 427942363 962968486 52254134 643899527 20528830 195480845 598425581 673384201 49198213 584875438 977002560 981163493 409216849 890625782 475254409 622690273 792703205 951877269 329994848 558918497 320200581 460403524 137739380 360693415 691259150 746524960 585705641 678701570 142594456 157526618 249499479 385434562 941490754 943022789 731690169 927254995 102705863 992020535 475252764 773243723 597074367 888879849 265911225 266218893 914460789 952955067 656817456 959545613 604592621 930972879 477093757 935727118 116734305 411863047 214467837 606442369 537196208 936400292 531448241 757967228 386129731 833053099 341161991 457933392 992798994 993411210 762739042 849360025 604788244 987034864 193956425 806695037 599266557 636677485 626393764 722651192 651195091 972457011 491719644 694311266 636448287 788169744 488884743 564356332 267860191 650535375 686415879 978015196 858182017 913540172 331565038 712605787 53600796 983771180 789708163 980559809 549069788 815859609 33662144 735407850 709307934 756849530 580565462 822540045 746506987 991464171 612775209 879388725 674798068 881056510 687287970 714170732 627523574 988266525 489634849 989380161 302878230 399650832 991302524 999639967 587396670 752459757 844629465 984933731 272220544 759995928 239381115 886119610 56871694 111065753 206501631 479764667 137134191 186831600 576724101 832182096 180557819 948053539 530348920 933334160 208825346 410132934 392174003 924678865 888098144 891011632 706418179 898272430 76058797 576547473 26676133 30650326 537138767 786117795 646784971 847402721 846019464 924452003 552700978 587785899 509918480 634907030 68107376 128269647 52992113 276381144 677945753 854428833 416900948 449369232 664615564 846626213 334751825 704187826 477911569 873308402 302300338 749490245 532409518 933571615 954621150 987954296 601639162 624048145 422402616 890500858 682241896 908875600 255838992 895921023 244216895 483513460 697453878 835184083 426369146 793493253 762296450 786147221 763603935 887702725 636918202 860181494 846970952 919668847 901433167 927197249 363657628 448556285 948615986 978757625 378257944 873466616 142413131 672010014 901302842 938072748 80285065 997246472 833662793 850226857 315922972 707374984 305978988 881641211 524736652 557544909 875538850 893582935 153210513 165634663 992973942 999204578 644102024 847714687 775505326 954921396 310640711 621931819 410081968 538704279 793741702 862530239 745574732 843074128 147016153 195045493 481427982 603816049 423691521 670058471 764888910 975682840 580103844 740096329 329471263 967573316 216079538 534499700 290824442 978633527 846505590 933470628 143882699 736567084 450174821 463021296 169821944 378575869 249162916 340386749 406942714 982598335 140059379 976531673 852178966 942220612 942781425 990949133 247573543 951653004 751429787 995513806 47073800 784682040 54768058 332550383 655001639 863098714 519710023 674557108 905107858 964563667 35125049 100321856 98976763 283888918 191882122 388222062 313229123 720677274 844943152 886989869 71393098 330424566 185627126 617617944 177263699 997623324 430581571 712450228 426203427 658254633 318082713 475196740 244191323 835870845 773461247 927380734 924745355 993523190 913280457 914283715 81111152 794817115 70159974 871907607 54614649 333014913 981534808 989181624 384996413 398182813 881058823 981369591 953493957 969818609 980987791 991313592 397634902 441293939 81508577 304257416 757920758 917208921 323999199 560714928 375885196 510755089 594332513 979695866 642423690 817690493 569874458 925084818 677462618 679194807 218512852 740396704 243973046 698735336 552995169 661516202 741830508 934217916 74595967 451338418 174117539 213697327 916435592 963441557 872077341 979918254 690397263 833590192 671976758 773903049 771352542 835175558 31769823 638642357 868201646 910719163 323675611 793095858 947331892 972895555 794888303 974012548 332648033 559999682 978489125 986509792 273805490 688059886 268650295 967074866 930901420 941290629 635135741 964024844 717747296 839714796 288585954 395640098 915041848 993203312 469587095 577192306 172457728 275612281 835976791 891568413 649823108 730802278 585172977 788971438 263514592 953083156 491147972 964081822 302986629 670306766 980187183 998702125 433787584 834397921 767379268 882534311 926435744 957048248 231463599 768160558 79958268 722888758 965227513 996381043 551795255 610355697 608903849 907950230 286936915 786831138 543786576 902004700 27446895 400211545 214825733 281880916 652703490 782167720 410327438 845227374 487100990 655475539 495780261 942687595 495344496 962051981 879301167 992612266 907413642 997592853 553389211 699978955 530772899 694719585 414702542 871111460 928395589 931856083 417907020 605277318 185155466 557828906 911957158 912656129 205603689 602599594 566448695 940106339 427918884 935874247 805741513 881728604 695071533 889898939 901703504 944320925 604301220 604837149 132231572 765003905 438822432 513918934 668372706 902036194 956515553 968318194 395466623 640088808 522811097 975218223 900721526 932407044 880030017 906299572 979851541 989116737 798356988 987207364 970578254 996722352 591530106 877889398 866259753 933919079 777708245 818417458 986101025 995344654 592914217 974001377 707599327 949455022 252676658 654232109 612478519 764984646 502215096 597584498 725992324 791573724 785273626 834887851 623482478 635315133 106022735 401088425 576275232 940436197 572085300 797042817 640392515 842419048 699036778 901186176 880885147 897571614 434239578 841596553 269411130 828957573 777356479 850137630 777180210 826972861 741130723 795530788 322998935 772825253 920192591 973419228 261179735 759497033 468909213 803382233 398965751 526321346 626320098 813619004 922651392 933429218 769509801 879970675 103403036 633852419 127710425 282205334 911279326 956379907 856871691 858632414 947401438 950678104 856174580 998387426 46980476 942621466 918290745 970887445 14184594 352646752 419488904 453759410 912375320 938623935 963124305 976490437 117986769 538282686 535228761 793129950 910605684 929837237 183915930 353873121 791751047 877255469 565305059 677585659 45298922 199513125 406092862 465864624 649578212 788174391 248317006 539452617 987461998 991265735 29201272 703327657 210543075 945091161 320568305 916560006 422619513 506562460 89215070 891041858 41693958 388589429 517600661 854132184 933219808 970494912 261293313 617056142 25973468 766598692 229328773 516904711 157846816 322004929 62422629 945579826 399063217 560739124 373789881 455253135 834066066 904262475 217107004 315860603 929093711 981660977 550085013 718294716 179670767 324692295 185438356 263487287 775488326 869459287 178166252 209478851 18031611 769988550 243914689 993735832 711620890 986154735 817292045 905084442 149388613 436680428 493134864 884541993 255071348 670520447 307376255 595897155 594088099 922897551 739501636 787362098 267590317 689128418 299937141 348773840 557065261 768723590 446287434 667999704 291791384 639399173 228428271 414264573 109572650 384319171 843492756 887995097 247644226 473629681 770711497 963287967 735665175 855465256 430504174 948954254 12484298 399638619 454687539 669863300 280045074 685023474 498030708 540562528 961758857 994012272 497283861 808841677 935175993 943154199 909990983 992859914 719775174 867506861 136996665 533722033 16364581 126780815 768858617 981699095 968852171 998230174 358196833 771614158 815485441 966882179 265712236 546005608 24025506 379690961 585043672 816368907 321229813 622930665 27245232 635211821 286966433 412310421 964706110 977903660 814508605 897981453 211181912 751505452 42001997 147944336 49903770 64334815 45071122 833079239 59944845 759608179 893848740 965629342 110999576 304152860 860239219 903618234 539452319 672039570 584561189 715678209 980303645 981326096 231692754 549508171 388105187 732876976 276935847 917173358 342523561 714104521 580567759 784531623 372490706 539927052 582797172 794179925 91663555 338238682 224265551 883393619 389460183 834045817 672627341 939784322 12883448 469342412 601261298 906045780 624320871 927386653 256168952 258786165 244529915 540300440 487319080 925297421 849548076 966658380 361841416 641889375 954282018 991944062 434447297 938953607 722720595 848354186 752741556 979671915 180680182 276209820 540855361 763441257 647164044 919716757 22853309 132796662 745670962 860580538 158677623 997315450 235845440 562814200 694936833 892865712 807239524 826817390 498074816 529909935 213964545 986791027 889628154 934097670 382739811 899919382 679327593 928136918 100177348 705642031 761494848 847294899 627310206 960434387 299496779 822866029 638179946 907784668 161172916 388787642 381428101 772254083 97578150 310747880 105105779 268056280 539429594 540963961 825637480 878125059 312495826 414676126 545690404 887722420 774229026 953565734 584540456 796918691 473688855 833346124 447211203 452011346 976375302 993490429 192384439 377340566 678354544 859217913 717335440 931220723 454730673 754017931 913339259 928195297 172098885 372470219 333142669 748778376 715321311 941749178 645731616 963479069 191271479 503997639 732705943 838326063 383866846 704352763 674720621 875468562 442368273 677038339 260661758 839291882 724090792 741202531 356988655 410888966 445225238 608150605 839861461 997460293 982282798 994637474 603353753 717982230 973835571 999811734 306761241 452582688 373343180 421155319 271620608 975387976 74106819 995341390 447882635 868864898 117779336 939184711 860659904 879392405 824434658 989441623 43023743 726122728 337774165 695293893 328850951 361245615 902353417 948948370 716426486 800206983 978332396 982549435 189530263 425140811 724311051 814170377 76840839 709843734 803298142 937469337 570990707 746764315 945662132 981761706 578343268 717430804 351150703 412530403 70074839 948316036 311257935 746468683 293449552 624338392 350809100 389097497 628410029 854529375 598110349 887293690 408413931 859734564 468233582 949671467 655470406 918705305 339935135 492681077 805785239 930813364 411586879 634629755 304090984 964797596 790613866 887256037 387690672 656861223 642375491 678092559 396260131 460128048 69201962 138265385 731561899 779451890 56962479 369280855 223934983 562808283 38775037 985625243 480850047 986591921 996557287 996574672 304288226 505727724 270126081 343580177 495584891 588980668 610715910 977214124 394608110 491385450 686378798 906417752 887141748 994913313 190710786 787766320 759670076 954832491 361532759 654781869 392181720 845917944 441636289 895898731 509135296 889578259 814917510 983667972 395761969 655587420 210819239 892555961 323018666 897268140 513269531 579566994 918100610 938764452 257558594 889139528 503638575 750503150 41041661 186517113 925027702 974737526 621180936 641821606 269025163 787906021 787454122 838649534 930270564 991344078 308776347 728148270 221249795 693547704 512983647 960009258 741880142 806126409 977816550 989908050 787759418 997849731 99229992 911252041 479607978 554778649 138571591 701685191 248180057 690835520 251422921 465909778 285153653 315098743 979596128 994923971 884129298 985880071 355549183 586737847 905727342 914937917 352851963 463319870 582092901 947332506 988585537 998157796 353217670 375871832 168405954 525655061 225339192 676293692 980980711 982381582 595964186 748715705 581751170 910726515 82850737 113971507 102545206 977940656 240367921 508338096 546287219 760246854 644182782 924951324 701188526 936034951 88294902 452290788 87849069 326283295 868951991 946236878 369475251 796695796 551732968 883914555 54080500 249214827 601709680 764815276 67504724 116693602 231122519 932581493 578445087 604822245 914202998 965073683 900886879 933494898 957416836 957893707 383346163 859306004 593135946 858753060 610558986 784487559 597420595 954403051 87986630 854954284 570317279 671471441 386811974 548867160 756318148 986765535 220465796 563160715 724409949 735864609 505673550 661778271 142094353 575706276 730904311 996894159 892351008 988429682 430767743 656884843 432108673 983834334 202627957 778549530 182946343 615900065 254783885 549177763 335705505 748158336 783891915 825867743 880031969 945478517 266179974 997857062 835750390 929869354 143942852 202595096 319032799 741668310 792317829 812055703 431831263 787785004 349400512 471993222 491855601 536934511 484628903 933282821 130089741 877434568 72128026 216667220 158913772 168194677 578041930 846994591 47685482 866928090 490482942 851571036 722512598 803390988 757061036 969348162 427196123 934445579 905735059 985206166 10805255 834918770 720348471 725970636 652760412 820027553 918454740 991826143 434861536 743059288 816215514 994065663 50226410 359410316 634234686 821474627 76053332 411700473 808369441 911455055 500490049 669378309 733005453 858248064 399868125 551334655 107911819 951918176 173803359 940772233 850749696 854106602 513826028 608544732 910709161 936061255 603878464 857304037 904172249 905172402 783513043 955060034 683835049 921764979 836798651 847072483 612911566 654171889 884935055 886358756 120013158 546365401 384939736 690779484 566787336 983991288 339757865 667201517 776691650 900335068 818476599 827041161 75399773 676845871 179221224 600768493 935625177 970727973 292511228 576553385 341290503 367659560 192530817 963090241 334346392 920525493 185956677 549471879 748528197 812596515 577655162 857347818 593598342 780700080 426898969 953019730 29998519 661444986 212229785 670800813 849281800 902666496 101621983 917949163 54192441 208537460 633908614 928763382 511624809 809307085 930459644 960902798 985146481 991852255 636071739 776133975 364425184 956177777 501845570 737407704 433154693 796390624 404167660 792737358 913960104 965299902 126748248 391352434 529716953 861684583 98747008 279353146 654557229 948382304 402691908 488436240 638423060 841047487 797442466 809609776 131432515 487604331 464376673 542685896 680684751 962378842 689341887 788005428 129896615 921698110 886513716 983058830 574638603 804544770 388217084 781890640 315802832 373219880 527733921 629333841 556279073 754121548 729765405 997847139 905820958 993136760 763563987 942062775 712124489 750515666 63174320 119137502 640166594 888496568 284814293 523979600 181987569 636048468 926271024 986072264 154636213 261584135 455771086 523417836 793286125 831741826 768687734 971815310 96079110 447559823 264776722 827308174 183425260 785308650 135985879 691086097 462915337 955146498 140438123 380146600 817202058 951400521 658605510 850053112 969266643 997006655 207259777 618375108 87689340 627655559 884724047 983646572 811738230 886850433 173746832 839579816 906936150 914164927 145299303 262057017 661031956 827748873 290261553 299410810 658198860 852599848 251528697 426884312 449805672 469704422 71181656 163626151 286290984 671675154 755935651 972972528 175021114 230573299 196406152 545760685 609879494 828237449 989228130 991602087 710979138 769302458 498343928 793348681 635864947 651124537 656923618 793316556 162428800 380927645 373376920 537186143 887377162 966832517 931823576 978264510 22579680 349635835 461093702 778901048 405497865 600874702 730972382 749753750 743970716 931010550 269242049 436958297 613734440 851473269 799090687 941971606 939714672 994776306 792636108 869917453 501926986 878889510 541147141 891793982 985712476 994465669 568371657 755791525 155714103 785006557 590869451 638359459 820805810 957093375 623781489 918067826 904143263 959670980 374346303 544460769 901071269 972186701 793815351 832557070 73558869 109090838 537498340 611705632 596749805 976350395 485955195 749622317 475599666 750956334 770680083 918481158 981558593 990826653 171275609 979324772 260404893 584180902 919940272 994633954 931174338 963011439 160387380 246970221 372310893 676065084 676579606 807921435 372123954 911540946 511737490 874514936 165174364 445944722 569737562 609169782 810822202 875601365 531651999 641952305 631784822 841668556 948438285 949280078 954184658 996827332 102951203 256205755 654301609 733286096 282343297 314612046 478789836 849942005 390532972 984957813 341720356 443295402 163003960 374879943 59453425 152129068 26560919 373499588 86101313 169075004 21143870 830622435 456677154 694187423 707860027 769789032 10331744 266459481 849679694 991729017 833150314 841797293 567094474 899663727 747182509 924588701 945638158 953112578 575747008 925274768 471417008 793483455 564155081 628127715 777596569 963347641 584432307 936706854 456478629 848949763 741984001 978357340 585518845 981952463 791532002 827437288 663221857 750377223 406460661 501806984 741223412 921959195 552913004 815340601 528070944 739728827 462369671 511255357 652678678 985280045 583117185 725534047 536166834 563839829 257317650 459531100 926611921 954285004 988881842 991378482 304093881 322631136 995091667 998951725 642322720 749119379 565554873 832442716 151264222 996157765 979335473 983800301 472959866 584072226 957542133 963885395 74314026 666155298 676432689 718186193 916921389 971602835 455541090 563601541 802530125 977468509 819339215 837513065 931855112 946427901 427501439 949054669 754658310 778261898 729286208 909278763 770463262 785263536 15726341 321995526 165070857 771598609 551496856 562519502 484877443 706241323 447255849 614835357 546346308 614498669 567995891 802410741 479352087 783692535 722150818 863339480 171352736 711807061 626805673 729787067 423525678 696138909 90124619 188419974 802873531 910510664 543020567 755326512 175426537 751102569 249437965 411850138 557109990 834095619 158986462 800641808 631733643 781768394 572187750 806592475 197253517 661503893 620744930 856331787 359201725 387374990 507998234 784263118 575503729 990917919 509775369 547247599 486126860 496352189 252060695 574047281 738747267 871010326 302089364 664604637 101393443 559780400 422495743 963639490 136279189 263184782 693424537 803417948 836678856 955107100 457914223 752590805 927112300 988281491 527418128 714964110 545328349 985488018 379589236 994300043 952104973 976865201 352313688 875896615 42468800 703809469 463882000 707694875 203794730 624187476 231077553 925475672 848879955 900654174 870985316 889516381 155744383 989236714 89770582 268061750 65321937 996240862 294097142 901056335 458884582 937657023 579710062 994303547 593112886 879046536 240630429 525266660 971782851 973552852 549552380 720366143 67888933 204931704 211297891 256714639 327099986 992220664 154984235 815346917 164760471 372343926 571304909 814753219 875275509 951712965 469861802 489968786 412028636 979795454 139835017 910888258 975647672 980521210 469651636 785621639 419178615 896734199 618589735 845443296 282953798 441595169 426779508 813833988 798098063 956674174 380353036 886181490 953912043 984888920 631511119 706058902 845438239 881626845 365111944 661304895 919024541 934189167 73520503 527757796 29503835 42943115 144846375 590477472 357224230 993332897 193916449 268059761 64156715 270240745 859151118 877220626 981502635 988311517 315881551 884362424 579788468 807457594 243830734 386190515 371461616 501863422 597782211 682574298 777577350 890844251 647367726 846661415 278195265 472123296 94522358 922113190 235424848 825099711 219660277 461661834 674626593 827958800 464706429 578393469 295047268 486763316 119812545 217853446 478929800 796156956 399169958 566260182 746027311 963047336 717244196 730381150 484627603 717496204 691623495 836956009 940046888 948058381 178024433 863754354 976238339 981608231 760404969 949440082 788486209 992664010 620803348 838156213 718327177 856212648 280083643 582880467 351813584 486429481 773832847 791925947 135182247 183264647 302968359 969991279 996134483 998185348 475087183 990495565 471695747 480868352 378668334 678055623 56273335 711501794 869593937 961526319 34020048 275088174 196825179 333242342 501654383 570773890 465693422 925277430 803715407 957412405 650575630 675737257 81492978 983042649 378616899 599541549 758098742 949990823 671456547 990408654 762134222 930380392 792592966 835814082 651786455 662940779 437692472 534377706 473973185 870289377 44580049 282411195 443829775 509835121 437628907 863185824 339609601 970076946 142302740 979881021 879210834 979080217 939559808 981584044 632020837 929408412 701271904 838899846 460371120 928773813 714416936 763235047 505623179 800169872 72588308 501957748 763815938 891288944 546051690 559874038 733090531 959403295 317872221 938888902 686841057 752341488 281606024 888690790 336543850 503616726 516255330 696577173 844930067 850216181 273983173 772938540 202054066 438735192 937334370 941876971 273132983 629114179 635227763 889892809 252111021 914547955 131169505 879118543 749923171 828002227 46756704 202157482 927791551 939360155 602042569 621294825 729835521 753665453 750727152 906038622 831050830 907980557 755273509 826524893 825642893 835035457 741456675 806223061 240252605 405399301 795534940 879320196 133613545 197494713 252533297 996000350 401245696 996092663 939020290 993358521 933713741 970254818 289876935 758372820 556439595 775029995 927179238 966982800 466131067 797845359 196894695 892638575 171836067 631775505 119068702 896193509 688656959 926006256 964279799 992458419 644219026 671275997 926403796 935608936 296232191 405789114 871440086 891707410 364438869 766302844 880206447 945247364 908965512 934044024 816230938 940117559 212977530 666123865 479672772 708403198 122179966 474639790 661609354 723856430 281851252 649414984 672157234 718511625 169786473 551086537 737059404 974603961 93236086 961000651 863485978 878846513 250239418 606032022 645757119 906689906 412182535 923546128 379258997 601904264 624625443 865138317 58851291 921473401 109003230 170292093 741020719 796711931 529309530 694680079 739490494 760716815 710167121 728722830 725468159 726681605 733154362 895234792 503134588 656767443 520444420 717206724 117450687 788791238 715177232 894677578 782456466 980688650 355133182 765449221 937476222 999009145 863568253 922123150 508453415 899109521 428071022 508420219 165113026 661760382 202395431 317877651 692377848 978552842 165820273 986224437 231613063 331265092 741307131 802700167 893008822 959519598 901392570 948852589 804057170 849590683 117596864 566636381 217496767 849102813 420681370 636498627 142460667 902513698 345980042 839630126 876007003 976495882 605488378 900861865 970464042 996539715 792593306 963903226 884904966 950085251 968922520 976427200 360666093 459704795 11427694 57724279 857589193 909931186 275643523 797542091 904574007 942599380 840507315 898222293 269780101 904016135 431473499 627450920 575773589 684426580 362027529 566382523 82573298 878235061 592760950 956341767 629241533 697283866 379528272 506360800 407476904 910981270 116388632 665408342 278678253 526475955 817317188 858464326 446435442 464978302 695784781 735682559 637379237 663140959 105076517 704651367 175532902 189310817 742505354 826941835 13359953 46951722 582578832 609885395 704736568 853719952 641537346 659891679 842366098 932435095 424277557 656675687 806296059 905079838 51948377 133416598 627111790 769261181 222191744 882334356 86549420 584181826 758515742 853903269 133715469 809444744 757337938 819012926 85708782 655283981 218945254 394479237 184201962 758445499 738153550 908319334 622189465 791755286 347994729 535231131 701496696 839870506 533068753 681922792 37012938 324758438 435057208 831833268 372174660 548560448 248414119 308080641 705935335 927419321 914775242 974208523 375946398 468932252 484763738 816130715 666967597 842385986 597147248 807057999 528007337 951143613 512141378 862862140 951778856 990036612 37606612 515746105 398849940 669950213 915613048 977031798 385899934 442183493 996228385 996629288 138185404 897043744 752652958 970380629 176338660 395995100 19350321 773646888 528613423 942071263 609755945 918211349 665293501 787837992 481422131 493931977 503947553 643976941 662224227 752015646 54431207 527762611 763830373 895816607 970422822 986180333 567873738 785745622 839858923 869695783 331730646 542089121 669731174 906645878 127327924 663326647 796551841 984876156 672044319 976346507 872899098 992121765 674659513 857401528 873885496 907261048 71537223 969586053 839409362 999931118 58768529 815518819 192447247 648052706 666072370 782709730 313492699 381116187 385389276 494014852 316607116 722092357 910205757 938114505 322207288 553126005 923176234 981869798 755497670 972862064 862775526 870458459 307084433 323252528 909397616 956209064 289011771 480803268 389017726 437919842 133840570 647013728 53051692 67030253 793640779 969448156 454039155 597542930 946566524 990922743 782654989 924489980 141081402 919343157 467641993 904222024 866881548 963044372 439204400 487636021 246209976 490769220 53861031 139965099 379698359 840224643 864825871 929101043 159124056 944560845 360628843 568206398 695634770 886447517 386046420 474285938 814903681 870470907 268262930 837173753 369219010 643809280 139538257 142724536 271532375 488645856 934675172 951643350 803692573 980410506 765466625 803262003 964792312 987456312 924701713 967851442 639090651 726662325 92870641 765181996 513769822 909443841 748447211 943907315 975190982 991792825 847346813 889434172 984949522 998885739 135545972 914273125 193429083 768019366 922079255 983176667 153382032 715527336 655700801 914478348 170284586 406120136 149619619 200609181 262799789 948146442 82050996 639559073 202708236 540830759 214624939 842991564 665483589 792227222 425461754 950020655 222558626 436563472 304818204 619430345 330992895 414996210 304255130 396753695 176251624 375576845 723865029 857386676 598387983 691382465 910247915 981724092 39202421 856415553 468191451 655687618 632345481 887803344 379369280 627645025 173604223 582403962 562465705 855873645 224870057 936051137 222863903 598028891 954556024 972127099 967972473 994953364 274006921 955085974 447492565 646691617 532032289 982532697 151072348 256519733 619089865 838247085 903661378 937063595 885870615 941006016 875843822 944461772 439877540 794303734 773649995 961437790 225526744 711354515 202534929 963700266 469641013 611233340 540145449 831083102 528950885 579126497 519595945 844817396 777412062 984766284 440364959 851641884 477175284 744283487 838956694 958528174 229910204 684064423 983780238 996277761 367620102 774167560 93780750 686168689 503594980 743761564 921491234 957276814 243916343 855182535 503662437 762632793 60560848 375693787 819459606 912938719 136028332 603187618 748268508 974873242 29084200 871670533 926904278 962078575 100279131 383741115 143469060 776268143 721792287 756605261 315658054 542984998 556697236 964361326 753543762 778881955 798370267 995308739 155894862 503728944 47304716 385514874 162003110 784890308 53922231 405733903 602654238 644484300 693985642 813658818 536349038 703754572 756180712 870320024 602203918 664555114 963619205 966588840 654597247 880940093 858106077 899431979 283458440 565618131 426768167 811875652 377622895 422460112 916577195 961080488 907131858 925256354 336121232 386469672 129895471 415553277 97262958 125862680 282183335 645791658 364253726 844680734 214143185 877645262 596567879 647541130 661319467 879697091 971804624 976872161 354508590 536787922 585255885 748884772 477774971 711946815 872881253 984486602 953073686 972337627 977128456 990758382 13428431 590227093 606880262 739210885 903835537 924132564 623801898 665759924 380578252 645630091 490838222 960359065 307394154 919315185 598548270 819554260 88917012 351435355 73383509 797605503 867268406 913408063 96782130 768883135 224626176 792259897 72487586 553249498 374815084 910063673 471336150 501014011 100045852 619810751 333474610 665720085 391224552 511184508 744822509 959980480 297660844 495272691 151570513 746681695 658283505 935300315 126977773 781438913 206149190 853211725 788815559 838377807 330738940 695471912 133766150 552489380 452336961 547748080 575064895 766076553 62958524 694535642 844359177 966160841 424446863 969561268 938204985 965042846 841247083 907048036 978987487 994875869 95937240 453607694 50927554 116456766 832106818 885862510 531612696 619124616 429959476 952818491 111451813 861167940 430181119 981016423 265241848 518045024 943773739 996638127 875935179 925069455 718048507 867660918 552433919 730399394 636946395 683394460 893535924 941887390 77002136 472095380 62349341 465463042 506858948 583164213 398674586 924432708 469484062 765143206 528577113 923452839 490058723 561452511 719269146 904378132 64761429 405535099 32003984 715571095 221142021 571478144 757913996 847380700 956274129 966592622 349904250 743346973 497590408 577059268 986354564 993644989 594418992 956026657 338156008 493660102 987338812 995631105 487338027 695024392 125985779 584587228 689975556 698561063 310563734 656236838 52595938 189866305 250052578 686915195 582673293 773776706 376544911 537079567 898591344 902353340 520956694 751730325 457127632 932068542 580390670 663497294 449304880 500443121 593100758 705402516 274696104 952419116 605139285 645870483 985064625 993127123 204064150 944736076 21444942 377735412 393063551 670447219 681438526 845478531 177014901 656435705 983200207 997059187 16058263 521344826 234239390 302933194 714095469 987150752 638372073 940901527 119780575 236599723 901515927 970988844 437356337 564257275 426900050 483636675 977717908 997842413 465337666 493699818 247412220 943238044 641429226 732771259 741535909 859827636 525767271 850703692 289971179 312616076 406681666 676291263 643214144 824247189 782922086 898701667 856409384 914595378 383674449 472188734 425745972 908595749 488221074 888037084 746340784 889126473 37288433 507535032 433035338 944742208 255794423 564042744 184893278 691631210 532243595 902265649 720082778 980515527 985321896 996403127 681764639 819898287 759098240 933488726 650446758 916636698 895249928 945206788 427803900 591819872 607500271 822862465 954218306 989494631 393681077 843902767 46422484 439881133 808808743 963335241 62056186 532815196 697903343 951513863 383888306 785810891 887398348 953065586 285320902 999361750 210676172 652315509 523459892 575549181 140391342 317334337 679694466 781296694 815702268 860414744 729067212 958591298 178029672 861581831 231886959 315634951 867911454 902015989 357843902 532819816 433484468 584413123 403742119 472058692 975277079 991104723 175165831 985573366 424979392 735370210 276855373 510359362 70185404 736595929 440690703 995649295 133095867 957093476 470473146 748339756 311509269 632442184 435113490 638943288 384833797 901771730 593241598 879205074 345098273 591907362 743004093 818596735 922305957 998536964 214805173 824553551 861427088 908404950 837603571 894050627 30624917 359324521 338207556 532040492 578089111 686688035 284235170 728361442 950428622 982946950 733844069 964661731 328279944 512248230 99661350 177448997 983218563 988052472 230949436 903387717 808571358 917952270 838956286 947153144 685666312 989673082 330627412 459712829 528576216 721279388 648674355 945382611 176568156 559856519 215615895 967473697 159151366 931654950 377617307 910361304 375282752 847135303 686681599 804718774 837640913 993226261 714000686 948537781 194425120 279198939 83957692 656845366 762095080 860926226 542350260 646610657 193536877 243223727 632004892 940969131 705376421 765539156 501692631 980688679 292166107 379200254 555629675 952016820 362339528 859758313 385524837 957323575 891665588 993107100 982997909 985814199 286986035 662969087 987721928 996626252 828360441 980805583 503279819 724869706 316558767 560949780 697800896 993524413 93650787 378666532 639548161 819959151 54971720 133468569 76864950 157581298 728880200 831150424 862931192 950461981 440271872 542149490 650562998 682402675 660331667 803449714 977022749 992845059 992616795 993694509 660201129 952910387 222404109 660268313 378956734 765627302 91721058 113473487 956218188 998588858 486133741 829560715 370285534 841840570 313735050 398104835 381802508 773319064 668026166 769216870 957923518 959881290 545942265 961991117 972876431 975339683 191984317 332959784 228299426 299800510 90045005 626926442 748740747 787630038 690119424 991956562 79198553 332293883 101147362 180599506 474856282 718115239 45633327 901900825 603999517 658438070 164203522 865694230 461424202 937420401 942465423 946198175 511983142 936131985 991699238 995226034 648705411 766063088 607256162 654404470 29942337 372326572 321981728 938954084 981495804 989653846 552909247 693157337 536094288 785043899 17056187 508384989 651045365 870574902 207437446 516471301 834099772 871497014 199103534 555734075 391603836 904052594 532002637 747703265 160483816 438852244 266194426 436027155 32526220 121838203 400243113 538034840 578061886 808455760 31826607 153435805 36805942 930793536 677708277 714176128 968933559 997183107 982594033 990358751 983174798 989193454 164011630 871964556 364171214 803070725 84890422 525022303 914327189 957518905 794836530 955944225 439955937 796780003 621929301 780085803 615763334 927540129 607567210 882947721 651952340 986232668 405443338 825821859 28127051 815530204 793520865 912355342 819711578 900971315 756803424 922542217 169504606 769146662 889733083 992393020 668117454 819150831 356132930 631583631 787680215 949965052 891749846 929684616 453422917 868043043 355109425 803911233 194652357 711110908 419986505 432965419 269624166 933886784 808714187 837228723 913520704 966733920 786297404 941480967 886662772 969149664 961395007 997033102 649067284 938581339 409970036 740389296 512511489 804908035 385293211 943712201 439891187 484480626 167963843 552307140 699447802 806276457 73052461 583996815