4000
978138193 840753354 580025448 861661691 989509667 507911739 776561416 429688479 563578300 538378491 489607783 215067216 6042138 107012507 957354789 425597790 762912403 78190948 148426841 715586688 562853275 699707518 616905472 62391482 304219672 602455959 382458876 599887356 793296754 834169525 947127963 538768485 815657702 758529818 405994239 877485552 32734019 756782780 794737100 347057380 750026791 562273263 680374828 418614667 476439908 523037183 132250790 214168433 188925202 507683267 827369647 89634481 908075638 959335798 629688889 75647235 36704858 2505734 782671670 961421184 397912700 137975288 327789973 553898215 535938852 450071188 443333613 526203447 732571015 925434591 290155359 175052989 581190910 293360592 107190755 995700375 531316038 43287764 71636101 668999958 290592964 428499634 716841710 944456998 751887225 403585372 350662632 205424331 46723688 672670727 564756921 622260735 574603875 973280436 778399494 979893521 500835299 189501585 670992143 836032911 749040896 995117212 517498665 168334810 126262071 119358667 452712799 905856037 147813504 855869469 638645490 775547417 772081113 213890499 146148111 881526780 55943194 166479946 192223348 347955595 55705357 735062959 188961593 117532710 134947620 418433999 884598278 43260665 869970088 359629101 415749005 193356140 645819234 93625519 2874910 206464330 518879336 649373600 983188428 495136259 294541682 496964734 198453671 374752153 428768097 358581918 714807006 155747046 130965812 698188227 242714051 234569731 666264866 627285688 975138724 387249109 24073977 769978123 266563561 746471301 631903330 600920195 571831505 310245111 116379901 660057335 64411261 798118253 230692714 647671451 354460630 467379490 773593884 225863721 888139046 354075554 790275432 338660831 946124938 681179561 676159058 935445267 344368409 633678337 41366882 216802456 106412456 420883126 665273340 109480814 320557773 67480358 219580285 467069193 601587834 640986408 117625682 736340427 328333313 953040648 631379120 634536583 220300701 972367060 961223368 427639724 770471038 228424176 776475804 97036202 664223832 419180741 14110190 623002887 262275668 834406221 760722342 18452285 259136141 182958517 672721104 572955682 585675627 991641150 547058487 277880054 361350297 368016209 81844057 314184934 20882739 599167783 319206834 254217746 857648998 897673927 302724148 285665146 463710200 165538522 665813174 512804751 191622111 732440838 728325796 238788071 29248101 742773778 381319366 224532764 440994288 230747067 904482226 215035757 328970271 34626065 901777830 652842352 715893616 895227680 679471377 331060901 878039836 43460070 147734639 717125404 910927825 48717 239267465 62591135 124372473 552130570 675396973 83956356 394591537 420046226 184905295 110158971 747621131 192302669 102199635 954878879 67677354 795617798 780637293 827100614 60512572 205729236 919923578 977198063 40685511 215768193 235862411 657616067 213220248 58157791 897117366 634153958 972600523 256985891 24447289 384396118 297071667 292364004 794272180 989833577 976286608 392108515 19934280 264405554 549867123 730574191 313811831 32376671 597763783 890565985 67802978 10483711 137526022 494208913 186390854 335905751 477500256 944647353 340168574 206176049 930448630 340854227 376785086 742898311 759298549 255226959 309396750 310972334 10677772 98066345 938887152 821218630 328933204 786910825 951950868 518214192 177037566 779761417 908522380 548291514 638660628 126882875 717575724 979795284 703306148 5560184 299461401 128767396 714430357 16943952 39162240 234106475 545510450 330664999 426668929 974530146 743050814 153611248 610681136 376239915 750187934 475182977 10497728 173536823 429399850 84611317 44993752 531686282 935046982 69219054 360472712 802189264 706241640 825190299 296021214 46391619 271529734 50372549 677735827 981471720 108580731 912717350 378640903 462682683 46736491 637197706 711623945 19747201 445438243 32661680 348938432 599122319 233608141 296074770 231319083 729503543 97416822 646056454 127004797 69939667 351012304 525670853 633596050 436979095 836961763 360628716 74464499 171024579 270750163 847842893 724636599 288531096 471217182 930784603 743640234 252552154 871925723 151153964 816149364 481880802 376891426 933307481 45883933 975289136 58139495 979856852 127272517 727342038 575469048 192117603 18133970 505611879 403883587 511735155 924201448 903848119 968220811 790377359 132490125 201937603 161151032 810034282 145943693 399491535 361089734 882340294 94667738 139946175 923259802 258763235 159038938 928408451 422979848 335321228 290465466 154647817 628388015 230011570 876340663 910678357 88237017 473534759 78308084 384317317 208688379 841244818 222869152 356058486 939482164 163466979 113348257 391052258 20612663 375860110 584569568 316675939 988219345 418139930 111909871 307818853 383310345 123794432 589044794 543724735 546134999 308236689 864403146 422071836 609404418 458071783 258673385 797012696 833291374 263698285 642659426 553122805 769512283 790690185 243081714 781806420 121808844 150205155 187213755 89307707 188961798 876982134 385617154 70176319 154419061 128047229 985001396 830982097 223073838 321989297 866729847 165681055 565797769 258793545 93535626 152661840 562418048 185439701 834761012 577689780 708590939 19689506 340942706 678891132 997733773 825456804 218787130 977536068 216828536 95724675 650934782 207007512 717650064 480323361 952423456 863938048 268432644 59677167 699568167 939515526 604593579 348346957 553922288 902176092 32071003 212546713 358644829 429176043 878678571 567573357 636634607 620726768 728989912 31578900 477107523 302040537 577130611 204810692 171789267 301582070 153861673 482401095 430483802 721934541 482219254 214332688 596292075 271441242 918993471 875073150 230923446 517915224 45974151 585308171 960092124 793928871 940970923 431078816 90703280 80101531 852694471 536914752 766883885 137928298 298218685 247256343 906603067 725922609 496829915 40071015 488400793 653439341 111436352 907323052 485032248 494698204 444565734 49192272 835553413 875320189 213365992 120016344 866034166 400576447 867778076 200445930 882183355 539672547 145013288 575440543 76076362 616409886 611259269 97413764 630567789 513026904 53596974 514301550 308200402 316560359 196737128 341948215 179640128 205859419 405983438 595021973 760761721 482571487 31921640 400171016 965485965 599308515 336021258 963907766 35280994 586733789 45500318 973650640 111023422 742787664 817120639 162181158 332866109 303477847 721617753 576298173 772740958 823580919 413527970 320407090 417173527 717218590 410919582 995629766 117979872 391442833 262189082 936956753 298030414 183829730 699717048 262204920 895044663 625553298 410320672 257813803 862822575 970006996 761379802 446947681 804480073 867574959 182276555 971691160 647951483 474702181 273877500 800613251 799826391 730756552 404926756 67236408 495078765 650329402 894753585 749543026 939011731 239518149 140706077 56498028 931701247 173420697 943936860 234938273 277973653 491072916 65596471 372601564 160920147 444744337 715682144 250754158 375589420 579082720 540756056 10704045 793492868 609458542 757781901 908085209 91061966 97992791 855931014 418467360 598221675 352664776 67053960 355976965 288014678 367490077 888828480 194844831 51934254 524673211 457889376 626445215 628877389 582523834 134801800 504478131 66168157 1633421 140712557 897949798 623035210 249302392 97539311 463982527 970163179 678553623 604574342 598088548 574998744 334482250 533365389 643398612 991299511 370086207 47216552 167052057 752607054 630556826 187575774 258074723 728309562 532126597 337770404 520814301 570254958 333769086 732641270 757500331 732599625 278119045 250635836 845949320 82099921 372286911 514941253 43941621 893079422 147742683 995526913 948136195 665288698 467035950 99638447 349024319 959568613 711057247 175853247 236203146 89468135 194854132 985673162 824846619 593003769 536480293 476204978 127285877 402263845 219098889 254832069 667507307 978925478 529879909 470034677 62424201 856485248 84511037 812910358 376528684 561007944 165418947 457945456 611159256 667163858 994735036 170691199 298993508 603585779 903265606 825020256 675520505 476424880 801789940 444123267 357207991 319468444 340827150 718367684 614750134 729279785 576335720 385219190 302318974 406612177 857780413 148599931 552817350 760974196 236788359 347252496 859169590 15294556 782732988 929035142 964016443 740464306 791916417 671502082 835366164 855002637 168450405 86871415 235177785 165209629 155972040 404600704 894001914 727134097 379087526 549986294 693528954 43997013 335989740 534113537 571031043 407204116 848342140 518575237 754315110 221367667 131872955 649226149 84391104 89585516 573034766 553856441 769394372 275000359 801872835 953213396 262277670 581377780 116574348 654580682 646823018 584992720 377311077 196838354 950206334 383719631 772067730 746394465 646522426 490748714 389375907 261348130 672139408 368862575 666372260 62243660 925830654 55261519 291053374 248105112 133248002 275842522 904249948 516357890 267471941 440232796 772647863 954297801 942183246 319081813 826663454 776903516 350269529 973818077 322865246 126319954 634697033 736668965 959593900 154488325 370838421 444116598 669113627 717801693 318276270 783682345 662505771 135733672 187826235 219233397 285650473 796803874 272623261 223074049 849692624 457727699 850629867 907177558 46097871 329413985 154557565 985812915 263037459 544932931 19188942 347701720 72707700 673106231 299524397 313886812 187255846 187712659 654148115 193246272 520938000 410102591 589191131 433765804 363115948 528853287 956117807 335681333 867062965 853230372 131732767 541620363 467982496 913459305 132394376 846442338 349689563 822810228 114515391 803620292 843278904 530712513 44026976 779806956 377585411 165534534 796698881 447659624 934292464 406992977 610335172 596450624 652386603 83086367 211359075 726967853 195359056 734101736 896142406 383431576 852576064 847233270 277303804 471125491 948269680 345068042 278245264 300928619 989220458 71315914 718885799 539783187 60372936 273967118 208553837 836997499 536473818 992051136 112980281 425633906 695727086 742466975 727753930 118084898 876811279 319779523 683021129 417619950 8776479 202928124 396877298 364609030 892262864 143047565 340162415 57292637 599829757 581351018 76896048 753344518 901417321 768958692 490921192 399017986 696347838 802603769 407589399 759275345 665320931 870858669 865132090 739172523 57277307 246367108 87760276 148597749 713598613 514579453 749201258 13272983 568499853 321632734 915948716 827690241 96903043 730182262 572383575 899692214 510553385 84440113 95079888 799987573 967308558 452598063 551124701 926608912 591572301 789123090 674971644 321849262 321843072 433673602 968498004 904961309 36585250 508684885 19959307 604530190 307417639 535238047 126444916 72799546 423472058 459589650 3483787 382525179 658792001 370459137 782984464 848930779 829216061 160374588 862213473 982515199 673562315 600140515 766206960 84962539 669452512 45486850 689211323 134258218 659082571 464208877 179283523 835899507 231547127 499790486 90515551 846146213 889661503 866270218 51641005 30437325 908537826 964534950 119149117 440061298 589743017 141206443 704610541 690456509 491655884 837267254 889529770 283471029 681713278 493675452 156508909 730444765 737218783 366560363 325365190 862194583 271820713 227589002 179879377 71108129 610129585 192487883 891684479 751649584 398509151 678279277 544511862 457973744 710128695 407977621 189743598 761693828 414595775 183958532 544654359 993157821 97944350 820650843 980721522 708580425 717920878 817886530 106913609 544318314 234022364 355246093 719477483 989601104 471185204 35371060 31092051 241513034 259288226 118126627 406249101 190387724 668041465 584131006 36096647 136519885 14069046 918516580 32134335 3621029 156282447 17118519 927134157 323572834 245162852 23585825 924598630 176151173 548389194 338555213 512127815 468314332 128399605 661281900 576251202 637026906 706646510 16130782 360313853 331685785 775012628 499953200 728390799 392062038 846483705 10892561 397550663 120915785 387023227 711207430 427991421 192035461 212172806 335189838 665894159 75328966 293320612 674791473 237454071 80078201 721100426 652193966 465741959 212638170 604451277 31481698 734121222 928919390 178782253 94590184 32473771 418243596 66159130 516185432 718340724 967135408 925512094 191076830 588490140 488134318 128965111 15151276 208842267 233334806 375822117 460510087 110355028 840144169 182665600 615013489 399996471 28231268 636582349 80458214 767108087 205582586 32427228 107666216 986051030 790060205 198888399 912918208 464322997 946531895 686256387 168720730 850287952 522593257 914847388 637544103 171170894 529074760 29231279 394201375 22197752 900213497 942903476 893321666 549657747 837904024 332135067 413831065 621248598 629673707 35758007 863871615 975485776 537228378 238340687 375509595 713122096 936125205 197217054 52290561 195465063 71611920 509199179 701191872 749982600 47669623 87854126 500701151 109600646 555698377 487207469 376566330 588759664 269455632 116721967 872031393 560603766 178358472 354791406 89595031 140771505 841813406 353246073 630185236 950871489 434506422 92333167 299124736 403434576 541744366 621203428 210765494 703408845 950238369 367261849 687990169 937350980 123325919 566643088 589388444 859645021 831624441 374294875 667727995 764564554 41046188 964501466 83191702 464178094 605979577 66731764 870216928 732500526 45904209 298663817 679410775 931790717 387010346 684188142 897299267 953204758 575200456 60916898 527261937 508424667 788713907 621236508 339479660 59708839 854030 495170051 451244435 4827934 665292607 205794837 491984340 304502777 331927416 149383615 526120574 63651574 132155573 557140891 377782580 26994018 763088064 701955014 11862058 942829275 697916729 306543429 761757204 337063260 914122890 828775429 316315735 162593234 957946711 548667474 170270744 810989331 346146750 878212565 248272419 382942964 482991570 965802946 425117258 142116050 224290227 464244987 975018652 270413501 596041024 384505644 506476588 962058399 933065811 712612537 237166518 157494918 91139786 431901929 844485239 845341759 889385840 919500674 653012775 930484906 621137172 218236645 677788419 631687440 993707282 80207589 379388341 443263208 816451985 543538037 856457300 722025907 742707211 142031225 441841628 690686511 19879563 882038676 243867085 384891094 746106630 705790026 339555029 743449409 372554945 207907427 305145761 539485422 176819886 120961011 320594799 106824924 276398010 571186017 48859801 681437589 239552970 182301166 370571007 385433783 646172523 648544453 282483973 821621030 5146459 890752227 213635017 176253522 978043689 185732834 157833321 385158976 464175295 318804796 402968533 79502759 631811046 988928289 381406431 686994725 821028223 799734259 603551003 499992031 178390529 923282665 636171625 8682993 333158529 314335923 994245420 303637318 518517451 292547577 705635547 187476789 201588995 986278259 713455939 484168675 951496896 323723485 457508104 440169006 12784360 655474633 737222160 828453543 74692114 717873948 347047933 683611582 41676514 509558320 81157832 667209152 692241454 792240661 632813611 19513954 789871503 907571394 745014622 748407711 145523395 679319015 344982429 808692430 196752159 547725774 190570157 737476493 555497807 751739006 399141640 842098249 386438632 896792968 688566370 80893120 294914893 574224417 744213684 373105103 800529186 350601869 362839044 988415252 269595696 263337125 590364982 805271558 864019927 251580326 782924819 415189413 384815101 782310894 965238551 547066916 613147639 470832731 358530051 506061849 523056546 778322374 16772703 348259189 50162631 906929887 949432100 924916495 32216579 252784634 644830369 395740315 730170772 717951253 332122831 408842796 974064504 976398712 409991288 934807601 626864016 931816203 676564987 652963773 711485908 867240258 797946743 544502661 786624067 492443378 384829746 592686908 72133730 931639758 411968765 618593166 225783694 144813070 746644762 194072329 764705771 265322268 998228836 197374205 979763012 129783786 403790531 517443702 812978284 497623008 901424724 77968679 811965730 864256420 432903214 231867980 19069859 424688964 82243485 741520534 963140177 385322465 974291120 832699683 22403794 58000733 199761573 718324879 475096988 730928188 955638137 647410507 758153219 753422233 996963149 326925666 550275662 69043468 120552816 73654479 694439980 507355987 934038123 399346344 883319061 528327726 494133290 500420756 546780448 260973710 635834429 453971893 379549432 101654727 112042868 731418714 498595414 736934050 911203992 342734113 484685088 247232678 703117429 315162518 762091081 52798313 821525128 39721540 692245197 393318900 357269751 887801017 50144198 167143007 569898614 920587597 761656990 111862882 218590397 108893467 472392270 213204842 195431574 502538185 112566495 600597150 484768103 473410069 689430909 473853038 295943816 810020643 896601671 716547261 494181246 959226896 264852297 299303634 382299540 10378111 385883982 527401143 885332353 304704707 575913667 654166036 659343079 543105154 592278172 719283250 72957648 56807757 275216563 725772841 947646869 165842869 608939452 159943763 339384538 680390563 894150787 434331282 16479735 311163557 464848509 399953700 11471766 27516359 350937281 702536319 637399308 781420225 176455655 417815517 751736564 557249246 28907078 389611873 962392952 950593732 798068114 321092134 374561789 941581962 934757631 972289786 929547914 209767059 487207177 329577587 551699351 818208855 547688248 481272850 409274067 279672709 718488746 849585616 892959957 135556513 646179951 838754154 634566816 38439943 702907530 433738176 172939295 699911975 128834891 965467254 801580678 383626002 339857167 357592895 69876877 651771580 429455511 339643248 71015405 418610575 810132755 380537695 868502301 140569546 49736772 562254125 632681958 377423786 670151061 366710856 876372911 110551685 810209856 327275613 246458735 855832451 668811099 758844389 963303832 986165041 57634553 47097187 163205375 321390935 577135880 896406114 853744752 406282499 287588015 436980147 560380360 44555627 501716746 210878358 660646222 204954730 186257185 380165002 203482652 829747206 823175386 336137961 755154093 639023968 16311292 859254622 808627240 189004188 884193048 856253625 484229568 453173936 13425093 336621381 110433582 120216685 415234929 611933465 691477436 984889745 975253485 629598837 563472771 808323828 353755930 799825641 694163614 316901182 235902105 544851808 24070085 66288361 759030904 519565406 472697475 537754164 945354617 679545497 910785431 690304396 131736954 833414249 173717082 166182860 102451888 210765343 752917119 161701056 257429788 995197289 431086948 608572664 42651067 399071111 747669676 114217322 339667188 564613184 610729150 334726344 978402793 789525572 660180652 530846547 719508163 237253701 894924948 718696263 617721063 100423021 446921863 68917472 368921140 461724719 667953418 82684788 211910784 766400612 852099201 857984247 872327986 54057861 732795568 406634063 743062082 628047147 85800884 304923886 792234 325740784 819186901 447266065 310989208 571492335 919977564 858342633 65468975 251062343 660519683 721897935 309406134 899225577 772583838 401582343 542812596 706190943 126665648 975401775 506656647 284266467 60517208 547398213 478587651 540622825 953811525 341380307 822643632 867900177 382871166 825595488 984128118 621360782 121250124 341592645 676559813 809036173 597852553 592898746 164722765 232266918 116352826 542188382 839455850 242362588 689712880 53858818 140821266 349235778 76619073 201992543 856255026 151753364 974202648 74362171 464528326 516975414 946515130 67747772 249524153 431760292 144142934 10123746 983009669 775564500 793171335 221251022 259330782 108520088 495389184 396667876 739285538 759919367 478288333 29379124 495973621 29574881 804335464 236629389 248214424 989329901 193658668 81883888 842612367 741530355 636885682 759618576 200252684 438522260 870299682 602615361 723690655 915878575 570452320 219884526 219089267 723578225 997781000 618959018 714488501 365531563 158555779 726622178 481162643 460420813 778670447 206156397 676687921 823878726 327573193 52736546 271929940 415960165 826792740 314534288 193077658 796715564 426772555 504731278 482617617 702064821 161560810 14159611 246909644 937302625 455515609 458041024 620149751 870993958 795217495 847958261 229175559 230446849 769564432 384015818 419982135 293189880 74013084 81246606 661507420 579896106 745425508 205386816 631889786 68084979 774812881 682941012 462729338 349666820 822912501 71186287 91129731 137612819 53087132 995922663 148490215 749301640 126834449 86844996 861806428 205794821 822630957 697266619 974073575 306468933 913742846 18169681 30282001 651186025 886637996 9880110 671627874 725443058 912270665 680680971 237362490 514193993 923903588 42317464 436269551 120930397 244992219 125988639 239368888 576743481 531589098 352672465 266703169 5183835 652541519 659602584 557474616 193726087 793706487 198933952 698354581 654668729 254986437 948112454 662825759 694460961 814405293 969701663 876674973 109232594 260204131 297855963 558488114 760628924 920796734 150095044 308248532 450520306 678886411 173106585 979337506 145143582 334631510 813154898 769455393 374860997 602866267 66732782 355287697 549509962 153352579 835304897 163789933 382366102 462277684 42076158 914273855 949863935 996605578 291685303 932789881 756850614 934577239 914225895 74782526 237826837 398028715 631384979 969475684 272549774 794306397 50229799 466393585 580930504 73910637 270086791 423769407 74704456 161753569 93612687 641976579 971884455 810354062 617712846 939017069 952703217 669044554 275980784 891629534 574944768 274572434 968315771 273412871 889010264 131766036 221948310 397788237 408022424 19896915 40213732 905439222 346110153 245406681 712232445 545784979 695590032 481527410 389526061 207485956 129255238 383093606 916001865 439058778 915894873 569396627 523390817 907613072 848712677 440643315 492234348 533786544 147082065 416767040 884523616 503801814 120000163 120191988 685951549 427177073 686741719 798688057 198857011 173870820 472475738 788466640 548751101 77306041 869494041 393813190 635072741 362708656 396714576 686317381 970835778 729740022 529184271 280206360 112771742 789361352 413237614 924524567 439895771 429873121 355941091 997721384 713752241 354633153 869362621 732620028 585069880 480938206 626338098 844299871 903992161 471845702 882786351 397749550 207337637 318745819 210068003 638165754 519945068 212959225 200947918 273604522 260304993 957683004 376195469 240952733 414199293 710294348 80064878 626560012 973755609 34097433 569258805 651281536 699388548 245391888 287756140 231366014 644619981 852404491 630095186 326775403 318042385 679993815 229044587 243539992 105941587 252421730 431988358 24195811 854276904 166715631 844580110 381445141 312517211 829541256 118755645 631925496 382125298 822760089 827429289 81201126 351702661 594968622 695277835 662382842 499959074 495836057 816406546 343577713 397586581 984721526 595100304 439892862 530423696 216492367 396992705 931637335 49107808 577255818 132166426 53075338 163700839 946124376 870788063 252179094 60877556 324859090 326569380 780456213 199884885 956953097 531663550 481896994 166214595 20878751 168595299 171664924 739750795 926789872 861462144 901763044 819604069 300510306 159575301 924889756 486241548 468996333 863735171 481428096 628511014 346345507 798695158 276060322 355659412 600688048 879124675 639387488 359463443 109203767 669925531 969583890 19353415 309473392 315072000 527154497 389672994 453102645 619434784 455153201 940503675 351912954 466719989 16918015 762676080 967094765 790470540 317162201 614700843 322965118 543325526 490960382 291714670 497549205 731935212 634723068 381488712 867270210 778336912 189021335 863790201 883160433 930671277 306214565 323782091 135473344 430462582 254434392 614130901 687137414 329504803 619244858 311522233 254699154 602544213 723388867 44650005 682338835 230610527 333230166 553270116 869921077 184117097 95309293 347468787 430240447 958145493 703317047 279163035 911780212 19874142 156667472 186812422 579679056 500558063 589246585 423393329 35519008 137579293 220861502 66375739 90203401 968774242 560575752 698537740 782747656 332182654 502908242 205421172 241771029 573890905 260741594 459071830 230535363 383938232 496059910 943379572 764363326 370348650 980574922 208090791 534413480 749004099 447719936 51909810 333354197 198048609 954874736 780373203 71074777 913042890 747983779 284986274 149410125 576612335 120426867 214254747 226190971 264226918 300109839 372981984 258928504 415562937 375634253 702217320 482556393 357016374 594721720 451477101 39915349 146224212 638409909 535234085 910619174 935263225 889665393 610959085 847903573 705779019 939137567 373290014 671201992 379461426 305642230 992581604 589996334 301858925 931913199 835084414 453509252 198472123 861885227 674881523 567122103 467567908 260496676 833661531 603768116 621761280 341059143 173549813 638578459 404397564 11087419 227701409 408961833 527294282 489369936 595388906 488376406 12255608 723630430 667496578 633394751 913567879 943633383 10177890 765914983 216830062 718527111 716483912 644897611 346070363 104558881 563049928 505786016 321478072 646813460 495628006 381989258 134270444 450189017 777537887 430423338 945024188 356507839 530752933 941429300 354253904 416379111 673924408 962610069 723489664 453014665 383095733 589605199 670820018 816232074 443088499 520755406 37024083 285912207 382924271 410119768 338452106 904937969 37385382 312026669 662932680 412621702 117812178 514768553 879881089 322276931 346938497 100016245 55806388 21146962 259032383 776396383 617569509 880865892 515170869 115714071 738216949 499697938 659616399 96634771 240316784 131130128 800899519 271828994 184584549 707068385 854881435 923841025 62087009 927527483 513476821 873365572 112455654 52543065 470485312 310343861 435535156 824562792 764828846 250453417 824279803 169411110 954082361 704068561 45386425 220567659 592101316 860847798 204413628 948174349 923824002 364799605 23719454 926873095 958242858 131372988 817921860 586519186 99805666 221323943 894333285 366717599 637058956 677115544 675067420 105682142 456743968 657307171 93472181 651635009 196970430 965783964 762336853 828919216 559040910 306115808 664332519 447715213 220497477 142937852 702073912 590106647 892613480 553948 779208708 691067059 858566923 177215584 748629444 619595131 932525440 828528218 870299616 239635915 882039819 719026448 825337128 290643517 916574072 709479287 561392050 589239653 532664057 371543562 332375645 297650965 385461441 778409137 572115374 720619924 269786011 322610476 321213870 155128095 578154626 314195537 680595942 757257895 729626992 624870969 931600459 659477015 689317730 159517538 995342699 265386591 147484721 255065179 871104559 133643547 611807074 243368965 166790189 854626347 125888796 708198049 205833416 640156003 507922439 678613790 900275481 322580183 149270097 545433331 370334699 158368425 124883622 401152171 29587393 628904083 579690396 69291857 839993728 608514596 314101206 351005718 566350472 295154641 42014279 115144168 655117245 609899084 632115296 147522318 469116587 128217557 979316588 7849358 942978259 172749223 939511843 337711570 692936047 471536017 857570348 62885764 597497472 73433721 377047476 373774204 255565741 100046763 237048917 465751018 91380723 81893407 791439354 706122999 218537654 726155420 354770820 862697977 585932463 701681649 155379301 99084809 841255743 289015112 224602551 219466862 169076162 335811216 791711758 212008287 277562772 169894585 158337981 121170291 40343619 235067164 760595634 648868948 430256900 576104571 648208351 557745720 911203858 280753461 319720312 369644506 392546870 605021762 785087533 628371302 673385666 353447341 608597930 147397978 55084023 300220910 287157489 763787338 303800102 4299069 15716582 17996453 61291619 525251420 741693706 946122087 69467402 995421606 742794943 815287354 269550107 267011271 494335507 387636716 173233965 773385368 514014914 668863817 637929163 684411323 866956348 402864139 689162170 430227354 770497098 716602318 616291275 380198894 243573776 708869262 981838003 796118722 478207284 814413182 766323665 658894110 294734778 410449050 449722286 191031019 448033245 441707889 835398889 869103548 345289525 943939273 447047017 834117521 614253322 540150206 386726775 289440317 627760086 853871223 796540667 719872379 97494143 468596060 595830235 425509683 977711772 238829322 845737684 41425228 796825431 917425168 928551392 608252461 378447375 620546681 779510836 745256837 519361329 958847948 463815747 787745571 943217710 472500983 900919833 101893971 593136999 980301150 93435793 543862925 990777584 249338905 728134673 881148789 384590108 837554143 283105324 703489704 334720110 364301871 452505584 106130509 89418388 818766226 178813167 495563120 304888129 922387412 621045456 217539759 313258092 983911103 520253103 424539700 72206039 224948774 859710174 976702728 826483800 916211303 755561265 459192490 985725099 780976087 357426842 471470579 202210304 111320952 61212928 811050010 44482090 928188503 290289710 585040776 254091623 698128032 350886542 771755087 493060278 169470730 821312676 431961044 976042626 362370506 867538524 777787431 541990905 553585899 913093244 733901749 809034191 982714396 741836893 570372507 850407109 242949899 352861998 676340635 833434537 690550796 229225855 104178597 968385093 633485910 985739743 316722070 300205094 221069470 229599820 342387704 243994435 150686564 835248732 641656843 790501263 903141287 24722659 374269379 929035630 531536429 148024014 74732186 263532403 774458684 109082528 483060079 158952509 457369227 830213149 759011619 530118984 307781301 658028212 550566271 499989321 695326829 632980299 112835423 635456354 148610075 444738492 642387193 635731420 984590680 81094634 603712287 159803182 352434734 102267515 343976485 1567532 147240959 834022415 532627540 49935258 736782467 525643474 561440628 695270220 690056360 598494619 955655261 685464718 229647018 445811938 840340842 900735091 273722504 700604990 297362302 863177358 491591026 785341107 628050623 797246256 166940508 441571455 929331868 369891032 940991046 977303911 362135562 676238898 911381724 268288105 805501129 59970275 40608673 275827468 579663597 40789179 375357366 724906406 951171888 996641169 157212002 889729287 956380528 223251982 879811458 709382036 292296593 786393455 956129061 118181608 765484555 303591162 350443253 601892082 39421195 41096492 549597976 206153652 401432378 611551030 547556382 406773252 888526373 69291937 600000060 8010314 560654014 34301725 717374570 867605553 786673756 408596943 408445300 299116819 337810738 843529228 115354301 985810428 935283331 355630827 774088545 245707373 557392786 505343810 764481286 296521368 36964952 197975645 798244384 318713289 524492841 851692335 973828451 526258934 304329866 933175308 948631746 319354949 656334771 502149127 574713853 62116287 342963065 1306819 918070338 943910771 770854074 18678441 735487933 436788672 958484559 877711284 466274574 728137710 451069835 984363605 750311046 867232294 201195275 477074961 249857627 369364082 233354927 733055327 969382439 533247235 86983410 932714074 659820202 847065776 889681470 901844572 394936596 650497428 487590140 923245701 652042226 744554467 704589186 895385987 921362952 426430263 782498426 15570857 444972739 683317998 662642553 44754920 625876153 416152440 556636525 618447374 68392692 453562782 924784624 63049925 137756398 397417302 456281374 918875404 247091089 441581367 436930887 424585275 332148484 511063987 531867070 904019270 71371607 761612055 123881537 960192766 217001720 38016488 333001579 697670031 840379486 96570693 644577293 419299674 844886287 115813119 487346610 901336180 966520203 717288121 553314503 986297933 315263580 783649371 13112444 293452830 589158481 900647704 528071195 727328915 561559119 531392575 78796247 424884947 452832222 624479330 371101079 803799367 433789034 831560712 565424564 234195164 941188240 559487912 204655548 803350145 870568430 750348523 571967262 249999129 790435400 902689927 91616635 960742369 143862496 569488082 796181294 46599844 179008088 965996198 265405213 938032465 878806446 405809481 642894521 9564371 261670956 921778371 320372333 284682520 975776702 656092575 475674377 474988669 926093989 3364460 960544243 232027274 797756898 980299603 185339617 55952132 574162934 636078443 991315394 178768960 174679906 148683573 33489502 684200314 759363026 952129850 959130712 817760419 990246077 742584943 794495296 897800559 754068361 914690313 990893827 201029203 360427888 418072191 145602045 293686749 598344377 124043614 439843878 184238443 85773869 402157107 560704052 645086941 7336246 297755155 141185604 655435195 875024533 579854760 487374143 661599544 196890014 568145799 395006164 904618932 892987605 730211588 36105962 422013586 446601274 968653542 294825545 709635266 678240928 663514419 311664127 887209171 112807194 323001809 904291265 952689413 137271936 846610352 859373495 748317783 501921327 603634119 646582636 942736886 854191507 15050607 807628544 53977693 188434028 655481227 110293914 268954554 581498445 88152747 265913178 194764397 239352255 877022539 806406511 118581074 418405754 203253509 113773010 678487132 390642293 851011211 147997709 459073309 481407653 924449800 602562858 51294204 159933332 446104748 311978181 757008234 132483693 726257045 486865196 947468194 155315676 624309507 27021003 409716036 209041758 695029803 950471991 791488448 666331862 246415482 66451843 557508810 441071353 40819717 309355594 106833345 150757035 78561199 106331912 291493341 814623091 350214984 425844682 973627084 648745157 673322663 685951248 864303007 6229599 521185552 59591272 524914926 156663912 773669254 197641038 21938174 384027402 242399929 536412659 197630928 859455021 899922151 368560316 100210171 337384790 682524366 84622689 884135671 506177750 190948692 615628876 296337602 101417474 456318613 833292204 527659709 1910617 870984673 820997813 305294741 665728722 917230152 112656546 480213751 718468467 439148614 246470619 664355371 533988968 825551571 67155343 352791893 995706899 850000796 477495301 927368454 198311485 646222863 455621886 375483420 814348781 410406497 29976710 433433035 879567073 654617442 878483731 894938872 699423596 720744286 755845611 218100593 711526134 480143841 312801230 64506543 249920892 163826180 90262660 674845990 366012608 349651425 521421308 814521112 481339957 171840857 931113369 489221500 288623387 743703756 866230546 604720744 867072446 788291294 17326926 550576792 239630650 291762062 65662169 651859620 204093267 235148494 680300893 426632721 811223044 800793905 925483501 78077375 995313423 983025903 167325905 96154377 18685741 418985127 65297074 427026263 292857490 728257355 35918652 617597845 949886693 891811711 664067612 430185994 927962516 147198760 437144385 909437309 763398677 465215677 640298344 114927545 976600594 477164200 218098190 954497269 329460191 291022424 939758547 309093796 899020705 221095811 877032446 942390357 647942866 128114430 433109126 265001057 189596360 465236397 861598076 620684523 807573561 957313272 174023320 742625960 388792929 481915435 731473468 884740171 604412064 850983042 896519915 558449316 286751016 220512242 901743968 611065059 556634847 500601777 974008575 690848065 43778974 313567411 261562115 85071931 943295079 632792208 352688090 82808232 950311862 197227325 350862866 843896905 343029129 190183015 781127079 678019534 326199151 556598069 248003058 444941015 920290076 517092085 958496282 971362855 420278196 206372758 712869959 241880032 94987263 798370120 71520085 111964695 712153115 63973655 751523038 531834084 801444715 173329368 178790597 533381478 194647784 244743738 324772543 282404524 645492408 800781016 960289173 375125314 191262548 320389301 259437374 99668773 767116155 325375641 725534535 598597084 898671133 695539538 537748975 204934897 428147393 102250021 116849894 342978600 723114410 730497598 129059426 284822449 19866373 213089161 927687317 808308717 199473774 216806439 951281345 87648819 934200856 179520747 951835621 245020013 59575091 418737279 793199117 344285878 873033411 329260442 802903587 716235290 767584829 816112817 264623138 83820487 310829218 140885927 421724210 836783721 623858772 500421097 766081371 560433530 875915365 163087754 401325610 166512642 588728637 648604671 861698424 541212077 128408358 512921324 380658161 729785967 639230433 295134212 671414629 171743895 94056724 524597492 599623064 990315025 497424218 521710058 678314006 52118077 598515175 865193546 831948589 459761546 750842077 242577288 780254115 105164122 31188270 288554817 163700504 612356413 506515713 465959345 33788792 658617464 495134109 38635375 830304500 315328987 243599891 247430655 852884995 131247034 293722108 514148894 750277085 566246094 216264241 875925463 431642701 79974967 969358689 467950970 899342238 881785556 656613887 161051921 756431142 983867995 870108955 833668647 594273382 402929862 931960238 270146701 619201570 286000019 912720261 125205577 883831583 291201854 614816842 877839410 62623369 480038282 878665742 802715906 204802251 232177755 907517681 604302331 145899145 671442229 4233738 585702507 431585380 13900360 37697388 657957635 626689419 176325081 785346793 567780264 996309089 511962997 105602759 206480406 793372655 157281599 364205900 262273951 665318879 157209546 396913621 523626198 487010720 383167687 643131313 387765448 239365237 177344056 40139020 301149285 809433273 890811486 531923265 358125135 627067311 621133720 382304552 277150649 263671646 595308648 736375845 715753044 308584714 161095654 931594561 15089903 850807851 417794632 637378071 72510792 315830596 763608952 133600391 309257372 443391804 35558256 509697675 602406405 135506095 390442372 25774397 981806861 433313318 327647297 127722330 918912935 739105720 704413233 51952576 554782412 282764627 259382943 839101548 367583059 310754721 416874148 204559969 212693868 316387854 960177470 261393252 436075357 983044614 325993421 666830202 521985412 116031435 793166838 110380856 365639597 919881023 174222646 56119465 575037578 911835909 530402786 270495581 282649618 754683554 522092762 248737553 840525274 137047961 514320875 392208329 562787100 421444251 353011623 511786528 299669216 66995308 480467632 637213475 549934321 133051869 871598519 913182522 384455529 479564426 734129192 461762727 779816324 604443138 746574663 461483213 7399828 348127359 608317337 117380227 211026107 449279664 233586803 963268617 41158018 599813264 75205830 891999440 58361461 684413824 144405420 471658176 734453923 760542814 843580507 605330742 641322411 915811117 857880446 809653217 312928277 870888716 448347251 666817925 155566851 983185314 521035661 611750106 460432877 244390461 78828905 276818629 8373463 763692321 762653420 926645747 785082161 24714279 996677935 967724670 521432407 560830145 274340462 353676165 885973368 647119570 34997372 916592337 362221618 592821500 997627295 655686393 996639115 652000496 895864545 35213710 994320606 887645464 442491139 342762157 388516961 844745326 247098446 684091318 38294720 719844667 326760743 525412460 868613335 4034733 738535965 965691069 603708827 281841612 190652252 986546747 731063088 244279810 718522842 144654399 990821612 844677349 579848062 713746106 309298193 255050573 269879248 783802060 194077809 729046815 95478087 404821513 87801213 995879778 200758495 367586664 806909311 648276002 34329749 287373261 866677434 754591607 435510509 805320677 534039582 2754165 607059080 115750264 322746265 58857700 563345512 802667944