10000 919
735754121 789015847 954493080 771886281 237654768 647345705 853639945 451266634 932838100 230162208 610184091 18374238 935693997 21064219 955897444 15499954 243291646 965055799 662395807 973147103 398008634 376067499 773640437 646578251 818263837 250003101 530831192 537607227 824241840 663738731 935186107 244216326 713001295 29482222 273367919 262231176 556509879 684332223 840695152 50235799 236427305 199782454 246398256 45827701 963044739 629268645 322218905 353537836 750857587 120990159 456950305 706243143 21830927 307142628 893332747 537393652 301851435 671009979 389299268 580332870 447524 856456340 361635780 651469857 448605504 54402484 442482590 652724471 67467088 366887401 712933601 394591715 959208969 455071899 187684990 935266323 49104882 406164630 388951100 196274223 566341711 80212864 849953936 639379760 197104051 926261589 383078118 338405520 582784906 185304666 204502974 526143958 309802277 245379976 271580826 309522292 718271133 247884664 746608532 897823102 194971737 82202768 340623693 250464679 457960930 138300928 31260477 371372695 259537577 903277082 139263807 224357243 240666959 532133675 789595014 352290425 401723131 4451079 37885852 723599822 871479343 606084346 674504344 524549990 631751112 714417066 355440541 535346416 774554169 968044110 307605633 560678913 355007709 638799553 21118584 238767582 967648088 612883513 174234239 727651360 609057678 613123586 930574260 968888111 221799384 573473858 621221643 449323861 568380718 694977484 720340877 930647344 496167978 606693024 60955214 719811348 371115908 818898922 581250571 364973264 734372514 486153820 795749262 306928220 976517398 540732385 427994054 503650326 161565845 747179875 655813245 972578588 240415642 165814214 569368873 308452904 996524316 345135227 913544264 980574010 837292685 221174046 588811352 644214598 692748539 288477429 620687557 593296885 18277905 732854283 754638790 797288041 471948978 184903388 254654251 121969992 27081169 934367321 910115729 376477640 45303309 21918018 97199739 149568748 26493891 531821047 438262040 9498092 941877165 510972894 399720617 796377376 940870898 128853876 883487555 580979578 833758921 11237785 289556542 660531146 909537026 34600730 587683118 792956852 511121202 12572397 215388639 121350417 714384413 740525084 399216955 160963590 375779993 945905279 845174045 695236776 253736080 602267465 74557741 119948101 53894785 361172157 477360822 733718444 490517144 253907884 8446845 571658523 62668894 292130880 336345698 610032009 741806886 683818844 166014392 912544782 180012298 601130267 271733586 465088393 649778786 770517080 374111151 546767312 851646880 181418893 989318381 699010997 268016955 74720603 371379796 926407389 10610076 257152552 613221621 285717803 874745840 798301713 958409532 592516299 183428224 71459899 818413091 717960223 287538215 700551293 7470240 613623259 786298926 935332828 6359726 310090811 149430855 533120160 591916320 801982034 447263702 225171570 338621512 477766829 426067362 648367701 50706893 4648071 822775684 280786606 664116278 203150375 720684488 566642473 471242195 682869736 444432469 713130527 579109754 971488346 401186748 72806454 118297422 219765019 683722409 475044180 614600715 55687710 998971576 843929433 49100896 729589821 708940964 44258656 344007631 536787131 332137 430021368 421912591 709124867 697434575 786659861 37174471 589158554 648161696 71984184 525165201 245879886 541289084 738815464 995485264 184974718 423753111 708115036 376546730 92987431 966449024 468060838 14303463 366631411 438418544 223524852 279558959 892697369 718417328 326453518 855222303 840979063 408294207 723765697 97646915 667853450 540585693 466561663 950730301 847300533 845608524 328429451 102444677 835046782 987085439 831507285 759231418 34874404 358963372 588847808 54887516 942829232 546855936 591665515 292756192 215267821 926809067 356814001 742905488 140193262 42225567 24184824 341417611 339514540 963840801 823930171 348275177 842377181 905295357 605356434 203010318 145316684 723268918 21209631 431767745 234229982 335160067 89603140 300225645 742245132 916838556 322091872 572976012 949884757 880123385 574523457 437328131 219086551 54199394 692628321 692779289 425895582 98161361 47451799 731709756 959720669 45566952 118256209 623709854 259824802 102235476 384561386 670963104 666008352 81631845 477772153 496507324 551587316 824023800 554006434 699699870 870788954 5263973 77818411 77191105 684662982 124647070 791125161 539744657 940065925 437730391 377240559 782813620 221016617 302252870 730899313 866828896 493406181 650247587 96553179 783604064 442479270 42414642 389422757 744515206 841677542 752398598 403260388 485389599 191595276 714511971 97706230 579211268 623418982 841389675 782498203 735090030 154443234 298602574 114861311 25639436 347675993 966967292 991133316 845165971 717672379 372388317 250580564 470871463 876412602 982500232 62167853 757094294 442459478 235672147 98000679 568558555 319632224 217240047 676959641 354180729 105963602 629213032 652561076 482917414 110544614 157847816 878653021 803964376 85160866 588964299 750098698 223833494 476479017 725757713 86338950 483445331 796815829 371532015 78476333 995708900 164246269 430633967 342579897 360377577 434095803 701577848 730635492 491387248 226542034 270552260 709659011 406569190 729349886 788073129 926443772 662739724 251039405 144690745 416881839 493095744 136934590 464419706 540120241 761873703 700167091 994865831 469215843 483614392 850175192 306801178 41358453 122586631 207172534 442107871 389242087 289655909 854377712 863052693 342220944 522103124 844612814 663421285 674726991 463335538 609656957 747210144 341729380 339507450 542082547 275603345 314931401 534764256 556941255 467713406 419450222 839501231 17502074 7765054 268453562 764976844 292501922 340191113 596047758 275036620 613855570 895287215 782085242 337441168 691176033 676139658 807253432 111930920 903327195 443296769 767061315 344596905 642611906 219207570 604024316 431903478 97823180 24170568 384520434 497882192 813280147 206083006 291893046 714353170 581154645 616354191 610687175 314225735 444920423 438997601 863378900 625954423 118802811 815736590 990686500 343231016 41667725 82979880 975997547 891868622 719118088 345905296 491106328 538663599 306346119 881231094 247504528 239653829 917426187 657871682 171302340 625659934 439444405 201497882 371738872 611268600 334650680 877573693 56556833 844273815 381659855 613541507 594777060 790359485 538766885 368127194 675822543 240090496 668575106 645688803 38064904 359854809 386306503 413582381 631312969 64223472 444657563 560949364 381690323 637909115 133577074 583406937 5446707 567311385 598350816 206574731 819248701 91900991 232480791 501998975 738122874 318436401 945622989 56886109 874919819 841218852 902283273 278166655 825618439 891100427 654682019 802958347 680290808 351805227 653994154 994338162 839175531 882282950 73045639 116284172 837419041 272012538 242789720 435263946 226961919 942346366 940334827 895597819 59290492 810521310 816104837 498346124 467376661 386414356 520748830 9346924 39540161 485967906 93347155 831317902 610820093 97692107 9881264 222990731 549493135 723992305 318330707 16177933 579595333 564630331 171654501 88366109 187266149 124995922 780763714 523728784 512830257 263940005 523687022 257763806 589143172 53531269 392559375 90248412 468504684 764733121 920654404 140063725 206345597 554775656 56376330 31511757 939682519 755140505 26705155 846823890 493709548 559196275 86851383 666912951 637261253 51005845 726129330 721265396 456996147 7795962 54620769 531660870 306037019 824308786 511755026 469014746 421443881 44994941 399300380 831646503 618852572 569494366 508682125 970688851 804598065 672746050 42248622 214003673 53362321 186842810 937700922 97046603 67436513 507779176 639955158 268558664 701622666 226804176 632437324 875670650 168337765 251988116 534791469 942872133 407716082 972062653 450634262 753172796 969037747 6829302 867673243 310387103 339043677 796257801 328165921 38901394 883819228 783377794 676489782 812858949 597132620 860593781 279554276 855605271 407131184 763292888 938914530 58322454 881167099 236829408 350432475 97153582 864565864 472779856 489804024 653719891 334151761 702904071 771997812 774606990 952070516 250881309 253090913 860080733 626977860 39889129 280657994 587871592 589842661 666926183 622118361 782976744 311751795 964744025 80404973 224515757 807544427 338690629 786086131 825510000 257660607 154590640 65893072 435472209 981643252 807289675 617593740 712554694 218511531 578228517 649444031 715018662 585838671 908997167 365213719 134624562 98647184 188788117 392802354 34314000 347523102 860774922 219526260 374230505 682241596 369708643 697356661 304194804 988958851 147687695 122938458 545701476 397807277 912386458 177780682 782012127 726481653 796157767 415765370 378306127 845054172 78189814 355942497 458115554 583822304 708289487 843028657 769178412 975841994 302043308 647335671 264204198 404044650 43650360 553466063 851120192 690409151 71636804 50221273 252122840 967429010 750511344 295870571 36806930 448240812 721019394 862633218 179573794 395017037 890134471 911759406 288986715 296028758 765342627 410562835 458392114 759485216 48765056 869290224 264260873 859957431 557866532 19532031 499230535 775094631 658018627 99408602 990517031 460985580 772160584 734578606 818030328 349942814 217973135 449788969 945776500 960537275 884352584 680595047 232611108 337664969 831187163 787748854 616154306 528652336 75067592 216406217 988748190 372294155 832282645 379993944 869869752 828677314 719470567 570293683 853533058 748485497 696256768 781823342 260251354 770782635 164822887 123213993 807867950 37924437 375462416 774150024 643110618 740689692 712656061 557626551 69781586 323944409 761391104 668286572 401142272 911195265 500291023 60761072 593764320 610902560 972703026 755838113 29270354 454266882 31949539 512447991 331650696 803562691 246984778 145498732 680084796 584568918 474727981 598456041 479353314 792882627 432529864 798146650 199756102 877452439 135924519 981759575 870217090 670160988 415118829 350949805 494406613 605611095 658981737 53859033 79714629 32905549 525691850 202789733 461863026 473559963 213546903 989114434 838267262 408414969 737916574 459893238 179006920 936659029 514696179 379078226 887170786 645616206 63763751 971688888 279134126 839971006 291145464 476188357 206556093 886997273 210026118 515107563 299637554 987352743 306978412 843031030 532836037 33209917 105269128 213267305 208992731 909039106 248139595 653174507 781690084 505985896 45383522 445487333 756180018 519188503 279871054 132678481 705533394 300856265 552933443 821132937 888006882 337158558 96561117 872290010 283775839 432061819 902192476 357453967 61879453 862690190 895258088 561270589 642449896 968808390 847578555 169502744 707001287 18060329 12467661 306062569 364995075 625188133 400698149 385146482 605191769 245860338 263410504 237429007 5804826 804881329 141769446 832900100 214398439 469974890 774932397 481833655 475057802 425238847 444016362 250649910 536672069 161295530 310776094 649821087 806124210 936430271 819510255 805271592 754111861 646198820 881489379 59688966 831948401 957352958 950302813 926246613 110968682 621111812 992343032 767549788 730558287 522880243 735452474 392835937 746253372 645554339 233896195 192793132 326129476 78871760 279069051 217137638 993500856 998282682 850514571 628695843 955330470 9251786 312366458 759313971 113375225 729526160 279169543 45631156 257527377 347021152 281005803 140375005 902753656 104815985 223734882 623711297 836575471 545533289 564554073 803768172 62528942 341045276 765059386 431548869 551691349 103764784 743015817 703718817 988199596 226261643 457418914 377408889 329016288 671779261 641303737 401815795 955806026 872904870 429915301 813772253 859103639 674743757 778832481 558511545 749508652 331325069 291038407 353023157 400904050 994290870 681247533 795418475 293519512 216872307 762000863 634254131 233704494 772406727 20361987 614387692 424954956 384184841 563902 591449044 94452072 216477236 433917856 166588315 360685369 722933997 388806894 341501360 273033402 474124918 283196858 976094601 91907573 746768347 140687346 953428139 206339815 292662763 296646531 791270785 698347423 690623486 253579402 647221470 238096597 576468997 967557876 466913426 333793363 179147403 467152199 471074838 367697895 202464655 539278293 544340326 707112845 291883204 622603475 597178343 310581504 40918625 288699806 350526483 109590224 159638788 788614000 917652848 15273385 346665950 776477000 492685352 739818595 864702965 896328355 651955616 805608342 503380056 927310647 220610809 257938762 818792566 414659452 659511419 914747563 104177775 284283826 487344781 409794619 17105550 835428536 33660072 338057826 951816354 704251300 260503441 679534814 643471322 400843205 33211768 690286336 241693323 21120261 882200417 949759033 129341438 1198481 751405811 190641420 100577322 919086998 953046573 331441790 232269153 228522096 809660801 467305769 533744295 591374766 527243517 812942286 378844381 495165147 770540480 739358629 822535469 33318798 745083300 22951439 297896234 197143238 234249050 355402150 211818895 118081368 921298645 202307327 946477313 754090417 624327423 21858879 258462975 194056273 123534173 12425206 680718899 177288051 968641470 144523206 178003843 466366372 791895247 791436264 533984843 727117154 608181048 746820233 13462259 833147818 462699478 129253775 771526468 703061145 80707610 4265118 167650713 246069495 176844483 969452228 307852628 484673928 250207832 869336661 544886937 127176692 414381383 60021655 227538326 381939075 243941787 106684971 95279792 293924702 727369878 207623832 671114885 643744182 466447147 891067524 166399060 694944418 538232607 143057049 188783334 476482357 6362867 57397041 537637088 50211483 285818997 765526439 82092974 718654894 355813045 259772914 752765699 481500587 563076324 643586014 373435490 337040050 104381868 52037717 437190837 35808166 500779395 740993734 332129858 49921369 605344292 474912351 495188549 791396709 378276292 156811223 13143219 883055354 197905650 258858388 927131410 805900633 20681381 664390501 814458012 881657230 186992703 922530303 770694597 914510140 393436285 30663954 797932369 386738439 750314337 891804884 617431790 745282924 241077580 895672886 975460660 243319722 81382036 413703717 343313346 253411631 742529716 315576559 501094868 216094341 42441849 132152262 680687331 351234602 403713993 207532389 491207702 200809239 674225407 529414102 71750778 474342121 956665082 849546257 352995971 309154726 175413905 909010085 957116904 881132962 15264530 745144090 653411136 807155757 508986591 693232044 864004920 900836787 115191044 461461301 564985512 844321505 247220005 165998582 45256571 620683752 664076539 38832888 444965860 895310798 917863107 543659252 639149129 516764470 557845589 387839456 948829362 445228883 588690861 174207647 628537796 788606028 956952422 941599302 98269192 119788691 322459633 715320404 450407195 925682255 554564663 72673077 493542126 194548805 637232841 627619955 630961237 561600435 275104686 485865918 335444468 41876179 51806447 911169436 636391127 194779478 151978707 157582516 948198673 557854950 606622212 779745994 938955934 292633089 371826261 626061815 786178960 589927576 302093796 417456596 569851144 159996238 417416289 207822702 125658108 127195014 989039891 416450726 412354706 493570058 919209222 966234969 40872095 137881880 210982469 474432292 477524182 425335418 903036826 414911923 738448729 527134706 297000589 879465538 318960446 436470542 559150544 143061292 360620079 272943453 40401296 62437749 287194579 446016687 505256510 273852957 173196561 353953518 751291293 128535150 432053151 628096390 919568156 75050378 254603979 830325616 451359639 953693638 144642724 289963296 888984719 947925560 831498956 257421975 259785961 607128066 770763486 408781330 791408775 337558652 895042788 792241494 778315825 338967644 589395878 639166312 648663791 454412718 330088873 227957770 498688926 241862786 632916174 654162622 814997756 145963323 910732121 905662316 60651321 94609774 157917943 714551080 647623486 367412708 620129790 804639200 158455599 474990265 879360349 279068471 830908193 979958850 621564437 531488018 726819461 85556198 267073085 662142284 250195529 457901922 195260299 767306405 434429530 146365443 378664054 265544664 295456751 584644489 558830884 659112906 911778620 472254195 479435502 479391295 600519232 65707016 269213250 647441985 648327938 227823011 833127088 433667691 788021965 541160299 488346836 104139183 122556849 570080338 475068707 708566446 338940367 146595433 719569359 612704975 219103233 892512616 971048635 373782953 424595654 178383769 447026242 96773831 141967348 521942575 364613613 228286127 459209099 135412840 304469386 223419515 257088866 880159769 814717868 153364840 573078442 508738621 202085511 678746194 454328607 909369709 818201011 269303476 925163901 672469059 537040408 51295002 45974362 274113035 27920316 595358839 389982142 565164139 659962350 157854600 73350612 452640757 245315206 650681633 522506990 316570398 849672602 626191959 999044864 611468855 983209118 155250752 868650040 648850173 862331240 46507671 290080003 986285627 849505680 472156728 87522017 459826421 761704565 918636427 584523460 509422518 257192547 247257271 823326794 455033569 844329036 76862142 678371421 870191085 973774086 842159440 239659079 307967902 413662742 375723385 444528861 7552668 286389848 522982106 43792022 258905763 483117198 509450347 645445446 176926001 579745500 356431318 950668792 731489685 760148692 563501999 171698981 838460700 573158028 519191468 339567403 955806483 948603579 582092340 72762546 456933002 836516168 677849220 290589267 696086823 670511924 769125968 8491075 935017456 557197992 551902932 730269772 338965691 470337588 340726477 572434256 317088584 592258033 218148569 244858883 325112407 759790314 923516300 729508336 283556101 569758941 253988905 239426603 370566606 749976227 384500308 643405012 507944453 697683361 24693841 535870916 714935109 119559958 743470550 973681171 64950827 584043172 273963062 885888614 545785231 632057226 889590322 141051988 713561522 407497295 115965156 851647032 482794651 413667877 200392581 393302373 212096704 292326672 994887476 55416744 59456579 233140947 621178236 948719830 353571098 949104274 59634088 344955425 209661534 749296248 890024646 938436990 681413394 235737207 772076220 753981679 975863105 833255 6604461 964338027 744486301 991248146 397703868 282262247 222240782 919836741 873401356 678077599 290262267 398558999 93189315 327207245 939667244 86614550 338825369 265595959 62658307 741874384 845815769 717210419 795204824 867808248 438996193 380990433 388675382 427307651 543397018 945746110 954619216 451193644 708172620 356256846 639422153 961179009 160405648 745254283 272027934 806102341 371911709 476062974 137078777 131162890 333844341 543559869 777679031 183608783 979698678 36132255 512396497 416343987 191133088 695519084 699841677 409939085 919577189 581954824 299549372 75635321 405768775 401326294 668464465 564511292 592333633 401040446 719435149 921990847 878852006 924720806 644075319 719480558 311231940 526035941 963723400 460799284 558682577 696489895 527845666 853739196 258519920 415987355 293505659 517169787 462283600 624247454 599101418 806688912 503005569 597869469 296384022 700956378 957316970 844293552 842326915 14986899 73847192 567924964 490653052 815242316 963083546 738481796 126895441 618011058 201258038 580115777 77030353 737761257 65718864 138363829 870520201 98727383 504476822 917623241 138512865 135391499 694334005 719900907 418766684 949521322 899762182 370563151 534907438 644352321 408477160 897053769 907348038 223905849 465516648 377645416 289721860 477385932 361574247 37866819 282614152 316063396 65950427 73712011 16747485 358828213 223032316 447125060 401018578 657428834 333468611 394507807 384966515 825774149 163233043 227493304 226518416 839864322 512951360 936734922 129646301 616234904 678656136 232076012 138953160 170640446 281151412 206625039 932760679 58600395 647181774 791880525 137796990 376746542 331697959 485426122 195011713 274543954 216273458 121168365 496124410 49659851 69771326 369641147 188642444 48942558 661913408 756337570 502565672 240442911 603800089 808259655 996373058 185708165 911568180 654265659 104364370 875242107 826609699 698248131 54850926 391105312 460571337 109326289 335953063 88207169 987782468 986068922 454719702 973849968 338174830 213187313 382782690 18022693 159831850 317922723 118973946 645276407 638250402 74595874 100058637 204912551 494532707 412912765 34092546 41885063 386486524 516139317 48259119 883952370 822280715 919561915 169715138 737425973 627099116 536544721 19762300 648183079 832855649 197059149 64721401 199950438 795006398 759604276 944751387 179932987 512741702 470478257 883574931 501344498 110588851 289529983 396996408 70344409 747968077 472475190 60179824 688988150 728492033 687499294 672215388 559570304 18257109 390188462 748181222 101659374 324126903 967414774 277684024 183628118 617312321 196655611 623267000 115004326 729841426 799053902 527614079 872732125 108492629 269011318 349855103 338355679 28826259 432637837 474651195 525184848 903455130 66030494 568256942 959182247 315613574 627879364 511814942 146101343 832902317 364721460 373993578 468991321 389123200 672712704 727638002 324889600 616747424 957683625 660806640 768586633 256126957 202917657 253042111 607039161 696750799 219382589 350478248 919920174 181941766 629130890 994748762 559159313 538127155 987875816 202919037 34047481 208738467 984892250 58395213 871146172 394236744 693484828 874760873 996038679 190140616 940115110 800335940 840435263 681974425 48277496 320076878 334905157 433498381 172162607 975561418 642976082 984383058 884208615 858040190 71404974 326035237 482642851 737274000 926138770 728941282 891971540 589695706 841575074 51178623 92603498 23363328 897578484 421230220 568752776 928861340 883429557 413372369 404115011 651346706 29280125 788092634 141767298 980972111 328935382 773167832 554137882 698002059 179477821 256022363 762137879 266784633 595271825 944667410 241963725 643601333 728488444 778169027 922851085 352930686 56159538 331841827 597530484 782196609 177696674 405009490 659672155 914353194 149277193 745775034 835413099 832597144 424212801 881603028 970446992 664939666 382614652 885797995 934638384 939173787 342422894 569521674 579297449 647923841 946645367 150858604 811819375 968092450 339235527 632837641 197056434 267938641 766205105 985993866 897419198 339160439 517654757 802671180 420949684 986497008 554235465 336401021 718801791 852758728 407516471 90251561 440814483 508189021 446004708 122893357 163172277 36615357 920540704 383104042 708317307 759123577 559290517 739169546 178687573 338790358 424474488 60670217 491882472 96332870 801752523 466215058 410186579 633033603 867564170 877123118 249501397 217513108 117188192 442417650 254237666 223197237 648453488 870343090 723771208 128015790 332433909 408108285 439980120 596663689 200306851 809126423 736037727 467781411 258832116 889691705 923647581 436850734 914775214 117270596 816078940 394975896 787051967 13533077 173468580 785948289 867006335 483230033 229447681 77609489 99875049 220648558 968047737 154973491 858112464 878740446 710176662 562045888 601765329 546475227 857176876 915817562 693248033 506994432 839597205 901549607 214617322 241285078 627985830 263965062 955467042 645666636 718761934 441987782 423698047 629883385 409215846 625090710 121303052 861993739 589110483 388117045 770624435 576934367 251010325 896872088 249478421 914494483 680207482 797824931 927443711 31920222 749820558 836466356 809085229 72149994 104505037 545102885 874564201 307714321 172337678 441156175 378667907 278889555 48246300 768829718 319600890 613276139 341328031 829129102 230626039 985682976 947558302 631226849 534121977 708906127 46939156 873648457 732894749 187428318 783367046 43787921 781758392 968169875 166461762 661421627 856480236 605041579 379536275 215052500 990415507 523247986 546638887 322625152 568980580 195248405 326492298 847508510 94700665 718941330 5357638 913936127 679035676 521964795 920258233 707720952 112171191 220542547 798681648 154477826 114092351 841829756 833406806 438863783 834528922 802033551 27824005 979836014 938224766 417003999 449442377 502481206 47591988 792136399 242046873 587278929 439780061 92992802 749655696 441997151 94256002 379114952 150331505 507903383 494714064 964278827 666485451 573776841 771628448 757180326 395103491 652991653 788633958 248401054 110375442 572798478 144701096 587279667 205194247 909072857 711529880 728223666 789890023 497506099 693953056 621203330 939340252 588575635 343414566 312680281 948447003 236667833 730486651 686270122 763968588 290438345 981641942 826237123 950932466 931958763 561710138 22026473 78430069 850299864 779650928 137998188 864464533 495431406 632642115 430694537 999677413 63939838 498830420 907526360 793053084 750004216 337064260 652339504 141589398 565645143 700076269 786198774 815309496 324453424 613069769 788711829 45568764 759360782 218412005 819485031 24669267 633366323 691080498 781141725 449534540 243833875 508061992 577987477 511891177 452749291 162223180 812814643 665049557 259126083 688771427 188060708 215537134 123454494 527992900 40543983 808728290 899730982 194571252 831657262 389464515 425293912 32474191 595681455 392576785 340159799 194868846 344159176 480389269 958058937 830549018 165388700 266158255 781856327 95279729 779058884 962467591 785701077 18330395 511390634 696472071 428872354 240325511 473669817 605318922 564747686 130624024 204439157 840503505 250596006 245109973 816305721 94040849 194208102 918542675 455376439 14408022 601312143 563129806 924174742 992144590 832675154 627580887 414765098 984344124 465840898 821422827 19698957 725420472 498021090 703487792 793215204 251532892 916412534 610812839 957420218 658480169 607774375 45829800 853996881 947423327 402345345 206261266 763395464 724502556 971552391 213369578 68418188 368094622 774513023 634310622 637328955 295495557 349136965 769783516 460918036 684367853 125481762 121092029 207584705 144701358 754016896 929183357 119179855 257006375 562122787 251207024 263927788 233513265 165582357 326391807 732619015 643940898 744721242 851696088 239417893 803940234 706510520 635568044 490790741 322343208 778374122 740750739 645529196 429449979 657971123 292952908 775905369 415483156 192272666 35442871 345764757 798143 463877662 526713979 310506639 142366478 246029502 569580270 756513294 507693089 690331403 941812651 240476484 501127364 68805113 99612467 669930613 798538059 528957587 741236023 992796700 347383919 641645121 518581330 59778759 856068183 323122788 403243713 936907004 112169861 151192752 718975382 220368185 52668048 342065210 345212954 376343980 135197019 317548618 106900385 734333165 138066319 331395952 281666091 86006149 421167906 963597845 688860481 58086716 7524042 237771536 602996019 150523314 899112407 302222881 872774103 934424551 339915692 755998368 785346986 917958351 510371714 502679269 320021058 252443115 81964967 106665087 928097624 796566471 535748090 705262897 231702860 124653180 676406036 845004033 781187367 542189251 325396070 506855422 362456001 805133938 569076992 914808816 132649336 537882816 997138068 572072999 534729805 112667949 464162830 13724240 257289995 56113180 669559805 181381061 993753377 515098308 876035244 294430730 211385987 141758787 946852090 353102635 357505359 37234283 538908383 453450964 632266681 625483701 838671092 807702125 343691075 608177093 236358673 678979517 171174233 743841881 205494809 764523168 958011698 275104093 735325083 216908050 228916781 528309671 745817449 803831232 480167192 619989921 452121506 304769437 287994776 268815266 161347371 679075687 67229748 944014642 291460109 947352162 346100906 720362731 13220370 182862433 745548727 522915174 75556192 69888044 560354735 402977018 497213873 746460886 485947505 472911756 170307792 308299262 244863297 563501384 381027419 840579707 149955110 891756312 242413254 859207308 447029186 232482862 240035479 219108259 460571184 369319289 931887559 361982711 978245598 431203768 288265516 856115076 526266146 166513207 42685353 279910082 303530950 440453871 509978872 62394891 483287571 294610122 140086120 780664538 131735519 298509603 897367457 844408968 383520068 77671977 713722952 547351999 160313103 346568697 242201471 669115743 424498517 383405717 15849985 573402734 570112580 407533938 639594833 444241505 209754851 931872887 127007998 362360533 723394266 482737319 439597174 411809994 326211537 773448962 557496017 148532339 606458481 91282840 579470564 225750997 20947005 436722376 197727549 815073334 393120217 955291471 786012659 634702003 795173246 796144702 975275616 226096171 333763231 424278154 121048268 805501663 275379228 351594697 855201669 707521222 868134984 133146202 144674316 602934097 785290050 592815047 421722069 233085687 355644808 980974256 57429691 156120862 10725641 408394813 580890764 590776011 921609980 301280358 831607283 818531441 77265624 395115339 866471579 321348361 526799157 235874879 838956875 846440042 982338039 393013787 332097967 512696433 359939340 171248963 79432746 458298534 467585307 604654344 897706045 360360802 438986294 531371165 130272860 252038094 288216041 354768895 843105475 537935494 471954404 435063272 623892068 407495069 637002522 930712000 357762120 799225021 130701763 661724416 819369711 831356009 122065269 570938967 268042842 507023971 772852898 838768289 298491449 867362403 896834573 633198183 894580735 887425773 572230338 302350554 816409212 664779575 637940726 918291804 162933670 931624614 34344478 759992033 462209247 25212640 742727942 197922008 254081541 589842835 999285538 485503512 574866067 176422090 292512576 999922796 687739980 876730178 535319426 124264963 875849375 777514611 819972337 616628903 607865245 665292064 610638968 173732988 321497272 409976864 816218589 38382002 64448304 734802046 633455391 884502483 786419360 247647025 715903341 216452456 348780884 683647768 160026918 909595880 435932921 994812494 247987452 852825969 328379776 574499029 887466796 722029851 860029452 48038200 689944264 410326046 822564625 657143335 482909219 525679722 47257546 7109792 813375777 966479966 636804179 949477275 39185579 379444807 545053248 507255419 477734191 480738531 863603152 750567077 797235855 734488768 103928697 585688631 794608079 351823210 123324908 476420781 12054654 13869751 764977552 71697457 69334502 69181781 299709358 133941071 63084995 236042715 920587852 360862056 19098128 708135063 325088908 693885329 951325507 295576564 159826525 442992292 575463106 412530138 827910564 579076814 411389802 203201204 815682791 980346830 251492416 438630528 475786644 804734288 179776308 632488267 542232480 728190154 966009748 707048662 930066596 646152484 493896664 386479612 900983517 74411344 228632097 488748363 727644572 792854223 412035434 137223013 875116667 905215331 709353906 457560478 87610020 930118039 523548567 697446805 539610129 952461622 807522979 721532659 624923593 5807761 747800983 409164774 551190581 494072384 504846156 287775578 443083660 338970828 759886724 183857915 768071571 718908984 954740277 854812600 336174142 737244012 967025270 199991923 147462036 100855290 453779206 304295378 483476241 983188221 680935859 783256912 238326580 189791609 496752217 807853102 102831243 82983509 103530154 240753022 841198307 662509676 870633666 795410889 401198456 887012862 991308189 979729638 788867082 328654827 967823394 855521032 255040558 753047797 16057321 273083591 861163057 705619070 812256841 601224019 749386928 242060881 873110134 667262377 609269672 474346158 80993472 756458441 578315786 945453779 878531724 495931141 311561531 955759668 290013244 700000608 801380382 482469816 702384361 85191207 683162556 628358081 559754502 683391758 925210693 137345779 182991877 192630302 8077659 684718692 769307949 59088514 901471339 410674335 145328595 357879222 470554845 35114339 280277841 220941994 487245304 503498194 615156300 657606327 828139207 931823432 97496145 532978783 383283652 272237069 175944933 821690561 305084500 447981124 257415823 230372892 377031284 290315080 534509512 38074872 377055714 277982461 963051507 182526819 473093375 222571067 840563227 400848822 586267011 252192702 604700227 372559199 489217815 155327478 150695373 702051315 554882930 141027386 145262126 478591668 518751646 107172240 584353961 626295969 66501702 270526701 687866919 27571353 773286067 325991136 283031328 330285835 338067291 220522172 502770459 756645050 908927663 481390873 179454801 506474906 469841081 770904335 916270424 383437775 544681297 812691692 597607335 421551233 839890912 749730071 936029258 205158619 846338128 423959249 191985191 549685767 571359807 404344343 167391765 506572815 351451500 734378802 270084316 739574291 87026395 359018579 304858121 373823596 131442313 386710180 828386603 193658629 353426648 760589126 920133875 473062743 813747982 917650840 683271091 103720979 869097345 843823626 427418756 547128397 883247155 154084445 380081226 735531151 169004130 329313892 263930667 284508320 301166761 658818598 927954776 618070825 902936986 671110802 427616831 348379287 510805699 182398637 583200126 708613938 952330309 128237881 280788700 238294339 795345321 476771914 975139999 621278196 463157287 314427811 712459275 118699480 102831574 996236598 387149226 650065226 448450151 423820887 360396840 269978522 172949036 242179291 65026530 777326116 414697993 506647613 553820404 392073696 942823835 114298895 78556121 175011102 450398016 876714481 100489801 592514419 217812064 982623277 248072285 549585211 759192348 111489160 544246328 334994308 750704120 266521680 239709178 779463616 51353457 594916893 288938510 875005052 806546116 60686917 56522817 298711417 579537242 237968007 157590907 462095932 893887564 643596948 68609832 150172297 456012256 221346692 945189101 304837745 176367087 74281671 82828489 830339077 608738556 226165931 832604815 319849289 889804364 418303583 393241110 725625419 105171058 841876085 580800639 44731424 870344231 264713146 823235116 292931129 500668236 145422792 125465439 695419555 809124710 49093436 102380188 55053277 76351997 636532451 837761004 804930885 546145909 391551212 981778077 128881516 920228105 988015061 172347207 962925241 514300152 198244721 136937660 328905987 646131413 820411554 162198598 7080840 885483436 783027272 595045948 681264177 440075624 136265994 577146302 932606034 230288852 105701944 957517443 800055261 383248878 267706015 240228417 305744634 677558186 394222870 21228478 730019465 831532934 525378453 639862917 802170832 342948840 393997652 533214837 297910805 46434331 48150505 31508696 673055541 811150847 977456148 863319014 59849215 768820223 582758676 181066473 942115175 952226737 976135870 38137909 203657642 294484919 798365476 592118952 398501286 254528533 374463880 773836907 878603940 287281538 355815320 716225583 591287407 171887917 749947720 478861033 182668083 34927551 278698266 53784153 941637198 582496483 26255521 480955431 280220173 927892532 336909544 857279906 283119141 522696761 488212138 858208680 670858660 547231362 572455449 749292471 591197181 662063631 639906612 211991235 65187560 38553417 859405228 490668048 141145442 297054848 458974916 549034895 415524817 485005213 49773795 55261754 926759662 785063755 85585897 65777680 454283117 973969715 680425641 523094838 101614876 89043121 633721598 343713380 792898258 222459814 60336003 596490683 235417770 327673635 439130242 229867470 843099604 746071370 117376004 980531805 133706640 756274434 742307917 374584985 984590976 42033961 811997877 992204324 978453645 995921068 493602241 517301749 829660854 242348584 947279301 562260938 57168446 533874154 972086757 10561737 872913784 597259183 183076006 502038721 725828423 466109803 943498349 800712739 691459409 452057333 846355529 301255246 418897180 458253387 550917384 313815809 516008874 162014438 942952285 577221797 425852723 878059305 951948191 921527134 15698040 18691687 904284759 108741062 402449240 302303543 559455192 246781214 105982727 470369387 905060657 245399795 509285967 831841 536019085 252516721 873668660 977005874 435741859 286708688 96763046 589580114 328025128 531094942 112565153 657937516 703742520 125741254 426813058 81651507 306735110 449220475 271549242 870621667 197492686 935760523 528134648 304419440 67784474 330369099 672456518 377857795 230278416 726904559 807793292 761522571 885565333 698333528 622105673 860876236 144942946 698004792 549547107 635901057 68169300 940924707 150611845 93438962 449228477 330062087 297844406 207505734 492315808 268079402 458946697 132587916 7286850 974168172 464484201 101902343 856840290 613985983 289801069 463218385 79220505 418139578 33280349 267598335 880382865 574772239 309944751 190100263 68922665 901735805 819967819 404563464 81953122 380433970 409593163 257432724 266188404 511422621 290220185 795279183 521423731 299818671 374036688 810892490 119279836 999108015 625041234 994635437 817465521 167971756 448448745 445173841 448508679 768297530 722821914 164104256 362853901 341770223 137018100 946118260 279803539 897219023 627807064 772114665 302367150 690172732 346396030 293410954 145959863 486569751 987656309 865245455 971699221 745769898 213467702 985570772 404770992 730803254 131214510 588420345 953442052 46489717 541717838 397109510 452384568 382407822 584379090 355587694 324002389 589573628 192697200 383440631 704142998 960391671 340887068 110116484 824638311 718811226 807940947 255181372 885470805 281147724 724111561 539602751 216271314 313037417 863132737 705285418 131778545 49343859 974757505 325683320 90520135 656602103 502537250 753188752 365760007 203605568 769455508 791360186 950840975 736425250 880821137 817848951 687756257 496120569 149443430 1855323 519275558 329529236 658924479 580675317 197240785 852241894 289175020 452037229 26879510 943797821 45528278 589422370 479320912 11026824 821793383 92566068 446871219 69583229 980009503 184466364 858894984 577578106 361729328 117568180 55517729 799624120 423023642 347520835 460709707 30580287 428918429 734636235 719921169 94585407 256577186 171168222 468339436 121250559 277387360 770380011 302095328 87380049 201893937 529506520 34235984 302297691 164576117 975384519 420813166 572506129 207662809 749651489 644180243 784148203 346420661 155425838 334824391 166578386 149817460 777491105 638329297 483952742 201356652 152738548 226510777 708868630 937469977 935793808 222731967 614355208 982899753 655078756 984603292 226279499 147508047 304652620 179618373 561513542 710710834 984551434 656060547 5275689 551677800 125296683 509668066 859543186 403679160 138074885 41636318 615587394 895934815 400472512 925098384 190891837 949439575 808057867 84454905 999218722 652587131 942504271 311800134 327377709 148877670 83616805 30109266 362368028 210760179 14917109 360975388 687356300 467588683 424970726 656562501 803956403 940551153 885617937 504283133 684562113 223181675 828840390 548545869 636606808 74071796 446449063 900212294 623445933 154896622 992803816 32153299 427344009 876191109 285855239 984482520 82134828 343027738 498555320 497874613 105390471 273988956 332062517 192579357 858208817 455714918 131336921 210186091 808410901 437202698 385056990 59554427 190934711 86095384 223279890 994251011 125535134 592535863 782731990 793481238 56583389 971060864 772290846 64392999 647400712 950305100 933107766 257636982 691403968 842815750 339138950 391410481 559513261 47177685 724533272 634005059 503921613 307153882 823382269 859037146 527622542 218841287 390265332 525410150 77153483 966216571 243796343 420283331 209826662 460565290 680068579 740899889 303847353 964603381 184004965 908372781 673986380 598964845 407765092 919851563 271075318 303365244 122065208 154080280 914498490 980895525 174925365 843899691 744938426 700604807 60429457 242329687 903519497 508463566 972901331 527286911 793024450 161096048 106274423 49339473 251752861 419266049 323160579 442315521 712208859 867770860 686763207 366799982 507658799 187083711 473545608 908695696 524569610 154712977 411770404 358910977 290475906 921412829 815272684 107633703 402576828 326089561 473041920 911209126 912745410 964265893 476148968 595284537 659745564 172325732 36162449 706336384 881999337 109872495 888923683 774053415 170881642 888350789 417505564 462543335 328735710 13667396 505737266 209417329 168775816 867873940 958049482 821385940 986992677 934082341 465192185 198219874 239808406 793077263 303705125 509603699 698278566 480041932 986177324 517046827 56161050 559488416 806312093 462498531 554202082 543992088 837769506 364132196 630913612 407070325 679825660 564226262 700530119 379192562 341930369 829998893 757211546 582844428 420172373 541386364 415024093 579859108 881550558 868110816 116205723 553947381 609372749 611484266 979904568 81830754 518075922 151095405 287457609 161711057 729980194 30942304 476922563 276669692 335982542 570727955 481057657 888315619 782959318 457481036 668543119 410427780 468867469 310969486 160713324 688343353 58313787 127313205 27845147 359123372 698170541 42927172 553532017 702218239 491164977 574263650 676947222 361908044 70795282 327253977 161949265 779253711 584724276 955000270 687382640 490157750 375821503 30761651 903202788 421436578 16698777 171079220 662032829 870126801 424559679 175485934 133207660 649208127 866913042 970521676 86532933 284110246 237695596 842989889 230816166 158703539 249689867 568580564 863079221 188737751 721179629 498758327 959326769 275571140 219425932 712772666 17369149 892624648 229647478 948073037 487063987 589735851 256382881 725125164 898477975 459114843 38646157 270011956 685999571 229177715 634265816 825277243 504944692 803163671 349414778 927471459 670165912 379378117 568477528 793557859 15494684 221872751 113718044 449055614 342392593 371668283 994629899 572688590 740560966 259955457 270848657 895233987 422665244 771522283 469582884 484591873 703694529 330412766 584609544 631647798 55665193 256555930 631267092 712132081 289463185 532989234 867968972 593150960 712256660 343573900 615289113 773375810 385008289 35904208 234894707 595193779 939666307 150799273 24076230 533943149 310839117 473311980 525703357 825024646 255530568 364327960 462846636 385894404 122777883 681919656 886978781 682988116 55408385 497720798 820838065 540331182 36928412 632531353 835480133 708662831 221406431 108069004 680013198 473010217 167690420 300358127 690652467 258866714 607016357 110292600 405498396 820984063 269668839 938466033 35451624 332886731 643244660 689788478 360846821 837316409 411963059 52852478 771318450 669891327 900206119 289376722 624424065 327542723 750686257 170269245 413969911 276625399 906418243 370476446 219419997 119224669 124817290 97233952 311255833 570183839 725403801 396821300 254034821 602840146 542977928 914491491 199725339 154254623 296841687 90342500 762524392 586019359 130274689 104922680 284270644 186119546 182156518 397767912 804595904 32998020 652720210 551088336 99185722 50485168 565892902 153222175 625720733 342748662 538531972 174857407 57465911 295288815 693071086 499515299 771185855 910693844 714293161 909574563 307562036 770553161 842014198 529481073 981508870 32520605 949678064 519761570 964371441 383085583 539578245 95352433 482725267 153607069 700188629 35647613 482168041 214476772 306553660 462001515 330519194 963031433 377326016 721105692 451343586 390738662 764074888 75350860 831500437 125858732 281261640 284082854 688524105 992853871 438406847 979030409 136652398 502105496 185851331 779835207 47545375 457576555 115935174 745214198 918452191 84298395 697356922 523886267 441337166 280096988 379918343 335856130 430391395 209187082 577626835 399744504 925877758 498961087 96349215 236695638 595644756 852811423 702123445 457774875 515305440 899978529 312353298 928644393 80826379 444063372 958367468 329998889 532445411 661968043 191298766 434797643 903756314 378947553 455475440 936852271 756752732 74907088 55961477 907038941 619553952 84792469 630894858 639141158 371918338 237979371 894733787 808837969 975061216 636470834 753034537 454003357 150509701 877557899 22945168 788144531 38424638 324905459 53236836 120382350 252204123 130926481 823688305 417448784 829757426 622762196 203583798 313357764 972435955 896778021 114942482 554033174 873622980 284536396 613572263 968591373 576302803 619563683 941824369 229019752 420227364 99707183 452732848 926680865 605965826 766608595 329885604 500471579 308846452 595972232 946240482 104887342 968225439 166827298 697298759 379307586 687897557 379367467 431681385 696154383 77010713 619407043 133844584 863692952 441004091 297292251 481078175 501463013 730321865 561702537 99678203 594984303 199768058 259963680 3190422 80626080 370469817 136084612 809679310 370742634 79693078 885419227 964196175 404337329 984951068 112592953 604219330 526586171 121932060 79361391 585748311 960035643 18226667 429238907 989305784 814812762 941039601 158770077 227916185 7288928 624478084 813605638 789317108 734868142 420790945 771065217 247973035 266739423 127159097 152206525 997246314 144862782 768688617 598717203 830461710 843741000 248663878 813054359 689780523 840453394 246242651 29921537 935304410 137661284 13488391 212655221 446104109 515965601 856889804 592958169 897701461 983745006 510042319 223932527 822855081 336987321 422933420 998632489 113085085 185819475 884658016 596422557 283341879 740291565 138920930 842900871 898298828 668629793 274797481 847005392 943441326 573784288 427147234 388377151 749442627 32269593 814684907 179729432 595898488 368495540 57917639 438594390 753641609 434148737 2495335 744753410 858751620 772424040 320456741 260235409 849492117 774963885 208417919 976152540 798456329 631079073 990738938 234486244 34961355 18753831 145914033 580951080 974749496 666347437 413950854 474344917 592006359 42130888 977104557 129468632 542459624 114057268 62302085 582468636 448601988 520952463 84166458 892363295 273460989 601669143 435570126 139085771 199433570 209282996 771352428 601443863 469785278 239751019 338465264 137768260 386708499 336322887 735284931 974939505 682957112 581956438 67062821 882497827 785368101 957689720 550473147 76878262 413855982 590651900 417341988 824540140 94301917 614208551 518594453 462681020 763529897 742696459 483935552 84864851 701885513 74352454 182108235 169522652 464373250 959023257 555895109 620325343 42085246 558006410 334668773 488177718 436401186 890897444 118134388 842136340 429995663 110692109 470190839 370250496 131117413 905380539 124384458 659169175 915360009 527870940 187128829 738307782 666023833 39401328 975665288 42520352 880873287 503852508 399176838 997488973 718333326 97657221 780598757 423456593 139838439 197673362 889532968 817656839 629630326 112567486 347689695 790622720 510257596 801469244 394844073 779450571 551513662 481271522 16957605 477386433 258205479 95136296 113120579 498244433 367888546 844473734 248074546 133853355 798218330 338504852 720537390 733727862 871975474 30210815 511391593 662729800 715391863 782784179 710041792 264385351 617220838 125985934 337984902 407378504 283757818 582174127 958624616 55329602 81927523 192947598 346611662 471723792 690578791 155057825 994714227 631743193 100701105 816857274 655927744 635782945 424948926 508669606 389431799 193156812 491836649 45130755 195829125 721826339 267802830 366905879 795273619 597339952 374224901 104257231 210069018 687583568 225359227 709470022 317179185 444782269 984262955 987849294 896953977 670107743 355070568 222363968 683893402 783833877 463840984 285932010 384229032 905270829 968464007 552136683 164622135 104774006 866467027 229408768 418043328 405197054 209933356 302996121 148494624 564350507 24660569 994518888 156052297 676002026 610509356 581143585 98309923 605200237 952368006 555646468 799426266 530644461 915381033 725388954 140764999 288131372 250446145 270831316 928213848 290817871 9566101 782144177 802130997 44670504 439427068 280958897 744263870 576531311 771642743 662124313 534535810 926027092 219097825 946561619 468385181 707179139 653326310 67642875 320765937 917724420 813000977 817401922 855947821 298981195 19994503 827878414 256041647 700822884 636457725 992742816 967162405 160044492 715885299 164311395 515010597 401340447 107003496 853961715 556382570 110560318 651747673 449086685 890284297 100168573 116012675 610002568 384295852 393976836 819614299 415699858 871231418 364692822 232530563 79157156 753646083 233388843 506986500 131309918 150799671 313509870 814643675 860396297 575396858 328966052 403168710 456655318 212631393 651555083 978389174 395197597 498513578 229504163 824059235 759749473 853484515 468464027 714459399 984758571 318897005 680526859 812832803 438793710 766348602 442555330 405933932 594410037 766036635 189982272 814209163 479304659 705188660 774635038 59596896 476191493 683107683 690316663 418810404 381822773 677176708 956934863 899852054 463829709 261975017 991228979 965796328 204847756 348267861 798989013 741865906 716784770 202916350 703471326 370108292 705717834 615813325 852046235 742196212 283277363 54300838 644849999 216364277 932542336 82336329 179012829 81751790 776143128 451105831 61716644 532773912 315233646 742063602 128484509 551857658 338909713 238140167 654740026 199219188 714758430 70735754 414304214 80640196 456111667 65217222 647623504 456856116 207088251 469723715 637007515 670441070 208946434 587097939 765538745 567151063 305996918 306190527 122998955 694645637 723170604 684540898 428650155 359956507 163025065 869762114 630588008 961956805 696905448 207312058 573885183 19166250 144251430 342508242 256499583 868442131 152987841 476337369 497008796 895673470 273924886 227332273 324975186 303332107 676508374 679682122 213291538 954618958 529907010 851902695 701583477 592850763 121891341 875234155 854519712 536596524 37251348 674335307 546240390 35871741 557626774 362052088 14790796 379770853 459138747 767931772 109838384 292527674 584234870 289228378 452482371 139684138 286367781 418842832 136577939 16616085 524480542 220227824 498088988 414477606 307185201 434401768 915772782 503653520 163211324 393028963 610289199 692569986 812256030 815910862 272527175 240666330 460702418 529918708 652280699 744641281 136251147 115824485 262917409 68005391 152599182 443615565 714093604 641578099 730893990 311164048 313489579 171180714 952763756 477905475 621026102 942102392 266818655 958717149 223447712 455264170 743678060 455498086 537981066 740578262 73380880 855815845 215450010 108300004 616511586 357248336 988960163 674277472 719858809 334950829 883613737 279961273 596178470 845771985 651568067 41407054 303119145 350994007 586669009 7635537 194248763 964332725 335804826 691636336 695573327 993124677 41112631 352753052 191169145 136270522 108139016 367009391 307966496 206731719 165336304 255921083 58895394 226617935 305210131 54216634 710663716 711023110 767377483 789836812 731694449 264648667 563927467 828797073 361068314 90849 718350707 1764317 184997091 998786404 603784503 190837163 593801734 602165834 260988212 243202976 466351607 598430713 698024602 242083436 361101005 742645782 961742542 447154126 989781689 581365441 687397699 122497783 437543221 396489023 961063809 107498542 1292947 831651440 643223055 280184623 557686277 35780707 105099076 773490048 191637363 521177303 132062852 515274116 20256515 487138085 373197108 564365842 863687971 44355660 28896834 978054866 933408328 886224551 594054039 903021260 192018994 115763909 945776275 83700721 843018489 848895426 631152739 60701984 410891633 854923529 238895176 850838315 901188608 585309207 563943550 914646571 424207559 219284649 880716882 671984968 964768713 85941001 881994417 569595541 75922119 264082935 697120508 719899492 330454772 953574677 268264501 992538539 347516510 108657775 484700893 703134895 82373074 361293449 215591513 977402233 785024118 583218342 94741332 125785022 700771562 596791992 515785841 795858435 497912503 218360781 912512647 772655859 117753018 639281439 648674785 133040817 106215539 733671064 539052352 242747025 279441881 41507357 970397440 173659698 702232702 173438251 274441727 548187801 721264976 622044071 966402382 348679754 698356052 386338804 716154454 111023553 987944979 313640394 480648250 663225921 116623158 70906558 885885275 989576552 488367014 613556193 112965482 903280088 490826397 479453912 707420953 573481807 675566581 25457889 873562645 268874034 911405113 488874189 204037148 515521904 151996968 525358450 668110585 461660021 961787736 418299331 659520067 279489457 517813721 235031584 780097829 570086807 904169752 704015645 728897046 107800816 102232076 979508437 469757712 420354897 207227109 765805072 737067435 229608069 168851780 649242848 140159325 883392840 69670346 449442647 944382658 948998930 792813259 82082775 412103787 955301706 655598905 775612696 483846257 338655580 473526532 358056350 171617349 471050505 715577468 534643233 688600914 861783548 848124904 656189638 983294624 851446814 958865094 45283938 61685156 600775655 303167130 605202881 634434906 116382876 472715092 50264771 761177516 280406243 83591670 388254992 1055018 467549020 747161031 294432170 14945275 591621061 848419866 418267377 493550263 583606113 436339966 540432136 943794944 714886376 578958609 52020481 376549724 720127626 491997420 886786998 785517708 564202607 699225375 825773710 734217903 186108788 242465464 990355408 313629257 415057352 758169012 112600915 297131017 779648583 640291060 126262336 763067554 406735804 237800529 612539549 707589086 74378571 366434489 566254350 552031644 507199494 345003140 48676610 212259266 867688355 59928727 834401249 7596434 547231925 840024136 218147032 449438424 469748179 793340754 355237205 888671309 653173347 403255403 726030893 473784517 549639684 829788690 964045521 746821520 224606032 805856829 321241539 343911516 634461222 237610596 943607349 284800576 520941837 145102982 568553958 192232724 613979661 706273942 548546786 397258914 394081280 462225230 942135892 88759739 137416786 672013990 632820768 967046678 886674251 994934413 435635740 521906476 324863078 83714923 76699039 544915410 121830449 719825359 971889830 993830384 634794300 799277512 920190590 687559558 643103738 842318216 330886194 10133797 156812376 656220185 952032977 617030046 670319231 863658452 558341654 570952266 718890506 984803489 271458471 832955569 569738207 386054869 465662172 880195732 282140714 901690793 595443779 490591627 630278833 575378617 343487882 496788624 30722455 925314740 241357929 856133897 226586426 406946923 816703200 173343744 691338452 33863524 852399237 920314236 424570282 909167076 397576116 748664139 947383208 11999207 336943325 232450745 313719392 133241303 96645610 605771543 723118427 936189116 55274193 423433965 786736884 33773449 549974602 342158258 484231644 509083299 169920241 442908969 214074767 948478638 997315763 189597999 593681814 583679691 820050313 191176847 340447790 160549973 522780721 418409362 204572326 543338357 779241472 956693363 794791262 977655869 948620692 161048436 918298171 266074642 241079745 743649251 282569342 257279215 329881409 287387174 329769894 654928114 719524640 846142842 847420442 467009718 596593213 774951396 800438396 692208319 967024966 947972182 940222928 602499345 730099615 251367291 907082701 201593915 987886290 852524602 302688102 266454255 151141839 402809680 491841105 358991931 966426373 356429774 970574891 320648276 141336121 500918994 427877000 206404615 485784997 732793703 66645452 766732806 930055358 56814962 563624850 670917832 150127531 500519435 458280643 211829418 490723808 5563238 273718445 933786497 73603604 536985798 375819923 322404481 621780348 537221785 483228207 468536604 65821344 55089892 184617022 629663579 407777389 538936126 815035453 164103515 962067423 80596910 379924377 603929805 344173520 410597255 242986190 1896992 564093311 391260698 869840887 563497028 69578890 262079337 801302359 386377645 465390313 918363335 179898869 202978300 250166659 845306624 435983233 602776335 711416439 9532707 300981375 655734850 730813353 917942022 200510272 469633235 188613507 621932484 934567258 825407189 231154521 649330052 989469647 668679558 338116617 309064772 565946406 364013556 325117122 971922968 99787227 166458866 930010379 15000690 523717909 778784792 805189563 131639666 702906220 722728966 800787975 791491590 688613551 731603941 658456157 622283349 740154819 48490082 426100023 621740813 169664616 462745365 95376883 758305747 599158019 298881384 215958840 747960131 290530779 3217144 759463760 668711304 862774344 130599665 683836037 436501512 636480299 512346537 737098944 931753893 964792287 572913126 240740711 904584340 289785114 770358322 983407479 607314255 346182844 538259727 551454725 498804550 40341063 105495402 379085816 34863487 991304234 610113474 151265566 546800517 646056341 77076491 826036193 786236158 731333408 223382103 991342060 417330883 488366975 826852322 74900992 774827789 541960994 38865030 149962821 231606770 985414332 392335908 999062212 461794476 947645263 285414048 643327631 59011531 734636489 524372572 727720113 353148867 491070875 64189636 255605601 378410968 789788984 307861384 980324615 11465225 55423834 296449810 131861886 773854420 67902884 358240108 154459089 928318529 701282169 232334067 685732712 768454872 842836845 951950007 873125736 424416421 767409365 471402201 878485594 791271972 676992275 541136231 412946954 544418964 181774119 689145101 64386383 402077891 280352504 715113457 317153128 516354207 818962014 588735141 517454185 534171055 878011160 15704118 435338435 244700850 939256979 517009505 80859926 586899988 303188443 637568138 866165614 51391822 442595852 197577418 98555626 354034793 416490395 43066222 616036575 914824411 973328576 55514957 51551525 332111161 795935988 837110776 780384825 163782937 805209301 371364612 721334793 183219924 611620051 467922512 585681025 91924170 884803972 461863577 929994400 478649799 331184081 926843115 484893942 969488951 471902578 683446195 690431509 920227221 445223266 876336508 138758203 215741540 186083483 444449376 63369063 527909100 444167692 668245885 771891158 414786148 981350610 731371635 318035524 708553688 381348610 784634496 369911187 599218145 135509118 456291076 77973328 367189562 105028926 436825566 158096282 768797030 539546246 403704782 273809487 840689700 41233863 73320931 126569621 322843567 173150886 20597822 770103416 505748359 768230591 311071685 794820851 455927819 326024761 7013874 942362007 253665814 884074892 595541275 649364714 444182792 786992978 20053434 142888126 988438997 523885689 676470382 611482394 36020882 234518786 933976578 605394552 980047178 685557560 144234195 745049128 799448054 669949264 250545097 784718255 124441647 935375094 762335889 192101025 205090454 267452413 459982151 340526520 326662417 415049226 31926616 328730852 709895308 116825279 751239882 794839290 930698898 836037900 828898129 50876208 159550158 481935467 362348759 944929872 408989102 370711641 731228835 138237068 552375475 543374309 450154295 202651835 337390269 217968758 511866322 237134001 545039722 310493359 706379782 782788558 11701777 39638531 123236068 25154569 245772928 944977392 203059578 294821191 413728325 902122882 708161118 633821619 689608501 870273910 113660209 407930251 546419258 229080597 665819611 386263471 189711224 346261403 940320408 705699630 234258219 421618179 335728825 511156704 755511492 107225185 539943228 43585442 575821714 178490011 48099754 619162596 919567437 280703691 259240484 195362723 733450964 195521398 369573609 650609809 224955086 6013341 187809995 820070850 104747247 263731818 27100424 754445863 426246848 305791652 406959783 826649353 751592630 647298917 718083420 241003532 622569468 477153769 44483871 424352994 751634010 596689037 708788434 512207062 995628347 912388280 796917507 83758059 29876164 486537998 498501628 372855004 932884213 932720966 798845154 72420017 955755013 670621326 491410423 245105834 505698320 902289525 239811358 437746730 841013746 547000059 521787592 13690572 439140584 188409876 616252518 453172906 657757712 474962549 308498753 700607824 805630449 697758301 815901488 688867309 493983617 108629615 165599748 789283248 461227255 923417764 395619908 773985031 912589820 867057585 715356512 952315430 938901299 915551911 266787407 499994053 11366378 400616750 340031664 232495166 756749933 167225413 680090539 989352480 911764817 978412946 637840965 446044427 726592983 772444751 946143954 371964705 451990444 232303669 61784522 235773294 329028496 103229782 709443068 396325508 872094852 58374069 331006975 34459489 198181016 106496451 183188499 341258669 290200198 888956901 353002505 489775292 889473311 32487352 606324121 868803311 715543075 797663540 468924292 145765929 793773258 1332617 493109886 36241230 224106006 275318576 344865388 540385551 225121587 4233554 69665751 597508860 364046492 338832954 204376474 191156556 877311865 779352103 942697842 641761978 208648194 87601278 320136885 637345052 229325939 834897535 850320901 893381361 161643682 24031549 51776945 263924867 529100177 197648445 881827269 693167116 701050396 258043435 244110931 376050862 821524274 914786408 323277578 600657997 162374625 586033869 318399299 614021004 365493258 824378255 70791049 424908760 494455710 576934425 349478492 867094110 164709957 737997036 811544266 395435426 52349 939236179 734080575 643825848 830320441 717510836 750391355 531324675 14625999 58537585 922568945 48376188 936998205 581546055 341997745 830706012 668717853 596400529 914409416 856011957 858734264 450273354 702234927 717862947 171988978 608770813 170858703 472601722 730941052 21770474 317577582 857667501 288228111 933897577 542520924 390365006 465024841 889702203 26115542 555848395 49822554 810710018 445473034 162713458 176334563 927248090 920916052 390341067 13537418 730706767 679314835 43939150 782101576 917224244 297023644 582874726 983325666 943114713 895321043 152568931 446550831 518765518 938693665 420741746 533955081 57233081 223934626 751658999 866601050 945514242 608543670 518824891 424085339 101284039 599317834 988307822 368994452 135425818 442529687 109567754 144999263 633480583 592385310 252577702 226684548 353670999 818666050 765795351 602689472 638478970 570375634 406816261 319035379 628540376 628556206 898526929 962161514 256037262 261157350 545634137 79755347 131620865 791844599 698107299 843427925 549354137 881272818 213867719 925026379 853544754 314974556 483931419 10152684 323776110 596212849 884267958 142072755 969396987 54464260 937378836 984997232 664466047 996268737 203177507 959329797 124696471 970351580 870963237 6692536 51513608 194111584 338986458 449125340 58277019 496808849 479192314 111337646 352797102 693797908 258920978 461379222 502477786 397228977 845567813 736147387 231502505 318659504 31102816 26941198 192559900 684260261 491668028 919880393 597081279 633246636 912064849 385968658 119452216 44816045 131113871 937579207 904963758 375535053 197185375 898460860 804391255 961477100 734081643 612154940 369812542 563338969 96479769 918102965 203318434 759613964 194067702 158158382 411406372 524980351 455943577 30689179 811741432 551273271 833407541 603382835 803285020 910624981 516430381 766268429 765632152 294279464 270543845 796393878 807251907 679624505 3703175 520856456 540399048 356380545 286227803 759106004 519729601 984196765 225749470 321381507 65265611 552970017 438862451 681793081 929263973 672259436 109648184 654939781 584573121 200037714 105830030 933553646 252820824 853504678 166215457 767820381 896172342 528015242 381939829 244811407 633117064 269622947 64131436 584281874 160803288 57920491 465141600 846876513 259643157 872122268 506069589 328341216 350471812 748440564 364440360 547659148 842249244 271521385 843727691 682030227 888111593 60099634 340052525 76536683 694739254 964748220 809458361 136927004 887845695 257099675 224306732 449135574 260517321 345775963 78664105 687097633 222701028 445083376 917756333 348207441 676807436 778212865 753437987 175661619 767058781 407649725 141894392 793996541 282165485 305666804 314973651 527805520 304694429 893464910 186037420 440818582 931722599 739178647 621547682 718640626 523371939 703549504 960994898 947629258 3460664 600550605 440055694 452988864 130814431 889803037 533623457 443956514 404326179 369365645 782704935 13326892 858380025 702134019 65402756 636454426 336307696 400813564 426614630 632082101 973206403 187282138 13875679 274195445 722937904 50078291 155977542 538524721 438663166 990010806 481937945 456109271 525907054 965701521 87401392 103489005 876245381 728441447 111117017 593537310 343551825 164609385 839154994 243252201 375340706 623050714 423679409 722568116 451146192 277327801 772680074 420157244 871307350 635709665 485240114 219907542 754073212 40577836 725749419 495320764 136180400 350762149 456128338 156029002 363891519 518142898 842340924 313731435 723981000 443478903 269212684 80805262 417598554 883097935 817800790 776113237 409374479 779796424 943550781 413912105 767860564 954762421 664023973 980792840 6217225 670334543 734054921 71387259 498743590 20679172 62667874 19868537 799089842 951320126 257877048 379443739 177263652 400052097 306860850 805191530 687039275 812050028 296188437 696892707 572645493 129364433 390238558 289617985 626222751 610571566 70295677 310633406 920126456 655809436 863503658 242623004 436905524 897704617 2920145 875888408 350091663 223006359 854908273 457644977 893659176 109353156 195532988 348647411 51969061 462430480 307009355 182119976 873559644 104674392 831586290 841132438 275515424 3139162 589603043 236583326 340765677 796729048 201626275 244447855 819572361 47938480 29358455 646291496 252935275 587957557 477403545 252431130 272539253 41527428 706512576 662852403 809972195 119577561 618106815 196414432 663406162 444595455 442649364 638390714 717320953 138281876 473996831 809833259 561162914 829465113 957546715 599636705 292652571 442199237 567021393 319622183 212217571 137025631 26568238 426226898 769163933 439679610 836900793 301569031 548805821 912803985 87670290 353287204 196499804 153447369 157406781 567380918 886220817 217661358 471294061 240154991 545096121 218336726 737458746 598747626 367520064 451754243 24294706 847242546 233831902 626325885 163692918 167156945 493762298 142143704 765987867 168816659 60989510 618597751 592917901 932434433 337886255 239231281 959225205 703813167 284970928 125424206 791251217 550282856 299536314 152599607 515191425 777495826 475487771 626983227 316690072 514120342 938787457 426354389 389593879 977284684 666385775 1742021 165517252 588763532 183249486 87030697 89694079 763660849 300570791 474720261 390878934 384812291 544774286 801813559 272177950 80234250 232377714 10212154 691742006 143330465 87466192 54866304 86459635 563809371 247874614 411880515 338199699 462657067 936069854 237365268 948620841 428756135 143203612 841968577 681573290 429981997 239713268 435313101 414827391 246879356 786212255 6956663 54871067 186893493 221973405 129096729 6415898 301082765 717451452 872939477 857342401 100377271 708511110 592755394 468499694 622320532 690123962 86621456 835745658 611826801 84065942 707823159 744063071 13043230 818897675 976390663 695085668 544341509 300531598 511731212 947457702 111512739 443529613 206344116 883601296 796801661 92771769 595890754 74527605 334329352 752660121 355016518 743458093 941455967 325626840 318199717 343250761 308899800 505609327 154612158 47805845 238046039 101591258 85025550 737972252 676948706 382908838 846086423 359129247 405306450 723599572 489866327 219639596 382881476 225152565 837187238 659870181 586453045 839904593 345326484 652074987 112712644 147126288 826348031 803343622 865035939 303621455 845932386 461224816 672208800 280752844 575604758 524424852 638317118 358242955 264918285 527199934 875435751 328837939 466479733 478399631 896128373 857391877 684486334 420006428 654810021 975937084 778285491 419814707 991335766 324622061 240157004 940561201 363187238 751074530 353019847 687363894 418302799 45477534 935839564 821264509 256224984 760800263 339311727 857843842 113788339 966763021 253729644 205889011 969305652 197904111 190238554 952822184 935789764 829229676 190423352 183252090 293295966 494169418 890977373 475215504 738141390 646266596 726562212 71738994 903364465 979991376 536009015 929634291 500669643 185862902 728931455 58647283 732460261 772064772 7793211 724666484 991008711 795953510 492650014 720111028 398660092 616254977 929340621 444500475 164678659 347682957 288146090 333647809 192174289 59175127 175882281 203287006 863497936 358874916 52533293 709833242 415427353 358343525 377257437 805356113 32119655 555633694 989239959 381972862 33669070 850067206 812154308 334784429 153786797 802832008 818337134 693848812 382345927 183121435 711662515 306838805 260817489 479001192 681492655 664060420 24287081 72421341 218689859 113893143 607623269 755438805 823841730 908724699 589636328 787819022 13284600 966277733 571924015 247620296 147409917 538161743 811436841 97135146 140875479 947484718 215806021 789938079 831268933 353246964 12231042 17587815 420196790 954965014 852196694 465404562 954044375 890235743 328044429 143391796 678015340 368617375 793110593 419418099 609557515 899113298 868083229 775389518 193406104 604993777 533227017 620220474 712779528 136055200 213655174 330419987 686825529 545377335 780124909 68328461 832238026 498063524 730244404 761004514 653039852 740674947 733054130 74931191 784662353 769616905 811504906 697487352 535373023 808153790 449438513 823201953 594202665 753369473 801587992 811934841 419763892 847340276 265748146 68679091 626520317 614931876 786363714 597668970 401473146 358526818 779121770 896846905 115211529 350597481 529014019 635207496 890331233 349373540 231173626 876428873 474708068 440501508 87640927 665553612 893104000 532469924 925949677 946235358 121053851 475491583 116192727 265422782 244259389 83954519 151110219 108915730 218545781 531030433 416803782 83220321 498648809 584469414 522922897 601407888 631588951 357868270 601559767 438583565 528711803 699509307 397548075 205439799 814722972 809991200 962069409 413182819 662358851 331695595 366345163 372955461 727450006 942485572 555615114 721304234 1151022 510423436 173799724 93557503 94116753 168683608 507220680 782809096 188348431 860728965 35989976 746499589 111013796 921619101 941384292 627691441 263997039 376196450 22954696 317685238 19059091 858680616 878044343 990508787 127774095 469006472 607196052 577369357 577889835 164787281 427254334 282405850 339131383 874707317 814303875 531431530 938128693 297399804 420903903 563826922 924552894 859540655 591531845 904787985 657060463 210440986 277701562 997620828 746822609 319965405 285564135 192918461 233012300 887664370 949540959 30697410 631158081 156331207 589438734 392074229 189844324 353886255 970017573 666191644 243148255 784014235 362183622 783907478 277702584 876517500 24780542 676577080 293536953 636193173 772129037 256414989 550157126 487514795 162282059 831035358 599937195 425065126 845493472 553526932 333982180 959376771 934100014 112626884 174920493 937540631 702688212 955226732 711146550 977305374 58392260 931232182 946428693 175389535 159810792 490509617 845872893 148582497 881182028 457513341 166779256 453766910 539709534 305948309 454328883 304862889 928013510 921314348 486194696 263080830 49279406 369068149 148283265 778540077 384257276 375798043 860190116 593243945 439004869 160290361 747542375 301483962 638517031 842571674 364675775 257942691 443380446 859343342 975824215 543600482 959316958 617138605 310078111 609031937 133318697 891848648 70306034 201306088 167902615 626215381 786810741 459393925 326390354 314923319 75872710 972053239 415266055 990624843 379734841 302074063 922336738 897462057 81300479 954194321 288125330 464142046 871089791 125023292 990268864 920421605 990669424 553498955 496116361 90713374 750264587 307448240 718115009 151871234 473224579 368064442 245402261 476814508 338103278 227219821 57989181 739981161 145212017 551639157 947619649 348354099 389879869 181766351 352911917 40657991 518285450 134917537 924509180 790516175 665006045 809513098 402542495 653456769 628865116 138042675 942949754 634638180 449253072 51480442 927648926 232036653 906966851 862177934 890599032 997512295 3816955 458433285 898655534 374816406 554203940 581490774 78070811 545430828 266681541 922130654 715046474 665232617 100160910 842085107 380781295 498145316 765733233 306972333 470207738 827050958 624848178 91301939 914513451 358452434 436635257 460329355 862878185 289165857 389234528 309588048 482294199 973592076 598580068 582295661 837592317 684362865 384768395 900353020 756794577 627205310 545979549 339704612 710443777 693997378 611814283 570409589 199748875 519753666 250384470 35908612 115396622 818498658 624089894 226245314 310258511 898121034 136102940 420138691 518239945 119929096 718930076 112253251 836530325 150957343 696438303 394998169 232364180 750150729 156168701 984911138 787071569 109805421 990252606 74256349 172477246 878249459 122484787 701121541 695719105 79158168 331607260 467022809 302971578 427557099 284146098 159575747 665795769 406299530 608148041 905492418 826795403 745581009 426462233 61518762 958266369 863984222 934577456 119173453 150576856 898893572 571722313 815846020 872759828 374314436 392468405 466870008 846055173 438413722 481833283 791434682 917134405 702324856 940661426 287364259 503049196 93219003 402798578 163031223 502360416 667902504 994674887 779268352 601944615 976937166 354484271 256726470 388110978 580702174 791472414 746385627 101497683 614945396 340968953 523510362 74257005 804037506 742990755 465469075 406869938 852903265 226531670 256021248 566054440 786747377 320238352 786208182 90059794 895868780 69833785 282527546 562722536 746592576 983142318 237399486 974023956 257179443 395535223 605072444 407091501 256366333 227477439 218102257 688353481 621582574 369556024 690000620 368248106 612528501 271176281 336600477 798933266 313814565 261654372 972044052 221232311 182733060 589532384 323425972 195814184 235600418 365879542 49049270 825377031 844395194 342843889 460710361 204465916 1468347 140206560 67951112 443259306 907532481 993355931 974941117 797459528 38286916 339052661 264705675 538414739 358284577 421790926 185511239 914320759 659720069 684677888 265100851 916681338 322761077 626793006 815236898 89608358 497844674 225379310 233869633 666089086 245349649 981025189 805781181 523239255 494496754 547261132 247764136 356407894 916057573 447003113 380729790 637850896 859765146 964198077 656695815 940290709 842728597 735270694 150393168 677310226 329359642 846584265 744467840 178382006 998231867 186868127 82240308 33074665 527397363 81154615 694001366 434561010 776813552 679606885 266107634 37831066 542273141 801056162 771374637 804843883 373117794 332126061 842883625 552826233 900550376 973079413 551066469 654070033 798829367 666104781 43388619 983457719 583846835 642526762 8529852 23676812 286957919 28984035 346137515 956273830 497280330 772965152 437022765 195066570 206187832 119245613 474264449 61247534 275192726 543915641 497742360 25965830 899711854 646818266 1834451 703647147 18537752 327904937 855714870 347099625 238773082 940388438 680014556 228991527 126484636 786051515 570639523 140978664 519269738 720439012 751196542 859352919 276633133 439888246 905165179 657804268 616406455 252533807 770457852 36764161 99989834 508419788 458276869 755714972 524557094 206308300 152786341 456607069 329795055 845412662 824157622 899493913 973524137 223081786 146676790 743523882 552751342 390465899 876105321 533779371 188004073 66530572 820811851 199050279 223459746 830787726 635110671 830747093 688475937 730507355 851886914 842318933 524720351 384602360 176998934 367115186 491349335 248037989 133292012 958980751 871751954 672082517 134397432 591244261 67659901 6646250 818993783 954087524 650717600 110520067 601430831 347047425 923201180 147941224 404811324 21580403 526768350 61209735 87073963 124412774 505230314 416008971 200793796 349299893 149874666 504346508 528835091 439001404 716745394 41415553 608914572 213715642 783956255 367843885 271340639 399279735 119201090 529004271 707640533 923898867 991651403 847117650 26796222 150284331 319742356 393833712 519627789 403723337 426130662 988248327 98623514 834743777 77587977 998059852 186427924 586520243 865586300 822971345 244691075 915395835 693208525 810649129 702336163 363433297 663468370 557961310 292827622 68122290 733157296 867786504 753989179 62964548 512749412 749478094 12467612 206304193 824785472 644351199 969445103 458237171 356558342 404987450 690793654 228175480 553664581 291175943 728680297 643038844 98188044 313577043 710903706 757797373 146946147 335741595 384537583 301120082 468828381 929013512 494786612 431030563 512666466 350453420 655220449 546140889 693962965 639980311 535577730 810555104 122679865 559584062 91104906 825307333 330912043 59213933 112247526 655189748 428469355 9359353 789147543 155526712 95705623 73231600 141796480 641906687 385347504 347651560 603446249 143710127 781395396 790554491 496084126 854212072 423230703 605962476 856903723 310447323 702269390 442558033 573442739 578879082 307073012 314566740 55057688 922845016 637263108 384438768 448686550 210957539 271534262 97401742 522873923 688227296 138014197 510554540 36781472 506705927 861807098 38169006 180950294 301691821 206356044 49825788 174787784 77415241 138378369 171297489 457885092 575177013 847734970 551227814 895703766 488688160 491671773 158133583 121019111 639540620 992705040 985419977 543101540 748830868 29496114 368109227 466931284 591562433 97371396 730859348 542351116 958894535 710051840 266766495 648737159 575230267 570952098 475916416 748840492 953305060 64265463 75549593 275733000 409441558 390483261 229405925 318263945 848217405 531115056 766145785 6203148 383674795 922622608 705186091 828317916 751492738 73743318 793866608 301981287 817249309 696434736 373966172 559840430 709320568 634388224 376284152 497482068 790519592 990774431 807533695 506887917 296163508 204548634 344109980 600299935 414364335 108459449 260717960 573947730 943897875 73793674 182116264 21744882 138053557 792663102 119772914 852044323 186953483 849106134 67054529 731586123 3098118 811751387 768771099 47051092 562280569 343768316 779460944 808980519 555743638 431669937 86839929 153057138 370820810 285863163 448673127 438786856 490964654 778995977 338211320 473104563 857081018 261200559 120174391 522140855 447501541 133689859 484761034 106972772 558635621 388542557 800216101 443370020 564104868 66889182 637727116 880558354 464266836 153457393 496856730 866891095 392001427 998899613 367124367 754429310 455546200 756017925 374423131 449502916 360891417 914177877 47441550 329207827 763456987 658967578 28855024 561759796 607225775 502200428 724679040 3411973 844012019 683714038 428806772 305866087 273429922 312209369 149641299 63486103 805262023 188568648 472769551 563917660 121884229 557809173 152580399 484392003 718795193 481417883 564238880 269736375 274390292 9842570 351746920 796711733 381517135 850738871 861681641 671085894 811413706 773043600 835699198 69851175 145359493 105865432 557195454 695290235 484613731 97714883 336339677 155964249 114210001 176693731 859195590 121126267 548387615 889881399 646704540 823083010 587446838 42747643 743584596 67377029 547519262 318990298 872585917 381989800 768324581 239131578 981513434 461124215 579015602 365851893 443419932 576103601 363045803 178607052 276089294 119244854 816680077 66934116 964899247 352373831 770696648 313972150 682844935 81897514 151582426 971558557 921353995 935829667 56895027 626631248 803603974 858565173 969802420 72876658 598085051 674878865 105596632 151215895 885204330 584666853 200358159 376926796 232928850 561781348 590466254 385903692 536226806 638549563 31221037 577309676 609759168 827320384 407048180 256159414 157545397 372609426 501429652 815591394 187318329 110527350 908383597 491093968 912394407 126217333 51414738 48600038 123350742 836207927 935446530 838475140 690051226 809701386 382183547 451442685 642276352 837920429 34497284 403490607 454217180 432472490 284973460 493737294 577548085 41232971 969494384 727777291 198580895 982915492 780298793 200308786 13972872 592886548 344197494 558428178 652890312 358124320 453175851 801778529 451448157 960892092 267429236 443820433 567026634 514906901 756457876 403060274 283114537 972039410 282362153 181577382 417741774 15142133 541741888 510060990 641496828 2472441 648390064 762516212 542853787 20423817 200321763 378261124 816094727 147699359 154616882 957056054 754602351 181156471 953679455 458390461 87991428 714506816 148491928 982433617 419584567 785806911 701460236 321207340 368425926 83789737 955064257 329846168 879562281 361626598 105544560 277122351 504088428 147352757 678978514 499051852 118352734 731277312 514815980 961879895 850702403 35274215 555157883 369820720 421046816 69068252 97637819 576573888 162990314 999823067 703830283 579197768 248730394 733155236 468846100 385931553 743802383 401028142 73186799 851258169 625375324 423018506 15730636 984642477 244917410 123074067 337527230 489444776 631791458 711625441 134706408 227525324 572195305 529566476 180453224 591098395 382567829 763028477 993489830 486664795 462940688 554293779 882451549 29431434 538747333 631799519 635963663 978904117 735963505 360921503 40436906 796318552 271964530 921078880 51338074 154327889 326061465 829345025 849321380 260300485 826116197 766310433 444450968 609416505 464727438 906158563 536259929 519703756 113253783 874304615 449578339 367806538 642575057 933361850 369444487 156567296 870062258 336947974 619745564 968701460 26974774 464916722 839797802 77827046 928047333 804485871 635941096 419862204 333833623 299263498 182037161 7428149 840120523 553950733 764923418 952077492 277670122 602231324 93897289 81783817 918195217 802746580 650686631 217824463 560748790 350874163 672525839 677349587 72718461 361379824 916624558 174120649 734138928 601824550 903083093 993933224 166118019 442992092 136049456 160682168 541774308 458980363 53452211 666279152 961938997 800774306 52828784 824465005 774886432 112311689 930894864 416124879 872741919 429233955 191566044 689314229 620368212 410294091 966921845 450556499 107100103 337319186 31215620 137143030 263405080 892486955 606463247 703885873 532739855 768704542 734965773 799613443 788084968 340135330 928026659 613110483 304505295 439851282 276997574 185427755 149481173 290163227 372023878 316059000 721516926 971895317 700988910 993331943 318575699 848532379 403046931 892434359 944713493 974324992 212840056 419115182 761249659 474990573 435620411 766530585 84252551 348472397 628837937 531006539 625865647 311274711 458648577 390626809 41939474 400385252 966445250 661833889 883643267 286069859 63393072 916143810 895491018 373690788 888473234 761164370 32187930 728578177 252319028 817181674 977167596 466320891 429079006 37913785 912989951 758702406 220953296 973628441 432908245 865059465 107087557 978433807 59125047 283687968 436095997 816422375 645173183 725071990 137082055 960716076 845086283 396152706 479686290 213598493 177436092 657735305 636089974 422609440 618904597 214812404 462681152 197175189 104036696 151278912 424439078 833427805 599689432 713353293 83535975 604851178 323453256 510135634 236429608 173163504 947089649 313925245 981138246 195063388 312961715 49995676 157052422 185616275 918928547 118573409 259828429 628999396 352577254 449940876 162157644 47218194 706898036 246657163 631506242 737461902 415285230 741881665 635679315 97783419 245228399 470155342 710429318 715912812 45280105 155848835 780896018 215889764 547770025 39572163 390837075 896896782 780111514 344280890 267757315 553553435 363437023 381608939 55078432 290081292 84059055 474751648 816860365 465738948 660291320 160582518 49567323 235953364 637377017 211169827 439118541 526023785 340891527 472485096 575461821 806090325 972451576 81133244 613645893 918223472 915040601 309606517 771009705 267287473 947612637 931416334 392106140 292215735 680714099 435139820 879587725 563239393 387597386 608609222 971471408 681168751 859636420 85221855 941509907 936386345 169693641 882298116 276853073 680860306 427599317 704972099 768017798 992523857 709942207 928205807 841457729 541324421 900291374 130790014 846231217 119004995 715159209 989797336 148216187 590534783 448712017 146367496 781902869 825331513 505278903 2147867 527953136 319037596 971178531 997485922 765530525 696894193 701414341 690896019 417491460 167285531 473382681 921129943 389070107 701510145 630529615 136357290 350631290 654305091 725752816 190690681 177723110 155212265 540645583 152244401 198991294 184723747 617172474 717747575 614469464 825419893 390125498 115430639 853558614 120455918 231605050 266930446 396598801 222819662 140551695 998663235 369230015 572219531 902834676 750876108 833484522 994467529 908947917 552680721 375275774 636914404 234765116 254719980 688969532 828299269 896374151 956295166 504034344 306364835 399319257 103771790 78755148 995630555 88710256 936949499 982214755 753032953 285144871 72504050 336146460 468930713 971030403 864314843 633375575 877883001 270146579 612084844 854400025 88012909 487880946 817297124 812148780 820148286 194778727 548705329 997723957 632604438 663926802 205983670 642457776 596604674 779425266 997618365 115047918 7508939 116758014 786947597 580993187 191598789 979520880 164178855 648228510 973741643 972484750 435836505 900961492 699506041 741906614 109407935 878792451 17546988 583256626 659389944 948467238 512242453 489207708 511502349 572004183 294928640 755173886 967070224 915982789 509062237 318442761 698520640 530425203 872179205 348253250 965648884 142215732 25674427 996682627 148948596 760170787 463723331 235700196 291908904 217760978 919191752 697981517 597196131 440116661 699033560 387378392 887681809 983987786 483409521 910667051 735301077 852774185 799638146 928732676 743922323 394499420 265174681 488409602 928501032 802668701 872239616 927265940 96835775 604387685 815847478 596343964 908636047 318952684 686936721 865812687 575333304 906493588 895060669 913374420 114844600 461217551 665600195 1608437 225185800 182246503 681502878 683089031 399489233 490367918 248238970 826018036 729906362 973369448 440211545 653945346 823922648 1372143 160848391 863932953 742367324 911142662 521521714 548675440 192274621 132749367 404158363 855716732 427350047 387191780 753960461 872741820 54262793 304855567 379958710 870476839 426139254 41161960 285482032 130479744 457325492 890849071 828443858 201632838 664741882 650060938 755222160 234008378 934004883 582980030 20398229 851878752 756091534 694995450 69287604 817136024 471311689 817477446 552786886 64046491 919762496 968196262 439185128 84338088 986699904 30005537 287696195 670121403 642691624 547205379 229479684 90308282 606814211 774044600 232662782 834555232 732720819 282450139 633502606 283808621 381034113 168033547 224964885 552317021 924728371 764388918 717507496 606103233 381133027 717048485 322596146 774680654 889117640 288830923 923975661 390916751 266459049 456683643 254307304 262000494 761692199 363719852 443963104 759150367 787788111 776256287 230345400 802304959 673775051 135009188 395844677 330995611 351812006 205535556 876902180 107039326 594842692 874928525 169884853 209392335 122745574 20912330 153727393 257049863 962957358 747479976 625014112 739603289 112206932 329974119 936067814 361116705 283030483 748453596 905907285 857894762 764923847 531377533 984353052 30838951 70052740 394358724 874854148 12943416 551937270 964185473 405256309 54010361 580321694 150533577 111324426 434878859 600017369 86618001 973229861 459427276 257845852 892561522 408623769 502637709 554237465 520951333 421991152 153701980 107564617 426965762 255433600 811364960 448968909 322687599 997481311 848015585 284975744 311628717 238511632 84168258 82298924 486582937 171382703 842045477 770948639 512600627 318288678 30322740 5201963 775275228 24470238 982417756 557722190 770411297 957255537 181505833 176044993 375828498 175534689 679385626 221914089 156995372 833882756 502211803 365451207 772881012 586682286 747800953 83118676 520898019 106373645 580092859 219904673 262667339 204935184 919586602 950117182 445699955 915140981 757349016 96628840 68274942 462107595 367336168 954346188 705067921 315558905 647216546 241257182 181319765 75103682 140257664 369775192 255948117 64109323 575385145 269518649 634343687 220140351 555728826 982256886 397895752 12695032 239887709 131958178 254327797 474725046 612001323 304101146 431366907 90730440 571554972 275363273 20103660 46924382 305732007 463592577 998548479 285725580 369893890 532042698 454044126 38010079 162774804 130340334 128512603 403507221 768278031 912666414 976260677 215660458 592847884 858629494 639554857 293595727 840200328 306733107 229639053 718918253 231166653 131904808 462420088 176414761 535615469 434425772 549570440 298845808 647292104 526384114 435550769 134749994 72963905 890339393 814167268 379407201 530827077 219994302 797070758 462421349 534808434 425176120 435943955 15560916 181319809 324480943 991624756 393082281 326165549 923063024 740832602 275983426 91098354 943458816 684272018 908252312 409223184 25442815 713299460 674886041 6296656 704226944 862837304 656435341 208386341 963129013 647248338 905672046 791360144 362800837 97572511 879536207 109698753 877726611 997447300 843302987 279934386 84622070 818002322 183442239 919283286 967111538 228728065 799293674 760832009 85964894 566138771 23552820 952204191 95250752 466116675 15709589 634617880 151321987 506188066 341562736 234575952 496270110 384397126 497207879 485408641 734692131 92786975 562006505 229424425 897181022 370762449 113618857 575962111 728879170 601607240 667057932 965673394 748022416 849751311 249805071 696685538 487081903 964916051 427576278 299842830 409863684 322853157 546793236 275423387 580476177 647041220 73624128 545757464 225639927 417804204 650373718 699295601 355669563 239190724 867777152 420179390 129601172 114852915 248890037 826888480 826224671 47075121 306926000 843822299 799880940 518322077 449619600 117357788 8981708 37635113 434249230 196349386 988985726 406388188 163800510 184577867 573243554 864166664 270062434 179332842 434577655 446833045 603489185 17355314 693817947 983175881 358590714 359043113 129149714 334888127 733393217 913774353 173223626 942669976 481920046 686037339 429267502 24713592 42382289 640277388 403402321 291570732 52995257 89334002 833459755 915978457 553899208 560103469 476252979 840270123 279008031 564359369 150580950 13600986 487941258 966780034 223911008 241681528 125352148 568622666 675935118 6951148 970351001 48949853 181746204 187683214 818354122 740745316 836837032 854956543 183193663 910942445 783737455 149091651 999024831 923094106 545066005 340254041 598863388 214420793 380161456 466176621 297115637 296102653 48237943 678552758 26561146 627807391 963518856 958134806 373488730 238202072 564830394 947659008 927500317 358339091 976776989 742992777 328882161 529285552 189369770 267501215 290516594 889739829 621927224 725193667 107737467 852692350 37900898 513842433 299683496 86088083 37628297 802927873 383649511 778960994 919332102 855020919 220656013 186659348 424740271 779826569 983831635 671179866 625641670 902016287 520604852 869034691 881461383 967448266 620666125 221787938 913065142 575909477 305468743 159228361 452386321 573205534 53019887 676701196 831141324 339710322 982177320 273077838 726949205 508141756 199173241 184900255 22813190 342671314 102042198 402732183 363413113 518352202 189085250 159967169 880436577 477075616 773247473 838437904 388988965 213037213 901837990 887016406 140773804 194485575 695903626 888364168 688902755 260720795 292515143 634726191 715381954 49605854 437354905 46675542 779833159 953799600 227649195 309577830 244037426 959131071 126491854 366025040 83216003 900685842 775146151 135192014 408949 705526394 851425721 740237058 825169221 191287149 116653477 209428737 796884932 782131397 202637120 953196072 588966040 974338430 372845677 125956989 113054370 621324311 766762177 751371122 440677755 878243297 362577777 510000091 262375779 92222016 745756735 735560845 139230729 372390591 16460296 928001803 28762090 654399899 943350514 291554902 579728916 385092400 410492363 166443734 130853421 257611186 533762474 70755344 707281321 215937693 745788757 414717484 1121334 414506973 360986718 451180222 287933266 361392831 299412326 944280160 749192590 804204600 164832393 527251183 479014547 319853518 157117004 619530040 520603654 870052277 970201563 280352188 503986487 675476302 620752012 298831387 839284670 110654935 170853761 385340456 303188392 758613262 941078635 196116486 707184132 356652374 666058847 389987509 919206114 392316537 136983398 156403218 448120143 334189542 662156231 906863701 618100801 32281804 6630594 883364609 741219151 13365767 882151037 866774061 686667143 782170782 433030728 763976139 993744333 529065457 941322239 51605057 363741712 818749994 550342616 580607603 985120603 854288619 668343524 186033389 310233320 640479017 39638435 715724871 338640187 225090553 709621575 758178406 220894168 82190277 599744468 310964021 583856525 41997585 250180108 576400677 491735300 344990369 316738925 410669447 26838701 10153044 720450871 96703917 96416890 99858112 191410774 208695178 992917764 206124201 656874808 176947606 832153211 963824811 718708312 896625421 906174564 677579168 601107055 209238242 600928083 990723872 384431263 523164747 563788131 749208312 55341665 976376716 935589233 828539358 970659229 968683822 272903479 567110188 787241999 355657650 262093354 108681352 986985531 11315166 740658169 212394250 532381083 897104225 455674039 797758738 591435443 271255271 761126796 55892184 771875277 783789346 86171984 45481975 136444197 752704762 897927580 517160234 165274051 813244613 736087189 171003645 99015520 99583222 97622406 373391063 555159484 749242851 339595486 392538389 814990884 796618883 751253678 397507321 377476404 747849646 585415400 249786050 964494415 19336865 732813706 972913986 374239528 304068160 363634755 493823721 876884610 895905541 692192927 94890020 788332318 992466109 835208869 93308713 583737579 360557175 422154829 495515284 953691827 9995749 866684629 132239781 602852484 654974593 385986463 412832573 749356407 506645922 763631247 41482061 852259640 292026700 530543435 975212059 181072756 818302036 174626772 292848060 264777971 779022893 760490374 44641158 737459882 13328857 294175352 658069163 129445667 948936285 935664531 701796821 33913465 965380742 105022481 701910459 624789064 774465394 356704206 453393066 651388225 541621818 860804282 45820035 21557666 906191653 198745227 336674634 855350376 203957494 641761736 877361774 471240848 674335558 416348982 783783627 241083264 565463417 533511568 754517809 726067749 995817481 287010854 494955604 88713857 742947778 114338514 994154303 705400164 536572747 896778198 916653005 154056742 595179021 559248894 443750202 345476128 791095536 516393408 162719714 501801077 674801344 690933027 250207878 846480627 285101294 667374957 100592688 605493909 175447473 451369062 381902911 56297378 241534152 341874272 339969850 880715473 209297167 409183098 504355823 309330910 521709562 364385665 784877681 544920747 616813517 969249093 961125244 443730658 380090757 234700010 769946368 698563396 617350188 335577376 101117671 474367259 849682912 246535068 249330060 479093021 967704427 14633040 496379409 949935643 571787006 951610295 561189712 572796313 386711376 480779170 984575413 203704468 212535628 320608107 776102742 57769380 851383259 243034825 154089258 169961110 265799509 644208763 926746830 795943121 232742053 435880638 271870534 414050922 849445947 539722053 152754478 338511123 245303418 577424009 490962966 95513663 713552261 243277080 434025394 495186729 539153124 303823431 939470677 959240651 889957647 704918798 316123505 465262324 979944482 429446136 354671455 116432543 642807123 374848994 405444616 523372337 302777440 84502748 439094478 260721089 829807578 329081061 163245315 327003961 770000475 155988158 106302189 947651670 233433633 509185093 44858211 982691201 262896846 404953129 264173114 482467264 175591785 91225052 875934660 23674033 896686366 566733416 479704950 43674880 501194137 916453061 602670718 838476727 714521125 351043831 179145309 464453458 826292890 251566383 73565984 78055299 841923682 543820054 336986080 722598965 37520436 549608126 807568102 706347813 230392384 702902200 658832428 73002624 957339525 377404262 685618472 796591269 865956340 317728819 646066285 506759845 110849225 810093279 722574760 85996706 454865420 964050533 355166721 497750432 26340252 974745886 211962655 638474913 454928058 395468132 787341509 630540256 917785381 142054278 378226381 625106404 216568740 371998272 881727967 981387922 757702130 793385493 814095713 439986496 303827204 90408223 817033843 664784147 886502200 126097825 184674333 73592615 456535432 728901598 935473381 3591794 409957459 620707677 678750619 500099826 48949080 301931174 189494231 600819485 610261148 269767069 685292335 753005145 723269056 537807911 252448961 289220006 133215068 785852248 650751061 718718743 66854814 918917954 547295400 814461092 786211767 202852649 903551445 460638561 825061214 3940311 954307670 522940555 137523394 442374266 38340263 341690958 863462511 394404957 744854115 927455411 699342127 639752084 322516453 861100654 273257518 410014331 978682628 53451835 151665929 350485857 407305512 930541668 800265229 129094059 727539019 166489245 641610355 128152929 801466895 974702094 334750867 961296922 423702740 724743142 740320033 839836469 529502700 891783349 817842479 133749906 912985293 530813979 493830951 335992494 199721725 361988240 308585652 696840200 263351888 416288113 149547415 447754126 872529393 37467697 569250218 746713073 868221344 496156941 709943092 132121597 713292409 936738198 711517916 270289477 448081747 290184927 896720438 720312122 853577734 752771077 742671245 229250299 700321574 926260457 940428721 248254514 422670564 268731288 104275787 325368074 137285290 904884063 518182651 688079901 832641159 966253236 166111149 663925420 429846184 910449621 749757321 215483718 156058062 786666733 684194153 542604977 153509964 886883016 914665753 713170955 952155117 706392130 813064530 685798324 101878388 975983665 12860345 572614060 877160300 206215718 2345595 524558886 164519405 18959978 580682254 230191707 390582332 719701701 775103046 678772195 613767235 159760990 886053261 227117926 8945331 593009604 626399196 781805983 723520060 412253571 787117519 128563406 881454078 552861956 617991354 378557039 72838706 496250390 693766217 846250660 939181961 355875491 770866758 171335612 60730901 377916359 314417881 429744554 355859593 564783528 964937038 987681020 480268275 496183047 231685135 539119578 763103163 292796038 805088557 37635884 986301319 620448506 180507327 495977767 256447074 856671930 247787525 552983531 475762906 955552041 5298688 78519988 788991556 850158385 184170413 408152203 203212374 189970425 446300884 487488871 363225688 215082443 980323937 93678125 870067994 698048855 87875530 61893771 731227379 556745948 221027169 317192641