4330 471
242128231 819027759 597084993 188054638 777917577 903213649 512426548 414146688 730875787 808798563 459704834 499180338 90977310 707358964 760798182 92406171 329499977 985660982 228377096 253241450 53501689 810448203 119264130 241625871 10130008 646856894 558257268 457588587 229685630 604191658 460693858 41255446 829224310 168710944 429313259 70881502 970041269 265696976 897196216 477871589 971256535 163096161 793238217 257262450 609020038 463682289 634392147 221066241 772852778 200777288 422526387 554436774 651768907 150820502 293649691 744403485 362969853 107126571 805888083 39384903 924215018 264307909 340995904 183371972 815630847 809460783 26318450 852465277 378195092 309063452 396906985 876450418 104717184 69919976 887928666 956722966 122382212 981800065 950930566 787900695 747142466 152108587 593300102 870989770 958127056 665216417 52939927 750472378 393084482 720669244 996817355 586596724 830099228 137869919 419084679 522348854 556760792 391658365 12493092 824693921 718748666 56571556 168143026 725464063 70962810 898432233 405320676 783461921 142714388 299453360 911079198 886721434 525370490 764211410 540899749 262962387 125231491 289604073 338639929 101298960 274770778 825648551 920639602 316437916 273374026 967820845 551065399 603371016 625979809 631533854 855550865 48341280 955152320 144767075 933179088 804136292 230848463 494438686 118368826 353348786 237253988 901738059 8530391 326868973 178008683 282516775 450143569 87252101 254868590 965400132 630817655 379843385 372429321 953594969 449795054 83022186 535645222 267302695 878102966 31287528 187553695 310124455 750373324 671524624 923741500 14057258 728914255 326138923 871707894 259610350 159177264 759283325 712209173 406367430 816767883 590678041 622109920 676239998 92833805 979568009 553289383 929006495 368439289 745727836 447212208 424595901 869533603 466675752 583128176 135891259 611342095 79221628 559534342 669280454 456172814 510904083 905612613 29821433 868028305 546351154 899524076 708927317 254116521 324856023 508023813 550091074 738052443 993957115 365599018 511277971 295990728 828693219 9680421 473814553 298272551 986618850 316680038 156592927 796753853 306730192 42931438 618346009 759362904 612255105 647843001 198538175 268869323 152545096 226702369 817928939 602123244 251296293 159004102 658601652 394423771 433509713 410643641 629590006 805757647 666431236 998038487 478917067 653155550 565954964 198442369 222130714 462412343 885635412 145743721 665839964 687864102 292128484 144541044 302840177 480979472 184163594 993116181 922715200 320549098 629919911 704362444 254296321 702486571 426602271 237575375 679075744 308061001 611347633 338935616 682043750 666146635 557583711 384684202 159601222 426775004 691929877 313835717 135851115 287329150 352329135 48222718 481249628 472793879 220206647 89400742 147166361 381702625 519028891 177154871 266534738 368830002 878722373 862430346 95801047 414393115 648380328 757080557 794839806 31473323 567742654 858259976 883345742 390374558 521040183 626898181 440440929 539887310 916442068 640848280 479428978 970013489 863042653 611082140 95442252 59040097 729286596 575398892 515623920 431375933 772648549 176698925 895862283 384454043 548140403 18708019 970061652 888976141 814973338 541531509 165988653 323031283 654124454 190900687 822819470 805571680 436935573 936583058 465935985 936766747 194878987 380482653 753544808 375401800 445005063 259097419 27075943 936724592 119194370 901770568 801840152 330148780 138079291 88238511 809193607 349136839 933836804 958267966 910285837 192318843 399820024 241349852 57540631 511581296 533847842 344650913 817845357 373947399 896240299 231552179 714473865 192086561 856889129 739300546 437948416 131946842 10813596 440133762 133682357 926700696 160455484 419250415 533784707 734856469 629888982 350467953 564602913 973815803 422695943 170488102 202174592 635082232 688681626 50954932 56661622 443113907 62918328 941039353 396200099 373568886 128563171 31066699 213689527 746480189 504145909 289102807 942986522 708605856 115313825 257619593 608052215 452725224 681366759 206407429 734478627 343377681 770563885 48176149 160023960 622160460 104529482 61096666 881568244 218609078 76504805 331139739 569568536 111081818 640130145 791348449 280975276 939178379 180684467 389964029 859284982 914846837 493475320 643454489 316047057 794717016 469056361 821538400 57976040 695644983 653005656 289758867 33929529 189604339 390204235 277760474 152753838 711667845 269751443 793210003 916922412 677483382 951148171 613754276 514344276 765216071 762254528 746346212 811792754 670485663 166214091 757443636 21378278 290178652 660500488 781863079 372986485 31910854 477483061 941220521 909666451 948570488 825985727 26143014 360513975 62811038 941306281 570007255 94121523 731338098 598010120 737091383 926333546 451834999 667003344 948242344 144676355 419060516 259857621 444900920 508884057 766649062 656377471 869016857 424145395 673964453 663383592 328170816 465898142 149690215 675833927 724241741 211632373 557035780 409064219 191050884 630776588 165784048 809613912 109682403 982360619 282028827 471493098 960018796 398956721 643319062 652601989 751271709 61942018 530570449 940639260 820561354 164458275 11821173 566052196 82077410 960765733 651200222 738502605 736408073 95396799 960989413 116178310 50600657 517081250 652346701 638465054 486169060 829861798 611432652 965710013 358164060 783593758 410375159 93390690 435409445 609706411 929006166 603276060 383393099 264977993 508866179 980178366 632199420 149198598 559789332 328738946 996381785 358982146 269101935 859659847 876133059 862929056 668374183 436099713 572103457 168882852 713909645 606674512 193169819 856629142 995640475 854855658 371663379 552388651 906210900 104797361 475789319 438614223 964321696 111598896 143447480 341384049 629305545 692791030 843855288 125505352 1000000000 959649491 857014131 186918345 298673310 288690460 479466796 983079739 353287861 775072250 168724823 43887139 586614972 912303418 912696943 440818079 128032700 252714140 841508358 184644808 797957575 672675519 400636035 187251392 428196578 778178223 168405319 125192948 784552526 661406267 971322831 781857391 819973308 340729975 850967931 408387077 578704922 784575892 557632310 665376068 712830389 495708986 613012874 471856080 875563445 855573994 983626033 616366202 549391731 849938068 828654739 824213027 374576863 593710456 146518985 44997721 995673972 690822053 527157712 660160427 97715675 637634433 44647062 720656536 131191115 516919834 39504960 64733218 710035050 251027366 751975924 884974019 118948402 588289281 196088295 67285878 46642155 228956172 723537709 79885306 439929461 415594315 447266098 739293098 854231636 524166309 740362270 473485028 429026295 620658773 331453687 431137685 566758462 658143522 41841470 514907704 1671815 769554615 445323168 967976896 964588090 313150951 488313801 341128951 826759540 450924997 946439444 254181363 559161546 875595464 817390381 879442452 812557006 672269615 766425388 708234593 64804082 284909170 687652772 346300285 357789146 8781891 1466518 785693106 460290517 181986858 514075242 724461303 363778983 703905563 36057423 559687314 549890859 305306952 901809189 97665250 747201996 860113401 765438719 575860042 146515280 91738559 293907011 723514103 638216284 809605737 704361725 46218387 435480673 214202205 110742906 777565024 185288942 126226635 510976096 361743337 755644157 869472189 777517760 452076357 664432033 780346713 228962983 328245756 473361514 222262947 716155215 553045883 505600570 785050516 174919557 961273386 211192860 509294153 208935798 894340947 812802437 90707873 438923022 404480233 449968589 522127564 723539442 970949094 269062400 43818567 11815712 492682325 360963114 165609741 909517091 588725674 990734894 783473123 346486867 573710562 425867612 552121248 877538809 409871295 411951397 658587566 544275813 937773630 317404359 538985976 550819543 518017979 489194612 359734204 80853253 311745636 299568495 788650927 294220175 943187959 593600056 422432454 452808183 644686878 363391441 567928065 730960532 991883276 432987023 241412848 893201273 231346885 238760507 267814113 765136573 257611174 948722230 535993113 786118119 920937392 930970767 446493642 441896871 705708812 167048260 773701906 127626470 460325840 88895092 661415758 116534912 714756462 711267213 260337501 419538766 387013090 203165656 775976083 817980335 637052214 369145027 775336580 515479927 391126673 855108546 635726925 182374441 819926420 876150622 20932429 52715301 603701981 66764295 959928270 894819458 957707990 887609925 234814636 864220870 773532277 663616085 859955031 386203371 168995882 909086947 547420547 213166928 523045800 441060613 979151943 29441983 181440358 451478816 844624369 997398596 440069029 353364467 289259604 939017139 614024902 406756522 830580994 88525724 208313409 28851043 486980208 667415539 570893373 911978887 700814593 112514783 84370043 57307127 401946160 210573204 322456298 936639098 91263890 564692767 543713274 63397971 41487643 256952388 103973054 95807980 113319181 969313992 421912899 483083164 682064845 316396668 221926771 814177313 66411791 609979381 786010620 712296855 825206604 3795631 354731158 405327068 750355222 910983462 264752934 693656890 185902057 340554987 370577522 898167137 421141962 802437464 494149334 604616266 25908827 984468102 653500601 711694303 5052430 175600317 77996185 81926417 277273734 443970308 725075266 228547489 864119311 248382094 970234855 36938748 284579555 989357323 937033220 922248403 594533078 207205683 961811447 729264488 645863316 670595623 285376494 332226327 922630607 327977886 435182469 264042164 43226600 469231283 159928794 838719540 211156490 52992515 552420854 180705668 439130726 806593072 261646228 617977290 732882873 311633458 908016855 432510181 483739344 968286953 650069962 172713279 293112784 560225471 869394902 262558045 238105134 424209654 569772973 847719591 737251549 462032170 984795081 27780722 771238193 40610945 826170062 391631802 918286668 673735188 410626565 794817935 946606642 950472241 753768926 693631879 590694763 699946214 558042696 911006416 975529462 917405229 478312676 390001000 694552324 354554677 631196434 33593434 883889046 395317568 630889602 753426120 707692182 181635906 976356488 365929959 317533098 886313250 94655796 962612245 958822718 131737183 521799419 499216854 808377131 488327032 600844685 628818639 791291084 763438601 572098369 422972962 833410501 224612988 900872373 168776413 506156883 790673199 565018181 988918693 381207692 474258911 382593060 458099642 926522033 371706290 995673197 952094375 573071960 57389989 180066645 35615997 224992792 695081485 545818592 268152626 393930002 334018949 858966073 443833396 979427784 96059205 25071722 933551718 989465790 161701743 685063104 313143169 534699283 748955423 409646351 682283634 276052420 908955672 26418989 889743392 255957624 481814216 337477551 680644373 468231494 828274940 980305179 477185973 70771556 302919227 408686242 128596887 281732416 779256500 798949558 277678036 629822432 369082354 413106001 821488645 172797339 269998291 580730405 563293502 209306550 480127464 215742012 832515187 813906664 294506982 789651606 323649265 911935475 945303962 340129596 502381647 564831161 883629967 661648484 231080384 952137000 650897344 98709655 625257975 889419815 309092730 88486473 440367222 574653636 574524549 87321825 142849070 779426467 396642762 660568177 89579852 937821384 272553210 327516252 352837096 761917339 445936170 835205741 888694302 594748380 806494904 654985596 899898602 901890627 425855121 235318768 740924202 95003173 49070460 385638009 287505381 382743100 804497054 178869074 451123328 328771091 274386765 60594447 210141976 582426005 371419657 779095329 832923697 967458134 822396945 889407583 713092145 341513753 549410085 766841811 718727759 409381159 856947836 166274613 271377117 492732847 321878905 855902933 891969603 569302840 127792462 638361862 701488150 898590776 666561780 93962651 389582532 763111540 730875510 445854987 159975668 63325832 879795326 623956545 661773208 167498555 635400154 888813467 98656534 950868697 834056951 604187425 679348861 193781811 501552411 633541395 885142363 243758730 198916596 585212075 985498977 724929268 899651564 961636515 981829756 110020209 945851871 601171832 982239233 35603209 298405252 834505472 975555858 352973464 564392196 934455077 455217248 116412943 280070657 948688938 409060218 756051015 981697379 587300719 447701909 511687127 68129966 426464992 882232117 854939246 242907718 213451199 448772483 236458749 459969289 881225165 473979335 64320807 614115264 645714352 65726828 903821574 278513797 39446696 656471014 356357642 574458941 181900167 277628034 692510809 852006972 798005197 888605310 163251404 156076275 253062890 569883956 296589768 426829637 401895913 417899220 10035895 809976074 175724783 693431519 62046398 855262715 232600941 443222844 833277749 388613452 53764539 272679387 531083261 332339407 81057644 402500379 900928143 901010050 345359826 392696401 715221808 850224959 633596975 251562397 166797120 549232895 344854806 22598383 802353357 83356486 867000167 522438321 834236597 199842873 243377881 687136279 585005944 701543315 240831817 74492994 793285204 387882402 986124072 324168535 855784787 585964641 602345575 450573879 152968299 676100725 986707607 176265387 819393981 433917229 434142019 276759772 488175668 67668689 572217209 94584869 436408403 306940951 453463515 310303538 317490282 47742082 393396030 205578432 950372970 397439584 295503012 67092849 234772508 30698068 968476907 483209840 880965078 857937902 41583568 405499580 651007811 954796186 985038952 102014390 166644999 635444405 312800619 973276044 538893326 181643377 165469487 426046034 681193737 956990356 572354649 730238596 103128529 343923676 536178591 55858818 229489430 909400564 829069846 921155972 866169178 243899487 983194786 457584570 101432440 763433453 692327868 260924446 886614723 843443193 900891693 149406279 14191931 567758818 976275747 460165853 78550810 942757313 86152373 732696321 796443257 193873465 384566489 387088857 656135343 447680977 820222148 845689487 777374633 182228035 233001639 765744127 878898827 574168239 376886574 671472494 793100863 480797115 571640586 526846151 987262647 964260796 932825339 628453916 49388206 834285079 691114683 637556399 33779240 68515394 314703344 141122363 504721730 187672464 803928095 594478848 204789569 156580153 750932255 55815741 206521848 198603208 30107885 932786695 45973612 735786856 720033464 229835600 678758722 715978856 755420514 977423818 382188417 482209341 677561398 530508843 406429665 987918636 766533010 282356923 493011589 579391450 669764486 977993120 43895787 134917845 496469076 394187672 797113589 524673289 595293980 721715655 988391306 108057912 474165168 182725343 916337986 617589968 371745066 169065926 941790361 1894945 639724250 910310434 946949497 860194800 247172870 288678277 332791866 867048685 271215934 204717077 558015295 139959004 449668795 388325283 225815831 947748116 481367518 721441966 955540750 524012262 479242085 238273377 6824869 611950445 516946985 209811616 494616026 418188559 436552038 561967286 724322928 339970145 357584698 431103517 195556515 945956513 85461928 145062075 780304743 256158029 74566248 644482251 434271425 549549697 338986587 54033192 274647081 403760056 563279915 484186195 497190182 254261763 216165368 956951082 943572471 497408576 721275738 18997811 580935730 699236762 794701227 804842451 648345294 430015417 703973137 428517848 17960255 68126453 985457104 419987525 36288279 721629921 207337685 810423805 481587584 137111514 983916762 203670311 788176782 984133517 193745240 934356656 668868570 716562901 503233094 941171844 486466222 16619875 45678613 660535586 968282758 460656206 116329323 333206637 56095794 401692140 127043114 614185304 729212903 264509652 64748904 108900129 786333825 289398642 946457573 229728469 805072242 553727818 128511033 792669763 456848204 900751847 719705688 574466719 635388448 144337214 458412772 517916114 831538858 281423420 514253450 889403921 412461168 63620294 337362764 588670347 949054604 729253203 787106331 107046211 586701616 233480085 23612802 901685614 597304894 569845536 48660976 797524732 667236118 179482517 396415460 886825828 71502187 42857987 753435339 607635458 196555581 375055447 118816694 888896003 624578777 652555527 397741619 782068308 956993157 94012377 946994798 401191171 159772685 268127216 314209421 448359233 193778278 10533356 648616697 350586139 515909307 864338307 904423954 230499269 44864422 844238744 66515575 346911411 869446369 718776257 662466853 491374978 502619495 947896297 662854435 745831122 94640587 436391879 57519910 83556701 825166370 979065544 124623185 498324064 505858597 906495784 140302409 875148238 141011944 224816460 878434654 40029121 794097445 669159047 104206439 622605574 799841237 509024407 323703673 378251394 259281470 449771782 427433651 759449855 10290038 421094044 804312795 753022679 929380575 833889902 957631751 157788898 124286565 107240267 566644874 555741930 533775331 225490931 973929433 407085255 617756489 365060277 146778381 218370798 993430019 430808434 135196731 203637155 260623557 33639015 51821992 880899385 442291877 57564392 11834972 38307462 372151937 596136223 813045135 569115006 315785361 839855839 62563934 871155682 205098790 68686295 520820252 90348258 182934297 968844783 678546841 249490615 475784682 453589661 887514968 690007678 771697655 872748351 65383573 283813063 940467395 60879887 863890390 443069573 528007019 544278164 456029914 473207895 481854968 336144062 126803937 615574508 866682330 428363981 897323001 607930740 855371103 73699925 392269964 848200915 919319430 555348879 4163170 420234352 624081920 823442570 730812837 533912104 354926699 362459015 636470096 2330345 170845995 808187229 461563160 25510438 755737896 87455185 824125215 210616856 725756584 89125969 699979506 198156562 568200582 124622930 325142312 52105143 664094464 633953829 3538058 345718357 764666091 807306362 29747798 469573899 588115374 70733697 105635811 535265323 132771695 789313067 537615300 899647060 51125312 656888597 369254591 922285758 582311296 392073776 971020596 571915083 571618642 847512600 143354968 201634209 19223216 128055160 965113075 287649689 218171417 400132106 992631171 788114070 569096536 167870749 761990988 813429124 343964222 889057675 178922190 664734667 485875445 154970054 732139128 884299951 290423401 431960269 132998836 414507080 170389793 219754572 531424866 365699094 909538795 79487217 656139113 751253468 883305759 916695259 54308829 450079626 634556242 145868941 404546721 662660500 411869273 281419234 576450111 766643117 120089055 343901205 14356277 579262566 796564825 300979093 625790329 726140437 428443082 86972446 735708143 18368197 891200202 357973367 784899398 379817646 963941222 663125241 283531034 803347176 448698068 909938056 770198974 84450942 402094895 421841112 185413072 648643857 239873569 109668137 47377020 379119668 796637964 181478962 854568999 367917606 960349219 928812841 27143324 114048663 766971255 618790007 559640802 693536681 32964256 47148058 48277159 845803468 907190207 47319354 957127073 400515556 844547465 169368078 750636659 990147290 137880984 320535692 526552466 163325873 842255860 111842245 945738907 709162058 552312457 745582535 708602817 929895266 154280996 595743734 856053559 675058450 811629635 589598496 233724071 937069017 444252682 192590053 772226646 911703088 552129160 128257871 314261920 216678929 149485028 623968073 453017177 778795192 835829038 113389253 98054049 879445248 705990941 975781690 365323313 721074224 582180161 262287751 208841442 994935657 675797640 119705712 883870888 264829267 811592412 876618079 146687158 247461077 732842305 93452786 969284814 558057815 786370368 763777114 22545377 42476976 571715735 910342780 925598199 564168639 57726810 751294330 42155871 716212075 366624425 721029949 77554797 482745054 341207022 904591338 389520959 531189431 530268180 644844646 139233528 648974173 5969114 134212540 655205291 248905987 749672595 320315788 930244245 985953459 691018965 230675517 474211436 670054551 646671433 103224052 810012236 132927803 751304591 65375989 598815021 343343385 322872399 543210785 880398560 870125333 377761428 949349138 382836937 330190328 152259596 198625971 950548268 786599191 394514351 555349672 179280793 957870792 699309305 124986056 458420572 258524483 980117845 859360504 390092945 703755382 143077497 419417233 444522173 129256484 428037468 252351383 264689048 495760809 943886683 1928597 591074030 310370622 767804072 982477136 507726292 583015325 544622950 847171624 715047406 849054716 349344795 325302914 834256492 565333109 33655860 156993689 949035557 559731185 570500351 442655843 104859459 959537720 530201420 898147417 57621302 599357248 480089638 925804245 455509878 812014900 178247914 80905018 531157025 172577053 361509297 838371949 73996093 931731924 869031843 363880964 478275516 560331879 166992502 253893884 772978934 400319284 758708983 694276547 447251661 518614690 8950752 865042022 288880676 318117674 810587937 215577694 611602675 297372200 763690547 445962929 873748951 126172065 139778535 945380119 591608845 857713870 78213537 698107886 726248668 51712578 595661272 275934363 981041805 119912153 910555535 934826007 159285261 756162974 448704425 377920213 350643327 83881150 183508269 378823031 947800429 272042298 649978580 301444719 749845678 875436818 382617434 653934593 19914570 66489746 518344671 326532057 761201769 275594317 670745693 256162411 226859426 697412121 83465673 862734657 611345078 636385006 799571673 924664887 443975073 862785235 614240478 304876591 296924054 405240870 477676049 817874465 259747624 566563522 916525217 771488648 189870355 395013591 17964459 546811662 674605778 669917060 427924159 247289008 150067146 199749345 76369925 196875930 432906240 765601138 493328268 962080366 353436506 62421552 389262371 54929858 168632159 9762257 167101634 224304928 501235892 477739854 193931587 569848977 949041886 57158251 891730661 543957776 443016682 74837125 77568179 950494470 154695054 447156796 502933653 972060203 885116720 805356385 839199267 784380606 783706361 797041640 133082826 398834669 294999051 160278192 139291462 257792294 609959644 339241318 102262804 58315059 998003679 171754399 382352115 259375664 352476314 93630511 679584396 224503193 216282937 13346299 134097089 532031933 454916891 472913323 942820092 72915579 705629995 373920518 715464723 245899836 228752922 509410604 341367539 309277970 352940470 406588295 878489944 398328225 246414807 617552834 626382435 151574734 356197257 532885463 813664847 736025735 314685805 593265022 226686702 711345085 140962382 379484788 499820793 96801290 307291082 323217104 933587895 411808574 97935296 230184627 665122961 701580027 385438756 344433398 412458661 425293230 280093545 304361701 737237175 255494229 589344157 804049415 173805236 999114714 868242885 511104690 844257647 101522274 36829424 675023712 861594915 388478646 768317046 264286490 925456670 292602110 637305769 835214821 879872822 530340626 669160015 583063528 238055286 391905714 560722157 251119648 595255454 684045683 848432157 352202353 708003471 980001441 64137110 546775918 15499942 488807 585165029 823562782 673814774 213013460 415262391 189715879 135178750 554104317 555991745 375042248 954741880 530252258 897689781 367307637 194591238 418781423 25697184 989884901 628457518 209841977 821068888 185243068 971667183 990236240 110567339 129194881 625206133 188283177 227062496 233889052 328795238 784119482 528102887 696695619 51494729 933035690 505148531 46436547 435805149 303293513 205520354 11149950 210846272 46817129 197052529 397920959 520663667 686698008 178546115 279480509 657954351 401057775 167720040 284649562 542079481 462535232 434708426 718133483 337372777 890075435 553730897 73458772 554424613 436749291 792721417 997545178 709641388 783643827 545596633 864741780 96180340 658480196 957888998 473662779 955978045 115421785 613996063 475847221 360533889 512276417 430780563 509953003 756974067 658570614 245323678 25329808 149071447 170016926 796579947 25093697 869664510 521889726 550105077 671318433 641458793 52045731 119642167 774904696 167639804 395003983 457884059 129233621 857792557 70659406 184628187 720000376 315409177 492826897 15664742 450018063 423746128 304840803 443797474 638347055 775304635 961761102 805354528 860943923 882453342 320553752 121682653 887211592 946236571 579516746 277473948 304490426 360017649 875430814 260996431 280135388 703426557 606535704 21875104 351981878 494843220 293547802 208107527 41829302 58594200 503418004 208069786 731604853 706740931 399406372 814615646 450911203 275717392 335239416 754194140 546609507 26865480 276388938 414490915 954185905 375435335 200001218 968503668 556772936 15522687 654882174 297958592 621584162 635560488 446839180 462229709 874182741 983453286 240156222 135954838 629223746 981903719 845193981 634983160 696129116 165663505 737808088 365983473 514340922 609150365 385430668 565536660 820964104 57331616 518511 765570866 946019581 460856136 702634295 497647678 618453824 962519221 958814540 919219525 214670079 443501661 2220012 962098756 488778501 425425712 771548582 843668369 487651749 545497742 149958513 701417158 937039415 399011588 571088201 349819690 40653430 801293207 295079262 639192662 674346985 424174791 545246178 150148735 646051785 737926086 383168603 708068192 682407390 588333461 277094675 127511928 762830455 387175834 338284111 670079602 888792056 400740444 441225433 485441016 868577322 70076488 328369560 401135997 624352025 170043944 132081881 729030544 120236275 907660748 493867950 203908384 719393192 136167432 658717834 229035399 292963076 617781455 816306130 99334765 222771041 867333854 183027905 923462978 295505604 638330959 757776266 274890410 999419782 24720571 234522434 341421125 848244979 403932194 394219437 197787387 332753793 536278507 206149764 421853906 699811220 953586378 134741076 328806418 896923935 75144969 669218542 470759493 354802072 924011783 456536599 202275737 317781028 254647818 743299085 56666480 634241890 463505790 526074287 79571945 354513200 215024033 185788925 262362084 284420285 306453730 51904885 696813890 144494542 444532964 852904970 896883747 304392741 669616478 70129757 99486541 226738390 824870005 738722854 325772551 453457562 645740733 883337392 236302954 429923557 392952950 485026140 53329218 912001438 499982281 274280325 628291739 78599335 873140375 616311740 806144045 246577409 163902010 125292222 811058442 528169626 475149858 885576689 525492673 205561940 980560343 892320300 366764736 83885078 451290985 899570732 980820775 973433451 785372897 94382271 180380352 393797761 542946538 709724462 290629854 161907663 409464632 742868212 356943939 795640598 102588196 441490072 787955658 53916208 451417464 839720758 554807064 504062572 785667232 601192067 691266665 953236238 443160631 652954454 39638791 790178361 537612429 616029401 657092427 518897129 182415143 339548194 6396708 919343554 149495156 233036050 255824361 493874616 431495757 579251336 328378993 62521480 771799773 55464901 971372214 837311567 557033865 481387436 189117745 139751834 645044810 518296256 979097250 229297248 345347040 490498135 932161607 129735337 72999793 718357970 101283440 822580228 187755332 445191025 910972908 784766496 532693625 708074956 317653517 922860931 314875909 938753690 715713487 160383699 49297300 90080987 866946277 81339528 84483549 318052030 114638899 24926112 27684623 956000509 409386771 584436061 148930022 122826481 547918727 941597807 165692363 502816017 51726772 366477372 88366165 571927736 606695643 130220492 454245798 183890252 701688354 381797966 644247208 165998086 116821826 440889088 776487351 557611209 172917893 946165015 6932564 908615953 8737633 708950676 169452995 802817896 627136737 958145029 259846068 164725454 696646372 575447111 231841205 947517109 385179685 255684307 524766116 523893299 92498260 211711681 33011873 999621097 167836735 73077452 817268075 154293057 915079171 567137265 462610756 436260822 786203588 702920875 366411960 754703250 662634124 84568998 360717148 425172230 905470483 637930419 306648062 31039308 464233349 215820146 868187491 879201206 309440729 861540721 178342828 125321175 657936550 833620506 212884132 621696848 878358384 494424794 73838805 301140545 150722927 914523198 580020529 549135231 273878565 4838801 5944438 979947804 890499303 515810040 138623792 66926338 133058889 39655966 759981012 993399903 107929078 504037994 944491225 53685264 948591921 184685874 236377540 142370483 455189644 189584483 213761036 942771427 499383557 2298748 338010350 957413203 600803709 840764932 90310776 715757480 893715740 351297790 560073083 105253978 252740171 963840710 841922638 528205790 958527762 400441900 817698855 491165290 935404388 69475321 794655587 583114861 553733655 455538610 756618717 405828224 792841072 410389899 500355658 762871793 150805643 658658592 230018415 9081518 180874403 823145433 13067604 857112152 726291247 239966361 460794434 93044963 23162605 808028931 115160216 160982903 862627860 198926421 34896355 21627052 165811364 763669466 433244689 911027127 151207334 755485643 305780519 685898950 58694405 30182043 136190424 451141583 80749994 104430816 24476442 423846282 207259408 311708013 744777224 557722861 889687568 68113472 389376128 429203029 226642596 625826961 734193400 52701126 189199159 730932643 554526538 714349614 917223780 652796883 503148669 138001231 589947333 912513868 853057189 981041286 774864185 774424264 976076218 622462678 866913479 844506297 583415094 419841301 541714849 45426157 982915029 878997956 91596181 622692645 557296126 332131355 190691307 160852944 878806158 310826554 216676778 783777628 184681082 515561611 898730468 858164983 558616881 726885615 768202268 656638635 756072973 16357115 819924872 855681104 516852410 456091337 128463588 605823354 516220984 143996640 276145524 372434503 608292071 192686762 403744976 886831344 738587825 118612526 103863591 564946855 99508706 319775445 923888349 763733068 378275448 665064322 777075598 197690582 539221585 357150427 960581234 636308790 674063202 997017123 667997192 574854458 892432776 51053620 606707900 747483611 134685594 85221300 620021426 375313520 724815797 531080651 631243447 729355687 781391428 659946847 241710305 470829734 380888165 264339907 205338903 391059150 836195375 673174475 636088889 768648047 300575441 845326873 229122067 933372031 47832347 372150354 135439826 251477931 934735936 336168293 585726011 885009022 724684406 518989406 737730340 508417710 13522609 59493484 957877113 374226804 669138753 923751628 103502536 202924340 137729078 484242280 848450729 206259482 706652278 395860429 435099728 319861454 500359177 56737646 630233273 615824247 525721911 235492637 3513156 86851287 370680717 390518367 243464601 327835576 802815537 618244875 915004524 204697852 710718104 997684497 6203434 956684296 926750628 825749571 459243227 104471721 402331471 68887069 39031007 92915997 522589726 495769106 216691522 756279072 275352037 298693120 749016658 923661886 661171083 862035225 294163628 738957217 974516937 723826861 308196015 368579781 614302329 991197002 336698935 462322477 695391004 921632886 592180491 188820143 463134280 664666163 588144594 526695230 506733935 272511805 125579899 125071278 818381945 542577522 483826162 825676689 958055819 434782719 257776809 712709403 41371086 114012991 771760127 470518773 184838772 170028247 361261362 472699631 153803785 238097444 78867493 552421366 765586234 103449442 34246304 129370465 103033939 69501747 1 650304608 573011540 662830610 424443943 637629150 604950454 706390046 278638948 398016391 552033524 28691613 183080018 513117814 405881563 674961519 175832577 671971775 318453714 128691182 86459524 257569189 579572458 654581565 712941461 273492610 694182453 739885338 619800143 595599168 546702910 561400881 703341013 705859135 501126783 758946866 278686560 358447492 818391070 414224065 629400889 405173743 187148631 162452623 20519580 788078611 487599367 913975508 406643553 118556436 890751618 845332900 517757812 102082275 69391068 599136152 691013071 859981087 506723620 316785480 817793047 17110043 582007194 941766890 692945178 229632513 463190853 572375376 434696883 908466506 997996700 351919956 352447602 265298596 919826106 760168095 835536164 720871850 105639857 248361416 214214409 335827839 407059068 156157280 519757934 589116843 88941969 51077456 786626327 429525089 208621400 30279740 549101596 603203539 337136534 754799326 452828505 943416276 515602768 986361783 503910004 277892963 219965769 466671945 169135743 299037769 278250978 178320030 852977637 68338618 646651193 928424897 561953231 942725563 983813752 408556626 5946242 326154468 259636819 728584875 360899480 385401377 373721502 145779792 281363049 128691104 918846762 575805531 222545483 449999967 260389084 273877902 469201663 143055745 570189086 886857093 955721346 779234897 810382269 701006997 839303417 892862719 621118159 671666898 631124713 120215489 478482185 663930988 726262534 398134500 820430670 633010519 952697082 260501383 739468799 930259875 391185639 336824365 59770864 413022674 255687763 822233170 927815671 117386128 810828009 234461715 556425595 210814880 67194905 880920434 668570179 38405526 999446017 912162285 479690677 627446262 360537857 901856978 763295799 529752368 390157072 218799459 93255180 758703122 345367582 704561372 163206976 251615868 687369048 66257037 554302577 406105749 962420389 118892193 252722505 692740319 652890446 178306021 918461415 65853139 26541610 804589597 106775737 964462190 485512776 51245826 265463569 997631928 605622372 968978466 297396393 752479811 641473500 479154244 390356403 972036928 283101753 295899528 535337618 899255381 168052230 79678504 192419111 639137162 797378315 414394999 849181119 381984964 898452656 540223922 6113131 311156488 691833942 749342159 577348768 128350070 988810369 54748474 245198392 957004377 223408965 616063524 418153129 338319845 417912504 417047511 793433035 445244918 595076829 176435828 174811999 485625966 351829653 250334151 516253038 266312830 918901267 566374427 917999185 497463043 502590654 875825882 425471916 572489484 341222319 918027184 838832985 988467836 335885673 622561272 364569623 930402531 151314917 222231980 54748776 306566910 442111177 290657140 359348366 244928802 694806281 591582159 374344652 599281369 40878025 45751509 528632750 402453874 13140751 709215537 3526073 527447348 7368365 977273921 819060662 146785275 41695711 633831233 407263529 732963386 744564329 373683049 636979060 481807951 731883742 334064395 121060187 951700431 906092653 349947178 453028573 603816989 779960590 866899687 877432088 315683666 451667087 410678518 149152259 150206832 745713573 233793620 212507080 299389881 234376924 256676323 345858283 584786938 635853709 642158189 458883979 32760704 813351073 28098644 790514662 411621161 583370466 915406187 985454585 19192779 836294897 546441931 87995587 112039673 966934075 830928694 977543067 740470434 440608758 741303738 682187826 678269115 945472055 577336076 489423470 631724281 825672859 158893901 348880064 342158715 949366510 866325167 151095375 790219456 857827392 640587442 410249316 240552984 975335935 97493296 439635953 261387863 679915226 974453978 670254065 528596928 116118536 589444616 264216271 61926673 909393207 579201116 165141122 490788168 904416889 649019329 950601950 704112965 104829541 232285719 709298698 366556059 308680135 356927984 172490630 296541643 101773978 463239379 376307999 281422953 800607538 292321731 927211855 687300936 695491714 726286358 57638937 753297379 377100958 741043018 779448206 718192441 369811393 950493855 247024519 328271990 279883888 869727678 873812596 164216683 305013108 586925086 917268248 329921100 428897526 904479224 122683926 680805627 483640279 231098343 634137016 251756307 521849847 855393665 895094415 639288192 272389853 812152046 257421737 431812884 667123629 968437572 312664925 419526181 879574103 690372683 410357246 338397369 761887924 664047319 11468199 743032525 83964558 606281586 574990421 223799910 152897211 395744137 254799481 697039604 992088181 439073671 997234835 940172785 743021766 351387649 921847309 57374017 327807401 314504252 85293303 951573761 730504469 854624049 298999084 506401344 140168952 709960844 732396700 992065806 826056449 18255774 568946859 527346685 695619889 468825717 973380504 715509813 591107371 521588261 961797848 164753847 347490631 541111796 267791185 804276442 781372526 351465504 100206694 505853129 877422706 696104613 402307321 114155681 637582610 540989602 34691464 399023609 931385517 532068865 301653472 475704112 220274466 1836076 71982487 741196232 846884547 196729935 595533793 766980968 775063382 984424610 105424289 243070592 355770697 488852272 977447722 955009320 290475792 309822540 949432066 436737339 932270726 417245452 473444953 913410219 153156118 891656350 792291814 927144392 254338075 79089170 560391165 442848180 857917740 919854068 880891213 426908174 311906910 342749679 693040587 691112749 221775101 121286345 140629016 502653957 320667500 241336219 407174687 522849266 501827301 205347295 537512649 370619507 623486002 163321355 820015996 60670968 11616073 311146477 340649840 142170226 466079684 929168442 768686241 478351407 479660168 373395081 773674046 947422003 104096529 119427051 349729710 780271002 104995121 130494623 947957502 225332071 963535815 506852808 914823388 697009268 573556024 799322677 815072689 563841897 60829379 675474954 680504051 935039050 504019909 938507602 688731054 382327501 722661775 907357250 405013974 987338920 967550566 6081442 612050727 632093995 674138123 608115874 291698846 213112896 745071453 673249487 797967715 911480118 91450026 261224452 412274603 968185289 69723104 707666028 910174923 937308766 47653776 100015452 462403363 98467002 27610856 651647165 668905786 396552964 948942252 223203395 127067381 242023519 607316015 746512713 781160819 231453340 907263692 540666194 863922707 346520487 314824962 425526009 256444845 408943452 752659304 931185930 7917569 86229972 541895843 172458449 236121507 430691434 592403821 817633111 145407326 934940101 841682839 524015132 464489387 762650744 894739619 417324676 618095882 20760874 136033417 244731509 211748137 484159060 626858986 316598978 111116578 510020003 37179188 486785216 141909160 876948438 672941719 756378222 576392158 334892726 576589072 255845442 33523999 139343615 720725573 715955734 91330164 832432166 143697616 54814849 53783691 227440902 106419892 811606482 466905516 782561043 309215815 11505748 433412068 255228384 900855433 936413345 726216538 427720772 543407591 935135939 832539445 644763561 316187277 227526164 156000135 289258567 763719101 340339015 179022273 261480840 988074468 582828059 392821906 376694689 491929958 820877523 114976135 459986837 234035829 469376929 339081599 760691498 609767386 714528035 16753521 168510953 978013564 979275410 339901727 455459997 229739831 623386548 433361412 96338662 645750008 779810625 283409074 577455580 442817642 503350570 562294305 350091018 475823280 159228299 717348632 59694251 821391603 677531452 15043967 383968756 605354008 171340174 404351800 388310520 407294614 279791055 494018186 884935415 237590003 803026807 889822050 451263537 716043184 780540621 886515326 427318428 570816806 270622102 812288047 325620910 806099499 528890557 787810070 839151339 578070319 473025646 800158580 542070598 147441734 192540428 947801905 413418885 531242556 730595993 246746488 982860089 633328928 591532287 397906033 649041092 622916043 770875843 565003638 419980064 265905471 823869377 913857485 464740748 843421953 850155273 71055175 888196083 703345515 850001216 399116739 811670707 373172283 803008948 867597453 503265836 330522717 267951427 65371845 475149179 371522994 693216521 657130838 432306033 551327152 172608717 267871531 315367347 919130701 696668320 286531749 457199425 507993263 649631713 991000990 453156533 293225099 333458103 574828335 919866053 525312497 70729820 863908905 371531250 923286825 627429439 761582506 631431691 16957834 480252594 785311729 489642836 556703673 99924924 605026926 815504614 629525029 127837648 122292566 884319476 789171312 528017403 783058640 594573737 775076932 327295012 539539109 227302470 529595058 575093998 721128977 633933864 311060416 356616472 692134617 691660876 793252748 810551816 115451903 488732007 315673746 432012548 918658268 570384872 356364023 660927651 76623159 388037604 3472335 462328904 863356698 142118897 438242909 535436161 11214105 139848235 400127035 142278328 353931597 484898016 126767455 651250391 200609935 235240502 580913459 799617422 97781547 799725449 534570493 962977599 42874249 330801814 480122406 512883342 268819291 439081606 950006840 961406124 822819449 618884136 81225171 461131512 645609816 457039848 164985406 491680073 275349990 299787219 989825665 548014013 53963636 80104983 841067914 215460919 317176762 375846248 402640025 577012926 643488159 171466209 809779524 694316312 51434325 97702486 24807765 300494573 946507685 583343054 461944214 576207776 292875414 631669423 427673025 552671258 658855674 921820745 842833830 981654638 988472746 721623852 102702435 398703627 856426923 437697158 969437593 181875374 389070627 243855977 818208606 136914674 362788500 971643137 25422948 305645606 717268814 191805981 451253004 465655447 735203020 407519000 548932374 804008385 598722732 353323333 34330197 800608496 671475359 892677116 503140555 53204935 243023815 149100114 199229865 119990792 265221153 802074244 820514960 830232849 479461831 436302915 250149436 988602872 819648167 68095278 83336700 526500695 518806167 192673709 407355325 82164462 819590944 500950498 694349480 629958126 239106175 6457088 603088381 75677573 955059934 168819782 82640493 628137216 299799457 15991867 366814299 18473448 814885793 134570907 608173498 949963932 969791462 577617468 231685460 823709404 641012190 990244246 885332617 136959604 785130297 461423604 774558681 23175654 950228830 709558400 61970751 358182106 723002365 79406934 632631647 526636094 210740075 410686028 61624570 410523368 720824148 529161995 706757909 212895192 243896924 219766002 417289989 415717545 886719631 577442466 455003822 473947108 891436989 694702903 56657585 875984898 480602940 353380418 630825168 864867656 835620802 760055827 912534813 131433222 997475008 164510719 6305260 903098002 695606359 702639865 831105571 541670535 400465062 69230444 459802480 755385111 170122439 232472487 143242142 422367683 156652050 317191255 272011290 996285278 832842582 15455238 687029897 512919185 886436065 245567252 939687090 684122803 913085097 14675430 646291578 460984086 165205064 71662929 407237052 19726139 333322028 172707536 305882207 128834867 303436490 239530433 17515565 625247000 73130061 721233505 332106382 153398442 979642944 574500111 588473236 739516935 249461855 352991712 788670290