10000 8358
877631394 255441479 504418213 615504402 856610250 997194708 162462364 262407666 331857764 898359775 507668135 419141853 370959305 761358557 566081338 904498428 768660625 148954606 426585169 905554933 357474288 418637160 895399525 842856289 933809201 358721467 964253318 866660023 579737699 693411397 935270996 876837858 167292044 165857883 335095805 968011206 642977458 211359629 294488238 228528337 81064886 225381042 418686026 452277539 710990177 892659515 799462202 348989762 634732449 177271583 67196889 43333299 484787584 889502620 930933403 836167529 819908256 174397612 709312363 696768840 401612904 187430152 546176200 139675794 164501844 886921401 125853369 657725390 876771047 940893886 90204520 137856621 949332185 922099188 194792449 875694750 449654798 306262867 933602836 677222830 240299801 722541440 23637872 778990878 599657520 953777911 558136827 355636276 527268210 807286463 652710425 580856489 367349947 847052522 364264245 467624068 969155252 300098916 62603462 963683268 798888255 160974487 701861185 38490399 50330523 884311044 618263784 100998215 722805177 778395001 137793378 186424767 572184747 536715297 763677925 343698649 371430210 90852217 986514339 864997281 31825600 299758192 346931106 501172318 999680202 398492708 583969244 329872001 458341410 229291349 86132428 118114001 334551906 90656798 741252820 918054846 710002154 256587401 57746394 106278969 636830717 11143272 43249336 220128358 372289386 742456495 706430739 394575157 748946293 946968248 210005880 500066790 227330983 781842754 317675134 891729715 691006197 14739468 932606374 201588257 783147438 717318785 446155983 898188917 772499132 42608943 268061349 268802239 135744208 755592563 707087915 450701135 555785132 83518075 269383495 393692704 641453063 533038590 748728242 557306634 568034197 375044773 761834497 400669317 629386996 758299104 320387857 80636021 184408628 958960441 863558011 948785859 808859338 170716077 14000467 557009998 515632001 503900309 136662032 162088217 609181800 248055846 528777001 411478917 123235702 577942530 707941538 674824686 483881318 705533232 259619543 54243465 246206045 251940742 321131887 307795849 578615285 605682518 28806724 256318131 566356912 40713915 419816088 810495985 14664590 859568865 675892767 167435844 452080278 192500747 641909817 41597690 458162026 753350215 974888156 381651168 382235382 607240889 914062443 517204864 238579494 695159753 716203587 837625540 242010470 896301945 640785005 90932739 709667228 844891081 361997908 762790339 961479941 875983751 481310423 922966518 958470198 979391282 107831928 86728553 362058094 364458069 461428359 707795265 386975820 268464168 535606224 914978184 111914726 286101589 970418 242514839 229307740 934407222 948954160 286919368 799675082 286275905 668453648 339006719 415413034 972598662 245410085 135275866 552344614 485313935 584308835 316077678 523902397 136567013 365055426 405780673 470698102 642214925 736113189 460368142 718474925 304660937 12111082 887065329 591986296 309142694 748792066 18336633 933261030 561430065 924860697 90263070 734296599 818985344 524997822 451882507 22554987 75093071 412808128 473908048 868339670 432992388 991787915 420377261 385166603 666593230 94646600 905194072 733003450 678207352 948681416 226790291 657597579 170850824 469653094 200290719 547121589 514713768 323734637 420834509 257096241 141786507 202773580 465093535 400277497 2826841 656211284 623881349 944299152 444437206 894920272 985065371 827404587 160115342 821606102 441188062 663909661 18639013 59406244 171422019 880929618 966044678 617714110 982973841 757563142 16555441 825177152 807912326 726167612 434652723 705231716 804783399 806250836 480320564 521926173 928953680 413150363 162102950 569071233 244918931 910234660 276132113 26878894 911640620 155132644 328734663 221262191 953384742 777779336 631022288 604733922 865758051 559030405 847719842 874173454 143208197 966905075 238384671 353972690 948432436 725796127 111706701 812922924 737625054 140100786 895725516 943820465 527535562 624575107 366089187 949896494 392482576 640166682 248554695 307206691 963467052 877803702 430232277 248273175 31600158 665632259 137183236 637766679 136568828 928139816 230115541 898322012 171011343 155955915 372767027 20122433 240533874 90851181 760412054 471352097 895851214 725057022 206310126 626579032 659451437 278850543 588867428 210048704 613319032 74994573 35493409 842580914 218412678 255333968 293249068 382709463 87508854 826062994 959758638 553337209 756747369 121330511 155487259 695343429 115490285 252929071 802286333 131997091 525088906 6550265 80136791 527121913 273764245 726132527 125897364 325561819 526011621 122739931 529361513 145525791 990279101 203214455 72584919 86320778 950482264 245795322 598310996 819905666 148392242 496085927 480411368 157103378 135888780 547373989 858150125 837317835 691877214 545416018 914909066 56587249 942920017 707995227 136956895 799362863 767401151 60139470 277676236 898422739 989576648 537739726 212019785 740459337 363640228 963358819 293815726 483775600 698258298 341606502 313306521 875164120 225410539 622051087 140025974 231881696 131782499 736612315 962075386 826945339 904808332 458816211 670527896 219993457 877381631 469378683 986130821 474925344 360021737 611560773 778536588 203259483 595857639 777863364 114575526 570630102 317700144 762378139 22199638 309424723 968609484 453449944 362902705 802830532 682170021 89735900 962636255 154935243 984467120 637633851 455913759 184491579 42253780 966108029 961472378 110667884 44737501 24677458 787746588 359001659 10677559 761880079 808111115 626195219 333289500 600113934 500032082 519831046 35910122 626355208 75840813 863992975 246955878 232964134 511933100 970995614 866680426 336097548 38183129 704054969 897654192 92845726 171398763 76004721 315921766 756215661 690210995 635319726 927990803 299798033 235140007 800692696 401443293 239641539 279307671 486586732 663242606 25419904 798389296 665151265 569545054 293478359 241954138 20673566 172452511 171701138 117520130 852051108 815484935 132133590 69285536 986006332 915890243 379431477 333417864 691820004 617133205 845732722 732415383 982970832 654600644 243506384 270738436 503980519 790336603 470238794 279171999 841757247 240883265 918024676 351704465 539808898 631519766 745457859 617498692 75292926 931259378 411433943 201226216 79412290 786101214 111611082 106896773 925450042 589108190 368569626 961687028 304400642 998365230 380066809 131599588 154290028 49943633 728817854 472495853 561289093 376193743 825852957 589009799 117957273 997028552 325504244 175480596 861736705 162705326 199778927 597778028 442302875 661126960 839299739 353850656 788731713 629715456 634544216 860276436 936398932 700011931 725341232 10379416 953378766 376568807 45392313 3873287 218814118 133490408 85779569 586263970 427279887 546250885 643689540 88212801 154996187 36443207 621861395 490226971 683670402 190839775 283990081 890377996 528528608 118150577 908445655 137008401 268967071 72536231 780111136 375687994 983545768 949531519 738650723 492848625 108090807 302210182 18575137 310751355 196911043 783749084 626114669 1545246 995620008 347508615 409019334 423585086 926452786 736239263 86009851 808141901 71928949 607832513 817863154 529847546 667189006 935019218 956435320 418335962 206043627 983742177 491259325 725870475 226848299 67916314 659373489 366303543 878983896 817757692 412157078 439463069 575687304 984698660 76734707 230291777 638989494 952187550 820842162 644535278 910819405 900278967 547120382 242097596 256118796 709711703 736057085 640597481 614257724 364357171 561376304 345794207 532420989 46958849 921152487 219845375 491722191 906455893 877775805 355330164 261534912 637029965 567134833 401728624 880577186 611448685 505883891 911384981 818921962 602967776 667215501 797232733 905872220 56512187 763211070 308404096 319192223 983616361 745708820 600828348 725339112 294554728 603397679 778600634 536759009 722061993 398450592 941868575 841462890 956249611 233300514 756233260 228521697 35445101 954380113 23095613 6414088 845394958 658324016 808307758 482047627 997712323 229677446 547115993 713528327 124190230 167413491 40238286 488506027 542805032 656189800 90155521 390562986 926508936 866386086 197193608 384282457 737612178 68237373 742837664 777778018 175005295 72708128 676642323 45930140 238761653 246004729 432058316 386159806 645771724 804205635 858259040 585449563 67170614 343888963 18508255 783513718 341573090 114443601 725578846 201632689 233357201 294964470 495077981 530709052 66542358 337857579 797192426 905637549 669423322 193847386 897531304 676714605 901633362 301655675 734159010 356719526 501652594 589515051 997145325 884142871 952098570 977527685 429259875 170674477 92177013 881082147 508198218 21136760 592311263 208205062 997182631 259628434 809120506 998834088 160495071 422497885 943583729 322019009 313244575 112133968 926039776 284450470 585675161 640139294 605097288 64214021 866078399 156482098 795908901 156886902 762647040 461263227 748058288 558341202 556522434 924211481 1640389 560842373 620988512 126930251 787743297 384998903 110762866 481143911 861458361 279529133 5037120 188116478 325982471 84369337 509099648 278058082 762527450 371428729 288591158 384671857 153867563 942234421 31088691 359759532 560956931 814377829 74301534 643785354 521435122 985483520 920415570 701052034 270150643 439519511 576406600 228401226 5892446 604563024 822279916 619157345 893879526 474461302 789003004 454606777 917108621 178693803 437264154 279573192 323989354 169945598 17729791 968810690 182513960 237292108 596183555 119966266 808781854 933325048 725417985 251150643 269407363 839010703 237319713 38169670 191809547 612532388 489216819 224740893 924879822 949787777 230378364 310646645 264696072 734586689 17761998 138807406 327694151 450438128 964058311 296016852 332537822 964728623 52556189 471206897 431660126 38404826 853334010 524432162 64496972 49710673 509515986 106816378 909501953 276367117 250512312 971455573 326952852 829980838 534754525 280134556 366959639 806284102 146172767 446647113 365595048 561019103 278923830 432526636 581921337 41696028 251961056 675855169 566744881 121675376 16911019 48266324 674969277 374258230 206620603 364970376 375907681 551805428 438220005 248559461 811059267 42122826 888801480 181617042 843329340 779912906 295247517 35399018 813443082 487187194 649665843 874442633 857383808 849924597 175314667 567017103 987323081 88411434 133632780 737869829 646499886 152575895 14565345 493445410 911734353 140506047 237501963 344311201 827386459 795085649 805808545 489658259 392159236 354940021 584738522 46268919 359413138 952798028 808575606 265273060 319342862 842541496 659326259 811585853 589031034 732315325 716504395 900534591 53830723 767025665 800943442 100640556 218518697 640409790 635316388 285757938 273001980 159045224 16286329 671589373 738934266 364675350 68922421 673050379 580784485 715327958 511438728 945262858 63711125 202766559 805966008 409687673 781496467 195285587 403909127 781698437 460599005 432214327 73590905 438433332 430763440 40431840 450875104 174268286 710175105 604254526 933928937 899451627 838525987 480138314 342819816 37781896 771766524 382981014 848876539 589310898 72494398 888719852 282007379 498631726 665541566 901067847 928310643 578845009 759079455 640471675 225588437 829212120 342632175 477879428 368727165 219149803 478244101 259208396 425115109 208863820 351768775 471066837 577180092 969713138 989608430 641283817 660744651 273804851 382340068 213246126 708895843 827343850 584203206 877623495 910353779 354835911 855706251 862965057 208517469 127984365 463465944 834423323 403851307 435309060 460660747 679954098 44552790 904642435 411068642 588837754 99025833 853241461 784463014 132246890 921400276 107208992 728814689 305173069 652560461 750456884 804788192 975343272 493759143 574348643 357724253 324449475 103678980 107696458 791634085 146755961 817255117 532464070 406292053 189454953 298711113 836185676 322971734 730024351 124871774 742156897 310433083 129508699 996729523 764174248 114373404 248214960 875107681 455459191 1715429 828797955 732173379 192806041 424117108 85964829 189440590 66043273 208296367 977695315 767275042 13594029 285636915 476931761 749556181 191481787 802091900 270875598 178134847 905301597 645405905 638928385 989058690 579128559 60009676 723681327 510079424 651501226 888134605 761080310 641994151 284665093 276873885 932927401 250189090 347476613 290822379 246835274 42222965 191589836 88213847 478519928 951607098 702987065 524273861 125835359 80236653 213368244 531698554 565577311 306208700 316977961 794651204 320697389 14598673 308870396 381508536 981386996 655213047 362740831 411897023 241299116 690972202 937430648 570053493 962575786 554895200 530181979 162068760 462639925 350364225 729737793 765937261 712685030 74862996 695117261 808629244 95934643 241341459 894775279 393423316 397287222 467156502 595823222 207175951 440299420 913840142 901074099 688435277 525718754 1312137 586087221 802888132 925688990 192368067 43938101 410850447 380280926 828047920 936337749 916628137 390428545 924759940 282785552 594074379 214321534 321581026 519374581 842394679 360531265 527249810 291933172 932940537 324440508 555776756 440536195 217281324 441230145 616175020 272072936 530721013 311543629 744943541 144498572 432382945 3299276 961267462 510267023 330142458 853591136 27481044 28021377 780194635 42414097 458413254 351046230 741023924 917370897 210951441 540167874 338252929 11189499 112441736 453576863 453852441 946228037 36519237 68528018 649135025 73581865 581485436 41660878 575133926 728729864 459891627 486366631 732529272 473424707 373065505 363367241 704061425 235427087 108316644 371220128 96258397 511618637 379951935 182040716 352549019 728776873 994718022 721367823 872096968 111547379 204122044 311888875 939479651 153869495 673265827 249131224 599038780 747984022 728666209 621921951 11396836 11939670 690551832 973006334 825978238 548532587 21719811 286092209 531634526 665181834 862846680 165501007 930929795 777086139 178892437 308572392 200844248 55431453 241569314 153892898 799585588 656092845 724325849 914891548 482858629 651366283 628918774 502476501 39905201 805314419 854985594 36330721 763975943 228516675 55372778 799519815 296455967 877158180 328240615 922814760 866153272 834006177 693122386 545554407 856941368 484882252 153552735 117441900 603379137 946640357 307713695 520928864 287756919 616462129 948821699 675137660 499020465 650900886 17357998 94351760 12002713 551997482 452310236 398207338 848127935 3481205 91870861 946864460 735791406 655757328 275908810 530903241 401152937 150907786 852118526 63698888 319246896 171531147 788512790 121989423 821874806 400609620 668025067 404858721 904116025 880549346 676458765 715963520 810283151 71147314 154531388 768965333 729892899 481556589 625431538 6797720 6377667 359597810 993200868 222852458 350004507 267727897 62762538 134884516 168084510 697941790 251860139 322213495 353234711 166495557 707198013 860475015 779562323 850148184 994145749 618115727 174172535 176911806 286918353 508956958 883559697 416128609 772309649 772440703 925884728 91154938 879207980 733597999 385778072 543496194 953364010 720627790 823594714 576185625 907644864 762217074 569045302 730846634 715073379 561425713 891827770 827117703 543140227 26504510 135836019 143632340 782938947 746698623 525539374 825735434 17208029 177126709 974044500 778768849 128809975 471654357 951204005 148516445 891913425 846240882 525681753 443262237 19458720 264767361 96469690 745271958 324790826 551900127 477258831 383662205 893344091 36199109 380134305 437901244 797084548 882105937 27486682 938358015 519756381 385795610 107784437 852010963 901207251 475332419 573856684 705256471 213283045 693288669 546221166 461818988 672311677 125316136 289813317 95031603 436295888 848202029 67733836 957573829 751969144 504622768 570095306 188345221 990019497 496990172 929981114 400570365 693884593 395479142 664994311 149620441 469040225 954997006 244495996 983238145 479511363 914600145 135008458 50109759 866094411 647542037 770133000 97131955 741218690 391724975 571312922 275247423 278741679 837440907 908164985 386062038 972633008 154598774 136265921 582384259 284860834 373919792 687386873 736622961 705446088 197253879 476320330 409835299 342930458 599134822 746468596 896871415 466319376 603362672 625759708 904713937 664329041 622375554 557558319 385607922 397558559 57734528 488864791 177204762 317603407 851845208 583971275 207473626 219272901 967184676 960586836 668483072 387792043 860634072 104001880 804774700 706675535 8353750 29110168 788348291 83786765 921523159 501098381 659687808 502958768 448699406 270680665 947321641 971679179 244556516 90112552 570851700 651623262 269801039 610828613 939873671 964346718 691298612 710378063 767813630 320317450 578016065 7498247 67377091 388524568 72188431 938343295 920429789 669785115 438601403 305473732 353461544 27989638 95767293 16310493 430564951 760078196 975819625 729233280 520191185 196933798 398011855 211060104 54319260 148692326 171399891 935191919 351462137 748787950 846173083 744126833 887137625 901788323 623315705 981082178 130917933 655151512 860961515 566338816 941930575 534313254 372165346 164414425 873132118 931124847 950694456 236137601 798043466 646122089 988793658 779650593 44826366 570611978 281658802 672418040 993673092 155890276 927911161 104518338 377087079 72198754 217072345 895501579 707004023 352973331 262433852 69374776 895643767 523077841 288649147 597104297 702128697 838073790 719683025 190151930 361027116 32743161 308318685 947969378 874881524 669431009 350822873 6650360 129649737 871827371 587295145 31881054 92329870 797028046 647830637 620147253 286432728 346672282 832995564 169065299 819184922 64494929 415977098 593733714 555607822 49091084 559889018 944969561 485126638 299603121 400220575 776935429 960635400 290047652 180107586 204350258 986008099 917444847 549264679 842023622 556370217 583404575 366132900 644413360 290144708 708948555 715017792 894221816 341645057 476492452 703971791 487888553 516132779 406538826 276689056 252019828 884195470 454040435 918929797 240554906 968498373 899657777 724611908 57757233 653670559 15202108 453793162 474108845 584802646 590999621 51674232 967530927 51123191 445662633 108995000 464621035 164972081 793693926 372726845 713119757 792704971 781694876 481117229 240448585 614302165 543174502 27151396 538962389 819749970 569237041 713674520 797392550 385252947 394008144 280368329 230475111 748951327 488171592 886119525 177871837 599443508 7209020 842752255 1631416 729252885 407376757 590940624 428353614 157202806 216259790 905850587 595919099 542855878 447487542 312752192 431672923 681465967 989865706 669629399 977341391 616249404 743157739 384120966 211340921 675929232 847555851 484880709 611679016 468691455 787944957 225685102 583095916 916360361 432239041 47003844 416488990 836788005 963102040 534299776 917259597 56233739 998691791 146973832 690372914 91205011 697890230 961462354 938648219 580595785 244177323 222290552 422319386 383554515 139523038 636003034 577011 539190115 174242728 111291416 560187892 351800196 931255610 230767620 47725899 259183155 864584198 963966288 112552087 427934174 230299426 632992854 300712146 520137875 681361279 103962708 452001747 38209101 416321620 666197891 804944853 512247198 865379689 537539587 896574347 21445055 808353010 387860876 972206447 683818923 128207412 762466799 998101144 983272646 885729393 126299147 683737190 660142133 735335809 325158443 265582786 590346251 557445873 802578 195490162 571544367 747969411 432080871 850533570 167236667 133805950 475021098 136281643 401948245 536488241 24518702 660475885 217540194 827085800 114758700 614808566 654925809 764594279 140729135 264090684 19855794 363415516 227262777 819574813 273241462 667506611 280362029 192116586 221313656 929291777 320775345 993837239 226971323 556568286 702449675 781326168 997433790 952183857 243698862 737590952 815125332 615571520 943090595 235856523 466391247 829903665 836837803 251396923 81189670 522848890 713248577 533502525 828404330 576570284 573895517 790170979 767091773 304630080 885060609 894107408 610798309 793161801 611497106 269974216 255018187 815131514 879053499 229575662 906090014 773314496 601819374 226580124 36326353 185700174 157246562 417387806 425608004 982937584 614942416 273605692 514853859 361043865 479852649 33948864 84310883 559099308 155560723 736702360 761295519 11239477 63425235 242646185 765735955 243481288 563788681 173955208 338924090 64313801 965481908 578454148 245692390 157800118 475424568 649580596 216046469 449038350 681771532 981891206 654018974 906473102 581772582 543493490 198743070 38215681 786818818 881132711 918408579 561867625 854778793 204347093 2383780 155451162 138080117 541157668 245580407 560780312 657912164 151266400 661533749 450115768 446271190 278380582 351162663 22446604 470566800 702597589 971620285 882436592 449745531 734580103 48157067 522379137 856687365 386432458 442880136 659811324 41988457 135646022 502801626 490066482 508397368 940028049 600071350 265555663 154646185 5451562 528648065 195033531 360143294 448049151 175240096 513444187 963559835 721012402 576741699 378471280 761847667 447521564 202379660 609698265 523434251 610980572 223625711 872725608 684234793 903424294 739682996 763953220 853135968 264016378 297193644 111359098 603180566 291975464 849257095 554044447 635708279 861146185 874333851 209015115 379949438 8129727 524987894 649806733 432580114 526930287 363760392 479750020 58752661 212756709 198843272 177672862 404247055 505535575 38977733 16744518 186105536 398860614 599796582 299812295 40214245 534501240 511451090 859508322 124670213 78517345 704756599 797278342 987539561 438548482 555945626 926855472 355917736 541405582 9399369 677029358 355709597 694442819 319385759 578891100 264760846 750079881 11403867 753636999 507128602 639015083 598216493 323684414 570444740 31278179 678969242 719678001 799658771 574517160 20929887 35251163 802419348 979585295 129873774 249086615 118627413 948859614 133256135 863697139 47007901 388796266 390818597 679364245 333141394 521476451 423559845 397889208 698089626 138056130 163963955 116509352 145570533 735346371 850691807 89717765 820583031 594238257 746025120 499872082 963390001 224373625 893428035 676121861 643665881 779980244 184268525 561327841 566032544 314945191 503222864 356017540 87265405 686502279 920018335 328621289 541556801 668094522 951125090 336276943 959846848 786808011 759413253 30635415 539072636 224275886 488314729 114709239 326717183 839273185 907135865 365061163 400813363 580281727 160695697 672236637 729843826 230583 637112540 533904234 73387896 678715456 531729114 716872715 962651345 793607293 70370118 196414808 109855493 355823766 945819747 266620154 909808470 778136448 837055103 731067997 83119177 113902950 302769145 739898840 244689544 927802237 278909929 885167812 105176217 33794249 603711914 924521348 391125771 898737405 780868473 964771450 762770232 558148926 876822544 186667664 68817709 120870564 591527653 490708350 314683389 544575827 863702075 112581881 573504247 13256856 848034112 170476861 54323402 429055509 949240585 401869375 466963313 139573423 757352734 283549443 150040517 626068077 376498809 316184261 978890142 61301015 450315973 471569225 142195450 384617216 584407860 777743249 485402140 3761477 642713220 398208184 746335170 961399019 223991818 266871123 370670965 733690431 176351166 997257025 889298379 976050344 46338095 623893151 289570556 742789797 632182598 980454497 796170618 958753413 439977940 531770158 741978795 238861395 818854392 647231940 409514444 876191567 352047720 851486711 617606276 743162155 736472062 43466691 940275854 438456663 765915841 168373580 528621571 418012097 435669086 364697424 997924430 825170384 804832341 534378348 256833724 904911913 278971238 171663054 83574167 884567995 602887693 377842338 877862383 886281416 533088457 481740889 735743820 839989739 824902652 388729039 331335201 197486796 552530230 756561002 9442526 793779752 52391205 243100559 529957818 456351472 319488528 341744573 713116759 579841550 937365986 788483751 884641942 316758303 812576968 378126800 97312041 789600399 95404568 15065260 512151294 639919496 411588871 709479876 813563281 153729228 550343905 420708237 796313646 783848247 503246689 326380126 17155649 47738653 917500280 117368070 642012436 272917419 410925945 849329772 518105650 22915927 870545218 193123097 936323445 401762778 587504890 289939015 472216752 468599797 900655842 999722496 208427449 527047913 873345080 230351475 254232668 924108204 121808282 314133079 381271330 730154398 611357051 670251149 847234392 593529325 718390297 683381688 433914810 7174034 479345357 524891252 838047775 204521888 465437407 303434624 503058518 130135939 623961324 201734823 953441774 319375044 685507206 182490102 929830060 605208891 592742462 115204379 819625316 533436331 181881626 488104233 74938422 635953719 162143348 324179192 428297594 809298647 162241129 37533126 205472125 912552568 54801825 893021090 319980457 421111133 46176623 438238096 926868995 211763798 869079928 687696580 506289060 840584844 649804961 192319283 872916576 971165765 584481291 27024710 259720568 304783436 936290058 682123358 188230707 947751926 834628644 332235464 559498933 925875340 903718131 839260541 287697699 916335658 894784821 205836641 105320157 752351295 796086521 69417513 696676136 406840594 741638341 598643934 242888978 90283068 653674317 942403052 889301569 24706412 105457822 52733791 89268998 138320677 855085564 743878408 794060306 399190681 405232400 553633588 11522268 590677505 407397265 699802776 104886215 822973574 879123209 221514604 896040762 596121139 822947312 476790509 323826611 313418025 547066153 618947167 278680864 486194049 235064033 588087771 134833139 462252546 910566994 507350952 606041064 120247308 128790552 845877322 134530787 60935860 131220818 597522294 912239765 397235992 295572989 198440693 284224807 442253399 331278444 430249602 567289662 564040885 982472382 224635671 230268953 707945821 222929591 841394822 925374873 697659253 260377904 856981436 497313025 498862359 497707762 2923067 964627244 592814936 56094466 986472832 178946991 319765320 321538502 995912633 98537813 158188327 134111093 51211553 694517836 332182704 990778290 375563370 584844724 418554689 206402087 534266975 431928153 361935642 399898109 830079056 643834198 248380973 128394347 591302356 15494964 666630126 843252517 373388112 122842479 206150690 56163717 800320446 466075383 353163595 484183602 257899859 802241195 762304700 587296554 428617206 156778867 767409534 731122876 739405468 771359887 17605797 799885912 726661306 640010576 206502000 658657793 648627350 478340943 319793623 364329769 528330156 922765196 545552276 109946271 843757737 673251466 439629831 373438783 9449544 76570310 742336378 630260357 588045914 85877945 781264395 862693914 379320098 168339383 854309723 63400726 969605038 671842195 144843139 566366318 941832190 677249340 454982854 418628577 761045081 175593189 12991686 909186132 757039564 992255818 311247405 966816116 712438914 685143436 156936942 505484730 804839647 563035269 220669977 49126904 472297744 250639025 35745246 831679623 680725067 980320920 95588395 671606996 699616766 101155547 413857460 352243436 458330600 743655875 193847678 556445794 672871334 826445069 76258758 777244137 957108606 825554464 582401956 33837570 162907144 877530921 633631602 665357511 485267628 605748976 740973731 485982149 613208873 459807819 55475225 942913008 883905812 90939204 959917116 889889391 713732478 707476490 3826088 292975294 386717723 969080825 711783431 895803737 938795319 3327963 694868095 959433148 359598203 284461177 286945651 219354050 48898951 445834323 647006432 346723910 373637230 725651138 643038851 488192231 951423375 838443618 344346998 347380605 346420434 779552553 144461726 470888571 62640221 363310252 337539183 182804933 850271384 704154747 918153060 797454689 384865887 506319682 816609567 92444942 979074059 606073473 812240508 675793763 988018341 422365094 27005784 648850607 87383287 919030311 677125125 195180875 454214300 375006238 468039981 81637309 501106790 840489653 986080568 811200979 500959535 556054955 950573360 844670124 59472425 928510424 889640664 96246320 364252442 474035577 772137315 258947747 345804536 584308719 597868405 473824625 97421538 404847634 118691267 591884678 144667012 780469058 663139465 919074026 614511633 789938086 118932202 327047010 588721816 300328936 373265847 257693512 604719562 601787529 736299181 819863949 839010456 565428686 304622827 693349818 483350608 909303118 404794748 155619336 986737205 976709055 566226944 834242787 89418075 249015678 771159787 99193171 692692798 995175822 258779018 335150654 213043978 182077523 749922145 177730064 912618349 422181493 668564189 91703047 807291617 295681786 670737288 757134921 942778137 246979151 174613369 872056314 272842366 334579069 224297880 766994911 989294745 968219230 880870650 919272892 737432372 83995226 411991783 108704450 305070812 593445094 646428106 215649474 965493227 887421465 770839418 384003805 386325916 779249702 614183213 271408828 37187788 982689107 764081945 62506408 140860655 92608071 285041048 390483300 618836088 79691939 418085964 108814292 718033226 771371034 236212711 522183176 98259340 386872340 455981911 663357949 223581099 808820215 182154330 75873612 896055600 774283837 655581122 670843265 781872046 599114626 947420534 67773489 2071421 999899731 208924238 369868826 920738154 602319412 400155944 447954559 941013775 125539393 684381855 21546482 668937414 388211640 389894109 802499753 408420173 710769332 670914740 34541647 770400839 518361641 139435195 585201897 882790901 238035316 722970624 539097707 867000504 889410602 400922803 712409350 137133510 992622003 360033136 219961301 128062913 304951198 503896148 58292681 54531141 29710912 772656415 232987134 361121199 87450448 211658097 690856822 741235058 382552133 25629708 61813770 63276464 903050252 553174350 29824759 61814393 317682395 532458075 984032287 966489475 851600466 386844105 638789530 702976801 78974674 318861462 570443822 847314668 576949280 986605819 956376323 796790973 392536904 609430879 710736902 986629843 344500770 890052012 160882651 815612557 745736333 729473099 791426295 65078169 583519411 926802544 285009981 48789294 193151789 919325626 455265501 483604165 744218600 963765340 493201609 61664997 397523768 450167088 954150335 875140846 655665729 357332865 307038352 942419323 794859079 28288444 104099348 371365204 805640542 31557359 940702638 703815571 626187640 400443666 353659669 83388233 709684138 457961025 611920502 589686579 955168882 804808110 601319809 351458914 116771332 821844599 661968101 796848102 448009960 865653644 545909566 658957538 47644341 267994399 893912136 983807968 67948787 948949496 529245108 92286648 744347468 520562191 281243986 66421589 750088959 697901008 491353673 665419658 581144583 17020929 484010871 837039193 546538022 199349958 642530759 58016725 318807208 239773153 277239975 830039577 609579138 311190836 153459441 910502606 226541260 341553969 59027719 612751148 944474956 735405548 697882418 970769484 982610999 836790599 937456248 836632669 453103822 189788612 194413301 71851447 588807856 413927487 509543313 519777566 573854212 300970353 546305636 552148573 384630730 573642311 315063932 387349011 822097210 599975902 958887656 405880580 918536919 284205902 990625638 262973590 530748150 242156067 398452154 48846047 192817726 202036905 278628073 722393173 588614545 975592436 800644244 870305449 864187667 325587220 766846274 903998510 881995869 714511552 67318703 524460402 159000213 387175799 422705577 57001350 810046302 792520933 294999179 947585557 183913928 565472646 600745003 670948995 325798474 112093871 344063380 414604533 82443570 473565163 783799838 158973136 109388994 680144436 41028445 908495302 789590510 506619003 479203957 864415627 557328081 627198565 754335819 448147086 698790900 495021297 547964463 728639368 812810245 37958748 38034617 335934194 244292945 675035799 410418408 688942327 790734370 218773696 887673450 197058469 685611293 827817438 352576678 594730928 761768311 401111491 9417558 111050876 879036655 488321324 769354027 727989297 132405772 302207703 476558423 844483323 621480141 156907021 814269946 160561674 27865481 73989616 230654100 815837848 571268330 283956687 920677593 724868066 297101101 472221987 245905760 761992891 373047367 534610097 432995398 64310276 875680089 388630736 288177663 435623511 81403167 297063930 617569985 514155135 960192247 115737189 290078896 324054495 482626348 934143347 854084950 992644524 647231387 463295579 392151251 425441525 518353351 471303546 835914544 510505161 351362238 450261915 184101469 715412251 303913724 716505995 132871151 123755177 256567893 170196788 625943560 535436809 187934117 668781719 1921565 359392857 34241758 892526906 348648045 95029732 780003641 656249612 27102202 166036346 226375014 827778730 7600529 536807797 112069142 528714177 231680481 606948625 743357501 705303617 882248878 953550732 177332077 748174508 478327061 298266618 202682023 446455756 804675865 360126610 902354097 625886643 610561184 392172960 855544959 41156584 487207469 923300565 572064928 406234974 321122688 944282188 211921532 722724488 974853903 918319954 566533022 823267537 577320748 646896704 574033746 67939021 910087118 838815777 136339696 692822402 510119387 957991515 516950058 142222465 543029348 87773535 827470425 518879984 117740690 359932376 475881397 960273678 902001099 703772224 125085207 445994069 787592408 192208749 407275931 442881407 634013116 466286417 457267655 9142558 49632534 257215414 13296026 245371695 654598360 381021437 442627243 424038323 654547084 267530558 463398134 112646252 286944975 138679578 290979088 688202164 900323092 955889726 228946647 344854369 43467240 142786398 14926203 260057801 402972853 152175049 809442912 194739661 223317154 662160514 455525697 384927327 76772563 250454289 233062155 581157912 536510840 897823946 329048672 24429010 742296861 596718774 90496953 671995997 300168372 433169073 950732870 920351751 531468634 170187177 402067335 11585815 133623980 840293489 539837625 395777656 24378645 829899059 198216531 995370352 48510067 115086732 644910137 832545799 588953882 760512673 389455775 776554827 285141542 439502179 751571151 609107314 562862710 247642037 434411370 31650234 158070029 727772960 825837723 138833042 173752343 299639538 29698286 53522773 445293093 565752910 309221953 857235259 505467490 72862971 382146659 392132310 524872110 832559674 589707524 774653297 581076927 213692231 662714941 251009373 692946762 631498015 954777629 239132829 715215600 343136204 899281075 780985459 739731246 616639037 953138402 106722278 185213877 385097515 180323628 197962687 615740162 545470567 787101653 948882977 559244749 499066741 26272496 834818061 559787301 679412297 219488438 460883815 849270583 914203965 853087292 972797593 238148534 946904900 290109987 878518726 133817731 740480233 643820518 917096261 361836002 193985348 733429884 872104654 380983549 500671423 566464261 145327196 972673041 493249675 777638188 38819144 911907156 906346996 257025546 258623329 601814061 266979481 599460989 443719039 309130885 189149865 709427523 926417844 910757066 689599264 433714873 678844830 236311507 916842266 131521315 132172602 335749410 260265006 261600778 666555835 64635775 688192768 836193908 833696865 188665111 727633216 437862998 41559025 435281157 623581612 828669848 785284957 834057222 868579466 520354200 871801139 742626130 194027776 580386410 244958754 649361091 603189759 390492846 466638140 674326568 359721386 33098295 965267451 930461816 214720074 855214149 851084977 557023050 605393756 82339978 695397524 922093312 773872474 523069591 471146964 607159729 974506625 564488605 480417620 496295420 282643885 296027988 906217855 600163216 483011139 180580988 928488113 765310893 530992478 327290226 226528943 963977368 343904559 610128922 982083342 930266839 210061671 500073617 362451545 135694750 288433009 726891782 715998930 768593495 231712993 799253197 831746930 353075992 958601708 871215240 416491434 427696735 493418247 942568230 786762354 671248683 441502039 542554643 69538305 114339627 543697492 582956366 522195745 870628590 419228533 212069032 289491958 437924712 244328152 330006603 535067893 101167518 156522398 927304648 129676350 82391995 490480629 301857220 366714492 527487804 781868842 880454495 391912265 690838057 908135162 836416903 154527440 123588087 912967804 591476906 175301326 885082668 230871294 28274898 214969605 916506245 783654172 998281255 419919833 182664555 852304434 46490522 656055261 351933754 107789888 93225912 25717059 203084267 589777317 410557759 894106392 938999269 223520120 8386994 446104026 451126376 44782854 560632359 483216292 372091395 799659859 686908779 479334690 790422380 433956715 464997591 244202422 880175147 534633033 173585754 840300512 457758184 548517928 926072607 293259896 67514478 787629035 83721637 109764186 795656777 35677715 966657158 198697231 630465999 530494152 14807732 296604761 343595554 682592637 248714763 841594755 34926295 317648872 405128587 751537168 396583086 243803415 55364998 821615437 817411893 923682915 39043289 399901511 624152755 88676011 727168993 404270065 623167510 373040165 558527895 509441832 555655072 498107862 745262472 874948266 545470499 619428238 600278387 76939546 187160057 655458735 992883438 785442809 863561165 154824130 442947162 211444792 515703482 910038081 224831808 954516342 531938956 95652890 198414656 926708441 147590848 999361073 378596275 466857262 690605647 829883784 491410094 193934589 789528757 478367353 264808306 111409008 101571843 699162280 134906278 382931577 776922037 146213168 19146981 221921979 649729958 131200943 786266528 351284019 562249888 843493394 41427386 464215776 354558073 669116303 57463995 955593884 937444825 696313829 622015968 242824285 56315572 81143094 897956292 822389712 766994270 279246965 891268736 627054738 862908922 917678811 299142044 526306394 467828388 515378436 890675597 382757006 442678138 488376594 238422449 676990527 446101291 619874429 457844214 869298409 506012854 989698702 241472599 419254925 959660370 980093668 194357893 664711574 806717712 740807091 944461115 394498703 23554200 712160344 192856160 832090327 139221597 601274760 595086148 118812819 51229103 584228123 240722700 227231049 901853608 416986069 960723329 448980875 437625862 704837408 882615333 420466515 922759971 503931161 828832484 116991690 162849882 682072182 876796157 62335543 511318282 312619312 570086549 665077984 670110494 301245488 86991739 7690491 499297653 443364175 59018779 649770130 449052493 846732917 459481797 889500384 750033391 245229651 633961400 954285701 49330700 372151912 510424723 44110635 64371683 309095820 515278603 175053699 688946696 271444576 171695634 554819765 795320082 595524998 935491751 152078260 368356558 393245177 355624409 620779207 423041647 524085117 385118894 557882565 25425653 914578649 788301596 716703092 510964375 301638544 677919809 481227669 960609783 100940989 773647277 297900847 213878778 937895314 587501990 693475013 150991786 991376089 390759342 417595522 620313596 525917450 811376599 964272936 667578399 621422784 546532726 458233274 495584053 730690456 763148988 624893698 121705500 969468226 735278540 955449353 498531157 796991933 574897680 253835057 375777076 592699522 104781586 938492223 646194691 1608430 458703126 105714333 555706096 468052357 874980650 646426304 414156996 128332120 111899058 334848682 814972385 13018708 976270238 748161497 817598207 201802987 427385191 838015937 326719542 561060076 550567263 637330157 311452584 179242751 981727302 185340989 638736626 340779954 967112823 927860548 60383346 122852183 225070046 523366885 304324270 249292521 460212532 729964898 748714373 310210860 999507094 985395807 939362405 511936158 102276550 458425221 206282599 807092410 445893599 426248608 890222414 861320287 16738994 980425502 696028402 320365254 624692583 874383476 855208375 702606799 602238033 344717686 446007470 981989528 481176064 898744380 674701558 352410802 694373701 930409844 37565434 724140922 627072462 561261656 802893206 275063311 705552160 298289787 62810112 352967492 492559515 922063720 435060151 564390803 335354977 838370994 207110770 252033050 270960919 803253599 926291277 4363392 45403125 549081650 103039623 876568842 110028455 254129273 490363333 464123058 278763688 826260619 548487703 27579980 204892974 117934488 429030056 616117255 409345106 498857151 603506681 818707680 732347329 579235567 386648078 56165925 406350810 986702208 753976974 11448957 13729333 469166114 916902655 459313514 912243346 860340617 891312704 722967018 454889717 141668270 77929900 471277109 419738079 110824498 827794166 955761974 980669443 492749893 742202432 569998556 418537620 225874055 405197820 85006439 480182849 311785521 980222689 886155121 739845004 618148709 181694798 339526293 515738086 585795426 276000172 751510249 447662452 950260930 830068516 958953877 70584801 707866959 67438325 846120314 353139330 391050709 929145610 830998260 215891546 621652190 277015949 514231409 20034155 31607011 229629595 574334469 196764970 915870901 680392669 788809177 427046737 849075828 304139851 509434761 240400891 289588136 880924239 921956669 771724704 556233287 377194149 272369005 357253770 944929288 980850071 185962998 247950898 765561654 915717 224150905 271941459 809000236 674639365 608336724 217932526 526242150 936576992 482885450 196820664 90009890 228731290 419624721 671993717 264705790 849996860 998392070 914636374 700121174 898403226 729791372 744422275 741720306 742545025 562101726 593820805 725085106 852054463 176680876 90536049 739896313 49178611 48754853 207257064 415074746 715302147 562531595 132643700 159655336 814357421 231565764 443988647 35083622 541191076 92765897 815530940 167086280 960942806 86028380 574005736 173992459 755931009 607945127 390149237 14144990 332291566 544155613 120851518 63629327 291653210 632955560 385561538 326653858 611570332 416236985 524008490 3435687 16440768 925474241 938942686 766633729 757071542 41503026 343714079 819200113 332237198 459455333 694332027 274324153 533520656 547268292 141441160 965490047 369500665 438052999 117446729 273033325 895136621 564329571 655224472 217456526 629205675 480967030 740369538 356606430 602339852 393297613 306849104 718814114 961649891 106902770 217449208 550787120 537102322 244037565 590695439 323102690 653981186 555395996 203353788 582357711 931792101 438912931 576649386 929327260 54151595 134456955 654374347 145435474 358283300 437264989 966266445 352371357 285181222 447483467 88541240 657065727 419924969 813440295 40087782 86494739 906372511 946453723 347075538 840657746 104573932 286984352 863836137 758978351 908067266 163833068 961550919 892298636 100034672 648319802 775550401 839493887 999030066 424831440 478288976 835748685 455740679 495409536 157549219 752266516 154427506 2595416 506367455 220149956 692851493 592853445 191155776 634960380 887113204 107348141 39789100 241509592 232756945 732076392 877394822 280257466 659971965 682201342 897774735 522892914 38468055 847150705 378187802 620165184 739438381 556654156 592808208 295986226 898631729 202073400 202189529 92361326 503148520 797105978 961651313 370824968 250985460 425998644 529437088 931794285 610124285 205263968 566564403 634793113 185479445 369432007 280010687 3689556 595088031 684623394 281238046 60944268 859624155 670487461 300945688 456778344 219644469 621626894 264945535 634776496 377109226 638654879 152818883 507985739 369617551 875169680 790912307 888118035 759289030 772136839 755384991 966231402 661357645 681791844 862401912 782414722 164015315 286800324 711479568 54292100 972520238 463492161 672058367 6181845 22905248 760703671 340427235 411257394 360498454 352532427 158571640 62704585 833655196 961097008 716123151 503692345 70052494 611616557 945966257 913690186 253236187 854010850 762995710 411281902 935687711 520680418 832635376 142051013 857003599 959399991 297201969 912080827 867483187 602759216 761272954 299034585 115942328 904406177 83137947 207686142 484650763 4658613 152353183 473088340 807378397 809159084 777933106 13718203 689381877 689838408 713320316 590569614 939964633 95031373 175407024 285771384 984233712 833786400 626299913 654321217 111755920 388995934 614318654 141608728 11737590 512804442 411303466 654127468 381952463 67635265 415249105 213651595 191284649 281641631 940649156 536476364 47369671 919629966 623160481 670031473 559969788 8217841 119919964 769603890 309536192 50318446 143863121 855876211 627000902 424654936 80692349 904322192 924260034 582335991 423134193 357231097 39098700 625032380 327300750 87370854 723498927 3586574 77212295 208906510 958937805 854507313 424923723 432899909 85095840 831581316 805727134 293337086 886952611 699807575 843215172 75245736 1671464 943090137 251362393 829538728 897111999 150679519 482124914 192151228 899540279 17018612 425425436 982032229 231612756 874244195 425122997 248655618 402974023 616715923 812990402 844197879 325540188 802951453 937831881 240152155 581652630 533885642 583764756 601312687 217295639 162627003 517683460 134802630 855595822 144343318 996669482 998749109 953206952 711681067 126207828 749710874 505996882 161835159 114891964 2128644 767891567 634023988 719974432 24494834 478934125 885680971 231356432 567920510 907536148 87239726 850571202 294345835 949125144 79634558 287994384 722498462 492475843 678399474 926473739 564968288 710323436 639462400 444295384 534798920 129328595 15317950 625219541 753564136 605672789 225871918 204938556 948669169 452152179 159585181 594314575 369810209 310776264 393782198 63568382 49518421 386065655 147363309 226555845 958860508 492196827 981749128 467480782 985475352 904016192 264636511 217790096 226208982 87190839 453493109 865387808 726564945 897231184 168244802 821157420 891688577 798775200 375804082 736832555 761158698 482439325 37210731 614950456 964973289 961454904 553260508 74388456 868412517 947343296 631150606 99655705 887209594 946339546 642523573 377253572 681368226 205684248 442478188 449012291 329171335 651945919 777350336 916245447 193845450 994089558 941724019 1448739 960811576 502584308 949915005 485766653 321657629 794370516 84333035 183286555 107087381 342221386 698318244 87377585 318545230 308089827 8783129 157759968 252682896 677747863 877644647 688569847 420882469 50411639 152356444 910807631 707539117 732153798 877627895 50556668 902411390 232427478 306463830 706313142 387608684 952505948 513651743 277701361 149216201 448273251 15228611 680501797 129418449 963566919 882793987 552578920 210679902 857083902 8240429 953159183 62819590 4006804 17740688 167977651 143386596 422679880 490763537 759703700 959356845 118700250 571310080 965835241 589775629 136091864 441820873 279454813 523064387 154399208 537983579 468498914 479383435 563680909 520344048 83215791 767503871 733363510 828996825 388054422 78219953 846322695 92428382 333218021 674859364 601067934 417102261 209394851 294361866 336414343 340606910 420001952 601254676 191495937 702553480 926839664 753465565 66523005 111559976 386514640 273042498 121723784 264230792 484041531 337171274 612527548 789521351 555832645 289234852 154591369 49321391 97190334 436667674 322875628 796102220 802372959 353923310 471748692 591242696 245843697 315133375 383739372 589694369 799328515 571006967 928702629 615532092 352772623 744327688 571022968 168368226 750981437 140118038 88490917 75286242 429926822 121475742 238289133 399364299 93324768 897503610 273533390 778525978 160706789 268764402 802077665 303677173 762593226 708980722 480405977 551519680 285191163 33296903 721551581 910094768 474055543 592399091 207749675 244879778 915169999 742973316 598807073 883169622 222181762 427470860 974063954 908258370 29000559 878063303 754611327 449737072 740425236 290652091 999414569 911908302 319751619 809792963 141661156 13609347 259133450 668047131 40749577 668493595 243284774 703332464 858517798 114740607 286941307 578456206 551990764 695711199 485405818 988584565 584012111 954673554 75299912 544529150 770144817 308425100 353016981 294990570 454394969 44213031 972054063 767733328 590739709 532972429 475485076 263354237 993843793 59869641 540293771 231450870 956272772 529955512 592332944 811703260 212918307 509318656 37783436 775505779 242080723 976902733 593375525 201057170 60472326 158407812 463253665 826200150 846898643 978957830 501004251 611055696 913124500 593896103 929456816 987120294 171780226 726958420 537424265 605091211 299313076 184637398 148687327 174536301 581507547 651543869 888977295 722479223 659117941 112199248 272075636 35915656 834293043 786230480 174973803 763677692 555703423 590360375 979864001 393120129 536481498 280774603 927903777 801081966 648371840 346789266 570555607 165304796 184147822 284874705 1380931 148223934 76044711 992106064 77104675 820248917 600986369 988537932 912925327 509033085 191088518 805230522 273767812 321566935 384135393 323022663 28675990 482942800 390565682 330518946 31052961 602331554 736922749 105979460 76942943 257446675 941406468 633746650 341499180 557793099 590674695 75193010 946261124 283260960 986408709 975072177 615760348 954118098 395898826 227196219 313636082 531468496 606852376 624774552 269263380 906587007 479223579 890726355 914010660 850843374 443000552 973819847 369736449 24118876 741911439 338203970 416408443 23635335 133334666 329580538 76760882 511042272 788451449 241941974 240485646 112070438 253025092 166673833 426257483 998783519 982868680 735445899 76436173 830515643 426625110 911848956 33625983 537826788 190251417 957811106 609242240 626695779 813313904 845995890 940768157 796881230 260156959 210848150 888617920 788363204 559320702 886718549 854249687 245882869 601552447 849169007 773896935 463192912 812753186 966185086 194437341 430869231 868374281 79057843 5150371 155481102 387945102 21877313 701347307 543309469 310210818 945271930 303963666 181498856 409307237 874776489 904219298 204596093 221512848 954646979 740841535 44607968 33939259 39705062 218435115 703568144 682785133 185656138 347465680 680061102 808282400 829195603 138036191 719471697 539459718 676547158 374797054 119971239 227795674 152564725 58828404 945481836 814756728 673390703 437363432 760562061 232918979 903508547 452629341 162474609 294651351 808188616 792470407 23005799 913406813 828864734 450083599 788549223 444003704 953340505 3140599 63364869 991010936 94530078 79656013 291907404 439713956 970246878 498640558 120104769 661430089 576641698 888753024 466429241 750661589 168752777 378465638 49550144 627598700 164420617 602590621 318070568 881178810 677861423 195320166 789169247 345984654 613179933 154172604 163737943 968166167 677663796 439230799 701369715 589461285 916836567 516767232 253123553 804730336 681469911 498558848 986143856 388809649 445855998 486887783 760866499 897969864 116836621 483723028 671690658 952631236 131074983 506360453 742250986 575779792 499116444 652953447 543382407 592965388 881526405 351311269 627005740 982743765 412884107 10950182 441589869 934944788 542259947 957525445 664257011 487131749 77088277 166378644 701999125 644365577 455921492 618624983 65630372 285515578 398164231 849983083 979327436 617408401 141458056 961941585 130379964 10202346 413729410 837366037 919367896 577356662 740267834 995055412 122493219 575168609 718744184 797001273 544137643 898482482 780088997 347785172 879483526 369723727 525279889 627102216 218773517 819096109 52098231 603026491 977075608 965237889 816379602 893100533 995682008 918657776 853899109 458820972 113144504 369191230 913013922 396509750 131918147 781692376 357598948 697369195 406552095 382589351 19993139 220597973 113611608 251843403 912412850 437276267 911844853 345993409 862442961 608248086 144282739 845767386 308649181 374809596 264775986 169949934 648045658 731937812 838209458 449224382 935247547 451309980 337790230 354470772 365446999 667280457 789477976 521044723 479474884 498956582 876426527 226931216 430201460 411568426 977676832 510187771 534908460 553499545 710119711 988181376 374977048 660029151 563729629 871509924 939672766 148289295 158033521 391681279 977453988 174986338 559039124 381467177 847727775 101131231 567030274 694856075 546386993 471075138 919066850 27644990 367964050 266851220 374616969 441569655 879587775 815430196 828099965 669664347 330436274 528726220 278312978 330318151 122962800 585339497 559641322 181431200 502959403 130823939 517695739 577741996 813216319 644986677 771490649 305365273 571182831 758706678 106484468 788061458 412827249 624245253 559846117 580163133 504818982 485569747 904510985 275416597 841177235 948284979 104826327 68085398 982723602 985023825 380655514 817481186 879423650 153376744 410239291 254902206 290567560 423303566 707690691 53801599 469261975 671002528 712449862 313507524 162626514 872920968 691522908 817291039 767023640 483909939 287210415 554017040 877871868 78431120 802550133 164520643 667342345 919270809 156674580 68282417 987208819 753256635 829532190 180763084 503582274 842783058 964517861 418898859 327095344 841216229 873095069 870507864 380763458 778703375 592379662 406950938 81012434 907108128 234076676 202640943 274918956 162922374 880161935 133070569 841061330 804267843 943598867 842156004 592831016 468065828 836383046 211201998 732457167 696723927 689158656 852578720 112075407 631778394 678198217 322539744 55069324 146314266 519131148 444693330 10394932 666011382 163318811 963141893 686138726 34667183 245752970 552066453 81104362 98432469 364383379 30455638 815082025 597796577 942299971 703267642 213401835 634626331 298290282 532491842 368242710 925263024 924398276 581825503 690545684 54596449 89338883 572938536 962523383 163622303 281985512 145589701 445634630 427261769 983807373 974161117 426113137 818368970 665605814 526346224 746370878 14628747 872523218 90433688 450219437 921447590 94993426 218167200 357569563 91134976 573969561 25734609 741103114 528239736 669105436 548190369 579015722 615516407 327275919 860330087 345715239 664343098 781900646 823884138 596624425 825102867 573088339 340656434 595543558 246767741 758437533 155546899 950728830 962887835 302591694 375929716 982688340 287390469 415188007 670158100 988861209 279681123 167691775 779551347 882839989 59073883 307150333 765515170 715708051 348145354 826820193 154265728 169022837 916667670 143094833 256825000 207116986 432626082 712960848 565341957 977433879 583291221 410653379 895131680 97521518 385567994 493763864 573468989 113154776 49608625 193426991 66516074 382036282 870506250 292339626 681610457 825969361 800757643 896765440 805341584 882578378 927038647 921475064 996381013 208855128 703794905 347409937 827380196 702069090 827935580 265736706 497513572 253572885 544102609 258921399 909538776 618169346 518634269 456153411 368003046 813553659 735612262 738252096 477324767 285814699 984672306 362295857 689136895 674432433 862271489 343152665 883620346 657873027 282645389 954421231 883965818 483007919 814562749 739451250 950169788 520541983 29058429 673323531 960008656 804932697 485209421 774981876 591875163 130654584 902333872 8099854 330109077 660164996 568279529 728352507 484681501 233616986 325083113 961851746 704154941 758264801 32471409 512177396 17652739 96957302 881608936 599407404 306951984 120275215 284508766 687382731 23970581 422492241 366915251 618956968 389943039 992406323 975717705 313073718 124541898 731916056 662503688 616247522 830484642 856178259 883873487 991830273 443193788 903900695 503226694 85996784 71587982 609208229 99339864 307842819 271896856 935888207 223509745 367168278 384756870 691694615 981777032 301159546 904048760 491497807 637687666 732706712 817133846 983534569 72615264 941042492 675694709 691048767 8291329 50725003 806637086 112718199 890081862 928215541 714122605 413747450 471789237 608602038 116539691 858961206 286110663 868560377 180960564 386504894 333569015 586653629 15998688 688471603 875284781 440856090 764297340 561776040 404447178 541238680 443573571 786807530 697313758 803465082 494155793 932137679 914328958 941814119 192037578 944556570 682273659 16168674 905827374 201094831 338946618 500339638 491420680 75830456 263567553 996963416 645939676 866514928 40675495 48159767 458307533 887832672 698772257 323549510 145167226 966697130 987143045 332286087 54484731 225678929 337866688 288307009 655538397 586142248 299206736 558271838 419325645 532779411 286878348 67972409 427733995 712818614 141090685 315487183 254787191 532031350 619924280 660278812 408130605 839181421 327828793 309024150 977599717 476928037 155187807 647082084 784885005 611000755 122273912 827704973 208641481 277326281 85178281 64271821 959357460 269982414 590498575 921042408 109366509 514992303 211392851 132748849 306190696 937272355 841936008 18158932 482339055 395821947 160422272 343856090 235770252 842896905 631665293 330971727 503330788 604238007 690577340 456212359 252456202 276320368 668701087 994700810 75006900 424349332 569151738 369047597 176674281 617453794 834367319 315104984 273777131 505700107 889453785 468800918 728123730 682143083 183598983 460309237 791756531 265957497 685037950 919935011 791001432 252504968 989893651 735491707 290718294 93917197 853340412 470441191 428488669 570777108 858027176 440160266 733918031 864754585 474902159 709291883 37415846 871742378 352069441 774201763 228164144 174071111 940547478 828554931 952018472 383228327 185495226 69157041 730462689 130758815 142724047 997971933 933032426 166434485 475864679 327906119 247130376 197327946 163284191 639102706 667492539 235931613 938249526 264678222 670294258 980930287 886850269 322311072 155084119 875577638 598349162 927731765 231122633 16029106 609962374 906064604 128849868 635693716 167853739 94714042 859071802 761912850 684839427 270108984 480667705 5560456 981430094 788379205 10399524 634002868 958166691 77542893 323457164 39329254 937492335 649117417 721640903 114048671 580335405 730212983 672860071 944527244 298227073 977458579 149453630 965265801 698378257 264041695 165372708 188390960 231493064 39623235 899154993 773149885 721312322 207853555 399612857 485382736 970799713 661282166 84292429 364216440 983578596 12640877 395600481 772488028 71759986 401135692 348197235 632109299 224051467 404861286 456094596 767297742 925168705 556622714 150624143 126073392 993145536 679079124 601612983 857672414 236518848 74555836 424419687 22826962 976477878 999855275 506844621 191230972 941594047 161798247 925052284 127810017 673008804 116934988 654262086 419592732 335820424 886300938 47171567 107390433 337436003 162809902 820539612 112977829 445234579 785510884 771022473 623423226 548052375 732094289 283786543 967518491 845266362 770565497 328865294 386500432 808082836 909073339 201204671 108858933 834469045 444737627 382768069 643082792 48636234 337509579 335309936 523326050 704687086 948600551 133429130 622694175 311939694 638692401 777129636 233546042 176668650 299658051 726041772 982254197 670589902 632788658 534393451 769217142 303658237 365706679 933636838 871493359 289494399 503012251 398692801 659238509 68356952 748525300 126566702 709974646 757264579 547401043 956982620 963805391 348217209 930961568 417939019 880281431 805404778 331019967 310936836 476665051 446411378 199344307 784217580 48715627 342534062 956895656 491445767 560945390 977911287 819077778 336526165 754645556 608232732 932088839 579041750 379465635 522534559 870130141 314303695 624215643 532178720 33974186 867341359 415604750 250005301 898372660 703102879 408414507 696603562 950196853 736772803 692872412 365156853 464507002 817109741 107204451 237825149 729639516 551369077 253106851 570443694 154170269 141544125 999502995 968716191 527706687 105743656 582336666 699101356 530742443 643654846 687972816 832414422 981924816 299540303 750913326 435960760 500529773 413013648 549548210 251537189 142997983 500048061 921694294 424079329 739200009 20409987 702881916 977715810 21235111 904187898 958913279 327081726 886555098 173300091 909957673 878118834 859219377 60264647 940937653 465921479 295586984 901100975 283329676 336519232 95869656 132577343 309095542 307245267 732737584 965740776 838749246 596350905 304918898 918083893 592647929 666441441 862591716 841392486 916427188 107525579 485416627 703865447 204307131 407746853 975984092 484493012 897767885 359102982 501651545 778026327 393750257 850357959 310218304 879123937 459490745 166410560 582521038 278200480 11213705 369155978 169290059 652825883 98150585 981745273 529364858 174759687 902224836 392471883 231971531 544939023 873050170 212864361 581404275 608123209 202442668 216276737 445400202 414603270 879860068 143515879 858479126 883042976 817697775 576228891 535084962 529283457 61289670 909921455 948054659 892056742 393893754 304708580 94824117 762954767 914602777 232291319 959595361 547764828 503765716 967253182 604589444 57934628 21526423 427509981 633774765 858364314 858980479 436360851 309902766 433824227 583332780 81700366 833154984 510970812 850115766 49217567 150464413 473388990 207497084 452161940 492374285 625403752 515640571 9039218 182899831 77666744 236548622 660663918 277337617 498971044 800049485 652630295 571768603 22026649 386273811 520159838 232553986 927155336 891814220 622886104 644579624 683325574 795915061 73548513 35699423 416179301 941533604 893431874 2207885 930994690 912723646 672034006 747862040 402250982 205731517 760845198 523295647 37965050 188088280 603540463 412725501 992395386 211319021 698816046 955179170 132209865 865500882 7497221 167784004 462077043 280289679 131490534 768293314 256664465 783984390 822367427 634782439 715613378 691874627 544429712 402768154 795687179 783047748 763654358 973224385 320442090 584858290 525541800 302618611 894204554 713769499 101799248 302484700 931924216 909924465 619022975 56703940 698866556 231684097 941997707 126125575 417345528 434296439 621689895 463103359 856486672 590491245 407696687 95997120 706118930 674022803 934227134 568569020 858758251 91917607 22904942 28078372 754553382 464846458 884739857 209192136 765163423 461800271 22820467 286064207 359743771 163984478 394171555 428953876 73809762 375311432 808798821 152488011 77966404 338734526 880739081 349919776 536114899 342387714 644918354 796135712 485204285 608991976 547705143 193503281 690386272 586967176 939827459 591195565 571010236 13152324 24793076 461093397 707006055 671199169 15539082 820605250 415606248 389342540 172140024 839048725 672613008 925600215 266634551 150381871 485232168 161252380 892193708 762599533 208775013 198904878 279389292 690462085 814245678 699673350 831427260 248746143 565271920 53493322 823281457 745947316 341926030 244295961 71518705 830866431 627512248 48149256 721187573 603340262 903232334 831005321 698316024 188438946 263012276 26565370 14130014 313239120 607230956 972060961 27827404 615160610 969166399 222462083 184534863 989863046 492547074 488976031 405431628 205964827 200142927 861913861 926670593 663427666 50940129 242406169 863799040 770745266 144945795 591114393 676186972 28887232 550571781 879893681 969193208 575238150 447144005 387917962 831947421 444862532 992630122 899819832 370084969 624146402 205835548 796491969 727190267 970947075 710007798 955421346 516177131 491979178 692820547 329710818 475717772 374884779 731259963 210983110 983681605 824646708 397008045 459454993 913165256 500049546 374119217 124108458 714919610 920816257 3539178 201941681 239693592 378060998 558580819 363901237 327119711 872367413 548234303 152892283 47253438 820330451 72694929 527339969 677125627 291710828 799192714 705794649 671107604 177099286 659197873 976259055 245437513 2409068 227390409 291011534 538291913 282513154 223873084 393473789 519075058 141622831 467933983 874515243 761451516 378567747 758002924 658553161 934377010 378936855 34885598 837099212 914681892 657621983 260019865 136997723 960153636 93593747 533054635 748106163 328217533 648556118 39209656 234302260 21620357 430740049 862042118 386892184 791516215 272026584 570241467 895539991 542159284 375410983 916861229 753901954 895808898 797238698 357124082 910075654 165337656 49864113 228470237 636918235 537681712 113224675 550251613 231900762 987007559 759773431 59258480 747647110 203532924 663468358 668907422 278766109 834409686 271011520 751099067 984262785 152591906 797541644 95912876 915446635 909517345 245412936 745127942 400136775 267961411 291709450 824496000 966231478 203421998 563337473 709721708 525342334 911546514 796941515 55138875 376286246 856335165 781970660 868789301 775374619 18272802 588688994 100160313 158807755 66162996 200980231 11393618 261537282 686915396 935739008 211997581 227668158 131302898 818179483 755679746 66345403 53975378 358746053 689520119 486620494 341203605 293232406 255857985 39069670 138435665 315126698 650792311 582758097 867997617 604505574 509887515 477343651 389734401 974434146 752721872 943283163 727009640 847615721 861182581 414852154 839177072 921319437 30153816 192986718 297893661 604121814 205430489 781482664 96651764 374179978 502976720 348328625 198058140 434862451 638763432 685333861 473775147 87016101 92839087 364837022 350717994 834903190 608828442 997055363 326862745 639703593 110438984 141570041 307680812 248772501 146210938 768784980 400303248 694605249 673667845 479551220 842591155 844196225 687419981 398061484 827038901 119931646 350896545 32662880 140273400 332347183 711058187 728200611 309176287 619824810 506016843 990856931 526992844 876241824 113211874 237274934 609769391 571366649 610304163 787883664 182845546 610079710 844747466 324240176 691569916 161421688 634937732 668143237 10597538 557673387 849645455 730392793 108873866 505998699 572369778 826166740 39136652 438348169 961295771 211053258 396069632 517686041 837252985 581366333 405142857 79894356 66623658 250288655 70815362 587615989 690000233 370524867 624090688 615637983 288309926 426002265 506240867 411610400 857210797 15035440 541398660 891730811 235913102 610671555 574826836 457575217 512126710 452756783 874151429 794351903 407245741 422110948 911048422 737000258 571441629 830584492 395849034 718750027 787616607 584560976 631415263 262219406 247598360 800614377 224742133 568133446 998682553 374840278 198933232 80667799 937333214 12746008 432118525 838987472 941472177 179793044 953525085 437699547 662482771 494216988 138250376 700396538 492435831 453980014 414016331 641963515 474752931 141818741 911179015 561921296 415623237 267725150 917383634 919564548 436123331 785905205 975880325 720592388 690538895 54886696 385053672 662618982 195969478 429118935 715693831 20725878 612521516 704090544 768914527 655674697 75926220 178184729 574931653 934474526 150166920 214437525 437098397 656003767 294123749 613703573 452553795 167045062 101400161 621062091 746959564 839463376 464624497 857032218 399293181 699991338 411210022 905471650 224664548 489764442 950794601 167655665 131219424 282069488 61559129 164894644 511102525 285349032 467294167 702175738 214267679 806423760 479375941 427703061 503620041 352927612 718991593 224054545 57125040 412339826 19941508 821402349 932308038 654901714 527153867 731985165 830589291 430580096 632827858 521484875 435066971 495704087 789474335 730764838 602312396 857291604 585268240 964196107 583653525 194255354 741398428 888152037 817401308 84431510 660810196 929381883 783931833 486069985 321733767 619213215 627234905 226751047 394732303 40774792 579047252 293683333 928011656 542378710 567046243 572207359 858404611 425084386 182333822 212611922 469529281 577693388 766465559 127033536 660898356 728619315 641106545 907744662 290349233 89177035 373016457 572812578 102728196 335981092 86429680 475280000 953114417 676478362 680703074 862346055 449152839 969152463 118107731 23534524 2580083 560041406 411496700 280638373 759375167 668761116 590022646 593535106 25208342 104700430 220175625 91259280 623520829 194639942 294879976 277871349 493568961 40500955 260938475 524197664 821830455 91319114 988199600 771989635 854818333 832634377 240729080 732149730 207801420 569017346 520037772 166405006 176466207 865040123 637311419 590576814 601266504 736351186 701358574 398502477 754444259 701542677 280943121 375684741 859262717 587791752 288467921 363166380 766461 46335734 964422222 793481802 364581244 379432376 230520070 466707561 653811474 147655095 919009934 605642231 113537562 240382832 474137986 834462274 836243413 973221769 25797775 224706384 515032345 560370792 426526876 413717269 559162899 843349202 175672655 7274753 374418952 431593348 558999333 684763808 410760388 900830689 253206858 799401475 795572721 419040731 975934065 743997230 5881585 220335403 961312555 606011617 42366508 642210324 486561117 652759293 372909027 146233218 781949564 213989115 534738331 317031803 45622292 581445575 943179887 508823583 645959895 130864472 820289730 534909277 438621954 697657990 564911967 186428690 647756240 564081700 435728003 520244602 910055310 659783209 119782005 706817228 598617371 442554825 743279164 595509870 69493467 72677561 40504290 258577242 920239875 425337376 950412337 859940009 785033302 940376667 26133909 950810989 558537905 430308242 182352797 547609464 191480510 441936113 277280296 58327861 891301339 883966405 809184191 641827852 772391837 149129950 35014020 211993052 932827226 696115451 657082094 569169952 842673734 518639832 248108644 765279304 584508103 142024101 974448676 149552975 376624163 810101830 233729023 572912942 798780941 717358340 545831122 188810895 152479810 21880699 902358934 550565240 803238265 773350147 75447526 71386762 215860741 865287664 741633824 342134824 489121668 574775005 890542294 357540179 26650291 371238249 552408309 123391799 710448038 271001706 118669342 487326737 309799071 373159204 978730726 314285638 45164199 801505646 424196787 8244372 446714029 535437549 454675011 475453487 155587587 685565101 833633130 602054498 716578824 199627286 866238140 132233153 376936342 33588271 303688530 216391943 544596394 304545735 832288721 924337006 82401207 383168188 554880178 546724943 338244083 318182086 218809155 715336465 439183068 902967171 762343477 505339381 813836256 624020143 871066447 72555733 937229990 713969962 994162694 95038735 139415052 924044767 907009031 277627301 959271867 938886750 362504146 620020047 391449891 213227222 806031447 894144266 889522590 144979517 506453458 132098364 141545785 448567495 98178712 249102992 263199290 533938268 256351526 445012438 642438402 933390274 306288560 94133650 852382017 85988072 182210049 349800226 730894991 746715489 578852183 981636392 670924967 182632394 504197277 126449438 506655503 25003952 4783585 5917146 770388297 297004795 15511186 785289962 134287209 924677379 536960458 992695044 155442547 923571096 73564919 124685817 913079419 727991622 239953531 213002344 287624677 234501524 579275791 732559427 351351806 949810928 336809375 998059631 453029902 42839516 478552154 211403081 173199485 12499606 185266794 923365945 848223849 435029655 649622436 782672794 30180560 590996166 511180039 294258984 107680589 71764624 157339718 158015865 540363300 710694660 216305979 118629241 815308859 897075089 357087286 590527432 237532706 268280621 731800113 388494280 697012189 824639688 227190109 674126616 168137829 485255977 587138422 728810696 821710621 693917199 799631142 111403494 783698835 436801830 118591740 499146342 564003909 218616932 904526329 554520332 678098256 548920772 23910277 579299490 184836093 385964928 392414001 603039891 681721055 150274149 239941826 384695355 763563513 252346686 748908640 944447250 480289725 421123892 724481858 57077300 275065977 152226284 654590059 578256405 333870904 829300507 801924010 667058599 41498932 878642670 711307124 616173177 502368204 436349811 817256346 678676046 717193960 813755989 210143576 885376011 530625378 111277745 600545631 780663990 120332981 821579064 284836266 30233854 552280634 217399528 26662386 739518944 862440396 204094468 688630663 432438818 478675917 320287889 985760502 497977320 404172648 986152716 809396518 354042576 646987951 560944288 282468515 788308934 428719124 252967295 525023940 838192212 526468304 891889598 130329584 587965998 164834776 18047035 388271454 75354188 84832795 604032256 595086411 547490888 937702996 333055237 957100464 260054054 766117032 134249365 813392039 870442592 447841144 412720820 199107498 249533205 998516472 321497176 687408278 885386098 6681792 505045474 371697621 850046075 41858394 568312743 568127350 441281188 812229674 248038788 587439089 369390138 291576868 491208985 535278106 663971229 897066487 606252407 182965722 7356216 343319973 100471648 743318586 403618504 804214913 372494046 126978452 598673519 860507709 545826300 256828063 763539602 405211313 988595413 82055847 59038500 143319283 644988995 486662346 634735682 1737711 827965593 721924393 74636964 957144923 690462770 163239183 980937543 92271855 279623344 190173595 314752868 61965624 831666216 737072377 698932600 744686097 243489078 361050966 530236045 856067238 32303259 766902403 431571880 17496462 254159475 424559717 920539198 792280288 33340974 892915966 843716033 695311858 961369393 146913049 578376046 879224822 151488521 520348854 220763760 435314835 338761611 841062998 282495137 238182065 938229210 672160716 901044565 853758586 566566292 394060460 714981133 705826484 57402218 59468130 592305772 982831115 35219601 443543632 131773142 537309741 318848271 533842641 15613012 721568805 482563484 989362392 53003324 464371228 293590739 429055535 830910626 527754036 224299387 293579543 394939470 901655671 555692743 264442924 620754650 641166894 931987145 140724984 450390640 800110254 992766766 33640653 171717136 34579217 473529901 406560492 419431309 569031743 354349081 286622920 608831594 487235352 413248935 279500242 406162404 379376 939807663 22934657 945581778 853879712 59415122 84293279 220770377 312700653 719762591 630213882 259435075 203474611 528838819 12915733 273499866 969476823 383431177 620817488 373360751 324886389 507793791 735778621 313707519 440884946 587771887 84816698 673637047 259663385 585524600 919307626 979892046 19250452 215201539 482287332 359669964 705806622 344202825 626828946 828536002 671162955 272403518 998778505 334553069 490152555 719053703 664504593 188017083 592903865 387436766 211741880 866165419 922247194 585444368 359785728 649150594 177457647 236060115 819951993 5747400 197898634 22220064 676330042 268372698 137133430 957586936 263903707 427864133 904320848 304219657 298944589 243436500 265485893 992571979 689564842 222644756 18056620 138997197 941785050 522576338 708258300 321337743 257101026 648102696 101321659 271937594 599918861 743129320 765006715 587717020 665227252 705935112 366998342 763256157 345537023 177787487 957254262 367780749 893023161 199261604 818361386 638992894 874194399 938746957 91167380 161795691 1203640 384613624 244141625 515252324 508143436 654406620 737573256 165772117 731445715 549255511 136585875 160657604 366218067 262654224 716587572 347736587 31716212 640012645 650274071 279238193 404814822 742014063 5909710 988572069 155620859 293557035 731322018 337834356 555549973 417747717 870560738 878518623 267798792 272471216 137530944 429733311 976364683 144097767 604911431 365102103 803058654 808215820 793313458 567532893 471420750 534867985 477310137 843670029 426712428 92983549 946636984 725811833 472240239 35781265 469854909 894211103 81881684 205248929 549568794 595766747 201540542 112319381 980580076 548645880 650481135 195837824 647371520 806305502 793551998 307336130 857897804 285314955 513834741 380304606 226406648 223439975 952524934 595106165 800593402 875912243 918179817 735411276 566455898 783526593 282200783 654531766 681194059 301593581 612934951 955372568 495534990 482990781 120087943 788865435 93499042 216043348 983673479 439217872 277037805 520616514 113600803 544605234 919805743 934323003 856228221 751348781 443415532 726638186 29938597 601768842 831959185 169261442 340720862 122382132 659898896 195802059 935977727 369888538 145615064 935334741 516727737 821579873 346851792 108864672 846441415 848694392 897236502 409262620 794732381 642783731 996021723 176523479 113850213 163804892 849677314 829162580 484995202 449494124 758081442 777466024 629919011 767976024 871667552 945253658 647131546 915568564 433417843 651190545 96908303 613303289 916327334 851387493 770492432 729777140 474344365 434050877 966617230 268097516 597182862 352771290 69724364 296786310 240385774 428118486 98620896 985998699 297839093 908739146 846443456 290810506 430743542 212941910 237248928 39355771 977260341 977992182 941552601 582564182 198425200 965827854 692369036 449341018 182127018 142735449 665455435 992394922 180044094 126774666 946451694 72587417 555622024 134492404 513047725 742423037 203862377 132369742 158490269 571156544 106510393 242261351 483036008 378711215 898472857 351593121 526623409 464450722 579620502 281415375 281464801 870573404 420474752 981262046 407487243 516368654 213774131 487223031 860085727 595425861 845952641 93342074 807023227 307195671 732820654 754170662 570174266 594033791 584669171 832124747 74898681 337916468 518206700 331730321 649385418 463527798 265160331 288193951 658531688 279517812 782658774 400806704 517560056 468475689 958588318 634763709 866666348 367641076 569077007 730889274 758512318 766548433 296354791 912005726 187309308 725808670 571772939 177978406 802408285 90294031 601246820 50878974 277425944 260458008 811345599 337113083 776425493 350713206 322770241 7544266 806135262 169626737 79049251 52593654 634036652 985857241 899377776 368142064 294758718 693398557 363429096 588901256 212308572 773471251 39875872 815748710 789438575 395015887 739239477 469563774 835986987 9224100 392454420 659903267 764318670 223584018 931006314 371578778 237207794 529824492 714136966 439841747 936619454 597460971 861327380 959436796 924271633 751210069 491651024 879605387 880853571 571981466 108408514 925807658 536359580 765493660 169581715 647961506 966286558 211645562 911158948 263872223 778694595 264557446 763026363 247479444 75085329 203567651 870331303 729221213 493413600 511086971 704875363 301871487 523326816 715281066 308540228 697294171 542142349 643136930 444382396 746866199 980455513 209199483 911530674 652414320 993038526 514134332 608200471 951750825 924375739 299782194 724722072 33727042 113188710 295148255 614692410 636084949 419384038 869613437 856552766 127745276 696587027 300775742 552772906 997073601 754972878 898378586 201064751 147201913 759069469 209227396 488187454 349919951 538856039 154562856 209716224 933501061 488093226 490661758 127802470 2502120 499099733 34413920 859005814 169750842 513148124 902457925 488676769 123382337 757222522 357737859 42781874 217163145 80972745 825980423 835783293 908356137 52316604 825024628 612577008 460767802 543147134 218990895 441218905 191412388 392798092 638719658 487416225 497298397 877765772 558565527 596033200 861478824 761930916 951457597 721231011 904977651 280159673 239328093 16378416 419666354 485912675 567335609 551128290 488835180 568134443 255866945 616017358 249606289 853498326 279698455 226793974 567020161 546522622 556942281 506450713 725026990 993061592 239844374 15374996 930835165 362324957 212166311 106457899 684950176 278077475 606892528 485611622 98651938 836346106 192768603 184620573 817623747 856196871 931284844 454407024 431116800 497926257 930121808 604441652 1723177 750984219 549624835 831714236 838183156 806713361 599052120 588320034 854549220 233369626 185465961 641297945 261877166 542024603 92898459 132778109 96519531 47110045 704926224 519440219 87968058 140152785 738383431 899551869 749073942 535992971 61135634 976571736 116436201 603681062 307191134 53762206 64432386 691552477 816234214 327326958 462352431 5633092 10047886 500998949 763451318 3997140 415585220 298508825 439496410 467739335 858636319 655563656 453180507 639881506 800405600 281630018 401467619 919346015 79281092 690612645 348927075 490493820 65343277 333691852 207538569 845773810 760187882 758281033 240466554 303597145 100067452 823221806 339070363 355176948 573372778 922826533 255153851 401104335 771241547 445586492 992192333 744189064 648556492 423337054 683140608 911815745 160476756 535263416 829021419 3397682 55391803 541839206 914100639 676150939 326889012 71748356 257164629 28000959 105457560 221125220 543522365 458953147 53732771 383375829 489500482 14086749 813979547 158883605 758119434 767869824 99305416 896651696 483206772 287508426 874507054 267108596 698072201 170575420 59111402 792863772 192881863 37818392 924541618 283537138 664213488 630849614 780247856 473391497 549573477 617260284 108789179 562163533 485695433 798720623 529224258 743085685 445491412 990603226 978963715 505552753 287968275 474055052 254159896 831592028 447362274 116578531 519755072 401199273 320133978 559585840 989468269 695577801 115561709 49656384 981364529 804749699 916619521 403732280 932990784 719156918 383244850 422594170 606807410 798139966 581641304 795600547 603303835 379565525 59760311 115579258 813557184 486293077 367206906 37911000 916068864 453755793 185141870 760764439 578048722 105144947 598592246 689006726 27498754 582856993 190764495 4816947 481888044 960637975 596687846 642003981 87751801 182207691 309339682 178026015 541486990 864262630 678771158 231828558 836166947 475748471 760279205 852911507 782096801 723528650 280459730 769653419 322752879 863517020 628656562 669863760 173575280 373696311 908911100 606651204 724703772 485866941 57891656 554604732 750881510 735023279 522800855 627884307 939135738 260210841 504427797 587249168 576096802 705247877 839255637 353413507 919628108 284351559 891390026 941791848 564468393 180191872 626637384 400912508 1304563 476375295 571893969 859745328 185308404 920548133 581384281 549321683 989017359 569194287 345824342 48095936 727680982 332663021 481327640 397548594 685552751 581731761 838299640 711274235 715649556 771663394 281997175 235092399 853877352 121792019 978644084 366815534 911121725 688782523 596792863 982934206 883436569 440886426 157756005 318036754 196468603 573897589 257257496 797529408 771684974 153340911 240998236 115103355 720332597 719392969 836898712 453540910 201833479 564254909 549278165 677139136 837969323 207220308 75414252 140459969 593662525 574755342 194220043 835045545 888077878 292000136 878397566 646206019 605710674 258390131 362436619 847167806 778642001 719293863 280018579 854183432 817272023 674754682 200405334 66482289 127923427 564791228 688090563 708317121 716513010 170432978 297001437 353509708 237029620 742498860 927408864 600870871 54452091 159881322 591654866 833244360 803000022 368237112 957295874 67843717 742314504 74972205 809596424 567344718 926888149 694539030 444172556 35845333 66707249 287371029 246465700 117549533 995455404 868197352 187791064 362601292 243537161 617647857 403584329 266730242 873594543 860067558 794224473 873340350 591551063 336416213 500876662 699866065 688016466 683417526 170806209 576614672 587025926 830934701 500506471 588903677 577252300 260939328 805677820 164215835 650670542 699830521 915675677 899998265 601697454 517913193 261070866 917350034 395427002 503162919 364777903 880900732 697743155 161215227 664792301 428696085 274015563 149215451 927151076 261885566 46509384 155850601 873420682 37816403 406329806 45679880 952228554 953969270 887090481 317670659 589594721 269461986 103523437 396306202 720127183 169908974 716204345 249108079 636807996 857129193 260126981 717911697 662786662 306303232 186007087 219815811 734609165 601098278 585932471 292928740 4233106 431833849 545919554 257136051 280376102 434966511 548012614 417064026 619652155 167927993 634764151 380372977 64793288 202332870 229881812 901202453 796797248 949697146 83908307 309522199 845958753 283220306 732664537 881754747 69163563 634878739 482045519 862087178 205356399 221622695 157882084 103181978 497075685 246870258 248719473 227281884 939394749 739916703 337549725 197881331 126136000 552322694 267670669 789145668 221570337 998023292 782086867 560138589 211416862 622607188 181396099 539463098 522342173 704953004 486441020 993519616 301668837 388140675 149901949 615374476 888385379 681790122 346918508 592255621 572728992 688327201 213229719 596653760 273832220 404928785 483848390 565899730 388747379 763355874 376969979 543168466 562267262 188098827 708686128 208566730 25598704 374807174 81944360 893713983 369257182 677826672 250686714 58008125 891255955 849191072 889227548 389803312 988903341 482817651 363023744 29020253 822021901 5553214 653579478 853630949 406644445 877319543 20064899 328087624 327200701 786740008 415050959 669044536 62886246 995133332 114139304 290593416 152891987 868322122 1571462 593413369 361004876 376976131 552433482 911960467 615671576 683349890 278258608 238532176 811316219 266557158 774377645 52523775 693795735 904817123 659969882 755703959 291251762 99109674 123368779 556811038 160668891 542944053 53892596 426103194 297046972 687562192 35091529 699481981 531276744 582211398 451061314 171729841 96707402 276442600 67924365 422106006 803323597 322602950 353979686 783739161 888565645 311628280 22844040 523970063 342278272 327112684 411555096 464649585 924941923 136194856 37238233 5796404 167591661 8538657 614123795 319682594 368323728 782059458 77770503 980035367 801433382 841535743 270553768 580870279 680400161 477670563 515802055 741157986 148354307 94948601 284738126 407571778 251458775 709966625 524320826 701756485 774097687 608541484 581981337 277542710 539800253 736021277 956676380 939506648 432325123 292535552 906862936 16632009 229994905 413708490 155903951 212771782 765265829 2245875 162443891 953605377 481996906 209501944 14096382 752293417 333026896 114984456 412192106 223025907 351536554 771832576 168418649 879543809 953208336 836065357 576746621 251417382 779338660 246961853 972637802 311614437 626572000 599376897 772253293 209658417 627140039 584962465 906579388 568379908 340191503 240557418 931549568 650932842 255119099 675475885 523860621 787970558 350571849 195674933 783124484 572274130 128340605 216785313 822945528 521941353 538304220 999238629 947320743 744388389 456193421 656753542 306576278 363943298 914674828 576059050 590930595 34610576 126601887 839958749 558714914 705432248 269547983 171666480 732066189 964154610 558581200 519611372 120030501 793346621 438381751 535415517 692524129 407238496 128678959 604647562 599182168 227608105 24062575 380475106 512840130 651440633 6703843 937042454 354763720 175736773 373362904 337892462 445776691 604465103 876481179 290999168 159392796 980107964 573447888 201536973 283997268 908050907 907376701 532490570 50477767 583785188 160778454 796694084 730538587 50443859 828411770 594099256 653128888 95112331 974080273 628369847 491967534 862068063 336371920 753378684 60042065 216876456 646597278 189947516 550864171 246399894 234147810 57445115 758866781 257780043 137763601 349302181 196683019 122548951 203005283 756117338 580317306 188620547 34108584 23881252 433856167 626350433 971406847 272894815 770439692 999072808 792343594 549255778 887574771 685320829 411827090 407670591 280115994 56872039 959881697 29752356 648023582 524312056 153539308 889636857 988120966 557150953 671812026 749684448 785714267 465169095 250552377 351728068 499094982 359457164 141704791 575849765 374790162 6464667 547657590 728518740 423047599 575877112 68438694 810438292 723484069 150240311 777733773 238315634 405895860 731960906 239175019 189711164 680562442 153123592 570582102 597677348 655057811 652537376 375031024 767862242 623992550 872962843 405453680 1588959 539225319 281641504 278127787 11187628 403690116 734542415 280749546 436565752 646316591 873274530 162308226 928995515 582552024 492693917 581618005 646568645 818188164 499765568 750068229 217349962 26073806 314962249 602599625 499071239 80097147 965083134 73745413 389294644 839407219 445102022 261031767 729635914 738629060 886397186 985139204 955261269 988400928 591395030 699659364 498895612 564073450 389206274 810713718 206456884 184184311 736344310 990130972 488949387 202058936 998220102 698454253 620900141 72051353 593396167 149759478 136970837 203657079 759746183 432035652 454794135 210785641 13845790 747355981 154961163 306769733 899398411 359910187 38718264 656745799 249205310 31183986 586909535 945068099 261719226 375955362 315915243 230830592 202400945 786766619 394724505 354467136 453159114 355706672 106677017 292151714 906045999 98475420 376454515 716206645 394841649 610362144 960151129 986924430 914931253 625359235 919135801 31320146 940969174 474032558 272004426 29710172 771649262 326925591 948904691 531147437 341517506 953235118 572967126 20924300 849634927 967281414 584484680 906440349 767556092 675554900 887541229 94587635 461767298 964988899 510246201 564060677 65623790 996801 580580271 827884571 335452237 221829323 361155757 271323112 365093009 595925506 882140569 117614520 323294770 924291894 694607929 659361459 117971150 343493910 43683593 736112391 488485598 863096291 408259050 832586002 944668918 589021193 226039297 803828191 868025094 161073921 759089839 625768395 85417175 353783855 627045927 303541258 610312231 145181908 569262077 39764750 76674432 18896311 887148653 876792342 731393105 685040069 585532289 676102604 146060751 600656590 262649465 382658328 853456916 353039914 446565063 277866703 193960118 342846408 369653871 709432276 93290200 493085001 877554353 753237519 304469975 93082626 459074807 498218539 971957829 386840603 433703500 18004295 591786959 165420093 622401200 91237167 210251997 356271897 881761284 718262596 804791363 645477537 719725829 602873120 330450920 496600642 568584235 86142915 660757077 547831350 364337778 214561865 961100022 848457169 160303382 209021805 536919625 826672072 697209733 560742294 573742883 380452184 655705237 262013417 922325230 516199908 359952543 580351627 753285551 146771252 145520403 985932017 207180769 176552530 331839513 709793160 553121486 977795247 641292396 977433585 98015348 759192986 308837897 933521022 867718827 764898103 861391663 628581483 615473247 213645716 977194181 80679894 671630724 41079275 248019801 419749280 507841818 589358936 167933359 409488390 860412645 736472555 216557782 520317351 211575668 282942177 965609434 951035095 290447314 389316501 821924954 117244212 102327348 789411926 296372209 198156385 373073986 98146959 697359406 650552541 372884544 750479508 201184077 52446562 363671094 660751822 976049124 720679259 888566693 625731294 602160425 857276948 148738560 36558185 898604219 954400990 628311192 628397716 593773211 488717402 485637446 86401014 763774696 46357419 461976968 875199938 45707903 544144904 37438561 139799985 933895421 269005270 875453017 532620796 370856292 787667827 202572286 390002909 813776886 935178007 730145237 184599070 393926257 805311744 883830687 208329962 401227639 360276848 873424314 904780868 425230185 590254978 139512328 123815721 398478770 234574987 439342141 1423733 308335674 326548600 958141376 528846589 370925327 568347460 464110926 942883422 898358753 867152830 402441955 873221699 299424379 758281352 938845419 512698393 170261600 660049747 930040855 615395530 624177458 513196052 154414084 735133671 572924446 960000689 980487099 442468094 4792688 315274612 662881062 986312181 252458636 791136037 671402780 979562812 110047542 405760836 192955803 995595450 340065255 562976581 271736416 431958834 623281108 383299425 450066855 351635519 606898858 419314475 758576130 494603904 95273998 935916867 22739248 624015176 665129597 624490034 966011526 503026183 724739434 73203820 212493629 303132142 913842353 914327610 126161443 285243687 867955712 199694605 447665046 12049082 322005941 584592599 540600884 57266104 516795519 810720997 201696981 549694668 870155712 394558792 827961760 798432677 956322215 759788509 635399224 393664361 811782963 413457737 637236876 244433255 917220895 39324260 265656771 231837903 807536924 283371202 753791091 696571039 653595505 895090251 437429951 250878346 192055060 912405842 580022659 227181502 962213190 313039963 838649672 877680230 170360776 264204221 176816740 161807775 570844794 917331167 578386270 618844236 663687878 515523947 785371651 764666356 352592868 60893925 406833482 79233637 981835757 345412058 887174350 446714529 223108015 1765320 720452601 803197079 678735054 181760455 808514260 384444655 706102143 620701729 716378568 826187900 467690788 529820006 91735755 383540380 903934735 731845901 347416121 459301394 242706328 947629186 2843981 756543104 325149427 399003233 127984104 445000372 615496429 816370394 349112211 416976265 502847166 688222712 324894026 423998016 805426891 712117838 123951748 415911134 258721472 278321792 452654958 248170053 531783678 311406358 944818314 104113467 822842676 391783997 783336788 337226666 970213229 51288395 488808036 244008055 980012608 130940220 718795640 514318641 803252612 685515690 669627156 638207103 224594046 779953382 530271152 120091470 58254045 992370576 738272544 118761994 912929177 993825462 295210060 122140749 714452416 602885695 47954466 778609564 892837066 856474287 276157694 494061546 521521549 421087533 185656251 679748155 647556453 269528448 915813087 809651197 913510215 439315187 512704738 660446222 297800716 669269207 875341622 832404024 981149659 720313642 608277190 44677599 382122466 335808027 739406171 935563525 22045618 218232453 76243873 798024711 174422373 446650886 210803949 203727601 895387740 18213123 243879131 501056669 369710604 152708198 270493949 835538483 670957663 554171749 444416687 243484428 232150326 506632767 899950585 534488331 598833130 562270707 505092342 919569577 937633739 444072245 752301393 995093498 522991121 677295681 124275395 35759374 826563192 241425041 255283760 27234112 54370265 933937715 675715682 503466912 257545142 920663051 773636091 665306999 201720644 554534195 294545742 120708750 433303794 455180391 660231017 886530505 799835194 476452386 212777732 358383543 531644273 715762145 341035094 15480427 660766266 745507199 674024117 770247141 142019452 906784819 789618249 990298710 367577646 573113658 910088284 167432796 813185944 900663526 282669600 87711839 996533072 139504870 868441618 864800071 393392614 601541452 905681866 570708926 763903590 67704914 102032471 356620325 433540076 12840432 289874088 991030710 600055558 344543258 768677615 800962085 950744053 701537025 98266514 569483765 803532547 672941856 277273339 115659623 542009164 551994352 324979041 299240973 806986620 572283346 973496083 271716132 389122827 105931708 203709669 125255044 146494667 136228241 194993130 800314031 945780695 572244217 153404176 572490797 85596075 255170941 792713336 824814882 98110208 312744718 407514548 326171714 628275774 38947199 557949174 413167284 316474381 413167452 733945319 492888442 846348185 270117661 457191227 161813428 548540985 454577411 636437133 317960513 462169712 372807222 183670836 234878453 379792160 298558648 229846399 385915633 40600241 663862397 686845806 646187586 454682896 924237526 186217224 991986350 199617236 983571785 495457789 930936619 969955578 589620236 651140377 133273546 475711769 203273621 571459614 978367441 557029032 328460114 878124444 340575947 109807759 529099272 952331617 3044755 271970397 552468720 230727655 149296741 749639912 444628557 805345817 86236812 148435707 186586606 493440335 376540310 871664174 525104595 943819869 629504700 499340524 967162625 587631459 105551862 389564255 107240251 286791146 2008325 159995616 278444642 92911038 801867037 36611351 668290882 46080730 818413980 512424763 984684035 124386236 929311937 176887502 698400464 975366628 22882664 180021549 64258377 64459179 990598455 638432822 419936096 444327330 808740514 267307947 541040858 863471776 932789221 892429609 736805421 525718208 579983857 887684375 406819554 690770067 469624679 808555142 23173205 490955190 210304922 122081791 963375707 80763395 394769114 346606836 94371799 907930987 393898495 243362543 126870435 373148625 862557310 798450417 882352655 311990426 903935926 61028784 22008981 710941284 832770141 272448540 382365190 396658856 176536821 517007317 234191239 375860627 467845296 581189737 291657498 468996330 867983935 184898876 123773125 230593810 574166081 902823027 322481696 604728199 117491513 579201870 221788467 279492989 616445573 376696188 799743900 615620025 607339806 414306206 576599420 3091910 455167463 836447651 486520752 349408595 312417424 573764572 549352139 301742928 647659818 3743793 502825795 821985261 148342292 196626844 791624778 467178390 823696601 376791812 839015219 603972912 277031631 509585415 771209635 368798663 705544621 73158695 343098426 18830555 817347465 11146650 611322751 530146329 648452028 542100668 344034250 120969420 231689404 616991659 871084922 472025463 201109214 643235482 517359280 799375743 19873616 106491938 277103215 226300488 11751078 219847453 54767892 478542405 344447992 400040563 551045881 857036868 796946478 146467040 803877262 486922223 59406766 610631580 971410822 20369704 755915808 799182358 986637299 498015870 82035844 252526626 87398527 648958249 503411574 712133934 400513674 382065515 962948760 251888968 303326255 954475358 353425385 483917807 15242780 544169759 913452361 258799736 742082539 484788307 242327939 288094004 462816374 644676820 126136337 717054282 142219815 815989013 685679862 254108932 422238157 9806325 589039320 477330631 14868629 801877416 454096767 271129957 243577427 836012392 592327834 811021075 253931870 59321014 57786722 183430936 239607927 221663220 17526772 831785307 187082395 320996774 713711741 429613388 855786621 615480060 790556975 630615735 207825282 69838416 652215191 451013108 123677841 935025450 172540856 520870738 666198438 192059517 444148083 415939556 459926990 115357467 330706091 891121523 346026972 39189783 447657659 718821712 868339314 186345955 151339967 211094523 529572670 682964299 5724291 899575559 706516382 91405212 824758948 192040080 835727221 447244933 692636676 267534958 295054064 381465621 85451981 871391066 296306307 641905989 856938576 167664405 232082311 662994287 705407620 828822772 397961489 985524304 110477611 69226485 192234331 705608230 793175730 696460651 962279833 515373040 535859365 961949059 669574954 782658856 538018711 58287402 232236365 804285353 850422435 538733658 868739253 433581540 263661088 445906171 436977637 403746620 19884062 462135292 484391342 456555838 926165068 90283678 101586799 70333637 220103784 423888307 763615909 783334514 153123998 92841687 779291202 341515519 594419687 732716351 663760192 78681108 529707700 133123080 627180606 524106807 471715947 880971783 670107326 888204295 870774676 572042675 106682808 894490493 187582965 805829589 74206213 439289016 576778846 841162561 965965309 421820789 775968719 976274154 271678577 692101795 395241459 810756497 352396991 586736397 122885549 473848313 901700742 181209777 354150784 249891752 779470125 154890071 649439651 905251387 535212107 552302670 17770045 322831919 340962462 281133744 513872712 200098265 84363143 601679506 188022851 252551514 34912317 909492525 327188920 803699533 558682847 604107227 747872455 171683271 572200901 121661754 98503991