4000
434174674 560160721 132271040 987432332 128388623 25905252 682841050 76561983 840823157 498000833 33619861 1716355 62085733 693627411 362145535 550477583 56374893 7486363 346711768 608864515 383465229 829423727 47599372 343119983 388339042 93413403 422950448 136879301 551840046 721518417 45246644 950922586 495897381 358177495 594138605 927782785 354681697 448088276 45303829 415037555 597316863 248947263 569297694 969785780 848082950 973980596 959381671 658353683 983641013 495888630 196596400 832662066 273604220 636079264 812903064 613144477 309998388 681998837 7659254 919768357 708598366 349648392 766384073 719052274 453805221 488028407 491697744 43603963 935497080 843966827 497891472 697826204 301268205 302745580 160210813 472826402 446620162 570671632 149636311 344501113 590319014 219881524 537703979 573319397 246896922 574486017 152817580 853790856 742206655 995561890 594511264 681941590 26564325 197807894 183200239 685376206 479669901 463766379 239059070 41086178 442565084 464869164 989426741 753896900 452298619 75314871 44636029 275983873 249617853 830741550 256488800 867517451 961595489 295583640 269334910 599022219 247620807 865675154 283967353 774604620 835998232 937860175 322681712 435737609 58162073 935662108 889268190 900340443 134422885 387878017 761443132 732762668 543216256 119132996 519220545 142309341 785041326 175515545 791541614 783244723 955969085 560295614 903641810 623597972 345475655 347610799 156920444 392449634 367438468 335409600 836284642 436785249 710732176 691520363 421245876 351535616 224532194 788006428 536539245 313031113 814627329 388704040 509577037 884838030 912754810 54104698 885684697 61041809 680041693 772847605 890373805 2410106 34228755 566458185 836226062 106280407 446074461 953001558 931336259 942312133 813926330 462284131 781974344 912571128 658015672 652061633 363658939 555360777 162328719 130917861 641781381 20176606 148477479 477101943 490362239 952550066 307278159 172810876 337941976 320720138 348572356 641420253 84160600 995576809 447505995 277541092 931941689 955495001 92613313 335955212 83147370 478957954 202396627 654793712 700126236 232756297 817311197 188589745 122795782 55183986 989834885 44214184 221893536 713409287 154210142 56420401 495417838 697658707 384150550 185573399 744696937 35141086 734030636 931984127 444672253 369731494 481022572 548443603 288147546 931694493 179790776 30862608 507555404 416062818 18561594 792028878 680647086 591695850 431203547 673320813 57550610 310330630 28414387 354326514 188022721 411510670 745792120 122276634 50660322 791058016 217970750 827936250 270509671 915159863 469386919 923842384 133623357 829377771 831385583 601600773 787909688 908564107 269242173 753491169 214825756 158032617 9939718 738180443 147074792 930399759 910657431 94810917 544979543 206882106 785148726 758111147 550907916 619989221 661336042 468470578 561092018 666938041 392621465 831504755 436438076 301400269 351461113 94358145 182177759 146296895 854747943 891498661 176675409 973696932 357180407 249321296 849232560 288892217 98124711 559338317 80854178 590013184 412843269 535406925 324552987 146828879 110592981 428509769 158036306 332753842 924741590 909578155 366329003 501972273 876932264 53965220 802684920 301572151 457860501 495310089 953011623 314072866 631149859 95781211 885826511 656652780 386694879 246557019 535636366 509032012 440395945 973853201 655292249 823658022 643017414 924710585 202444837 481801034 114351128 321569424 349369542 98640577 464034663 166085470 580490723 484626724 483059265 380965207 737769619 934893645 294161102 172122482 270776181 19902193 591698876 573953801 388814664 509417816 520879967 437432664 392829451 965640077 85787969 60836395 682215405 803643313 994566694 597853813 916042486 840984835 151492253 673315133 376039892 578312801 86577034 609701951 365353298 381768759 589302094 133292163 957747106 425952109 753715882 241871652 158919712 35762679 390096519 923251364 82291575 833255562 204938854 16254106 263440781 958128930 710199646 361790987 692199597 321983069 99772890 397382376 400319720 68841364 403300612 992484985 691571345 849854318 77929546 856204063 536767927 924347197 742826053 254610095 816207216 586585309 78469423 161927006 277718387 270564387 667921264 578081849 911166663 899441587 815831477 837823870 786881436 684836591 89421071 387478185 336846979 831291828 361934794 137774663 676370214 497930470 64224958 181377458 732492707 233211230 233441927 354808190 592655933 393532838 355358637 637184132 29999807 221541722 24815957 87087936 975816806 396713343 418995654 636458005 182716167 274763163 229979200 735808511 525472437 968732499 223802023 551817080 846146948 318892209 621487439 932953647 866119635 681382145 84386992 192717592 613848470 406913451 294385901 446752689 702438955 777926414 839437026 979842166 207755659 38121598 525145749 590840190 814864835 23468228 165815603 697856261 521396957 435360137 978463716 282514917 88925903 146059444 899288865 411833997 878850176 247181575 92427645 800838632 504036708 510909686 545603810 170149769 493477202 211141062 548752326 58215099 625779640 914542160 335555408 604848643 330349090 607289423 340232621 904997327 712519783 965023442 303612450 694429166 45695170 906648760 742043680 18474095 677404020 469808593 112427442 451153635 5495227 295615824 283820633 379268239 626012006 623450232 342385277 937070905 989737722 734278818 439159902 936972531 491130984 836405238 104602732 287249649 245214752 339948962 413977596 952081053 29022217 257443876 778818738 788037955 611162774 391174595 821013890 226428279 203062473 581275654 607764489 13457959 899267216 655646746 63038211 683278005 727423505 719418699 526248752 542097406 881615420 938007788 914168574 871902106 521132942 307668047 208011282 41478884 148825458 414615833 342826803 357395007 345180969 859121670 975402423 55308917 649421204 592289632 722259486 929554645 866422476 557682242 587871242 399305464 796830514 293385363 851751855 537545341 114789774 144019458 94025385 360368763 89582304 373179308 641382664 899755664 944802243 983434868 397825185 653781693 184992926 3810011 896041867 581394638 796854061 445778123 610867821 559361413 185251421 185879562 166179660 426929331 391873254 602851849 893876531 53326813 181920528 158158377 542689886 202884748 629330851 234933714 88142469 629829666 823593280 965362701 668315342 131180270 766923635 325444421 887885870 128726585 454606056 813388147 781527931 160604241 637401378 446169010 995489711 84125912 798561632 849969061 238685876 763594119 505216222 918492463 950978987 862491272 952052549 400633396 311457661 941810718 513590042 748730462 514718845 298345646 581887477 104403039 739990892 347390910 263034636 477517751 375489723 962695549 856908170 230517249 981228603 685847244 63200882 661942130 816908485 615666955 95003823 272045191 381703183 130296050 756438344 410017668 692629760 773968746 344280669 870753782 650263968 765865425 578385013 494560078 615343034 21620297 588280473 378655209 67396033 583143377 909954416 586331271 766710066 923273584 694844323 996736953 670794332 506087660 542456341 304158011 789955315 104983903 212844979 690041544 741805217 864396879 537931612 322697743 715350988 270224288 946960924 138175584 105086818 704958713 978002919 51398439 60734042 683248274 127158264 910797731 579746881 643217657 129457692 683626666 233495370 236269325 332814407 532584522 937810957 80782445 188383758 565693870 618859742 430948448 626778755 816226062 875627036 573648051 86421542 198029009 867851617 926668669 49454948 806879075 887523069 221482695 524779703 735981069 896737434 806626322 850269377 915944243 523590968 303770168 895621381 608395806 967594230 598770003 936095063 669478189 623989181 150466438 682359949 129241403 863947361 99535098 523646370 562917699 729111751 895288492 610914193 254214902 650011465 518853467 565246246 392126326 643111900 974902222 720280224 828026057 683476046 127636732 84077330 982338258 451263450 919686861 482986128 344485877 401691019 548263874 462728584 539938177 495661642 982317326 406660736 587849688 828917651 239774412 139016273 137229326 235034947 629594917 456606471 896379491 945543551 715564094 932857967 782894478 527664023 255052984 60847278 71074654 471215057 818434270 264531750 251037164 666920341 262165001 406476500 764770119 91474636 583133448 773723085 507189004 754739320 914232370 888381423 390014982 417452065 154860224 312470536 38790591 600519250 115782153 41694450 646792535 97862310 775685163 556193231 765282648 353033132 82235788 209505434 33292692 992063759 452661525 617932854 898339798 5004272 235883133 937658537 566561113 523586786 466351981 699739692 781827584 182314147 29201002 454429399 867279100 483864865 46712587 300532332 257136617 984150958 823036890 883911502 310308854 190898615 733684799 536776128 538829990 885358469 520482732 195016391 780976739 335828400 543883805 652212344 752154264 189539757 9800326 726244506 985406302 732557937 443297277 348517956 518944894 991543754 392887903 220120204 822178235 144666128 887480854 941666272 825830649 533686943 422797359 604532765 944096422 327775629 131568972 819563989 167370109 354114745 891202339 949494925 425575824 99196620 112219302 665120770 930862394 926821441 652416904 938551555 806529634 912639652 754372806 212483472 250559313 417138800 478152843 950415351 708203128 75315375 490889558 909512337 88673306 813654441 669157170 880335946 394819175 678248651 94658018 244111147 394012357 274247805 852323327 891758552 646926700 904967788 476069820 425802383 964704844 31639096 735457243 367252027 889099803 414930190 513826424 282657193 973372094 541622043 914462979 378182895 31971714 898071975 133986276 834785857 687330042 247966641 643527803 563537111 18441229 309776596 313153461 613404709 963668115 459349232 28329174 14473853 242087115 504498986 82590127 651326592 877612849 2756126 46935620 969088428 463917928 364805263 725272639 55960635 452864165 41549411 706454627 95503074 887756694 160533795 498647467 664991781 396904473 958563015 882616488 417192740 844534677 186903037 741076482 322464872 204341074 905099415 627706868 269580620 229213393 529095683 511820346 449067657 405803240 363397437 767768409 35540551 238485930 625493699 126054207 283991544 954320819 77612056 209758581 192239303 675155174 247685987 703061831 542328207 701192018 346232572 65256430 170201980 767407500 535107577 874324945 664630455 270196131 310710564 561277258 243707192 957946011 425682272 748655589 716967369 89220492 94917472 33905901 513946527 492456642 549457429 555159969 986669247 66684956 430208881 622448462 876485416 260004256 598719851 543001990 347183514 726402914 247474237 439976474 73562787 787359611 896182988 174137569 333505986 891268623 5363898 790888982 71920748 383153810 938044061 111243859 846927924 365861692 308688056 390099149 294894538 129941815 506458323 817513934 439325401 730306287 590416201 235398322 653206448 147083839 618125872 236590177 461343220 114850983 850327857 891804659 460587378 377800108 435807892 768201473 899717789 648656823 687915802 590880579 371248869 496416031 931709818 363173005 881303923 834662178 897865990 165559436 963896158 186241186 228418726 910475994 393880257 455910130 290104134 907116498 538951300 725403213 821957947 561247362 756750476 576757437 267155547 202779735 506606995 127264063 737552032 668769263 532707472 906282204 933236322 493348425 593967112 358635012 594573891 585721951 409406778 558875226 479905616 447044065 142646181 253521931 893473527 621183675 981882745 785802156 993738728 469954583 124702533 764933713 279243812 828027025 783420484 723632388 290634989 726341559 659672507 324027087 911897356 988993683 232912306 18538439 110931822 972889288 866291478 541277560 279111084 935452435 797060355 245152135 947191651 205933463 257484137 204115259 876935217 908486685 882595358 988476713 60509074 789576475 100239697 827244452 797263501 955016937 603064691 511900075 336477830 504204509 131324131 623351385 540927365 246233807 607092654 326117714 612933669 546417489 552340308 477108152 715361389 707936036 803589665 213352264 990987295 866874804 531152683 585178060 733796298 890849877 802620901 180079820 711989070 865450868 634967089 167911816 632625364 880995450 363457148 465720861 551916894 348050105 506058755 650639503 198896253 89618359 749278854 673310990 415709858 459034582 145445098 517832334 201653278 583753920 877223985 208376378 805097614 324468730 103064445 418288082 222479536 86285897 136710499 880039096 914057543 532916933 63056629 388161159 258649827 4140836 351800840 488470310 664847230 220895950 916547977 402169043 914745683 793952295 483033039 675871123 379758703 997814842 562737636 340526249 629991397 676150491 297188415 482675072 388948299 929184618 698466624 292668846 625232863 666349725 469320089 43825434 164098121 512284122 482794526 670051538 927228232 214939473 44118115 275742720 905378708 351845356 599363141 692387812 516482065 454925992 944603517 48171818 374885596 992634709 482378119 118900243 917620651 180305412 234066404 477254811 487409151 673457735 291961893 938310005 697591898 43154200 281770086 990645610 138748473 177438988 806797091 619234831 414766917 583225967 595533048 3681817 194733960 719611005 832210102 624091351 345721677 148530220 388635386 115650614 814558214 735028287 91972625 45451227 668798999 693211809 730342647 15620966 117726989 63308639 20651448 784203786 366016101 497566685 782554023 452126459 362616062 119406804 517919926 559064805 929388430 440981763 653451768 617754082 935718250 72518542 498409544 208006572 947679406 986301562 697870283 925367767 935953601 746518758 367438440 735683893 883165914 360150571 520975698 268245108 829253553 545836512 90007167 88908626 501223946 115043657 740886989 373563860 311347101 17244881 549050460 199827184 985914575 69016988 803341452 3265654 992921061 17903170 915405476 119179936 173612520 229760642 766424240 356215937 351211577 477057829 449413540 172181103 732628422 29584981 922378336 764993689 79528966 84874714 961531167 102952240 319848325 159838917 891227928 980216822 806936866 597623280 434422193 486496343 100329740 688885643 756019220 796739110 20565498 701816311 363145807 850084792 96549826 106875517 361048993 622172274 313646064 962661353 68820201 745120569 965585175 648396227 595208061 490962463 649617667 239331434 84933850 203417002 307354859 253984780 19964139 425284509 262906763 997013427 547256849 524621457 609318778 349227191 46821636 476870683 836895105 824246583 631089108 224762708 926525429 791490427 23975358 458488442 696214688 326849543 109950675 457597543 200898142 583383333 131364074 618112690 172198061 532462019 526199378 924516898 765322257 761633198 491873464 952824971 141446468 870093872 58820155 189560029 710640115 20846210 807548133 433259603 158863611 922267560 609413881 354332688 205866316 328475943 343582111 652827259 8355923 829546147 767247242 561703346 920610984 766483485 181020096 869401603 222021702 408920849 423152109 843953022 371377249 454355018 860985063 104096403 251527076 41309449 226313997 358667719 99511628 425053976 267011102 6972319 159397944 912511353 459603074 860624238 255444316 696562298 707732593 953869245 423333555 511870742 550488976 591449096 51067051 381655760 937842546 840917866 456595143 18495644 199968162 688540659 956123743 142659505 25153910 874172665 471055351 145576806 527625541 623572103 990973657 782161520 457497111 405605463 576502650 837454565 676903696 607158339 373938682 780704635 732678573 16532974 873108393 188468303 517766220 328568908 554613781 631512398 86909767 101304693 203499271 685496683 12714689 971386430 651800375 151620176 238884009 455863336 974027907 979575697 471501742 240652671 400860811 21779412 302505677 423795141 584839938 34166976 36161035 190306914 249476597 224988956 491267276 325674850 42668162 950431253 303021069 837510304 571477541 719474586 204938254 934272481 619330271 868532940 690441778 748362474 393814237 104651869 588609994 75759459 445502245 491629790 674559935 558417897 362622535 475026228 50656985 570327985 679688463 361515171 765034569 770993516 870047161 960254223 882159340 745964954 657913171 471248547 187682699 203162764 961950815 884996446 208088822 595308772 101658921 807602360 743367652 122368466 47121934 640636415 305669348 783667264 126359848 771475092 908961583 45264573 192582288 404647198 709877387 272250274 156825246 549248964 993037420 439197781 860868745 125163637 974149356 3989604 820602868 961683446 546763067 580344657 103385016 67217027 700713452 266672670 369183858 733945729 852932038 795667681 922683003 259040940 353071594 192607437 376963957 812376678 695570224 628366507 505234608 343441366 120690346 215975503 399008468 682445349 676749889 577605975 618527717 375629020 259188234 306973563 419573756 545580265 331540108 285855760 728927668 113954278 654186513 531045851 931629588 364274660 804871190 182581600 969364830 678398407 465143464 380420033 95928328 969501771 37584793 57278595 344232016 476185373 325053555 613991999 828942911 63364743 492513688 753694995 28708625 111268169 586430614 744182924 728557275 515642391 454798739 183690436 315242248 970281160 86192986 900612214 557819247 982465743 967303197 846070384 718397978 626010878 206439213 365932325 688237450 196431953 740194717 635035426 214473725 517759838 854706201 630668879 969420468 401901176 127951675 647390468 576585462 964988360 543546917 807651489 321507595 730344363 207691752 345887089 312366359 808691284 503600549 672004934 812005364 658447064 563289945 319141256 713338489 655493034 803880879 408425661 801816104 884070817 542426720 853898555 172351537 625229215 670338246 496953189 13494014 842129018 313818045 6255582 657336526 311191330 94781783 15310850 220774105 213938389 587928801 97009745 371863959 426982665 18998717 313447415 147220750 546204788 908538569 300636929 214179435 923629804 836569433 936453507 172571704 437754331 315216092 618622365 171492549 257155633 53155906 989527999 411015500 936148742 38444322 639328328 130769492 342740728 427349128 498307805 137455707 910766975 727096741 103629078 928115899 608935851 566879415 335941994 377122882 197549712 596833578 344123970 482921 296255163 949935476 812578774 523351522 62530134 350077806 215775696 51100410 353901041 465448602 299926551 615743511 136835056 938549121 607234790 554985650 531221897 186064422 745891935 461421994 672681291 982322528 776610081 631835787 596834138 782124287 41771113 243279889 754246891 226102890 573234760 565446105 83802333 331167965 802088532 173412801 230245533 852326211 421882269 976504965 671821362 207166646 688837754 233315570 268060386 695659446 526230917 391582286 755878194 62806342 761962359 305480426 849556223 465976200 623726884 434483491 633534901 470943508 883137486 471145104 585815862 463339985 336864035 610075105 781844266 73034265 403215862 990766629 471377332 117695107 339168057 431019245 234488478 268437687 996738165 574929966 64866657 392815235 81405625 707762703 560536187 440843008 151553737 847737970 615314255 867878467 139925774 221841040 949378979 585294420 531187264 45998376 163507434 122899806 242573677 501767704 581481395 743937276 100202655 205183682 309574419 953316964 391380511 554937978 311241910 166577969 315831368 935066647 479728843 106353887 166534185 752605321 374090502 548738983 924630702 577503216 53863602 736145605 767738252 750131389 228646506 122174680 236733816 720779385 251756347 768508547 737788485 847164782 151378676 180552048 260738712 411916445 729699635 521685724 448154581 448456044 724744425 764004423 165779002 72817834 964338947 182714731 637196885 232877499 515757157 714956768 445204529 510690309 210848430 670911891 672636994 122328989 702537764 979888664 45322690 874188198 695087852 226226935 531701182 392379677 406871512 772623554 558365660 897635365 43853269 705210804 451381103 475034413 677891482 637030264 963786125 217398691 575037337 970945805 619374100 596560816 509707809 164513538 568055371 594997281 302495326 252136203 890464674 886681226 252774748 845990675 839583700 413137917 129130660 880274000 392805844 869519493 931542630 279369146 984599682 61521367 5316606 236627096 877145642 388688718 760359788 598328259 890171731 347588522 987593390 84669923 948539872 925649770 572588078 618566230 255387299 840294630 766706969 753218867 860172264 480476618 98498319 544527417 185874173 83256568 549872376 276758123 54380211 640565218 584713876 283135275 975539136 880186587 969625143 405497208 191226174 61396212 947018736 506521166 288465367 59639357 671399479 119380289 417122243 371870158 778758772 576921730 270523594 947448363 952770544 138817026 463992739 773545753 778616685 305221466 47778012 866246888 124847535 648352253 328062295 880056075 378673453 17331652 7597384 308796865 95630133 37739229 932226630 844857009 211566038 777371275 44410988 674148969 421889100 727595291 791768156 773659587 315094202 974464234 589686356 262100453 814845482 781785009 855777047 23191155 505644429 705938386 692533866 552380722 230302503 998158786 545771773 263174096 384723038 370059424 426473000 404600152 644470182 393325916 526156365 745470502 757238571 246151467 36173968 775830667 174142486 635006696 737822561 395488785 72525172 206288447 693095217 658847164 843811169 1132702 867949837 529511948 810627557 721702870 224251549 972443310 178704263 2517208 844739938 951973944 438002568 993119067 562742123 139469818 782247706 628226513 153111049 162728265 360712865 433286624 714279241 147417915 829472943 47101106 392615817 891046253 33529718 591822846 473954442 357055458 298040526 671661702 376928294 186550880 678386717 858332931 389319962 320788150 13342935 702685382 447523283 83084043 212858985 467113860 939854572 885303774 455596779 543490795 588904002 704363560 494628981 474627323 607807533 143990401 330118571 536663063 424110031 104361994 664398776 357555213 710937837 817319633 672630001 188212924 496698293 870019945 491691245 14867782 834789323 666210312 707449575 707412837 255454351 71555718 90415677 663233868 824928309 825114996 69074950 718056420 449908338 644530178 446050564 46194399 647067826 783160031 909446208 948886612 640335760 167694251 467649212 933531781 402030284 470964904 909888508 97931878 320732111 165640759 4870778 533220444 663242301 396019882 295263142 767626788 512121104 339011652 111508065 740019601 749935623 52571033 634304895 130218883 116970448 60818997 971577933 921346558 315582213 215673128 73553987 933652400 251179773 810717901 962330088 631040348 10781512 389101255 523261214 757854604 623280990 501048022 108990941 331069524 511611864 687445019 948748119 765323082 866109749 919662758 29518134 643134619 265428102 155873003 553389387 741587963 359438671 761814702 434958150 382743913 935497467 710792301 623439654 403298169 290237963 110862623 720057625 548473624 477902518 82392830 29757511 395386366 271494120 770806188 482335968 535563249 551178391 979132581 657132077 570105440 485349699 557122994 677573760 912415490 886749451 29075357 745860120 493343362 551495071 263632772 519801961 982699117 442541352 527443651 631086332 879896859 936970181 502597966 674636540 339690077 633663238 643448887 486333421 523258942 540102946 777720921 421069210 824830685 59788250 991363987 200411558 384191485 951843872 31855407 267934175 880064992 268507900 935197098 907521508 447398562 425677055 461895906 56318171 644355332 451627680 972567061 384845229 483789710 229289348 127779621 749814789 519692082 288634526 759931579 954157770 30625909 975236951 295599928 675451089 265208825 126051118 667262837 184984335 88462441 339759142 672214040 142708978 536235199 868107864 946160479 167072672 254850895 421124979 639701398 561810059 81802628 652863044 496873745 756269176 430229644 849369421 506807890 823432725 486238216 264008218 605981135 678209843 96498058 72748384 432381146 389507722 734080120 879139307 981685270 224450884 78465169 818352457 105525717 613514387 871363890 494484088 859966331 925614796 409022224 17573271 191990647 727742142 162236219 803456116 546602811 491922234 204147993 103757340 687078186 51157981 356022437 146393792 311727962 464399070 784686517 265271236 823423236 783860130 396937727 327213750 678911692 728844929 50916181 603030791 77593780 564646416 155605768 527804202 98355936 107943019 124798768 156332320 533162790 63348538 502527380 626704025 682188853 303260205 27156915 583825310 387215236 70050710 358512181 574371214 562744141 71421231 389362177 138356703 109787668 399827381 719711597 825744288 819899079 520750216 142161076 909217804 279783845 346189201 495562024 542808820 638602236 83339342 87755200 319298241 902511804 880361715 362579526 425657943 380982758 551039548 480198490 940977897 625405933 850644492 932116567 387469778 80946226 950151881 975605041 616733343 785913131 444825701 717306096 350262818 965517557 238999763 507714127 658511739 923316895 598494635 832810739 306955291 15810754 775994855 973876663 475027026 595073169 457350756 633535008 219319167 735409155 212740712 485889727 337312850 992640481 597261630 453113282 884188245 741110480 979712943 805697760 745566456 465672381 411840164 410053379 267075183 944979340 566727328 277180327 662000211 657274501 462269417 29986215 466685782 699422403 518716295 976830380 634670915 4430551 361160124 586652204 390531125 241504360 17435042 926843323 806844726 93997541 282086546 510613353 610316230 376355616 291851019 268323717 920712383 272405325 768153506 14728024 98969422 247092696 508543048 791021819 9221229 269784867 913712309 19070644 13930076 310862225 944081605 447480224 33440562 361035151 412555546 578832433 695862264 737013092 473622997 511249816 912285872 212136177 5444973 673785036 631796747 971395491 356602855 170208465 979207687 162254801 218662495 322728361 925066952 69751115 881659658 663053849 322232460 235695071 133841613 552008938 373963390 39595878 952885695 638153129 23555918 581893429 208807196 886535623 115342980 64308886 686431954 550836244 848592454 360262491 868550092 353351643 435730267 687394077 966533941 422535390 873720503 339556411 341716551 285685542 402667180 247348240 471875977 793387508 191225093 792513235 459859324 536071172 266806219 24218043 520884870 911279710 662134332 779844675 513657235 364315759 198951032 739991292 414161068 82185180 841192844 980598418 523193677 511666995 387135174 915785790 880055965 143526311 616105666 326361545 334261292 278525894 296920743 995287456 394219513 857643277 916734246 492644894 930499841 56801164 269688354 48423626 736797244 426321683 978198675 80739754 8309636 198520812 762635304 34496231 616556690 39427749 784950459 695646513 902033229 281602143 686038640 802232728 634685291 183360213 682242328 369612602 497851978 719921778 754203713 273672299 229338777 399870492 262360535 336873048 238456577 252968861 130465548 498653121 661117519 361326926 965943532 970376446 17912647 236020662 780949728 794162883 712416360 605431413 170148059 97539486 755001543 103383168 182216639 422262317 344901233 256802677 88951749 188531306 908392124 880214544 372595976 698591615 887807257 697897552 223905575 513574591 262241480 409156647 7483762 477889524 736650035 942376240 19145528 239009426 100917660 971193880 182398700 864877512 217205548 2919194 365552876 396720212 659636210 5293929 458468877 556379047 654441992 928503970 424409217 962039700 968652092 550379269 610819047 795577601 476287750 312046650 168145988 286500155 54676679 720905151 76827123 998146891 109540365 838582690 650280308 322878988 220382862 353235292 124084349 127087250 946452960 495270977 554038893 137815430 499185891 813612984 375345821 820084013 423700311 131973034 364300227 261332250 458541423 200204946 847361771 252006881 822435717 679790321 334304983 91785307 719827764 761118130 112719556 557711115 399444970 415445709 209325091 117273525 802700125 187532044 566259252 91222484 537624634 961843300 967229655 975523497 980403191 155667630 309222143 153927845 390013765 367837836 648505883 937829674 978674444 539034236 696252631 513693870 184889556 820805737 982866693 412483415 545350701 129358637 816291318 996377113 340868886 163018624 46459232 352530551 757056881 91682764 166093393 289262777 973984346 587173658 392597095 699746308 297309145 594163370 975024819 318312138 623109503 21098326 632975707 330709947 700400595 242255869 766877630 536432400 436556807 165156177 980664370 226557142 849141897 791931825 427727754 983974374 846910960 101435695 851402210 637594201 231698442 713718840 653164964 434779748 156575986 962908241 731704255 849214678 805752017 483029615 931589611 943371491 258210788 871805282 940557208 681697995 213382674 81165033 343463885 627676560 787283342 391272624 801053829 280288714 74291646 475308053 789561855 462519490 839164064 127991170 358414823 193373009 199178913 57632522 193809091 162630413 20845149 540037987 880080259 907059021 29935735 142530928 730609624 835003028 803320375 506032565 343719736 431620292 107546359 464100477 484174406 636221751 333003194 189782832 965033918 495296535 944993292 835700541 399209309 758910018 881870029 684041897 559265749 429124638 47895114 584616165 790608659 804747490 409154093 336397302 442158565 66296267 516809469 558134664 57738552 209246637 470059314 740580941 2049759 413792014 600577012 621257602 379785001 361256210 476921521 815086492 325587411 515353683 208574601 875688883 315917157 168465686 743043115 578255451 149996411 410719774 402199535 6396803 498737877 592094341 298936890 551913353 117901284 75661002 487018615 183636956 720128625 728537474 632404875 164071069 543453920 733053553 847583464 468555325 363922782 746661900 932176243 600719140 898488488 232653768 851319541 3262565 182896685 799186587 36432869 123262869 240979037 797565512 529801232 440840726 749800442 751610836 25001688 297308328 304899896 420173656 333834593 328932796 173043708 383571461 306862882 400043369 234380855 571985612 99069309 954654860 264038193 435907113 851545927 256321435 266362430 604857222 671902141 176325287 862899576 426547249 750369354 205122609 827566604 18629833 244120913 29316497 229048326 880501164 57371362 624631998 641085558 172841051 303883303 338717106 613326949 281733027 414875783 894243593 788115809 148150987 28392354 501703347 172956905 138966887 337895095 863634909 945952091 777569944 595753854 799069415 557295158 2239768 703248305 600654323 774235747 805601072 601044868 910674535 431803454 544550659 150770743 909571805 132566461 364274813 279521317 78414548 692360025 141598277 398353784 54263759 169205187 841905794 714485986 291776107 794085472 164884186 617418249 326133229 731376420 25858449 579095827 310691877 274827864 195774132 997962811 564466983 785444706 59404417 252557480 913312533 294450435 271593130 627113099 544913813 549599630 158794353 313394845 770948847 169397944 135884022 657295091 699590958 322016880 66212642 828805293 822352886 934168262 522670195 293809199 886071501 683767420 803145446 135400610 622969635 42148253 907318519 369481429 672141778 683938894 239705003 636382921 406343485 164709528 583991186 560018905 900029054 419177418 890565872 862501320 335264557 321252830 54507340 866814968 106600516 452510909 678078548 473098938 260062030 912059414 982862056 335855930 267296346 954059913 481406977 699110853 728941667 981476259 528740779 830777511 785370007 824255258 849800081 767924826 35211290 805354976 193637778 708144874 242356395 773521558 699972386 550970791 216340488 148930044 458276596 12027216 623085537 710366067 933207127 518955677 457638213 927511006 546936059 493060821 82852524 465325349 811277327 571643441 791660504 147127982 512639313 733019565 576793428 210060202 146776541 782070290 81134734 609334648 274480712 779181562 920056438 753426467 13763367 787418473 32419658 170254923 870251319 162520060 665595563 726295069 844179192 68180195 52723434 215687494 234513575 689333753 203959907 757846881 239258962 755062700 693172451 591180399 223898010 969931676 910357751 946965390 845508981 582151288 280332442 657027895 405338157 390992263 576669937 582009558 390923648 269659743 279668499 437468638 635134065 649071329 605197568 11793919 802732420 184953343 450214348 311717468 620551797 784459612 776967654 69234538 585899381 800073795 520252178 57797274 587575883 899126035 629768458 464813428 443448800 343914613 949061651 801615556 182077533 574748894 50498116 690185137 906770207 324311929 508740042 469169139 341035938 663478920 754877857 155674169 900477268 677386604 510261599 350205082 513579834 851197282 985581983 591844171 96226249 43572200 477221436 495626648 647663762 54470810 165370246 57692686 709262469 826539626 649341422 445659441 813302679 163977408 846065187 170332952 759185672 508032365 227453651 391274875 281354831 12151272 37075514 834140477 157620428 624275577 905550839 179614696 851435854 493961576 664329891 945796860 822837535 779078326 418103336 941523670 688483318 405264839 409438962 411960881 814243505 611795364 693979285 425333145 370175127 19833260 862271203 190974379 126137739 867027227 297965462 418041615 518385075 887434603 429163304 672835212 825061844 10282014 383205640 771513721 965414098 336132983 869393650 618271222 186439246 517645274 985984561 548540553 668823991 166244919 429678105 418590128 397244934 283866587 56031293 344941210 11167147 551758225 642461150 195365819 986175873 792871910 532840330 695471219 100583778 810800085 246245883 980868326 387411540 356132968 474979372 499734973 178477800 834423705 813562221 752116190 377314509 519613473 919872403 223637051 950787202 603231312 263724751 507372711 612257215 11064506 587726314 156934574 767712583 269320761 247017819 482060498 72555204 983623458 231883808 95506157 354414867 180581366 743037993 174886059 949122636 460353715 531970007 182720097 190782203 376480422 958986401 114084205 691671112 302592785 23856426 132708072 467308069 733070235 369179272 858554766 683560208 313230416 448082859 297250479 635123164 455028395 994687727 530526092 887519238 687043587 538022484 51027479 269846822 841409348 112693642 688509656 491336319 155237415 18794417 911221814 711026475 828486317 229286696 149260514 190315582 593342202 303403438 707348197 227733894 533121206 674966424 405519580 621136065 347409158 627303093 673912096 821429057 359772973 288966867 20463549 529409007 707265469 525261812 539617122 287082151 632106162 133712832 574348491 96126263 572906338 511402643 795204535 702427822 448729611 350646312 493680483 836639349 803770932 139400112 231701828 559299032 277556542 194644780 564363759 623058322 80744534 889460790 883954956 143061856 98063405 287988256 197738600 593127890 226228163 801495524 831056937 731638746 294960150 724510013 260847268 380983270 528079619 996528532 32022119 730229676 217840298 556462333 736546017 347696528 159384626 741787842 570090580 391003155 719263562 306171758 470318528 188420463 291227888 443713788 940982185 329502281 170045092 36547131 151306064 643702105 818416923 179118405 697311675 481134927 31884138 430709076 303766038 968294299 231116113 46172948 878000552 239138835 127123456 964468907 692006098 575499182 532876125 272227675 945370494 69399942 809776340 395731417 357263285 480753765 290077749 631376849 728007036 458745750 479973349 247387220 341908917 65344671 467583327 997649862 462668165 596974086 877707367 268599107 188292962 114554508 571294709 124870247 297391532 89599861 646116864 812849909 475190426 408307473 71941505 637471740 412297768 592537760 742895068 922324601 478891449 663625733 175529994 48797840 853256582 987784483 480049030 368985197 902711293 513112026 641699583 426170480 674236677 138608326 892084537 839594162 124282616 781319659 673145204 452061986 869689420 862696698 383982365 315159621 794182116 294457376 990644590 623591376 845906022 523282477 868054026 732290926 204108124 456746504 734031366 563334193 175071248 833732446 225585012 87242133 779066327 724126358 291575129 290257749 60802719 324160331 216028679 33317984 922082434 245175381 882817991 108379522 537764112 488262841 588355019 682625873 782300990 196284107 929724542 530771619 625492319 925760967 51615879 455235226 873527223 643768828 583480265 445218972 967974141 709647601 406463003 493186635 348482900 89125179 403627761 159583466 938748136 696687531 530336644 213869590 183111659 287128882 805869722 19115289 71666942 523597009 589014789 230505527 706427797 405763111 864279263 8270691 517544831 933285007 935981228 228145662 38877481 521394978 679723261 976906791 807080575 622356602 925288626 13997676 673150080 798997808 843101417 15564856 104320412 365103157 877974541 306926950 265421775 438762425 493879226 529307786 273879098 738705 696553627 988194120 226611154 602396157 464445519 348592098 241829847 269980546 506417142 603492427 818213687 904124784 571544428 806026093 51208450 743993536 226408498 133732798 44008726 692025459 698338523 933689618 206864025 490921871 179520335 2780457 368390375 964767359 842889881 824769075 826592686 318384862 624918963 171775302 85036564 186389115 224755768 928932836 142282602 975174451 878804656 317455826 533700112 239015845 705540016 292227407 424860003 315744215 653833606 263475920 886597784 349094692 458289445 174836941 847156561 686498248 60363523 857422219 702988457 983964418 411090658 239289038 778056915 765526248 826247459 160585007 64999390 107472648 955581955 703725315 764395242 305502437 474549298 257493576 889036546 377313280 138960391 293964802 15253045 177829781 615733420 152256020 125485520 307524921 674640727 798522343 293910961 358421147 742032630 200817635 88439941 532597705 394299488 612100016 925918517 418465131 975076475 455286662 140832268 211713991 863017661 328794742 564604955 8309798 536433099 61552969 476025367 214783596 640436197 641263402 473656756 1058732 589915842 82391473 908199170 432494961 671616878 857177378 840145789 803968053 660540531 980820011 855792504 940379182 636431087 142805934 381436125 270481684 656315621 7343192 988828265 565576046 682833024 292434154 528409895 786075293 889180298 840547106 676161445 458596567 397476316 501422972 512488814 409956681 475710575 522139177 40199598 839545549 105602119 858523650 972701677 68457378 139114106 439269469 48402823 170927799 92269847 231590424 895725229 946904127 870182403 389264702 757515803 817892157 967290965 270893257 808504027 801410604 882696107 94125582 336681387 223729640 558754065 808989297 246094917 881196137 587424900 756791493 412541784 340788792 284192355 987782487 735826221 186566332 519469678 857453503 542867379 457137680 513731999 663291035 3311822 571137406 757398410 164000514 519853205 631680001 718569456 422299130 113687820 731792701 299617787 408116663 524919704 53802629 995411023 213128299 718220186 820920299 831935073 501679732 635516068 287590662 661208296 572443266 243321749 714381550 30983057 217255439 503913859 564841141 291422456 784572690 134031759 892721605 477861585 503348032 248608249 609046818 523709044 363966407 487087689 801381657 598263308 511900547 909989631 833893916 374789316 540287487 405982842 900203986 101108705 966554247 389587108 920822162 9976262 31940231 611505234 374628138 488792633 710167618 311941729 903856953 951592929 649837520 863336052 750240394 345075690 218695195 47973242 237579010 703517857 692582228 553706115 323441012 77604712 929804023 146357902 924501639 425258600 40732413 828012095 1367764 807012852 382667042 437409918 345688043 116416064 394943254 218746762 673002580 33825 76961856 221596527 779922112 240257338 880014529 915162442 793944947 897127582 490745081 850793353 166702403 235138628 648120364 995442079 207368513 325486484 811715365 15941448 732942964 134436130 792233 801347980 382385440 409449071 226531812 281734242 182696999 787510724 257272305 438454078 231754643 161028120 44074430 959630229 864935210 678783300 250759862 613182992 898555613