3625
776309319 114693360 779954688 431231323 17479886 808399255 177007314 285766059 279349118 920822288 926713596 989010116 225060191 243758417 58911224 728035684 870035425 66897269 953243843 250695565 148571150 457255358 913045688 326014213 349047733 311190445 363605374 436437825 823098643 527187916 587029800 971429886 882243660 834242231 199699760 269431780 244298408 250175864 748718702 125174047 123726674 688722281 117555163 60081807 325254477 336530928 6245038 981972089 784450645 704956161 201522181 190191916 676420029 777566062 517401573 83579827 191079060 330011215 814293751 915811306 915138001 842913501 337338814 381887832 568461124 654082913 86174440 703379474 68359860 789216347 54620110 164485634 943276196 598793046 101444613 865064373 155420699 761775259 459805392 84126899 192953890 741684770 611539875 360239851 93146124 811813484 171139709 579483868 904882593 782487933 647467095 752782373 120839116 588236044 418665959 119608979 323210331 579954779 389348277 589604908 449391394 63226324 468575041 554949093 301766097 861402170 484770584 225650236 939198813 974190378 727803684 614530969 603493470 373009480 537099665 544361977 895327980 179138468 794732300 436376149 655862784 618148401 943039193 768087103 562712994 60396858 791908620 213370614 943539127 796863971 716532791 48478994 786827964 225217398 504913254 757656752 986679822 272330390 250701555 177138350 925650600 196248868 393904529 956051924 989942456 338574645 567987464 67693023 775844538 926473807 939975866 263858894 163633179 64890909 964118545 966330542 985500021 440953140 62002508 290713933 751082885 758869804 151513090 449885138 98342473 47035995 132978412 509043232 682267733 775864228 502931682 648566586 371323660 815560834 91628880 725415474 927733397 854804279 774793467 925278572 186709846 338304443 727839177 150786510 524834298 325119347 137653954 412833400 431944016 552044167 463617739 372642984 844369785 267517193 683281889 302744492 944913594 556213549 745447668 21270186 868643692 90024884 680840098 727836776 466802999 584530500 325650096 588104689 22211360 126329332 554473298 775558965 890279986 703608571 99815154 580134382 701489875 30667699 342401003 52615585 436496220 152092029 605277804 473801504 521299420 190579814 377136694 507894267 501521460 128700808 811494337 13261492 20058772 117164248 595728971 323054244 151020810 271182911 340796424 727094266 580250108 372015112 221525326 780928540 452530106 891510214 908407265 958786362 750692315 633333642 219757082 897317348 132291453 164562373 299317833 564141063 117731192 48016177 134582978 536744507 133776918 45117040 80568676 221860681 711421126 458929311 541440655 783029752 988138630 478921518 490878457 786862728 864037584 337245317 877353783 416369938 460693478 770841130 427507542 33991440 182671097 577504292 816462891 273761013 569230382 853235729 353238351 629234656 304118062 338512209 107563679 951912947 455618506 734409057 669129375 551959808 766391399 566119664 647962601 538310562 185170238 377491656 895840853 751171383 331694973 894178517 855082424 672846815 102890164 835183014 839931176 704930841 854416803 624463461 524009169 949577577 535466166 1993700 363776780 194140882 546543989 828388177 540446093 490704714 651161265 523989473 486713483 498289338 695503219 51805623 902789425 983795482 550764364 73887841 112889993 750030499 415035848 288967966 899261431 668013452 744694418 340794849 163980961 565007886 197989800 609021578 88341017 25097797 448399551 195836670 497765499 305828746 249343909 570361889 165608370 709572863 244350873 171582972 713923174 474825685 978249906 57338710 832544071 387695681 132969931 389613650 867452490 391956520 192890652 922950849 134896457 785661718 174012112 800868647 392518804 274676748 927977964 960273232 838546945 571702291 345338808 422822553 104065996 964429051 480256339 141100557 370096465 808684813 825564004 956777880 947623073 810799626 464258496 212356733 484109169 787147825 473747836 276133148 129762684 829479067 718241740 777835413 697241652 376753663 241625337 449652785 476263675 807043901 370303748 456283662 109708713 233980512 736266008 994269320 84933329 696037294 294220566 434172175 217703137 634038771 390507308 445825552 61859732 949066964 267131639 346074045 529204490 878359321 923718192 691923516 503623619 886385750 778528244 272995978 619412777 551563536 858920194 834105289 908594857 594765853 679277437 245826885 263503259 822369120 332780620 270826515 748087219 33722084 487684200 60176439 913290690 685813000 107901104 359676596 217860111 10592798 442204991 300116461 851337805 935332361 346609384 102625179 371768115 326542645 431204268 628193002 670670178 727812689 786893048 386601289 750602976 887863402 235133025 965664848 837869038 259116990 2397580 959751092 691206509 691425854 755928997 258369426 126278424 740220219 934639106 615209464 153454853 718492075 854681149 348300370 730284368 741040569 141986516 259512690 940614221 832331751 115217938 391074073 709200454 775254214 195218802 30235687 349878082 283867774 280269477 297104353 450482238 545771849 701455597 483070332 54281868 941541126 65141078 238454366 321751376 948775854 585163309 638507838 895354822 597122518 851050645 731001776 61864611 903479867 893367122 566645012 975847299 566887969 281314800 729543966 485287169 928118934 18499582 917139409 391006694 925942988 415582819 956573315 91295862 33321350 223481277 378922950 946973964 457901357 445823272 25989262 546406630 213826594 400392485 329739498 948229704 110636721 351604621 921259359 575495305 171707738 303356603 735487996 82857728 358658315 688199165 498859335 628379244 606487286 856212026 679703082 541006384 767869121 340670262 303863146 187865305 673227136 169974478 167787344 26343603 974638271 454478861 582811196 785979542 383980407 703567894 862100241 432451580 900521540 787698466 995697260 49700242 923586969 605114767 399668237 58342732 977892180 272783636 221106169 759126232 393923777 410847745 66448334 921671792 209110496 653298222 906589349 352922504 335757318 162724288 297430926 507469709 976331818 79489188 137065520 855972830 168300629 783341507 177466537 938063986 920189046 978177436 333790213 969371756 767343237 899745848 784073901 98880387 443067503 752185338 237793710 339637265 851121937 12574294 252586450 20505917 597669301 38296311 6113650 184324074 943191876 655003584 806203942 693941801 208348680 655263726 938796566 447741129 738172936 335461348 457451550 928362491 947299554 194834073 190281380 445905525 450574724 836556683 232892425 937457019 753883187 269247500 685687485 317011272 266920340 256219398 154344253 399231950 558748910 860011159 730642639 255323643 381709112 683617840 270679017 527183928 481664042 763038295 794852221 303291351 983575715 785389532 745982511 452711074 970643839 33782265 630446009 278314910 928882177 389154501 275559857 662092732 716518864 954090853 240506673 61225340 922122823 297231785 614210808 18560316 801220807 430208472 851202836 749458703 856727439 661031799 555606512 965029372 158959632 288163231 654116027 940915152 797260909 421503305 949754591 765902698 999963453 428349079 800005561 221410718 517220284 246960668 583873989 588317601 495139899 872144865 513596681 524136205 461396141 80291804 187079905 216967844 350844195 888451684 533927457 620068080 464941780 466323054 72786889 162405728 998467694 200479552 813310557 682510688 798988068 160881219 973002587 543044227 893629632 353600454 852651391 228537459 106957793 179177063 300039466 356919943 449090757 770301630 638582567 174874156 797890793 819068861 22530993 584619502 53937394 892897015 785235221 502510493 781798908 704073314 304727871 590007125 530000942 956702776 740852759 247077929 448918121 350745443 706215082 857244037 467588002 827527820 669123599 506558273 49394936 329381679 534646792 393318943 310236896 373769661 836491792 198641486 485194947 198924277 280402881 55059191 790853899 670918031 763492674 630238872 171301350 635405350 162719007 319336766 142891964 771985181 728430290 285393348 749974049 14204806 840093200 856305348 729939391 597356669 310121240 583390924 470526604 40384919 9278720 385974241 173999417 917121794 992215365 632823027 148279444 858605686 853980537 399633446 560372789 460621190 189900218 263830315 468176963 600052763 688052000 487446012 773418257 545164183 116152596 532224215 342069992 329248678 353649988 895952239 864545850 119569348 362278460 547346500 724549017 888048645 205451362 577732874 41397316 250643024 720888117 983268008 765902033 237491893 496942197 41679913 929388824 827354723 463226230 718866849 215549864 993269257 898915194 104014500 788686702 738694248 923177536 443996434 6850994 613325897 197865213 729131060 955843796 3164320 915856784 13483614 682080991 381131675 372816657 774628415 361464640 326171418 335680844 793226654 32881880 424027412 577093864 20575480 662389358 539456249 124987895 549428953 427531443 541350443 789209366 135690701 436731283 739129392 882633226 364064653 326236818 242733739 132737641 116381049 465093450 388827253 162881829 706402829 970190367 314286245 637140032 805987479 451021082 102250495 312994313 725673005 792077871 802533544 251408065 925574701 31446294 213924229 222354711 85594513 107515949 507676312 232885569 147459867 184790729 853462859 130461726 72554007 904330146 51510188 794407443 514717962 843710852 19447992 597888449 339286047 467283831 21911061 853713875 160228790 710804188 552862993 551111253 347496620 541708242 855083343 922912449 987631268 828914285 277124079 767908968 511011663 264314846 501630541 353779725 604489950 885395837 106925494 426446568 49182351 131183726 313388844 492859069 941690557 864701718 7196801 570909100 213140362 492262327 797427114 29143342 79733612 997271103 123115060 965462351 69309234 153383257 403304748 391459547 967790938 326451908 84034584 218338006 851399942 586852617 582776977 308533445 747126790 19460431 697071104 630763938 610547297 659013919 75854225 664156928 719490003 998542438 164385753 896049024 166713783 673262322 248159975 234640373 99935140 759788483 989020261 891053433 674274391 352657082 622336493 431442903 775798200 407393080 688677793 505429657 317135973 753771933 82804832 323127002 511228412 640553236 178500445 522896971 947512120 442819285 697228382 308683609 519101438 522857819 220729359 830494675 736507559 484311062 41508356 345910457 647876830 653649873 506788976 841804037 97091397 686556066 746922116 689918038 619408744 20705 176919685 565886071 62312587 75455552 18884569 3672181 304329112 723366841 418220030 883753301 981687180 343497364 149196151 955150943 975076333 699718614 141606866 769810197 372509210 233556750 997599052 860322346 608800833 329455453 384993724 461459603 73258811 642983190 784228519 311236019 342554813 70591236 274013063 622469585 696287363 931742481 57709128 329381651 75653878 921067598 772173148 478481562 560541571 212018179 599330509 783070005 159432566 651449668 864683073 436280327 837999242 782045643 357988013 160222345 58396214 480917852 659936341 899525052 926578957 61819520 772823419 617724129 273491278 800922176 44241038 186682926 288319324 971949965 535675053 854691154 416556805 902432707 922941710 760150791 719891357 676391529 549561766 579089424 855073610 724193038 648369204 848051793 83046729 169333611 921875308 271042974 106182619 889507619 737007654 301653388 672296396 410100408 59202259 368870859 185210349 162164044 694085678 95180388 569906253 172948265 627030381 601790197 615861780 687942326 749297841 973377124 77545666 261976171 816428791 356949249 84301891 627274073 913242735 622766229 82273231 657508033 863408119 110148099 291299655 607046043 356254538 610717410 96992155 276390926 730253801 298750946 212480066 426117950 943688504 588536079 398942567 955218990 634574921 895248674 211707656 510651185 593484839 17912563 833264294 275116008 176902202 890757433 702577884 384861383 462266771 306432648 824866866 153324757 647606120 252693690 646397097 61462094 580554110 391157323 617235183 762722866 477761970 506369876 776368162 349430141 103717311 333993800 182786397 779773222 139908448 926210654 677474999 509981474 989011803 248505669 724747097 364269929 149259765 299622633 958983372 842698303 784406785 581747674 222979461 466256696 346106379 976534488 588851602 916449657 122530253 733968605 116960093 502162027 637621338 955382192 672986575 877388318 832403802 885226612 521386185 309288071 667496484 927239658 810360150 541441278 859472977 838705072 801576557 146974818 779410126 557085945 772857211 19209939 25813699 607449598 657180931 35213291 629351506 413932853 199308828 881613857 146782070 446399953 603035928 873231117 360525113 975861916 123571663 293593379 867127594 813366825 32939263 817246478 549349837 95119957 1988911 623421576 139916106 359691120 747049468 299205621 906369185 757904419 340151430 599077806 77392438 449377556 415199578 724844678 892277861 364738001 876550753 110770017 141622381 19017432 171286946 896405517 716145966 241097630 343054130 562743055 854342661 548885773 955412936 485191244 556135250 125510401 690868318 232847548 904687051 411287060 802982817 557718305 920060731 618712665 515718248 207583698 462504561 918713982 601164383 260375980 8730390 499596609 591575121 544634676 369496966 659548253 837437922 375665332 617360911 393475947 658219093 126965585 96294507 416092589 778979125 657110023 463964911 310698370 549713823 550701949 206153807 293361329 360811512 660665664 373178516 776620667 239898099 749490600 915651997 659341383 821524455 982081770 463913711 844228901 165314350 785558741 800936452 501805809 189015563 809977674 884751680 344411134 200885886 983086931 735763818 781231207 667786903 787170510 165638851 569475736 572030923 869375575 418224938 972774850 892567182 20319789 874248114 760926400 520628194 356973630 317397076 702485907 503811943 47340511 896115191 10901592 619118280 209739865 238547277 103063977 884523772 632499381 412886367 514669047 483427014 279614647 451253413 958161831 622672163 55581478 291511477 745355032 400064314 465800779 779408888 177002674 535203532 987745204 147492384 673421689 853094292 585857897 699855164 830155630 269945363 660363099 136216640 783639987 594208602 545081064 647464130 824787088 193800629 355055689 70224302 733375837 860507795 343427541 676232946 315947244 496483386 440861307 350824482 349563291 10147452 494913611 122087362 620113049 371144397 637514665 392252078 488013515 928698088 310506523 93676004 425604920 881887910 897015160 896089023 355014466 846497477 376961408 933779630 979859771 202618492 784109180 448363910 434599360 776930833 865651751 638308387 178979100 528002909 308291128 510408691 761841756 153132510 463686340 911869853 286760858 358884580 294904041 208433702 675236108 214988522 20979399 83925265 721187602 102347762 261536821 459841231 982050211 524395940 247728526 764554874 366362079 986167152 222304398 226923983 568137103 680329238 819536832 824464141 114783679 736075704 48021137 776405606 21295668 992334775 839808314 284695537 359366480 141028154 855250602 34002311 537631957 297788926 608071735 248272313 277944861 690928279 51527901 436864891 263557977 536959626 989777887 114918978 295732354 475611742 603761241 581860422 613038959 136827336 391680705 555259016 635595851 677252741 21494077 563481942 67124067 245293056 982312073 937094774 951930903 749047425 838703738 795632941 284618227 391594901 493999671 443752239 731102354 777256826 177080779 74358017 56934871 149656879 666395079 719759398 334502556 698868397 530744664 445120244 922973372 142672584 921679619 309451707 48448571 495357474 125517124 289419464 109732778 194862655 694240549 360591612 429712657 753085126 317025266 754143597 151921103 718326123 648825996 707562018 985563439 604421118 599987050 557486627 138219562 123483967 775595650 883628455 116971666 642543806 518643006 703828423 750844887 175550055 290576134 716624692 745206849 313032109 654286460 392829049 439717939 860136415 42220734 286262255 547510360 366461248 821381387 213878102 625610889 701805308 471467135 483811975 70761371 560585789 473745230 163720976 407333259 884604999 320195546 811744607 140808838 124684031 604734201 936483078 379583899 325522028 661779030 573899324 49822011 346269780 324710845 384132856 606205547 298982508 495509338 752122405 669797514 876596057 664306344 230880207 260924407 204457756 903664080 651567629 751748252 182355133 170835869 944717705 863660354 77131244 67897434 457909304 300311133 339811524 700354052 455470630 582359648 941375304 94439771 718079280 135780264 125008781 238754720 565679267 581881913 84737251 817696755 695993254 598838690 173827482 305092505 285740179 675085514 421086920 994978814 764172354 879479652 434610064 3646878 764567449 727823639 743186561 327757352 653847070 347159997 883883566 378941226 56515590 259122365 494534064 929552905 782864736 747622800 766353749 750573537 460956249 784952657 212234868 480827669 527754891 687549997 346069135 678152313 689737245 893587899 662049919 396641741 256203891 431843958 66216289 609213643 219231317 119069256 939138407 395920442 221882329 798731641 757292382 253041113 444382651 298919111 240581085 385979052 680280837 45896551 231152010 417729180 494364212 239535416 463021821 668251435 91119550 109928518 729589764 687708677 575857694 993565703 41342006 571403769 73900815 250145116 514943034 865517718 181780881 811297120 308190207 100112826 82893 754392487 425907917 566024941 926549965 802170389 704595050 525361493 387751684 946163567 75784496 57366651 465611685 729096231 123342894 48711542 658937231 610920809 890367440 232683149 492477525 7195984 490703399 862383957 96179634 789940266 324916906 844531642 851321272 823400055 994066121 51892915 291329095 897099318 463741138 416982529 273417468 824122664 442960992 292132063 668883978 489377175 905518282 666933346 888538915 725626098 450305598 655153775 177398354 629356504 779926231 529870002 753626326 338911318 9724546 973221008 456841631 402796212 190218421 712296845 133610687 541455986 694713577 103167838 455650304 416540792 768777278 133545996 55352029 193921696 860418060 604505674 317554772 436789939 688147182 863148587 781946146 727883797 336779748 527010889 237731248 102954307 758360650 618203988 653790202 533120625 991336310 340576349 492449086 915662866 827409180 333922167 645962580 441507738 47894782 603478566 589427172 721736311 803356650 405352158 684451433 782714633 30761696 772744272 734178317 694925319 877336518 948060171 967830293 171138065 777550868 614339336 794315466 826452834 666261611 569092074 663657837 810122955 307071490 532846470 313236176 724539355 317227411 765937035 738811542 105141952 13933845 292742734 805393618 143174138 900777280 366114454 66053640 430851580 372233362 107255444 681133185 122879522 237593599 258937012 7646262 742575992 295255468 333487970 82099785 89846031 94013823 290871213 599768659 127798613 434116304 85099470 521569666 554915328 852713140 348790137 1300228 834026683 702072563 682028225 447237171 233835094 235901752 525379021 368686692 6436808 302017663 180749564 894464934 404918150 787485120 832340827 759146774 991466495 301173372 693551948 833897748 376740259 158436609 792546372 895346048 172202325 565457861 605360341 678159933 755581416 321017775 229648236 657365284 445566106 232130436 919901360 956768908 719088407 462187726 403909452 438766615 224274918 588170868 546869567 399737496 475867217 473630174 897755542 23844506 814870360 896840271 80695216 713184221 440583435 934292733 818135771 413070114 273143944 2890725 604422289 468041765 543851118 440026455 135001032 638828024 445582879 14807379 461907444 297174669 153594222 549572174 843660033 186307593 889057448 135273202 850763424 314022544 8308342 508971803 597888050 630020031 803151303 151647554 265858199 358543722 902545696 401296732 615505427 456235643 351919975 239134507 78496331 992123679 956990814 533141820 338500674 316215235 272464355 935241485 223040125 399479533 415885933 863435527 695785208 719711331 838296714 815117757 647821908 494756029 908424149 142833619 488963106 465152408 979430401 891542932 119925670 90951574 84275688 128164270 960705063 77519874 877476085 944019320 80513510 50937425 240678507 598060378 342043503 984615054 789823241 602814098 70382742 144975597 514452736 994642630 696021821 447818115 212544468 484000418 238601359 566691316 804821664 641581171 675002312 177895764 684638242 447431491 316927234 652284157 80923775 230607371 662274319 503603297 809309101 603766300 304285434 809738525 162910081 11127660 500155317 895399541 892032904 294385348 237260675 18884723 864146372 673564628 792076078 251598635 577057653 575778642 241602260 627484704 550249863 658219288 357439282 611745097 569228807 146251599 193511936 482008007 131866913 839932118 356189018 769504070 849557521 63768685 605218249 292780889 990227402 367985849 331157675 856915072 502512535 706822772 692408406 306189537 265231032 792502375 17259682 636415465 525897513 533770018 60650538 474963133 726499336 134968393 245011701 256514114 673075903 538470612 385592786 595392614 277604912 163473201 647345207 96622481 80642537 707093558 916117532 120432291 816928110 800794517 695752578 512012431 317291852 954716531 650249818 861648820 41655703 610434276 446458865 375009323 323631461 398322086 241189384 214498554 285640839 556633060 187398093 248796105 421344271 588809858 413825399 306252481 600395274 246261119 632608857 975712203 259991622 857267303 155186997 418723981 125054543 248462146 732893010 102485835 775916943 619031226 484961006 417011245 66742838 331589655 657654489 417233214 509585611 763124200 810313557 867461938 897629616 123433052 962568482 973318876 405547747 751055372 762509052 888789040 865897183 458149411 82059733 285087603 976889593 348913228 801535320 733148210 960986530 747430681 606339507 317060159 440911037 205497043 833798422 924300720 217566163 782810685 212936460 720240371 193100957 351156937 515618750 532745372 987358479 922472556 803013206 262133505 356901451 850734760 679648513 460149701 98679982 966184148 734814967 951535833 366984022 400800519 598865922 655409902 351235276 811190566 893396096 209003709 970204746 105407279 495427457 316154316 633550258 391568354 973388736 216935341 751930348 212880061 199348175 68201147 744698326 268869437 483669401 530407903 670113857 261557892 746149706 763163271 29529351 993904848 574683147 117189628 381517521 514602390 65159799 119589743 304472907 686509184 271133578 513888510 952577045 878121749 778221717 997577011 28562065 877638035 796924668 603328180 627203712 795245226 932829456 660791412 134832119 864135379 269944795 228410952 213092184 354989784 290791534 75686035 601634416 224376770 321416708 512904024 958848332 947506816 501157794 324873293 248994300 310869185 621007545 831841819 950701397 615437836 752390049 676729842 99322326 4982734 217640059 910679893 655212982 880049434 744066575 385157077 480601898 828830849 221821168 160867916 364025767 639716371 92999266 154803739 750678466 755966377 3958793 47657351 941779828 967277928 351210920 126374783 955260618 445711706 477937222 487797399 632488420 230949123 770440104 237892089 428810741 151021300 628904958 199811068 183940686 897161502 773229332 318087220 167767290 961115904 473091698 710078167 888126937 907026482 197536982 472776405 7049314 939224826 53070605 171542135 8722824 952584120 458371184 786559350 461172166 469564081 815931834 694194412 737014661 594799187 567858468 988360861 890172978 944067485 167817641 903716233 708226308 292250930 910440707 348685037 532373573 738735894 535829253 284068466 889810744 192623475 546717407 638830278 437386600 417521666 873488689 971687377 110323762 739879989 791380012 417651221 56505633 4402992 268763099 741462868 66714452 496836889 345871415 740377336 618189072 792589992 825071602 986350874 802314825 394059598 514562888 470868427 374239821 382646389 439660701 252707074 82552923 459638324 261143411 809304683 125908096 364245751 637547787 11548335 45067260 740278824 529014382 639431395 765870872 259235766 171572553 43704634 716435053 231694761 705636915 826803408 678842245 249407711 197412223 163964595 247822039 26436512 220635411 333000955 451685496 340278843 91805490 693818082 218629751 179941784 646047046 258760847 715032724 758080323 288050932 311931494 109241172 264987735 38890127 743297143 156112303 36477399 221974575 372514129 830238658 840702614 879573459 740073614 69079332 764997465 81549020 403865057 938914437 768424490 403687881 767742725 332301016 928910541 192265431 315275433 242978089 298747432 823310798 248283466 634234329 980580814 582235015 981097664 116305261 218974214 903995511 830283890 530774483 531855060 786961588 799458419 821727784 299523411 630348465 85409929 588846978 311775042 449727459 296866271 598668261 554629205 552854235 327259133 714702005 963621277 128895759 752052632 480418853 996615943 437198098 399147741 224003788 781692164 944680005 236403340 94998975 312314200 777760440 122336644 123326881 529414890 259992021 451104693 747306817 373361345 279457344 43659700 242404231 849044375 413113962 96471269 981512225 862908745 107426424 576663026 857570326 526184943 784573018 659422096 372888256 604370127 20733118 419028970 403107812 570936148 706090939 266831542 692291541 959151323 711649288 553351900 362544390 215283795 51734708 522545488 900003054 304793176 98124169 369173913 561691277 66386483 182701926 784419660 954605349 486243100 24635299 944573016 174603571 482372124 805689915 448249202 782871274 142580725 935858698 613749807 557712485 880641414 255009719 378147147 366046147 97204549 325766347 273517881 883632186 138080621 820620903 709946861 902911506 162562182 810828483 434875926 830928937 795110782 926616396 872381737 577080412 361575623 180214686 301941442 464620153 574724725 701125805 372031822 357273304 81846525 380901001 860887498 231684316 684023314 735324454 698926887 306611674 441763469 312261297 252961995 727384807 182009166 93029832 32146975 552780261 904625726 438309692 812986246 485389454 320855348 498329387 463132081 989880613 577442593 559281959 484003056 451512608 103608395 430966796 244059502 84685053 787501494 815772799 847412622 975783913 795735217 810822268 33455778 118004306 298801507 978455782 755031405 60226393 64972940 869915874 601622089 652376457 252107506 62764720 973373930 573573117 667889507 186165533 202930597 278953857 115255321 478804282 311637456 790252188 301221984 131707864 19542668 399862027 23142615 212234621 871389365 256307550 180300705 882419869 468632866 655194797 684596262 965339367 409644960 955118080 557434792 576361997 274611918 857293529 828879675 689439856 71954268 669181549 568057625 161165954 639841428 454084380 696165261 131813504 532032141 794573660 213895367 991962382 12419984 59548697 64566765 396127874 434437434 345161082 182244601 527179952 471829632 708751273 769204713 587360953 644545286 417138436 171140740 850412193 815047879 772015151 149436084 538929089 503009469 975995692 861179228 892267187 87729661 274282554 887191424 71388347 989748596 95297322 198566856 9354862 832694655 283835140 145113760 601433365 979716220 175925765 316956464 830226763 180044873 541293060 191497248 431934001 514387126 617926704 765155566 413056430 676689028 288150905 840485006 343625813 889763935 39763315 667189810 411578417 197984433 772120912 691290555 241679195 77400188 438662762 61121179 392315793 875769499 99376386 839146715 819535934 391141348 277465944 274154337 254580852 148343291 76362436 687274305 673487896 617087756 517064962 177934650 716918978 623471320 289918343 784123601 539980445 478153863 885189308 275586501 825809523 171523600 630850632 628730578 170132265 779494356 911841342 807080061 52038629 738906295 593848378 144056442 494520807 643862397 293742881 862334567 933403415 648803724 498849029 433082786 211276344 988379212 837192367 649281458 417261859 102737346 14182223 289234041 606288600 977252463 862571966 320208063 368441179 356866210 949370773 542112488 928707465 674208308 879288406 943498764 842467716 752024271 412390064 544474703 381664919 456381907 763024771 344046663 166284590 783880872 152310404 139636697 921069111 667998189 788063713 665195081 652900058 965348168 678799857 842647588 160190272 597233901 69832889 24173972 925115323 805939606 117957272 120096755 72716170 293553048 355750965 693939826 563536784 994197932 451008985 702505359 107708674 881270280 883837934 946925053 117239404 406312335 677597853 830390028 42945939 273395727 496126511 719575882 900473925 532060318 490877440 301931704 276235645 552098698 19299834 216569678 113041540 936449430 71308580 996202951 92660880 979768551 32155674 891377734 788379060 529939723 585585702 903213240 932245105 743041304 336553391 786153421 70902087 977958064 636326996 275786856 472090142 598121144 822688462 106054413 281224206 255079377 373647412 579055234 849543990 423961241 60972240 11441256 465285685 204531042 784877268 226706832 581019137 386883742 755545065 278253867 901141584 642552747 520844593 896969232 404466475 340880844 976516849 101333594 267908811 239548523 163654042 201782368 155052807 240337522 526327379 830714363 726554154 728434115 192402451 386051367 290252717 329456667 250439648 579435377 323034050 549188793 487846336 391119212 949249629 487119972 22668641 162462394 700861373 255908653 210386012 485860242 477464737 292670411 598251970 580189279 610332987 474570612 242364181 754813535 782507688 915067016 440692148 812881214 349085236 913219036 378033199 55167675 791200925 196638677 854945983 356380736 147349133 234915547 51157498 628336981 51922729 194087679 812199563 801331079 734069434 117458768 351352753 330295211 433636459 386173057 90002692 969733174 366254360 512156700 960726388 269837449 202743439 501463633 89459193 287456662 519594712 756701369 393945861 67219968 303881433 937440216 866760660 200298932 969778768 399616733 242186422 796153982 226743848 558295643 653711352 260013714 268607057 901796031 117321883 818560195 460149761 792179279 848678475 311841788 515008305 642410377 911762133 707437076 188564633 119677988 865715181 864580072 9639237 555131967 574746834 112118195 876339267 703039288 470107653 399422564 968161320 422839023 183397204 971029865 670316658 784641860 308474271 709923220 19386681 476070464 597257468 58077276 652659186 791551264 597905738 71193954 134963970 964279112 785822899 919850787 685047101 906479957 683319173 894186245 947171674 22209263 696733773 546465832 258656057 60173825 507688938 552752657 20525377 602782002 127904692 70855393 649312731 395237615 399143374 490440157 152929855 850374593 975382181 693135890 212031113 856593062 726215388 919757161 326510732 44286242 684166167 33026884 299680880 885593309 767957096 418402333 831875887 974866263 204564357 573968364 962134814 129215295 876010392 55683195 637909186 436465388 978532318 688660678 76894101 818006475 186815760 197303907 330395366 915593922 619931576 150001739 436349889 69936348 487367527 173702376 588862222 852126957 133070113 4553903 29520211 7933626 117297020 386654081 804655852 731094469 897871126 820017157 70200453 952142686 122097314 491656548 440829925 348882485 289867107 101816840 48098431 222612595 75237937 435879929 946244134 190555419 810723087 748433483 701508689 457304195 612234721 993812269 218499333 515651392 877891168 604912233 149795462 763563216 162799131 676999432 297175235 360279952 726132519 124869083 312124122 322286449 97518371 749872173 451923413 529757513 367222083 213423980 629921971 100117050 258014446 382058365 504373342 286119498 661979476 592604421 958358780 833030216 307962629 701086828 339809094 351197929 196867475 101699593 610487561 936159071 894222571 128037537 523991964 11957497 978387419 681765959 344396139 542144238 987288417 389433831 751370618 84828709 268473122 503286457 76818520 182318293 378763394 996478912 558993672 436323845 291051979 888019037 923816411 585984562 761398912 826082085 500713731 280560924 727941979 800226559 752357325 12280542 980039001 424828453 537174720 670347287 906048455 115737234 968097559 324883165 58738658 882272311 852141728 356211040 535415892 789902223 474128496 779903421 463949429 462618099 771458513 393834501 773184681 639336758 241370403 648413322 216030398 724360832 792994432 506639045 671187620 981275402 327606683 556232857 702194631 881866357 802501518 764416599 451820422 985048615 379403543 21581050 934674218 578022052 883193817 678454989 822843744 565788834 578872914 927580187 81102092 872016264 713798441 304890512 342746246 552180973 220460501 14825281 175624584 569620559 257714968 920111765 422423761 579916746 811390135 887230779 1366705 489462048 251399274 423656518 700296246 532281450 143296119 702673129 830126124 888896538 616064394 809466778 19004981 1123586 518655911 815654938 871826129 613433251 204681651 631992593 582345020 575906602 531091999 193090907 467609670 193272938 156227280 338440154 676366545 82012314 283157381 561137433 171193474 228149187 752772512 321212146 971344163 909169865 834303941 207655581 244415231 591668679 955698733 302493251 906529249 649278527 50757771 79356992 705089492 412121376 59270323 952926786 2865686 681834441 577709879 331055717 109897499 458065373 160966181 403587601 23676525 80513473 299185826 294160167 997803618 165351554 359548979 975978897 949679921 885252519 444723556 730782285 969196717 48320876 209796232 535958567 920711860 194796758 31557001 638182693 910620325 110466338 781047267 215331891 715977760 128243221 865543999 849834664 697881291 272363898 649012977 873799341 117807030 683665029 882575923 778682747 679075168 473590822 30733220 826213829 28382726 658243878 205634831 681736088 374396531 959266996 708695082 501798437 159042730 933438049 847050431 469444665 666850287 81666832 617784083 805945366 110745340 311090037 471906594 817493913 24362437 528742085 532392946 959853163 631366407 493625540 28976751 16407717 193077896 935133786 645360210 601669211 136971485 536316869 544828485 37534320 551914180 914890713 751386406 724002346 75750047 845810676 754615591 291464334 469583470 674342311 267934467 945534900 76854611 376280193 905749991 601962701 411803088 383280271 954153147 629192490 537439962 518912293 429930572 762392508 441670687 443469788 41098685 848499960 93962012 287644621 597134864 768894986 728389514 692543307 49323552 485520877 540031927 158666685 391391383 487502959 948111384 233715789 463400563 591073416 513322423 203889594 569603865 585078990 687803246 352078191 325747108 627514381 87254284 495161580 83907360 168043417 263075052 654816116 508954005 437877314 931535882 2277589 459989057 128444946 824553281 658861664 34088919 541090624 780478004 115964687 880124815 100951619 873699422 118601394 366537240 464303715 701549895 770471912 685300793 499340936 979037273 499402392 192096836 178007994 65594675 506800905 60779241 590583677 751045867 511733030 397729213 934448829 230654304 365855535 691912896 731098922 747901819 377805959 522037520 124919256 607968982 405832823 103191271 116519021 284141239 668344288 188577329 442852043 155144256 134299241 82542004 72756961 702584568 620634594 664913247 715292043 407494197 567209494 189704627 807526706 291707549 12416104 160281085 50146018 556419931 724516833 11725191 632684319 564785196 289720470 724604735 391445830 435702758 369862192 75276322 233191689 754478078 531905224 480275180 597199036 270128257 77556139 107015527 131098046 533609420 949722557 826120587 579177782 567098896 406322309 298404880 575943214 535696615 313201958 299472158 964223375 801153789 257279194 586402816 984869909 568205247 473602187 828785934 738403014 592498295 155466167 969072929 202907237 123978984 637294370 322992933 53059860 665989247 939976591 807823955 518020833 854297522 904770960 535229758 121688845 923443874 593890618 129164816 692069688 230513732 686113313 666753788 667842900 945740364 892587361 328584971 481081960 207997583 55416062 79255629 553687929 566472620 165240701 305839599 108385766 406463081 249022361 557437182 634202471 936851475 219318651 422668542 18047206 733160558 246393516 450868676 627762356 75283323 289775007 6176931 876090448