11451 206699361 976931801 926492984 408577656 154614707 177120151 161816695 899977159 623724412 921796714 388133241 608696375 572446055 741470440 457476191 251265269 392106411 947126199 549317259 676220360 562476427 829564313 434639184 463250917 132604176 123326788 966593016 413638103 96320861 946478946 944380290 622521346 460161412 925018057 88981801 311146797 447206631 197182143 21542495 738722140 311861509 814621129 560949956 316097494 600847565 490000571 403384607 321300413 597112472 231376573 391610208 53698192 640428421 342488568 714580919 497019270 365640636 246542081 868552113 193048371 400400552 530879760 221764081 68556799 734363237 718640642 611906234 620691530 91064125 443429351 963833568 992888103 845975200 815062032 494194506 449102182 167127867 84863065 142258506 522800566 413179930 445724988 142468356 764503881 708589892 68748204 314761473 166000407 862404829 692357299 935766147 639484986 69718900 258350216 778100573 38767523 41630308 662486445 252743027 93369021 232425204 295618197 296145260 635365690 504051952 465253180 247155894 294821656 433607029 128418389 323520590 686200368 760742840 51469082 672945077 413579452 800858382 959749368 517221606 295142216 105951117 188780190 556839116 829185207 63704528 716001989 677621763 695516091 859808624 893518665 555520886 50385106 619897146 89497784 888274586 904733959 764158273 547803159 589564246 146563645 586810411 965206006 181280960 251768845 755087995 976709556 838904151 741868796 363339220 765983335 308184986 22636365 789995896 389868818 485319478 509806836 540180694 296509182 1764844 27179990 895626395 245940235 474465672 250496667 7529347 260870223 300541981 959365025 431639022 738637538 805608751 763403819 390544739 58144028 911096549 975105209 613442539 383124174 858071076 471182190 15712832 966716928 144925205 389822045 402048611 288067676 696763436 429219164 291362105 71604621 797848988 71149993 93607235 136368214 837598609 83799914 198427898 131636541 793584319 315259813 127425278 152514868 5167181 710211031 587240832 183164242 272634476 508233524 148054333 637893001 343882292 107490311 286767160 710208710 921397421 563699896 321997099 840361664 918525499 406989147 703166749 634608343 856185638 989111496 193811047 624540230 281992633 887973761 79932227 116962063 997911918 580500782 463424506 242003457 412924727 192113421 784812516 141267343 245580470 617172424 141631512 393142968 628400380 989827829 249074283 725125725 65992703 920663193 103529276 626633161 165397887 914947262 425410308 297810817 905729695 464559923 760702597 233089684 148018788 680813051 644898938 695372889 390895174 101331816 808638845 393922498 711868387 134051273 158076313 974318930 734171698 104934542 899352668 541021544 607187673 150649152 264366250 159035056 150096269 357451185 436412067 55933126 515779352 142293959 664168919 283071313 28667085 151678763 384878164 222234931 896410464 160625578 661763572 822598649 474840988 744898605 19292594 30141383 762411742 532938533 771823243 551636010 259477670 204254257 858268110 77757889 52276905 546801664 942406324 112252613 187665638 840549813 168108944 364881784 364825623 304759010 296796680 871016537 352995658 607591203 43031469 999217136 757402323 903034097 122889597 507714880 351310210 852680409 931167617 252878540 498007584 817828194 866853933 397188295 293231926 834702962 582837893 795368573 147859431 923130323 58960331 435975645 416018716 841374069 906171043 697534109 111860980 136214573 526734229 216075214 935762905 425540472 797942449 739683589 567574081 225786683 470568989 717741301 213808605 334603511 566934977 694149670 54107404 633489991 822326912 583271770 885947576 766712278 159830628 714606070 512064946 488747066 160625060 75704400 116591610 142663617 179967010 729553390 104434044 73535111 903057035 524429256 133916008 156279846 997771489 318187481 62786902 180102987 383379903 264013210 301316672 185512563 747941995 970092235 651911984 712336489 30536468 119051284 248490447 307498860 655659975 136752025 274281060 926202294 606035811 597537520 138929316 203550867 619921111 432310830 853411455 216103073 181939787 227289882 839508217 162512194 684140845 280600871 437959224 219371492 756725118 720154638 584318652 206959014 77996428 828267720 286882771 554926159 902477309 291153313 896276019 168765954 355421220 657269612 438720348 646234092 92352300 80054698 876112526 443989332 374298322 420067496 262705871 546531427 673007633 688139154 641187882 132689217 587320411 421377781 66422700 600980927 578595792 233526406 637012419 777852938 490708298 47174236 912229483 935793713 824214397 698927684 994563298 22193922 856347741 110353244 697699541 605540531 235145834 516832107 888597702 597203035 3154443 449771445 728381408 826404566 256798390 367737222 648767817 44631615 61731217 189483226 59344760 464465881 713968200 14689090 591875115 309612548 148417756 232957862 279512146 360400184 394538897 288056648 847465561 854725945 30913885 432846899 294204855 380925403 312769417 65222221 733778838 628019748 592200540 629744790 330655898 250628389 30299105 419896044 982378330 395615119 827012553 51626406 258149446 93071069 583173420 27702507 490247239 359645995 525563215 424294698 173556484 163619508 333608351 984868174 360280733 861790005 371583455 279845026 403583451 227612036 585355201 85141595 53248505 445008659 146699283 40648926 52073551 104845330 643994131 918792611 919851377 850410370 27283877 210195961 471030644 689263389 81349298 476537198 911934495 84249173 484758200 697223160 675556553 479529799 674305215 414013356 780743501 580245070 273000426 993488440 996274854 215484563 51082399 241234775 676822528 765739840 184069088 84042603 419264666 193270091 762002220 804579633 964400606 569753486 272014930 666942680 60521449 78849268 68734337 474803763 38528170 436504145 941609616 876932890 804775229 110752070 990448925 145345197 338518388 68547324 124531302 145509405 654442749 708540138 34704975 649618499 657362560 704322832 555340493 642114003 390717652 393632880 467843703 6542657 183436205 393627269 949706953 40886908 803753504 148777462 493980646 512319626 428549950 898725553 407795002 937627659 876901990 746618907 527675260 485238226 525637616 84990510 631785071 18767547 751371250 31070498 25869369 769313616 22185145 711681782 789716827 317671364 309798964 320714073 71936615 124191940 173619789 459872979 806014632 286733342 359115980 140945846 341557696 812921873 57672754 488465645 690159621 587316189 243852180 264601540 664251588 309987361 443755115 847577192 927145212 436483289 246098614 346497182 149942175 74473427 490781451 691155183 241128423 756151695 494541555 572227006 640318992 981265596 349016391 810738691 652417347 894532200 764653385 917276018 270097609 510008840 70259533 72649120 142283910 105912824 125751988 559508537 406621240 446844004 987636919 585115824 23364814 863277637 521004272 40349590 585325493 804501354 426665956 795078156 114308865 229756141 406747572 602971339 242158119 712933421 479468320 604390027 772882501 226055878 538620118 637774076 223101158 74896343 955079726 9572937 41042704 852098687 243341826 491174238 599295719 837682303 681215553 524697803 440567742 622154550 734632142 43608382 598364496 876770355 442617906 289037680 113444076 503076159 402064519 714424343 457689821 748774207 197010276 302360548 153074218 558556043 110393422 599232467 724059876 514054117 901798191 412652814 442232105 269961305 239404003 690482025 249134172 602728167 410545578 254825691 252552866 741750356 765969275 474239836 239277223 529526837 318613133 465877162 149179826 479023758 578275246 767061258 31408404 295911800 811130549 732676003 102477131 150156321 977990343 342267371 503720133 757458033 592622601 661377458 305290498 973785492 114082736 90106314 165196706 540671012 755582748 53291689 577265105 139277864 235210178 963238240 845471745 813701496 375690035 251469787 745724673 301368276 733882652 812892872 721100160 259262810 224135812 304247816 68395015 6132883 861843488 458508183 711363091 946982534 927332978 369656805 591172893 12652539 911366744 26109529 150367967 348000383 419796142 249313471 746832865 708946613 176277339 366422135 111421691 638536367 124933398 359249987 899601532 792429199 42589616 240077007 674115035 279044738 2012787 977677910 428089904 223086422 245498446 227437829 508858427 620063344 104950765 151618262 456246877 744330423 877961070 171964845 507357655 622894474 894110388 776751114 651106946 38350845 399113464 130323255 103970752 814117909 769252461 18193405 137113808 797075633 648214163 722209715 774435324 601076597 750733563 575167175 806608731 287824076 316160477 490377209 4397387 903856840 618707167 417898383 308660389 91301789 699948570 501528821 919404836 745153036 148376157 519034774 939202344 803217844 503912626 228096905 721184872 278246356 238729157 808993715 776668019 813874124 474066805 267713474 534479812 715865102 702489141 467314671 193374756 203902609 203300578 126821940 890018155 362277544 647178699 823823494 459851006 681851094 982459300 176208178 275603302 900273095 136611706 851715816 154955102 982308282 595351022 802008643 298344542 263697997 575600014 11074474 958366266 725970391 721650748 799225649 958093461 770202696 910565584 871723122 849762321 288240096 917576552 240706052 223689964 807414359 290948082 600122051 495336768 253801872 481581018 312672726 884937447 526803195 31748055 593843636 613262449 733398883 819021336 90747630 288610149 973618539 267928979 69708269 91034337 99872409 873436876 575615461 532254657 452616577 462776716 139285476 107528985 626335630 752335987 227167030 805739404 642256747 984441913 575434551 382111632 642093668 772232255 65701598 832619665 246634081 329683158 792538628 932930799 494445067 140219122 150783763 592221624 790810414 179211031 636442403 669376335 926527807 690207442 805293964 509607890 755372444 596027552 180365181 966071323 570482566 820296904 67913673 673440370 522559985 673029119 947346492 597966375 234238681 62728924 56540596 3050721 781955388 278159136 262791374 776083331 444908495 204051351 916564809 80121777 126573742 560106310 817089389 695263389 402819291 251174223 805431547 271862197 99688384 117038609 294533800 492289476 904547773 848588337 505291415 33627095 769090910 585938101 253054293 145610420 629730279 339708339 297963687 278323413 351206361 425436755 962181801 809035836 931020668 293021362 34670047 722543693 207253223 359271477 858539559 484503432 76614129 539876473 978106937 749678031 604102350 657624412 710593604 58003846 422621514 917515019 649505630 799335713 1347203 501976886 665598538 927148115 297095277 38909551 428089179 275161438 484957870 407963652 216675658 261209161 982482492 509481553 727943731 835736599 322471898 49276787 569904565 794927770 876812260 327669849 191087968 302095131 109145424 250932966 960409192 322390374 168815677 863661643 179194481 190191730 467202513 94637654 506127946 589586088 16812538 274182195 76445509 694257117 11065623 517279057 27770847 666098509 872443668 601593964 918598526 242113014 119465936 710431600 750417102 869527629 965785424 686747383 851034880 859665447 661532430 868787325 242296814 214761909 132063015 705315716 775874357 277871782 192527778 294493623 756486114 30527945 136163082 450056819 796737810 324738264 366808110 836004440 817607608 95176209 550045363 28817486 90948772 398839734 221084805 467838868 263793063 450108811 302652334 256305871 873132058 669307208 728514032 246831060 489538240 769266694 183324721 167326571 519264743 847016600 53483881 131622988 651473699 685955540 349056012 317168408 119014584 757853266 622185017 779975638 382469217 108569551 68322093 149492285 57978808 804002931 84473945 530909495 610390966 346704256 557805691 540979018 242254270 773715113 816491892 318482307 616029975 98907706 672927546 692355778 459476458 66422642 285255992 215812147 917520517 548873946 796150250 307171930 25800347 118521581 503662435 951974376 529938213 716552095 921741937 308182007 878848637 56660683 374578560 728742376 339710609 323171138 811583000 79759420 186687988 389863112 893009763 802682054 204133501 896823511 373344675 216197945 166570573 867649455 285159591 718546048 897147653 428698576 136202078 688281449 418032692 217332840 889490673 315435999 375345453 55888896 101435474 131180618 875465010 375450391 341556791 802712932 404489202 61103613 249306275 443158304 851985775 308660653 99452000 617476510 406407596 501823549 663689201 612258939 750209242 19465393 437613328 957395234 983847295 23770613 946035388 27595839 47701324 688871582 367418669 831762981 831153440 290407819 911042954 108840254 227467487 334037812 260731871 898987956 757451032 19620844 928550361 130979640 182543895 131690589 570806028 884725910 336856320 831058443 391724324 663300751 203493619 114276681 900593685 803561696 993413810 503678681 724388994 339260179 730949649 111217901 817473729 526172224 714843019 883824988 646484090 300152918 852277592 53496001 711855221 412023900 508296580 262664852 223528721 718026418 48822402 305914178 364761657 658040923 133263743 695239277 18690874 287111201 256087222 588448855 283536370 44944324 800348296 128449247 608007522 713487863 659529686 478867242 31680001 718424622 701615996 88850566 834950376 45456371 282566809 942237614 304846762 187447291 217525476 208163478 722634636 82403374 547802420 893380030 180513016 192364327 204110174 841607534 885915678 876866369 436951985 169760204 367325042 912866817 967537534 827118067 660114887 441049050 250942617 439137185 297445789 12066941 929271638 583910767 211310694 205163854 104822715 800324563 661487789 4971189 347463421 521239141 458296831 672316604 589806053 983707013 187558505 386685525 356152159 379210078 312342959 657095481 99530883 36152606 785627186 149955558 968614636 101214681 802088456 775146414 848377597 668121593 486759520 13022706 35307859 969964194 573068001 772395083 537897345 179825613 857666406 769931516 582199248 670831652 797133057 576204233 812143514 249559980 664840492 204521460 677597398 69738519 586231210 883460338 375655844 615376252 637984279 267090187 178097606 357155305 814246589 282280053 677539555 298137784 83855530 300123192 232177485 77906201 88023604 844270730 972495407 613207355 800658829 761268757 546062844 283917921 943995485 72618089 275488757 582785181 569015176 177214021 374076502 739072728 905574107 771342679 35940079 483563900 946629118 146961639 865947315 244622568 422029680 85195522 508972079 890904526 377138007 268936307 697701747 394869529 13579539 317456298 228843706 359860316 516312181 723073169 170543960 559383366 473527475 868549207 894846491 768406453 168654787 930715023 628606551 548644227 164474115 900435154 549357766 709568282 628715008 705945675 285229809 757749052 663980476 685326060 776794881 861046517 990620995 24609366 474946836 130371471 554053458 924172371 78683928 877050792 239980482 972301428 626298892 717304385 946724636 242530286 153889612 770132672 142458885 755929846 915303646 155253544 32763065 548603518 482135067 276169084 136712381 344920400 744711621 644855751 871100008 272340125 429098453 83124693 572685000 773453411 963721291 146540905 513113493 471967578 311197391 586334310 393873529 962237798 950395474 855521152 24413426 220087822 588355831 96297854 49798101 945436318 832922252 736579472 950773050 176300083 333835785 270266944 858980131 212609031 422579211 51179017 282919653 832978737 191566485 187080099 445150177 659018542 47746164 719628673 804098124 790950815 747370199 396532846 477205223 789392253 540829324 3438684 584924958 244420456 666453795 269712650 914505748 345740658 516571729 975623549 588358610 466445098 549194211 376676193 688857874 186742036 650552719 886424862 790022281 356130442 834577768 785042449 266861468 856277332 89853706 242375852 398425161 300879722 151586410 556400130 437460200 949958763 450101481 655252581 754225148 531756399 248991280 148002716 516751739 395486088 42191553 413573699 721157291 423829383 880887730 77174118 454373724 973330444 133321284 636104643 27420750 599084271 353736466 388926525 326489184 62350374 424834932 212385604 751001244 646099096 910957354 291412255 723565215 960430827 983050630 836304642 648573726 439756599 229038094 232573321 217877806 904645836 969117688 234926561 796364727 535192469 573914924 54751029 155142141 591805639 676484527 335242327 33865811 741258856 492335663 785015930 833522222 158572167 701073777 500971181 162345813 893891335 163473409 1798787 43640091 473723430 459725390 151077396 200659585 8516712 163420720 236910788 190398719 14290929 585410727 361360180 932163402 735277814 706557438 331076945 951906732 906281095 101653921 987585156 826314767 703408716 22576880 368286446 119371446 655471749 145497970 60607287 806657798 575074449 495241478 69349811 286965067 985658265 228832311 461234637 8734146 607697646 121985026 342162923 134588189 750890285 494057731 757146656 983771322 758204031 961801981 127527708 645850045 303435050 972068790 778213506 499221208 467891709 345915074 876973379 293769047 160492756 758200954 107710598 888065684 638057398 557045471 95029322 792742764 869865949 406838352 268419987 2412646 79928184 987291714 798151891 518256069 759974993 864507433 207109427 408100796 71997863 447004119 688200694 449900422 504790844 764283153 243462710 725338774 525559504 961733081 120343032 49160073 832145212 754038496 101563602 277557762 733349009 137387145 379538610 167155397 66865725 249212543 915175316 215621223 933880707 422548646 267321246 137737986 143495713 37298105 182711563 395870448 307839087 794480230 756008163 932298642 653224650 112458498 158915459 668331599 164481863 243095366 332875278 215605392 448347274 665956860 527074342 191386892 191323465 53332368 651277222 23439149 840166272 83469277 351796744 824190437 519279903 363027162 531166186 457446311 59373158 156046608 83579511 714819895 880428242 74165855 154740490 9798203 905596257 241964287 51963279 612414333 26915028 55328301 771621358 281874864 22263501 413716460 236662892 770759369 624180173 261655595 88543160 237367700 686075053 394005569 672599259 248875769 818781004 681193227 702649497 592039384 894684977 985646159 811698437 99019831 873711262 104505281 999125421 9591772 134939565 267352121 212269286 413378460 436809568 643261237 347503903 118586973 293778496 675195978 606088445 683440386 826248395 839944734 700099487 655666761 471071682 880734167 22902960 19398738 797891018 444826856 374127856 155596900 769234238 743426983 593318726 194076333 141732210 765357593 362355659 416424226 778156460 628077525 359941584 815298539 796582695 26791339 432040477 52648984 121510170 961353165 607331239 455270456 356750197 480741291 982553286 937192521 731307298 160680563 951070568 697423684 900464626 258201610 598718057 556206755 921508980 402676872 576066852 7743114 630319631 903892520 772767065 275671968 991588887 348582961 31635620 153892734 430329766 424216578 446470137 577475255 93041634 300560005 456871083 92871892 39060962 31310882 51070162 779740965 256973926 470671266 896407604 865632497 393527260 576859853 276720983 325503275 907394104 505931484 117686094 812817237 594272308 416936072 934382131 677331030 731645199 425695953 379459319 530003938 249709763 291029216 680897874 203856119 565538794 716070403 87751846 726562458 794621095 941006775 87377390 660263925 140040970 686951804 51637734 464194405 605765365 615765868 730411302 922347472 714048074 240904945 843845471 191419067 783312958 594879414 787008871 709678364 43902137 608746590 490507945 112357888 186721975 621051576 413681267 284806937 177827197 338812299 437918071 45093827 16794270 361978579 739431187 690907088 902232797 24564034 700870545 927496507 273770250 413592873 765950729 934928176 966042050 670601633 83229665 808527793 352740011 54521416 732880226 103412788 789491135 207350541 860604926 825774543 567207981 835926822 205221504 198037638 900972622 261515232 30715418 572292972 322096869 34245132 413216652 33060170 393666739 700892356 874980195 607667018 134659115 277273344 872591546 130394115 361212837 860652218 150810157 987482801 794106624 319371261 252462229 242707386 148540040 50419719 599630637 131143356 684626588 101068083 947921915 746476946 81865970 298656813 328048302 470515457 183341537 999967321 871256813 398139030 120976951 711378451 440910976 16450828 62903671 919377144 711358080 859241302 493638475 224117234 569063522 345627971 265823932 991030375 496434162 83487274 452279157 82417275 914051892 214575454 584135362 909353689 366669933 789351803 545606858 386037073 753036022 196434521 416148734 607786119 877038995 234050561 867859641 335406904 823124187 328399082 232053806 145208787 478575080 334076746 995267119 460987391 544080488 24642877 313140363 681010995 771159387 346377405 739610315 711246018 524032734 51885019 247029130 154983207 6843694 642674144 187372821 80496689 999535605 855255617 320482515 888341415 479132173 280725973 175097774 799769212 299109959 178903003 239184798 102526223 874404182 451729144 318632762 615547331 680075586 413976109 301625946 155004552 787872902 840600025 547551211 795869900 349094516 366694705 156539118 369788421 174491978 790987854 337791566 859258152 910719845 587654009 658468788 271622796 508326276 836948455 535979061 545214133 409704106 797324011 10395052 476940361 320949240 127847238 261312240 348324371 237221597 909056288 390315460 291561572 495965203 173490300 891570189 130384998 787753642 916326612 340666033 226093726 128398616 947334580 635467393 794024334 686513231 409623209 469836679 327939699 93378146 215748260 16223667 251895739 428901563 35179888 1273321 592461707 848431750 232152124 318227075 931450793 846928061 681674971 92940314 940500517 525708957 284324070 870403583 134347728 245508787 135085759 115811909 921690586 795431016 810037253 72996645 6368541 245220736 689288050 491812129 555954832 208012568 537309836 309723997 713039441 320532398 628779725 894992373 426357290 98591093 477988186 416717730 276160941 374091123 474128830 691519981 274279328 356461165 921192984 38478698 684207425 683876876 637764126 659010723 84858977 105554035 139252393 927535907 740410812 539390610 405957751 530220520 510841218 600501085 444389939 217473020 526407304 939787214 3450617 86436756 102091881 421317337 449667069 329275972 248188236 383102506 656129750 975348659 971320526 238819920 742930764 240257287 834577001 717846636 134268599 678874200 867664040 351095078 695284879 330768701 326894714 341217779 292500700 310297985 595916488 663646395 990094209 840941368 720736085 196182741 854408581 4394766 753705534 439245325 270139271 980844732 451976250 210260734 23772711 386057565 687777522 619452385 902288361 214604187 183841862 256078499 968225424 895618669 832864426 731274641 689768594 568266886 385507839 156870780 175197952 570026404 568055354 79235677 282164684 660659478 149043260 2930077 354716944 80564357 131414926 232425176 598887762 136833577 746764136 180588548 116062939 25930271 386045340 658978721 857391038 615995501 35398859 217403864 563571049 814735758 322075262 685822726 72800434 681870715 238157366 989252094 819725122 455611281 482437460 64755272 20203433 576787391 251569813 763024900 348438092 941802721 554691316 206719860 476609671 12743219 297527156 27835805 650023422 29430517 86550226 350606346 593923343 24553082 624404682 93068517 216457383 748084989 387943665 794994818 650223504 136079185 220386117 560746482 912553631 492104021 164608176 144857115 518253912 840591577 947255624 96519685 451551944 314893719 508038523 114897939 102730835 940006840 879350285 997332717 713344897 191023519 517574752 349031067 961950516 665712809 854383542 156862159 791328851 99393175 878547802 545374589 49235832 823579873 25365271 100058533 376469903 178205221 225440003 429225797 493876090 348089988 71495801 177399693 314812855 190992394 729046972 163801891 726022466 686790785 819661387 189439915 364595751 188766415 10303813 331565737 982854951 601322922 116843928 915125021 604588004 496794083 861930950 93662098 263039413 780043570 81813207 757873052 268886815 563403784 444077478 449517272 833345094 500453798 139598326 49283995 264359561 873164000 868643736 917351493 151903204 2099766 134257656 800862484 51893371 650263920 259630980 848140665 93192152 798554524 748750800 348502274 542339873 133430223 712731309 784120127 815203707 562133306 932881904 537394429 893992808 653103026 81375448 234153109 227757052 18254091 977977270 770976066 215970288 802558996 67754292 642785023 772708025 4841013 423406150 114001688 569759842 483316167 252951984 875259355 79328802 592416557 843622714 629618713 332050143 133610834 695423313 506083382 587531857 840343049 952523108 830588082 290119124 287837904 738265265 130530764 208743177 96119198 52416562 740049337 604813092 30608820 492477628 648603295 797455295 908442324 57432166 105037192 385059528 317540488 146934873 411528172 543424353 919294042 704353261 916974417 285172475 832397426 732745269 982531493 226037477 516410393 806190033 885456407 19309023 880716797 7001278 772949004 256811076 786211983 987136964 316121658 555051485 751171846 383845281 470848934 429230970 223700988 68328389 738786201 733458961 11799276 548511426 623846592 474473640 688374265 259809014 428566257 972075418 157777636 867280691 808317510 143571786 407104717 270539992 913587258 281404333 697844351 182904988 921437536 702477635 170765122 738959734 117466513 582926775 808699460 225303657 891310795 365906135 229898624 701906782 310189770 136283591 349382016 22889797 680383351 939656613 573441179 780591755 655331308 635641683 695876978 668658664 641504807 509323530 445660156 691168092 575506816 35504239 214296272 897819585 799739016 136717376 510484092 369029988 704632224 541030483 613994625 451664634 175776016 973620660 546018544 468007365 499195236 242903770 972373964 396170615 601078501 257187469 92929760 145986847 723483182 770842996 814434695 888080866 886347985 98347726 452131474 129228565 933799819 503129324 43039161 803717300 880282769 382337531 563670192 968835331 727821156 12398189 500576538 203374357 10886405 866032209 526477765 618929022 694869442 793322316 170912580 622679327 107701358 312680483 655042102 620417417 235202770 609204994 277765425 54380261 281751411 665406980 82587796 389839545 244989290 927533456 519524221 741188050 901373775 306430304 139854851 224015471 828242906 400080312 263138425 660871865 92180695 845894400 625814151 904994128 635780260 903638656 510593615 548301414 271917058 236839057 119768936 422697391 451266127 668365715 776467886 135244608 299859856 396984288 674521181 940499399 836125465 94783558 523429923 863189032 290274426 583428266 982882901 148419613 128241865 496542441 931187946 284086974 196766098 971391296 256767837 807545994 101250770 848888274 929884715 599726979 48363219 241023848 110534774 543537279 165330229 498847207 155478434 289853177 684183555 146770342 967517889 673147368 173751744 9831280 208459489 313589185 353123394 289938974 60433950 949545887 592579784 457748149 512569775 56184139 413567536 826877968 314694063 615557858 728383087 549817230 231152964 158884225 158651438 468166593 578888132 838627826 791877794 806360846 456295649 6026894 153042530 790682321 844415615 574872220 758561029 549591450 976369874 342932573 957972141 430344058 194769325 297597030 999782159 551674793 48024092 207276384 605923888 249898415 166166372 532528945 447674381 873585636 60242589 22640418 24919999 773938759 588069388 875061550 940358351 775322541 992484422 831841626 78558855 958265170 168431518 142355203 422159843 38660521 350094054 5802744 25297572 247900858 490785133 752291109 982938800 179994697 678377297 911350217 800627578 866399191 838307281 804109148 130270360 709959983 96194951 113156819 179193798 773668117 991073613 483063361 685735100 790803865 851721084 137590436 635305344 194239901 900154148 365150194 458870845 196811905 66411307 715661266 213408684 92658860 652237484 89221511 188027693 216766262 691018853 132320557 225619764 953143188 474747199 348694319 738578774 772584215 861466966 163778229 183851353 586911335 778191748 711376331 550518543 219705038 665868758 953714754 330442602 341467337 719109938 94186533 130924102 66997691 173160279 365657931 149525761 60349931 526954429 103899127 157256014 828664063 54441396 3940726 966967807 299082794 976858516 145746471 721981979 584145439 490725922 236018334 338988795 950523276 239183150 558238998 726245377 113272871 847849226 466500511 767423617 812348706 742230946 234866284 682388217 161286792 7735671 20916581 657161234 837756783 738667853 680990199 949606917 456825679 802664525 884078370 948029634 374236571 148907423 673139653 718618172 418473618 651332191 170159456 875754082 503245207 376682212 260521371 344855023 556000881 229576598 900718454 289217810 597022480 146167325 258020418 474727861 461277100 65941667 771957333 716895383 469399095 263564941 610583538 893171022 200047610 236034058 725849424 812435346 784039295 72920331 259253154 688394853 427843727 221643906 515731777 717564903 704795304 154755727 162123790 181759895 974781512 64660346 622613202 386793986 13293575 758403118 88739478 916161150 612545140 638407036 256659301 972014305 863176056 35669906 730173981 610632714 200225322 959379257 183066768 519715554 755073234 518394573 894118661 535601444 947311672 982969447 579277361 25999414 566661866 935138331 341197100 442962618 203897876 275804552 742244778 990134937 220898330 261489908 694503567 868454238 344840288 221407120 278769444 172573483 364819178 470036428 134321142 598555569 234867638 693871788 370953754 477091697 493085736 958217748 632243457 674906384 429104696 713500649 52012698 53879103 220368749 128757411 221576771 891722881 733610373 810342301 13198435 62136560 199628042 289703425 158798825 113416454 244918365 283343962 42525975 447573124 291798982 881884511 88987655 732368794 579060052 246620347 722854287 196989020 243608428 58855049 572622966 682514243 612770964 510187625 227285061 811290350 655328688 578731094 25621744 72248878 711792171 195836181 120248670 791038387 104304688 506388788 103338515 629619466 570332108 671896385 193393440 62911450 143895697 710373581 296136339 61344601 328023154 256321248 47462278 524136541 897685794 891128622 105971653 879621012 377133590 168847529 789539362 678293278 886859330 401755310 826191866 893450288 52877127 72532051 127203162 260834692 19484682 272481761 177052177 289467830 607979926 177019884 774638968 171801937 308156195 134882906 348194058 189594050 63501664 696050810 147808852 49845623 352674728 291836269 649313382 598845432 472412535 177162366 980229740 838148211 250959387 653794364 719029033 733198739 83539575 415886810 127605086 399462088 328316919 883180739 492515720 440092659 305295525 171031765 689495016 989465969 394972331 989621125 710419781 299481406 640177261 860469431 94172323 537226068 831495083 460701020 666047581 600842221 795726992 66568318 683940698 560730732 282063287 563380341 2316877 376624608 504635862 164375200 149687212 609311975 176347245 603552962 123921683 951652363 336031899 522046734 892433826 739405178 110802657 477629647 68473271 897920526 991021761 255801405 255798304 648464505 643838329 919716416 719424297 975710924 599105153 43428691 247061939 98868961 691110369 525203790 27259095 693693865 729365294 813325555 709197262 77024226 905660816 403977779 967052913 221541267 72620501 148410238 381746085 476128210 918889039 695640087 809615090 616614789 748337987 800528404 698612373 326813374 346524962 939761864 248515073 522337759 110359320 249111537 55979373 937079269 593756054 353941432 575144419 469979830 564279641 472092969 356839965 832080791 239403190 207506378 606422988 869970110 149998340 44152256 697385507 110594042 562990211 154828669 430588323 224264140 481645537 366959205 758596371 275422657 160332164 450910683 630869194 778187931 721010918 819018077 512475632 25624551 980754353 80149100 585898174 39820105 634340713 98304280 568946597 776631646 817662676 891734691 317203466 36601748 662587776 590652402 729590409 650818806 38142709 220541097 364913819 736088556 923217354 580972783 864263200 244751501 87983406 484919797 91138044 451923098 392247893 739975123 86152561 314005603 258475571 364282630 941829837 836135886 981811224 687682719 611947565 510055348 778349474 785830251 7184522 874460356 89987656 571525748 901385810 77017803 380883547 71315911 285438204 4513414 826696101 386916716 693655064 165749119 714270504 243136777 50416195 118551780 96547326 461647859 919683159 207835897 804440223 953655206 88891490 428342651 869202242 883240628 357013008 484944321 256171712 558686763 150106373 965748831 694238381 51560262 906835563 620783734 112173518 80171662 87305264 803413503 473536641 237970066 190327428 501296381 547408955 147100091 726433580 675943056 623709331 90867654 843651967 798496364 650579807 139226118 612340355 816092156 756795316 250261580 273180542 965228128 583504777 975265527 156778523 521369052 767668226 589974861 495059403 55629724 503933231 493865828 495215951 618085893 366214060 300287561 592977440 878787905 864910187 878893841 511389166 595078525 868944906 70902133 216064751 961434705 360144279 372471266 463907966 134265399 579778721 684648356 539627933 274386847 293800152 11894368 385091583 267192458 926159035 512611528 667514432 657464107 748084210 805814873 197825335 189089642 600772356 479412755 795627212 166985829 387337815 502054505 661211188 758556273 236164377 100251262 824072941 946542831 543949711 524699571 818817603 32163417 806496703 7066056 662625279 337272448 277172356 982035009 796083893 126521563 501571254 104611771 435253604 112334660 891421712 518378998 866493259 186483029 703132077 235786237 899742787 871596167 374321728 578843133 768354196 692867698 342510409 553416936 35921457 630992291 4606538 968708129 339613994 611785170 474101889 147953775 353478248 610212005 472228559 360987853 634467953 264918114 816074876 321119675 173852140 794462967 341193350 88720202 914332922 964581455 210901470 563348042 691132053 293380606 477395841 507109937 286087839 686169592 940704881 421104074 287956033 274693580 280479195 863427355 569694355 776839829 838073401 493151273 306967434 431312580 966766413 179846617 254831351 200054392 272085663 419388181 9503966 442033247 623442093 625415578 672674708 130280063 76967961 362265931 879701397 372505429 148501578 685408337 658996885 689778357 825752218 795349405 885239920 382110774 962769877 381310658 434793835 143374016 509363930 987018162 920431573 158367671 178693202 997583700 752559645 431864393 829409237 109192522 229808755 598105836 646604078 28754002 574218482 574772243 904180343 325737704 133189203 720527916 996651716 840751692 912803497 149319790 414459076 509273613 718237326 335109413 273778653 799388384 109998344 475328096 701150580 937801813 503878879 661160109 703806794 703722315 932658475 625166782 641859723 495626780 657103034 235492623 390883295 693586067 346459416 104676772 863390737 791566527 884879430 772552536 814323153 68898824 51241877 747261161 62748396 51329773 917521284 26582039 276314022 527093887 214311100 321979528 875590685 920336783 431890301 455153245 940323420 17578119 775830004 18014263 141509830 448582115 640254000 388686286 485935891 306486792 495409515 617348775 232000004 194183910 855106453 460760901 545268228 9325424 994901346 312677527 997859303 684994226 105000431 301600820 800324676 31803038 762762811 860288571 846133236 22286256 764487414 658700798 82927552 199251962 515105718 116728320 126987899 28441814 976363168 16613650 213279598 959120436 260121152 504129005 568414430 291360627 816289085 869192033 602264234 218299039 180341331 551419350 257141544 661111115 703178266 371968959 120506306 575158486 771956171 565038815 363086592 335671893 159499100 356699157 898447307 818449869 153221979 367148584 748575639 892987282 745075001 716050438 86094383 948243423 674619685 830866646 86846126 554174378 344393155 165412688 184667598 394341799 408137620 344415583 810637340 463148162 459847270 359172030 761894131 806471447 612774160 325422608 918552083 983518998 984869741 213020875 257388066 415996361 127585991 779922705 739990731 320925445 961547104 414338081 507349665 567894796 778077528 727069055 459108417 147309709 921401000 835949772 120728371 681331944 667123347 429991766 735504761 514172367 767145691 34744264 884856794 99930932 158762026 47287195 331923149 454123543 784291696 317264977 237202670 386901920 46367141 200564407 63246358 266666870 261552011 116334747 930804305 901086418 671298385 829608407 182762914 409022391 284968341 464298914 409462863 535835300 158301108 955717617 317971034 76488594 184495212 71180575 551874218 288533631 735528366 632791001 607601 786781388 470986817 112711871 174965195 44419776 311629376 889446407 90776728 935055126 331808996 212132260 200132686 765876971 843578716 45864296 788656636 16972273 749468334 662026772 561816166 911005216 557162296 116478413 237511961 752626590 482829065 67206101 791484574 324159775 227228811 956672926 474845301 330215049 195305584 347581263 156094569 45643977 162158504 854861715 105681431 9873001 339873741 790813850 806967112 325544854 53625927 595846856 865772725 925844532 991528743 478606749 466680620 778072399 547665330 627758026 492493105 664715751 447602829 416014908 812595497 108900444 548120747 222094055 647159973 39061095 8116640 130284033 424459846 103726776 199234199 707724498 517528759 132777440 744852667 762183670 804888465 843724951 15378244 910620619 772546518 262442957 918107794 249918907 359478721 765291509 160496589 686119716 245901829 30199011 455351017 70831563 464541675 210821664 486817888 982827554 782495302 392854956 840150943 682284397 306537001 65202218 730053392 539575639 831118078 842569901 766045773 775062402 269407435 49884722 601242021 42535265 876642872 68416488 418822500 169369487 169381164 653489229 434763053 83908128 184734076 656793333 265454182 19903250 278903067 14411156 419670772 588196385 411884411 911893875 180316653 8524693 106210721 566098482 121453997 989113346 73839055 435560428 710009961 887250458 592628224 601025115 543909368 224556998 811431884 277316398 429356632 187239600 694910532 687915892 306105998 150783003 218199036 233369590 995419174 873421761 687098336 46597627 229811185 793431197 589113343 565368409 992541030 730031660 238266029 963656223 271158360 397463681 555288725 73941654 955438111 882351357 559789818 979793488 117931339 528391105 122832781 326394267 201968631 700879217 188615311 599423744 963592770 979375126 936015904 890141505 955049925 78547311 636107850 240551474 413873561 556850247 482418078 60974318 7399601 438452744 401700806 622218903 234313494 63419557 830577962 291361877 29159355 101147350 67981249 933131740 763456036 532797862 292175055 307324197 880894744 144485260 743379123 991055722 198398816 99337299 586796453 212177814 140667116 488087110 899950938 420861569 811408855 532635241 748751795 384164946 252410885 112192369 65902505 900218520 963738239 897897419 563708632 774599494 844328342 141716905 409833940 72714523 543406145 84904569 113463958 785733489 129063558 469109724 883682144 958249555 161959125 734529539 459510337 810832134 440139714 143089542 601686978 932942222 596175450 153904172 44197111 802641519 86802872 865781695 965185539 321805024 129159945 649822545 861898020 617404137 337736071 962769454 129880703 561620113 458047032 187151833 195163784 495823096 287675872 411638153 687982308 457182589 796673399 829367709 495228644 284267245 980915476 749428712 870902841 531722599 618887993 493639493 644105171 793469574 525916717 319491089 549172997 337668232 95052568 27929818 625011329 522150496 383104831 27899038 470495446 603155263 792037701 967144626 816696125 886305557 301284503 168668833 780063175 389986495 915631916 438517437 839662907 296206928 238374713 505063767 62127512 360836751 633478861 330233783 729471710 60578209 80039900 888213860 432394685 167604554 748064990 9754661 241938637 448932056 266456213 877945149 433661389 437232890 115128287 395050403 909444256 239987240 343378733 480042592 210995068 314384802 328578864 255686254 137089046 297998777 276406297 69998751 971735528 791634923 356557529 909273275 485590246 901857850 318045238 558021351 921760587 549768192 763216547 188063696 126135794 58977728 938942854 150411278 123305972 964143873 644281021 46431906 562848673 902206731 540889649 1968257 692099071 342621526 550034306 977352128 481398859 737530384 709790456 966988245 926784572 418114748 706180514 449685450 215940968 809215407 915897647 747310660 863018718 581299344 445639296 516425397 146703875 58907434 121400147 268839735 237750123 942384788 64095412 684366639 578296096 693557869 20504434 690824647 999458634 397843549 600620297 33510471 855248820 735336443 574139356 552687916 633682246 6614661 301093215 177953402 10363439 785944669 837623986 943389461 353038373 398773937 178353526 329912072 638075038 237455394 889069326 33462965 320537528 186399552 870441564 960470404 649646645 298818696 691960004 851672206 124831967 673968648 435870276 125102173 217022559 258160659 505794035 523999114 285057677 401338232 679525300 49105438 717613118 336357741 657301069 566142358 181129951 336387770 838431267 855398554 74193024 256461764 157077666 195450737 796150280 956825765 500540691 720337956 217169605 126654860 863936117 741277846 409592470 938181495 699665861 289351276 98221745 153836559 87750960 711531552 62543906 416821573 152014767 671614804 827765411 731465787 650879600 411078286 54830593 812805196 504825184 870144955 326023224 735525769 686745480 157235637 288803346 415267214 964754055 476526221 582215436 610443221 645599063 702641814 55076812 567421302 430753094 531706081 892548876 596854204 175061319 419314381 157774954 279223207 226233878 661839705 224259962 875039297 935511885 583600329 109942339 618928789 288452708 521895717 514470383 148018433 900776241 545560119 729097972 599174945 928298393 922357894 916417981 590513906 83517493 536762304 30713336 280689117 915805262 843539491 198449693 812431583 888509064 598207980 904215418 324341076 812741499 619068919 197815661 230249750 394089188 261207037 652082022 604147105 83344256 241585572 781035434 241272976 985083608 537297821 125073679 868258064 592323338 137201569 693152552 127295655 332648596 119662949 508725568 320741014 782985687 338274201 627303847 584315582 166236277 345615068 957454612 496852500 877396916 163715895 152064806 524092020 739553197 621806307 304257538 289099888 672435813 341743834 665013212 403994334 554530906 226605955 119107556 214911743 847342938 130710311 360698322 847584699 882961885 347282339 406479860 287626387 54191933 903686843 737156617 107783464 996563218 836275940 398233120 211976011 171831556 477215116 124632758 603467146 934855999 399743446 571373929 75153652 23495145 738178006 973427294 843081868 418631548 198833215 303626188 623381915 800165650 466466586 323994338 204093412 727211517 237607967 865086987 947504415 755645574 121156700 515243441 328077346 444327794 448423980 432344273 40315517 947658359 879769778 948958887 50821318 64370021 166624328 216007951 915600730 216237762 897128270 115498252 213135763 22926501 610630590 108775929 739903770 620063234 964639380 95096813 577350351 207430080 636948442 812930650 112566642 74817725 637688905 58875034 738030091 64679784 966114207 118490716 227491659 876046548 574205380 233742571 695120721 708053426 809915940 990199685 282856955 114895370 165185846 635275649 212547790 403617402 221590776 688424105 905968628 795917043 733413864 246168608 20637856 492454137 727741952 556813823 840351687 103686268 31019225 234513721 576230145 246453063 699867982 26960976 456449289 30147760 384596101 694043551 932663322 681035165 516926710 252794720 93403571 457159113 382596002 2278016 257378609 48148563 881391061 496567372 219111976 121569917 710652568 228331233 66473009 261694763 47870047 314688360 686945438 687150821 455569122 58353332 473838771 341586300 828684555 547401062 351526588 888093165 950884083 678476416 43693150 666623415 522791078 805956070 515859303 671339961 548160606 65483061 108655626 95166175 813827151 377961086 470921820 693126301 878063941 614825949 573493685 301003948 152697241 809308268 203080787 157851398 53207443 324604539 226549399 367902029 246130211 167967625 14140326 158892491 756833650 372741963 311495437 523311014 392660634 682757942 362571610 516835834 479894486 929611032 712626728 300878494 352712106 204946596 827303028 470932977 142201162 802700022 668369541 109504988 827622204 480034535 135626030 99255657 684574713 552869891 808489228 20805791 221880675 52250923 916832390 808757295 101621215 779929044 779932044 264827045 631538588 815266423 215882391 371395873 424423942 37786772 51768457 344784001 504561218 536869642 457153221 923694183 371537254 273267033 396119543 790616347 710263742 274705101 331048529 442888698 174448134 913092914 971745583 218788866 80578694 977340258 305262397 857420759 325796255 148574359 70850042 844389385 850533300 622692244 830311634 47049130 229779801 432383313 265331490 892383305 163307246 152065892 602018677 627544924 68974498 1024100 428817261 981416743 264851841 822864548 910475457 594868370 199019914 350402604 546424158 70724105 646761985 915597488 386786127 438535568 928503979 933747274 321778806 588739243 971691762 707957173 631498359 256664097 356950111 368365023 403687738 706016702 938271742 427641651 273171818 393137734 345154039 917300331 63704635 954060791 523767895 587235948 966437366 24284894 564682628 27079911 10425163 829994782 647948236 347938233 122444319 521192958 956990171 63158069 405682275 212122186 40340335 233808744 592112901 2410351 826216014 627228455 156361021 526624489 126326890 117760045 905747118 284634375 624067503 23602159 182870466 998749459 384325640 185557316 511857528 73310535 175702133 579074095 121367899 906363439 677331841 29757736 690663885 459595578 513781580 611693668 314058421 337208318 271856528 824297443 629634977 644033957 279538744 826532586 492145882 419301488 221402318 340178714 719742586 604614766 255282049 890182482 966430337 645783328 591112725 355446702 416178839 889171910 33339019 67787309 235466529 330182698 898041518 700218345 400166029 199092430 566241957 225832419 425357820 136622526 988619915 440357270 660002127 12146873 903500402 103374272 620925200 712964150 322855010 974086642 311376743 397646247 64598422 744618476 90902328 557662043 82181359 703187078 883275156 722165900 785198823 509535696 250321573 902591030 424714597 550467485 989752772 192304364 111979167 483652572 64719923 759845239 400048228 106571441 241249629 14615349 724601217 685088285 536595789 695297939 983469158 136079266 666793096 873301162 486524730 189266723 524884896 551071942 756735320 800984207 623686150 23070820 899432145 423100518 205557016 159334037 133770276 432322423 975631142 74992294 346407976 325901582 264934574 4711883 259673939 85892717 230649120 691996890 793654955 308788633 267765993 362416961 65793177 808306826 900607638 691560431 154459392 520388625 498839090 795885241 614431303 543362825 480883118 423495378 876173139 22807720 63773511 757325207 89441323 387840488 634556779 829027213 368678922 573306208 532530362 456132528 886740645 256957198 555271085 692298592 324419226 638134300 169870185 891094925 842435816 158544468 977125727 329606552 237381760 280641404 122202961 987537787 910706524 974856696 770250514 698292162 295212622 779983920 263130129 786640223 888830895 138622978 253760539 30732820 752669351 608677717 150657834 87718075 274985207 670177234 240602814 29280933 140788648 792428289 982491591 924317399 905196427 381681008 243886722 331950674 213943736 589883133 833885202 952234579 117761277 734547196 954046273 852659020 159388978 665768405 778390769 287130660 645811440 974690795 141839933 633204878 59777510 784602726 681592883 246506919 505946225 223162559 20391703 377581668 395456170 206321067 91516944 164923980 578119706 498940164 58250357 139448934 310398418 445475585 36885360 809821836 120156649 661142334 231722252 525344809 187547710 434471563 633156243 305051057 967439880 47118448 722928979 925627612 551736421 100058125 299609744 437772848 663967174 692133548 937528480 243301220 640168830 147443234 40093817 547320880 872993297 136993537 511336954 615503884 609158217 159116018 87903003 124813855 30103982 724956480 978170086 599730048 890775741 819809529 237330805 197293504 654044265 459002357 728743566 764055793 268420272 148888904 678509868 133423687 742943465 760145517 94580815 980845979 986023452 644509666 549768844 876658484 478215582 481446909 139036424 244962985 733061398 467856889 679198131 117358558 945195153 881719533 121442827 879488 382577320 212864011 294428206 972884210 235466301 724695030 710405461 755796540 108259271 981967910 621769798 641517172 878979939 118878637 899504338 941739456 541910569 363701878 274100682 936898784 642071957 370511193 595090477 38702388 506764361 764944672 535937013 458489669 76864769 186862518 214293272 156993059 793990938 691056788 856874588 97234469 475307682 88727098 249554759 671574418 85347990 597404284 404247740 963879013 242161310 161704687 643381363 941921385 774504126 186901505 732150842 259993466 413610553 222878694 387364030 492964760 904108921 422367166 617711262 673226609 130291579 455555074 913403726 822969626 129268401 298257539 145455353 205985968 266283995 162353753 486374396 644813085 527765358 663511531 662650208 967453149 222239983 99991145 454323348 930597317 667483118 518716901 268758974 191191558 69692626 282234732 175614528 317279968 920053740 344743160 92612498 527928870 271055338 483370102 7608950 813603380 679956698 53979813 591092188 140488019 931554370 76700364 970221473 576334855 678549043 258094295 270884758 979835757 434194143 157239520 430532950 286648257 833171350 294346338 940177137 229167113 594342847 685505131 77020815 767023286 860219949 12876650 317465173 406635648 759219580 397495847 794840549 472584751 768669067 868936629 252196653 726227467 483782172 959389487 797636301 718822557 604410525 669106953 561213161 665911317 161725326 852418936 555191264 42752523 101843227 249761908 88379338 419221422 292269637 590333472 941274884 18335490 933975911 269370457 4950959 775749481 845268519 29333555 368610285 29128899 206371487 318911157 704630388 780056517 58242780 383837192 191684545 116087269 396450575 856856235 511006848 174744624 910919766 888473778 728185054 258381977 479994868 510039430 399354676 365890602 265333775 484180582 220302112 862648081 468333974 400477757 549125682 547179393 286171169 430515335 823580684 436915924 698445290 223530061 546617637 488338741 549482838 778595999 882816358 356338281 703968091 818705738 143611146 965859032 86757019 670063128 744738110 847007279 525946133 283720843 709358132 392964361 728045528 244511978 340622604 353432800 534134059 651875449 516011274 180702857 4873098 998336274 115644011 892377801 856778662 509856630 202334075 986918107 850420948 611600933 992709958 77243484 920969331 328700366 114172498 1861941 752239513 931924787 250208449 218455567 850453901 243029719 133393723 386443033 952633288 663925783 737971709 302249439 540029886 934286663 564594392 717543661 9332434 239471499 277556048 247469303 636928922 348149938 971246348 464698692 879413993 649534145 167899570 356537495 289162362 161596452 978992951 791997434 511688159 92177423 783127378 357252701 998420831 836795798 235858055 196229088 130145460 304053504 512630447 526286276 408741621 962964729 895253725 547137527 459894294 275889377 650799762 720353924 174750139 881847841 814437020 452695379 745779516 491343968 348850833 990200569 124113089 105613996 899355935 229103977 805827934 125324885 901937787 4589986 66508030 338155839 418758464 161247422 682110892 114791101 77093022 748398498 533364226 841484164 594931077 871543398 304855653 686110115 593874021 426238144 527902506 956304715 203066800 621391070 279697120 57761384 349517776 757084828 947752611 870075020 669024795 605710461 934288371 697574995 557359484 650181384 480235863 967928935 368521220 456874313 686886409 928183602 497563853 318969982 935090087 61398597 239563412 688971527 607165173 116720462 751264803 405086373 509405288 616635058 774922110 873150372 114631063 499460224 553241387 218427508 376050559 353144110 324495348 738786960 78329378 448976741 321203506 816693271 827841210 829646942 548846351 751457315 16924444 445288455 415668012 629933523 282795749 342323176 468646533 463596600 58734993 23849708 416713407 937314766 988219890 579606040 97427907 205992888 608173206 588555458 575992373 696682955 255920493 544659991 700373319 362556256 726063981 871330693 176160140 556940768 381807254 674049973 719226356 251749132 621560621 360725999 494695689 745155624 138544778 958084877 127839598 158393054 416631768 91206937 405013078 968857259 277378757 669406517 251635902 483887682 467013801 744872970 626174557 24103329 458522988 832631018 97887133 254801936 583534084 46311809 221708095 808477034 356387936 247668423 818020516 44045995 800860310 161499503 804094216 690840376 872925810 859838874 408482672 78057527 886242470 177500729 213288500 876516374 63885280 286607482 224962654 776549400 74264974 620256649 606226793 796956811 266113291 434501116 477195855 748076171 150460578 171628253 326693311 750419948 115594833 925237946 124999179 430484670 835648629 166573365 904200861 101325088 845893394 46744303 751054881 494455927 899376008 59204351 991276714 819049854 531731393 227642421 920062011 396982225 555145545 397897171 70552094 723206992 988887513 333868018 230551418 126315290 295353510 79936496 347195043 90896375 24292475 204276342 602397937 225792892 656545131 812165995 958649319 522690600 672195814 713379056 817483588 456840830 920731633 795871471 24974728 284318158 808235199 639139114 233795860 318209319 229358941 279471565 644345313 53155364 758773905 68904820 818376974 72085425 26220891 187768773 257149843 583345151 181221245 106911986 953446454 435510653 595810919 221806451 635960439 78777074 93651056 615612753 244460998 84454360 141570778 114867095 323508489 715147093 350888403 191183982 974957765 682625608 864112260 24979240 453913448 634675759 428075785 827553432 582627646 349566270 328536851 199332851 614138614 489170541 673669252 786468163 122868941 871484379 564188765 460926486 284310770 200324554 697637332 511226731 302464684 160751340 577235401 875825539 951905882 111169635 330266825 151252749 243749889 163124191 734024789 583157935 283200166 513089424 18302863 980466543 351026433 678487512 429462504 63249179 48682441 753309645 85588521 33761411 177570812 172458867 308811059 790723552 939945496 735668174 641051890 465734801 502069248 691387850 229277445 246304175 662714100 352564271 823832875 194205896 988763611 969741065 292579887 903285263 83088733 333790199 197443156 172084550 358901244 773156585 847656629 143804482 734720483 225504650 961488131 220164433 37925564 277628446 354973963 274001812 726934457 985022303 489905005 9548634 214900389 486268625 568874109 322758195 67420888 858448032 33378303 302989346 32706145 741347106 213903006 50426195 39047287 8591742 54722119 28832815 195751352 695549602 172195721 395421475 786263618 985653185 413008119 224287078 26249911 639680633 636015981 881738598 763098376 107747738 252246538 380470640 828107738 968642251 44089377 961051712 247768893 260284111 169101025 216181840 500981125 238333707 303744837 584468952 201622506 826696607 192547039 720714469 492764412 13774852 796436991 736236492 884359740 42980345 386521957 533353070 222437942 721614712 310328385 453292090 488694595 619334692 835785889 432819253 31198698 824174575 78568643 45816211 230424702 700409707 2699589 237173477 703941917 565656041 474454122 626984859 885123155 116240776 251038585 147953611 163520727 67152136 373733029 202210572 210025220 603968289 432151017 396677690 968811757 260766573 790291713 481968969 65756322 210551103 560156153 227753380 385950174 613218516 17382925 81714804 718435965 997152327 479290963 337832844 942496099 216466143 833607968 104459572 748585311 458958373 462218222 294286589 559245701 45795193 879302908 908523702 748986255 218797499 484295807 671012933 202041472 344261707 531971286 81229186 68356200 400624835 953253466 154851059 525723978 802196453 496049798 582317784 487735070 312578317 302599684 290901251 170902740 323983761 437830466 67721066 205352362 261061708 162633429 442566906 444535026 679671752 80605032 9500254 592295043 962098012 694601076 72296270 919959390 845350727 790942270 43132489 264010083 749713410 555319811 349055033 893452277 179394499 65246391 30520522 217693411 563283056 322205830 946864750 685247790 607848752 201467908 697107454 917558510 740696782 785858695 116043442 61366207 943535386 992684779 344336983 94243992 625166099 167768041 45549568 892768663 412567020 871860617 839395128 412740524 631241291 613225140 156475395 868184932 262714511 309502815 520624723 657998575 39134377 454587022 713236131 415996731 494666455 226637361 185141478 236787499 819120296 500074114 450204856 435487106 25862149 273018413 460920336 861264101 780445032 864733472 747848883 962346363 30097660 373729922 887129386 981000272 199792265 185136521 81183599 553020568 387220 571380951 852810616 559901126 360856828 530787126 580866850 407189127 246961147 616596576 454537859 370661258 295982180 959063980 153076598 81738163 907074353 91215418 588078408 892862389 175516146 44286261 838656762 598497208 12544946 919492373 985963944 344186548 58337288 276586323 311568502 549536280 961257365 74778696 937547822 26012460 524645561 779883032 139915681 967050169 490084119 639507900 982166823 704484332 208790274 264984227 439068971 798077643 1623366 780913307 156203508 336487816 370547398 796808209 624387701 370126413 658704074 374124099 835145575 84492428 962777769 552197083 812573306 766085865 713242166 738769140 977789369 991772928 69914208 49439746 994986747 598472945 512355932 668210996 116419363 112067200 648776397 345571055 341735019 710266504 38875984 451196945 86904369 184277822 469471382 317021944 929723875 202980698 416281012 25641656 407341396 128166085 446999899 892468583 169477974 505134389 257703152 806615277 120249516 279107907 950088790 55948140 859354726 689844968 764007610 288244792 257963410 266346179 873098241 120143439 834149518 558942907 159311037 679448608 485775549 187882899 158060198 83561583 266343636 243529907 357402673 345878188 308312842 856579500 540625605 733032497 107096830 744944260 259374267 828590400 200507791 1446842 492549505 810352896 23869272 784462678 255382737 774710348 203361556 781879452 262253749 83850377 60214246 862550191 674907650 769354833 162572063 741318233 939762247 279839871 756345645 988809085 570199620 481435852 657677316 121253819 869096043 831130915 465695176 149886932 217562694 103241801 492542529 792943524 490199193 328481378 662690647 293805351 448621231 397245412 773673384 18838835 735447989 869002014 142201478 104189680 912275868 795278419 587454377 324524220 282490765 280882787 739962023 790737690 53064434 662943084 547377215 398680142 390579758 12186548 994609115 913152181 249727135 42529327 994262352 102536790 974395770 121499413 155440199 1888382 20796106 687950384 55054995 81809488 750231400 813126889 112893396 441406973 310610224 383369998 760691372 28394559 463482977 88615443 418413357 464898151 857714420 8310126 467323626 954644597 771282709 693485786 630393664 682324380 693485142 683702080 169362058 896184461 46716385 821694693 325521052 941654745 240328387 476804227 569250794 25018013 30029318 982764146 715041253 974689689 668504507 993954877 660981626 781621935 408986514 272155476 540936939 659905028 758599323 717139306 750556885 365400186 35358656 527293244 583002007 159180513 878785001 605299345 826741625 819792348 773816067 355407183 122625403 949045824 587897210 158393984 212535724 48143179 186807407 21896681 2996387 329272250 125600375 706683211 708801391 712258829 376060868 274500113 276158124 93535978 177470801 933101285 708575161 345879768 100542450 724103016 8431593 96363167 403037300 539745639 167472208 330225295 464193618 478260213 112918027 676069537 184968369 24524454 553576225 182508008 110528704 453392588 721127465 379607013 931285658 942865720 791821754 766675035 287412374 864895247 694720032 883465588 917999141 848847355 221053508 638926441 547251364 452502228 721682470 222025668 95880926 649160950 298473085 346970793 462682843 19175125 203753368 109168203 55336831 565252391 580339296 863796118 57528384 299658527 749847874 881620036 456990657 993074508 552889653 93050043 526086881 869697730 970801673 34024362 107769315 895334943 756498168 218801208 794764232 738251547 176889318 929806074 37194076 984329449 484897506 119254789 35542608 399943639 698450051 470403267 525127574 29039496 197465364 588278153 1360446 268614730 623071804 652908665 662889000 976277586 701973825 846052031 437337683 23747099 929992277 656704188 510727476 253959389 271877193 643905724 695630889 998992617 883096864 922645710 345951590 281621253 358967703 734936460 7276732 773887030 274704193 407454205 798812774 566149021 98461251 505790483 495523363 104819305 984973243 797285844 272982125 831882132 373968954 842168830 362557826 112395524 9474243 663936629 324832440 377903614 40743078 323795234 475677933 160988868 152126208 920524949 687553404 163241271 456190670 484312607 999394178 89255240 192376923 362793990 234064305 911731376 918470394 424746525 294317392 403593853 473259287 548550974 252224965 786831437 313008529 282826800 242423293 733757409 399398033 944990377 107965614 455394589 488124768 213160321 868971374 980587192 232321699 966191816 598520487 81613572 58932830 125266451 957502688 6686094 699218838 287115993 587141120 231694719 553336609 43740352 546291825 148244479 471771884 431685399 635092888 903592675 741960393 901775342 508055870 984676062 845601232 15580083 540788711 607687562 65029204 815092314 919643062 199651685 32510655 940893018 825098103 53773754 980580376 637970678 28810118 397531561 259142223 181758526 717361551 833681206 663774963 681915807 304922725 856618322 896408425 264368811 332019079 78785462 736731177 84502332 20467862 475935605 87373503 812442558 653820401 802601223 236680927 379392620 782245847 489397076 449074549 575188048 541377599 553022005 770935416 575323521 65164690 318266170 593829486 590570566 265869180 813113083 386365864 957766483 217266181 72490549 183027154 368338553 239357332 603854868 69086488 678542510 44879062 766898135 493547607 272819142 302323195 320405334 39147450 345106883 642312761 645247144 338988487 623742747 273656130 763870344 384604934 67880159 190646654 820764081 292589758 518330537 716395986 68575626 452280602 808188087 120776579 939168305 288403593 99281244 924824274 908628834 260677921 187088132 460537873 676983509 379106655 805455973 655296626 308177391 675515873 549716395 250540848 923364036 354092941 669874370 172822350 840612074 623208963 996307679 680944342 62069104 201896081 19108216 83232875 179344255 201267262 8061877 47423874 931182957 316514716 202951062 663169000 206977680 940398534 890954592 410216621 847053176 173045396 197912097 22861893 320609761 510168301 561751063 920286442 43644655 549710796 557653649 556638013 604989760 74425655 792078365 525506042 830751450 110496072 126240852 540603610 829979639 738341780 23262039 394940967 727132077 165151208 658851961 838607755 494906131 268309705 923560804 154533111 670273151 738866122 657147350 863302303 159682945 223855315 215977993 898332522 877159606 313236509 29387940 806733134 274668245 83979503 695986530 758099618 776262224 152018157 282856743 911648179 456000941 57578804 218401241 777530091 447347263 894079980 492817414 871216263 598702508 576615305 395881536 584606427 358186319 933695934 682496992 17340447 147730164 740824117 940276458 423599614 137463981 188975764 429680556 81825119 609266811 726115154 840888386 848928440 363663941 449674488 838912073 254227609 724469751 59093925 606212773 538309459 473339811 753914164 259620999 405887011 977216620 196213571 588853650 128064045 36107736 819111582 885477370 256490315 704594096 602461287 284419236 143813394 44808259 445194088 11121000 139895661 140346767 36094991 434581995 86764630 398560295 537868665 69736294 807759973 144167520 88794050 933107215 715858009 233787548 374723464 456102136 297786796 154098235 605009808 417137770 124451122 796495215 55955710 729045859 583438470 698982296 458591182 981485890 894858932 253903297 700444776 429102636 696986485 623658876 23088175 257892036 989169208 2873578 619541533 876147508 303235983 202349286 490807224 420196144 704008686 830697610 203507725 168988522 681721866 18859957 920621569 27781479 430173135 111353937 622878958 428922212 611024931 837332379 923177391 228368926 262601539 218841538 943732278 738193227 656196568 89502548 271376577 647120757 703975221 5486518 243666644 48385797 493773998 902882435 826550429 251511161 151060436 265984242 450234100 932455565 401119185 101586900 746954523 116936727 990510048 125222586 741419838 856865369 965371581 611339787 930336620 980842638 425578262 991539003 738572078 82900512 946630984 683633049 44241635 243062142 240875696 825622411 606869222 479203484 437067039 309431989 23754078 161370890 787719538 284259237 980172211 696808781 268730493 476835948 126548316 617915230 148221823 428127923 447803437 829085687 598655391 416599282 15771477 21341399 423808611 773947349 257935771 998644153 33152241 906299397 817175417 177206118 197718078 586156357 410439510 655357520 316976889 493229717 5360685 199809358 241472650 415355053 35051355 209142825 421574695 644914790 581612712 691951754 783722559 731739871 684398406 325414398 716231381 253948586 450674929 669534115 547252320 11839985 119369522 390021822 959994978 981070756 869402798 677630053 931044171 945467 129777340 482333587 333561253 445472762 369132629 222695381 455117725 596460372 637201929 164189248 537770958 806733470 771369189 992084708 337928068 227148086 225207583 63301058 302010062 307156527 496443614 420047230 630122943 606250184 149914364 637571257 753942651 242174369 823197409 389087922 25499550 94592149 234158395 203632606 227825731 644289922 760763273 707532435 80989289 124183033 640100739 213338170 337715995 331586096 775053287 801105499 962260567 172811423 507929515 346423859 463307269 433839886 49012776 545661313 582253653 208363699 631245205 746238353 771418394 116910001 168852468 376219430 744391893 320289506 445239698 787506984 68136937 238709117 71437268 976475383 18933398 925981024 814666905 39222243 686755442 791000482 545790799 885568388 99183853 201233918 800930963 718902686 855455046 854112554 690942050 433412627 551825325 807486939 293804497 151804104 368550975 446167232 550721487 71955719 488034357 519374296 561151102 210561708 714175764 168990880 458139779 761029402 74389786 779146433 353081988 631886959 348649867 29263761 516224670 231765955 87981255 958373390 444447782 764735884 713753834 794668843 99871204 878569780 539538756 402166448 929146991 544364156 561171521 953590552 416181699 372076796 260201208 20745376 561414751 579240668 936562263 468720229 622057515 607837268 11390595 671299538 677299588 168789163 455626463 395626588 973052295 786766791 720843720 126481932 484984771 508721015 431842501 829460660 826282396 759249093 700647721 523771108 842170432 288965219 306322023 472454964 75013483 173936189 103730220 680191482 47316107 757584726 789042129 96893581 11171697 691073812 385753279 186188113 844148856 845578031 828598795 821934578 76410901 289870516 565502597 605444717 820252176 759990842 862612437 941701930 141665659 931933349 588921149 671218273 270542773 706225696 560216051 81116837 72900151 199301787 988591053 147880420 681657522 624865910 355174614 169776761 644972819 525035115 661127787 652448864 866914225 444726743 558627205 323864208 772651751 137244058 258484588 720487926 197885977 50060496 644662863 380433359 104262784 866991247 117364082 120838060 163194016 64376210 348803367 469548582 971075347 963259681 590619205 446022901 793944757 922732463 477855619 87501527 775368598 51653338 939242504 805463656 773583962 810623270 80661189 167459691 914776473 515478433 271467413 33018540 46754784 128207869 126578556 526565330 653812924 274719101 898264769 459608644 83121944 248312152 47342288 217776320 576629474 150436877 147456874 498104485 818634517 800711806 615617434 882304630 84103691 329423685 921060915 13253716 58367577 122969970 953329963 990253681 589692958 534799678 855010864 837454945 223089145 613843190 536783453 938784472 859819014 848441000 153585179 990846408 225471165 347916532 636867862 514196010 266189546 222321857 522118290 631264089 19539402 117500641 421318209 167217736 40353760 504798365 372133375 257081280 359939368 182761774 783558661 545227051 849290344 740620353 899983861 932864388 475278191 864777371 487755567 660824535 956633715 155372923 410266559 970888620 764728956 768406799 251766622 800892835 980300849 244719549 479237383 502472624 202493777 481013015 157531409 193033265 72033126 172388777 332093014 884577712 341968672 936854698 865365811 788387924 394772342 549290988 891536336 205562026 822728978 117422955 224745412 573117548 297064112 66579827 886410163 146206411 762466617 773498647 245162688 258211349 441918654 44910061 704065588 89991388 878178919 245908034 831949323 835284594 471049081 563018825 389998999 204832663 717832513 805990254 974041197 110322347 477913196 515524661 921921566 387690321 85483190 685357970 701242865 149851033 415060304 74661489 95256232 561528830 541978938 462194215 46830672 467233577 366471472 358060560 352177008 413337522 111823656 358249190 864241962 139487924 455632616 681050263 681418535 454923009 742909012 462121049 826960248 441298709 462876070 31339262 234832876 817423944 973480899 432723415 581563244 937093721 97920681 916930703 769574227 951712981 393446497 475500124 913963959 546218823 143389579 226507164 132377361 784967777 621675806 73794187 911829725 244678358 445171643 372368508 59417866 731741394 735709291 248241083 444921120 641688529 139119792 886053835 553684504 672223239 107899890 661853935 202284507 358411018 848019379 870579059 340819402 13448160 933920107 808379289 154892076 781964137 238893647 719510974 732355954 196076870 553036763 35081040 499011636 221594278 394144480 231886019 510051997 105393679 972679214 158363159 142292486 595343904 7589768 306887446 510432810 868816035 465411195 700820752 251086243 196083296 398513340 86033961 523176604 596237130 395093242 821552091 76529129 497198984 544783133 870442742 78925130 673099775 721720077 894861699 368724528 280716167 72160829 42711140 992261309 231473340 842355195 480149233 50718751 538330543 123599899 13595675 17401366 447716615 700800966 431263280 756649748 408228028 86660111 349695854 136929042 752722548 755116010 941874366 709801769 865937691 697062137 473559342 138475788 150098944 797636165 925695786 400529237 841898841 304891849 844410810 471789659 383231870 377522696 527707546 699505827 503096391 207315346 448632856 433777232 846903259 304546814 900625725 300824360 83807381 124714548 154898568 239780001 359074653 799062282 54662115 71777247 396026952 76579358 582403542 710286201 310900937 347194333 498431598 550632125 397731323 796300897 900783878 683754084 183321104 542251132 892439557 453430728 23419677 123124632 875472212 343157611 987348101 136164177 610074776 917273950 817763007 476063995 539661596 184250535 745606840 305158888 402682670 788132458 291728669 793963121 886320444 967497658 719452529 351749545 665351671 845590094 156081535 965424583 284343059 233982533 262785189 82776502 613723537 739848303 248277044 115799545 577785607 942720866 988575055 444655962 567308928 356658717 861270810 9833633 696273170 760996720 723384088 23997256 152902879 41491054 448859190 666352492 320330149 261159495 315694640 411645865 627681637 117688805 299682630 489650303 669705061 813606872 705705046 318752882 117807050 828122751 65832496 625802358 101537497 357581346 380742294 588074341 855526648 975217906 52545924 132007378 499257584 985020375 451541413 754694292 308776892 402958889 505668234 441525974 996465200 615813507 7224497 904435988 390996021 672928768 947159400 719352397 772634311 545468061 674758341 429747530 663154288 677961439 983307260 652586508 862766358 609766152 124350945 550800064 920423655 857447939 915854875 269281030 52033303 156616893 508009551 256234790 316484057 12421826 926139053 905218304 237046758 841343685 318871145 255291575 842627037 13562032 129026305 277878032 948093830 709521089 351320150 656524514 190926221 643280748 906613509 203101076 360221142 655971953 863475307 82552284 126831281 146001634 564550698 687206205 796806017 858730800 912919213 220976082 649206398 65465497 802101601 452647935 531209313 255777928 370098200 67468684 962941427 169146725 393077165 532880137 652521528 515016722 150819388 922111766 695092967 986242765 190124235 308305948 845394351 177733790 648713285 287711630 481971717 724462061 138589190 639779632 491155637 885031908 167403273 367061142 570027748 508537744 332081942 540960481 8472942 550790275 359782311 782890977 612812556 461723089 771721205 678915859 673295507 449289470 612837553 10480310 644887066 277291402 379195661 554438562 301166450 273801703 957248856 459403595 261414192 485881015 710435950 217278803 428772868 546472870 959124177 175029433 418183936 799898416 264849937 309453639 425708621 586237949 95378773 250596055 251732822 918891178 26368588 905561418 499036384 274768241 384469035 769479103 808239618 155942159 642551440 710555719 566548574 452751308 752337527 598820729 589414676 183043786 446629278 160177383 429626789 753431142 595134489 871103369 159781744 78644145 13949849 405757041 862056657 352101580 38146549 85632082 256572620 332266700 39699247 981975610 901410310 154516801 568658986 476928722 686200380 703242166 378085481 237673488 21708677 512079003 98292397 738447402 482542308 122708327 132733534 836280994 577217080 740408612 518213673 837453900 196894621 77829283 412149847 412146350 643063321 847043947 985579914 994923604 765818405 907927471 918640908 170306378 953618117 249152989 780409212 363922840 594919969 918265962 89419843 399773732 449916347 248645074 643186785 691304585 116477235 322078764 201990670 775751758 203168365 443579965 956572005 343006682 977161453 122133901 113401693 856478151 714612856 724824856 140422491 538021603 431366591 305994342 863677464 679239287 120141528 308483123 612465710 53776302 623256137 47585353 146996038 794664033 876596171 496044066 65606246 649896914 756560293 266953366 190932602 321659801 767498455 895419475 559905500 962936792 576914879 769442674 657535854 162272516 53770158 88604810 915792486 728136100 323307729 763613714 610192264 855206532 434212409 611707769 288145516 397528512 204049898 361401540 807924854 196175176 891375014 769770851 492390053 645208490 191499273 142820275 928159974 505036242 23876307 234196733 804470352 265706218 216740838 971930658 131997322 289723528 69295268 229877389 753143160 805198994 902454215 537724402 259924342 841807847 522348260 406395532 730003094 492618638 130808988 490716007 254530289 620642482 298685725 841476832 998426259 931783064 729082980 232522220 943536852 691645243 245699925 992847966 631677153 343814 102558329 965221028 785839323 393911522 956388986 521697709 473713120 927996485 904996780 95799286 65809307 414088967 866584320 492017168 685879656 905552767 298763638 694521538 393460671 580055570 253327329 636704018 274071997 860673486 29802612 159741214 551982507 246988446 875997747 800941609 874592840 201113834 620802277 200829851 149743324 27390642 896222376 415813299 118767728 455012852 189610948 347058537 284744888 44298828 929375484 288496307 180439341 325755727 213677979 96687983 181681798 170151252 406020277 904910632 667459286 835503165 34947236 85951041 115593192 145911366 669859229 784863301 209238984 376918818 413420303 232139781 820704366 151397915 824898759 145396980 925295464 485220195 964277664 372428432 35039114 507920268 748318181 464849020 747812252 876911770 410984897 648382336 126773410 170775620 181141876 62177880 532711042 293560072 895625986 891832618 936269560 762083479 488681736 270906986 880527940 83020436 48299090 227668477 633803631 286804138 639300619 233966477 116870643 951884618 722830804 893865840 956314138 340021232 995518728 559090432 823918395 136229652 522693649 47407689 513889568 852346901 48479912 637786499 107892220 629859696 130545774 20131130 746628752 519530984 615192239 461734380 138072451 203382770 148700176 127206161 621086097 759340417 558817614 273338150 150491351 789743374 511455833 506803059 200313415 918772261 741316403 222077513 857582404 626356132 527948732 266269149 970550358 271186772 825257351 381990080 638692635 133466961 301405692 77790744 996476586 189391765 58743447 958895216 913153212 906474025 728119193 834648755 50587504 317302144 632179657 612068936 964936806 220675166 320690081 748830148 663919664 276978431 746331593 970515007 524023550 596369867 264727797 158176423 201332787 655133527 228862197 954151574 388797539 250122771 180275507 205015991 125289419 161509574 650610 36257159 135817640 981410980 875897110 384679276 140702471 842406477 700791973 33330964 82766016 30063162 96854867 610989509 456076611 693471936 98060232 517181883 611728191 793476804 120801047 863132918 233746017 395561414 546864223 629452859 222890366 426619250 697084041 188654638 62779141 411836364 135910250 246820638 73174523 969696985 927472975 438422337 116134272 202052564 462442385 441255290 949124980 122078291 293562291 733074082 369338492 952048063 365215920 883896118 307868582 269446913 37392941 996367504 460263 434477604 539458230 44423109 983162503 112871354 8545850 292504812 620150777 47126548 600960257 410117878 236998897 544757674 560486843 394265674 921498876 52041789 31145933 452115719 246028373 242182448 130058699 369101695 883879310 803987175 635223950 548817441 359065228 411427198 295972120 864488246 964205922 113602081 968951995 764407243 500337969 92983749 522683096 306111434 454731361 151766966 51188555 262900763 890542778 640480086 455807086 938246118 720808601 331034753 796097112 635010657 209669145 317248246 518530022 749552807 883718491 53321416 582898812 669192870 656656094 617344770 130853991 867203162 877326067 229706117 529022657 20153529 576165804 23889942 397228675 869058540 789219504 261249059 197181902 131286485 861778315 377983515 62613790 609007727 541736763 775480168 880426238 789311595 793860212 688966118 660538255 906119398 846942269 203252772 584997641 444842117 303448474 445869179 37291395 341061650 199321096 553110444 812024198 131975728 784550865 13803483 767664498 536935929 198492817 727273366 396561923 596841133 925813299 71274595 114477531 293946675 556010708 223484598 265144479 950224942 502470884 563360428 764090857 658430444 482503068 49714215 245824481 703858913 503541637 288130737 195438946 333426983 240969011 385268085 250093598 563854453 103221299 428783663 826917603 413081048 588303214 783132942 179661971 39240178 733577734 995261448 750858231 347867138 724458094 98011703 988901592 320376186 249172282 902019410 172802288 148339490 515512857 723433970 105579044 618133504 650211945 453307182 237709584 489371803 284126998 5340931 161478477 59341405 292461442 128270308 957891091 161850479 787246576 536396537 914759957 544885308 307835951 334317940 734641193 96584842 196804930 942377194 8453644 684188562 321659282 23817222 977825006 910266863 317651471 524989807 509536192 764205889 843077790 868320488 504422639 679817987 278057268 887971686 501115107 284373856 90117950 994235456 61094404 336630325 939292449 419706302 984363302 787778766 432131990 406929884 528534078 50971528 681404736 419734147 818605345 619567878 804245596 17792866 23969097 266409286 275108742 976444475 703075119 532608876 997999623 936313131 236357392 170019950 769737481 721079499 745017617 166001977 263469902 772218223 167598964 673806385 95717957 736735152 249798959 988955013 866314830 292679325 207185417 407351157 787475101 563061027 574918838 343443933 248980721 808622121 675223950 290076444 272101194 960161793 12689824 536276193 270622588 205319076 264458781 281282399 233856963 757060666 114477533 664137718 397814510 397887598 181167579 714009415 919649332 813678705 760273416 216255882 295188569 280981278 525537787 935471570 270231452 167790625 846825962 811586071 437946243 969499067 774943869 707736069 410168674 509661046 446080031 641591853 431640017 720214656 189002841 552707375 511992838 70047062 373217809 34306592 865585784 458656354 465853655 160272060 605890799 793237612 79187798 200736698 51868334 45487527 879726938 546872988 593037654 728381277 557666601 590610491 619098188 822991739 772413014 776640047 285456086 616118362 195578734 874072975 489715732 550423123 752561028 821791095 66749641 667463842 377174819 892501715 903464098 906900818 262719967 760853866 239091896 231989453 177871422 823402874 292641709 986665609 404841835 312658399 502859580 155313237 144899533 415892124 64582221 373012959 839857174 533838892 564559026 61570031 358441541 424176170 309841780 323789587 251179613 740006450 106902715 854740368 652019863 871949393 371045419 280671958 922453008 709301983 113769771 126231572 21771345 210159573 939633497 660793306 19040574 934367690 275821575 3825464 266099813 641997141 302435959 959617475 446035332 233603305 279554886 418768013 359132478 390502814 526866668 576285283 452224654 299955796 594605622 998434445 263545067 592914034 751745150 887519364 564952695 86258296 177118145 521774298 54890711 260481739 381858083 600835038 321023766 270619761 333343912 132687053 872026225 782223516 65703819 495529717 805676082 47599800 395400663 245158118 137687306 163122527 639314207 203878285 748850245 821371127 740264635 770193836 977502070 340562419 956042793 969452578 854823612 694155043 296716475 107105791 186714287 54993233 578231769 787093224 649792941 409653669 905606533 382886113 671806011 494724236 504399738 430661422 361678611 174380264 111574872 251252883 275035799 246173463 774630069 157260357 437655267 398651923 449100223 971134666 740207032 974715082 608428038 595921369 172016349 871431588 28605529 876657217 81651246 89722252 934316694 922927983 160716845 644840183 129314132 785492352 814945731 837012347 864003779 117315934 2833732 744779426 636070769 759428502 657688515 848729510 691719486 904704987 955868315 785360849 515001502 185318970 516940183 740333363 899262918 300569510 141028816 990322561 769761106 970911361 116732183 940872954 86454847 640389630 541537198 360377307 380142563 934984364 16795183 217966401 44106933 303749358 95474005 517685372 180864596 267274047 57123196 346161685 214025774 87119052 281843630 667652926 347087769 846571105 672497814 182652306 787633996 92173387 154723111 547347329 507603009 444555516 645586641 484838019 779964004 885053788 516644775 360268273 326684615 991838823 904494904 188780585 86206182 781058158 866687049 909623632 802354769 872806058 92114119 924266671 944395908 106580047 723256357 591057091 469911015 854424599 80608753 886504839 432759018 106314958 45293950 84306055 743733350 302957640 512070750 211531741 275787457 108337482 168998805 645504756 3144116 134150758 614888472 173673538 906228234 276679991 509537482 353910764 15013299 22792590 30071214 787009595 333986677 71159268 77531549 920552395 135245755 60796626 750845663 746501073 722651891 806240284 460056517 72098256 479160343 416919246 56860056 492936917 256364714 646755663 431649070 591435229 868138821 292507453 12872109 88154833 781015185 267484913 147916318 388448141 846251323 733881615 438647272 361690811 44227228 493608278 75350429 698887707 12710600 810773456 38473588 170979468 320879923 378376888 970176917 274338374 53904577 559895294 820559928 397905206 171887846 718509572 89009478 840610282 138991103 708893193 637438394 288724585 753937680 166125410 673894399 97976044 950505788 618357908 351698088 661907474 809309997 442728799 81177215 504506715 778661780 206962849 848842413 125455113 41150487 14958620 627229139 683097408 149676370 806223076 757356605 501557610 302267198 987660414 640282529 312875127 439229972 577211966 399715238 481846752 932592351 24412011 789160741 835919892 482163133 805950959 473821941 710067116 28066879 882045822 851983902 653567955 58141352 368029980 589073372 587084470 105774109 851444696 755290506 672473495 454882516 402215096 135223931 490852512 620828769 511715047 593525580 709188557 801601310 866877441 83122276 705424411 37192750 5288545 298406083 733897814 866048565 520815279 341684365 904384981 569979370 116983000 593667278 126132459 762522007 160449848 561642056 542958650 525713187 981431985 509355364 626118224 549127708 546842457 924186380 390542905 190963780 155136615 117287093 799181135 27073628 518972007 636564724 811099283 635279647 456352815 132207616 216652661 844722040 163939690 289358690 150887342 100143127 815181339 941159382 794711953 218714884 631405674 713114249 125921350 319702495 274789287 191157573 348469051 788038034 411573119 720727627 102989205 56135267 789101071 144690517 77622756 238528066 443403348 767237555 205792137 704832917 831952236 648387909 158668887 761041115 590704496 181445024 416021103 932203807 902531690 773356912 650148111 47458630 188487633 676586180 785266082 893734865 6503356 721944171 428095805 790368266 102088013 363850448 532111607 837969301 612754092 901272189 952821883 971366775 250312333 119673445 71036421 559472647 967602617 57271138 773787849 562854585 877969093 57074453 253962416 101326867 478072185 475060033 719100821 456971091 850446971 722342991 930098247 882737056 186668924 914763837 559707100 634963914 899237535 754536359 360643545 431848871 526459988 772232668 216944934 91637768 821027757 796528558 350322644 130645378 976143474 386932619 346013955 893023198 695386361 234282481 652127414 970399935 663339721 286171371 881797829 224597381 572414553 41520876 297718602 431438244 108933477 818417375 722976242 175147621 129801155 97117450 136035277 345089159 398991083 534251962 400625610 29811240 622065621 420112283 766324893 775496776 84880940 792789643 107821650 712898081 899921925 161837583 804253436 137146017 239603099 146748023 511244505 319407752 72530856 998209348 238984759 170609943 945395682 804105799 663576821 414691944 121019182 102307142 831320676 933048240 578127265 99251822 537428273 188732360 60659098 582890050 366909538 295998711 471047379 921319417 143580966 782542087 12506279 715265265 770581742 700739579 167391000 413106925 128515910 109555109 924729540 598515902 317093128 448101043 561459584 12710609 214564654 595585792 394411699 980249704 234923232 941360746 202501814 422456822 234908610 294639659 526020280 61773272 200428474 366501116 315335725 656557844 647825764 111689631 453189178 316895272 265551278 651847632 451785881 816748185 408096012 834899103 85751878 689543636 488970294 828360589 386720077 515878118 824801179 438348893 261735697 878169188 427347878 953952673 498212046 786861521 398298867 961655576 14372839 995715398 315249054 721654076 70066419 325376280 474827222 323641197 659438025 943573883 794721097 164813681 253374401 73380647 619962960 587321041 768023289 778145754 173072651 228782798 588148670 162375943 636224907 587877133 928439030 202919604 605327152 4215882 301539290 928645606 154161428 630979643 771796305 465393079 95357812 701066494 1888738 784158602 822032670 133537628 958828292 644796445 161233030 71204623 744208685 517614219 452754712 714598269 73570139 343580108 7250772 826491050 41402274 417299675 878267146 489668885 79891302 392351070 151550471 686331414 55327521 473894982 990902394 208265673 659808841 352387755 542624846 779506933 230594161 382636936 961188782 838064550 945025022 921726270 757732739 190120994 794893083 415773449 900343495 137322785 159645096 665741559 995928876 509444832 306507098 946739120 940842100 757220872 999504989 847496025 707547038 600541780 240164938 356042554 352358958 105969060 57646050 552253569 373641782 278394676 313701665 606804720 510858135 444635115 733022308 248925295 440890529 873737186 420936983 602993045 812996343 405794717 55586357 432934155 601068090 823634813 5458783 126206439 620400345 623480622 277760556 374248218 908827231 298996775 463505699 30225526 63453878 621862270 24657757 459665945 219456867 3172091 319645354 779181404 260977564 179537929 285307332 739423630 792055948 685896068 499413100 662746467 745820723 920542197 281310802 241533473 439949622 77003740 103134386 631779525 267944731 718997411 917693733 189016905 699911695 376927208 314854484 790116101 72590319 705701779 917961020 865888771 567604443 127778938 693858433 970879550 869544229 133315910 198485062 861464048 126046657 762176742 977737871 617690458 865649791 725542426 227553235 196951485 478847387 487944608 535497692 591809897 38819782 43299908 647874291 311817964 107260461 67083882 567498926 68877740 337321069 215977101 82864337 383554308 296780465 178249981 23326144 621783547 544808447 424789045 155020383 236602259 687298904 218742037 767578926 245935214 203284281 853578506 128909029 639368665 802018028 525371406 493769675 480097057 35822558 208830041 895807246 55241619 589992369 64224755 13829665 180416504 190539783 560361596 256948814 848072783 38177384 61197026 340922890 532295373 680314738 124989406 561448531 56049699 408530815 845268477 127089523 464313656 362793163 594050060 148966862 81852340 859887215 811466636 262958659 880880346 633390241 104795638 932683688 36797756 233955269 669485212 178526211 681803146 472202489 895080713 420550811 499808143 976534828 27958572 300724040 344617882 956045887 695701207 877637585 126403102 289396828 912181476 663834225 108691109 653665047 971892592 293659368 237333732 752034762 457071271 954110017 601445490 86502762 494027494 464860447 703808471 369465038 419779491 20884578 619454020 821827854 177496933 122259042 224017569 87660111 503167699 245942406 547581304 266360644 43440996 868685206 971788567 478380232 230272299 977709447 316423433 878647266 908126376 917768166 402613719 315883480 527205241 658737477 576539174 699371032 923786712 862756332 498244557 757460917 410370739 312123485 942746640 162837194 460898325 98011385 871143966 965544343 198924373 746278797 317453233 274518505 417285849 998819231 722367069 935910461 563788784 870269396 291418829 980931543 784332682 786429878 216887192 434707407 934927421 672995308 717437929 214990031 779073244 411154506 923544054 970391728 11942600 126949863 907001173 291406947 899664024 128362231 906468727 207287223 500470606 804107550 531511152 451429725 170886752 171933419 476941439 462127540 971753373 318906451 810081922 799939234 657897371 830230663 750687910 199670082 918798592 537926473 655926742 210826274 533442693 76161856 224047831 125526493 860100434 199825273 52105336 956203656 798892720 580555172 792172148 504232571 253476800 872047487 607622602 120711175 354199762 334354371 625263509 809107293 292392506 888650958 704963656 453380456 322866018 919301405 906372183 342599891 962918108 183565226 708597428 278047111 474069513 697200229 840710241 945878103 436458219 351042874 557070843 650940743 418003085 61293227 648308269 544806093 874499589 257852683 215626018 544505004 32816448 739912242 65049173 2771199 487358069 473863108 972114061 400848371 386698330 989041336 217513738 266827457 634523118 814443744 677714357 394097585 422318028 897455858 229545759 136051908 302797853 857837482 748938355 471353266 659148962 202103481 151144161 16608848 64117252 113197224 346124287 123307813 751627529 336116575 58233153 471652434 819180502 764510118 193614834 874680370 141804219 253794851 544371225 763052903 337070872 211382447 545691532 948298308 851463563 173489939 360418647 853650613 346465552 42464826 658078483 991363905 796859662 225033025 833868167 81218595 56798585 964049919 208393342 379328877 682693889 782662017 576058405 307259385 274958368 983113996 974703758 209261630 845554340 613488807 22854180 828614428 185903406 894410279 312562573 164041539 41254527 630756951 856701608 106011014 110905865 790660842 570581795 524188174 820171874 594358478 552112342 988310553 150010857 135230848 62743646 602232903 440900822 644378420 739961139 576132928 528582510 244223742 208776970 125767295 786873872 927438534 98014114 928539553 369014742 663121793 706633986 449562622 627496749 156832863 661784425 937838931 821868464 521997794 594107265 580483286 639817688 164141423 673799 990067740 964599964 901776859 424360000 176863920 99471507 555514105 227847773 528956274 88356583 109755073 870764688 746542625 268523911 779966586 874054027 30517796 497312810 110914714 530582797 934147026 344214493 496312870 298404332 20213783 315157423 586088391 780068907 698086010 914152656 991380973 776482016 383649398 87091378 411265048 309321119 895016719 782313042 641169110 214380995 986547461 627502179 523001407 365359573 220860917 998623585 502090007 26940340 622874538 123825254 284248561 905184465 711274912 283972825 931689919 968784938 367066995 345458569 996756358 890554523 815559089 721206374 89090417 177730721 621265905 968981759 807768216 645347709 177834996 216812169 84596339 384643073 602812279 127938882 394437532 454793259 295141211 88105916 543937095 701268140 530873954 429562206 47063652 36976276 553565221 199821881 701107383 47775512 140924372 450236126 643642992 306541276 237816976 333978812 602395002 763349470 425562346 779568612 943488932 141435392 34056601 249781233 151590672 856060738 861531368 553388290 461619443 247308443 330582728 985255816 126413848 238053380 167179677 705326636 149805657 425657685 896394839 330448359 43882704 389750006 314111535 168509445 17325563 473505349 971377779 423111590 119031571 280805681 848291427 848304398 225304421 11826458 697044212 612221547 136196758 430157268 848740258 561478367 295781352 967006133 96643970 672871901 510353029 964004249 970750404 362636940 285860618 307011194 138014300 259910550 932934584 850059181 427514055 904773010 969359424 837536925 472453633 361114122 218846850 445238766 843273477 266234433 748909722 543352907 973109464 7571447 464679100 784772621 979524445 201463941 4574093 403576077 177957551 788627836 707056846 128256880 624960219 616625469 338068925 285158138 67694799 32298403 580033336 934376788 532471914 477938051 958130285 480398925 530203519 785110873 637987821 2915142 385117580 160497111 175584020 157894678 464739919 800284771 251888046 419579190 548324285 517959924 6298421 658843670 18191599 24316290 890709104 776543447 416724488 132387203 68135108 873686863 618002113 178546496 374704289 902516107 327963065 224195548 401757767 121236536 823199816 56640052 956724344 399337656 703597808 751691506 294210760 820922259 947784256 140405353 356379500 402238014 417730707 798517541 240215281 154412456 78080915 151827141 829347998 879005395 491520048 594366860 700733249 154186233 573236835 773829423 157117703 782163875 491051540 173457203 88631278 136163315 988577400 48543448 732026699 335826368 448497479 811153823 3759591 261039341 457701035 529214201 295029265 824462185 105008593 936845379 120766496 980705973 77603864 317276806 558517338 807094185 286311690 668415488 75391445 977040979 163809056 599148957 294975751 755480836 381320559 465645704 762838855 530355188 379381278 527747113 851841969 879145162 120688033 182990154 583581096 874119432 195376579 389883955 802208289 338717062 578643982 198510363 437703735 376628583 893565098 89958746 492948933 484503301 786914567 280908478 97020186 519280735 904281722 3690312 7464619 347073269 319782843 26166885 456588665 150462205 753411505 793954193 146872493 125427879 381233974 958622242 63126617 812363671 375001508 740270859 108602451 105592727 92315841 147897970 711905004 612986559 384582170 333554979 783813933 806188476 303872831 232395117 933999352 836971033 838797352 450892274 117804851 440399417 498476066 990802579 427705511 948610907 416043952 603830472 328925195 295489963 421334860 619410442 124639893 463049704 856736369 41602801 116513908 111643936 11394102 435504672 586578617 165321126 101706122 709091305 544138998 524511478 105410870 155668018 759577816 99636774 816098022 317021880 368853252 312767472 108577741 47247618 312706738 425477677 656072222 804738801 940741598 398747083 99548535 997408977 335400101 723381604 520542407 975641889 225519134 760158988 446135369 523427820 222925620 272744494 127177277 385884627 282065132 116241108 739907731 884187571 653730813 385260822 966263873 807199179 243985968 663590191 162467438 860809723 572275589 448978146 34075493 420578849 36259553 248499592 34660793 888726449 821308733 247162773 416201108 207105456 999136420 633353123 805152084 799723492 445847213 355452705 24982371 480004319 60170261 652252312 592854339 63459069 883428231 710933765 215950466 341982788 21727698 67365787 715513029 334001787 963787121 950857798 75752251 564788873 434288530 134482942 503334209 356833812 154607041 559438689 486641128 489043070 743824013 753719409 76490813 627931021 725504110 77264670 823634816 718016917 171093294 449797153 14366332 51221997 874604435 7682114 822873637 357567211 655701308 980559066 275481154 96616838 457161019 721909421 764082596 924658700 355540813 354606052 124714778 985580668 895951952 293593541 372785830 27665150 542031227 579282152 233675460 66381192 136444476 495468851 585775128 632198165 526916286 250477652 44900425 889813417 810672581 360747784 391621864 888766525 555567098 45108633 533445483 302474011 940450532 683028769 202356590 914267611 684020703 202600507 965897621 987212646 529249287 413583841 484439218 506315086 254816803 630470731 611937073 338761891 442705589 497155723 210569534 242953697 133045246 925962894 598466920 612150623 520552099 736104834 743282174 42939346 20034476 730325529 289540355 901687989 342773765 966784491 803150348 774150654 166426259 374706676 195619588 868989006 360335760 660207845 549249222 35521079 65952662 27571577 119701295 67745009 544805947 10345189 174844237 320705619 92076057 549409432 148305475 781077382 205980670 676784637 125492942 977456241 951524302 208059575 965547949 816569567 696684171 827385685 65592881 714049639 3995862 319447498 373407686 817001296 704682986 184772342 197512425 364229607 15266380 123772714 729903751 622262089 783022560 476611724 249724076 847464029 85497877 59044267 326575286 330496654 262707666 613056069 7947001 357382575 896065573 13522144 546914990 623908836 849825291 187859986 120768884 26058772 420521844 85467547 2474196 144392032 481463985 383159475 364134561 26276904 239936730 592769203 348484996 597537883 135094178 621290016 687550790 22912359 852284251 991223689 207795075 640946809 440181646 58949307 629222207 781101507 660005140 938380332 271056566 299315653 249258650 959352036 637872973 196741056 58650521 254848006 658059121 331896400 465093840 251429647 570169198 843080637 261291108 94499259 518043254 859783043 859878011 577006288 681602442 820257082 514549026 501599015 323659053 1406845 401297631 290584392 810319218 955564125 374037273 935173715 253358789 510050807 128215631 745229921 934748879 515890011 478286478 51913367 385056034 38972176 51186462 26085147 841567116 490103469 368910209 478885953 56919930 250274611 118153816 739945151 373915163 308039859 82752012 688936207 339577234 957960114 256928308 939681347 103871462 729094188 656912247 22825857 897061429 192578241 194845712 48096811 607400794 565512934 730882032 77804122 516968419 182012439 557984105 631057393 200835945 21362945 314658398 325516730 220247672 520308207 349661558 634485237 328251534 744379761 267112215 333546239 24643596 728029705 594644486 466756720 373356004 102650796 142547083 955117019 750929220 57612992 944328373 615156911 781218098 844188546 47452180 84083342 286720201 618092106 665323407 217179610 880981833 303691703 687819118 747468248 666616218 265241505 260244503 468919294 378762876 271015766 224712443 185332779 571696239 512486058 508653767 812899705 519760205 923513942 786458313 124747737 648496137 304446124 855175404 523372856 586841790 903785841 222102190 76797184 29139293 184034531 654228076 995935490 860074087 947456209 337329295 491446658 637362665 869584007 175193340 783224950 324907857 514111675 57384071 828683772 29364240 76380223 194023483 21732091 164151633 654831841 837906296 294290405 341177311 118464300 762741545 423241140 108721925 525655230 77534294 987754404 941863134 608274475 795662672 424362767 147956873 69293285 317426670 566627683 978331580 512247895 969579528 528051133 914856180 393527452 899578041 813587412 626907616 297696166 87908736 598337897 365684946 501169889 572960082 591800083 984077319 402802365 921172351 128145163 440667570 60901593 178297947 997653787 416515181 544293784 901874280 164444511 910957415 506223682 203218918 51717146 16379155 178102658 24918948 148883456 700444166 835105735 364927939 157101702 575353827 487061978 674065008 34422804 45692153 752490289 104801562 784509282 500017454 336947171 979111608 854689159 602811408 709042545 71719360 273047210 177266430 728929444 86048302 444033353 485885322 749442667 257550849 897031523 133964922 790212549 750431147 499201860 9384165 998042228 65813044 443108860 386260921 101558875 645528500 649426987 502176864 265361184 507941022 839714048 475774978 165624730 595753298 399837365 559925414 278375198 350800653 108533360 533076182 604236508 67833077 850810257 21832302 236412278 68983398 159203140 841440811 542540318 418091856 710505808 601939204 202950232 805336891 723879341 387505439 313965684 329724972 568326048 66962896 840146832 523346979 327690259 321631128 674242498 282010586 34451420 127397989 700258689 91196070 753634599 955453191 525882061 760815386 562927928 777933944 280421460 770481381 232787901 581347746 472723945 474193123 798624862 879261676 641318770 318832019 132555038 290280892 241151146 732192799 747976145 280063012 51388129 586168154 845083336 736520962 932257364 836084257 246992021 985170210 742336276 422356699 812390021 353187112 368939049 476663339 481751620 324226982 491131917 326194648 226673331 252410429 486613748 163956389 495124678 620483378 319650194 510813877 698442737 354076582 569452229 206607972 342509776 344900785 272718085 289169894 183076715 544382498 586730692 810253075 126747720 324784954 578593422 526465748 250895510 268892697 651498145 485854447 711993156 158646317 695054005 113635378 122038050 251145870 992660630 907347702 997448893 805460298 133549742 116321500 663305482 438869749 10890148 551695354 437354479 756225696 374606637 312647729 69603509 583929444 248046540 411520762 653856659 476997493 155216853 477809962 620542735 91181914 274188505 717523431 279886788 933031033 667569480 698695032 253252646 461996404 767543368 655378904 335047047 394357453 619581359 222957228 253227105 786476182 593729440 444637563 968945403 745268179 303614191 991420555 534543044 670281509 891134077 639837166 203779044 643497806 586013534 788098517 50914382 250789523 712127127 420913958 858610042 919102121 825786823 648895933 761224112 776433004 764910008 161604443 425235346 414358739 800871592 249360207 374945838 631595212 311068775 849559225 46096231 266038594 204531585 69753415 929197131 739477473 433609308 479427259 945464226 449451802 450290794 925693931 262272456 817780114 814710004 306601673 545217686 681186859 572891269 490477628 136849636 358096172 941103812 461175616 46137608 32072039 393658292 991190363 841973491 521313269 23026657 113677656 683170172 182397271 673450450 376888326 280125372 5729427 362390096 439509692 174572364 122649338 195166779 621316143 74694940 738523370 500245300 116334813 53359457 2632608 213722479 553872411 428993798 443160680 698276595 234329907 659211834 644697244 955938708 873720733 498969596 108243715 868418162 978576058 176551210 79765866 309213707 520751327 787888013 734749385 958444227 435870462 349187092 842561283 353427352 504132151 962038437 182206504 183874444 530622558 519833832 986748632 561531932 479510500 513167750 374969904 229497529 384978421 905340961 696609785 788416395 390815635 117895157 941255433 151371510 162337931 479170169 903791819 560749330 876151495 67896534 846043362 624292810 125790218 440930064 893373491 586755411 884230453 225182516 205543304 270669971 212166259 338637719 372314803 745224297 459718788 316039674 810230456 646698471 472387314 81059695 280403542 600031585 372540926 880315158 921026477 588468563 57639599 284950411 304188008 806576065 828994334 382847432 271319307 410420079 317210046 456010718 145963461 812523696 616603415 941450286 284504364 646834151 363035563 623648253 755082745 848776237 551461020 35529384 639291005 764680778 74627827 337335539 92962136 108427908 204291539 283133592 548141655 132255326 653005377 830726750 472177576 406373743 299042205 941459206 36395480 320023334 141011967 438899571 616424318 485181707 758018439 33570521 135897235 681216928 673557245 663804255 132164436 874606099 573898487 843943688 974647218 154682061 105603231 879041719 91383657 161536012 265103147 532607061 268280425 381470956 255592623 117536817 983489544 237777591 150170392 873063223 486274787 52569034 307876426 188876334 347936712 562684477 207688937 944618413 853151951 24814653 785926926 487135126 39279530 582049533 199745115 78747512 237375371 625079860 778203094 872978240 495648146 134509367 139999795 347839790 295987907 576638137 961626159 206680750 215096964 972880612 965198580 74248620 597958138 946337545 569625373 111050962 585606585 786010388 194282676 640739215 148221424 163171401 514922620 682468201 776523706 45614964 447988699 355390497 154743335 840171236 132205150 759109993 87834684 313039041 739039267 676113463 939774607 979023598 302552067 816085113 972162414 188716236 191898813 996024156 118103891 351158684 483920844 121753753 702978474 588094344 744203948 117173 705436059 155732845 163845882 786706498 635408046 422910205 657018617 463889426 489902484 484685020 452728347 550049760 713785474 796517037 320414000 593672515 226735808 504434995 278709788 126864102 197527464 569657412 586157281 266939108 881175947 585349428 772262594 26391440 656241081 621807353 968788916 856387088 913714730 938940742 203203801 117421721 463819780 936890746 73548241 124133373 14885182 756156755 237045727 770372571 345633175 535321776 54508238 429697890 744631123 815439038 320242345 977055138 287212431 258373629 858503332 664128482 845343378 475224487 622182102 26644659 517468371 251339191 605725152 315576111 989828556 258062908 328674430 942002014 118317654 21031383 329728191 782451464 448148025 952610199 671995945 925828786 674202031 758617760 336642722 998765903 256340033 684683823 236192591 865284280 669303948 111931660 28655549 551233823 139528675 74894028 297144326 951657097 467962407 729344057 895902259 691199402 948341069 37476868 845894711 748982374 183201008 967913921 630669765 176375458 593771512 240954264 8054133 104467161 740045776 980754315 667204462 350415776 701493624 5177417 263838996 245889662 7459185 931997089 770933904 6108961 163001467 302585436 148657489 820091350 924145740 596950667 156060110 216368878 535728776 501143173 433094136 681583610 31707095 659270599 588338714 845708831 463793721 609882142 60474748 288199091 436648053 504279384 153572636 893798247 269651999 21014583 964182187 439865796 223016452 168684436 407224966 23908690 850079821 488846351 152353062 896237112 882861811 301098300 567934750 962889149 242926558 451716638 855298637 696765965 813988551 530234576 887459062 381368568 20206836 496206150 453388424 459134417 860377104 969088269 347189181 760173471 894614160 900051201 857964054 767248281 26231978 252428570 164846542 975501994 881018271 179597884 465989935 160557622 106786705 107604859 978228141 923235055 343336385 998140242 224352846 467977410 17634398 137552724 666514941 66648647 538852203 674141840 534903012 119858766 426087749 336352338 687097612 930418818 7226259 743574329 806430273 221817650 880700385 671542053 266310329 209174936 374520443 270026327 852455536 904954552 155909141 466863543 265055514 18695898 540169641 361702294 202796051 913206644 751884131 303459804 927611083 224544078 431075982 706541772 250043980 160714867 731864666 685127410 180321936 946628051 742100545 972767232 690097120 222004383 815048532 220228653 905334170 581912538 640173282 274887642 786604564 354124623 358629121 706742458 57531190 141588712 117025749 28170169 725587993 575558341 300528561 409616515 316804850 731521077 901333906 349140631 290276571 781632106 828300554 219780060 151028425 252340472 254933079 626181261 831745369 481675230 181149519 952072097 428463193 813644826 242103266 392881961 648454780 887881084 690652608 948457621 20058671 88643157 75635866 626876254 28104295 798627732 200179989 815322645 444932487 506212119 72745664 292689708 306254689 413490803 974222299 983709427 299053103 735814993 184711139 902330958 372968778 281836274 90436036 390659892 201271802 520796215 201658559 803383475 964875581 588212031 744673073 434005073 241443229 109271784 206127667 297075858 861204145 309232364 831593818 389629725 331954609 728285508 192647943 37444623 558254232 737534642 600375148 782278444 642487890 407969219 871237106 634997443 569966636 109207407 932411694 893542878 913286615 146665799 672467299 361903598 481848702 627432946 16341272 279893381 969146356 505930037 812363897 922210737 650753780 140080411 456204180 424203327 834388758 821221980 317786699 724891705 315816704 267355491 405311403 980868802 178097763 351608341 980793900 136351411 11041954 569678536 543154043 24954982 54648082 337507741 310777787 638016959 27009802 707632097 614929099 669084263 757150679 643643865 562457777 468926427 701251100 766321951 702715936 491555822 61855873 143793865 472913161 857949273 308723052 900798080 89713548 920184537 734944345 234072170 625658004 71521700 800711993 937266005 986760365 843654256 185913750 668192221 86829670 614569003 836487520 17576087 872759863 290685344 275291635 456705799 628222313 715860231 49778622 229912771 753519093 149742283 764429583 668879887 91347536 767251042 140267702 780551396 971756490 347283751 411584603 941932999 426997913 166799526 625422637 313020809 543388141 552037731 548280984 63435346 289420673 989638985 459087873 199257292 290798720 345875236 864791822 52480949 307802188 527308690 333061188 879618708 674248575 597431713 18171691 608537704 997243898 122661532 789536926 735293576 208298248 532534655 676949743 849706410 746909726 543174736 158744150 260707403 165893778 575774544 857403019 697860859 630262862 667307607 10252446 598217935 181148878 381204730 583305433 325361695 659079849 629774853 864282940 755257188 108076317 465080856 926014974 462396667 365309504 623178070 958432259 725666434 88609153 932585857 936244535 885570719 654466796 77616488 318316728 486250742 147224302 975822108 423412205 937654617 31621333 148016766 813931352 735759537 302379067 994235905 837084100 464437019 640374998 292958123 50426858 626871139 282332391 85236414 721304552 602135582 108924539 362009709 534692365 928358916 310097226 349910319 949761268 457432220 602739720 178770265 105672771 805961427 451052820 460418901 913111796 47977572 18596373 498307624 966060395 772005816 545360950 286482189 155711801 177014930 807577 183946131 272661301 835192224 74456312 668871080 54666322 693796157 62359823 719542384 729971229 255909282 658443472 592160287 554411069 214330902 60169094 180220008 360386898 141550019 561124794 275545585 237575591 224276118 297952447 511570634 947825625 813662213 874848291 207735717 995237630 43063685 452236065 815829858 288843077 66216806 935336434 19486906 280300233 908440467 417810659 830599132 672757380 771086082 431801759 582225537 10679190 920448626 377957038 108493846 425724316 750349424 42570755 366119311 93241913 153370040 811286798 928652 475213979 843703890 450855336 350236101 311581256 172607735 817868034 261455422 754135320 409002139 405600472 137242154 756792373 643187280 267600230 516293117 283680905 425781423 646698962 343971084 671334393 980901744 682946650 701684590 826178553 527281576 207779270 168733885 932505599 223918758 969781021 731738832 5507356 61719426 432616996 696391208 491608729 921569443 555692024 715489697 231240542 686821561 241857939 172676579 715677694 394973932 820182851 734584668 530570618 847977731 331583520 451861416 37027022 54014042 121132399 578029839 374234985 847789808 821261379 397416211 79183384 179152176 579950582 267606755 245756595 879438247 676785779 36470835 578379918 361391825 915651976 543080796 666220578 901084743 89020073 948435539 788351790 138714602 301210855 670761633 390288014 368718377 639563085 588962558 293738055 754700589 292511526 898211134 933091948 820034561 272096685 518437049 605142362 521569189 51642987 129131098 850399925 280854551 404733416 998474953 856969068 337547311 722914059 128883289 856501028 493332849 654148404 962801709 55100257 242176109 503065350 251981979 439097822 190827457 598299501 134078662 142799817 716463503 469308179 187821930 886768779 763336584 575852597 800372824 218380332 922139609 741479401 663152244 278081322 1508885 587280140 922908767 433092189 777601968 780401108 114409624 787247997 591166146 45871294 621417692 543207044 887758590 700231708 731813741 599418813 276153797 266663752 518479295 630965497 209839054 31322263 554574871 89098756 571930680 805228775 525041603 631215315 853199761 161180213 619418173 38078900 732602379 271113517 205200768 170904602 110417946 856238436 490884265 260259991 276622984 126873531 191871670 138873045 72964101 327509651 608382842 770208136 420575451 108484574 22390180 253568448 957000431 519952839 100405587 852913468 820751207 58299596 237153865 915662687 740990774 209595475 153879185 5566184 67135319 215225516 328931109 635109383 986985359 580061266 754447521 691287137 474124294 134192112 362113815 64483712 614485720 260996931 441336710 206727684 78429950 113201348 26555316 198209479 146079608 52790368 190320193 647420324 189172784 757730366 297798813 223148450 717090136 36308187 125867798 943708311 901568006 968458485 329349012 337362515 315045741 948922453 352572173 27006258 704124208 651697642 543025592 432196580 147360229 473830918 572579680 51759107 161530408 425762662 49889442 105335049 84931197 399340166 670379905 306812084 866356536 990363407 999091857 679495835 657374135 222139864 848488719 945633439 333943531 260037878 688216465 994060854 971937121 956060055 846772292 701645119 242893782 533302740 656365771 336966561 858719025 85686006 879173117 515784125 883062644 217264678 43315919 10894148 921497418 415086036 154271987 159639928 758492824 506415370 644507289 847077129 142913605 921607730 227066971 742110907 254799580 591732367 786176383 75781462 113369743 434115949 480084693 781380049 597891085 704892914 805089475 86640192 747692906 524544529 219348262 5816902 436997237 420227308 111655209 528646645 831619489 632012808 775606740 142184172 826657716 819592904 814168739 565022906 590932137 284984956 118309479 317830736 776035900 428488064 167934518 215817318 912872099 829902450 811825667 759666723 440762855 245711523 150296249 502997542 526702390 716713572 954054992 279280945 538386995 321037857 26618153 673725627 354330784 501608045 855617563 169263930 699094013 78504898 81648517 296225636 215526481 26019131 586804348 530336546 166896695 255053630 940144407 611449543 284247657 773831864 605464226 948403004 236827187 160317974 272175910 640789690 262947720 771331233 351110831 782585864 189473983 613098308 259072736 362501199 924462001 183031801 151696740 400750873 439102091 772505130 28369399 576151503 866473685 297258644 351291708 242750294 63000789 21313661 60950092 674886138 86577208 496363031 4578682 417790064 418892343 880490380 729744487 704343802 117708667 113655771 30534717 80919879 352013115 121802579 213752420 537071843 855835435 508247669 341389930 497386178 40118307 269118455 805286760 682494660 724279018 254966029 57887798 110251100 147692380 834520983 107954524 166551895 238846476 849828453 339190436 639414225 727883345 30734957 649690521 371762495 554510151 323618798 38277627 80200214 759690873 743830306 690822190 489029580 715485591 716832433 418019259 640915641 389976021 883891322 882781440 68295050 973448366 11093085 479131042 36489341 268394975 80125220 192275985 842471684 898919112 931372867 182503147 774930879 228106739 341588566 168394475 482399919 637184949 724113276 879323410 681891587 296581479 956963343 286929562 634521101 780790304 822829279 972485026 913393297 91454459 657648261 849698678 946014359 331106493 707371341 806487067 558968440 494261849 628086839 573077759 694310649 939216165 828171981 769916160 870364032 632793254 182707799 866172056 953244542 155863760 197616692 310069870 591041641 335839249 1400917 747324481 449613566 747793847 977323899 748143337 8734125 756760228 806344441 152678482 149865663 28510689 199672655 228926592 13712257 599985377 333860986 673414758 810544281 946653690 717302444 767257993 965489748 775300377 805522077 232546566 273195714 465354796 384289919 796976606 512656466 428364377 276225021 77139071 310859125 523472708 135511977 365014360 736330398 658672432 581348018 434743325 861293731 973893689 226956292 316973607 185848153 206568353 782970370 889523951 550308833 632961613 556963402 787624663 317654629 141678382 941063584 756797759 253116032 4527085 752756604 806704637 916924240 579259006 923092345 706424427 975030486 173715279 536535864 226527333 932031513 881539187 369982445 697642885 651624178 400370468 537854648 716424100 668942431 609024446 259202752 936281323 15883188 371526706 145228752 441837712 139125486 910234922 216895991 295247144 983631791 50378070 518154993 557862306 644894308 337544761 63451039 171812684 481094450 287378626 807633828 668343467 701824995 206642050 899810457 144351615 941659206 96896713 881930954 127315638 206567769 987439324 962066004 270232432 157033801 41817359 599253826 986718383 494073538 99337088 232906467 602580012 86025242 134156049 420070222 286474148 249301145 9596047 780677689 592456840 267844590 61378446 476157213 547905959 127956955 176476918 109714318 652209312 53286466 279435272 884937176 425600659 360373124 164988347 702937681 448201009 737081101 556897242 852849100 145639887 171319253 541382509 10079968 170115496 770702389 840295741 175464406 695501412 375382136 598861458 539199058 442926150 863396332 634010251 692243311 599602791 415972198 509981685 101357202 163962581 56773297 757520253 55886103 183451584 745624552 289134283 237929169 592076680 852178090 815525393 479893620 739811850 275777963 537590948 698644947 100816375 1575485 312732002 978800687 803581522 838238176 242762107 484210107 47906108 803614408 586739665 226126773 785880990 346763621 583529047 85256780 40174580 723993558 41232809 725514818 863284499 427882616 927531738 303634763 1986448 22158806 489289112 135075730 511574817 104705989 394129767 430090417 259536433 61446655 292200159 209395763 281904331 181319920 896039292 454387237 863885868 444036577 458464902 339539595 472089842 895615053 206075082 812895774 972759332 713213226 891234743 396580481 524777555 443308822 419729140 265626881 191486786 278842507 125667330 955388651 9012326 142815284 697756990 938167402 570586242 948920027 902470151 977140726 384614145 713255841 284243828 757284116 856752600 983190179 5975171 308398958 344368552 818575659 532823394 257783065 69739657 906939047 965871335 950661875 965254761 246108658 492836530 523454987 682645203 300457923 433397670 6606496 545840654 47802913 25776510 838447782 606305667 930770184 814158744 721869440 236168885 926276240 366828285 904262767 773276160 285946347 616669650 721590520 520542076 646907531 376082961 605163333 9116564 343613108 275182583 556543030 726204061 652147189 852487252 456622252 643682051 400305094 790371845 57050679 678218962 628707017 670559167 303917713 490974059 221333219 902399804 323674282 415322267 787090860 178607454 865760120 961590953 579483202 192545226 206166883 271707323 738930826 264481413 601715408 912104475 857233348 175216945 327716571 247280641 647825673 917868130 395367241 450342253 159216472 815524237 897232513 496848198 209094280 428152775 117050497 891285216 837953607 305329282 386422056 313062896 590500412 739014870 283095027 353736618 399208640 561342670 420200357 612216357 263455059 494177779 246017231 236086303 182511940 908273982 671228904 445602007 931747171 37099003 217561932 564722091 170711609 874754604 443564216 372169619 914522994 847511021 462735725 226385859 594320716 567759311 78304908 333057724 372285470 642556628 67539752 316724570 340025073 405071127 821096121 363668304 650551423 581212670 407791949 86312815 976595565 402173441 770720495 510349011 791709493 942479217 517238767 549956286 107298597 74001080 84307096 867043347 405399734 893549539 506432562 230847005 27456700 90409736 169164406 228218548 676541920 357621295 244953417 959640272 8671798 523959522 688272201 693425153 674645827 399756079 844884768 929819838 462873515 455434270 627303101 921103661 865775861 480254763 773837156 215160413 534967395 589366537 590552208 899912124 138073613 151279962 92535128 953989703 247685430 516542395 772937230 371089842 559621042 445061829 515699334 526016350 835104467 766887511 207336393 46254389 870948076 43707787 89412806 962997821 942996227 127481442 724644057 891378744 281547099 786772377 660477510 752071852 128285361 150382037 74723955 46662199 195350663 606875443 914310884 60101388 270178208 424352507 102647736 711574611 677290134 13901658 257988001 190250513 866668798 525164580 143224137 453515403 374842265 667995408 490930689 434517149 4808407 84708788 143473442 126897536 233617157 26241119 198277914 78703667 306370649 681617864 592406362 516781274 779858138 961288865 619119752 895940826 740926166 889064222 565564631 729400039 370488172 773011663 451927845 719574145 355674965 105291283 267693566 132445740 50313164 445641039 720071193 380808039 206083317 83764212 248149723 847753211 253155982 392940753 187170031 30486736 196036099 150375426 976976530 136601771 464564492 849394240 962356332 59850573 74057563 996104603 855730128 188792429 547347037 871365273 473161694 393978622 840115029 120243753 536161236 588820146 351011080 212778676 228040418 697763107 302764980 775430413 978339788 70926909 191105505 575620390 579951226 963480507 8583639 88924496 584594842 166820259 750382771 470621397 789873725 247438898 20244754 859583927 248767109 121367747 637380267 746954254 732605322 288132192 187221083 950291328 693667120 519368713 377826284 974500639 388270140 104124632 235313574 563161239 384184624 115486957 643692173 261911459 697037927 262578243 298346198 202581278 78504212 283347573 6849976 63287267 647060688 956656581 72957026 847907850 235303883 974332277 864930172 958937368 463570927 601424828 670493115 512473716 80012477 646474683 886324639 769910361 431706858 706356482 1548091 205894064 481887590 873654829 270422556 260687209 588910962 26242065 478518552 475690669 316102658 744748562 317576552 31206186 244617583 847488459 153412413 23496451 331685144 29700914 211488879 615883172 915910222 281343084 882820016 978894361 581598616 561022452 122527043 95293724 57625570 44073264 269770998 944087566 517406336 442799386 260558311 478792812 166111002 184750436 867698799 9857715 854025518 865474925 772120727 386492502 67916805 958739550 813095439 706546343 516944107 271888834 157797278 783776681 182952349 239239314 347390645 114871310 68012048 604667917 262840658 603709590 928361152 590470316 536510086 177570201 739896386 201597850 846194496 602587653 909247722 369715086 360531564 141005975 632668976 183737446 934905817 714175250 717774582 217899007 780702275 883599638 550166550 842367391 318990631 284867916 760657357 648999234 962342143 236204192 187381848 732186490 553875062 221210454 604975696 635608014 821291344 172299100 418685091 815103637 143886760 625277759 251673073 920188313 232192409 677867607 117584022 644313680 21227791 449304218 331388695 199774141 681174834 101459085 230869187 892172167 404200387 871181764 797990194 533971657 242150130 810255016 699777991 362709304 96972542 863332752 858478880 24692967 514460695 482979403 578235618 477194179 190263181 929865821 936446182 466740565 638481545 608486149 957915536 978430898 305969349 753062556 868667558 180546535 403768877 539601369 133195076 917603505 838197884 281920965 979222313 117942117 392722162 456057095 305127833 831147668 880033530 913307664 172439277 86732943 309135800 781159101 35826294 121504233 173196364 881796396 204212193 38527342 838776901 514487006 508947797 960036030 349233375 13083384 419469965 934987155 181422521 818953837 405181928 880869824 366491469 678532094 22659555 717533281 362732590 932891177 947544070 565889727 51998409 415204841 55811013 112058007 652483111 892938879 380432252 904510643 442489842 484825680 293359638 36797512 36847483 970238134 544219424 634144063 937972601 135577861 254370164 223833284 167909278 407004787 909125562 671295454 290851806 229343074 195873266 104448703 111050332 793014321 962977213 10892704 88832618 511574338 625357284 939983278 651566421 497341055 103905346 400670712 107452260 510175551 208133783 356484105 301085662 130399769 515304436 912413355 24423682 498450685 384620509 221111562 820296243 164173098 365243676 182611331 13024209 897807773 751250732 796001090 791569939 650740477 603052256 506446254 267303075 674340298 541773586 257052250 854408503 982307213 220075837 135671081 339728289 898720378 109863683 667350690 300927683 54247083 13048451 417145516 47280940 837052045 694693339 140127812 610373849 696950148 851505844 875463796 275234802 634912193 717628212 55566935 396439817 19086270 87544122 706853369 758290172 664964520 167151987 82441178 962515580 111452273 689537898 90671261 748318664 390865581 978991006 759658443 257194863 378786187 485809890 230977805 295780032 137840577 474501630 139037774 573291072 936275414 566282097 786721526 282638018 138020590 718374133 390889033 298377441 579057293 643150053 894148450 362553671 608691724 953098382 984280882 193846532 633461486 110561209 415346717 919069395 483458395 786550543 309752699 983753635 98272514 658610188 302439699 829568646 515476764 701022880 532851759 228956061 649922077 116161253 628977264 691215782 786977000 243926253 505525094 509137711 652045445 923403793 702176621 521674463 772360161 571621016 185088422 630872373 914572994 844754483 407642490 322778262 813735285 739272701 477688562 955434042 621726479 726535196 185739403 943814993 481797560 721777771 934264670 431056712 924094445 424021212 410322392 597474166 20739332 465486405 743619737 885292579 959743063 841537541 610410621 48643787 474666060 620006767 176739237 314758614 333131515 289903824 315719350 313062256 612223132 905030127 313670525 955179798 483470997 416187374 356004322 690776023 483694855 328490737 99243361 705565066 464008833 565196687 121927863 870642481 155015025 521347511 453678159 429424072 778394771 416542022 165237572 815801879 576482276 628249310 767566909 961969187 100866492 170969919 79461740 976431830 918798976 830565591 44561666 699088561 613032768 119487801 424479338 524072448 142983641 643137177 755324602 187306800 628681379 38757676 45174140 903208695 687363486 582206078 205776121 710011564 712683053 355470437 831959780 231597102 63938553 592670199 164420169 291762221 291232536 626706625 839132065 937670241 333161935 959534855 807673301 969262800 910614439 213978049 201026957 820692725 112281544 471938278 970187240 227652384 713909155 162821694 146564173 10202704 967954671 101397541 156406999 228765376 545090708 784147415 559582489 646227858 399323529 156281930 860463446 27582799 192458286 203620893 98639296 256299875 508757194 142883152 427026307 217171821 134568669 156605531 717718528 533551450 141077968 623108949 715205324 429854081 31229378 100979536 977123427 91039525 552590194 618978477 162109324 75228978 33059905 859954625 267406903 751874249 958966447 326627445 627526180 348143787 520449507 509780840 878677864 191268621 492519737 94727972 635614497 750501207 629827434 70844102 663753427 115078604 120321533 521247754 456196068 444829882 98153345 54777725 400574649 374680313 512584983 235577539 247897519 35840254 635868772 823789728 23935160 857577418 177668631 80408257 390642049 132586023 512873915 515654623 86103970 839462643 559744391 18876831 128443542 639079787 674229001 813939001 552746868 676305883 84058661 891594872 307628179 654622154 289977221 302014613 759242134 886256664 490171833 189423332 364513766 79757946 529000857 667192258 761035064 472269148 803494114 389992078 462606703 509346111 363970837 975489888 224795495 472731625 251006004 472641187 896154198 8219422 683368010 653017514 905805281 72695831 159986871 918220781 681493773 580954281 756283356 493587428 975309376 810761712 974213408 308188100 942368676 17669238 639631877 292725380 110854151 736897055 522005841 131871768 240569801 743773688 689583517 300987029 448323003 261095508 744553164 603563581 540157961 722908400 442613377 155636875 934587994 1167189 563054361 935223408 634014111 500367557 590916316 23508398 43687436 37533595 290974505 820459319 577440333 941144542 266151924 361351446 786689528 946406239 106683262 132547390 77271288 613510264 468538935 770559371 596486734 13008848 86421367 938867072 666880802 752717283 161875452 765365820 772965843 486505623 23236728 730860688 240133657 645326129 765147196 474396483 778131441 509869202 34026827 878295113 363855263 342582870 50700205 908392994 231167054 770145254 15196431 995716856 242656446 361518404 446434100 277371674 391452218 905174455 607768813 33810333 201392338 652313246 286044675 590076320 870307348 273424642 68863981 444969663 807726815 976976994 26051997 396608820 246919103 406897167 110619821 976675643 795314770 889784287 917971074 395594239 795941054 324207993 450461841 79304891 889916023 945310674 860627693 580958158 533490528 199095861 788909786 979494649 253716458 143129128 972421785 88279042 561848612 218910600 589304431 126676912 877140042 133610842 613980296 102879474 299542934 889068750 328164763 132935160 735759053 757908690 142577643 650887930 717183793 819760609 208502496 250236256 360473475 823832058 286110193 871555718 899345949 367552109 563459476 330493142 666403917 598538033 122292824 977448955 282956381 615128692 78030169 258401693 580373733 312473169 827498035 206783092 965333945 441349444 290008474 440956694 732762127 210321588 598471887 580376001 904353414 840199824 999210544 610301500 326616791 225794363 610047761 574331070 3849838 128002212 443935608 320379665 95820248 744421687 147799006 972955182 168859974 948223155 831050881 217616369 506758429 26680413 439729820 949339406 52705080 5021593 843525326 618307170 657765786 620448716 113529713 492278127 309413189 446186262 288608516 871172067 506571482 467404681 747352496 611851781 214023555 153032714 358078256 195756424 287361615 136571545 113812323 95906495 393191531 406557161 988462369 436121572 68370227 115188931 814549206 152609751 121251181 285782500 329679988 831263915 550054098 642931538 808228518 517329102 742282013 408336928 295905499 84238769 342331837 378029584 260028389 446544698 212071836 652201610 405703008 341265034 115916079 697513559 830288330 36876286 71061374 547969625 942422990 550950754 263520147 465009970 966776686 63143856 505715596 447801670 473416727 720096478 710291494 807497265 8193938 627019330 26348848 228525112 926772977 138202414 252747782 250878719 512163297 222654836 358324598 770249269 239190377 419759498 44353921 269492235 69279691 131081021 240974012 755914385 810528511 528614803 548227245 239209074 567389424 854590507 792494999 158779589 163988688 469039738 102613051 158915462 112376055 578272892 532405170 764300503 704488104 347628882 581986049 134902505 498120631 39614473 655456495 89265482 78868179 740536434 214136275 240665260 586597507 872561829 835764218 533218436 255152945 418631444 402665169 259101570 170399949 96348985 868681606 938005840 368770534 34958797 790844921 752326049 413273205 884460565 445544693 599625488 24541745 682048979 184452530 987606371 112566861 81758948 924151242 64763225 17747739 550670330 390548505 745050440 721083471 87121488 421959026 223069571 997158530 892191114 64335024 569761437 405145713 989064200 716808127 512112619 194133480 330494329 71235407 725477859 924290084 803095147 431640030 992599788 769056755 660032519 140251398 543781223 625280078 705520635 469589499 711959426 349954436 786224396 576797686 35425066 774362147 16660079 771562514 112401476 801720317 457156194 16875006 69513703 381178202 349471580 107768330 14817547 54197702 842260858 231449671 253293410 467308575 202593454 523900576 167334349 874884150 349869264 545186434 354662705 814182235 798183581 430384817 293292108 809042725 461580486 860568564 293428477 268301562 516597516 939129860 897990217 866617531 528767724 607009347 340380411 537240873 462046374 226618415 419287528 33864347 680959248 737649898 294951649 645278582 249900667 860449907 551334721 924148343 179869686 611932680 117261844 610710686 894084495 965355624 370532028 13794157 11492632 721421963 650099254 976678771 713188183 264949075 399787884 681945764 984482299 632982384 522121107 829055918 475823984 129130199 303528733 514174665 409367634 92172502 440498610 208498928 206645175 509459033 723657743 753602628 517937804 748490286 954497099 137501370 14660337 12237473 379628056 77778848 239358130 168654134 287289215 320551147 600813636 652261621 636079665 500443654 163109935 309072476 75228396 541094164 92357111 862439603 186416270 809171415 493559771 827166626 398017280 985780367 755491297 356021141 368692448 440409676 511751148 6077516 186741732 580528618 695682652 24623022 413492971 90895641 404224299 276337633 738357627 163589689 326817360 292078349 181729548 585204415 856293402 92922003 552685801 148953499 110044794 307083290 679142647 402963532 370211879 27360707 992519233 274116005 63630120 338093603 873319687 699092652 440278854 139221929 979190511 825117094 72767832 227472659 604516776 825839798 191708459 612516191 855356115 694544050 371587520 626817655 833635841 780290556 830527410 660717217 535704085 541775358 655632741 926513040 239249481 39994040 970678845 532542839 160352804 195062726 124345770 414701435 25893986 148368192 209017667 895713425 234436577 491945335 225135975 40583212 552544794 545122291 111524686 87090465 362059729 396903675 386818085 853366168 909786877 200922380 36654005 275554580 611893731 349885 968561276 968814253 784038023 61597612 6736053 722434 479255483 92291674 916621723 827661465 130772747 562984905 429443781 213506834 317108703 957139658 840071683 287323339 749085203 380964939 749143700 102011789 211356647 189428723 303255879 197244237 179969381 105627804 504990446 656020768 745210903 578807412 880594813 249156641 794161430 568836672 226072435 416456676 906012926 11981756 65082267 726642675 144851608 766111601 71586722 179648948 976170236 751040567 696971112 210272144 243749898 718605433 598866257 237589542 63767310 511932813 158406435 377274867 659800994 372739144 845423932 330368295 815347183 436564782 594279052 523930587 306575838 642101062 126548626 321269744 535081938 691479637 138433133 153010855 491757255 671143688 81253078 237384841 263036716 677160022 64083516 547516522 815471282 108616563 246264808 388823035 377406038 56464661 477119690 94789734 882717474 464142700 152648899 598501504 659542028 198076732 401881305 229385717 823945286 837481669 519041250 440731796 482933159 216260765 873104177 63728418 246571346 345211535 66014489 893086206 214263711 623037841 103556467 324923860 215075534 428858392 27959797 660888543 532445766 246690251 283394137 22500815 609427728 6068549 182145413 10296920 953498457 216764852 904969656 744270652 762447034 244746935 886223604 590382242 284825933 287930643 147503902 636033640 268443229 530421115 164050796 915665093 6596756 511950664 420814583 66177720 335717293 980500083 879873477 518607115 295429650 981291165 583847752 818552107 686351111 293652570 9897877 451470676 29749719 937358064 685206170 138536841 877421531 774468077 226369949 792838926 718438495 479098629 109080066 53536268 196319604 291690193 688275381 804266028 701965945 843695100 89446792 123314119 845075485 758936994 400671976 938856364 115294825 267335848 509295957 423740623 987548486 868620898 631549578 987562251 451818266 696654116 412617426 879695807 121414690 17460910 370204286 731350041 274421135 940089958 370205957 367151485 615575392 83261776 751867514 417843052 437025637 61155263 618188575 353431657 97699924 907936927 830614968 225607821 709862039 100659953 69411551 698258429 464066864 481097541 483401745 39088734 830891351 10070240 506015400 716211318 46450661 647217397 121552503 218531827 434405767 227465871 171591991 424372139 724801354 898657564 335980978 564825608 535268694 916463748 172630689 489756328 313177569 234859600 337731208 601340942 601297673 945264605 119687451 672052276 933375601 858494030 369837488 577147148 29422322 39049297 421553512 180439207 903404237 93424669 111363675 432687330 286065756 332113087 858721407 244869959 116456028 676865952 514194630 103375740 575853199 660106315 432586932 713064475 6910400 828773310 764062418 482573135 517301238 866965531 555901224 450447562 157359647 171265911 590512609 896023493 280140216 609337112 328408991 108251990 163885923 646251723 980896726 624840018 356520019 740638653 711176185 668818539 104832122 901668775 282758122 84666561 857439376 396990026 277965349 795861141 582800842 163595733 658139392 806069487 320639661 87181014 763592206 846648663 780436434 491793712 988854310 123646588 190613206 890847851 404534083 874767215 689922767 54743917 800989323 243664801 437834737 53588706 129796541 592431232 83847155 472033316 842946857 886574935 441610035 557083035 20992135 36116493 594169199 472739474 598993403 930964153 898830024 408649058 439024250 411367395 233645966 489961551 743650036 931743726 827885884 612850267 19345532 806783706 648005476 338567129 866335033 103703299 237176260 66173028 276552855 971299021 23323974 65177210 207207107 719322004 190745386 191500291 265890164 949928819 260341003 847749628 29813059 150729957 565471232 22834515 6239910 440188548 245176905 718678309 463487789 278589395 193783449 823832997 728900525 999052539 644094797 352872783 640591915 188614745 511895990 946661504 136650269 569382472 71902687 143909099 940572578 84820374 425013968 260154127 430592037 753736478 629546806 381796524 458558370 130195319 799825122 46243838 725534297 790285209 163126919 255734151 293205923 247367841 417937602 467492630 372688693 638844360 116758863 569223202 408399427 712208436 397010368 251304229 213186285 250953140 592292975 749152296 751457372 429129963 329405140 261916010 536586670 271172463 2487873 840369501 308651791 240728213 511569699 321991998 607040180 480877330 776134981 646686581 795774884 644578404 613215181 19178433 626221805 43332586 783375359 242409884 255411199 47126027 914598843 80229820 856828822 797093921 544328961 202639001 303263275 42208427 225325384 947678078 484460122 149555206 134487124 384385182 316653698 374113773 427874396 189307613 600349503 100089500 860467669 96571844 668724173 421886580 438762637 596051527 585293963 14012911 420532057 851729097 745786297 269098213 238200401 520511947 871878263 259423746 495702183 115092132 19353330 645899327 818412151 666657609 452899781 56888581 804526422 770856658 845299457 510563619 227948486 359981952 56281004 234119208 177932904 910824452 125086516 675432410 975625645 624641221 387821272 268418053 854746236 670462063 351437817 600036977 417714979 916696986 285778699 381197819 636414398 198870606 143765505 578988052 210314644 872803205 284848631 246188057 844902188 41856076 837248761 696223847 664919951 167367936 489845084 981397702 335086881 962797211 235921451 684427103 812713240 799529854 224914757 265675325 749318528 256664543 714889989 596092336 656711148 55387557 750356149 442616267 114244034 706612384 999029473 724150387 249483838 820460773 384738915 355000324 429279498 230682362 165978178 782732262 272566415 165314104 862689725 43372579 110890971 825727991 300159621 327267029 955535624 406308207 840825611 715404170 222134093 128890063 242439236 759235491 926893000 975615368 243282106 608175974 743069874 991565253 524336066 810413341 910962162 187004153 845115610 764268016 615358482 232146941 448798052 283121551 733761244 81103680 228877134 778979133 466705588 975347068 896830485 372359731 997868319 173685305 704014277 879568777 234230364 499180776 947156803 55253773 132841348 541581356 751945223 861177979 389229741 807009517 565869462 376902264 183525500 127095277 774248343 711687151 729475436 414923827 57595185 221456311 708551527 204088739 196085069 636949481 706345326 319152307 236669388 975379453 942982178 300930596 110057638 808901502 90746539 6193537 569220701 769849204 142720401 435207425 152945794 719691452 61972489 744084285 329720634 849933766 976171520 428696404 888993530 855805750 718912201 17136689 213419094 12011310 596471432 256418494 765148228 540477911 81066006 834370901 215884922 220040411 753637824 73383957 294854981 623069371 600336473 230584964 497141959 885908387 724988290 983147202 73622669 334800062 890910058 801279082 342242307 208506525 854774249 113836146 707256600 568223644 620884116 542815326 547507526 540754855 535022867 269945457 944824439 237754074 13567142 44023886 475052694 707744876 268320941 817662463 9965537 123209115 226469881 583243287 683366389 298172558 750132279 232272340 112029939 145932156 701585375 161958856 499096875 251705430 869409374 807172406 677894508 659464044 781493675 16495421 988190585 27391478 384022124 902596487 53684 176639297 862632600 6944667 296394610 265919284 419510325 861615677 70379812 627490590 800351885 545041248 921356004 246300418 650071028 474686549 74869161 75356920 209769695 969626321 125777903 82429138 765344272 974602133 370289001 947297605 869945609 362470905 441009285 567244159 513694033 798568275 538404248 584690596 8870675 541945715 989728797 685306962 621127710 63456281 606851122 519340884 689761104 710275178 326849374 679112671 909902253 930398823 928931382 612325709 864288708 113005184 918681545 172524369 750742792 853337072 638981197 351431007 221758776 764126073 127399300 978092799 425150638 265301969 356196762 736923927 506035390 922488262 725989319 909569325 500132192 203595034 867123834 878797504 36150757 398272051 740914045 307236714 94294830 488695184 70895765 512760952 181414121 321495597 30653199 190350407 296879398 952968116 956832051 709358629 388773656 852397070 328335274 107229646 139015777 699627375 336586012 720475458 185977352 79157585 944603042 269744306 766329438 483193658 134597796 836718306 891845203 406275685 620063596 949739539 886996922 214087848 171095721 825938846 215866945 421976326 31811293 426096530 395651611 479820582 20416867 216014233 589472406 475686607 409954465 632051305 736697879 488637697 901049968 139699853 515482633 23216793 34387242 741589929 67632808 406694512 984177063 433691055 138051025 19671243 590073591 139148548 425724111 158362707 495689830 83111629 94291460 683664281 963812669 732664452 280234267 538652909 882857156 657732171 629048974 114141658 817635000 77219639 558187370 263838916 44292 759259199 268689880 763322151 658588174 425383425 394504732 17655563 445260753 37098312 716793558 78130152 237173552 944825609 328364983 504074791 515913196 720423966 94270635 217591353 633422796 307849254 833628363 789306940 924315440 132394451 11976177 720805688 389949210 517304903 96153774 639297951 64766606 520556568 721840846 223965388 103223601 192983004 205197370 879405504 947005174 120011878 318399618 261149008 577401479 926232868 71662292 936687431 255752672 269670202 213583833 421164199 515432911 595051261 746567195 896040794 986129728 575543161 489730239 10238296 821006606 834223875 117346550 310065866 167026706 668180306 44867058 238894876 535452837 999699611 12476489 63873824 650145076 864834603 647847721 831442585 78904257 954459012 3156147 677015488 859249637 180710853 594682647 418141315 84255025 316495904 874698574 309063198 909725378 962792221 744072942 158249893 799959169 947191084 18435150 606990822 43827343 978669916 282948065 167854485 167250012 824906526 577174392 847169106 697800117 636281065 660707286 568515852 154572369 503331253 678753715 415737841 463680826 524445858 923744559 553977639 632636249 443610061 133730276 375623808 949216030 459879607 137673226 22557153 649213345 851568750 503455419 126521035 232694885 70754705 212582833 166944728 370656075 92122008 639741177 253369123 153097122 692772259 525059160 260763928 598197486 631373569 582608736 288268364 201846249 69443593 770164933 427801298 101694253 260895826 53038324 40599913 497702033 214159480 798361030 93051678 129832059 64419440 994274580 68111557 523569099 569735698 647912713 467131544 915372532 72511487 848050221 828820850 86889299 815330003 89644569 766262781 269887121 693104199 37358074 860607101 588304331 162176314 586223581 959035096 868394069 302792561 405435676 797385575 935575567 73141646 457431718 809802455 127833406 163850548 203326760 45385946 165835165 561020438 25427961 801984904 748735646 876809609 923934261 108335730 289252914 221692501 523935709 965697827 470776077 427704999 403807228 897650050 928576287 746607591 240738280 787527555 366470223 155636987 134826200 711141511 759103021 215260374 698516811 99104760 100580011 16916143 445590033 264926101 59549125 355440101 73947385 70004953 123694325 635827671 52809734 738189075 127429130 465138689 492714945 64923014 914777923 32562691 984014369 739968596 311563421 921785333 963826566 868519901 565519923 830333156 45437443 888358500 948958613 462565218 500019642 822802424 259535333 536798651 38292792 163688535 821201826 252734715 966737600 344464520 384800238 919043199 542442000 42374269 96886966 321013349 892190945 355237889 57804765 621416101 293620122 203040209 986860422 536535709 73019919 723381071 313744317 452018519 13315885 740310301 479366473 151012958 51369135 616634061 537279162 271248018 60267923 49855140 123750793 871882405 959112897 993086028 398768962 963165792 149729416 397684507 666204753 918720476 478587091 224383008 900093427 262101218 404022075 688744638 987188101 613845799 488123875 304890500 346780771 184341955 81710957 113404404 839797416 979440628 170703218 523971486 511634687 161881289 180503925 326648989 242843761 127997829 222692027 37828203 612663790 670483234 993516680 281845881 958991304 423371716 888631076 952607091 192181564 798003742 437725664 572865075 528340534 994273431 445704741 136648897 334323078 741860204 794756329 464262567 51250627 999904278 474575800 761449964 617027298 417128071 133441861 116215474 446135380 431347171 668826371 177525778 496905123 15673378 581497032 58634807 712509969 486296207 141392748 46686017 419655477 4104129 168971334 140625602 945461408 243920703 133437032 63190392 238129496 507393527 370042264 830727333 142796854 456475239 469014496 980501702 468720320 569912011 768457126 18448202 994370852 457952708 488650634 858945217 988179884 261170336 864307653 193585908 874678484 393693909 766640053 830042508 363774032 33759445 63999706 7743792 515401568 399170913 521435938 290022978 250949682 612663771 473715500 851150822 362512043 307770906 235710767 385386672 749830426 498936616 28649011 328462725 883188469 777695809 280199075 877015408 177214145 272208228 36097292 177272043 193961675 135579682 247481255 295068659 96275246 55206561 954738486 600745044 181782280 274017619 255039740 43191145 202705635 732915145 456798882 468641713 127496983 49949286 234702416 767122288 882539409 527667395 403828283 453756 522975450 419519882 555714371 483289850 822842688 15672327 325925117 953408446 473088579 642527821 676293397 560522733 433523349 245210918 959244166 609588993 201961623 736127137 682690207 704275107 940754936 115695719 326567662 291747324 695981603 573038469 646708333 612018324 188693273 873224585 135224347 725577974 19831939 934904806 43351370 103919009 902653320 367599039 880289690 329100792 353047593 222620125 982530994 401089935 395026015 423213916 805958455 107116060 830194932 666964686 262912876 188041781 390673742 401795722 337694523 794670959 325438421 396783163 12490723 249746233 711692315 408281511 395995486 509217752 466663721 274315808 516717419 538318236 232469801 778870630 392594932 112836842 327748097 690918861 996240618 150811703 577581685 926304642 37158035 389888019 921314902 850158838 682731169 971728960 433391676 657399596 183460829 943539077 100528005 354031027 948484458 499602977 493117967 768282772 516216207 110386624 30440837 856483202 246536094 3853492 139662374 512751030 557342423 883754833 814396119 222100334 459033570 765847261 545666335 702714952 646266633 337949185 901916544 241987023 366629558 249559364 703227173 346206450 390169133 923480034 309473 388956216 658768309 938093536 246838304 507956389 403234570 594840734 752348109 70204099 636123303 919415987 861156271 952704608 878607634 464836565 962439343 548889674 103250489 249887505 189766008 412978112 646882833 129468438 294337619 115842127 7636218 130645236 528510217 794170467 242235554 592458046 455728595 775089987 467631061 836556381 851253792 862894090 976460703 475975515 208236157 364395779 977787272 744062332 900557756 323478980 123386761 271084129 187833532 84375514 982088526 530958826 987623287 770484714 292115919 517182204 977322464 856985343 134984615 25298652 126831278 116001181 834180676 312636459 380148898 442667892 77256208 294474100 310912756 341538204 254338807 111508348 330181761 745096458 273104541 207964290 275202624 33906744 213887773 540253053 232830908 199669051 254769990 661418328 414408885 319870046 882667978 376633489 137090745 468146015 35568200 26007103 575788897 135192537 425061523 876363442 294624407 813970704 862960988 554031345 11835668 782512385 243607968 127520593 896104589 900180744 6313756 177620787 727571209 214370254 801074019 555504054 136901160 809638845 792986362 104813440 920885081 47899665 891921889 385576335 351791618 69016267 144336040 708350127 810238206 565561547 129840361 547102535 686545298 433987750 615480226 25566490 860608638 95326121 456909494 691526328 124096239 41452484 53971733 301323891 736556580 340018887 118843152 44213241 579982853 633524598 25275890 182797420 612891466 314424553 991504466 378509181 577317408 723043128 392089175 241501834 919036706 931210339 223905199 489238299 683581754 986615328 689538822 842638464 996527372 758465433 171597266 576775121 54534460 139918834 206765366 24905894 728298844 328795946 334383291 108499395 688673782 197662868 919517267 380855928 63005252 896102252 125677379 696384508 725652404 252037675 41990527 505375207 647744723 401242077 788860227 333812850 700288106 491728903 148096180 267665459 471758975 476051281 501038921 122086795 157012021 145150195 178260942 74754514 399576842 263206985 735279665 937105019 703410599 225133945 792844982 160732297 332163086 575139707 62011949 230709318 834204089 6855665 342268815 139259211 546787967 761434920 833309429 44276518 954467613 420767540 817777415 799042350 965773332 168172506 451313984 863146023 973454618 517036428 930122716 363547117 23447118 126061474 132097814 945452455 237231099 511790333 991092290 360297764 175022161 696686090 904933274 522183797 238888839 840118093 232111471 809674871 497519981 827042721 828171982 422942948 857211750 244422050 65633794 241284737 72776414 684835477 13836615 257132250 411455033 171543425 171056809 925736353 451729458 828702404 700044736 738268813 411327033 929764993 305995957 314477125 589233956 569803496 659595427 213277159 169571180 814472729 374167577 250177596 790325634 57862857 129986714 242381201 326026838 14651202 650310569 976753299 510031452 536272892 118545804 548038493 613569738 360940429 995248817 933744105 332561560 584554314 828708100 276746618 527907670 717457247 839595095 351937171 187022721 511600145 613723342 603866896 414570911 93110257 39747162 628999485 27431030 917723278 391546472 808318031 867313329 447009691 694656423 153517756 476039706 135210541 833936502 637820914 24305695 29903569 800956027 928804316 703489804 497840920 344678080 97369842 968698427 128195890 815711153 786026707 701531241 3986249 143800332 957469243 136862016 581777208 583446363 878628809 588714933 386195545 41685284 369221915 133651217 790204215 319401951 924566363 90014811 998712586 101146512 86093790 779078899 103527435 915875187 244221884 808521322 514494115 921754584 757549548 633547275 105415287 993034370 553394027 649108636 250118773 784870930 97273577 193472363 464792734 848511859 186860530 842830182 705358144 976684092 445774120 741692204 17583053 181750421 508530786 452049686 21277304 151823125 618889710 196015988 33120591 791519257 548402756 538995618 892127844 56905060 848792055 126614595 775094596 457563160 979870303 110464866 155329786 442755250 233810902 328393505 614061120 735065508 242746213 25681926 715544529 820471026 416020103 922386517 297231758 713200423 255345313 41172147 119481233 997791586 942430118 703124175 233038231 240843943 826713282 832617387 598041905 95266738 277761865 305437224 775681514 178230229 562119112 409680119 276365962 314090987 214275196 356692344 104683176 885970032 666969028 51042680 3801091 895750446 590864210 85833346 86567381 779489420 27419161 29042127 485187995 769186212 768910641 15659335 580042645 180320049 896427652 873817370 873709989 82498362 256658712 828551372 823685743 795068571 8963511 843159933 886178143 825774030 845840887 360253289 271289894 46847609 514511362 430359704 912480946 160020661 972589281 910740843 578999527 741854726 10826984 113805093 329604163 847468642 946919814 160037048 185495661 530393046 223847971 898899095 103183916 574398979 39272800 715328940 926035636 684907369 603392157 720379893 305261120 146775045 664031150 938728323 43979659 692965037 426631042 698394922 864008600 177375483 443092829 595628383 280454793 402588483 155721718 583321802 303746496 166705074 838199241 194503526 905095828 867200459 735754860 672524516 560520336 956389204 750801668 97990521 779096723 80347517 730191518 723480250 363646164 363628701 827179234 523104660 57133222 83538035 445456864 167734158 602558374 736223403 7794795 556485752 51707211 742562950 22354498 737028433 659215219 135618318 50722051 233027058 210204431 867317769 644661675 471123205 806006136 845274992 72699654 902622205 824694573 261188045 842887241 521019514 99581057 507985467 983051965 649307112 936701746 296445806 447099796 368628762 246877597 392440083 849136953 467754915 626916631 486666572 848381092 89472974 740156714 696155614 148442000 449311232 258119957 596850979 797196673 161483467 955669370 200688133 204980496 792229761 925712916 210937658 555535300 434766510 572790338 135000946 413516534 89136854 728234145 110908089 954525097 798625062 709542493 173869630 172845138 285597052 731873406 957553576 628876180 58506696 2970737 961683909 202930917 331167371 214481503 155669211 236608650 996970085 218088609 892898389 228440455 218592314 158840210 810294449 629675158 15454115 806437512 32076255 803519578 97312836 836724223 632892425 794343084 169067625 176837752 186635180 494722942 649867711 952791880 504405500 814324229 764365472 712699271 822168230 198986369 800103435 967014866 142839916 233759961 815859957 295612876 974226483 363343460 70722960 511518020 81192834 28438960 369472716 2315926 38535606 517636146 366778725 204312121 937953095 910471182 635101910 503085869 932523533 340536267 241803905 337398168 222464584 855882550 156471997 100620455 162849370 823622136 434794694 658464140 516172658 941939977 57299966 703374816 378019270 363975083 648212297 626445157 114485866 549408284 463679378 636064950 693449520 683018432 272599307 247295789 947944538 318203417 646356897 64529238 277835440 192695828 806011773 599442182 847044083 965165624 861291798 859091283 29621177 897041024 235942334 843732602 328911808 974235435 824277361 736207056 698953482 102669905 450365673 845024970 63818015 444884788 666652015 312162490 825867595 815875027 808049940 502765788 236221452 874154686 219084280 965894716 703252163 786568182 471828006 307527639 313610861 83634297 245744429 805256934 24395435 844211623 616276176 458347071 355613626 326252824 804813839 339755136 705895585 48760820 280239881 421598168 452546053 677727759 194269913 428608295 330499100 339517955 92745311 68402386 219008387 738118697 719758692 246838914 200056098 996229505 523067705 231935575 178596696 539534605 914631960 919788919 674455576 322351228 89735771 924131170 393965880 10591010 234486151 733787673 613688604 330206826 832210726 95500147 499807937 200590121 395753922 883974742 9234438 117399569 733155294 368941070 967913486 835316858 982225983 180036210 444280087 776294009 956023509 370744696 111257200 21312691 555555464 659719728 91574558 989681700 367778018 735310067 602430749 860927375 572974278 224865427 325862512 889475138 66082447 22259286 856650949 851621542 522258378 399454413 184956512 279104051 965658261 258045188 20566283 223234994 777654701 130088971 750644655 622220672 561354979 969309438 165388487 131657619 411977529 24529218 715327687 910449152 971444820 658722033 823333661 686087532 648202535 733117880 394393167 159274323 8950624 108759205 129348933 512346247 849911483 559111132 541062411 32344673 471090944 888911402 257960451 739130172 285130310 381225811 185630185 872382419 323992499 225286295 29245205 332310530 475919304 77450516 771650325 486468104 460611262 243640336 282800325 551384374 642500269 144278323 416845467 455067875 717000484 315678735 589727005 398211955 18761963 257041280 96539867 385248885 61667767 843882642 143626167 258917616 194722763 25289459 268875914 938546201 140729271 330357230 685592723 665998663 486532888 267182823 81166521 886180943 13201437 178327 710307249 506681841 335673347 941623599 585784767 786388487 296906573 125967751 606478690 260648523 361536680 676940023 989266162 528993400 170307706 358280351 525068387 414828985 392372354 775259292 75738677 775434842 727961943 100640749 830113847 379741491 55222712 223535789 457669016 162148290 73005 585238915 834476347 991627589 231653554 557487057 475711201 164580125 58922613 109748861 652767390 879807225 464628678 410404667 15981858 22012414 997094009 645956657 224083542 66411265 280816229 780122710 140402366 876820541 260518397 183717941 111783710 712979017 465901573 65490061 518225340 926733416 879071641 887567668 345039297 423970679 535379835 665801220 987277094 248350918 168542096 242262544 629675392 131154287 419577817 13559900 708151292 98589388 474728317 945427230 489366910 426082980 905315527 553111518 803011273 2037372 64437875 811191600 169698995 360368839 944836312 335605868 814889546 121758845 525976096 520283352 410774500 721472354 89156362 465724211 394677983 261812455 976067060 493056640 474533959 340534343 63927705 644294663 106526711 752057142 235034968 169192596 182167003 580075650 733926664 181057095 460033589 369293765 234484175 144402404 171387987 843231110 565910919 139477189 820498200 193813980 805206508 890911891 15632671 365309220 269854377 232080872 763166498 422510008 63044138 164569585 11589386 507000494 946743088 182592874 924318637 198533453 112618614 9452088 496714830 697262291 460095802 507623649 455836533 250083253 552554332 890093091 45747086 54947697 511669655 81239700 183120767 609016962 813596216 333837855 40188008 317454297 631721234 900071692 116674276 305575400 706946554 772500153 932649009 613592223 507597503 296952509 364777242 48994450 28808975 854126249 681942693 331938602 322947887 444657951 202329770 416858203 608894667 794279208 187993930 597943665 212037898 874811280 667816552 986202767 728240103 48756699 632957617 390221797 5583222 462656271 21214203 8273429 40087549 981148855 80953188 196431579 514159421 464018451 205622234 309983776 516627478 333732167 883067682 119530712 541940758 136722475 396313841 512502016 730973580 297060029 93376053 625958243 841762186 377336999 981245194 200280891 711090993 130734166 718083122 129029163 327869338 338735779 29171710 140112773 656558432 232122333 245240293 764296139 327355562 212056080 619436036 355117210 775472695 275008715 64473360 938152151 513440746 215779163 838544234 367001398 20863918 154302255 508696629 558715851 43040088 862259961 658677182 406228347 782171561 878215939 392180337 75033681 919454125 769772254 240704990 430654443 164009061 198924334 362902080 976813769 953504901 217347510 670823621 25586638 47279242 637116397 457990203 836614112 508967062 753616840 326010475 602176928 410014867 582256692 144154669 315229244 45947594 630183872 839470593 202391112 556638706 965954295 347465497 414204154 238375871 335206669 158983014 501171968 36941829 515975207 47058439 571598405 212217825 660655118 198842574 747067384 509461604 555730120 917482887 71608646 298852837 113993781 57700078 442561149 116237475 403995160 182352963 207800293 319562215 402068510 671469425 317739341 19633098 509165692 131553853 530875638 7486609 415700115 125820731 100815015 286280178 832866894 333380198 529892570 746713640 499924259 466122449 716980465 695779236 466300428 940616001 908146139 338776531 45453335 882362312 779521560 573679568 936773017 882724826 109126409 78968867 154465509 708363323 337290119 59308440 363262655 436317662 896204789 820323141 87832688 825029529 614496027 462441402 934551395 386646190 844114421 129056435 442936984 623721438 769526353 229988280 222891538 849961949 993642916 666244244 823039354 809731907 221283051 422996158 160458710 678385208 9301117 784970675 935622262 189876898 276063121 594276730 787318616 630688776 112016915 616982663 13448079 287112780 938044226 918415671 496673669 81762633 114197724 935938366 39280495 429901610 429705941 175100286 959741250 261998787 944051707 951475429 260500927 569300782 20691909 148473995 771256779 623028230 276681435 634334382 776428679 667388315 919698923 518008555 51917986 284479804 943303793 197773768 708304935 1245642 736573721 119398246 561791948 188263381 789574067 736155484 104000681 150632757 299265635 101069631 495061216 110192250 178880524 66880704 64739927 57813345 516719230 359789558 334136895 746045104 150878344 618898855 233046130 24678558 105775483 641454228 340362380 485053597 528535604 378496314 570561775 238580953 110473145 348178867 26116305 545852503 522058657 254053045 254428687 446650051 564328101 892319600 47827602 681603947 173714872 146328224 888281214 112687255 517341177 193260075 875458590 220530063 934060087 417331475 194059670 45829316 436323024 687917832 655134426 708260920 722030467 706362981 777746862 263660251 293785921 108542720 121607338 493972441 222059559 490463206 608250952 566613694 850510083 556418650 155017210 593763986 618889698 158125633 275476363 719852071 117032752 469944650 897888069 811542625 894454848 252517872 253571625 406875682 949093720 151036318 100364545 992957796 471278668 617981304 968206215 164861500 473968751 62395034 126873473 271835164 988507511 329476760 139492686 345809252 310236595 176476390 97894979 545666426 41010421 37143863 385754700 428218017 95697496 912197235 16706825 786857822 688695854 175409327 759616053 63768924 219713336 735911664 55777814 841650371 967662767 35049547 604389251 933071309 121386649 50557090 453096620 235188514 774592637 619809093 682932365 213434717 596866815 427582403 512224402 86143194 334752221 858654037 329772575 784387617 138463460 819401190 18359012 38842901 82158011 670000796 30800150 332837849 621789995 342889668 348165595 521046804 652479311 135499711 66454321 529360697 844837280 261974761 264036847 152435052 252210379 229558273 789790970 855631440 670169690 565968336 505617409 149895150 133726652 479531111 543412604 146524091 277750891 19028912 344413527 420401405 740469578 945740933 794100562 449237611 361480135 874186534 803424980 420113672 189993287 701349993 994964450 386236548 928752140 50434033 986092048 158346246 443403136 961850907 659491794 559976107 374305206 609918417 332373959 941030376 73868239 949682231 226160856 317293678 927990074 754096796 907117441 274455005 660900752 346773083 811849750 661328901 881263003 955525107 202056692 461365222 810396105 425457470 713439512 904307114 316603930 24967513 931942146 644573205 85650748 84111274 171177184 419441444 895120834 940473635 781677568 3955729 939743220 968914044 113945212 369912717 878043140 863590004 21625832 807838413 873962716 550028403 712726125 2015411 532772071 621949580 236065494 833914597 392036493 1904511 697741041 177328546 821703176 248404767 307075446 686437665 992286316 823756377 614836833 765592295 467752872 12634913 1461583 867892402 211548019 33473046 512554797 250865101 591929430 953573716 717490927 331801879 914697194 84183249 443085709 2139522 352630369 60892271 234418919 925024225 242017564 280453776 793582551 975276586 508704885 405480132 574953888 502829807 52047295 661859077 33735811 59090009 506423681 290733514 793950165 775133813 230822738 37616601 330027074 327869798 532159126 487301958 33793893 370106587 140297464 635289048 257637939 794020783 32122120 212884733 434923091 296955949 221700351 93252893 373123929 481255870 813332838 963597683 864385354 36170744 487007758 85371691 194786714 963568945 895388268 36665219 292913541 863093496 16590720 54705897 13276166 573675706 626471272 676032397 515540353 658031301 415684423 221306841 994561553 586986634 625007025 841795771 144982820 748516446 200741288 69727151 70086114 779739037 6397040 626178546 939242247 579925817 106498057 976030879 373285071 678172353 697715185 37455866 122897885 469379382 71669121 144774859 469161966 973661080 28775958 446994760 506039994 331414286 263575089 949454378 831043445 357355244 501841573 636751870 304905289 266320616 261661663 97442626 806285223 188543087 166238061 193725098 601677467 960218504 116828776 695553872 91631898 403608779 630988238 105923561 357468370 286361039 258206664 665108894 550371032 697912467 491201940 525765377 80481852 676453565 831858237 185251927 45481448 939050307 61457591 446348272 685883195 256063988 759269594 72714973 503620385 841688727 326866406 447985836 287976888 174325839 758914976 405606885 82329843 312830832 324348503 547927504 998414785 911484205 626101450 248371846 220034797 619585111 611367703 404987797 389376825 865108115 330592195 860504055 778450960 407351736 617980578 570504920 828454133 656688519 795405262 582271683 511229428 783543706 268617524 585957444 635574066 262681663 28809087 416583953 174485535 869936991 30389610 117401437 65898326 454831427 541116989 329080699 126010313 182126398 758978405 217830726 289155501 709528199 234744766 386343210 233060544 750051487 322471578 93899425 562373648 223417765 74438683 370700663 819277942 158436732 672042096 42847287 664102976 328235357 182471798 646646047 327294219 356270248 779930215 831204636 145180558 417656572 699225566 522301622 476211995 908212317 16936960 844140445 255585061 805948486 531759629 390232282 852098358 25213317 147842499 822921977 506400705 547124554 420151828 738956244 690105049 921112615 391524015 143734693 738553538 199658398 438995929 646189573 317086655 293130386 801299017 176462174 626561684 316840731 805188926 40710882 570600760 267740853 260870298 669908933 44144265 249425370 37178184 637603459 723814985 262556388 925422314 920585532 735044871 634477907 991627760 515124271 401888871 199184553 827194995 678970869 399598729 754982928 227416186 846873754 956394538 805630559 204290793 963157362 787922218 858157335 11854135 717865622 719862657 379040969 451333878 591376862 51458157 93019202 179174223 457333723 244752655 176681075 763458747 992382749 154296410 521102536 301292551 411504642 441908109 80186299 622369479 20655336 912856930 214239042 456382817 138803433 593044614 494247165 258289687 495827167 726969276 411144221 23816780 435455677 790087603 703461941 630230988 850581624 643655338 92142780 992072636 602523527 590665868 229807297 722637230 342568019 868101488 690108100 747662515 19990903 44180303 317826424 295734638 416995654 771443029 761455844 345243402 288496747 33302973 737541696 261253590 90304539 188580187 993871271 348116589 979306351 72627484 427992551 59876372 946814695 985074960 364207138 813519246 909231187 302061883 441876115 213919026 957002841 747038143 281890425 657611180 586542500 191543074 514045945 633941102 640504419 498513079 12895884 289739447 945690722 71388720 360829607 562036515 505520473 412635259 102208259 668012190 646979791 725151035 262960319 256097915 988120655 822783489 193150109 757681090 505840250 542741119 474310853 185065283 114474419 310739129 523458821 688647922 805752741 767259003 943211902 575327424 509304974 482823192 755889017 380663759 259031674 821913152 85864592 723743678 982205720 307168934 289143571 543517910 633801011 502911899 739241905 601326813 477464754 82962393 496573942 705915180 684794813 671553781 53296722 139304956 336282572 165031936 411882036 136801775 361089946 382607831 803874808 12264379 345904312 617695436 937166689 571471311 389887346 67119094 376204451 507843369 996180072 986828670 517355068 968402481 186101796 9105246 998742358 439600113 423563250 908230748 527525039 36017959 636318510 761449690 883263776 160263705 632163361 412541490 223712600 850509247 483363900 192698928 282988422 327704522 235204265 754985224 661538675 110639313 537440424 603208954 918798493 161018337 484820255 641403703 295132017 524813774 194187309 759110474 110565259 958568678 952911547 469098536 982354912 452544450 591779002 992564551 244901355 987506185 317958815 708710232 276502252 282970821 908312230 93495492 36303114 71276086 37662114 39236153 36577589 572619223 950583311 132470315 292062654 857061809 974216465 989023356 551111498 945238525 989239806 267112753 45479107 458824143 47678119 248675530 550912475 819212979 930410399 534658257 141214406 736727425 690140204 450005244 185280924 133095689 177463786 188708048 179175103 857135148 299596412 467087079 601436667 124769854 601364266 34241903 536765385 623313869 325640413 795151403 614955326 4303262 284137175 358942358 559011139 184788194 802855221 79021753 983947974 268547844 735037152 826365717 242757116 139356633 312894097 849575659 162194615 21572130 157471506 70734732 578805612 157408115 512820777 231113416 764352859 787201053 777790151 413175526 989585554 828730660 243391386 136629809 577227111 968334036 391587139 276842044 17420940 808121962 526307535 596331152 291407860 326678835 169457338 593489575 32811107 681013257 853683688 659173260 134820014 938917188 962766667 859300650 952137979 287244375 17584240 301195622 479878467 104117912 563549327 468950893 99623917 901801948 945876998 90650367 416151567 52060515 749539748 519310823 683874624 667167091 212707963 972497950 651521136 496941334 187145107 687057746 95177571 44530700 133194758 822417994 683770197 372082698 504307977 981899970 148587966 349480103 974773641 497688699 30065994 294212150 96224790 263070392 28807333 26221174 124955770 736194961 160683720 476675821 790105371 326865994 615482170 330162637 637223158 412937968 211339078 594683688 901908913 387958205 212052954 173146191 659895050 662616408 55028673 580389764 933644909 675363320 162837887 721526964 180025758 720778518 616396013 473272093 271309033 694104820 329972258 182010183 474510716 76618564 996361953 991469779 837893321 834363486 860403337 230007255 605503490 212165023 949899221 223561975 188641493 156416410 859112277 587072039 281049821 86862399 114988213 468598018 469701581 547251604 776789567 568041534 822861379 784416919 416843859 419735500 394024957 920837550 862818057 547289155 362576239 24386019 121035690 726135851 61813174 691415728 648111111 281089958 140874244 800944765 360873970 411076504 370553351 117113562 315409592 781476162 331545635 674735983 286200034 407552901 511647469 822687276 119377798 161524419 439626786 816992069 26012523 332856626 82129608 180044432 912815805 3620516 24385724 875673828 227192725 305113669 858276618 733030449 730770622 403687679 491992758 614533392 651053513 409124986 753252994 86988117 184404901 59382591 667730998 176413211 565060899 88729318 323883620 898055206 465995116 379747106 998479728 482968430 829232305 214755586 405995381 900812292 832595244 919300226 830808582 106175680 863593738 955122233 41430462 215133987 127260883 430308493 683777464 533648302 713656522 382424770 403311884 243613296 323937358 925341822 131339047 464645223 556197964 767408718 983798880 345315964 189498288 392939894 630022028 786130886 146474626 289375392 487090293 773896071 206304046 226024463 561665006 397139289 178541228 481674211 855709892 610421203 492035529 141965772 792653228 537213058 953735048 950248523 800382380 182690454 953007505 985773445 125505662 262123473 182914913 356318744 410158613 105295090 144623394 82238893 832078581 431226751 225021468 450686274 875617239 39519980 248971753 848523664 294468125 753503623 110398545 186040666 882731776 604092865 509283531 34282944 10344077 187515673 122000647 180087799 549610537 247195097 234583227 29837228 81260243 655942242 914086013 763675709 761655345 717157649 188752792 388774404 412854498 92782217 281477603 705329131 337527771 498647339 281379255 4525157 275371618 511922637 734612430 573234923 300873286 446291310 626413281 681497489 112276389 616701278 393927171 609468612 377863341 492670531 129786339 907474467 195421990 448764488 948125112 56468231 604703138 527940571 637428844 896355670 366916322 329731791 220027380 46436941 859226420 357160777 791165982 55683135 945237319 931123934 558383647 241456241 439763569 76220464 748057698 215347828 360655284 698439251 924032691 32007245 622305634 675637273 170294510 923792794 109296418 669463234 900005114 913422337 271607563 330818897 219720471 726209014 382292419 696337688 232185777 651658619 890007895 481768322 647290126 765281641 535202299 107706891 776744127 338672919 779886759 15779059 448686834 911942567 47488728 782353848 442986187 993379670 577570374 434711211 565395922 551380672 914243152 171051121 920775675 214058628 176773464 323523364 42705143 983544254 76025464 297774598 733422599 921249539 756172692 104335100 793971852 311132626 735981881 933265837 644782424 80642362 829352766 513598885 307702464 939949903 145463040 914605789 497667078 945004189 425083454 175540418 446805683 647778861 216775326 118780133 168763166 866621745 578886506 605077982 91918991 164278611 556222968 415697568 961442560 710256474 670425358 394934561 40346192 60085688 65147951 908957517 509234567 972755941 964484230 847153375 544897489 875384992 202225475 85453981 95778098 942848465 690028339 732215095 732195132 537945668 177248846 280214269 144047283 279367360 879115505 40671263 474831355 281397243 331016260 766827934 263215333 146771610 575437970 890841053 518199207 99047126 629293306 84540923 473321463 173130102 351633718 180401961 668265112 889420999 646083438 79254254 834652118 835014186 30543411 63185976 298328118 77721313 253499220 644873677 974956072 431598329 679867745 405658178 560061854 68819951 71711409 638636077 725980355 771392290 13364250 658639725 612591955 118464939 1485313 588070334 542743620 124070611 783347044 51276708 77101638 92374127 727771205 858465033 341825341 675796473 332440796 80930376 35332918 203231246 938149299 660935599 598463429 597225174 42759198 730192409 504918954 573658847 426694265 799346804 520372489 407011628 188672671 637202357 241167581 34038168 778366747 490215850 750697513 375507997 797646500 46960278 702310208 973538972 82459335 506538647 749444867 28426450 532605457 585698553 135854701 84271418 730893017 39932443 760019794 787218053 41188805 201130384 20312151 348186245 878574136 121110149 857320870 331463839 301002917 77580051 840999191 23389447 546862763 409054231 760629378 461751692 446311656 245941019 660903124 46463257 34923866 652878164 190907083 79383450 908109816 423162300 96475126 275604176 516987674 405038437 230051623 518325663 725065983 280716544 273652578 45057637 107169917 170750725 424155127 848964239 304131411 78313233 787611977 567036158 82922733 874213745 812987469 392473540 650916876 793971056 802384640 672357656 61499933 615529228 15802497 980251542 447331844 554958040 951416691 825379290 290838729 853372612 837036072 315354340 155567464 312005034 103735540 282564141 655748825 532452156 368758295 429026137 116096425 558970684 309076179 881318170 563033326 75158293 477428620 901229851 675858680 38163330 678523677 104398059 101600713 741660466 951931918 752782961 281038851 144751962 88094612 609914329 943407553 91415492 851970719 437544130 879518981 201639124 711047850 288639339 642438960 402348090 930815241 104587009 187472488 960065738 701918779 401966898 917160295 502207153 363360617 816269898 914798187 936869454 463929095 86017731 520139502 684286666 85673038 801231829 29397467 232687947 144061424 538297070 842138196 128384593 646517014 730471644 906122229 724376604 245705057 217729120 279719545 490585408 798651565 64626065 465741782 161652197 165193253 94723454 360474098 753161609 652775905 304242184 588922355 806603158 810742473 954595632 493435748 820007390 383347060 631335404 247154460 25231462 152181099 493997564 241911065 937811222 139844514 49632638 615309697 428965871 402074729 291444071 291429111 120009189 614031331 926882818 757797990 709248572 608974959 459753528 350313516 64545043 85622437 30611483 742076019 941234971 523295509 646787349 163450540 216904452 396810629 522365606 369167642 610869744 128730004 351984293 245198916 408821212 640261572 148412707 968463309 566007964 330032644 278069141 816634058 72108403 664807988 555048264 61255949 343327236 284740372 557373719 423213960 291096787 611129012 505319500 827705141 196369674 231951036 877118637 728483291 788762383 982010043 430622761 675904273 646996474 73773428 898992122 959707780 155860612 641555484 104997170 23909915 143091556 786495822 832645270 998660974 160792176 31337169 26740167 394137702 955161808 952019018 65721715 525511302 396241236 426790056 589124552 582435440 886663819 723874486 213476410 368819358 510142408 81248463 204370538 959709670 689643888 947214129 522691402 740508505 630146652 513515826 518348910 913435491 374689388 619440414 209980443 707567842 627907157 921255752 104974129 184888167 533645652 413008427 788680813 637551896 323491253 118087392 278238810 680185605 991586088 807128533 838211660 385841998 44493760 472053643 862186960 437610297 851300382 139163918 279324937 119387938 710554786 309814465 231025152 261277761 629054488 503963365 530594470 843833775 215289350 809038526 140809009 529915785 304581250 813918601 922401101 706044774 579218537 683827341 497537733 796902165 274486949 206560260 19350252 13865857 871416914 81827670 932325194 757988693 5147332 272600949 189775419 908773381 489155585 229515762 171410202 201984877 594962637 381731105 899234635 646630266 192460654 326240407 209882731 136312196 743920191 477575215 504185806 419693689 582494700 70706823 226661839 621988707 813588532 722301435 12672237 971467797 931132841 827897288 180846575 846846492 40735573 7474441 291374433 470853711 168955030 357795290 890555978 173117401 515696585 759469649 797862887 352285963 85987932 453082028 539040536 629903887 624958765 877262207 876909001 988140846 508320342 995736689 24486885 400801997 462414903 268510414 310864382 66277090 912529141 74418793 707309603 281332517 713709810 58260056 182342635 535267840 814362067 249595542 10409359 625210491 759208208 851588546 855787822 986014245 64103028 160993084 626499319 631851075 698701060 813185803 864656922 905832411 780189053 886703702 424013467 842319230 818936186 604948906 204944935 802495502 419811047 20521922 446552853 224149781 797593810 92984904 590263440 246604907 913319277 234663085 240434668 392965664 19963324 209901283 709503384 406211467 86110875 247525706 89476160 219335009 591346393 608897286 665640884 613023552 892375263 6418166 983603351 841944606 139343537 884892193 60053522 990435396 870790282 6113964 89957225 854354252 539517139 735445901 649112297 178431361 501717097 881900000 444848837 413892146 256028854 64118597 604500460 714008756 676654264 380058109 844431836 732918911 165158339 464728663 805367726 608636726 557555498 420478497 998986191 431396974 430590710 314156480 807848623 227219414 883417095 821955292 343363482 318660095 189113093 41948598 70358759 267953241 662636197 152055812 760452567 261885822 289703709 114414271 694922919 40892304 76564615 828360956 542125752 118375648 839275235 345980732 354008570 947970070 685334523 87264883 805599638 123101556 848374742 938131784 535350418 535566929 777866571 54175423 30702887 57427960 476653058 579318645 629045395 645131567 246926844 206032682 708041186 385473752 866129704 135249589 290909698 451853201 258675322 244358599 329450715 316135396 899087051 134800107 358751226 922038137 429925611 63485764 706344604 503395122 185505024 589373024 960709227 183776394 196123951 933655697 251639898 138830301 144693139 234241227 200597707 966531136 192364560 163413339 827743136 761642082 255400986 948448812 158693033 167185509 928324028 805144604 82472849 279181746 53263881 176538063 287915768 999165412 923850792 277950823 55659011 686587685 514799647 432517719 203547705 513683045 496237333 327150521 294718038 808975616 162731274 145036474 797071636 853886513 144043571 652372578 574450821 174260879 562404534 386269861 708321237 956487731 556740400 283639261 31427705 326446569 618703179 38572164 653149558 25362952 767658400 446304671 175248213 475852319 500964195 648347953 192287020 62778800 643193513 726812886 665900580 182832953 424395590 12624809 265176557 430214879 49587732 971316043 194652467 481480894 212654280 182121913 482717314 145169338 880138482 613597460 484650785 206105175 344028926 448099432 763980873 887803706 196139981 771493024 956546889 789244567 608556299 121130717 873647687 237890706 690208847 173488183 55292716 186901534 968350417 360044921 207188107 678753913 208254799 566481493 676790139 523541135 844962521 3415988 805242075 358949294 170237080 693283347 421286442 737334759 103999638 325758552 750907903 261309378 188264008 484466234 112622784 307250098 255665917 75693015 808060710 72510784 249627071 878131087 299739648 743326975 220389509 984227855 922278593 538725195 766088509 577224110 477799360 113955465 733718200 170963944 679994294 237339982 483711177 988857625 37442874 100004489 630615700 314670808 511184032 548499593 929765992 383893869 368957962 618471495 883944432 557022868 113662503 795043720 693889900 393376751 313924213 904480681 426921044 344635577 238269937 126102949 309721439 671472697 802533830 515666369 65980597 439258904 191907333 513839831 549857074 474571994 331950937 528435247 603602821 722057163 710800689 574545981 993403417 683383262 10827504 509005911 22858986 142349155 880426039 977493001 860643129 494120554 446122137 926135481 905226587 7785657 314184933 788731675 30570806 609216849 179404496 771201141 139900822 963521209 271915461 832208669 589042013 179375352 995529644 968520246 751307472 144957295 509815418 676355242 218971421 925246361 203291722 775375813 820580413 997816955 181240781 140444563 195070548 654272399 177505936 638464450 767021559 170330921 774817981 351643650 901242721 240741606 741804175 363241752 72313588 662236220 617272323 111208757 870466079 874321028 529683999 593795991 7698163 217163003 112431623 250523716 632772600 27111491 410897903 410748105 531463165 135600704 208857113 809279591 289974144 260855213 346464118 556920371 837572041 389425358 917074584 422104951 10000936 933284525 949204077 216034141 76374053 927894333 496029469 226015285 897343194 463393169 328654353 212693747 117159139 247278249 767478021 414042477 335851139 721262384 193585266 306447296 456991162 469932359 552591386 564808566 120483540 459874148 411967599 339856251 936811344 317738751 149354582 920104624 775273333 213477836 135616077 480101024 66576618 639579291 36060476 519537106 320018595 805793995 62138890 605623319 838698899 747309886 616483362 870635536 403422160 680481359 505428490 123110676 523641875 781492581 972504775 939834030 685964286 510645571 455412698 260298762 319949679 107558899 285834525 764176736 818690902 550306094 840494133 692930499 535654729 89155899 246623985 679229759 805001909 668360354 968091533 625982589 213749579 162865497 958075447 868040370 411417405 267725053 389028575 449062453 214184577 562327002 760916989 268591430 707651414 177282569 650182940 542680469 66820441 267318242 958967212 153269153 876094869 109486253 872612698 645378160 680917787 766812678 196745556 726496531 92155178 541618218 735482862 170476118 408444053 170362993 325298849 120496500 737425789 258280003 39225032 113165182 671391603 745011157 323458623 260930029 942725602 146172259 135245131 184221991 139245109 438774118 536771473 720370956 889907004 924043108 926510107 17126205 266104981 132477086 95113155 708389783 681431566 23330215 899097036 720914109 889499485 714723765 208856462 69954034 176004962 503422390 138580621 703456278 495911725 335483054 884219591 177454206 300802292 863398998 100669045 823097244 517162728 930594955 219642021 601075374 257509819 134751260 52494886 427689350 19986334 761178719 8690092 608190370 591865566 614373960 479947706 26380220 973718784 194542597 564722535 487553827 172787791 761207718 253214761 385925656 222386810 622197333 860416073 408025019 119068798 801552924 130358187 728053577 699346585 719768729 713351404 76846252 435155857 292935652 869287074 810274724 439358523 730648956 896692075 743843313 895866197 174125001 530689412 426335306 680156274 493898017 14258386 868480227 711409027 9461006 293179329 204505342 777022594 22785319 491302630 239044443 700163051 72914921 89231613 826740396 684638575 559815915 458540700 662491672 471171006 293191009 790428857 50201548 895367113 898769510 932230727 445140674 338720456 266675571 17710461 529301809 885158907 634718356 751185093 356871989 358000057 595826898 960540391 166664078 752820248 985011804 480404037 617239520 31719308 300523601 501051256 137003521 570972686 790939300 89380227 535656779 924950771 887889251 851591738 104700626 879559959 491711932 204094459 210395919 30472547 127573594 817897406 771154372 98004673 501088791 286029032 538421798 710531778 753339100 105655653 768600838 827834090 110374413 181383974 132203721 268277783 558580428 397402713 98921785 935980339 121978080 818186043 968394144 401289094 909453055 968058859 846498276 327631665 184470395 457507528 170140191 233695911 61867618 219182180 14541914 591345263 420650379 869176776 405753770 731295781 260648895 776278319 782924611 380151589 423978089 292184602 696035482 839545044 230640148 378750512 621777623 765832544 766346814 34713360 50115949 917843286 72097479 549492040 549685464 881477432 849089062 183237982 707331182 31994533 8515701 111342082 334573488 425521439 928264943 17275919 734151501 498624328 238851748 420263748 287260723 616596430 861494509 178529128 89999323 482899169 515849953 703730703 353553879 285266433 213476255 605252332 190237604 900317345 501374485 91167167 767198409 128770696 950127969 40281170 234703448 492120386 690890937 724807164 628149079 504516795 769701121 157425187 5759862 780554075 151838440 323413200 30984199 766845985 727054942 20360965 360328158 507267725 132765019 604880377 290858617 463908774 105632302 140554785 397242446 213412090 30597037 146890612 577250012 138961332 843520280 526655207 278045434 230614266 300956631 419268532 32413546 594660139 397949264 183490927 694846610 625912855 448075805 877446992 752043641 124607934 871275489 717366476 969232015 549299421 501433330 377619547 264563886 69139075 963698988 723407366 355478509 324489781 349431233 424118976 790364056 847754637 118053474 782098899 602296163 980145268 862781933 316536298 346538791 268802408 926319460 555330635 157709652 990580883 543279738 493615068 987319014 34461749 306699854 718099395 235429013 682571608 738348242 205667223 334108314 621358673 241171245 809043765 305913547 876963306 242167814 241765879 130000976 309376310 909321959 959628822 124502377 517122628 710677280 5779530 801604959 261239560 510791864 121031339 668947440 481191507 543510891 959361553 508645379 771814488 696606466 343689861 7098223 942524242 256332101 145533035 110235645 304257377 189780379 581557594 145214982 871736934 463363520 313460286 1185654 433005250 552756421 910526796 189193710 401508294 988370344 877513054 690398637 196896051 924472668 230099226 962743339 490518711 402211938 6191464 887925238 842182607 484448288 326356793 569699337 753129347 704763717 158418297 886219077 471977637 547340227 923858918 715469202 143993787 552817439 778979480 965832319 531392338 47073703 368367877 55651375 236229023 184633117 11621151 17000141 551654946 847388461 571956476 842109334 804606911 739584024 1620291 29753556 117524563 161889533 162340211 51664797 269027769 72408865 51648772 330282603 145162281 431318827 196725841 355395231 331750586 258296738 331159904 917687586 961801953 19151737 929963407 835840026 807339182 131915697 308593218 489425012 283778511 27968644 843437514 882142644 282884456 220078767 554311667 530487553 99516493 481174043 250199149 250206174 218709529 760045260 83153901 386053190 460288712 812736878 680457306 455049114 266138603 466354330 173560546 280691588 395068836 497520419 156182819 164397186 154810669 21818895 712063010 684286170 791504990 659262560 846762875 644666637 260804634 126062571 45652995 118341503 611404774 256122788 105665824 409427130 240027100 146059651 884038729 767574831 769098648 739283349 563670360 218130088 223249773 396399744 378683579 222698802 485558508 223571623 34607290 573748221 652283430 859787228 827524218 250810098 544727396 821777596 383125035 204028629 688182808 569994527 903772625 831416569 15041951 195137495 972263628 964330681 99235499 38473522 793713494 725704314 961941197 155879599 237775439 119549438 35890390 400279275 448844496 801227271 807752944 150520848 44081521 367227785 492019612 511263214 25898018 73211722 780173638 882172647 848102019 288147480 524940714 131574089 361232303 272065256 825287587 806567804 144674991 799431085 901553403 231772764 143091072 63817561 165118741 515232886 518624819 241086325 503931564 244645630 799770528 670677076 68531397 920699393 948924942 394009449 708236879 227992197 639203613 785930441 305078475 601382662 106225197 381884951 76783759 524394488 66151234 32166024 227608643 595243065 271935260 348705899 253817815 442299553 654439337 544224051 571960580 166884906 882378483 850847476 516275186 500431365 835074813 474000851 818984491 865830033 334942913 215938764 569230890 338712335 892075127 880892600 387019043 262047632 466426472 888699982 95827878 151535307 287578567 154864838 145123656 810415894 252035891 571131437 86665079 350294259 265562659 205632192 517165948 572414724 7648590 408308607 119742226 74797370 695808563 608139395 637087313 301730197 186393130 817050022 238293867 639523688 936429960 912067979 906947905 361621828 170409026 536335702 347370566 344167151 843157543 854058969 656695573 104030604 131357079 69495192 185723401 688750397 818740887 686271114 777396267 655623444 139354417 704561001 119869364 206744663 169810598 89040310 263777921 967354817 333973393 618856439 142897275 685249905 288775499 437780400 897922446 734600214 913869914 550027398 230626856 736547061 636724992 619560016 251398713 138120528 415476234 231085121 800084811 551871637 386044684 593423886 519959965 579692818 520107063 925934187 584762348 861057693 196868446 892291707 127891923 918219855 227346517 660079871 250882175 433790540 997496104 122832807 476704235 893077862 915305738 437856599 732028856 171707976 542756363 672034296 865656655 518139548 807681726 286661355 684789385 449994182 903125347 640859855 942500249 348294059 34561441 707481353 503175588 157294423 898063816 62731608 659385671 83741914 788773925 206666030 105983832 927146679 974493694 383619541 439695405 435191987 524159319 922823308 981797868 26485022 814234933 260805376 11930886 23831041 60983037 433631714 625331190 117506666 29404516 944569494 836836215 58254939 821191888 564269365 50900143 369368195 493391725 173109814 496827641 698348156 27709611 684573770 825602559 306975443 54132458 962584174 855690718 775730055 197107435 262050285 884131475 771062579 901910343 554630520 252113338 972437912 343099655 452142060 502682960 132191511 920046513 343310996 449008620 270971574 695410851 790800737 812850023 121840033 106603289 183991889 355319966 701777244 112817885 907066446 695451380 559500565 145385855 140793030 634127729 142657019 642103530 825685743 727651805 927220460 419095088 576918082 119567868 610377120 871488226 722742323 16413376 62952725 203234688 501084036 644358043 9548698 339330560 691469342 547253554 618433149 176014036 36290010 483213426 543967080 151424713 799745249 553639752 90449238 274556582 173755915 730401271 787069703 409602041 297873218 440885016 196715320 570354363 334198786 234641991 374967389 732387801 691132989 147110433 934049348 724197254 72252985 286567644 851888317 950841263 531414678 170059737 74570292 988039209 344742420 144929528 872241138 476148836 932253306 622728728 433364792 349335037 613881061 505991632 123982246 429353797 570155886 195912079 603014926 23900095 553904574 504183220 752117547 543356284 868927371 755100658 46832528 537951757 548107472 6576593 202692724 172025652 516969605 392778062 435213267 524796951 559705399 385773012 579912204 177076140 853845911 672858897 10201015 942678569 684902701 904450981 669702928 438408717 241158879 482790159 502287971 11909507 10383283 871022156 824477304 307354278 288789027 897412567 860705905 443569573 630187422 233844317 395216798 469504113 293127738 255228646 86285533 608231326 277017759 202622039 702775689 147829537 880704203 475055655 662088209 75853615 248918322 164662021 190848641 265600404 75924 907599402 327470389 594986608 52541014 78184893 243324715 839643803 512176237 599746924 778751931 359568181 574076966 512393217 464931772 98402059 261694941 636881406 409371155 653609707 679624564 863780402 927094922 349092438 566728266 480437599 580763262 645522671 966525035 753934345 840823231 268542851 835783838 321057703 516901031 557234457 84089528 750477745 981840037 875124740 333450963 841653552 313323292 118362008 654517280 161625733 528593127 927746687 801135699 224741602 479755902 310380004 219438783 551774533 863156146 162669523 892223681 615766297 591654728 574103320 718486864 317882147 966685088 722597232 738902232 266987362 750500479 214963846 672615017 188890597 486918047 136458916 172242806 161934442 28222424 182592820 25568640 74357387 256728562 283579952 477613413 603744248 69350820 848430733 301267770 576077083 603811727 379543111 553844224 504236597 64034570 221898962 758453950 351490791 901772421 355358760 157286580 774431443 909991334 222248612 16802355 772134072 740208843 857850775 247638905 271291959 569799546 871963516 419033004 714702977 357986616 536603596 797267783 296530717 208072896 659890402 456051056 184141960 693322961 653978406 853358259 19626072 985338725 313289702 171158723 725474862 65536487 646316036 157842852 347966207 991694696 684929005 765492601 391538406 676123296 463250200 227691759 820916807 377063292 4422670 356879182 113251672 665259215 561599914 23539378 876653675 7783831 831949581 374778820 532220465 70807974 439373701 952674607 738875186 825035903 818274026 627949120 406685037 596964331 895902583 925530410 328368198 646706656 678052255 112571970 628113699 40237455 75623545 431615418 479546315 96881445 79755817 616072683 620038007 803878869 606139180 972546091 57141547 850912737 55282133 521415714 8322924 333271997 55719341 838269561 579721011 260106406 237302925 368289195 611046133 963247187 518906774 818047558 605483147 858324759 315443149 449661929 877859611 147447165 185857619 699715391 515656244 220588905 60761553 654435204 493732351 966886422 904553316 238666791 85564634 628724461 23966907 88082346 510266179 11269949 428135897 594522287 644655502 947557341 249474906 586638658 28494170 9717673 952552322 227886811 240099913 590643695 968131248 639229686 222778619 644068448 114948201 892405046 301893262 473399440 469636374 542864294 476469802 213592628 774909361 267748592 579376977 754965748 227272951 111192084 763672500 35083541 640482855 605248266 518675240 137950837 92114147 306138928 922395815 676241593 926743329 774551874 638942820 457663674 407239646 720027975 472269387 843039623 216233832 631638926 164404070 383129913 470875022 941224870 847756017 310163975 622213919 872722921 914574448 254553327 225261626 8481839 809354162 79960640 319662195 47214195 131842184 931594309 703207372 68943682 34252453 635312862 11075982 666173397 255109150 973730584 51989751 356954654 82023330 848249027 83623752 387525633 838066039 56974349 560063268 446427533 960644081 607780914 321991819 38831063 499021929 652811311 42977171 582573058 106569086 737767041 531693737 936968330 830843719 161841247 780928982 684813337 717058531 969523525 697149087 965972460 509268930 531507645 243915580 777973742 210885880 931913236 288455382 870029723 247019904 294057687 307483530 716799713 992271289 446745722 123256015 383144978 551460227 623927938 345189746 883246584 373820211 549413510 502755065 516651439 371502170 615674869 499118727 776894002 685479665 968571150 802841655 114369463 119921833 824799593 731483975 495284943 768197249 665096690 869966681 901124501 626878760 762265283 542858724 345927519 145712001 254422525 191362458 651297550 991006016 781804480 774050612 504120447 332328456 688275594 102954821 409679355 910802369 86809908 884940602 961304806 582292334 105429386 134192354 232474344 255325749 114430850 533409755 563060686 69860125 943589061 96492781 964663675 26727735 217188945 110648882 311477310 734996393 961736695 393653695 347188536 992923977 898536001 897655189 235092355 668070776 343242156 685479085 38737798 419665572 432300352 807078321 232130633 232669347 233210140 148837858 945423371 255278826 791672801 645307831 69531979 24738087 293248449 899929428 884243867 343670832 402838096 972672632 126178692 661861646 800110202 504886332 109849962 428539362 595315947 582227826 72423339 914843009 540331768 243538229 41407737 992736175 337537177 48037684 191370850 670138264 878573473 809096643 41748203 960331076 547954560 636800524 819617235 539738636 767038789 427079053 346640057 438963258 510895400 519416106 161055622 941717355 172213221 235028844 823804323 431790387 490884161 805251644 399554564 815641479 982200894 107611794 854790211 487133575 326024149 469506626 856480564 16465162 167653302 270146672 380678622 721973984 929310530 378083138 598701872 201712206 166889586 178976550 40885521 771984124 406987686 783090845 208690427 897349345 608732860 515401648 289864775 694679613 634006115 112516248 853337270 415176458 83191215 334102525 922742044 637568820 422116500 119736412 769300236 78411195 963238255 360592344 501008840 783998448 960184172 237198253 150319907 318115357 704393867 704937673 763504047 805984791 167062347 396735065 886884831 949615086 386836331 396543728 787590063 140612743 579182330 673932330 459394068 540342962 108012371 543894640 935973608 539671914 374005045 111568202 827492486 568573289 852322836 110918771 693658614 798989577 969524295 255080587 231450194 285684319 521930679 452600923 456590516 643030842 895853294 985775303 161858196 10517936 290815180 742747387 623417853 528527504 139194950 661499625 256042864 279536876 990975399 673497725 812204430 628846020 69674631 923857571 65469248 348200583 526379919 514171708 52429800 564913913 53235304 150430510 114818899 92376503 96783157 165554422 611363213 486649058 743391118 351170135 585025260 326398596 663390471 995321071 529786353 676147908 930679979 972877677 195640419 38699067 365010181 854059094 385208914 49372671 380323988 853792915 4933595 785365697 521557163 475016178 286515606 951127115 335302121 409776525 303538952 534078120 674243415 102853572 649868413 805699139 558950337 980414223 691150768 460216840 665544255 882728580 636406602 5760890 748436949 205851288 63063385 731808040 874040427 383957877 995374605 517966638 377798800 162222512 75920578 446510072 951414380 401636561 374919217 138251548 480610694 197984386 706870363 176628856 629489319 57850502 373813940 444615773 169600165 730538295 733118413 131350089 522157869 554979498 861626401 952565544 134472714 930326502 323253121 355584117 100765 688323794 36230136 25324899 122873654 174940697 855211916 787572635 414309621 625060061 123216062 550928448 885027338 549027512 58591337 242194158 862696434 698179118 894984141 50778543 800318725 478735455 203856139 588966274 837953776 546523384 441096561 708638348 768679274 212650242 919142186 799679098 795072175 525491981 638308693 316317143 67077157 749491590 556573030 868837852 78481666 760249642 587924307 131217827 534357094 947492046 981996592 795175529 505023140 403930061 749284170 620890902 443995767 180420102 755843215 534270784 480490057 81275846 423601472 755525458 583455195 523569863 88203895 539610882 767542958 147861701 339405251 501844433 346284518 281257930 918948934 742733644 703813807 647442103 863192315 934582029 749584039 526926720 634542327 421347464 375595423 304618746 335605507 984650145 357751478 531199130 184077501 29910375 562380058 237862465 734737472 115942475 625324277 583299596 141172301 155064355 180104540 531685632 101017695 180809062 220354254 709105547 232734823 119675727 464267952 331420365 769949296 52280299 396903415 255412379 560206992 222683297 245501284 921152564 172896630 162702188 661219332 181331890 574167260 466400513 234553725 505641084 286153579 143854965 276191538 62425361 122893739 344147699 770310328 559845155 861051938 254838428 784335437 289045506 448093321 855106653 21819269 796532307 69495527 275941070 731124929 50239100 67079898 493438826 210629623 655326110 622303452 251739503 657392107 531855471 22984737 66013644 196855279 461879470 459266698 710295080 929437816 314651004 762973053 269509739 22925678 565694356 610499168 944235506 736321330 840435458 467592533 980032534 282431332 909444968 12190604 457097192 40531341 370966116 242738304 786433777 256864320 738230061 10925653 946723702 188391800 174595597 756195639 716206467 628242864 558427188 193507722 10457991 127809413 628265548 111293461 555824955 943403708 160436292 248613841 265238017 609941492 532100964 327306142 479265829 201571570 465483268 577618281 409719657 485091616 136311061 699942382 197112270 568285822 410700288 535548684 30745156 423026040 836057101 243682548 634367307 990826995 136748782 524299142 863869499 367218192 431362970 651946333 730379619 947786577 678474116 330714393 147422377 507035647 621633337 781161607 380523936 309048378 520865426 172774338 825469689 128144828 19111999 973517420 177350244 9794858 13209543 292539967 834879190 269903013 3374551 943551301 379264855 768430290 518644386 734785848 985244644 644170379 737836768 831972501 282164422 854870001 106050483 970000004 387848475 623763434 910864080 531626329 312739056 453543510 233112224 251964704 328455157 589255939 112946511 363496450 120715856 710017319 648284504 103285373 107184257 65729244 589140224 634800696 547141477 950051368 909678336 10852070 257327019 684477668 53542752 25657426 429673246 620668176 796818366 607726688 154332330 699471005 401457802 448798441 238929323 592559279 534810118 258522785 590778362 804211372 142095836 516497976 99243654 765459056 584100830 794050970 652433937 293420623 210612954 33771765 9642577 766227748 231634731 128620409 148789272 605796876 316851333 787100086 116475769 216962651 683701471 217789211 228931646 894393938 48859286 250523201 259564371 408784641 437275786 160159705 649946111 200291000 92011174 38671531 916585690 121876384 272428484 83418296 65390688 631913400 995261074 73477596 640965136 665701591 935949356 110131194 241952249 249154487 218085341 261116062 711720407 410974541 588647356 527179116 360089662 530210597 174561123 334130014 830822044 477308237 587264847 447207246 79150041 944072851 675829129 274035041 223391924 275629072 267971661 922160285 890054028 511125666 834941567 473674594 269529844 221058028 741236485 523943567 111372599 266463422 397293745 249746428 885224013 216066049 187885701 479794990 619821703 940442317 317428718 388709435 74314211 187801823 58433096 217667401 658013831 662694033 525740237 209474932 526490249 426012239 34518060 252475135 395152161 939289990 358494996 749718266 331839632 190866035 147194309 334794024 424616711 643214365 987770489 627352345 528528742 256602974 391264404 83663604 418348150 721395739 242917827 790132385 150387905 397093865 265305639 19091216 828337723 11048251 401775225 570699359 58427046 239572678 951458121 497212490 52359713 742854516 111503873 143323547 896136587 236532836 252353343 134317006 555874164 50679020 799942203 832404154 405457908 561448395 635593639 932266184 704856070 543136808 560993553 576302734 641269588 59075931 638720028 48639125 527773325 720762732 572682118 355436047 443118496 631510301 150777580 936441251 783734279 177854008 160983867 377984028 139187102 13999324 363313867 353711933 626346130 134501930 720966268 560500149 364437280 168818877 921785478 33450217 630833618 819918183 92309663 800770490 199885500 242103793 145520598 246565156 358503763 379232058 904675076 135929533 559838582 188967990 475791638 512162777 140278458 536911051 916457266 199078753 69754267 89584360 976960084 961553179 66884826 62382731 664313289 383245630 651588178 594972021 771074686 874215574 898585747 425639934 148867349 626577293 514911561 247510053 372281005 980742160 697345485 867827053 383559443 252999622 45189008 219134895 999111279 783993471 418366580 463109053 67965439 303950828 642804559 274842624 782115328 379844899 66075721 498411355 646305552 434554524 122580782 673386162 923123701 699341501 699111947 418581311 876844803 215849265 600556195 203467695 252042760 859016531 202044346 870808485 489508840 757829002 731168767 421084253 873726093 752031524 88046025 394677577 707658374 428517637 425807182 318246226 361463029 22906939 33750558 13159994 954770057 620369171 704147559 752134384 454700714 100075687 417873545 605119841 192730183 193877306 570370182 862142711 88159339 806635874 746632254 39164536 664538122 803374318 915629577 728174477 627191643 455342954 591900668 523274744 958204283 678257527 667892073 575641252 4728940 896445332 713106633 713259069 505996267 105213111 543656413 227621008 610415982 341512306 722106873 575278961 7204377 358905130 503779465 458699656 796478515 428133990 893337629 226523376 34819480 48359027 348656664 359653106 92032622 132949355 857727242 853485961 774082224 484287676 264124960 941580090 264263569 406049428 741324738 919602772 860699693 140178022 474950490 922071672 753916677 289764977 896558718 227071264 367929390 595307300 180346361 951396089 670737702 134162148 347851354 299982412 371619425 308734983 462512556 733434938 773174815 229937063 798106912 536914562 809923679 12362192 189765687 944491338 529550431 972216349 779974255 993443916 757532177 891212610 950244807 84271733 240638745 627969791 266596363 303754466 869325027 185790843 623803762 685196266 570403457 231637407 944483044 345356756 843394407 288801272 447016821 554585314 190943312 853259339 932472779 770737015 340055624 751123676 828759181 269229759 437022700 926486821 841045822 79145015 44637822 616325402 216064416 239564622 897654216 439507628 557108593 584343700 185687134 184746540 972344642 641467466 59113778 439846459 617411009 984045112 584438133 275401704 269847077 557682045 944865283 740163763 502009278 374142380 193060811 263659266 807892941 780737769 360292575 396365301 634732091 645602350 305393394 266681488 158180566 418779238 263978235 901553826 394887063 685458125 248466898 210634094 628989641 281881295 817552794 882912283 109090943 459969400 51568501 219301092 882996233 832644485 506363250 493342947 856252668 51913515 168451449 319171258 203297307 229374138 187167684 99050244 569820779 833743716 7604255 64989773 270083621 809281781 430013734 709511687 20338474 793179233 604610836 254255177 860181664 407501137 529432927 212363213 249763626 949055078 32732992 176079075 982609762 581863794 303967872 592965014 744968839 981012924 486477685 895425438 18584545 853013353 831474596 419463867 901133942 411126880 237106290 53189125 106102413 938489497 993313622 697781776 211979316 604062224 644162089 453373319 607448809 791053078 488282078 925416421 767306104 762822630 121375042 249117301 310460761 74077216 205062011 267210358 119366024 501818239 31555125 956822764 494258627 341294588 959425430 717806137 270542374 216215596 522156599 682445499 400287579 268393396 277690555 691064621 575752797 60118694 217541842 908660025 410552374 95641150 411585427 768223301 729826722 646742459 330973498 608634946 26086875 318821256 424763313 984002395 633489324 967806415 256100552 882341796 801624264 682049777 678645985 589979776 346831938 254278965 862342297 290621668 307250248 499666002 634562950 174468278 209353902 863603042 335864270 126742716 396342605 504595738 858531892 287930803 697169326 532872542 149177094 201710627 113507698 894662886 843894648 187213412 471174961 731134154 417976825 894768556 587887493 61332135 575858067 215333897 673862729 762840328 44134221 263355494 685430531 345904603 168698322 182834138 37233153 474278757 841700337 988643941 429839405 882303415 580158051 553751666 176785763 332900737 588162042 980071882 344050432 340953633 432525426 108908649 470455905 156029448 426868690 27634569 162758061 768718267 485706515 635241500 498764385 264813475 467904458 646318562 891875283 943156767 702419213 849243902 766480962 357306228 258325827 887514467 211136621 255942849 657818168 85026381 223031381 476765938 464352816 558559535 479508191 200109560 765957665 821922735 177775969 242763042 207030437 700563481 942266730 699957709 40008655 564618353 676900308 53079930 928520483 156456870 888379891 983932501 430811027 828116950 441322518 638318309 233419232 159825704 263970416 953680556 525573757 593376666 70321114 413340332 929100602 129698072 778383553 226155295 91399773 152415421 180613107 329998432 829562867 19836498 620391364 265798906 98995529 992708090 379553907 300280371 965367507 140724389 574264549 425807602 413383138 337616432 864984451 246784008 536416754 727489913 258853376 238752351 590148490 740370494 571118393 86288436 800599092 640192944 307732585 471070058 963086577 297149560 894423615 200100770 494666472 983290274 649431246 497712989 440536641 506609382 7586123 706222472 380813755 651853689 745983176 244645294 475248204 942047907 228655724 585775955 15030106 275827592 388041634 775537929 80358249 460479916 194005119 216094802 365841028 586254945 228444188 950762853 415561015 839565458 78756390 402665900 665267824 920264775 855918871 623956366 141188724 181895371 544735561 15099496 922921917 101033377 445026169 132254374 240675086 155662973 96131991 41030873 160873686 637831605 210711619 213417851 401284829 933121975 6245216 455457547 32381292 50743122 731314981 968841294 862652211 319549465 84408536 124602553 754319689 876646916 140919356 567845676 572016548 772819553 154321190 299799830 110865842 281036240 475008638 449341189 188470584 514579231 477068176 222367225 766214506 532472483 153188755 173231797 207033101 172383309 739252574 874364474 357149104 656906537 150896168 37967721 716319433 274143601 967093330 461364805 846018249 762267213 835592769 684591354 485549993 962660927 373631597 43200028 314024990 381448903 661615369 181333835 577411619 163865941 297007208 961691110 605905968 179337214 847416165 891410498 953875114 348817605 861064669 590427789 967997563 169678970 37752669 184637026 827723206 410504015 832970573 622493282 52517969 469647109 606536984 339339426 125152753 381621711 852390771 115266149 193522640 173804379 351948011 390381875 921264958 143885228 96570173 575246666 544732752 788209670 578596663 952540886 947286049 88177889 519788678 715649871 624942964 162933082 524652161 412792991 929315229 163560564 259433424 654288980 638667913 978851804 128792076 887046935 927406814 457493692 908319509 94750773 674064180 481266208 975456112 659346817 844805244 296536069 698785711 911070444 386256279 952250688 119317399 688390621 901014258 926746580 278712445 210076861 291049278 707910745 547229839 453330318 587620630 530174902 60387717 101718453 524100977 368169573 151422531 167931391 667887179 708522170 41893305 919466813 925508303 241681180 880957803 79578660 6607375 813870770 962466240 375366161 219040140 502475103 291219403 137094807 54347800 736839672 374164434 837981734 231650599 110528980 75320897 949269499 815170876 910753124 248547896 566037414 472247344 600626875 13208879 18453941 389288902 624292307 267669916 381483495 650420068 229341062 576234082 558162819 179922464 927595237 127223628 154901464 936726047 59960138 283967419 474428366 25872463 443904297 573641786 334809775 243519331 489063659 187429226 129618171 676854363 862905961 511043489 723010779 959232738 79499427 795221977 667803243 69365277 680108287 168279338 46386169 324861436 11428594 361670976 62912007 146144460 175385924 435899372 274656327 522683329 435933499 411738227 412601923 733532953 69972678 976849934 874852183 1997204 59069138 472740568 138443227 8521476 82999570 656058584 946902377 715844068 329913051 164318282 936420246 226729795 304871486 437273245 435345251 471236135 478334324 657860845 315234476 768348893 156294832 452007140 459301158 981941558 91223282 861730371 996631500 218903751 229002573 818495891 512516636 203538582 233548331 893914893 761209086 106462946 970518948 810673399 315335805 405293545 66172383 404469026 901370683 576882764 575381424 563582363 275635833 427240462 55483705 928022869 222624801 444280934 688616860 349630844 181772687 144232061 62662919 54943762 688736108 247999849 246327088 279205577 707690681 791531199 831988385 97049781 182712945 645003604 137788250 919888067 591281306 33733966 645249982 777553455 738759496 776975769 293499975 666565310 548300716 404985953 943605469 262107470 164800399 124789088 331030853 627641837 540870808 973689209 440550643 855033654 582272226 659762912 114206615 725453563 599350296 251497718 31951043 839475897 947191151 175435485 194435824 144301074 226557970 236911891 318415573 961078098 248743111 110055123 636765202 608189264 293525555 765435117 340656136 971140285 152004322 371457878 500386109 904195390 593973824 270397151 291978419 49800168 63652932 948314570 191838186 789196273 153279003 164701631 889682672 850151320 875186263 216244711 782282257 22986007 32137468 719090188 318421800 344446367 971259239 472452008 517503227 877963735 499070439 197776665 388765725 877408655 210346311 450297349 481572716 458317590 546751429 266676589 383089189 921377387 554369024 43304137 337055015 79609207 610488919 205891285 376754920 716077721 607776799 294101963 465712076 44942191 77854808 592204045 713126561 141825358 241758960 463836429 553764977 63132694 873743783 158753818 607328309 332867089 326688927 762739485 776442572 149808803 102726012 716280590 56372760 530525167 567936390 487626295 85899170 983729695 150902561 886544256 240611754 398071797 578379054 527314298 970006407 929223107 857255424 76385792 409465981 324295789 321516956 906154002 538071608 196458837 610596072 521092408 652031189 837580675 878359922 618378581 699320100 884114529 100747686 343814031 567413529 219011991 905459190 61293079 949801805 320850762 291681246 745904643 289274850 334636572 519047049 771587488 997009844 895943998 760279201 516574296 82335958 286926278 451147759 565999472 360362205 461333510 473187921 387785232 141850811 36012610 513941770 813854261 584373009 650299732 756330235 953388102 970771258 156179976 560614624 91736250 498616692 716947666 392859214 688739672 182206542 751607780 817744482 542399726 86050016 129173319 167829022 526117584 213887804 491608696 110137784 816742744 611644760 321845424 810922747 100590307 693039316 776017480 578822361 5789798 987395357 71704210 962229853 737125977 604469111 266516372 399875260 907109278 648735262 111470676 713609463 198392948 600776241 13176539 703173301 753504535 271466533 657352339 844853116 202054349 946161863 606259211 634249745 159983366 552224489 154392683 86402969 182114610 18381381 902878494 635244683 161469926 479467061 132087346 20438948 907059881 226087881 470597585 660904089 929818811 669073079 32175948 138549588 343123674 202773853 221169570 85028576 63874761 732090563 422022731 253455705 802108864 433550734 163140939 10097980 318989037 228359949 95190015 798285030 62360642 812757396 915688406 205975776 987851967 203434472 390543498 272532396 182319959 449179026 993953152 826634570 803351461 494701635 190838427 712786730 842207863 327895459 291607021 846665642 722009322 104211099 682502119 468966302 428548011 923645441 526232098 815314357 753522660 569502134 73521168 533336996 160222221 771698776 546945626 23243980 234071001 501018808 401580410 409951209 343997298 245811122 970546142 495574391 841389804 125875935 360805695 866525312 948980256 545043122 322088696 464079058 980627474 952192401 233341501 531764219 574231283 777054726 490535618 248105324 887952264 566761479 385266350 990675483 816684542 286327586 762710773 188478017 741431239 901084105 275928222 457990552 998664636 906924878 566649157 47420084 262813103 614597947 152500579 810386382 182511415 42235669 266330301 698589124 176273339 333700302 551644850 935761543 222780730 587719410 659723586 526531101 609562879 308259553 429584341 217321376 297197186 915622728 660892560 100803572 884620882 255878343 708008551 183528269 571054074 323410140 787707624 111936707 155527914 555240111 664838616 799260917 857561271 878352736 29423607 859115918 618676187 572588115 156410585 203363328 672771303 961985216 76046572 971289051 718519436 231104209 415008483 651350916 113343713 316883567 394166829 214875060 355911910 478168671 300825551 563562875 322092588 65184584 908275088 738506780 173744852 534532492 444831799 766977357 905968357 598530173 616865581 219989051 294805803 986300536 656160707 269912950 595027186 313900715 912313874 183497312 58229945 112591702 221526027 812109699 26645748 977614632 172100516 953257641 359395056 981364467 820270127 799272969 850037852 737617138 277153372 956941947 167845486 515122069 968321404 624486149 881861718 546867584 479637850 598230250 473089384 366895609 804090494 443019451 665161252 520345785 899061547 71077048 437641029 211241348 387194665 404051876 212417483 225921518 894622811 138615965 869212457 529493750 49093511 500520399 260360778 639499335 251905453 389021550 184993429 829585689 724591798 615904980 556514946 951165323 128137862 869285336 313347304 490632930 780797666 213774567 360716410 978852553 897921024 672460093 162273659 992619477 621156973 260102867 91380657 236817407 58739135 225684556 63903820 331701748 884513645 76227413 256334868 920717558 328429550 602900778 531584877 658408299 724646321 106523075 942256348 496623804 57454581 596229078 67269174 150338452 998535636 69304310 165941966 686353889 384387231 275065691 460347675 911125201 267442922 289001635 683819386 699350990 522085165 60247119 796280822 339948290 496759533 563201378 790500116 479663666 906278361 701411045 754006484 409745677 449824913 418425307 10126834 751113871 1603965 586774786 371195167 12011056 112154866 505687035 282003611 314687023 266304697 351200899 231955594 214147457 955710207 111680163 501125510 581564529 786466417 954262181 481015633 32657882 962362688 148669767 421667282 396174706 274743536 141599451 103046890 101681699 972188643 309735846 341429835 250595935 512657708 500043921 596272540 529869416 111852075 755373986 56657257 503860648 945021506 435470122 912451015 308517069 151288562 49577778 621733795 45243248 271978101 636517023 98425267 931924528 370974626 445559936 54799493 722315421 550234143 608555033 405949788 63793912 888718444 489354252 413468673 347393240 483452453 599309831 599391163 527885553 393492376 651471961 88275973 746492506 284926927 661635876 383631649 362639124 16226509 525255331 563101988 51672031 130903074 254490810 494111504 438131184 595981965 94028150 987622354 138637999 463992561 322304094 797067938 227689888 242875818 122657830 926340472 286125902 217008255 513751007 175143719 886058923 66366133 182242574 556903896 916366843 981277862 556044028 115759951 820065003 722171383 112365723 915483631 42353072 769894738 31669438 187557912 149044387 184983194 651293353 114790620 697046385 35721846 674247655 318553355 80189036 451701030 689527747 534295833 651887675 153778458 161027189 88049809 36127592 133707502 198530591 111538215 467026847 774234265 725134594 508887124 56516844 354550398 220322888 429102677 378854220 670225875 80422216 252709107 657120256 827972625 157232465 899896968 181064841 146714974 880960061 177888866 176019340 592508338 226027176 103699901 76843260 799181435 415488101 599079667 126907425 459401138 412098152 737372351 250262831 759504998 394832453 206101989 358170147 927246203 73930043 909057122 708264576 367288575 205351134 402465996 38395080 198538061 21783524 732467420 170789624 820417646 128920 404191167 550328862 974220570 317136602 545015700 75198810 88005339 30230717 945712678 852956624 477477734 739493929 708027762 462720086 844096012 754978766 998294266 197606384 825490368 229755898 174304332 206502755 404125446 716017304 901033968 583339779 58182168 557350342 574560022 937599221 839681583 159658366 878487912 165458808 75856381 228782233 647807030 923247199 947948465 655620723 209885821 677956626 107766373 264544435 652039088 587506322 72179966 69680176 29125456 907212909 402552857 291988787 622072011 78585774 123865771 635411073 699252219 776655951 309906180 792141655 554252274 581885352 578906011 515121088 892883882 657291351 830825458 258513805 366003390 572808545 615268810 311294966 881067153 953443757 921776728 221417551 476076810 241174260 893372036 529257965 748462910 570162480 734877016 788368682 476047394 836999511 17166622 546570147 246072668 275315888 313852161 111962176 330445820 51292191 39756872 523375392 277381870 554003907 695546910 528608328 525184625 1177488 266603189 976604047 446012816 604562407 204224620 49797806 544089391 509228927 809596917 870411002 769946110 517472134 490293883 91227819 788834038 354845346 734885320 277269418 432992896 337768268 748729881 398416353 9953827 891589432 175992667 610710678 27943376 576993537 92285022 926836762 382474861 763176580 450596675 188799132 697651830 403326058 16198912 195137829 178143410 646382359 287783120 958079948 813477152 587004083 637597577 432025208 379361032 45442306 33765241 41672158 329985183 801708226 64216416 194383448 537045609 227802568 154034076 740133450 30576613 165577653 877756419 489575962 991513585 488282761 299589770 343498227 824197484 978184511 160644100 339335607 504580871 456351155 201222398 726256439 725533648 791189438 227212888 210076387 721902310 908740877 855243306 944106485 832031757 319136153 805633866 91388515 178717781 293467132 63598617 676005695 83614572 595603599 331176747 387477681 388810661 239041960 107278836 36909303 220841042 653774001 557240539 905004718 679089240 645825283 25535165 907615047 277672861 568010571 395764764 707013069 173077317 16627848 896887300 889621553 81577792 441485052 288454036 889149824 709837549 422486839 969475495 394285447 947411176 462456560 556486655 45458289 703387512 145651620 241990630 97853931 502979887 690783893 300284766 632344784 809339294 193882053 808859499 663202437 683971187 279748839 399548188 551948295 989871428 587121564 365202288 703872776 874926441 926171504 36757830 126269887 293306096 831920535 252116483 450450184 975856254 768454289 996269641 799339592 538665886 17917339 123988451 817029701 611124679 672569494 394857592 862635560 721677313 260859657 105218525 968802996 30158435 830287050 157950596 481063548 259582646 84369963 402989480 39545354 357514641 994985652 927835831 743340843 340201207 406011671 268652451 834645792 404371521 271420859 221428396 968460913 315231067 694105968 291454157 686410032 134940717 351323661 168395260 579169711 699938716 707115155 239327582 262917785 880956424 134127288 57095853 510112192 784006760 182155057 603525140 22321488 87111660 969009060 399577577 834470803 780131247 430706116 855916716 369887231 818417536 869241621 178199711 990263515 273824107 372055448 824588001 634589556 998114424 219442695 33479284 216971211 678983421 191427978 301801824 794795406 648468385 2484827 123630099 954392067 916151739 411089792 208358095 623802303 160796499 195179873 175260352 432633834 461474391 748110262 850731381 934910635 948242125 855191337 600145922 863758112 897402162 326600419 777048741 602985749 702805846 485438827 256421838 363640202 173613133 4522390 193834070 218742193 555215799 206048886 202288370 58984383 999382308 498816232 155491861 943185374 955926481 212472381 1445357 577892550 491816361 448464234 953971006 37601328 836996500 567158972 343282161 107298138 940983727 785442502 432804658 410772945 44015078 330248859 667095124 869414839 397225902 433424810 148479702 548421647 514478799 298235111 343022936 786791003 678247160 181698270 399542330 465832179 376587665 553358500 271402030 133017766 5945107 669599296 824419592 48991598 322831280 712864394 739744322 374200027 328097844 590962019 733787182 276592220 551682625 209360501 508047949 494678461 614378833 180187452 297386494 441354211 485039759 849327331 542590870 71479192 923709097 557118620 101259286 585581974 728769639 965253628 522614952 738806800 135747936 896921653 746766387 728268775 458008012 875871819 684305925 838964987 120468032 260111654 238240078 60443500 270969663 442641078 857838552 854299670 812919867 990875191 124753825 606739286 121570625 379848235 645032927 470203737 230932473 221027678 132663961 96695796 690578999 623297282 137452255 367500506 166416704 273024174 135899114 315287605 886631533 460767982 912811915 870586411 359120132 942164478 163018641 235819779 422310334 962314693 862066864 898313573 725007832 671652662 970245650 810324388 558848346 479346748 99316531 41349058 396950110 543969521 806798419 651170536 638168184 891407761 656395354 763772426 198373267 796932373 428831925 949683488 510088404 709312607 993338803 81789752 791844380 179977096 861916232 646756365 346850739 297961578 240145499 124143762 203550234 572936498 250205545 132596773 881083601 609774325 40264540 221272195 78867081 789868529 685869532 996322336 473279673 405374009 162871068 68498264 194209116 870850999 380715564 407036986 927258246 452642291 95409547 912411739 489974259 301166403 851631168 956957415 863210850 518043692 194602041 436279350 665950010 650144610 874039289 292467771 49517802 208232274 560824971 76616873 885843006 180556917 563632636 764515110 354534332 279291376 996754818 854764155 435734911 94651832 723116103 959557010 451081136 247537483 366804488 523732858 212057094 289452855 842419556 837839734 226316955 842307934 199609769 154400891 983341865 585198560 913740319 375943618 877404018 98542188 154472594 611642009 132147991 267440771 936071047 227481862 889099491 815704389 8423173 650716801 988763251 152171086 724604468 42688684 16568479 370650742 22887420 241141097 230723392 647636734 563859362 99129820