13353
281568910 432221387 637577134 678322894 795037854 208320919 483661055 378943707 424205289 114661623 723982594 707567282 43273086 177601788 837472375 45487989 348442902 5760615 443369035 238576997 65908605 582901636 241257572 966519045 793493161 893835010 575924603 939014025 789733333 308751924 88027377 71302243 740973310 725604511 602141488 388527515 786441781 85802542 767471221 210647069 52980516 343970167 770730702 96253602 521571954 460719429 994257942 722531208 466480043 437626976 961108204 532388648 20528612 54882127 498907692 666538124 948717136 74832294 605552149 590966821 236100569 546095877 514785415 977073878 124216739 116926902 365601392 910658519 55245796 985588965 121305588 108226311 182075483 744552641 56996264 703647436 205272069 51254206 278694995 671752112 341397533 92319551 56657111 214442496 147201677 555564802 880980620 948435165 482913447 339049120 391918337 719014016 885144996 906703751 548604245 9361735 876147004 914205637 772536605 783909151 752310953 746358544 744651814 934386435 490911185 801648077 490550222 548699605 705418634 769245217 72968068 899332519 861564767 129625178 113775014 8766443 685189979 847271985 809717959 20619778 38837456 201636295 592150145 776498804 960856397 140754389 638376890 689519753 907476377 410913494 473428903 659787329 9788390 70597068 446690115 500699574 872245145 937240337 49399178 430180130 706485553 122367246 182029000 420566671 104508775 148320366 281849465 789698754 995592350 91567424 662834883 886946158 145720070 254985027 663444961 106576467 248255767 154338202 796096219 155732144 565251695 122041473 668035824 575040084 192638541 114725939 928256009 917400037 51966275 830171539 200096518 610968179 805055136 382125518 31534849 909563910 530445883 165900665 551779015 378554584 257468088 214613897 265500741 403188158 322115275 781462053 362280976 570371042 935800254 10893546 726103185 353568301 132935018 246655360 928608384 178089910 361381298 709380745 95489946 265863924 539552283 295586464 729348454 197123770 677711981 613399654 106687679 60674215 779300319 658466694 439228798 36768406 725596942 704729539 292472915 47712217 338707943 654753890 618083258 274508197 665647435 196702794 628076497 651098805 443358153 409201232 829188714 657255803 118581976 924678660 923119726 510650610 72781475 504984532 707774379 603009807 118384185 666978410 663684021 897684503 177961455 102912818 786969261 903558396 660158708 931958527 951270612 998866651 439228769 421870221 125891199 104876203 471089366 753967695 608491359 914447519 15685278 437680073 424219673 986783606 214875084 199855750 349950567 140172910 704840281 57724946 743182716 823224466 577219707 406866736 573425320 755181161 362295905 212910932 658739556 22454613 144869459 462526520 21321263 436614579 736913092 147212461 394007133 208002458 753696507 2498492 974966328 621898136 292694916 399186000 608681741 507569999 599041749 958632308 647742908 156398382 868873605 243441975 979622847 298609663 650308710 405564518 53790823 12604614 470991802 565046730 887575578 468377612 27573249 761413192 904992190 617002693 761142004 298999322 825005150 367354862 154014165 652487829 989252998 446709080 51673828 450451090 954279078 503231928 261599749 454538337 659630309 130473353 697980311 491769507 281599367 200805372 749850377 335390189 65926338 220842178 900436919 953501915 689219789 780526519 567431459 446728330 250045563 328573462 745727651 75050712 695928324 899741816 580054892 537697673 198967247 484245071 988148762 5762677 987476999 249748511 460301013 499623659 232738215 10797676 843909518 514337582 64119399 593759894 702244122 130045736 667118423 455197392 936064003 208854563 88240263 503495461 655582892 338285825 684585274 253826894 265852889 233029949 6085061 845907780 770727621 205052308 330152851 758876383 210814984 170146201 861141245 671115996 522286211 93879459 534430023 366195728 460733392 598549422 812471973 15493866 728595157 479590395 470691257 517175511 688444957 558931519 20670971 196544200 897217344 557772597 450371094 163070232 790802545 456456154 8978011 561530166 661508461 191647213 172922900 872323444 214309765 34064144 395955792 736595976 980459954 930385814 102791703 293709698 528935235 767780028 309203563 110046744 99886774 779894819 627222254 788331731 191342690 500409577 984875930 88560033 58182173 287763375 104146616 701501069 744219529 113124626 115547586 405727989 157288191 288470485 130567785 371597955 175050980 526523576 108193930 8027286 456909389 63501985 154253335 838360976 683798364 463456897 948407719 783685137 95868067 428146324 424533219 287210756 781072252 261925501 228287140 691770776 549688875 332433755 393271845 293908403 298074733 508819430 552152744 455362923 649806267 682720528 679477229 824857246 209244103 640187511 685400883 518669843 556205847 839654217 357030818 240004210 155627465 157954888 23689346 251495532 438617564 300738917 391222639 219689815 562664417 619509779 911460591 112353291 951943533 157248787 258778046 250018265 518584568 810930789 557897539 168390834 493651316 237374768 845764432 555411770 877562278 531165314 74081612 286284476 223335883 283628782 526288685 378963347 441583669 402494382 630458878 880201232 703233298 21681517 952407399 118414066 493707647 716384341 230767357 445651179 873633127 489545402 548185796 244734046 152992542 106083334 413124880 646643857 195974453 111405663 54571978 73536730 642570976 128653589 212337557 865906858 412282370 738626241 97386557 706382391 993636975 727845434 439099974 549386624 602043302 391507372 667800690 95750948 107891712 898568046 393918479 834041190 240629799 942104274 78775236 393622340 900703959 344416467 892782548 96678412 455822129 947354525 22731493 950909456 76008113 235069050 669332666 340806835 826211642 766719222 47189225 819848616 347081007 338805550 221751592 949124309 730312922 889552281 897391608 690720985 640636678 143826438 377278527 881266476 938447063 308570114 127405167 839151022 505502932 20187714 788345785 961325060 820058590 811077277 764750867 748583054 898662678 434083532 89389888 724874320 53319105 989095464 397239287 400400112 180417366 618990878 202040772 910730287 361059510 99432379 453967623 1696187 95775169 683762501 735479014 34222231 992332614 862884180 725889604 350351897 735588245 366751740 164193308 408163186 30345369 928944175 156746240 929008046 215544058 98652479 506398717 268863163 940264295 903638004 669263274 120681660 375145233 871304045 883928298 736204743 823252775 190412272 590417281 919027943 874174773 325896295 805766526 719023738 41296826 384172481 69375635 629401423 750924221 233568942 37564608 781269589 15029468 46827199 562793986 230573526 145479678 69192703 499436688 85743972 825347058 168699961 58941983 53008642 40004005 942870280 789213384 715773131 133282551 232147017 487317426 859973675 558043311 145600303 578997413 451856488 529772783 500889399 81257910 133213355 734458340 118822518 766999295 749487808 18166068 329793281 980061333 163645745 251502335 332014372 101906068 76849392 500714332 13364402 129858033 393234688 956234681 771587769 109007818 942033584 3734785 448841595 654523610 414294447 594441897 86037374 866150934 124214680 586926772 947408844 109944386 173901464 918747713 876943681 923389271 936913780 59253313 755966955 953075877 310755647 87981326 54981944 240121390 441212009 68346346 369979422 686963048 877097378 141567190 648487217 671647313 997818326 97328812 178687275 412112772 691770708 264724648 130780058 668501739 851651420 78188901 630962477 25552883 849452965 360422509 801458505 638883096 419675821 409941811 444475324 582947819 350439488 351973620 823069208 791651496 272836317 45564981 331130895 2450046 39648523 979618111 674097359 37466848 76946922 852784633 302095972 621233982 117509280 432876029 142252072 821677051 363581281 773214548 847229933 65550597 133637056 501204789 704433692 405829228 911146599 1425368 988777046 261586086 353398987 664362605 905753933 626235303 709927586 236884827 628685348 749576108 69019290 155299058 787042955 145966211 8083690 89138926 619716544 978109322 374531306 614484968 652302724 738112586 240215867 352049009 803663182 226369275 853253797 360613226 632198502 764400396 362038593 473491900 878502833 715437579 137854504 784256766 341672881 700298441 873657944 970358228 449874548 942677233 125657286 89433855 941159796 986257327 31089132 413392691 816883000 405620438 27877658 321702076 143733023 268093525 673751084 799912557 494462799 527004880 160525782 979177652 143921627 522564374 305185903 22424460 90518304 295556759 659197577 432191184 995855199 385371872 255065763 298246099 328049105 233239400 387679953 121725252 72013079 271285436 535117942 741412430 676905873 562995600 63114505 673155248 683605476 736865588 325584156 30584626 116386820 486109937 9762277 112824798 861190662 314948180 135249257 951708965 610504938 646963185 236416500 458876488 32335057 491482262 757122586 212900513 577238014 144802538 334625764 649251092 268604326 869743705 243179873 945510198 285255656 306294378 471181797 968861131 895676317 796765952 999445756 12063136 135392240 861724385 124887934 996582901 29188916 112653542 800808217 639693853 612133079 37224716 98570340 496984487 381223330 708209278 562401351 958461343 705528167 897027114 460228786 974132492 619287170 703408658 772159042 757059178 9703035 95857190 578436660 757895704 892623142 430398768 622475191 880531733 292123152 599879476 729630986 321312067 565049370 530439202 813522271 29698800 420180270 764608962 526683286 801403599 472818239 89084636 759864941 30862758 838628101 72610078 4995249 310431622 776018735 777154290 67490799 638238122 873011480 498443811 396133825 618150973 928842578 18609015 351199057 73482081 471004843 80830042 394794147 36054212 463785596 60832769 65753011 883965865 825441730 444952648 685369463 150776321 386553635 297750755 181639078 77698087 370360832 186634326 388129708 146379566 816304968 308136859 637134039 541832799 806580669 33267863 12500123 587939598 904393230 363699179 661421678 227914424 444529221 56215824 263968635 908314816 117048592 182237997 644797032 795006673 627190644 182682846 945782993 13744278 480433600 127422070 91442364 703310783 166572748 332088423 702206700 982877715 640225281 339340739 524710513 299322301 225124953 537210635 887261898 982034534 900909813 401199927 209948957 197955385 309932102 326433943 958786552 279497045 508671939 603583583 74503718 135862582 786266428 20286710 2123211 119216379 225132 93565574 822527161 166797879 425653997 377250213 2191945 918395629 716590951 526902457 70234282 794232255 916629443 957496179 776266789 670055607 211212458 838732097 868010992 521144559 165166040 679313895 800641604 673837978 135413830 875145321 662216912 921680257 747948382 664340122 893412988 600689865 757905696 568456500 767487743 36076044 945706712 769679687 954471672 514814014 149098495 24705953 309046269 65727937 834718484 937829409 588299896 45930941 776561505 308827239 419591851 794243896 988141133 220233454 320598226 123554962 947895126 982815137 897751571 548359860 647155258 791164558 149049724 257577305 212137409 769053819 146169700 157844121 391249857 100641372 672658134 540348352 977863676 834220754 458592640 665098511 772050162 46892535 563545803 401128019 208236125 983137654 47888266 196377258 55887459 368486491 172448571 3782585 351301627 70200141 404658796 850973237 713881050 553708519 108550541 926018459 175278689 107236593 83862579 566528546 60394316 609037064 106876897 38257991 295774170 417985888 555872854 67824331 317394775 971935008 321468701 525630899 807589013 369356967 574524508 863476472 737843457 746973079 719775408 941661436 817173219 124434203 792634672 383570621 530659073 753701564 309589079 705937762 860938156 245968009 124982659 921332471 707521424 84375907 812106814 3295593 502361794 220496019 923636276 672272920 44947378 97621328 50420171 852536391 466978294 624944678 568529214 57338103 371917756 140820973 998999538 41607327 117771527 644150561 425177947 648430599 250368476 587283377 206884712 963822984 833251385 331867370 737671806 393289160 416243276 402294971 396584753 771121422 622790989 172737380 443394341 667738367 270358707 493814511 372791109 737337001 118759189 941320322 647191455 343193296 82141294 498707344 237316974 199912820 142857904 662494920 700859770 245742731 102294648 907744482 62082066 935546032 92128203 799753872 181351544 360887831 202048842 577936296 132009252 677356183 750673675 427919944 197610901 21032381 921734455 570402009 610885733 893009995 511722330 110593539 88719642 446379975 609300882 326036616 646292794 604675137 841047887 199668915 850417868 943342535 107413396 912499933 731404918 52057951 564770156 912756461 412945781 766818998 343209108 397471384 296691532 93882782 825391327 494302432 967431515 599642133 64704440 430833599 345168479 428943121 541427138 433888121 875323095 3244371 612441088 374132240 607919508 453488974 573801154 310853727 249347860 533730902 75870011 980752778 585788852 640640167 893509238 851250984 259975516 89234698 248722367 556667047 35633831 74113693 50969478 3065345 526272178 115673917 286415296 871440656 397133389 680358785 157845128 272456483 683603155 770286215 646588722 291522662 76291541 72906227 602376388 325639400 606637128 678246399 306392177 44942331 171402917 52417767 896193314 431378432 141652464 144915680 988045478 177286294 71545725 39014955 32867991 450334254 7205223 171799638 321774909 256854963 852158422 479620037 529311445 535761576 102422603 28416518 679800590 178714143 101322744 134693329 504353543 707959872 812939727 810745719 752902202 984342643 715679837 501611868 268237426 857332300 499043899 256282903 887134946 423105975 147814209 920002936 873440228 7535783 91802573 47731489 264390745 796477346 527351525 646218541 184755273 629774127 674635058 864555862 808488270 628474154 999249191 165358164 188950377 664705269 976103882 941852578 501564264 544300071 295980797 769801689 254148722 795024696 26084592 141283667 218130670 26415152 913802954 91570898 33950935 858121878 139302386 150858031 654599223 519170262 797076572 839354496 1460740 324227981 556426709 662465361 952702134 555675899 827823524 141652510 72897520 656443758 936021440 574461783 200743828 84518588 344263471 454892549 879543283 222864414 448692568 97673953 101795918 362495521 41761202 135746852 73133751 33579939 139121234 727732973 405266552 788714157 419603820 259243643 112942138 976030529 921709004 918160623 384222779 749532527 912329485 457120298 258492636 700867276 31582080 459236463 785385863 228361903 766645364 517445498 303742668 215337931 467635802 405538585 430349803 361913355 393801788 503483553 248009645 532923022 83732878 653276196 174153530 503336697 912519838 139612019 331883577 686745193 57772642 568622708 288794072 822618478 25743005 547286707 376002105 909841437 6523170 13904319 990719691 625684885 531349816 294462358 841022815 998985617 700000943 123888969 213415323 93802730 627372522 461424967 479242103 711105399 114701162 653395633 66958447 879737352 793007651 398842024 418998896 703296644 967464731 707792967 378431473 845724087 255079674 606949929 608081875 114119195 620854248 451317917 739804079 4720415 745780275 433343245 856222384 298297569 557232213 69637706 244616650 37121086 531062673 576375105 748226484 498280186 82287089 815184931 230533889 875294739 66543306 649532785 431107735 34008036 209842103 662055559 732248474 464921776 269005488 192846701 431557322 742376087 644164617 23877752 747096501 242461243 457220996 455835236 393275163 866969561 525472942 637891813 904090646 909051966 66783269 652317130 259848503 149070357 320018412 490382392 24365095 386561717 992431528 307989181 273086104 202273630 970044740 5334577 519711758 91566579 50697629 951269079 833942665 547378598 975146831 433555517 789839840 284884178 889390753 35631355 151853738 267380046 673523167 55944384 28948363 740306435 560777865 288796865 889376791 880796276 779179256 766258237 119874344 624127135 926763770 392960447 826400765 749324861 250811375 198628874 840891439 301509004 149897952 527350455 848887601 125044782 813422323 491243792 262445312 555329427 526875146 414299049 822709472 52914664 322759784 851657834 645737450 736054000 140454699 387630592 469366627 772150306 6405181 589240970 248793793 933168950 982201416 75194557 682493810 233012791 126339782 375901600 387038146 276237733 755768406 88442098 253798867 569190728 579685889 516244178 124520155 959077387 783059578 799745978 11992050 105819362 503920164 510245852 694389713 496891214 897876443 163756340 121557871 904281623 752997309 370351663 837450572 587715077 298062571 372460733 820727867 424402352 600878684 60282364 553156437 356647089 148724461 806955303 778354169 728410349 175715832 755390675 540004087 958775409 407653004 404512489 917111122 911573167 914758340 464017187 260980732 812634782 627773526 235054955 569432757 233287186 605406617 259399680 821002262 755985540 631860413 494246480 32904243 85255448 554528843 586060679 441902537 703253303 245532333 72773057 284180004 421248164 828163731 824184090 232539925 235816734 81212930 2167398 999906253 995971269 466184584 113403336 661122403 946474461 348458290 230555159 32277999 953864907 489954838 853280260 562366798 974331602 200043092 595271040 59587050 607088286 181331719 354005938 162857941 426864051 426778994 447037944 700628567 254942724 123738385 933168491 343275809 204951315 787852240 343182061 53438935 106553176 456585397 714561337 53027636 805043686 945116495 85305634 611424944 287587685 791102246 26308093 114435638 991145337 621579133 174022687 450749974 802910851 528028624 613607914 82291253 954807617 60645857 782919819 62266692 36900594 568604661 405542501 94368260 208973253 601240913 147807194 315526428 57826309 862368531 368554063 715386347 660001377 306376049 179327642 947589061 97478294 205635735 62024699 941139982 827214867 88563737 391889955 482642069 469108713 5497869 417449673 276432681 918660077 52885844 338699373 808077022 621490504 596758225 902445281 830463756 197999137 50252475 145990183 108341798 912621005 367060598 676244496 425138733 673436646 855572137 225244146 623431291 913724223 139785196 564571272 593455441 228348932 808977578 76097509 697457644 666991798 346063534 973890325 438168227 398949377 165106049 246245248 20439880 761864273 1206881 703419988 812379761 51459355 701926522 920721558 816596711 921503471 449482405 241735443 447456468 157570894 466979588 70887758 71295116 606764783 487975381 664750557 687630067 296952959 593364417 237604062 963944756 939427950 64010738 254629334 190893678 229116786 500874582 63849910 843497410 502081462 767269897 655877171 406057168 321712770 429115080 222653878 95732593 878597485 316905672 543189060 36168378 783885260 614076818 959979845 243166394 102052198 477246753 930796460 251521508 70611170 20916874 67982616 862555471 84927611 322611949 53449149 314044397 676002882 117299058 10058158 30600695 737085306 665935328 436657862 911314427 947566760 659311739 7047019 678680596 976217411 550236079 567365325 612619022 16829248 527345169 708301767 971397797 4591922 491614579 75435657 927719443 512531452 143418272 642791265 597459062 318546572 548756765 911503458 994549454 518572174 921561616 25150148 108173831 440013295 461808010 19488258 240096406 973636100 879051628 918777001 802369862 281804058 486142325 267505235 298633305 866003846 975807002 122547454 723112119 467421580 197983110 503347913 979953031 341401381 146139177 429928444 659947952 547412294 193948254 507013757 918500819 115509869 532163905 26674650 408039515 846488266 898679259 648135921 820124365 630247238 419429273 475010579 912051296 905571598 742515813 63200952 624091795 718322814 185748405 347203913 38260745 383731514 850551825 870730127 725132894 849207353 300658571 237597198 249135998 494606824 744610954 20153169 462633044 129291210 46827818 723188910 975779475 798023428 223841182 648420192 280787017 643270455 123430770 192838312 401358404 718462934 256039264 25450198 289302100 441787668 225170462 327562844 825519182 75722286 50809323 403168427 777445990 351467893 493281976 879098340 698591068 90409282 899251508 13740463 219700491 798595677 736929372 47996318 449135456 960770554 548932861 729922472 604041008 524879982 922760784 5399411 243342915 31316399 883365960 532645014 325620418 108536421 712724210 3655951 36775058 763533532 406824378 666737399 115001424 900106353 545835738 666108843 990515634 297603597 679849305 62732477 96199273 416778676 110728794 545334728 230065581 512178006 127773552 834106588 37057987 50534335 692022350 132917253 934367085 427904661 665562267 259987502 536441081 230802828 263643453 425732490 994336359 522984182 92469889 961854134 275606886 490821978 627962976 118638872 788425575 160328632 181371348 884624847 577107307 144616493 282475927 807172888 656794498 410249478 493795827 546368836 313300164 38334529 679286088 100183600 466239189 197364706 360171101 855196622 428167533 476330905 280929111 422503891 999315086 225915351 236874376 274921972 716737329 864837351 393560843 505162903 25165982 427448542 242304101 454789641 572065034 377296379 114478880 81375883 787545856 460791058 627744718 953362371 499125586 159547157 53545970 817881127 356911863 266233423 673077748 785079395 742564327 806523210 60099638 741879413 32438561 296974013 869317736 749175889 14327716 115394930 106855143 39493697 542843471 201675595 346799689 114908504 578971974 313794920 48800738 219034181 774585978 529061807 172396552 126227915 688608963 78458873 944109041 45520825 344692295 469703140 830600220 87256622 276226350 890699857 681652386 161181262 40190221 550970121 910357150 54517936 666365050 869728644 94011633 61724872 71404238 293327673 29149727 650376211 607122593 77950464 869410392 234224922 607012270 894323295 360452836 148137584 972782167 304561877 193658409 317474462 774265016 876774980 257247435 903007717 619991188 938899820 64188978 660181408 342386292 827062479 714699344 8751341 696791122 661227328 70476212 620711712 954555000 99625938 123604274 414193944 30092753 993014665 648418865 489621374 739854311 8871701 637758957 712636478 165949929 831417365 882627291 792731296 560708696 139874725 695739013 180699883 78774544 612444342 840881291 273677187 439506821 408096986 134944879 988814294 69324313 57937442 609526005 876395664 10079731 733130279 143105960 40172483 578661295 791524824 529793856 171031958 652912876 20069164 883668435 671379156 851486529 618812077 464110452 264711576 758686801 12365816 445411459 689977696 624810157 138809101 963654882 916833329 546906086 98599760 905647623 468746750 9053553 367689979 345142413 19133283 953336609 488248372 59305765 384514256 132289548 441615972 555546213 637718775 461685135 291730999 309097931 165688015 910543075 625724734 430399591 521746227 638090549 875811049 64240274 115417057 867136501 27895155 32250386 266558938 979011266 790414360 735305687 988064818 10620690 80448099 7198100 963957299 421212823 919020216 200987906 406018722 360636187 756534118 43737496 822321321 48265116 205351778 988009336 958808190 831076511 270925278 333070768 321683411 146736326 397311041 437100468 866389178 277722547 321867205 132948115 109250164 964797916 868253801 97314981 975418605 801218251 957029432 791892255 74947425 728565999 992880160 480966146 89202185 601930629 377219994 764039857 650195744 582571771 604565544 461520285 413648282 875490821 794591052 735331692 874743498 44418444 24948511 593649027 322140990 199332067 726597141 431391153 164129982 447367293 381222485 992064939 101101896 190768268 636473545 28565672 919334266 481870057 509531818 861052802 83800685 886751811 477609011 586512781 321839933 82174554 48033065 735488214 810181727 695140469 323336258 537441576 739558912 200801120 131090603 61699902 400133187 710204095 345607406 564263168 10087740 726829891 408844458 111189635 917598158 45318003 139755306 836932424 527188059 501803475 550501577 463505095 241071637 28110587 50017875 562911570 962801493 950567292 150916135 625499571 498224112 326768744 15457498 90299375 527569864 146548100 4515628 927703050 709268547 350123034 344482569 571872638 76952924 753327027 535578624 994551081 798645029 527850281 683999856 178349439 29653756 87017785 641854533 123241744 115128371 544388760 538669665 77929863 494956051 689585800 555945785 993180162 16354543 571403283 83479536 396440758 570467734 87995164 324143807 132252632 290634549 668626376 704125269 367587472 274469754 239703892 214654904 73114782 767554173 751171112 103980572 649724280 838188896 598351456 625482375 953317266 142740215 164152040 883763481 490212617 706254191 292225617 335909130 575125085 863628899 271905018 971565843 434096633 212416533 148226001 566349264 503051081 816852376 122990885 870638552 91322129 362694776 937809807 16953262 982765300 688980918 973450185 485005931 379686165 571801641 110488306 185519783 567058207 127156697 69283263 57270824 833410887 214025231 393179953 408535971 77654130 665084970 232618165 364267114 877501502 380844166 930616377 233068934 50212893 53607261 103707485 141535022 268818389 894033644 11004635 104100040 435530913 836971172 589105971 815217078 261289164 699594276 736860 828347370 826750972 922536474 885618193 512678210 136561704 131314498 921214180 66732185 648915819 6348697 430999298 378933673 387192862 214132027 612002606 437405754 120255639 568226443 431457127 389074027 462260086 294978114 493174067 897790998 131949285 82280037 565524427 393238448 634390664 566261286 74102169 313657987 341314111 959720362 826336196 477875815 943551211 600066727 544607999 592467029 606415423 975607297 971400701 993608284 42255675 435919659 283530390 162511313 4146101 714987516 551585340 318922538 9965629 897275758 69229887 141914913 832072146 634754314 387669712 318979161 53531951 461771881 632637147 394846062 274008594 311489694 872721876 70076156 764072772 269846226 662543184 223004547 97969874 486460237 69129182 140225548 922379895 352659571 302736861 779042347 67647087 706838552 97964884 77612715 604114309 167194770 72043980 288702806 801949083 312230043 607681966 855481034 626518275 92835464 102843447 900526868 404325157 975565322 970603023 20914280 97927899 485662559 243918826 48414125 824639147 313048008 188639672 599535393 665707578 343892884 378577739 733354664 50731435 329058974 663483731 507362095 496253743 588044062 796064900 150719178 752790456 403746865 858716563 379308731 496582328 961560009 132351950 753423836 789641682 955471325 774338116 887569580 293650235 18256941 935983704 118289381 331304948 977139728 717824773 997012526 321032611 948918863 582883541 224280398 277977836 98883623 731642492 626747930 539444036 527707392 777467107 292234492 783970608 488700021 524059574 133069288 450260029 656411523 886493123 92418062 464399199 660831238 979987642 758049433 531604531 768487697 876338813 862909478 598143776 446679937 712438355 919176387 248115151 147838248 143456784 526092986 99238222 727615627 5357268 638682258 107839370 782824374 930916749 891809978 124040747 307492674 24879265 574300775 963904196 911372387 666718837 280819747 424719977 499222830 38869179 956324507 120226878 767724344 671750336 718370654 66920632 236705043 490063392 315035783 237059642 486036527 841128768 336297863 66168505 846486035 974980120 174007875 481826761 758413220 65817852 605867507 65905893 90697116 32684633 882326441 854585854 551919821 163146187 131822182 51142650 54531717 940663040 23885880 822256060 464929728 594772885 889176692 701634770 84836276 204212474 938694411 423389154 897857593 127508625 489557658 596859980 102488745 663565532 78686740 860901964 581899735 537070598 779324209 525113202 422271582 661650649 232215408 974191403 677313187 364037589 877850404 731844903 157216981 901736283 554100963 622146708 349025519 295794006 176297829 286378146 500006479 114992239 709767299 250380423 95017215 51841309 847240402 197505959 567923192 778443493 910924275 149822927 168030442 690248483 674936128 590302024 204415483 907151535 564493426 881728669 123705476 294860181 466089923 280922456 49112816 20190885 903069163 398138334 168501242 79366991 684516480 668507720 46875581 246800130 918888143 141892795 298641438 618644896 191915106 866564630 397088389 102839380 868903908 565118830 645604214 396356387 7937205 702536048 156024274 572430630 436781068 279729749 867290811 902870990 413168556 916403626 775578227 168754070 167058311 944079468 100637412 851574790 465103540 29344 98374920 236508034 141922138 249532709 855152929 186353595 116097338 104757669 141709326 837517597 669876499 639829891 233873984 677813703 342365938 389898257 102760685 779147005 522144357 822567847 534534347 935312912 591487824 310112573 104066981 758546134 106708392 204704392 610120924 571811931 204733735 561012195 808319964 199172224 810544903 663472893 238042171 779158593 768230561 379751496 616676189 290623411 19581387 703066524 820953466 214463676 92964780 923714150 846127033 467625488 598798348 380661379 402938399 190286171 543290303 359521731 948832304 649998694 564226122 411469579 221810625 621476208 972481773 30130588 820648432 635543028 546119832 58690602 414701620 166866745 290958449 883894160 310006507 163056187 586960684 130959972 230036215 532441815 907190473 76163247 67303 505988820 309340977 255522053 548791342 852631279 615043784 350139998 502629972 31786257 761609576 576956948 653262465 586607701 459603888 326427248 74667080 5723719 237634201 489368699 25106815 381109001 225779210 335113322 544165188 812739893 318589645 774201402 197698060 225780118 702881000 50281714 584285289 12221976 158320118 133076631 864853254 773363901 483216628 219999577 657666510 97342555 796956525 163445326 536466607 109076764 489872573 611133686 114800482 580023125 100502384 992423649 961132125 178797946 180053322 357813664 991537838 498642966 132015065 41752249 724423083 687412416 92033962 161224724 699634391 102870432 294301354 417003996 876234332 630034333 489519925 386417193 727376887 138992801 549862518 116359846 248069564 39735090 727493531 215386397 472274566 680512267 207810045 433406691 859310212 387863366 791220354 703364401 886506332 775751771 745116650 463445766 315680538 689666963 624670489 15314929 792537394 771488194 284835276 521288078 401522526 774355200 907705270 981415765 913348000 310084140 97775610 13933915 202335581 825269140 229320312 674610147 358297758 437130356 108016837 217607969 677510074 751753542 920972370 416532757 380021664 518605371 879978522 695702202 60788685 357165363 563533482 705842431 128653556 700885109 79646860 382692434 327756661 987352129 216624550 93621012 149952620 314400159 107554927 352288201 992185650 336875238 26898347 350483408 774005593 987431535 420607728 304032018 591701428 194096449 720564774 971723092 712701819 453059648 519941645 626006856 810225010 935991478 331849286 791394917 636876586 411496145 26603702 964633246 251364625 243228251 58254258 401317245 410144761 18325536 753605445 402330411 355200773 633020143 605330170 129206365 620451677 25937897 285754735 64669456 220034346 6319508 36392547 785252516 459379155 408850543 411259371 122120516 197358372 595625008 766031785 834234958 7121152 792635486 651384555 111002129 888380089 562155164 364835725 298524849 580480699 118441169 553371611 935681471 603977663 158701780 917404188 76945691 37156029 55675274 141615146 257190374 61994781 30524045 42442889 373890288 439374587 306218612 496010803 636732959 901843619 114558939 323484268 761481123 907194425 827385174 724999603 648090865 242056690 89835327 946615713 822537388 60792847 352503676 610735211 664770509 511205455 380655750 741716199 548361483 436331023 883331344 658068208 350842155 913855388 553027449 724732442 205746327 859246060 73259597 694995637 613606030 187818535 18479904 227603504 95012959 698381429 952603106 595620175 940438118 894954784 394752240 615491858 955747630 747255915 78743420 473034490 110977721 459399169 67267040 659339204 748246543 803114736 169923763 99088697 569486475 722951211 823821139 775232801 434713622 897080735 322744789 48319652 84899269 193741044 128439507 32428580 892122473 933558965 480565106 832560590 828513748 875317345 300568799 636777730 622573259 379312218 962328571 733550980 838711386 29595611 245406535 439474280 685226698 415330297 538562977 254713172 138281508 214900467 882462325 425511481 964497553 205207113 326347484 901913173 398948157 454786991 786858104 143586981 240862307 267423210 976147570 69376054 142740554 129232721 558670135 617830165 508544938 373515058 203897496 199772676 255627020 301820382 639246955 940853717 717150678 30326283 48083240 707948537 245226749 930545564 133460018 62240653 135752677 312323853 964153826 387217185 767110843 751011929 530804165 7973149 870951490 359468086 929865555 866208396 488700806 341052041 336554912 997245744 714567098 540452407 49534771 970194117 842272788 688781725 763564185 411939817 719108008 811647425 972404706 964334756 742192988 958381075 26575409 730462016 270704927 843245586 970195552 890332122 446773866 353516068 750821622 317725356 712984154 533203528 36450103 54201311 874255569 373005014 903963406 441339018 913457420 953498176 264049487 608246559 642279901 27613671 872702727 213904260 691777447 845107432 30755367 286486787 656004858 57330775 16948802 926709785 753092712 839660706 669558258 199866578 193176773 420379879 370108285 758677278 953583407 406558387 812878589 680355327 779563400 569358346 974210696 545537171 522856522 90776534 6300081 17652774 118390205 879002807 231557033 662684003 576626591 262312399 949170789 232631448 172159526 818635943 11857584 925252237 658296648 681415841 977635166 703989772 954312072 347743450 462667050 760411830 754301836 128061990 293283508 386381587 697420335 267494203 931918757 72793208 358270737 938218837 90445981 329177293 817221644 174519365 991861295 246364586 289348116 793548436 478996033 461507641 612184378 343369969 239276229 122997377 24785809 69427747 826987148 831614232 417171196 142170549 592026061 23989384 122748890 885309568 410370970 820169225 5320123 194806079 745478784 216107211 133024915 688441117 545284503 802762910 862960481 389662149 49127495 4824948 35726936 380639880 466332588 647911313 724009848 558125169 623425041 601312008 627552915 302928541 432926240 44724110 445099089 877468652 921229845 567847979 615294572 184117167 240533555 620614694 378923245 986012338 836721904 511948159 526969806 234522758 167227421 242446639 476701258 216354915 247271586 512428194 596994794 713604174 12855858 173520993 124245694 636280899 774833001 751798608 939209439 60275592 649039069 236824879 937744243 570268914 804672857 553038814 754386080 897722763 26169859 133309324 736251453 715408114 497773834 263221258 949930871 665001254 505667896 279148481 733872521 752939482 791576674 183383666 319060007 804432531 356904659 443305700 440713429 131737659 47620659 232439219 192013250 696659727 469264098 129757492 119444992 126453306 535312658 873831071 24176069 413998868 859656746 760427521 129406982 209946932 876165130 931854204 727464537 234349378 211002684 461337057 987288859 2579357 644720723 158865217 659528240 1625381 454687268 100241668 985879391 502307926 185197239 30408992 198967652 654461336 12682835 318412644 780914641 547995492 44760066 805090709 961994360 756933164 418034581 943917693 966880095 146716063 875771896 546860983 381065440 939290932 8198040 220870650 794386640 505435114 379735866 453914879 359576846 834423133 406672899 197972588 189247410 591870137 228381579 388215061 98847824 241064413 559144056 879762464 789059905 603904122 537369525 603570616 213353637 955404105 400004660 32750083 102120167 128292907 579611065 335701958 67583838 440325456 556572607 861970478 945760569 936308472 168401708 157853766 623247956 427590958 355826353 812495365 19461094 584207931 53226778 118308917 825272344 612370833 850587733 466848600 68791306 387957257 922935567 282144942 195877713 322940226 314895024 150514232 451233132 894506089 486216189 371333322 187347896 42788796 85820151 133108465 831613619 254221858 143478582 307377927 681812816 351821287 972389643 553790261 936029217 25616420 524615530 613817912 490503605 227719614 933182863 411811262 615676870 856118429 693956204 664070934 31575006 861367579 814585165 335324490 608390019 153317706 706657811 795737915 48622853 792477961 781362731 732752823 46699818 924841312 40130749 581028985 129178950 865036744 987335598 65208167 743169515 364467479 531542430 86189471 592187092 317241645 498000733 60380313 25876425 44473288 724451246 57451431 905840866 391552763 392775920 514230885 544870468 99433730 162485151 446009672 744428042 943847881 178762494 643644211 721205544 71409595 77189548 850384494 936446338 64525145 768109012 532132204 428992623 152167793 618321675 21179714 469409437 116322407 81560026 495285862 160795694 658527623 552737292 66636559 50080385 798029563 433383795 447467204 749979644 595868945 893476875 494407685 392233177 72239369 138051895 113438721 996165315 67757794 963823214 785128004 132282938 584448577 317260207 413791912 736616369 935581881 287487977 206025806 904420639 221564354 701311667 65216332 880091977 106565310 984369243 930172361 904594872 270269389 230155917 507090867 718654686 123632791 1498551 110887862 48388511 992066797 76842934 44553825 59824591 40666147 682198180 44623880 477631075 999458387 458415792 214247444 787556619 745903768 272789601 544493610 967468122 974101267 462226293 700076450 933182928 299111887 482765162 690294151 569381276 712921078 197385017 140552313 836553869 51399919 251440174 737458731 895983067 328283108 634528908 808324009 221465606 316727087 852947889 699096681 168701825 163880032 765860476 808774796 762300151 38650076 353268405 582284624 865267694 815494697 282361073 798450621 114606584 765126235 341261123 536504211 330563664 538646139 677056523 19633884 442562409 781013048 757092615 338545475 109296155 391621522 146869484 183278113 560864960 852333724 734891145 729566785 868730107 500751620 390857932 631030257 391918047 744126336 65831233 257185740 412137384 348192305 908152712 379260319 965834891 249413834 768280881 296398555 640576324 297853755 316032438 83138732 78866803 73125052 274200558 40679309 317262925 273586393 76473773 878127885 125920116 811364917 460211021 847166574 164632888 851068952 330713183 556550934 447711639 396544415 813736673 712365374 744736719 574405736 91625693 563087962 823819569 712422925 859486516 316912244 10276680 28035305 400050975 89143482 953676709 674251533 982339142 123455985 947837925 58812915 1583869 926274393 870177831 314311241 625957318 34810719 17896544 956670500 443878004 318124534 353214914 110131029 30489908 950467985 684536764 974631952 513555946 360872685 687054876 225558813 677784928 549847907 106110469 77835903 491507740 59787177 604603787 473846882 183243162 404958063 385176148 37343382 183748807 107870330 204170975 809706125 142681048 222067518 618892976 439075404 540192052 972107890 549206432 423198311 775092226 233743195 397830262 141164523 594615879 937401489 366723335 124917159 487249396 472833803 55269413 978757135 385137332 659873199 305120368 568380493 917347613 690296515 458240226 101096420 798166845 662411200 763318896 793364244 884478718 234728223 84955999 277187121 59352464 634162430 700385431 834444689 867905625 950732044 975609211 315037855 888133532 194848897 439955013 227899279 667682700 495224425 59172766 52820031 7613975 216809485 473716875 924961588 907106000 931957100 878574359 557789196 446884652 494409606 203669791 183879721 729137828 288625790 461066841 788490292 922788219 13968623 475451332 643210195 964700666 451060543 810764402 705350549 645909439 103235766 785766180 166108490 598460191 844938945 71444872 458590517 61748429 397678098 236068456 821370780 182151550 114642814 231676327 629036201 461568771 287862470 812915921 43222951 576488259 126499113 684229594 351792829 140467735 159680925 847519376 957684752 463257819 658283777 515551652 109167258 761519542 301317831 127792099 212496084 998773127 51753323 671086601 913037908 449431420 907155056 586925039 631582969 874314222 818601366 260619169 188399344 106463835 73535089 84138646 535468445 52550553 768368239 739777625 193018287 928049164 587297000 3219390 243823334 98097128 518771042 205506943 712133022 820088872 333299042 924629105 671378351 385052364 448232057 584416258 834483783 207903465 23857648 318583104 934734038 842459013 579202272 123133381 801439199 505253713 59788379 189423995 557804265 828156617 929201620 603338904 608722132 369014971 606558293 852545466 319628451 125329334 58052408 31761472 797934558 243867801 808906928 469312908 628920164 109655337 906245517 315920299 317558801 930103164 634503402 104809190 625078529 66222025 80458922 279034079 423992089 140247300 468458074 981796354 968403917 250176045 437651609 577126048 471707367 44209901 282187865 791335817 22055587 340240273 823097288 819990144 584108073 484520568 141819403 65544589 594175904 48064919 233981239 911734704 978168082 868484640 16543893 455762962 787223016 97002814 734797041 211215105 89766466 55771466 45527810 58170382 305947510 483179418 487812781 777654876 379905670 770000646 421507045 401961256 110240918 97120684 221951399 546865342 581641251 363770801 464926282 175817154 264352071 698907520 940068209 95036505 419908511 809128453 550799466 207131527 758647619 285596506 270862983 848414084 341367971 316390792 906584465 499831832 652086561 246913597 130003060 31992230 16914242 551510104 433953486 979671511 648630787 508421236 379053205 230272038 872192037 843979486 258605543 136544107 542887006 198673752 84096963 962795516 7802204 634896429 22443394 618966174 920492934 293306376 467380257 114377257 462213519 226481073 614209088 114300079 473394670 744212147 146292309 342825263 148238602 432762146 322496774 796869389 941183381 701549978 27141426 665891769 398045815 138263320 654952228 940932820 336937071 739049190 756244688 197255627 226461970 631204433 816221800 146954904 924510809 136118409 113848512 239240679 215115833 580573951 353540758 688510502 177302450 352349418 31335765 325541051 637627915 206348890 122410439 431327647 760415219 2068216 97219416 158461033 140331536 604687995 951910205 329784958 196253536 560671244 527040584 422715506 191875676 195778736 422186761 968902836 184413496 388551624 208143515 399529328 969125574 414200624 88039830 146428023 766550041 971891946 471969074 256694307 30757187 446895864 688021953 791172405 448964080 637757720 802149789 441811967 94962066 754059993 771596924 291215602 167247588 151153860 566447459 359123264 346932595 988634219 180542451 531346090 229702194 388685965 930875417 198827767 802886588 871431598 197772142 421952980 695839895 669741215 678647286 579113433 116637078 219185591 222802189 418117509 856943310 24951978 859929475 951905376 631528322 484042751 95637329 798775910 635196610 662084787 10415525 982129204 503235357 190957975 365991645 732937550 579643940 149383413 931765316 235046879 873331363 129537457 509516211 421687609 651795023 40679848 801042 620948453 259865438 223603230 891582313 116808748 101071559 604028140 68714123 732599881 88070890 16867803 531375790 723267499 678952589 541791314 557913054 182187945 732749288 776421050 915125494 164909579 925804462 699407161 252472810 651652176 681460970 761989020 73339785 185772344 802668867 74140826 659237148 62534305 150260407 550819461 31859404 251331966 7363952 100573526 983931846 95434841 117441328 367823987 671218691 648910268 762131652 81648096 831098212 347397291 858069145 598740057 512306870 636389958 150663569 764779679 288042134 684640890 379285050 213898270 870413234 181953916 140555447 382166733 97004572 290815853 932986193 128863975 394664170 940350144 81953852 231112367 888301336 51911531 598936353 559520026 700821798 213584356 641168121 384436361 560981647 351753617 983176417 73288516 988143575 986356338 690584546 128702060 670997227 69869595 342600329 393926812 104339862 483155775 776093545 201344434 773971627 561596089 330208408 21152149 354462585 412162260 252264515 95280272 464073790 851200868 654800298 17411940 64785223 148484770 401848300 478283221 500238387 237541069 404088088 340898313 223897406 94672633 469600372 747410984 17058579 812200700 141337796 973914793 295356474 769947692 27775578 921844452 184060132 357983985 942996600 391039068 622662596 195261115 486319340 86736386 898978334 141119637 104148325 816279908 142120758 358512976 294563129 494875496 596054044 698651216 835773808 819951449 645840201 305374179 419878785 515415131 117574878 413732932 341846275 265447703 36196975 369621852 39808507 220257106 727605837 982805106 611296174 202784784 30582572 97615513 142037521 929560905 91251501 98702197 745840813 85888610 457215173 892920293 580764106 53269216 444087860 269054265 725737017 89928060 574428444 145615801 457859543 544519673 559348732 799705817 662483728 595545706 21844021 702292234 668319163 749449857 685097339 132131688 952234640 715679911 82263552 94272161 497757167 26031404 45490709 96114331 111920014 502705881 989034623 545200471 555975097 433122483 814254735 134228465 375566894 241199530 279844265 685942788 785719203 691709348 338164957 300719282 139771405 360008977 3011515 808090567 109458833 540625205 940222255 914209824 108821467 22485806 860998336 606578634 48517210 906489045 702692964 12953575 261711277 691727587 558154045 817686373 977366421 372408779 951914837 205449666 613608309 84275453 891392454 251843863 775984800 229557410 552563144 915756204 589566386 408091010 576363123 551541570 948716214 516585377 318267745 57537681 391587534 31782433 664116314 440104743 790787829 219325629 453058317 52499105 911053215 11212361 722701830 740935987 236137492 527133018 946385653 702262152 611408471 837778106 954106014 239909622 919851867 359185509 8182178 361934604 767276518 584545300 913476173 568509083 953647028 84260269 626046763 345234561 116042701 142679428 637855656 759346881 362005057 90913972 811845986 125574623 954642685 387064167 866510610 43296528 914197184 665412614 745558679 378122006 355707071 552181044 618031628 275558937 763882904 478730157 637493540 383675773 63275456 403486064 952184855 869438835 340262684 430747970 67189747 308821737 573427397 705045402 68168617 787948805 648475726 732530954 913523428 455634762 119595120 632550389 498931289 33792304 150479354 97006319 264430661 506186424 501703714 882462288 781745360 265586617 213708796 271755251 649262389 129500603 527757666 453963595 998939437 868020349 884711564 66129184 176842085 310655313 771174585 97527054 98604117 272166662 830058007 864643896 727801423 949653127 349710636 79249063 835961782 500189989 176255381 100392442 6376412 677959094 835371082 640638123 796062062 49079877 912393373 297840802 31096832 292667390 751804397 30036268 160687739 636515960 96165451 190046175 947171272 719856388 287573228 898291741 992023049 117631235 762935636 572340824 919800713 112646272 651589886 608278846 465352612 827845267 561187639 471729024 358320712 249075072 112367146 6899126 150671301 877276871 304739927 181768132 22460612 56544323 211804399 183148350 545576635 160486202 373194525 345264258 732858941 660767752 243555998 577398341 630915338 859007986 149739164 550716050 824170609 801329050 11511247 289523220 481690668 572698886 613768595 692527731 821773957 578652093 699426856 972445257 308445315 4166783 154213388 330905926 60711105 218534139 514054276 458804091 379020340 739765152 804068349 111879280 253049255 47624346 541793972 883964593 759148683 691533136 287196994 583319291 345378537 298708241 725358863 679585556 871407126 339127457 372113286 693181082 917779549 71540142 518142691 78741215 928223276 672356078 409647141 841450732 890890216 923701416 300254823 122426907 515982919 104323171 86822538 769032173 4463868 628616510 652996765 616128903 172665997 940193759 51964545 370560885 91418351 777323407 50146440 962825476 116450864 274776077 508522909 886746764 198832570 26665599 965487979 127055845 551538029 227651471 968506577 294944596 3869238 121277751 417371503 519852156 78117273 356710392 288884328 935097492 985326901 794397445 551226394 10509249 587107555 603190939 381070133 678525905 233030697 283732924 641351380 201997912 558509001 2390640 88744676 757341570 29056239 906749006 884397415 580594267 134400476 705420343 875538862 138269713 679214445 145426716 510638220 757331717 502137108 799522547 544945560 339980360 446436343 96171954 203005961 33543897 551879244 584076093 712069801 784909940 867809017 205937532 986907852 278834369 208328172 928168879 36175938 89900762 687434236 773089704 670495028 674351063 331026398 398550241 665137127 10240842 396493309 28291698 620088910 898630416 827814244 165034470 91127127 126766939 113722775 294133087 160310835 518118370 730725532 724896988 155544661 451050900 930834519 142452512 729885268 991679042 923137742 766061205 81579803 463088329 391667261 604591182 989955743 722693658 3141423 507609221 732934500 252151083 535900918 205539761 3297850 216231514 370574230 94424976 342998452 336813356 241074415 503309286 854931725 971799946 80722625 10476386 422850845 11557144 5445249 5252464 855752537 781099343 771313668 937332340 96704023 15497280 394439873 86659766 738190938 250097647 594268986 323641789 502248729 130169904 529181549 505546578 198917769 899755779 599971554 541916220 89085486 841045968 45225505 944017211 665362265 125948130 954493596 88213109 990021625 812455196 93465572 698290513 593554538 717295591 488139204 690258561 732792871 882579077 629434678 323500160 132676723 76220015 647141948 634925452 58906270 176323496 140472029 257824038 928595626 592959934 799740257 17681112 286522253 697482114 961698322 951884517 675946595 768708269 892613977 518484571 433679816 838595900 216775083 27234354 408407843 704914287 570009266 993717065 440009715 51960295 317217224 572686437 128180309 964359171 60128240 187086579 993199018 53116621 444910616 921794644 498592906 244650873 791992107 785115159 942132986 606206780 589516027 470595932 227431400 334646356 989080502 661111215 25758607 58371936 540861920 286682801 763286222 110871185 280399865 55812288 15347831 450133440 628498725 143528140 267008962 541143316 330614718 260207980 594259936 775525333 34518975 92852842 20176205 826511081 730484352 814825542 285234212 172516730 137937825 512665611 359679437 127018326 173776825 385438044 185390262 714638745 672120844 801192835 678026281 805037061 857005123 693374112 255170500 338020199 836902251 522179462 879163514 20033320 634903793 325939802 795558652 669422767 271308995 668251209 348450199 1793346 335593102 633684410 26826427 473530927 146350020 386505864 600549252 172643196 624460259 638455865 739798292 149097454 439648700 270340925 954134514 149170174 963715036 61821366 487190372 653133638 584000827 366353885 673166957 71420971 692293686 321241960 740843737 963602680 989493168 941810287 817912377 325086270 428011048 697255156 798617196 426877419 83761019 251682799 599520614 560737629 890138664 191835258 709835082 182303715 462176182 663969596 331473888 278407569 725790961 818664259 931541206 162308139 37534495 457224514 233729109 582344533 778466473 827089197 398463564 620475993 768899483 68892293 945562262 49426882 766147448 596695809 476304300 702424818 700894959 75824913 263162446 443549974 120176522 972997527 625853688 582352703 489483474 809843927 860760271 67790786 481024537 644817828 82615276 518559032 102042341 316344384 100903564 733025166 143433580 351883479 206017510 764849414 420775771 4096123 814276295 186923218 600791931 143096946 889348035 154203241 71438211 5026832 597753215 191614732 830540711 76123254 773967435 172540536 885967181 634727705 240331322 366991717 132061885 322946597 738067100 86620577 491807333 691487015 819645742 487757264 43370494 25663251 105123030 464146264 29759373 919399324 503585834 483067655 62496270 245450220 637270896 133934480 250477052 87540462 178065563 81017762 163663715 952032997 106074649 49630895 439277054 346405970 269138964 571338938 521868919 7206063 657959514 13676251 698693078 330121608 501433514 594579923 208301210 606556543 58726186 90576935 378472219 414828371 573644589 293484840 660278591 63431836 279935671 910755642 150972297 458001233 844289755 314636012 262550582 950364403 216783258 701827635 149286725 485922221 273166572 671155643 493128284 931126085 537348245 44337713 113764044 38781758 638917635 322065254 497854653 550160172 412642188 728843223 964988543 986286776 22328062 477783485 902234964 154780084 241055478 53207260 465297668 85345232 220359623 727848249 888225986 437142881 429675883 890029062 923065101 555358806 413701056 268709736 339001243 951049300 165563800 452765286 842347410 804481434 774830539 192718414 207157958 187472726 921561636 24662852 26275854 796406049 502446336 928510817 951186132 743501813 834234428 269000151 681363396 907110403 996848400 422105733 196769635 279040634 164651147 119834735 834399440 578352202 241060823 173400682 529401502 406624622 626165967 224265263 63622408 253512858 416983676 123296717 440985583 338545311 147959568 319777788 134951359 502922255 100804956 938653842 98940419 935039384 60170344 780303814 694666138 57018743 54925898 891435772 336059377 219577044 863786858 22975168 797929246 104847680 196375849 179847099 363988654 675058167 404112361 280127413 928571024 821096036 403424129 222072959 12157698 551383696 541850746 999625408 54305950 642655702 790795601 5762720 430211437 850965944 786066533 124877574 907984687 693508782 16313345 96560415 913085826 732616554 119535582 563531423 689980586 168427782 595894873 53969239 843485948 7233 186613003 772056972 673619620 590037131 994129930 538293669 141420826 388497027 537919076 48243127 31152728 181231028 54005846 461364164 32196971 692588730 438758089 792698009 238613863 307587785 889258423 4216040 40204339 861310356 567747462 730184924 29738137 16158686 636670514 873224085 16165918 823283516 497797408 542301889 265836998 344443689 80595557 259774175 732940715 471030984 160533653 616609795 652262011 67055850 77973958 536975334 759644579 369248399 329673342 998258441 676836183 71448117 2474481 717040521 932758472 422738294 299741796 815012961 438896980 788928661 540753397 307579249 464728528 38550804 702397490 730565525 235510844 635509398 990339699 820967910 106540382 150873351 437577704 611318744 217929200 368068014 810429 830090130 737316412 330483771 680864923 266668946 254448239 535855755 983709467 39723062 958594048 135967614 854736022 250007379 924896275 395489418 410102980 242141154 286556573 112500469 972706679 374583768 748009866 963046377 195551678 707066599 966436080 485645733 170901695 36881631 853713746 171712123 866971761 443546509 354712245 547836683 710215455 609160483 83692437 546441273 648883545 894802836 534925238 503619566 997326567 312337864 751625336 407429546 554479018 38181908 372446366 527185696 265282028 120456231 342748424 460833705 680039182 161700855 946479437 703457228 198582486 652709535 875169350 65554246 948772395 82397947 465907280 511504201 691558429 402116068 57945473 340441973 149435255 445387063 696577891 146761821 757724926 448203226 406707718 312203943 338901485 779154083 691905990 604183512 752126666 34654414 917533568 284682199 48871620 716529357 988139426 247454105 221755243 715825127 313008350 170527637 798223073 778915629 682031838 489781502 33548048 592493662 682739826 182983303 37880724 379317716 329745123 648122002 680037293 736452841 960325944 18938778 368123275 504748286 475638641 120249940 391919051 245688561 404932138 440790670 962217917 245587915 688244775 183973159 961413042 1253124 207017147 759636114 632685105 889048984 101933967 666233152 334058998 784673793 849216454 224456073 16507860 31477929 872578074 696545153 620447121 685420370 568000282 988570395 42685007 896155274 108820335 434604057 141843834 366268824 875394726 104061750 611856739 563639500 140551260 425786132 417408976 347568407 37938597 902610432 89133742 139872564 421359935 275709091 777062708 123092741 500165164 793570567 154570669 225259589 342632071 775017789 763196310 763148704 616104535 805881316 659303978 577441221 240485372 653664163 943710045 115880098 610242265 408083135 532035949 750793524 833869266 801961276 950878282 871807862 704571707 40012024 864196777 125931642 168237466 641259484 101540734 668402629 287346403 256111402 746178570 482494825 883645542 509374879 245643529 499750076 167772547 757463858 77191297 408257918 411128020 873417693 376654367 21370284 134017179 761206668 624680160 820402796 563167943 428074793 544727009 120256002 320603168 408923786 98703995 488840634 902699621 200244728 9759614 42562375 308872481 755938183 525057200 192518022 117829414 770700728 544784449 285601960 380680937 474492097 693859877 791808956 200426141 923030596 665695592 334443319 684237263 142892103 7362466 99921557 570966895 552089475 72693910 891570063 961013260 171397904 232927048 716229232 224158983 242686661 758791607 533031463 998624844 283848806 725549484 116454257 907065885 122850285 402056216 287746821 597342381 948432444 932072128 797768522 871463039 450284071 132211840 408216653 593176173 139574306 360654562 16659420 544180132 433348471 760745834 357709743 604746375 993672881 73938974 828905357 236359541 832730580 214453172 87500736 969095737 940002655 203954992 876161621 62852939 458527559 16424793 512711672 406960003 948496921 310480193 130939393 251297343 295208384 391672398 844473516 287299041 752326959 713649287 831479172 185675429 474395120 41705266 642938155 320584352 115644240 324359864 556943892 800891171 538813035 644444628 769986908 331332041 700915971 498664880 246701332 159443530 367606025 759413003 418919884 168619297 69893195 549859276 419916639 217617930 941531673 116906506 357433323 546374983 830555792 41428846 732050412 157467263 83134112 227504918 478051614 198778351 551864781 34995506 999669521 90677815 531956485 622172780 422009856 85388807 973354012 668711187 244832336 340960036 280640541 663752219 509579332 203050087 66127847 929495970 420668016 860175871 46402476 778101338 406550854 729474619 819530184 991117617 886941882 902664295 218622534 364993495 953958997 770487315 252505352 806144869 713681481 636978188 280834001 135691336 722366995 254188012 656918874 967199330 447664399 937559414 483467901 957243730 140609500 402112099 739256051 413793868 262287969 638174878 44411557 521355174 220165849 716458092 512472790 107107730 471638738 583611676 324617576 425597734 206615342 577122928 84258955 920296822 66617467 365092955 908504510 788984461 619280966 417939735 608700143 66945364 208015501 92168043 876705445 201141352 346796493 468477847 614935219 609084461 959169077 511863128 130439635 179334925 228321219 495428776 138959006 699959957 79040451 463576581 978074042 138172144 40699508 62332996 58468966 107316975 427425950 966973475 748817787 899223267 237429561 357517929 818684982 445445061 302202323 547906778 646586413 648998815 16384625 114037983 110599628 828070053 625901110 93555614 7404977 854222329 441500741 146363982 406698637 373057544 462456914 237289030 511229687 355672774 299622026 569698652 315506100 579564327 389188478 64323886 478787594 626618039 274358167 149988927 72063099 576560489 697895705 571165863 78075656 566796681 685203846 41191635 394866733 311104955 134747248 254788061 17843635 576247988 253668394 277058623 949305531 716125307 514347653 313051570 71798080 813969678 882750221 239820531 246050356 124455051 304144417 724837949 603589441 578502583 874826876 528168891 7579423 425238932 99334754 85655078 992035612 784538599 126846712 239418696 948159905 114110311 494206756 966003540 542874651 600391501 95578514 344696533 169033159 609926166 657748102 93347591 276412195 393014675 333168121 522462551 517469725 637312537 99816851 121059165 68331471 974643726 501744407 75910894 252399009 601079160 14082323 244434620 238134110 993445387 483853315 38810367 960072049 830576422 4813906 502946699 430967922 100392419 847643232 600001081 562834937 357907685 693348671 839247131 750922359 26516791 361709681 120908435 516345680 461526532 94483951 437193502 288686609 596228358 365620747 541085618 49823869 232219422 638036589 287957979 78181160 121889904 326768345 38253208 804982677 184098602 393716259 88466951 137007372 93875842 688468031 699842308 451783526 234333053 391605791 202705885 113366195 753315471 323614319 482228226 67358354 418098270 919421728 208561315 14326627 285042474 749646932 64150495 517261895 240199872 204624825 595443054 214606127 383909521 486212614 19588804 568008122 879928872 108055754 557531846 973804713 649040136 109890505 425588238 883373188 501496295 480810474 849255734 107328118 804424793 331483960 174686471 75039414 103422039 383247785 941882392 388464512 985411068 858549238 758242759 225610940 63174063 206202164 440217066 299599935 692414777 312322221 867608057 572343648 420377974 277656254 398664712 69418109 387546758 824252950 805307648 889043053 157579775 507079734 996371170 962004567 838563693 23573992 889560332 941985731 406821777 831442723 182966594 244749196 542508313 941209352 470360135 458198727 147411516 763093553 757798661 692342644 75415773 477923069 117202644 348310099 755579322 515867355 270244559 143126080 192636656 75552207 32169132 350216431 435148292 881056653 164737349 126228336 904630644 54297681 68214066 163968772 738256755 103697011 408717968 280765067 897422715 879078102 738963793 897350582 494688006 349278806 589693225 570103779 827201874 706895868 918413877 582781196 75279575 41174787 578423627 267916230 116726993 463109110 618132660 404391636 344165762 782870009 530619971 101312757 837167689 451350388 265281529 427940795 555047399 673999496 708705862 304986465 405593949 300186006 202337046 900281955 649464811 644546622 322902085 329183037 203958842 93832313 911964232 279238416 135007099 342904210 547154645 104250444 806013319 165287305 508642079 2695432 948157313 39262050 104008188 637841353 490612437 369289716 65782147 898176187 43289211 627004360 203162651 448883160 779706718 258016048 201681466 281687880 902562670 524583550 610870916 106521511 618415862 375351499 385759926 753422960 718255708 932914570 857673403 524269026 950718226 366315482 526964457 751391890 258093883 630972645 241749594 748706319 262360 160048093 499398858 896067923 787052452 702561508 197467434 419275521 960577556 399148899 700963401 715656577 923732448 311834316 822178087 542148309 687185815 60454364 148087620 257957874 845885285 5761023 782226900 796603511 224592856 161707708 400511752 482686738 645196704 642261346 83909408 497975416 802309438 583308265 394043338 441878241 138386125 591510771 861153762 98963680 990659669 562117162 667136608 766908468 726467829 341831046 161573128 266169995 402285409 309660747 524127869 100687045 315421769 158871120 897290555 540014624 320578827 150318659 22701361 965775531 792580004 106610769 316267298 594889441 542435385 710310635 36767681 680821509 154337757 750437794 632301540 997513777 165071307 299438147 764422244 891539136 641269192 925995371 157709130 896070952 88172469 681836998 996757997 403594238 840708117 746564903 796125213 13803296 896883561 671342926 832095178 689463564 630470046 148362475 136869356 172905430 711189461 26153389 853726939 865527217 776591182 338544830 715557345 941662489 637982977 332495940 685717976 131768520 111007662 843427105 27839472 199180130 377780455 877113820 602774367 71004923 623678722 251415932 84808218 373078635 922758857 769419747 62542198 553228902 917782221 51927906 578650683 481488033 78081294 284893973 199531601 707188827 623438803 915088945 501367667 113938131 247584884 39601994 245706650 358592545 883029099 126062473 557772675 113325905 3176292 13063393 36847179 479371366 264479324 121655397 852450000 39754532 743591495 767508549 592983433 513890068 671952806 24150468 995378100 602550451 309044440 194909701 162255630 932483242 109998645 663623296 46421372 210099881 703225290 144644374 421208777 438770740 270706846 978981451 404612996 126399490 844561196 441460174 458287207 109040519 415631922 163253558 1311403 159223417 930762106 594294835 673113484 455231264 618445302 521007935 57781714 927489742 715917635 220037343 712489335 678432632 736176991 758910707 741048864 291918632 903555080 162257640 730689371 26778277 993755443 135302366 5694118 838316638 429278891 463981324 799873508 844910813 627234881 801184910 4134229 410513339 247996097 529764064 865744602 718957750 50771998 923526315 498963843 619205985 996080010 211453178 150154968 732257000 822880236 891203831 24175631 578951667 905977822 607381353 605729943 899733264 595200070 611424061 590566253 24478960 75405384 242956113 721906124 555156617 896657374 578556704 965669955 144653470 108320767 831414556 716127572 11609117 607457222 215091414 483331453 456053583 279060943 486002772 40826934 101941178 229722954 65002564 680892844 135700775 524900268 139139139 887950391 972616689 603079551 331032995 849612001 531001286 573989107 571518124 86157902 323162833 2591180 51827856 320332654 110911946 735758763 36460225 975037414 195732337 104067991 310885218 651785919 383128933 796887989 692612853 485070111 26610942 610131768 18479306 14828069 987548388 10134796 902778459 960165076 613214346 86327805 662293428 144215632 660316912 86327904 82889885 983479744 88919083 134717741 156328749 52347380 722992855 192788974 27384794 771241543 296856964 190786363 275543814 679985896 840190704 968156666 17572358 719317997 430804785 36051664 734146065 270869524 46186459 489440875 83550952 511917157 575768680 745844379 656132788 88601943 832172282 739022672 924598038 921091364 726256764 80926786 973438744 301765971 126232111 853339889 73007513 423089074 44126251 201067678 955591322 736833306 21740695 973163679 456151303 452545480 861731694 42813719 723415003 760434505 384770946 806965954 124868013 960539625 405326685 781000800 901657919 237498966 372539823 826255956 11106682 951312939 759699093 984545425 105595261 885931204 837885313 31119125 161536629 734527915 232186803 117127950 323877573 253927497 942807981 780028875 706472976 657056026 675358945 282404331 270006882 60129890 941886636 394874894 873185866 347213320 28392045 774843784 437228638 400931868 453616091 448335319 204761158 65831536 432880743 310356418 951762739 123282407 341475542 113299367 710326673 573662344 82943669 34204245 827589841 25751649 666749471 386579168 682807674 342108416 668983498 952814556 254754657 463386486 200205801 127940523 810599805 228597846 755300658 100344794 629529713 61433101 548680112 834290870 127264636 981560854 144647287 79027374 957359612 338639180 44843092 667686285 912301524 127786760 554406881 739891364 153538408 221156352 126470531 688862434 415781119 647970381 494193341 670535775 111356866 694399141 798476297 774473022 922996986 406293307 874817816 405043050 467726407 276014279 91850271 594991042 110091485 89013909 674018415 67451096 427653089 718861506 587653732 339954612 846648266 142060613 932362327 852703025 215733316 911349209 541565458 631514434 411835941 35758798 302050208 375709158 582674291 953042857 2698532 505671276 359336163 877516347 910714326 827062569 6046977 2564596 274569962 116138461 91578505 948588376 183589557 371747945 519966233 771243288 711702556 219130850 765820252 496581234 71833875 981553567 407930442 465915684 613068000 819766383 354190834 767634560 47991892 936865124 720677416 50690423 295052751 932529930 928206769 58283428 612108850 934253746 913364376 886678811 50392206 857459232 687783538 86498114 229207176 60266122 710257754 793426083 279396972 476078005 290007316 203747198 310147924 550454109 522179233 923215923 222736843 876370066 543366834 270728735 665751541 116560601 321419157 813320644 49090530 102142278 871604071 661199379 36396023 637484798 400394541 939304580 494944029 88178078 878319046 576667556 148444200 588576799 370093638 280357523 917171155 512617305 484104720 227319078 63071414 6283952 3051353 285808256 735170370 546418186 556536990 253438262 662978787 877956147 66758905 564585668 980098424 790879328 78301399 869010798 280880477 478695939 660831729 775824506 566874017 391667126 205008413 567834568 980243924 575102051 848192090 749931431 87719355 184813161 977250508 3307120 43613464 832818212 141631728 778783833 231752750 698168717 884738447 894731536 428641215 804013703 311833555 261255990 447409382 390134953 982783139 728289859 868830892 496131220 356630716 288221260 887798345 561639128 856055827 720558621 136741178 704247916 470490051 76976885 889061076 300256910 932800356 932674539 133075122 74432083 563974724 217344223 625117152 301229522 112075758 53758366 105243224 276425664 167530708 552652606 666560617 2830198 133458816 535391508 498961417 490089531 823612767 386759762 51728658 532184945 107318382 40986188 88949212 430324784 970479424 978010287 583098045 903279779 763201177 568689518 830228214 179692252 786033740 455345365 480921773 750625849 361620082 438681349 27051513 381667141 991333954 693612129 384497339 124792769 81519988 883458755 467398651 757649106 122734868 519127308 289834050 82569601 412629847 378783261 512894384 383109270 209309899 95992429 138905401 825027427 517198298 969133614 4719679 303232038 276995330 338157803 53857886 491131763 776839151 933425750 872798904 620689456 479554230 257296242 597998576 561074217 140754996 65397226 171239674 116006216 437040886 461073723 198575816 849670732 692373335 711470200 85296354 901683233 659978980 76718106 579227012 29693629 45851719 436463042 332925666 175363400 774620844 239299904 666495162 403976347 25242005 391810417 877182154 504796235 649106658 327697082 65870451 642378006 245610659 89626477 758384221 682651544 550700199 956960036 384838628 95589886 520946587 322651333 997273118 33441918 399369438 429016481 63135547 297737508 865479522 248577564 473100907 492616718 487877467 992112420 896593064 513119472 383922837 626291569 17915706 885545846 953988650 936302508 380440203 199599309 25928984 138824423 734767204 429145535 948300811 119605831 524735420 321763749 294773515 374524889 207722019 694142952 803541370 270857565 991880459 521537243 519435128 317497717 14153960 859828947 309610137 763263375 225464770 546049325 389554944 95896827 431595170 196059945 32199334 812035373 395659253 910644670 803376147 130426457 192306556 604193309 102548639 569558327 778473410 249838506 944083215 986195428 943981457 600140936 109569344 935861916 121678179 629004471 105875984 988348490 341349769 415486120 751611865 566814538 961535444 993683160 662711364 245646966 189743104 547427050 910198690 437918709 310588071 566091188 420861517 502894626 22800849 375926507 72452952 801274258 625765012 869052518 787469685 569746469 321709806 897039028 358124736 295904336 378559850 464000719 136769177 719909619 732003191 888381041 139240508 546054986 734580552 801951872 791701951 924323656 349378921 554416992 214758716 659966991 120508180 635620232 15377968 143309028 11546738 940347271 944583285 637311750 661916140 584569321 59574570 983625945 334124700 270215657 132046632 565200901 734216375 268815809 137626871 318735917 9713201 276867379 864790903 744293753 78819250 509009205 521133760 280714522 63426197 735892475 940681512 36450728 224029058 808575831 179759755 235575795 748923101 976859391 725403896 263355592 413945063 784978465 99497889 748069762 55194121 231544520 165787014 641926848 352876680 303413885 960662764 362589881 580281263 677970018 959399985 659100512 186979223 333050096 939815033 102921771 68942570 733012896 139372498 145487979 394105078 319132252 381063773 143028178 148507994 106467669 258900121 562453056 743962485 358398009 163039169 651672958 589942529 328826182 146116157 942819208 632240066 959295272 157925440 212521328 637265290 117325424 724138191 676760864 302891871 516469575 779682634 224350792 101998822 919055131 369838770 496103899 90703734 750902543 491648428 239211727 709886563 750548549 801664782 306365399 108946557 964703950 810554708 551405437 293530131 956670864 346740997 925770197 768482488 504666436 990807876 258264129 474508212 714946067 935024992 777400082 83931993 714707625 1750874 185930815 486279107 224105995 682034713 576982840 975008537 173683141 816194566 537411451 924231689 617859347 696293202 885694597 435079648 506847909 437100034 728609778 316035125 783841030 506896326 84517612 141023817 350220554 195298092 468048380 65166620 130323083 97964814 1614964 697547059 99715687 187545778 183826165 176338033 869580491 760809004 3862922 43263631 429519921 541274372 820011671 47379267 90083925 558222619 334975266 596931834 995322652 63585043 765483310 631680033 422997721 702517273 625220202 773218274 897815364 93268581 690901245 28138446 191233394 692516208 578201856 143465432 880061986 762028020 319803465 602158828 375353375 323666386 497938810 804873295 717457109 170466832 704768913 807541034 728689450 39744178 256989219 576528454 955845572 22472528 60724838 231359644 724989800 685945039 857094269 475321515 779213620 400511865 355976312 822963365 93028073 934178167 966428797 825606410 548722538 138748613 280281589 924075912 314931350 778220398 581465558 32388458 948687229 138750822 839929491 677376678 31011351 96918709 106421483 839373274 971907588 167146321 70732918 549413739 853091359 780343538 24735253 484821330 180855403 380711564 307784695 126399827 167406082 126729843 804522588 716128619 117994807 84804176 492720882 432926156 863024573 74186439 465314613 664228153 65453612 157760456 194121182 96464962 107195516 300542665 788354588 79103104 467688985 711603857 481033194 320780343 491947394 505768447 805601673 525319148 738996362 965902719 651718974 906402444 92632561 308757913 622531062 63143719 393562088 115251944 496069874 109103012 41954734 961384486 773331164 959924698 971661293 967452346 908906011 78856809 120511362 697260598 10476264 588200346 261380806 344025809 908980688 753328200 849794255 567098712 131163699 441306969 385517782 782882673 347709412 330666694 91640585 822756825 393810412 337719025 790525120 889880285 299338388 684996206 703781123 72669552 644920903 675442415 892638249 406343265 606815575 13149610 103603863 469808190 453866307 217501020 813833999 215363346 970829219 516144605 782462058 101992918 957451573 20496191 737391942 157677336 351162885 681548878 980434161 744973296 871784254 623475632 634853581 171122642 308471837 191151055 96308545 805909091 866593469 841463145 212252356 325925396 707129106 168372570 648249937 160995412 385873589 314600287 376358757 209219160 830744892 11337166 163728429 640712816 31833357 753636722 650906504 382996241 287701951 483857016 127969536 159486205 107332647 615339468 183125198 268320836 806490522 279433742 74229926 525600343 120896886 138998633 704042090 680542343 307371202 352292026 841537754 545761143 666892313 70412862 754980302 350153556 81750028 771225082 843382723 966099736 524861803 494289226 201612328 812563753 978146241 182098215 824566309 937995240 797437683 7691506 206316075 456444556 139641599 133062352 834561250 113054836 272060985 538603339 793597178 579432186 743411717 487651283 125193328 262820381 558064145 732689981 612973936 492330524 356431414 308873010 310946611 881293216 803162236 512558938 546373321 633824828 694657152 223455981 424336419 344611186 231147487 630652493 801055742 370789085 763714845 488133343 483843921 35775829 26736682 129957450 467724366 622664750 617608733 445434046 885485130 28189229 30640378 350975417 520519752 387071792 659848426 831466362 120881359 315527013 196541651 519771031 949351841 891198802 743227012 226204611 235809988 974374498 856857104 889382081 197679934 473088300 377515423 534040206 361380480 256768456 663997656 681621197 879433205 281606388 127055242 617434686 309795616 10211972 968410102 682831719 249800115 628258528 366814432 370681473 943785540 563356082 890452504 745653732 454554883 486195867 971858343 542881222 313086716 681231798 432263302 510766649 6836449 662295077 44806855 220733280 919063532 561320862 902354476 651013089 842927249 881926070 120964126 5239216 892138041 89374228 688070934 141938155 570149107 54885365 365135979 366450998 470757798 108104834 112104730 925312680 594300700 936479424 320710254 907387415 470227573 752973555 270670416 329580373 267784983 167993622 550313652 39364867 729314483 452668127 690377955 424758083 187110548 811342080 282513650 79248588 753232659 970584583 73703094 323381765 877986299 291355425 689832763 201260448 251976610 654453844 126573127 846277310 443449619 299799732 606181076 766193543 52773287 729367843 95773915 173074621 897361464 646087566 212439487 479192298 951272044 902817441 756466732 138382592 566675873 38980381 70147531 172424883 862081315 996366977 495806648 592583965 140238753 38155762 793844412 392215362 545125957 772933891 91009023 988575575 72733622 697190099 607285469 978023260 279074293 703059383 151097881 28952109 201663300 363537367 508144406 5451695 118871160 117127490 143834286 538063384 156107870 66498169 710488266 18189185 62865145 58811265 463289501 203103897 96967026 257133913 595319258 642092982 30067803 686328281 483184908 955317776 236034731 90470376 933341036 515109023 646046110 936955268 544061131 700225761 153008986 904721889 705677456 271880145 21849378 849511741 809943528 30473599 916009909 372948146 48662783 831391405 431759410 364468636 34495301 528726436 621602548 482330911 23335769 504186702 21175543 359037029 312020829 109726625 302023756 97878216 624835647 948069866 34833483 21413130 500811978 187842469 926135018 206489433 312238965 800500747 908517526 122182493 830974345 677043786 347646990 732153480 508435191 779406399 96622115 395446843 160649186 570741014 730294105 183984955 74927715 751469647 543021983 239464895 861196271 845045738 337343111 338548270 645631955 372176593 212477751 146443933 412535413 138612768 205449717 724774378 791629866 113967242 699473222 622604210 643527380 47120211 207274041 4478922 826526609 303896155 399925764 987175795 874637168 130219869 23677101 802081234 734205867 419215435 41546129 447918490 116777524 231405591 638983111 762409479 603582183 851460861 761369763 16117596 842589980 819335831 593408325 634219845 785819425 292881546 109340406 429346804 192518108 316614447 433825725 19044716 473026953 686267840 858736862 200180473 669004060 734930314 2261706 255726279 154145748 896324186 703644768 270923272 127729776 195144230 885849102 583828311 46605090 499735216 452462258 889195069 319071046 45870582 375931265 104890470 191268479 337788022 386753625 383786586 654402468 673095701 255347653 127429421 359363541 966600867 180126245 28367600 701531180 34904302 136610230 708193280 931228488 840254997 979116551 911474615 35399226 717482004 347819277 934520667 217217219 652797886 676232087 388804616 551184819 52163351 346211438 742453297 242467725 732965062 978756234 896870192 258577115 86620239 876815964 617940655 53221105 56942208 498824606 607268636 91846510 635434836 315461915 875591349 328206184 147094817 639582315 216121762 864576820 839917944 3158780 934310390 492715829 679390867 323115006 43900648 584070569 669326443 638870296 826538293 254807856 470142882 575924837 513384970 556763120 305257152 983841976 609984224 214715712 335182934 69769211 159078573 970617769 385231126 34669921 151340304 384842294 526768587 219978417 101935466 219202882 223137197 36245855 711918711 902528063 211877212 608335710 486598631 881203654 99722357 165653276 988527862 569865238 741578112 354429183 126628357 46835263 338271159 589128932 261550974 673454092 658898143 420629546 496588212 896645620 307815818 500444867 281487913 687100757 720423284 383423378 906303638 943560480 272185585 470738700 846088542 484062796 79074409 185203524 217782802 31313118 350856799 206310663 453694707 92434910 560739845 432839416 991786525 751527355 21968347 105853850 277497798 533382841 526483396 774086009 282544812 686815565 127047228 564032725 373916321 847470511 799972454 132736311 791030990 72158038 603475010 489635883 556220834 535065771 527355758 774003635 566378888 878212557 832830649 20073594 823163818 246086845 305429361 667466694 997614200 179914060 773320544 275111997 713296900 152320291 901714358 995841712 839135855 28761585 412390788 65568528 876232095 64879593 198304838 519779436 137037631 801779847 861931670 545774816 336845617 389287427 172294802 755740856 120016335 5125450 628330802 795696505 251212294 933760162 463163198 101342845 113674221 89000093 376454842 679487473 241320383 130685551 527845536 80456238 159447135 940236323 146024765 888195581 5115915 344329602 260491368 994669897 146109448 122423037 540444712 335471417 364226815 712739513 91212272 484243150 570381314 572059425 132456006 821593608 505819587 595619203 922936452 472010159 684619296 151907645 151497631 925939678 282593195 679343166 858912267 294556681 472095840 4937031 182752261 329728107 201782984 443243628 176914355 200408784 418183016 717359067 388396552 782409831 282614931 332125175 119169332 852996245 904184600 251625337 527106204 262520538 847244539 302559007 734530696 384380186 306983004 886028327 162836216 589576198 417887844 21748482 884132879 742500036 879201865 919401491 72228142 933501200 215161471 101658848 133909983 633344486 819017914 374822886 415754316 954149197 706948061 534923647 659661793 611132660 786548983 39284348 873653197 486309874 341843354 460700244 723206411 648826357 199244922 886042626 90918907 617132766 760307460 827568137 212149153 492025676 746969627 136893646 278043227 962131097 238552493 264469562 447991935 57570407 639292447 863746250 864235955 346240507 251186249 523897747 809889518 890251583 563182094 536059066 229077808 757541799 996759310 952284219 258884508 196004231 690843196 349803414 665653348 303667007 29887902 877802500 795692682 776857528 14696145 73735909 591504977 253248638 190721822 39496911 163335396 830014268 755759512 27571350 28771127 859462112 403985448 838660644 749713695 819683893 374719710 978791502 577225691 223995371 783592072 836110198 419999601 474435268 38429963 85652949 778102274 68317864 815971800 426311308 697691744 830667945 352563568 141713072 936432934 543285389 33726334 99768329 225816008 789485845 979856030 254587134 501464309 236357829 93247778 103694355 56041721 320483839 82485856 485783763 544479209 718594280 174410313 964478809 45545899 65356627 902648109 823648172 133674491 571136261 102475831 831366234 254320557 307555750 973079305 190753490 850841138 6805638 143038170 76657146 648807834 975410551 183760631 2788494 64284731 277008408 106482848 120326451 597492246 41485056 458626565 141971454 760079335 485553229 958966615 805625233 550909856 714131075 481789756 684584346 137783687 584265587 368466931 392104243 891821336 194062587 582857732 595178826 53384576 578412253 524352323 554708761 553822803 708112953 557497255 618107533 837637713 663980102 590950335 287646310 705465157 902093252 282134116 465544491 387646480 93617082 123686075 938556335 807748156 605475831 475657032 945531843 42257769 696640314 190152437 934079104 890702900 773010169 381774281 796603827 203938773 758642955 351312588 757761576 319272260 908809842 228385460 156909972 425306295 671852147 444556281 130771452 573945398 726690396 448832294 814108229 820307477 572518369 605180916 480571985 177994199 80837947 278620179 220251967 629994613 468772615 6847422 373213864 94299135 241138055 169817691 298237908 999781009 373646630 908515835 319053268 134972823 136901294 328479591 560279117 661269792 773035872 691050568 87731541 352242619 139882862 901839770 25066448 564917582 507020685 358154784 742911780 440374983 636774962 815680098 70369595 958063928 822527519 296099811 52363063 63665573 465917501 203117322 915962934 839564130 111633156 87532553 974536952 101050801 416012144 387332420 614836945 41564367 78382988 702568485 393806985 70782201 604408254 271389784 488216134 963945290 629544567 83644265 256836625 118835880 899324362 179722571 76899808 574368232 475822381 981779222 490550157 941739881 37412895 406513090 633820362 1562402 494045642 460873665 102613202 910057785 848206085 569966498 951622151 779105424 272534983 197945488 702403976 729459588 469335271 43136461 693404878 98879838 126780725 950241502 70232069 26105086 129964072 147131876 600473317 458302805 128911097 91023473 252559037 18840343 350052914 886379399 20402744 696614908 199769415 123015946 459189044 900491851 545498795 263327547 532113626 818033777 461273034 87033953 400009717 783124656 130170413 93414594 734520845 256951137 896172447 804752914 283056222 878652870 951884789 736045891 189472026 933312238 679585715 442031063 952152580 29638629 180926813 972555324 578769888 380696227 948087621 37958931 133704430 346102767 301286477 665818055 16652896 615075862 752852008 416662612 398200518 883022420 362593557 132721362 139973557 111282355 789990627 275546130 989935224 594391768 11592020 31923602 380220357 691177735 473954664 184889288 573332715 654881476 9960963 4618954 35577702 958048583 42577884 21798483 156667702 196380713 687616538 173320597 811456574 440468545 589983208 62173443 176007316 952576764 47411157 315980872 63859118 837401783 591527002 906310693 431793550 455635373 938234294 812013906 146813107 412188957 996903194 572662173 67070432 6864156 577281126 955164486 817429091 472375362 976962968 974096792 668756074 517095857 147417388 480212647 957564401 589916947 542386090 133571717 542493710 589797246 302068940 458869179 279715380 746112293 365179871 711508930 201747666 155930517 376039187 201077124 568119473 225458732 626255649 487706257 84839240 56053126 295387094 754784682 528428487 124866413 581397825 197184560 641962270 581331564 529913559 452043022 171248510 72299648 438131090 566258571 514613245 592716382 25127749 794328624 338828674 242823971 358353905 393092691 398754487 586909444 594169815 966873960 812368175 72941815 307096568 749723766 128994940 455000013 504508447 657423427 579866425 85906271 854607986 74345046 519754186 237037896 378904420 691002695 161853895 817035509 109777617 676467139 262268242 134905365 323312115 601096916 377729336 534182371 994189606 776483822 121091814 440875772 595874133 785976341 513817586 755487052 535700106 642812526 210487064 892724905 152752304 642869841 831147527 7360289 717214886 350901713 96914537 96119305 894420759 258768431 765671166 4198376 935235570 27939407 139103740 111064036 481552674 369349427 645246406 328258632 998349601 618854572 621650755 446740085 404830912 135468341 202227137 793047369 630797218 265230552 685772273 783549521 908100392 369436152 643426161 477831630 720337864 740340697 426467286 467274974 999109128 44654803 471473349 786861049 72594210 463093441 750441436 406663235 684959219 248204193 587438218 683308819 867058764 209088973 130048904 124406027 197073665 184792392 917453396 680387234 450022943 455742020 316453106 210639687 825178171 959879266 688471316 398032386 552736315 114938601 865307360 404361794 159593404 189297060 43739194 84703965 652390500 794180629 343883551 189866071 42384821 931321769 873174889 761959937 140410741 855740144 886365963 190000757 893048887 803819358 870387990 195588182 112077730 39357447 406227868 937255900 999236712 94699183 335288286 404489378 62154135 53111997 661367523 221747538 242409056 705106716 158967854 894799556 351803696 502851405 84665626 246704869 434173173 810356866 8664805 427100265 518613362 747547119 469617373 264178600 403882829 192521714 459766781 515960558 231879160 865994648 453216457 83632223 960693830 641021094 488121601 22847965 694133090 2005475 97111854 936542146 707112191 256079708 683858053 911432238 758931112 621040030 10653458 45620636 283913247 19318262 325237252 802526608 619381733 794854624 66705208 23264561 987376337 378988340 539225118 219255496 244982988 844957926 302887718 58193169 485979020 643525670 933557485 32628461 645531145 30669339 969170606 205159687 139265398 653028658 116591924 750712861 126585039 127245382 796333496 410498286 999079995 121570747 65541245 618461727 768941722 132246452 494242639 756318058 363751144 33467756 828089905 608734131 730942034 130977622 519443651 69437405 627019644 453001136 102065865 272550788 336186826 71236471 477710474 327968575 576781480 446818749 78681435 703366519 574064130 727531282 113864804 425660477 701618380 179406048 44122203 470560101 164168852 390881194 79394510 527919995 276865301 907484414 989170477 7807334 890978387 508614127 77244738 370514382 814131614 179310603 643065169 2834791 103063425 973291994 330803365 679844904 420110743 409484799 383211422 846691224 137016080 349592577 272351700 691150811 528998625 168990255 14227263 545683828 559871448 93621772 73603822 836736748 853622537 915290650 697060434 597117276 276421128 774305171 967631657 90552742 806132125 463213178 93387532 909195549 436505171 424190897 589040453 709132265 686192047 824768226 555823489 675724479 174360803 680691540 366875289 555875779 849681794 381102552 101559606 262069593 327240675 27679779 951322693 180863212 942970428 648383126 777980487 71907907 275204648 598128495 162460648 81336773 61341672 108364532 843048673 350363195 532555428 284605477 59495459 71263826 109373703 467835299 746988304 136250857 148526839 113863593 692126635 850724984 347482496 793686240 112794577 674723170 673882370 916633621 708102733 469369149 417533098 338599571 541277055 692737745 936728066 703737703 626590869 998069737 812102234 322155894 200949283 197174013 606761370 260444742 268437838 716135072 728280040 15426142 852385928 729323230 981806086 397028914 580048214 181804933 43231505 545359142 709044454 717113874 314509114 417147187 186483022 732042211 755746757 727760077 277296307 544991174 284014131 903887176 395577263 948632716 78559421 596526545 145806728 685320790 856971286 266760917 253972214 437767678 134703410 106358141 19607259 969025847 355903407 599655472 3347131 399134911 997530965 712391585 116248785 312040078 129538771 155248158 44082288 737801879 883008234 173894947 135309405 19538716 77782122 530886667 968171431 8857894 127413211 966494510 694178683 836900849 85771779 948150896 127184878 72991540 907025389 146792136 42017387 262928795 746447608 45364517 662063705 596494924 757756101 630828841 908535002 739811223 786076999 805133641 330129454 521601584 979028587 465438858 541140300 909327060 996325524 361828082 918184953 976255086 180838944 464879988 813155934 119127074 413030883 940340811 192118613 172572623 87132947 234135999 435501417 686096906 132016868 950081474 135108181 889772968 580910314 43643182 482100543 219503664 701293175 664746348 741105248 532838113 130185205 134761899 294681525 979027080 496589980 65382829 807798517 529945275 530262816 473470803 649072348 795810051 266327965 841190961 968382673 205977263 75326959 256400442 892074168 59860178 206481915 27182349 949633146 639908580 923341882 284250040 859412244 477151408 948996387 600517491 862505873 931697943 735279389 9703749 763241374 84385720 75086577 423556242 614330995 457865745 897027044 115919694 253675795 163355009 957110654 74574819 369332271 884953965 330975260 113922791 944814142 537457174 993621491 746963639 29882106 769479724 31213678 889294349 99147484 832726416 342328191 961653356 616940710 77607579 971357104 232698435 14509650 46443680 656254677 481356996 356825776 405798072 597276690 610501570 569153080 554387343 685076389 791001703 291857659 16051648 904924493 236671801 406025174 751062335 983635439 435907279 520542058 867365469 177717979 619689541 552608236 520046169 433859248 22065298 450170099 405216351 107280084 464679748 304176383 763534760 946036744 661002158 21849184 395829785 124020080 591002263 950217127 661612820 234520317 94591138 530180819 139444809 331262938 936205992 743023495 167414728 224629622 116081905 887296548 402347600 735771445 292421136 922393768 22147045 314486433 225080218 427363395 421766516 689759966 584056129 37817628 488313061 97574639 59666811 884142845 221594718 503185425 686876323 883207537 737705742 781467460 265904707 729666902 965246749 54627051 472690397 132661477 279256672 588772301 872474376 534120624 177060097 164895511 309030743 199207141 331898295 534110961 479086888 753664811 76387278 63143016 643998790 564700338 160717654 703665600 301359534 234828723 59367376 840752208 118036259 797073117 474736020 236457318 526740019 439982768 291084368 851946767 425160596 570341039 293235419 150151324 104461662 470295515 315046834 266008757 522019008 646945129 800119717 1105895 253126291 876506994 64248910 897125080 293723683 77482916 453307031 595083216 312311638 512674406 288351775 282864249 162263875 763087794 519321566 689003893 55586914 810405933 393467011 480747509 233263323 686702429 630898832 190241337 9514295 798462018 456250093 531533302 297923498 108886161 532639196 551049788 985393154 449404458 300691219 279116836 379403725 606514601 726716403 691715362 119189006 15068177 827095962 133969232 778155971 198933879 822973124 833742884 9339811 68956486 167006744 95119486 755658914 650421928 137877174 765173209 448883945 594127266 296706510 746807442 703013426 681862058 150373581 540922931 131266515 303581151 820039766 363186591 910095751 399272520 54901952 881801108 414340696 734514266 15770340 45013018 933448144 691259815 731272253 795304307 760216301 898278997 890423792 515875214 401217276 28300965 133564774 850101220 474944582 430271284 449425013 30474359 112133341 452314945 571397289 95916207 755896095 243953406 311619149 665991845 643225925 219037452 400309304 910082972 953551717 416079643 955095990 886999861 107339458 538884594 534820519 720072110 289679942 277760662 88463675 690897217 158577978 222028449 393514788 633522559 652299732 842939800 516513269 616949424 147771096 87910557 565381982 903667190 184380314 877001130 422175386 680122590 96038581 822484690 590205561 902106650 91080684 397817902 641622862 50936493 936702496 176443380 771008602 78898789 454204041 859472277 769796006 612782018 81500725 163310793 98820928 586316808 858766945 615334196 55782583 6538040 555761104 621164564 910205230 592657769 350682045 184896967 272780358 299236977 7381656 715502270 53859978 98462340 113320172 695482839 149398832 902539019 871926218 920407434 981437807 178646610 632396062 603750164 643944979 713896786 767060957 742765906 152729945 478344253 210616453 208512527 484882292 618893908 829677090 247603873 211551676 32875486 432500840 336848385 184628814 292398847 52350655 238488792 390861186 18187178 933971630 392776370 773242548 658414200 165700155 607196706 837060809 798096216 210946870 333522140 364509353 830524178 76288045 517239297 308868430 139420850 725751823 646267073 758314757 407945264 893870946 822382785 440820749 178888137 159231169 625449562 471286983 64098175 863938353 714664521 82285352 650426335 107440890 855527899 308840534 273141044 315240957 998417694 71237259 526187826 331939833 288262963 209228355 260744230 805502259 518096784 252681431 531254081 16880208 10996187 939199344 910751153 685895323 232536444 942155641 845126492 710502357 265958976 909224666 426957062 980623496 844026370 77383396 88064385 552070620 238740281 213721780 867311576 237157974 137475390 246015753 421614159 425738352 455244107 682358388 83756962 973340890 935039818 615011042 990221098 798552356 406726737 753488602 336964031 491779532 548160595 34606874 202281888 814119570 943831539 629238949 794743065 640374260 559138696 735323801 192444880 797878976 801561932 59756455 35036950 939037321 158288560 309167460 217292024 613532666 991525847 301048985 439389908 779082016 768576378 282127357 430150723 27819466 35615958 767114753 519598997 436292904 801721626 721880884 250412473 598069517 203636185 897671889 90960128 762774880 485512041 283405007 413170208 287073972 195677814 300723509 78627644 353966373 609890968 148436019 967499038 453933166 449485003 259405297 85531533 70577732 541532653 515682255 98397197 429664963 135313360 617996193 865957866 789551337 192393429 116370339 240137205 396029613 866558579 331097333 11320844 352070620 614502339 424491051 491660943 662696504 725214559 570288587 16662876 187621878 718724605 836678266 641555043 20725960 96083562 727086575 91303691 490132567 95285182 189700888 919797529 230598541 807697080 785755394 20149877 90508 754642084 112803434 248636472 473717015 443900766 112473668 825787634 58403104 536964718 169964928 573615960 114695629 740253514 442795187 302317506 311494471 131989804 943872549 184736782 80589718 523475475 276040472 570722284 618760656 318257711 490519812 849359196 125954791 128791557 722025425 978561650 735949993 834828858 79714474 209667007 131245975 192188141 887970992 42165430 581669210 57935919 615781389 696364838 650705785 58576576 851198696 962200255 190566379 647587596 146937036 271156096 171063070 275493859 841878379 789823726 593751570 184914542 491699273 572222712 166222451 66241049 403300713 902172443 753586258 335531538 111839449 884832232 527719678 852326792 926997662 109388888 910262710 542779050 658270077 413484846 453871977 361985124 228201452 644438356 9572719 227654839 768110803 33152141 503148698 462505534 822975866 949416619 647420075 167191490 374155682 813642525 85948891 777456394 568331319 839535148 112987932 532687119 724367380 493223961 385013910 503881393 455129200 147792972 46660442 965915629 561277817 353048771 327900752 789479269 997487126 189989823 17134107 618114280 223141963 372799156 80619813 46117828 174732126 580556240 65825669 548887807 246715116 151774559 178860553 815046435 991309707 144364836 347733553 568193438 637588796 585263815 72074830 945234348 733056786 971251623 911149976 146850954 176816745 91567079 788846574 26820222 281556901 658497033 644934502 504698863 31296188 725554314 403333042 58544666 158626905 321675063 607432472 405342021 473449621 786293024 220388455 317275679 930657859 420638359 737985468 420763007 5902173 662576649 365997354 591475310 486344624 129663681 738326264 663161368 73747111 379689189 689981590 355304012 38186221 334916091 712519226 921998761 912986756 115852268 980543426 71613661 290043682 587975897 476955681 763493302 226785273 549860487 933285333 157443131 970498845 671270800 578206137 976401018 186363801 796719842 420392679 672708424 926383522 11235294 335869791 130633 390924483 25851380 207950996 429110703 213283822 920470221 203625815 126270578 888838840 184169240 50400590 31398873 624661489 379872622 794892175 851446761 929733108 580693859 8889891 900231952 104481010 439612380 729149321 290844810 88848573 2058352 963553233 15232095 13293645 151939376 867879079 404218127 30307107 928346426 833328830 243590929 701332998 36954644 222377858 442688190 73640236 125294799 474087062 698301724 505167420 121495588 402264836 434900527 702189446 263671078 187648830 806670456 703283457 769314503 97515265 792132030 771372854 61068498 659880476 784666498 65524225 380275906 188884625 95831331 161138683 874729806 339422259 862471680 764200801 414316468 305159869 837841036 539611266 779246931 388659111 44778685 900742518 790923946 332195563 455448316 54595024 519844393 262118771 610394832 141675247 212150387 255043213 913048100 125735236 767440040 697714597 191259460 232297 739115573 287090791 161370979 613845378 626513049 23842659 230562531 40829517 181518879 68403566 432957134 960765809 309579029 477735819 714024679 953019326 809931381 21989346 860130701 182292125 284108116 323041885 323967371 496258502 578085097 89531822 621993738 198041489 787246419 813253197 198273785 378878343 100343987 359644764 992723721 579373388 383487422 75802603 472719256 565006300 144206168 905676389 378288461 306301548 235928559 944829491 111837226 898376292 966818836 971967926 80668416 103443303 295009810 257152139 599701804 725611259 346683960 74211893 923652747 986446730 739981442 121926531 365325073 692841780 481571294 210565145 124731519 717575067 286367747 597450774 135097719 283090266 355643515 513386179 441908166 444088425 310732021 553745391 342464716 277550856 525713316 275649484 380994158 673239478 385317974 833212313 398850736 732001933 907424206 175019834 570965015 499921999 296946364 936290087 192763778 631034010 999371583 317495297 348609076 138255681 767462422 483706794 421345946 123105936 849609324 863254111 419710713 160341344 269515853 762175428 290408551 795229169 890341263 671402708 320984998 275659236 357131373 719835733 860177521 117071930 894855566 431142535 616993928 44318281 219948973 809757705 675352290 71836907 979769353 876477718 210092587 747231775 212700863 631438532 722854062 62310187 347208995 142564774 75167882 616724847 757256554 365576433 264470367 500114168 36979140 585455364 775773404 246626864 157807448 488467276 363698793 905179365 919609810 980692720 949497646 992075134 642966777 477366287 63912040 622736129 206360356 274004626 222484255 419061219 757959509 797854669 481371405 105168503 792935794 556539286 574409702 402708699 922115718 691396420 902822867 811611210 129368136 531112622 58238073 287175583 19579897 274453218 44871300 791706058 255145937 994368945 783781191 898112713 324251583 700209582 373365194 530611939 974214207 448365800 949673157 584690067 246220468 283560913 542374922 39156262 692616550 116784623 294381312 467248620 660697394 197204178 131376181 790065529 728316799 42130605 77241112 600413047 316583822 122112411 392119104 571729759 968997707 28416646 322358823 145765641 728626227 548240368 528893931 555356785 996606168 331083439 140046852 95342987 614644351 534938125 134499248 159777253 504239099 281396912 627025872 164936492 478601089 758402052 955002021 59434240 800532656 884759484 659847286 117116478 859388246 904482742 541362588 680902304 932899387 863721410 679184296 514041966 264478130 208078227 921915102 261084297 539161665 914478305 356427283 6322368 449416429 343442883 166099620 953655527 624839794 793125491 971108371 955957234 404043894 778626743 15391473 204576549 515902578 527755111 174209378 227807175 284754204 715571965 908709478 70169942 431809727 440410125 584211907 696287856 648488351 358643361 957372152 40166368 273121665 166315786 46488735 575054446 362275020 65104706 381226324 987114813 710746548 352334694 795588399 114790441 130961436 663496223 171883341 499380365 43767685 346092719 727187539 328521888 61664683 488413368 398691830 493474409 928823493 982903736 42278616 429828195 194063448 999650767 469994562 467185113 18482905 368999648 42239558 380757924 286620705 275982233 220389089 997367252 628316927 15977487 112157692 611794714 531990061 136557385 111175079 575757746 482650103 690878969 904279633 544314785 179292337 302971462 890305546 108115829 138391550 932584161 390460375 332454997 784751280 860454937 652156461 803234184 81970936 546912370 36508459 368591641 822894603 109413899 218475244 303727881 125391385 183149288 915522594 509897798 319706672 879214024 85655543 802356774 422609345 989935175 199187910 601901681 145422989 89493455 562533861 136330890 22077616 952994235 468785886 659345247 665965523 120942347 315095782 600452811 520371068 351604240 969044451 343265670 461018139 40036046 646993550 438925875 223185333 415032496 948823672 542892004 146762871 886995566 345248777 569372215 729447093 544436687 23790247 874870081 486446493 438840459 11200970 361040460 244351046 332503207 20385706 910316568 305961905 335481487 363285730 826332973 539602079 184846532 22114994 620217 224882578 521624896 292062443 448067910 936657391 93402467 990959914 935936613 980398032 188725042 357825180 562361476 733161728 381615426 289747908 72124573 820455885 153465229 433165032 64806930 485968436 453550738 827639849 644446692 641548576 43441931 323296016 181150654 228288462 345411010 34287222 453171039 867035905 178866017 901238949 656209647 272268483 892198862 444662611 105182866 80923903 802487790 667544342 666601983 36619568 957292249 738726555 857075452 110757478 24407938 774398733 449242265 477958675 454554933 93688956 119507251 497996863 269501324 153174256 726285325 614912333 39977830 31972715 334464589 218843846 933211663 843190587 491112328 677926876 287853197 448811545 611367131 90340987 116355886 130485465 126960554 926164487 869212019 836552357 889438316 893619956 463467441 191196932 224094983 770538725 137402239 196118585 121051940 406903562 201809192 847337264 874332246 241787021 879309978 61313186 460630866 665037993 904503772 951743193 342964868 44873321 253071090 954331998 135214307 221943327 84817462 114691212 624165 806545832 803759920 890062480 552682140 119743712 933775763 629293474 890282436 71178002 825412058 11334375 330597915 27221249 711187990 57446513 121524622 443014320 118759698 582155487 108052312 23263470 386415032 303533531 68136790 639486121 110381881 55867448 861429447 47715694 23075011 862053612 706777878 679351282 604632443 111976369 799094993 538408206 741269842 541893780 462102559 419198251 405744507 645216825 298935851 969448848 702663337 420460472 264979519 821423035 2615959 225548182 844686504 389030990 529081713 765339645 28517110 491979945 821207092 742462908 539695638 696798454 604516519 98989867 376149735 61665314 210966235 27761079 600073519 952236076 422171210 914692429 371434326 827915716 559909253 670370177 649880916 115088942 90830648 914860434 936511976 945962958 140408616 633714831 187510299 522006680 399054475 68543760 13986624 72777918 811006668 406198613 769576371 268039538 505188480 998242457 329704851 716154714 26003535 929778369 668390790 300691096 696987149 892341467 128606812 109412754 415227995 631004079 224501695 358574995 545864512 161013670 304537952 538789479 794728500 492048251 60796158 46299326 560592010 74782781 119077243 224115029 333497746 741169965 492154567 838686225 591928773 821859417 554840938 470448659 604154138 75748079 771139754 301141286 968089546 752262917 410554039 235833892 383266995 635055733 594408886 781647859 648585754 898946838 320437337 295830605 243511440 233749847 342129930 656619801 161048979 313723524 880734830 494546724 907409840 372889396 333232948 499338612 47265164 740590238 969787270 651419301 816338316 593443376 952560587 636944213 345706292 215630977 872778105 581489639 703203062 319703342 363137497 351788815 71166531 536091185 647619420 314677970 769841031 842265701 971297771 930890010 8505577 704548952 425436733 915915416 77438347 611186033 267770380 124703510 351776270 90074001 628639163 20630937 683517376 433716101 510091502 29223668 649347077 235385958 463229658 205066490 555089299 826367154 556855305 626255830 214974690 56991076 940933799 984815721 899256776 764747921 915705730 907762352 321813224 193658814 676194120 251767922 804844846 943964499 228987784 9137467 34038499 857626946 29768404 717555875 291343046 392376257 599295894 793206474 627762214 62525551 998272964 182851512 741409056 407644620 809107341 956383745 464635695 602557492 793715817 216408822 219821764 561937898 976687526 541634988 755596712 652881645 793402909 412957909 449362495 22390692 274611728 483400993 732533989 156896483 53473219 23877034 549272739 505285464 669599860 177034952 420327366 667872823 212402815 14252773 75517442 21510156 970636518 392669488 476583999 616868686 461594661 548922114 178806584 438282186 90557101 786919647 943680182 736476362 52393907 393042676 611383405 327005634 728960021 196433746 483902116 782433239 72827131 33174854 140235055 742426990 62726157 560562420 262816164 275128972 574815193 190849957 149155479 397968062 583519444 625739477 14836747 45114105 27177942 46159682 335912642 117735043 833079328 132109176 706727756 885473235 525151851 170627512 212478868 106628223 367061257 696380984 889061462 439888388 582072189 29296516 34831729 644798346 442375287 297647893 919927317 17190479 488497849 69082795 415158540 72017293 547338623 282511639 969647749 574516564 328671320 158076742 544767958 161750648 290185917 104012065 47223882 667854120 274639577 112219101 774482342 494217185 661116436 516060155 934105572 243188625 397873022 968937301 887986970 840248309 119101545 660430638 857438787 607599393 729513432 125113679 532133037 129368406 407625317 354297137 703884969 736296636 512373879 248652927 750563635 655076147 352664991 650303868 322930266 479820919 762522969 97412608 974038104 276155756 465989114 760660027 519344380 863862136 582113679 259847701 704110444 701215223 920278338 414065582 308814616 502308121 391695612 840947652 631676526 799320928 47761141 188077847 388133916 560135019 436730773 138697550 67727517 641912115 641517770 390657783 121733034 256557090 340586742 95771137 532712845 806575855 708947515 52057225 522954342 291061194 164421277 79581137 992276416 937215967 493646719 153607383 292040439 885342330 847071387 923716965 537179610 894832527 111794811 777829877 307483897 401041935 769043778 375211413 42954049 410561547 765869195 17203434 667118636 958972288 965490922 52347833 618064495 674438437 104405057 141018836 818015982 121342685 220599973 662808749 58558651 566763043 816416132 203115442 304621724 516003870 126832406 841801333 410836396 91143568 472147561 718320292 344701854 241191339 93531704 240172254 504269237 711917251 109892040 23904225 523405890 75382961 76252057 141470384 602337749 33173465 135005572 420353730 154516149 355605544 83162479 65591152 922368586 752094962 268706593 79506661 120615183 248055350 921307994 531451578 191715269 245971906 102288221 388933474 487163244 48336276 629105727 991432481 612769878 738997766 15336705 136175768 666897079 91588761 130162503 269234827 124762225 265168074 542104909 131794725 620773617 477783739 49902228 395658554 82395052 318608820 475165215 203010234 419180521 248989560 734461811 610895789 494961465 689266383 999829262 834641061 737602658 481451341 678589893 202888888 72965458 546442949 339064655 739862536 490548061 469227157 861613715 467826637 734395231 403718623 599621361 207685199 881502361 649523589 455860105 963897412 820648760 931025319 19423997 239829281 32531230 753885807 703241421 380009046 295668541 555587035 214650106 33271198 37038375 893239998 88676437 962520184 292199298 427741091 554899072 782747358 749484600 416512786 250573994 336396182 672747760 702711707 544081380 406766472 204751647 999941484 223180235 25400406 783483154 242604231 117746038 668530735 996490037 820987459 48539781 144674929 376574493 115706238 30462478 266129219 8946236 119138915 81165754 153661885 546880005 636064825 936409243 148880956 52577610 39499588 485277137 577841721 742211294 29358517 984608192 946962940 881816352 207788426 972363346 517815858 450392656 90109383 38862944 299399044 763613193 87402724 444073972 140187685 203108962 474536450 258833255 64571549 593675364 339999009 218233433 993071720 976063833 7159027 141952676 881157795 46658615 627229812 311515867 788869908 509104680 296124059 735832848 243437384 356428836 560712545 613769593 806821492 503338279 652632536 958736887 119467824 740035260 255327211 112171860 795660573 729863660 371005115 860232121 176055375 563520475 930981905 21643446 392100659 938140932 163596121 125774805 984799546 643342285 437290672 773669453 4963316 733414730 362018652 248400699 89843565 775247548 862170291 749181408 131102179 367319179 560434647 250570002 107354438 815761857 362741861 755531362 398141868 733746975 468279834 574197242 149783801 399261738 595840687 541884460 189919021 611953160 667659264 174718566 255295444 104949935 800904371 260258759 690881016 15439374 361175810 633240933 790686922 75862452 234938692 921789100 443181630 795373338 172359101 403052419 611135194 535100961 158583780 9277061 121364288 626863613 435990654 271148088 878641703 884347693 813032547 68560723 496300852 333208163 95795641 604112647 438158097 896700011 864371405 129039113 912139384 78063566 614796397 702826305 153926018 849735088 477131756 597107647 645108426 649490856 160066 108759971 37108169 11260197 970553384 10988808 638123810 259060389 282136895 369281864 143408081 947685794 437842586 492225284 280893956 533638226 96337930 571568404 282854588 813225687 553123868 194993972 891289252 167920264 750336628 45215269 17655352 227468384 642322916 515280129 729475591 494999333 476556451 766583759 506259529 447109834 777572566 144383338 706170223 912225813 366181553 702094655 859911606 804024139 194319939 993321913 190178716 143174220 564890316 473033304 956399906 118014184 520543627 847689158 138450799 270880254 745420778 8622502 350864989 240260045 376418982 80340580 735259377 852975433 699440690 241518906 152601618 329529608 238418595 858771840 241755420 604600148 413382847 954183377 261140638 607702785 947505289 303835705 750877004 364911956 776869008 559793262 335442491 149928986 259998771 326409642 420809240 5419548 335032143 771674228 245679593 711451125 704531159 980938969 416942909 403971849 74974226 569544526 733501456 165909173 280832718 827773227 770509320 694215564 781956603 884166309 154434700 581978243 188002013 905311703 799406550 817387373 317621316 134849041 967316358 577620086 313775034 240641949 583039634 648807176 12316177 681235578 212774652 569363687 514690898 629717560 973335535 589665124 51778438 559353342 755574296 332611155 239642920 378599967 26826718 21599522 115282627 181261417 456094116 303284639 939089471 108017018 120672011 256710787 95382410 940504721 834330872 409157443 181146669 269886857 57964618 45979197 951122434 123255622 615342884 318329684 605489533 441194770 907994807 657267970 853064464 516085454 989879124 92707383 747201772 16705841 966823257 862484398 50483609 275433724 18285388 989573080 383450741 138957399 98800218 478833150 931978471 785647441 887990592 113125139 55534298 798471562 11620688 859173083 921727183 479479923 30019118 379733067 920674692 938013924 37001037 626255507 306615729 26880160 718962890 53817500 896102353 538302498 768818249 799102313 813736221 787103637 641191744 197186962 778577387 739991961 676020111 710555857 378155754 416527055 676197347 286206403 214998616 540334386 145379485 989242150 19814308 27914955 368975216 793005352 965928878 258492604 419260858 125060959 137889116 990740099 31394810 33991468 529042596 800213059 685610132 195295169 439833047 326801876 392482130 218410433 919310188 921018592 781482641 297465941 337545646 310196339 583672343 405060613 850530725 581568180 394302762 870345032 609483134 615794330 515866735 427928363 874286933 935127593 405505673 12176048 778384043 436900483 898683867 159942991 89629893 584293999 355238159 529462939 763612226 747720288 600389723 682922413 521255231 381872363 832904706 858800877 692068701 269093400 116377841 395115777 850661579 510680603 117977161 312661064 126474932 633843895 593105779 853278216 421487839 998611451 865454264 199871882 288028285 616654482 359814872 377658177 53464832 715053030 759637467 817077057 315289669 360027189 352515822 836544899 594415903 185420527 547862127 139000956 454513926 664239968 534116732 157691857 27436922 652093892 322869272 6428205 285937787 915975050 859706420 707425625 914586501 577677035 759813858 55131137 46847869 119628729 432789314 100312700 687198110 44943132 917389757 855004130 404970321 269905578 544065381 999386223 307842456 91927507 138387178 762356381 608683826 525020262 772564589 488637099 177114153 95433861 495065303 315568291 11408910 207288075 22993916 778511762 637481461 635324125 833642899 684329329 607469206 118948564 784642029 147183667 163891695 702031785 2187797 421378367 824453714 546253177 273280942 132296169 490697035 264184471 747168901 951897213 789204732 519733490 440534311 966318885 467683702 788115966 134403527 331608963 995404040 9913794 110120725 485401852 645237919 796279975 169731181 252707124 767744890 954373209 399890790 931636584 508921345 254594938 205531303 185891410 800848114 478812244 318187578 144061501 742996714 65356478 95958713 532201446 437606319 389009375 351036682 905290020 29641692 485440208 89415335 25045731 495354002 52052411 362963935 140591920 848332385 532695115 245815395 468593626 339584675 498222536 252746561 701022371 752817474 458277863 886913780 406181939 937090106 57617709 550243439 680086820 122974186 498718503 64804617 413096857 740244230 268357650 170903228 769885921 753797857 260318562 647448004 101668210 312370972 10411938 94776481 13219708 395623404 193108227 481813333 735208078 691330763 734559894 288746800 444148236 45354108 175660579 850330174 982444214 233278287 253089965 515047385 208768824 604324819 579852001 474382032 344569048 848209650 645285260 114454969 454523858 758120173 614419324 408708420 70491145 624831261 503484900 936227204 20454664 696593127 270556889 608179093 240440241 5116782 896925892 684588476 50470889 925102822 387435001 885431454 10897460 493041317 400478838 219666283 97366136 832847190 694048315 294451535 533573191 191849926 261422855 988097049 949970098 875842178 249321820 872977594 353189790 752806719 661721150 226160805 301916197 932278038 834339897 542356437 789911171 583782140 79461264 692898411 361401313 319412617 578329865 372298772 812453933 831325054 591965055 909820068 664172244 138529721 56787955 50261786 182895998 318210809 38358834 132866095 194052987 140197005 858360041 547242776 893003724 372597542 773403581 47436272 304875579 460259829 442309061 94786749 896558321 521770324 640201511 257959633 841182940 71047727 630258405 506153225 902372781 74739811 268489644 419061376 65785883 325277598 469323161 248681880 643488407 360198347 234064326 837541393 500395351 92424366 237300520 245915426 317538259 863220452 293351698 622413837 175996633 735660758 569716937 72554953 109947433 62434800 183030937 803646725 133482526 813289341 309799949 35855306 740545503 578289592 454916681 806331385 903567190 924239842 55013264 399571948 136954540 289077590 89629692 637349890 234018307 326930211 883265316 551556566 42667015 29133365 26486754 218663647 764794122 448720043 291218599 727257906 511154842 474249535 530904630 644637367 140055228 693220930 680492673 880600730 124026874 987925705 539448467 27594063 764681898 594461730 279682362 901636437 736055671 369312053 538986327 970073978 696242263 274767994 374146895 738909277 303901358 253150000 957572923 68695479 701870042 101307873 648469736 213024883 428073760 31890718 857662250 568128987 725111647 390671274 301246068 849138520 231113330 840694534 729248934 995795228 287672616 8931295 897431664 23728286 378243347 288934342 846318615 927001962 563702335 72981861 518427590 867603692 326131861 328516865 788815522 28001902 429824737 289801610 93543137 857898496 321692327 803721738 278543834 46803973 46909363 432306254 895942493 278022692 125517139 477707778 273817919 413189754 486639073 23765935 289434392 717398771 165216628 988269358 644400732 728918963 61251219 15344674 449039006 239899431 343861538 90370880 120417684 773686274 380172489 66477172 484101122 701864815 870198909 615161307 601185139 917108271 47467560 349643983 195130963 172984699 827351761 321465233 438690804 166507185 345231167 728125195 883905955 510447795 568910905 380823039 91883109 482678475 396167712 393438466 722577905 740029249 483809345 695511940 366231874 716498185 761989112 850332995 270879351 632188020 318010654 872064490 401812643 365478213 221708472 596943605 390979263 49060232 918408837 829670067 68083768 116156356 410311613 951989723 479120502 979222517 332812761 571003610 461900991 728980472 964442075 36995247 321526072 300767772 732507187 687757945 17265956 347012650 390607292 140661659 979200669 708617945 12726148 233529663 74096157 86950971 830473267 317591772 136011203 601398456 147261838 56611322 570071163 557573450 8601044 49191664 389312319 193930156 472711625 851213309 922910627 289670051 740724908 96953050 590437822 325748446 784710995 460220130 672761095 175318286 600881788 504478115 883936230 466124287 738007778 810548738 553075257 420997396 128140509 541602811 22395851 127918698 598214133 444983365 538008500 606815176 494175028 927320818 800745332 966886652 631050478 576172310 109073055 371775385 673125360 699510876 697523830 310352706 12247357 222801276 485670991 465645496 727279391 222123572 931769782 465287168 885188661 484845039 886284563 865845522 26447849 761196766 993764219 477178333 58696482 384289070 83993509 552871510 311609887 737255192 372274513 942660365 165943853 481347567 166952101 691585564 33374795 716992283 1938269 45622151 939793558 340125611 363783999 667072948 562249182 295553780 984876467 299954195 632915170 723677382 165799716 511879371 337390499 12080286 989057703 396086980 396369356 925567563 948958489 560495594 515339106 173749354 355672310 681282959 507613272 522624411 225384874 540988066 92133045 227323143 439126569 31926602 567448753 802910567 551515902 982214287 950980698 536392368 282168481 583895868 112586101 300484548 95775238 449976599 312564833 937349292 846063579 561450540 862916855 647538419 121946134 230772312 821287772 477618443 912055270 181417396 852759205 137440144 722405461 944892249 217279638 14048381 976818851 637244742 669475299 380851104 619459028 620455997 917243471 754143860 56868216 29829572 54628407 5159805 332322522 219709592 942509096 178386100 781160131 657942302 825924519 903106264 888714614 499728642 233241059 653286235 681146037 86000263 643242730 256067850 883408864 713038719 122632582 712744066 350283461 792107881 93595169 822258840 265080229 863354991 576402700 321948444 745700914 483547458 179624600 78023436 703257049 122133695 108925887 484417180 632592349 934850405 240039795 373823314 287095399 325797205 879625900 820757787 264313820 375384982 76825636 147722683 88423700 51974570 860466748 291223512 844082450 806578268 113482352 109162678 669933258 542401403 283627473 268150524 25948860 463252072 346173959 729205909 437902118 455099845 66139440 70494466 242466602 158695586 296834131 382078352 484492791 28976383 202836138 748806610 404361364 132178126 896529292 492785063 184152695 609512391 784008575 28235144 268607010 750007278 989914173 938540267 292408680 273541645 59207142 170873891 736793716 405381100 900079799 27212185 712997297 818735590 97706651 955463898 977431176 247057133 190058601 461923966 276033515 392894738 63246927 680394878 377589215 959776218 25696293 561741909 421804960 662221219 442493404 690411969 412228496 284923928 481468587 557153527 558465572 540675729 728027417 147775639 798573180 480623568 174987824 511570476 299359157 125210826 319550725 129306684 224784310 509609325 591230649 500817825 755020415 654477575 33729054 132609629 466770144 59425346 546867890 741091455 574162916 989361293 284019775 986391411 126801573 765488362 396061289 685267144 158680442 124088706 685559135 957253621 604712273 860546958 321340449 756587781 838274135 493407525 885894465 63058444 3016850 329641465 416392620 610553616 984119040 450121674 743163244 303405535 362063371 142547485 44496990 936226287 131908778 181033116 775134049 111226702 946521477 23711690 796493845 957718270 147800395 334569331 767488243 605029019 47632640 88828691 361616799 885906774 434752567 100027615 948965218 290285768 429669080 217874189 900839383 266304471 667995862 496518979 569710005 882575585 639066463 466723346 671318223 623491592 647756462 298968623 734718293 446794290 322680312 383728490 257028912 470480706 718297820 24517154 75509724 765930460 965862196 289642875 651837233 400614762 389670489 453318802 690900530 819339568 671192991 444256264 85644038 191705204 940775242 507870395 74280788 579841705 827110092 598115362 55849648 327382905 897083985 790567941 774177195 219764296 174296430 31206106 542761354 892594249 908239611 470787429 511041060 874101806 760430303 15394645 127232919 2617144 468713446 670649800 674473063 992422788 114906064 612633453 36644344 55681305 120503847 110925131 488039361 800130290 561556845 543889009 127513195 458640829 186973301 754206741 530921476 361269730 637929198 73682829 106380330 546168808 544470258 617421390 272786965 157416912 632816034 252536235 12550407 954045831 923186035 687023470 946468619 38092098 299656922 983112962 946289754 272677120 946554444 286845467 72807409 360627640 683250827 52836955 819268468 870224127 807043695 202706296 84010208 297489244 276389124 190390537 843658051 673375733 660328278 968961367 830792645 145660663 221497602 843343051 99706494 144683636 382882872 898691464 35292085 682539793 734320777 834098190 807733264 533391572 973460008 733057025 894019212 656710834 785893979 565804031 379451312 445454026 768510326 463461519 742943269 44899450 653852056 439117672 570791534 166696685 260595390 254100530 312357348 482092991 97443581 412063841 479292978 332842804 163271656 367101414 15382597 897592432 53715956 675632212 430984003 27175963 408689236 177519566 536403149 47099567 743323597 915854460 345069944 511833922 231832331 88013212 409249723 885684386 379647235 980041257 52381070 640242625 86658138 217254769 974851967 36618070 629318609 306661297 369460874 792590264 673762710 237359822 542699047 579995017 912992033 973683050 459687332 174197621 3718967 996090480 221297187 747042563 764461291 566367130 111392837 996293621 506896693 520642559 734494358 739060280 353200167 639391780 231819256 439858305 856646548 206671222 476476374 338481509 513332518 845937247 983588124 39611580 83297068 526287171 619606596 848805453 352486572 79293927 23003073 356205538 927900758 96816611 103248101 544878401 663183740 67157289 393688373 22596784 587799847 980699083 761657063 793516366 472607214 993476318 85891022 181770113 52663892 562367395 520251621 418512761 260820994 356356097 458124340 196634413 882643267 930247288 45439865 87646190 862057566 920959289 296368079 642474676 17775899 252132531 39869428 533475990 319289819 433557800 556072774 907089666 266773234 170246188 553122383 739380447 16238858 639013404 921150560 68902749 53897150 293918532 339931861 314718143 650274628 798056201 363868908 385434246 580819840 261825124 473080435 442877405 182784413 769448514 85352080 53076663 21581044 125221507 586552653 193387215 411295659 142625426 100476880 678068892 165387965 506115614 269965691 34143174 145129017 191116250 103045922 199026166 485034781 295494135 366260661 135309409 93550335 730129568 373260006 526886526 991954691 846340441 969763930 27255455 468305306 907632362 80332118 342402701 885370220 666884770 535789915 149182230 662026547 488783146 679767474 827414511 994898759 949733164 861557685 992544127 140849413 817119958 44086645 478400545 112614092 410347305 466226305 58680778 140476872 839486311 438083655 132431562 538343103 260363937 12203369 859164760 20512650 92535486 54083812 905882869 759420255 589873727 907581451 421446801 931173224 587348924 101377663 778588335 389598439 815451699 771132461 382964203 485088009 815219105 861364747 450218452 78082761 180107404 361415582 218559632 872110066 799499236 203507546 262969520 59863172 215710914 122134279 80375821 308246399 176218090 838775042 67666653 618608168 746356492 341629805 549781392 186221767 295523819 180886078 575820205 110975518 952018538 958784407 596063526 619753995 672665505 46281977 697836755 705289260 260213910 768912739 577399325 59713146 972420284 840368844 119576317 40647549 815019474 52468490 201410299 991237564 891243531 121593303 462362083 490116374 463223107 12143474 528854492 758746925 45545903 104674696 722238794 997564441 915975454 170818671 469834787 441157310 69617000 20187893 146446570 329830909 789100631 576362246 389544054 614037266 269247442 361636723 507201166 84266915 266621564 708611464 928020830 10381446 830204766 242899265 500497819 145944224 107559090 29352310 904691149 153104993 986543357 479446294 3185785 755035162 650264965 473020571 48708823 719881964 345724815 47671744 49712872 134825446 476550342 291773278 601379063 745797783 653410000 108580229 682581049 920031563 669708044 463118231 930413008 499912810 706017495 283427178 645857033 813576584 165295839 403064533 966681576 4355547 882510827 969867360 611907060 385292143 295404282 660615882 105174106 641129097 560803978 7403329 628470894 37354319 299176606 82366308 635668453 952586605 43462888 170765853 725134519 713170932 633884083 508063878 65600093 192417929 644007407 563973477 858510865 809303245 967038010 677708792 666175143 702065188 500092504 278082202 87357330 795496785 791214436 45047787 289142233 352018413 52451115 770129478 241889083 351627721 852495786 877557535 156730677 748475025 48323387 734381548 314162308 534723822 94961777 379762400 727141750 738969184 943735877 438168966 400788780 763290238 115877758 66963923 317871777 615970261 197562476 257745458 263983397 988776911 155309596 405641982 193311675 207760710 175771459 435200757 411904782 880783596 312758291 568635459 629258621 213598030 155533358 943420928 748321851 250495134 175699680 327979952 989464317 971951908 766148918 390253097 587758497 882026675 309733371 905630273 350513287 507295846 15892082 467013035 496072757 171201677 872655016 689384431 231478738 48426475 124585188 643383520 781726422 289859830 64535330 263501394 503457859 220068687 59438674 104296061 470563820 235138353 432276013 460028137 59606612 198424930 702797585 647365108 932967956 12530955 405511732 135997594 519826800 421403813 603010628 868415908 445121841 475665644 410316691 676600578 376608470 387418230 319984097 10851243 677278059 384519426 274352637 33252270 604588112 333791310 137548330 75151932 568929662 569824342 387696420 628536273 620765623 90494004 128417732 553733578 955541310 533929463 689731171 327884461 955333275 145258151 196300369 252971467 620923794 606617059 929572044 850048615 994035288 102072493 860899857 523829698 486591918 135252493 409598319 943696382 469043802 547146649 871364665 890489815 969487342 111577436 371542439 590252965 54587791 499960170 996502894 10129100 33889632 538750417 338013560 841739258 684008567 386830280 94710724 157448712 993447338 24282768 7497326 839998977 126355260 868397182 216345027 465463529 856166027 625943345 261676262 177726180 25606345 133040926 68215995 995093687 244618361 439758433 437863003 299206151 939718603 286882248 161851602 826124586 825632664 499865162 667863844 509641230 886695441 615090919 667089941 732659131 491890038 527103618 425174459 470761649 248017152 494035837 936225178 104183178 119979182 50417791 281909357 998101878 183458717 202641703 845711916 280593429 642400136 136091270 579799580 434635090 422973518 741651181 113276027 248606181 94032694 781139870 610763763 833244487 248747141 130370055 418419969 740637178 657473673 843594427 211398827 905490824 190146616 140356 9674001 162642149 50558146 144099709 160744026 86533214 346741412 6455942 367126643 841657899 142547211 946926222 128809340 418037080 541093754 242085366 666643261 487642800 23225236 129923375 320887286 124488728 260293429 739307254 865125905 917767101 435418032 76524731 823257924 625564647 929181438 685448276 788206795 979739584 682064337 801467173 66272797 28805748 660439466 285915791 722979998 655503028 85358364 851789337 73540108 626452118 93874702 592699720 114094917 969616289 722623094 287498554 94105016 982916522 879322159 959230921 900683623 167256542 888272003 576457898 792821189 669969793 114422526 433544335 502225728 796486862 87527859 421014876 677808961 747967324 706930667 253305310 403470352 792289030 105094646 329526811 271257499 51485699 922226530 237868767 21101988 644849623 525367320 115207003 480282496 257205830 926954275 233482470 424462372 667742630 809940368 69799912 190228774 776879245 503344246 692454501 425882458 590872105 113469376 103691418 191355780 820400042 209513079 594826131 465205424 314607724 924352941 736462922 366093422 699095822 974331689 239711761 196461796 352215360 207435116 676744292 609421190 134389390 910226761 33883561 654648371 572683480 103683472 844877144 349562724 459544069 389847996 775445181 50416173 503317372 731652950 94288305 176233765 941166028 689114435 641439188 108290103 465983728 230418462 326899877 17595901 204750150 566611637 214057697 556965509 774046752 890801988 18903050 760952494 801028748 52786610 268117216 226228580 8986433 112994360 575791303 468530502 355358707 203752836 371463026 858676078 787922137 465751330 887426195 581604517 7382117 381381734 689894619 473365844 611800195 16794495 490961744 816550344 435922484 705019440 226032205 209969235 448337779 244935254 970921728 101882879 150238216 91555296 328111458 159224648 57066007 903902760 627755149 412424713 960171947 999218175 123617143 748094084 464969504 11043337 182214952 472351620 392425070 872109570 798233815 4225265 741420417 141711911 673291960 29859252