100 100 721211399 257112740 215893208 969518512 625658379 101606988 581990731 248080988 458724295 345877169 816907306 85467810 222717192 815975049 477280227 287953976 982417599 410230332 183261786 987481512 545432453 866137253 293105784 299323367 123806062 18868362 851592982 76144412 577678843 629416353 578829258 648265252 545334739 435141817 184468105 185865221 568633163 550424217 91389009 881680636 682641869 885415576 51457172 186263689 189151119 168602396 294217801 263143810 278931220 302582456 812102293 127853969 287750639 748982227 73957900 590445210 67982691 676284552 149413521 104330391 394191902 276068649 196814232 290111655 235022364 119611196 183975657 487893477 298735395 287310466 504858729 516761599 971347076 60915137 791990443 706350737 172520702 851383663 802850686 590173295 710093034 141476678 905798410 602577504 434706733 119949453 867098686 125527242 698090249 633218940 273092582 99546319 389776153 78888815 838478594 280872363 807712285 73613578 245505967 868694170 836273888 584215286 945757074 437546773 877769457 444770765 381288022 793238601 541161797 683086296 845960640 387127980 716400427 723260786 709104933 977577434 285251464 18092132 610801886 925943533 54461116 220168686 297147393 850294290 202788859 883804779 387014569 865009652 738229582 808570125 260541132 220247558 178915090 60671653 842035678 236719280 915097965 618312107 446216593 755234956 244497773 439553569 252365894 964592038 416179886 971800127 802442932 930216579 561481678 515563463 577335948 80205027 978157313 531482616 77675196 444764479 475013393 419757840 479402292 848398786 553973976 398811909 167940240 98623963 168922141 966995083 415448559 951687721 606217250 813835698 302802522 942739345 497519205 212875757 986757276 448300365 30431020 14791084 465867286 653025406 473904692 765849459 691806383 709956480 266400115 212815092 799934071 85529443 400993414 778904624 95162395 128342807 630060500 686642208 26393141 876078119 716802191 854222070 12140302 182665582 596670201 926031466 870891979 820148999 698408425 323151332 624343755 252060380 431791122 806630554 336195515 443010593 370295520 509704161 375026419 29923605 529883625 846435192 143330076 834871311 881881935 697917117 625875545 567462947 374436224 780111845 982212167 81414755 872527538 583281941 606816187 273048220 371748813 799518453 369093854 770923785 66706725 253158580 342520973 491396868 245684227 945738869 608551123 2314288 720163480 820625802 292424810 685765282 546147501 524875611 787079641 460483686 641903812 9134727 743661311 766212665 218079693 209083722 635049888 807797138 273784313 465148289 230750583 693931046 270937278 38509066 366525514 410878555 470940414 731097935 229261436 939644042 349963498 221000782 896496718 262014469 134626904 655170406 215724064 206978151 60692696 352972310 708881130 657287130 529410714 181222779 474320341 472470837 34415176 697210748 961342662 394744606 844077368 142221030 820374104 901578955 875217478 72535676 777025158 698648647 139437569 490491135 971492431 855156130 933718473 29657691 696077115 402088709 292010678 555341299 1111107 443749805 485861766 812771815 594803472 690458225 993981320 869311590 132915040 289848808 88820092 686221098 426318440 153303707 750956214 980174914 340070328 986821535 662360257 233688392 889438385 445558140 793161995 381847897 101595861 305304159 446075320 925990700 37992655 757461640 168638325 759585886 770711020 923768210 174093127 615564286 558814051 72839919 614978490 186206224 156636341 273697367 914822166 181742489 58501854 46822504 919234589 364867832 113799392 192501847 900869981 387575697 367890928 367095781 789840791 289075350 394237636 695079915 733156485 423562804 852390755 556903804 525438880 485367360 402139571 28381193 394632643 353874205 56591761 835468826 14815711 884791224 743570141 29520954 415399481 874637514 151092768 96191688 871536992 617143577 637771725 987700402 474504443 984272379 356984989 724635108 344746326 662661175 371420285 218300360 886554336 708029706 378604121 792450662 19316433 488308874 144933690 804703082 346208236 844943034 166352201 432886794 822981455 962898070 998731609 677151213 334163018 441841483 485186347 304176892 47618172 210614646 194464113 545373044 229060506 628616854 387482918 375847085 826416609 738760258 399210267 705022211 741428610 445960040 528589884 625750378 663649205 445631670 197223779 77689217 38811803 751638238 246670456 872611305 101232662 263396808 702668186 675382738 569225525 176645404 793688450 149518176 402596397 238475379 260492166 602127102 861040858 338367725 565530526 159804926 472898797 130010284 891343744 865614606 347812566 26231650 408902201 411079756 257444581 395866455 132707519 753821886 570896077 566293636 921342127 672477092 648802307 825098107 663860423 753702635 858423860 167729164 700121046 541530114 375940433 415222654 803325104 903047972 123997369 435554679 871468936 927083041 509141868 60844649 545821451 125795546 922675602 36300387 682679888 694520944 78168485 428607060 252906027 952039994 710766506 411688183 93121047 286770660 261296761 585194609 263687083 834937367 707708564 725687717 51623286 704017443 344981145 54182095 426372923 519008578 73292792 659918533 458401532 978612210 531407724 617026484 970818554 491310537 873518182 598487554 930553187 767271797 270729972 248364078 150167238 748785312 638492361 442878079 201524885 34812473 586482085 131671083 195724833 624488119 65144029 226878036 448924197 917192534 636449805 767759935 94134664 963329315 549718044 10524811 436834886 860659583 255241887 907907588 171877882 964682783 234325951 576358634 896611546 438342973 31870448 417309556 147484507 474647780 518169869 669643656 682640912 796928885 410319688 79303635 240357834 269505752 274347427 735031999 649398616 462928368 712901818 227189162 970285640 458698805 703507807 821542360 421915465 199319645 245539508 917053975 534638763 541181124 726566189 433055124 116592023 187702439 59809199 270879500 224158247 350497593 419247315 786747684 667174414 483300629 9143627 846244034 538556266 837149218 290874672 984394807 335015499 815383545 433229950 35057147 460024794 257781250 401780549 250449805 87393089 90008930 159143711 194481600 493359367 688485187 386556789 138738030 996701674 697695727 769619508 222765852 582851262 965118835 547835058 823228252 49995993 376267787 676731531 819016674 565430176 436601709 515900155 913183072 766444680 628552156 782990397 248813222 216690658 53593608 184649219 282303925 659666538 785953437 330802347 733476826 454779150 676944799 44377325 964220187 422938935 774291428 941848963 919080308 687668594 592107257 819405496 212446574 627524718 416440892 585108412 464697650 970854955 227499437 489713883 114926570 790301961 908291307 231410960 436479091 101961129 831678004 181326986 902743563 342304112 851615930 460682857 198200740 889387036 481101839 592625529 359655605 642610091 639867728 384949044 457449624 669619934 785364309 404115948 90133609 608069116 93583490 535810001 481005941 307906538 510907331 83602478 839125202 122603922 733832716 574905645 599321638 73111425 759284876 453055571 69778425 899060936 370433663 582639069 752391464 976662960 424182030 287880819 979770120 649913430 438164933 934754894 323692718 349404251 944930036 533580548 796908337 847178470 606368284 331334683 622687007 8953534 421220707 990225517 293191753 406122579 519468566 109474999 404941496 736027470 418957141 325059491 992269973 168456729 690861370 118490515 900316576 697573611 702374554 993262215 771162201 391914681 217308853 763738609 785122625 654240323 316904365 420961510 362423288 48933940 330054545 409428959 33297897 29265679 608530231 952241639 959002670 409388208 154358815 579240185 909592848 940734885 252872393 576024617 76583804 172328932 166538506 951613582 489443936 187939874 404280154 128146148 235162101 362451434 485677033 434850840 230254699 977372510 179372091 554054913 642843318 805840602 669621160 768983729 246648509 402226248 69051382 74649229 936690747 119731226 646175730 992717269 667928328 859945265 418740467 345718257 427549571 832780281 565688313 899867392 33556313 923395095 665465111 875205989 808287345 186219899 898254644 793465042 764039248 55635156 445845824 806527046 713780243 576908697 731065947 734936252 378799915 549705560 556193215 597518989 680574497 37021374 701968456 31455782 257371413 812130603 493357383 291056371 349507731 807214256 794281324 703504128 45095419 564947664 996977630 104960939 154033441 66042408 427534611 383981495 68285484 925251900 197708405 226263319 85312191 422240743 854759730 641687796 33805136 496701862 45702952 25095954 929572168 695286500 978846600 918407676 450832255 599694298 196728079 580412679 636740615 835298242 196019646 832838406 326749627 186756527 846328217 422299150 66396082 819269779 761357150 734833966 489098499 844388035 550386620 129443305 827808458 439467063 459561557 708953217 105727768 730161251 640771323 71804911 890417553 711940356 122258383 626228459 3340445 348913074 696911467 304108601 246357495 29009355 6823002 391989812 319967468 306995106 854328104 431501372 667074246 708745615 368884821 145481912 150806847 479962435 128462794 792853284 990705571 248634590 869384397 863684381 935053463 932959460 572853408 112839601 959597698 115700495 490086560 645201997 41566217 517189992 223520509 903577577 58089172 801951905 688955289 501892561 348149143 68690508 36540388 98870475 977073107 448491010 503802135 304571615 714569651 943129434 247276823 665845819 463580184 270530575 695339907 356958623 281129487 80782723 128352435 249688049 41049085 318771401 114468783 641948343 298297441 172553735 227896194 677183701 575610738 117649361 231975870 894126112 123004359 626436558 486666935 577472623 50578843 187271685 719610046 740870652 478008468 236052158 857233528 798043218 965736980 778954580 903577661 939395749 635432803 782693231 257226511 364945181 620906796 510652250 307104686 626869040 462610224 267518064 887640149 800051619 486327761 329098038 532684410 130136079 734608132 59521427 872162478 660009381 573998790 264711369 546692164 851575697 461552242 772431845 749323111 115207947 495077228 555281225 823325317 967373896 450007826 829230921 760619545 872239561 582272819 262756698 229250758 725478406 791361786 339881651 382367226 828062665 227242247 102652214 267531698 685114093 694801244 644904317 556418312 261318143 507684709 632161470 972633595 910880957 525847538 615165834 28456787 184043009 703873150 306162413 542585676 351558437 245570238 311169347 970610579 684407487 215808372 950002775 775105384 503910165 238628906 790257052 78240308 944385069 801959520 374444412 715766855 46278693 667068432 753301599 869414098 734990334 1556466 303251578 774224838 269129882 544460006 703328156 304667840 156405128 492059499 843448222 474745321 860629027 882324834 566348429 378727407 218804978 948009840 949003056 43794854 235281573 910948253 309001037 586350787 441832046 829655778 520729946 581247613 455517324 40954457 206954 155075717 862196458 909801494 23738616 831371269 881550603 978124521 822817749 298026970 936699113 77177443 313963445 958559770 179707003 206246542 54286529 213062243 687742697 229886167 156558850 351174722 167831480 566547179 230392919 515704950 278619059 63919636 213596585 241626155 607417234 261463060 511115942 663227676 650686590 950581053 642048211 746917664 855155756 681172040 36726655 142524657 557711654 893339100 385941589 332709950 789264666 147301520 228554750 26486857 608951721 181289578 269593421 856103728 234671183 255015216 327836987 289582595 63575738 602389921 746386228 715434979 881310053 979908069 16985104 807496427 652442410 611056504 562900667 67247849 905393905 232276283 685360224 493957639 418584976 331829949 578196046 367937727 127214489 54106840 162150119 732887335 223836949 378986098 483090089 857614232 266824109 913150486 100544387 400648387 518508444 587187412 697829770 397999314 96439083 525532203 728952822 247831139 23668167 696211504 698940624 482217936 953085252 501156616 456766861 260657178 65890753 749876803 282682054 661919109 147513811 869546973 500936572 770345689 180803441 906784728 996381697 751752445 419565801 967809141 387341190 67361641 64164081 925026553 598590224 86693222 124303321 548288741 261741465 790593507 299139251 287838562 98115989 500942776 830013836 642564231 110529006 674046418 483005030 898708810 289062577 693671997 236544567 187167177 223295856 48909401 669864378 611683409 793797501 619377585 408913356 906298093 318528308 183617954 731035605 833604301 269164231 581710434 870460737 693903122 293877534 192170191 51252559 631978543 470342623 622372751 299905353 664825298 465953763 385222210 292026450 296904914 987014634 59958092 974536065 131303328 617535208 263872583 906560120 236667329 312935964 347769876 787892898 39310187 765052528 607487092 355314510 743951738 721471732 478690695 93617425 379805715 232581189 375566421 209901760 718686072 625771338 234619568 201762174 419778405 283557200 161839590 272359392 571903290 943349493 262950192 947999735 428274426 831646592 604698646 451521955 904120036 490065968 700177184 374577298 629543497 460829540 505019767 141503853 169957862 270984458 887276070 185101306 792030480 880906153 757764507 689973164 461665810 133334759 262729852 430409515 29818432 325642618 313056210 14942894 265847190 739427509 905294924 440209814 366375093 361659734 820541610 182151108 19750754 488289265 980415418 271639019 309302883 507776347 329262285 250393348 530201662 292645266 512748402 425163043 51854405 610911459 358580671 842562927 93289672 278654645 276500745 327374252 176931716 644674921 29459822 994845366 754214081 230766013 655852458 220773581 692040450 820305420 820045077 798069617 830184087 329011812 709578929 14750072 30686100 429518044 560841166 543483655 757895767 760154430 612221168 660947057 361459129 672126508 182294697 803380625 886763958 774871881 402648334 473253916 223425800 104812575 930746133 814335575 109249811 601774006 53712861 33013470 865285601 788491061 593863757 393339432 190431914 314112894 283462327 515048349 828764734 671560329 930292825 924846380 577750239 26017773 390905797 304671520 635203512 40444901 714126424 843131340 897115481 703537813 303086135 270570212 965693016 769384165 16489519 633379815 673207451 660130530 555986629 750429716 137613133 160977287 729273793 600459816 3041096 517642933 156608904 340478523 409161946 730623821 84354852 434240102 923603464 470068084 18689938 209234459 910669824 738954019 411952810 10600444 384265448 497232648 148728312 537644856 882206836 267584529 373136179 168523356 473472503 347961243 962781360 105868036 51742757 721182978 711598057 581133135 398002157 41768967 924875546 953829799 952016914 771762165 896171864 974389787 98536998 642770195 527477018 942113723 111897436 803153922 33057369 308664414 422498255 754147894 7689543 121606516 413628174 506349359 181855475 908772113 797433500 524620381 854545821 946711927 234737852 381771021 266742933 524153577 14509917 569495467 366348912 960497680 834757333 707681513 823148956 594815120 361427004 65709084 28154117 223056837 347838409 123363883 862085140 511158337 136574766 990817477 738088958 837554407 225760353 488835108 883521100 514393380 319519700 41309012 885296863 835289161 549971915 381831011 721263023 27651708 849935746 924296108 948562542 439876767 251071691 674571612 40231460 540047331 331876134 789654079 902242411 962379240 958354632 620965576 857744278 116919125 31159916 588222037 797167877 31707743 634519479 344841151 670141934 73987991 489618927 285710405 128298406 898728840 242420697 211846969 788804184 782509995 636619671 396391423 568257202 369206645 966293339 844393907 329876204 412664563 18277093 982406920 592228261 198848910 467346593 879490150 173769966 271087151 841915925 555314708 439044029 119827489 228838620 46872819 299958421 372767365 846101318 179283521 963544648 488203257 93722241 242992035 875612360 38873712 355760037 718293277 367342951 333800292 600316024 172301990 717815523 947973525 777774540 488559164 201356496 562958498 313651194 962223550 479526001 118154400 180494265 182269352 215121928 710204786 357320206 560788233 299476948 415271864 642907416 112155031 733893026 583960084 788033118 441445379 416637447 671066233 118102531 300421701 937435819 402510059 343144746 308016419 35396496 200931994 407029420 508013928 915010459 829138760 243477930 34432295 948340970 485379053 633470629 752101437 926825610 634054305 744505235 993025618 557208012 57238764 113948857 161742249 265094291 319679753 597636576 6227204 306689767 519466206 953856455 640634682 382281645 418736389 490366155 417340287 438583173 877278812 173218327 611901910 831300341 263502311 876143641 319645911 267162128 200824630 800662043 264642999 846879622 670162210 320758222 637763924 892923501 261646675 898774774 539731865 708872554 860631518 750025376 268379427 455808536 24896197 539956128 276086276 200383038 940723050 906213989 20512450 524608705 121552658 645663650 173724244 992513872 706308583 976624348 978686486 897576027 588309139 246722820 88497945 672467197 457996655 553901236 783070469 275070958 179088764 417117372 295840360 805489819 667574498 730128428 317834685 85684787 728857905 136723234 795147425 99348 830781977 58322125 551267253 784255434 378794918 734704126 618463078 195016443 186270958 22158339 204565187 792479107 818704375 297751722 817277794 445429891 406862629 142855505 467406145 114692390 429753110 470214230 452383788 259835179 227791275 534732622 218288491 448193374 832779160 67885811 667082071 652141272 975778757 937934515 160224863 705619507 923445427 790886264 765577463 228815429 527574742 700963089 653251760 990790661 837626731 287937934 527627637 115231653 647382391 714576765 976770074 798070642 720296277 382984397 78474293 762075267 716804476 169749069 973875930 465610320 390729433 595420079 43428166 97254135 727325594 578956124 309146005 242481641 917925564 944008926 182538790 670226329 376668655 131787009 23677019 707936604 438702466 809733194 190003728 110664346 597092317 5960026 746186526 87401947 279839885 311000362 133731203 311099848 119743565 736661100 254736706 449864599 828421417 8683914 433069262 460887106 192964241 719363659 283637217 62612898 349924528 534738464 203956716 355745095 539528287 286390289 569476892 125319059 779580834 296488681 695514523 312939823 245804206 782247571 157506291 229954764 903879714 361737549 825634938 839561882 7439828 896838695 23427074 291253013 488827324 94814366 838339964 994262502 925339295 127921528 193960612 526371696 809346041 914866332 416007903 574975212 651971554 76383652 315542203 852599046 125971886 437435086 707545317 244565010 308069305 631961299 29723207 183378541 966793033 972235446 428795155 189413061 99307713 939557317 812426594 533841048 848604314 746209465 301350085 547236341 682764912 864676504 120236692 115484043 387080875 669241950 221516968 985904556 245583383 467865444 964785753 465223719 34675721 32072086 550732470 669902886 636403459 965988474 333848569 168820497 243013781 2947085 796396920 284651627 171014315 459564574 650539739 192559185 999794187 774122727 837801883 247689936 423717609 152924349 681701180 873154571 588469134 260637509 652109608 950838332 311435389 277632498 504986854 105826055 76448663 542694011 231986868 475919721 399739332 359677786 156725874 429217514 159487782 762552184 178274741 822417160 551519683 110540929 452419749 366268440 622061352 653919735 980987534 16279063 606980976 580608230 225265636 207998183 265407023 495616785 197432789 773770175 776831245 716528953 496799790 600838865 113597024 87505224 873717544 149796028 395697320 401345415 609610155 958446159 974617136 652074497 583601786 793583140 508080797 990861944 907833787 69872715 895472407 475017965 455837594 708624599 682564238 802018430 677807298 528682336 296454067 367990101 163285025 302970054 568793811 880486545 36075535 519459646 822894300 167736755 760626995 795979012 708832487 297245006 928154835 314878464 957990347 27001882 467216360 309431526 674817348 741899003 974575391 837170491 853452433 932564695 654137347 739687770 439491624 969331470 742546628 133610441 58488125 28043937 23181304 740140663 753617268 493460391 129523772 280093506 811885666 452773419 394466780 321634874 951519486 671059095 63984435 302806612 502886421 53809658 269806281 773774540 101086231 5700361 541142995 124089898 6285610 438843801 210220650 577210590 451804878 585861527 346168610 702988732 863170826 254337318 285900414 434603609 322133456 826151997 910745914 206812403 171465224 390987566 624579990 366084453 395874019 758933739 65139686 343865980 796913999 897553256 998108602 983576592 422456034 212206096 598299186 353996211 837106259 174759918 785738787 237746681 505052370 606775089 284189851 584576360 251858931 331690225 869254683 556265048 76750541 301025507 590324459 645012597 489132629 696747359 491716415 436870588 804880877 906387201 152042391 115174202 988522465 289554218 314581521 285127458 826019412 174535658 166676323 773570090 759400458 250168632 675648357 193690540 795070896 629969244 999142676 489454214 683374900 863038005 515775253 208413803 698665376 577662398 758433088 653015011 460423048 265989425 228869595 174869470 218081078 518135197 21875880 612670446 758495031 570903172 349556539 572675937 758591526 497356307 130229646 205774320 672216772 679407998 43026311 505971208 593757531 838811524 25780023 803322135 697364482 538981581 791972122 382103678 412393502 519619802 356112112 922477293 232115793 524940126 853880595 536445847 467444943 519362368 756193269 973009728 619855558 896730614 145787962 406608384 170142079 477472939 262238981 308844022 858168919 45066300 323940003 955000172 888940064 193325678 629769390 621937139 708312015 873698415 280480359 288664700 48192724 840260640 453891825 359611002 640611001 733764242 335229985 115240543 952724323 342120813 638796881 565388881 993663985 505289268 801291785 913739243 510280817 715635735 164324946 447805528 649933963 191160515 151225326 677295570 405704898 223976743 493584510 441898162 494674851 786580193 247823167 911227395 22997024 202930778 553285828 662084995 451748717 360080110 63815600 832232158 517603437 359888127 115000323 862046356 991824747 353244523 740059910 490964453 363835154 486299 839729801 970052018 102183433 890103342 877780750 190365262 658873533 577766843 81609353 918859224 437446136 998237775 596758802 368448099 623732881 741477046 737006654 333049817 659113628 836584520 643688498 615565052 820446101 665796568 20558979 613734291 959713172 565449543 430261272 705483548 284396536 87301106 489617510 151001426 940296712 614995325 918903986 259832368 817719089 504323054 223257974 684080048 285971669 391427669 829018414 864066425 652210485 144144271 245938994 971770226 869121427 837166922 904134428 953716779 634915186 10113372 984630689 197321775 551534501 864785148 858143783 866112401 303222164 790208434 952067493 532783078 362146433 784577477 99549599 516743297 155134177 610879384 633452011 822104127 757184720 741542431 54726026 380375163 469512578 167298109 784207061 88417625 526984188 115396070 418870493 333630511 176942746 842679773 113639429 95452277 333046475 325564888 284948900 874732036 367728008 564773855 76182775 54576421 226019204 626887038 515316682 396835580 991613085 689759955 415763007 839799401 413092047 719001840 284122079 290527172 557720971 176858883 859869886 718758662 669385687 861924742 998683684 161698448 945276416 939863048 843358686 625986709 41752505 203601277 754768629 191730814 615883581 622286481 745814647 164097967 977454204 799272623 220474746 686823061 361380929 335492257 552589227 433071956 336086726 234162219 864624719 14286903 542537460 804937175 5253243 397002686 911002632 643936647 522191752 276590355 686034719 746163481 508721273 60488880 614110619 707560791 980994910 803730477 441796341 3835503 697968385 199360403 859429236 922302904 104508273 4380873 581339974 102623897 458572413 36970635 992174711 934636090 936973497 297929067 186203795 183156765 97604922 533834394 453638338 844270454 19151718 958880651 496963364 168620041 738442580 68077626 883266732 741926930 963238159 142016008 916878012 251543416 913944833 485026452 334872977 251911722 386586583 571889983 814214083 369747167 467146280 769638875 150561397 147232138 454268627 41491050 369919703 638847708 85322265 493861534 350413047 518092485 959220617 317079436 926474121 800351531 969138022 240790124 571682767 862074301 105895060 203176438 226988348 698029940 186365366 713648580 188653587 540309597 888342883 931401499 204017702 912287055 378965484 163319301 93066913 372946734 36507989 260235070 947850745 570125395 762415187 840574997 434893845 356282725 168816722 516892958 980403890 49272958 434163270 24194373 544553909 367602547 75423797 752606133 279543357 214682155 262333934 369331060 139023972 145794346 894184397 73327358 193819162 639740242 30802588 715177875 985859802 90944189 939573568 939082904 722946466 182383056 841440961 509017616 156239867 459909134 79977498 141711476 864217506 724489238 358484700 667088639 322776272 957157571 688695095 111435531 757040600 626433538 613685739 891849572 95287871 824481207 365272619 885510972 13157737 19095445 97459440 68293241 728370401 813844204 272604547 862994024 159620384 999627910 980455593 979620903 820354872 111649201 682146606 428942286 325595407 371387133 167783058 281161248 816102859 820435537 926539393 631870083 863694054 986652863 252621973 704682411 89184666 651310408 504197751 891816046 773121539 152483305 981643084 813791760 915871830 208188689 31997990 218321058 22070484 437154782 631724012 403650055 127802176 679796686 607379401 3564161 9403611 829787697 741701452 218667377 387151985 312624839 757880702 814616076 692721211 764701199 477639934 440950106 508632714 502157085 90205053 227899587 648360187 159127928 640755079 395325686 815832082 802704924 49169085 370235174 187773586 680183303 662958432 433043154 551732623 299018250 414871118 454378599 26965106 786180236 834019510 112142169 290127889 810671517 364788931 600879957 455530899 879423553 544926988 97224083 240941032 487461828 498711225 948276853 925380761 216468372 201704316 506126886 550564215 90707834 973110132 811158138 479766809 819201965 905120595 141199592 37980285 622900149 523917438 282064559 2874512 504590653 270987651 597145806 916632860 303816663 415447027 417987436 463038462 768860262 403073786 480827552 739469140 193157549 398174094 330553369 510995852 275299347 63427217 160144298 713295642 785529562 534321357 412764366 973568212 607577352 871127042 828420046 345445564 394528317 372457625 354003314 660278269 585183438 458446546 483214807 554611383 115228385 970966121 520091851 90657667 980891115 594785637 37157734 677589924 311392039 219370737 390360014 586094732 596508730 774949655 705208704 285507887 595899110 977010938 773733232 130265616 352197411 473927106 894139240 728871097 740816363 440190794 842245963 514490792 999481361 474815723 171112254 53613069 931366799 321482378 292953861 82913430 783869130 760315126 754212969 477589650 858256581 407161621 754896515 760928928 981061854 657119230 397590992 413273537 963570513 133897947 174509347 482597100 453222400 192436960 108240926 419484422 844980145 880751770 975288374 275887686 87063867 433708321 645828078 31480623 251005008 894030030 553620313 79532987 514275965 634463360 552951124 971425827 187589867 913114124 450929472 30958353 688431713 270207111 422838991 107706044 639799086 405510306 520422406 452742401 646374710 167200261 450957073 774538064 985556147 348937988 720736511 399165579 726286364 297222767 104492696 286549743 700115209 419990072 60158819 410248072 915951971 515170392 444796146 708899196 952644793 111771255 835228247 93021910 760828911 155430408 461219144 96177298 513332306 162630602 942392752 31235048 454501081 827031232 202846303 801096632 321531320 23823821 570065329 325000042 663560103 626493730 519618648 153222178 17301420 171654067 511834166 67333979 433018723 157489736 262815224 647124665 883738519 629747050 812293903 267037512 310152674 258061657 45252731 415623153 831134608 478767582 702512977 917589978 602088759 677491467 760796935 319975464 753359074 765552171 660230354 442656772 708721953 589401622 679413070 656298084 435127961 325130196 485003658 500628767 687790691 101063477 732349108 847044480 844259211 952416673 443268553 901838619 84872571 44753631 839023892 852873651 998355177 842074078 478550853 130669032 534810314 720957730 879550430 53849427 953776915 811860750 253759127 802027148 127342649 967648525 193935530 433946769 304463881 496900644 861967718 431107707 738824375 510374312 591187280 815365925 724963336 868373197 806931956 15364312 510213853 668236802 66994030 624194609 848180946 611870594 444068491 749591296 601086745 733001157 237198248 107406891 740319676 710295057 848318428 829111747 21811587 12263523 835103841 319727031 676597500 200159145 637512135 18795102 614274943 868685684 344404798 537618716 454953311 736935714 833711656 217602268 271179195 124657680 688890616 155878109 372985778 845914039 899564461 258456840 133643615 617665214 10931055 354460975 201047544 440395564 948016131 855173826 531017884 734281474 680839116 335665451 3929881 897200486 680479368 315795453 670375856 750248839 185989483 789832487 191173496 360744119 742552033 524492892 277173877 459431938 264191530 624524653 79487676 729858004 827091314 912140712 632558562 583855865 20310244 902359439 59207586 992913926 338576880 545734177 306134095 252120022 874761769 642513399 569460474 729190874 93619155 648275573 94340605 55708888 641506240 188644428 375476317 238583616 940742304 245021892 159677010 939107282 850567406 668014855 182084021 232193502 311004420 165563085 709769026 48324358 9107772 283011901 575863119 336706757 179591841 280695484 839152898 719819270 628320641 566988789 636183953 103302682 450857340 649361057 501994232 310542065 970625610 741360051 711255899 488969263 602628236 140896102 813396812 182943470 729006561 551475074 113475804 284483541 988309161 382070615 116575058 785567193 764192927 555985050 856833876 877260287 519706622 688038400 41695706 153814405 738733449 99551462 205109493 643321322 104673441 535564969 360596146 734296859 808950350 554549905 734620247 987632222 951392886 981641877 302261719 272159274 896384547 791869567 527228941 766115509 302309349 840461431 958038098 420338820 91531424 927801397 626316868 376776263 14612771 713324362 616121784 602378010 732963066 363947276 881206793 227883267 83237176 685353532 84805611 902331830 239377104 398498291 51912153 96468635 643858351 280607641 864984414 400653525 120795960 407057652 193954076 637675065 900144843 115150217 787421601 112606479 923003324 173543282 137944280 165733299 667505858 175759383 334436534 5225103 686489352 274203274 149162437 565691154 196776801 992191832 203808648 411067855 527308770 846055638 380093637 209471473 670784027 939769723 595953724 17020246 42804256 27133210 852259808 362068799 858974537 875315357 813643159 566924468 839246049 35134577 28836203 840350404 772609021 162181182 384866143 375997971 110615790 85400440 998752840 931209217 658240932 6237427 813986176 878456573 167102382 168361988 248983847 202257709 406704871 220715303 502420423 142346695 439715236 143096821 261972684 871589546 10523156 417083662 39598318 362676640 661776540 245463606 681001278 904910433 530776783 584995260 156346514 345232922 398739663 197677020 912132882 912919287 509061463 204810406 546643405 65328990 927485932 630535710 969933773 277094344 685370476 177892156 461389693 605091120 286382462 456372057 363472336 157070300 377369352 574456434 355430976 667231648 617052104 693776657 250122982 252143845 262428970 518854813 391009912 337513854 266130344 926673852 896943497 481221507 30822884 570553136 653748668 531386631 820167099 998013228 401505468 895938626 169236774 987407476 213529091 240387593 773695722 482365974 364279423 452806918 721612496 701492061 937587662 722585157 525609979 418356032 1694875 526688885 330269050 465651713 645576138 765596000 24990363 494410433 996286766 678034982 671266933 823128318 382584235 678279910 523047361 364171592 970533945 478443037 719196731 466234546 793611749 959269136 352387350 435742679 258571154 913583758 686722067 909640949 542058903 746547038 781899160 202049230 691928802 425148937 198096920 645037645 647085478 256784830 741457958 160408236 454594215 482243561 821540998 599831512 547352449 647344480 932649394 611534181 844788695 291415374 630770273 348198622 441322680 382920151 769002402 204535244 324016446 206932123 256355014 458569197 124377030 128394715 223150620 109969041 464605967 505490019 890694685 47637234 474091202 402473370 204362350 748682945 293623509 974256997 795390533 499876748 747143890 257139785 950822953 627954347 7571825 144941294 195169936 930497971 863497553 755043723 817852432 150658549 177051632 97672573 881323175 926283324 231990950 956053561 76457011 251342834 723150009 171865900 51340434 689613997 858699925 993702047 782373481 257766171 35440617 360860189 988746064 359870474 562330404 465424357 73724582 262399918 976398713 558906529 880350150 831638711 980689512 400360965 901120964 280175024 556432276 934488979 896464466 549746053 235491922 232703215 879530937 347143506 404678631 500942639 312481865 88933433 980928460 33832379 231185696 710704457 844287727 742003601 334963243 470371223 105416971 864316224 33089776 588406141 698396326 757362554 86068303 935982505 495522199 790363615 385250868 310548698 779155948 118971365 445455442 39770636 675224975 390547908 587621939 7453034 200022631 737904988 924902095 451767623 119034965 732229982 467715662 497744153 492888084 14894230 520235926 872126097 675731922 920532326 18462728 601059679 130101442 699166294 457671582 60670627 250544507 695716664 99835600 84000412 585244599 320787865 619823987 298530769 252365573 841430257 775821270 462896693 949472482 62723810 75684056 242199862 899944248 444360726 858865661 947492269 389063818 241322142 400175801 775398667 603377747 174942564 734188062 642335958 230264442 225584159 261273115 771986931 646297501 542520360 623591050 892593451 441321271 106781399 725299800 189283659 169375344 766247874 925500799 335967272 654812341 69476092 218800576 703088416 852109705 135720277 221566392 119193858 803286801 502849013 874397577 411990375 146715336 173996735 178481835 670566805 518438069 415488063 936241437 685160229 574156546 382818996 536793077 825862671 998841161 574073216 782022406 811830036 658076196 626022600 470703403 361690017 443201744 387749496 389769359 807446039 174581027 29226776 45399067 173143829 473329951 629537105 796456914 743421799 590597565 852355223 191375362 771011036 731257269 981483292 909955705 919856600 846794896 420941613 198128079 788508875 422205614 296019969 229966720 928742445 442375094 997163354 980513327 734578847 478664821 334547670 995122127 962995685 102474028 40949743 174052050 410001575 127664066 510034874 407975120 514626846 737749133 224875881 840324580 402237295 517244660 711147989 855963078 777582568 955757588 718320137 4507601 16754907 166062961 675549003 181020516 241177908 991504030 645712326 899093433 380079208 105132864 573500689 991501179 224738231 178668087 677382649 323520171 902626347 890599076 334590344 21868375 63661506 320899642 939413092 461481009 549045122 73080525 831778859 683912190 946201320 100654984 874870000 963735446 520377582 895813507 977310679 49965866 437749779 39376815 249728602 875305192 868228793 87388779 882021147 160090986 59383507 633300669 736783751 209545642 335132995 339008352 860097568 740629894 242931930 245500574 580302546 116524073 130247382 802061602 883330087 35283202 136012385 272783917 647913045 324509981 225573338 277349963 756639292 894278310 184194096 117660586 758285034 52764853 505990235 116049186 708686114 104411405 520607827 28052362 556542270 265470536 604432211 773699770 228343850 33238875 575748092 834028971 263839416 466091040 299459884 913955138 499023379 473073106 228255595 594997876 618980288 878071531 299567962 88089904 186041409 908691919 898719934 470275061 435822449 480905519 942927562 620224213 414720068 874738567 10588020 719215213 199217988 700559163 835350352 119962006 360186282 563244329 846376923 554399900 388208958 510819870 296723739 32646441 800726753 766897859 72288687 323702652 875951631 436722147 419866468 881373428 328710123 931304686 219920641 11517450 594407365 839345559 947945982 761147000 352418952 958282568 230668650 956643247 247651987 964134502 91031787 804423870 236714866 971175806 644199971 145915871 713449078 567301888 416603795 799258812 943643284 189375309 166963498 345025526 715709365 134262489 405145308 621350459 239376053 207525420 194648609 762535986 167613085 684172054 977855319 743385413 389424644 589702093 608138194 5992247 432369577 113654757 810963888 258441040 758586953 758612741 46738711 682153096 641370674 161993193 968821301 518125235 850424913 19310196 295674295 426062946 610935280 769371586 450364765 140066423 584575198 550046051 561768273 758696510 733228102 693744765 320819072 179679422 432321756 941639527 579102568 799071322 8088641 184187653 271660162 781702325 486147595 257744525 180507642 905145706 719072961 849578624 105224796 637230937 722851645 654012588 822215201 73210110 685592777 335799403 917263863 887854211 711677641 311880883 221188207 298890418 822009305 459865096 243280022 186833373 831538391 874992006 588852000 783685553 512653250 130479894 578983335 321539409 393595724 147942710 270470374 386780599 460393679 653374295 138056696 260534509 619638179 763857829 546859131 965198593 673078412 611198496 638266637 331985936 923960407 732896390 517146896 264014162 12476046 885369954 880331708 762420105 120975900 420119768 729194469 731852717 197424000 393060 123299684 782957433 954745661 740859718 35710741 378111433 30199495 68595886 448338377 430239735 585702620 1461061 176610080 134783216 724677930 256294692 939202161 37622659 498480395 607142988 121761715 898568813 843480954 407157154 942909281 698254241 832822420 118035901 564690396 935604575 839746044 863301656 376883653 867771414 499675992 954134815 81302406 969140660 324155203 910722547 915651300 958489901 853452372 276364263 594156500 689996349 905365548 834970626 426927711 955161208 937610722 211252484 945870795 850461725 569967834 372202334 50203185 606911391 884661937 347856330 911388326 798391493 943053610 27211185 472019674 405018053 291293180 361334998 87512970 643702530 879334822 188064062 723020273 661392738 801805618 304803708 769066339 11244625 817365454 988563834 110989664 784950023 338278081 985061882 814170446 948884646 734276112 478079916 766756361 298366836 759610712 894274559 66920038 19902060 826073573 207184803 85912646 548288346 822405345 195558843 317088287 378204024 212124111 594089763 195905924 887432615 77226353 831269701 498263006 788208610 784602430 608032369 650441176 775970256 992043479 163086186 771026750 835859164 728289348 307218186 411321181 167447324 120809153 390348773 379758308 94203902 859649958 869723024 335846703 340851170 122516403 157732694 531355002 913332867 607447557 100822043 118313547 801578224 766310584 793015679 507902899 870561902 587137670 260879259 38402721 977886782 215790148 446049032 440468849 538848604 104088633 239431867 729878676 870943184 216778085 373526928 361279776 942992445 33394411 89593840 253101528 619332243 849054158 317398664 533516841 652635491 732130070 976484035 207587657 223997927 196178013 966565230 583826688 67537063 192001785 952964786 197722977 691990828 99220835 10169245 759558891 740595650 88180677 219417099 888976874 737883592 870553542 340446266 161261862 958428656 967394138 599143518 340927768 727799601 888996868 196999381 72274531 665193283 143771071 638870187 441395864 914822809 47672026 106463404 269513653 454571114 598836515 562288744 131628916 576867026 124468041 856209488 401186584 259889229 103120340 400527756 652841131 172829327 790425609 596299091 473839175 871647776 65304331 477416086 612307193 89589186 239834474 185897661 380034785 241348887 192779595 359095996 640476866 893089640 818925964 345120091 858543055 43168549 771808672 319887661 546607485 750992249 555824843 188579062 203003230 504501470 15195027 597975613 559249918 851007179 697654310 879747794 396022518 296906044 642924339 912432567 324995210 764689321 352909684 339323994 379267977 872271337 846366473 32576 203551352 148820484 967873847 448483671 260275195 92767051 490675654 116150991 256698765 437903328 477431060 741460317 399266484 148946651 374779251 874335271 299513920 650511224 21972869 907145290 807578016 979063088 451000752 278844615 259760649 607269846 188234370 749568349 157908103 793771492 949027331 901926321 596694808 14272930 262422579 354202684 261249835 475469644 993474376 470731300 644683700 336103131 163249278 966244629 796834963 56485970 436910031 784290488 668905370 275376761 587779604 382978459 142655778 140663360 123248782 632259377 755309409 257637779 239655785 272278287 712799946 576954038 23055915 293320841 975881369 986785012 500490211 983518226 428711884 689881890 794981671 157151762 410156307 535488768 687159339 53656146 24047353 436395095 917658059 68776861 548156132 396224395 728629425 850236372 941747978 39185331 420310882 735341783 104312365 678643640 33740125 960648559 473213568 276925115 575300166 409798757 351869048 362316389 488006411 167641909 126759774 616798456 161891174 861777096 903527978 929669941 177033491 711288803 537273882 512124469 328174409 741046401 949128007 871044171 97553964 171892985 230217528 739730853 299227567 992137347 361241179 381593474 96454881 984226808 154672234 216429452 865584562 272720102 480789909 278433755 159937533 603672089 917178538 833240134 723587843 996026572 254010975 806046956 876532749 371450977 737951959 160373237 994686386 890219803 78839950 676597190 619490693 142374244 260299165 332418863 152571776 616961336 289963675 457142536 726811773 339508956 628716677 484899056 313716080 764271326 104641813 833731387 123817006 527737119 610208914 140137650 475081579 833607350 370879349 460478720 96748666 899097503 493352483 873011817 264709999 150382444 873605751 355210580 694001406 306770472 417432977 953440886 919513677 565812065 559049841 982292394 829144435 364719067 593374624 884796335 943249374 911489317 88826174 931278898 778001078 361660894 41450468 307713366 107285366 72727756 808128174 622346738 726153539 70932317 594787743 561632453 916436665 324069177 395403941 56153039 5456303 944537652 71654116 843580858 724018561 768533287 259370509 831620382 585158150 412771355 439621808 239901535 232137628 170840185 743469156 699209214 30454027 784607183 686603170 125582707 749166493 956945070 83514710 599673114 279503491 743322642 923959221 203655078 463503582 721808793 583256883 7272292 773834553 595517071 855311939 807981218 102996305 49496788 532711168 370190331 206437495 147367577 693770409 691990692 944241749 676692334 46843552 387826420 645687680 394224502 641712389 431930411 414708913 957372815 627144706 286540891 389872269 758820393 986997995 807230151 479871553 460236301 824899189 666400351 929706939 713618335 741205154 568598227 675077844 304590598 703872990 532894448 129275171 181445744 272187166 575387925 457455925 844278248 423898937 144159300 162751735 414152509 322823513 283968401 714891232 268094752 53999754 336533189 633006015 204082587 365539453 486862348 935449887 88583097 289798156 880154471 968943890 605459406 852729182 904273914 210806503 153684270 897072254 774365802 310675387 888672048 442311899 320461813 433864380 828394535 163215007 916399125 510880187 700825650 52085832 331232649 969200145 594651463 421654608 567206236 833787594 588034013 307546050 509698852 287126987 520425213 604002814 170587885 772090604 676374955 328423038 352815402 736388432 603199578 105783321 298653453 73536777 704807539 89722608 597336080 282358259 724478643 521486615 748713662 299887113 726466000 300529838 872479274 502849265 961982418 41772617 467932888 831788408 272002407 568750253 502350419 118051749 85126895 977575650 339771347 288092322 314373675 232549597 593822967 867468022 328129720 748730224 676621776 493294708 489665435 878079408 895769143 463289635 123260491 26441679 10171665 721822563 471981953 263670809 261244133 323303691 424212924 929784351 983350929 621911642 932106939 763810988 363663479 533580823 688187951 590484836 334108049 766725609 411690886 946285077 58350384 709877000 128755578 28138733 766816770 356994216 973457464 773609433 770200288 33372801 916603213 879958445 310111894 672563417 374127295 237147554 57161773 436394012 57457784 29070504 952929227 70519617 215675638 550269449 226559730 226937365 268439905 178959380 310069500 946410532 493829909 652940415 403226481 43285598 51302048 296266067 291616653 182952915 474687504 958208824 836229823 306241530 976348138 608709909 129042190 519817291 306968319 907110766 42464884 5015471 174379845 325989345 719562037 174381541 822047630 781770045 75115851 389060161 734647218 836988692 420624247 528172583 398282806 950006565 986571800 442506032 366542679 350135172 100485493 736497513 187261968 183329504 626803190 640684854 734344682 59552846 614251098 725572493 756063254 774186112 502133862 132036637 634050368 883485526 2617305 90815781 23796916 745340665 334773517 914915567 267376125 645119434 412625921 567139857 519718900 719854729 189866410 221582798 879239631 301889367 439849383 833517318 491199272 90496008 87365165 587339073 247060346 885478592 793393779 82014902 487101667 170016494 257297451 103496733 86003943 106535805 831168201 802417751 814025915 625655661 408721567 223690513 176387046 430777675 453197583 576734525 286854538 698553971 508854281 358587548 419310504 359637572 550343447 391788957 645017092 162564045 252658957 41962780 435118102 620173782 541297864 460078421 156157273 282966286 442980699 448421956 325098206 94903708 757494941 386002058 367074658 617858810 198444905 931140914 218571089 498288675 392211733 245551639 524289347 444782194 514475940 214965631 444279593 908022244 704549050 930779367 410210403 52367957 131068238 747412715 145645308 439211065 674067668 825579997 637893234 590251303 698600207 312504805 197278143 25534929 425964778 880158527 194470039 594645385 308383484 298070470 232013884 114719179 30325315 554974320 481919887 701251385 479254211 621095107 387466409 16542252 97475016 890341986 468510989 435129914 573036474 72205387 280718717 711222540 962418669 472355483 341841719 385407020 117436436 552023939 211235877 326765693 908554241 238315288 509272884 907672298 996653719 804571338 979007359 332956313 503323441 290320206 635803242 755803005 356270609 772262293 781328859 6085293 503891591 851193661 564536731 447018952 657695759 96748736 591916169 620713476 325059287 320785168 247391704 929085341 175081427 803795602 773992026 167945169 171152970 773588105 479272945 253262011 329786261 287603460 302423301 983830195 237815620 114944761 19117151 744607315 466303361 745018014 226437296 209409685 732791989 882331307 997234295 89104363 627554953 716863016 569717025 340859 786600752 710882006 56309682 618550457 414639171 378927680 365999448 650063219 997188784 666395572 698674028 612234123 707682644 201563833 375605766 307891360 821513389 874476972 352022007 835516386 43715234 336503764 331247835 988451967 353526016 946911457 737416009 712251422 891427274 205915808 548838183 231418154 169524137 477110548 21340677 74838323 766841353 898071715 544933190 408223690 523754559 357040865 680886054 453344306 323432427 922926763 890227532 910957144 115335560 256477380 201294581 549069715 810126561 432668337 818301134 45918424 40363453 524575715 603979673 767555155 687765135 772832105 179827989 733952842 402726440 203411346 639877263 73208465 73473925 169047872 556352833 9914938 444101143 755786463 378941158 204566189 272821095 435439430 755881337 92611300 646210841 538374020 583165853 408442297 760085959 273131238 64371444 950026785 228133741 310416796 454694585 669672434 524841967 963777718 550872792 697986443 512410834 687387195 376957991 783389484 39613489 649937665 866512130 409155082 348299932 233989592 611127383 956674968 630999193 645730827 705367903 6972962 586014794 375987573 702546091 41192095 875959635 857271899 983468954 220763413 758193845 539107150 749768011 200628582 891120790 638376306 565259067 651882274 832779764 764767843 719912342 525799884 642413069 832552941 974238847 761918891 257059 516758716 512961187 852365884 557300845 122710794 202772471 140246525 603327248 989882224 228492726 130787455 291515925 630684315 972409280 639012402 502404373 387077558 121203500 435651805 811846476 517018388 84564383 476719053 736673160 630426755 301949586 63522246 845574398 229556972 109155865 566873359 494636389 562624728 72823420 241547304 861585112 92965601 933933717 209551483 707981960 529649525 865326177 382113578 158272494 295815992 456279615 48431691 578663312 52636047 963692750 812672358 590716085 549794980 445928808 933394128 918666613 245712262 684042926 138838373 923772453 30055022 68626556 593496779 79659592 593544452 841291960 215212370 827610319 408604050 131362400 119733265 561730863 147468427 322924629 631145501 295066038 315514951 156080518 302200117 347861863 600071275 838906737 246679621 875667738 16031484 591700721 305512513 412715313 874002808 145580437 875734833 148562594 918643248 963272349 193278268 891844558 669845523 958251029 492204595 539499019 263168646 988475446 643697719 696322094 610021076 708847539 144838677 893989055 760971494 764084354 910641233 741281044 308988592 66015935 99171183 810436175 363497548 221341127 849120125 673481894 462270063 966068391 763922120 732909008 585370420 614937059 975760206 152396523 557090063 279372323 782689972 842510138 384705581 954878852 449094676 289276927 270279610 364473304 253656197 544291795 553028591 228120076 671207041 643824460 35777625 154470196 39140726 192514411 27843279 763077387 533200320 157519645 583223756 493512864 549120101 844098859 484005603 450270067 560512037 23925235 301002700 137454621 914384595 308626616 850937569 417899799 500778071 27127526 611559764 999896409 609763694 877294967 240842293 273677394 159422392 317889219 889945615 974131753 391395300 210110492 908753733 721998116 693429082 303765388 731630878 523328875 182676070 921889825 887718529 137438435 793953818 517564861 58480825 829349036 899585126 33556033 545394935 782853143 696583180 825841027 826425383 559201174 230328083 458798260 343271044 806057551 806742035 607708465 371215346 541364237 653945802 474934666 818789722 780512275 774809340 563789942 604712453 69115724 924346688 625688532 297850965 35626036 428593256 297877428 772687899 137179097 761892829 176730722 659608281 499037113 125586848 182076897 578462003 586441832 965901104 104546874 263922863 985889648 68972894 596079059 14767378 584773508 603436692 443409962 52146445 437137932 925108769 679810973 884183977 68260744 901208831 407642786 648244765 497932188 31026046 371664643 561843578 857977553 77520949 451817620 82140958 877528827 55687816 864569874 121444121 736823105 528835700 138398183 566874392 34798558 776875560 301959248 783241235 500379164 298220796 698657535 444632141 447870243 508564786 866155700 5266000 361138852 877290356 195522219 497961751 36200007 579119214 717223955 231872483 518183035 776039201 691515019 361410178 495846644 684331886 229504582 515812932 709675448 844288378 241749378 531678203 494211564 843615481 823217480 329778594 870003010 350086274 411507955 708477206 306053116 691556343 59280872 111193591 893615630 308979581 765079651 128699281 399302235 233264820 432949791 372070530 73230405 980280012 812017240 371218745 587735972 447119966 577060997 76399285 715619538 371246541 853007644 302649770 4565593 365974355 102894431 118529437 567341072 656899532 386028813 77674996 177555431 696256773 873000240 235939113 955963657 696828122 157144754 448505469 852936359 960432621 236431604 389808783 966683794 817913312 959054356 939172395 568537567 37341555 705964992 599646890 697115615 259861943 662368215 234235404 647012240 511488838 252756194 940798726 567012274 61924671 746987695 959136626 952886444 806592936 272523399 900207906 754509445 50356937 200083879 300734216 989938072 122227830 422201873 401547222 738648427 173551808 220563898 69136905 567535858 646967033 750532405 533995586 751399124 881954026 702911500 156040600 316970462 347876736 436241990 582724709 126671107 80969622 549896151 892253113 417249254 965924434 28918808 538183537 213236571 827911043 124089773 491684027 84513083 95666649 36676768 401920770 541056968 525550233 821014549 732332176 806796482 135278725 42014782 440230661 187584391 695651898 112664384 632887698 256875288 84036874 287804919 336436863 182282655 47849066 699201470 149617264 396107744 209026153 53250800 415183354 413848358 500840749 818157509 822880532 277395976 777701317 382058874 499964374 45883455 309455827 64904927 132885968 892708786 883373487 40426818 456280475 558397667 618468996 50150650 695483175 959188575 744937136 141418746 823410480 108942825 490569012 885871875 433248224 275843583 752909222 388445305 361349988 811164143 54586950 512074351 815945291 463383350 653180244 733254188 459105590 786508711 980293728 225008900 676197061 679390916 133924727 964116196 350773719 911748920 534994592 451108408 792381281 112450862 852352906 468188341 591308909 732127036 77284503 275943631 374959939 89204485 338055982 937444702 880185085 148938895 153537968 82838573 263527896 532455956 47284185 384838544 465898163 876920898 161441948 348653069 976524714 267848896 431432748 747691094 905908554 66863423 202604230 878895039 571584726 872003574 741089056 890396987 794794330 812193454 665525170 687532451 999019866 93666322 716292195 435139188 611760715 175583798 874793381 649249177 718217828 278401472 130311146 959391828 769009859 914907498 150670402 274153982 148673784 118162228 290459995 801420293 746578333 497660923 584311584 915501226 346049557 973764547 800964847 626553767 94043853 944558337 297239007 968577477 848251416 967575215 362405526 16180228 326257345 109299792 535130234 11924547 908581377 331409106 962089516 331007064 79278612 562047996 948469759 962064513 960775210 689835105 349370979 432766277 18078661 501524876 352813383 108991442 770460289 785632453 122517547 633700566 244727393 369260620 119606663 613794976 34164042 921508676 837650633 308482011 596819520 953612118 876715765 219932524 123376381 620306660 680046723 585894312 575045409 554945396 837791213 377687744 480361665 33705478 287480148 461235311 508182442 467794283 477176259 141683778 686123593 672231437 944157741 397031085 366611505 807600903 570804743 862053580 355204764 291624710 557779956 207339629 912601794 745986541 329530809 928616937 932381905 396813750 768672146 186137734 726682820 279061467 805755582 327303620 543930218 184651463 205706051 439550335 989690064 168758761 283271576 725660970 283221691 153494341 527610382 743145636 411210471 359196486 86838615 200946626 458510546 368209600 339623845 861214990 914676626 419591389 894149766 40618958 605632766 586709205 712715193 846454469 588085871 776195364 231020521 354107400 756476451 164727115 271631572 952495435 365629284 615019590 842905187 300519817 365047995 386347069 48148793 46470955 23781751 94013274 731237556 18735472 45261592 202945555 995713051 93425672 992798565 212329230 419592939 659586176 247580023 613424661 807596178 405129802 730269539 938717965 940042571 914101562 217242687 524528606 947733782 774110045 598582268 99075253 552783915 466377177 624289289 662923561 270976087 896994314 370974913 43932690 884366593 151263193 658321298 875224916 864214918 991984324 286972984 386674458 73370496 833248617 135156508 936880391 258318128 811127563 494251949 505742379 191754403 887455601 678584370 449783199 778166686 641670103 713075214 48985708 727834350 689542048 570185243 520931244 744472720 469370621 884778419 995664203 639040437 910257647 943391843 466427572 559947367 902154184 667475660 637234199 475914443 920387270 551002325 311566411 754524597 684927514 998339623 462883933 47602019 146405164 546828774 791555141 409379968 289505715 929451179 21327540 154916200 535173148 823714886 197514714 130418820 992032169 772857462 892779559 892748192 698017575 746510517 606674298 949445387 249920157 600314428 223815261 280963665 327106720 867424377 176860915 749724472 770507646 838434709 80176035 529068738 650958365 842288421 892963195 115174953 797595262 919636136 485279162 225921456 767325789 785528712 932900444 982488 206122868 929733389 440365497 951609348 508517256 936131780 685714642 548736212 920441697 177133883 380032748 75234613 163909330 622253788 649365335 533399828 585269795 472274756 483443998 102322299 537090756 874587104 541982218 727828768 786691823 874429899 304472388 390177195 639096842 616340563 522540983 479422159 157522459 983198666 458742055 389982073 761084629 815603336 340131096 589781280 257823025 314640591 157242849 411795574 683465045 352333064 990253582 764966899 515216257 666510120 350897981 116228464 596512538 773886973 178238497 461348067 648045568 326519803 399186251 373890857 229161071 130083946 654061941 312315745 340580336 173241354 75695986 457606451 913651310 527912749 346487706 990019623 567183639 768897162 992861443 528893894 81474844 374328248 613151078 159006912 10754476 379297685 735854799 544579917 247601391 177809697 877337228 899914052 244632071 639117151 267210501 405033182 78782817 794256136 87534703 134549074 278168646 837784652 741319142 18923090 736917625 395084275 445120053 558793964 912675779 167926145 595162040 669814794 458545066 961108777 953006498 80917717 104186528 9235888 97295322 708261821 135417782 793356080 497211831 416276954 400499257 345934207 647336711 351635075 697905401 838538449 784069001 57801935 69863124 796189615 307620086 141696544 624388942 820800205 283719197 541464655 542305688 835923068 358869998 146007398 344395217 144686401 913909866 215097550 176076674 517525725 189500290 443030631 16263246 261600658 112502669 280016963 157955843 766088908 778777643 77872811 228940064 898189935 885725874 394367004 683059608 753002516 99681028 154610804 726772955 788840165 457339392 254354635 795322789 2466663 573561244 777133728 414098780 590298651 11978793 671456374 36058688 598626158 794307263 232318491 49397012 329104564 326800139 7413922 149953941 912081985 444078397 438865819 778661115 168080468 9838831 423565 611121318 785187606 98305982 343741740 746572926 284430616 824480611 531497190 242906273 492560422 243474655 618882634 575236139 4212480 376780227 364865367 843911953 974582124 159430075 207205005 57405896 328153041 666561716 114065339 197300779 500400385 136153664 400672234 693393677 404383398 863326587 421528460 773295925 702094649 148844586 451913150 575293948 260580816 297127997 493116664 90655316 945688973 271908467 471167246 440069203 139011701 205008061 823451493 788704507 917478870 776941396 340490172 244984601 22069588 756684407 805705965 340293904 325101180 641066230 547739904 556385682 784637730 551295038 476798322 194047334 292398367 162286735 856626747 483741801 923081249 890288628 716941854 48039804 12097036 564103214 43142192 37772584 577723566 148549488 775802240 173484777 141435395 501563911 902519508 958847456 917018003 577310399 792197266 948017700 648503370 202885654 367326582 232807035 92645317 432225110 938958703 367385375 284330187 942034692 182903210 794288615 948028516 981733700 596971728 435918664 954902440 28000440 829549670 54286042 290981000 251428287 665931981 352887021 607767437 69948915 397475305 562274725 542063559 748020821 527900070 554911469 64822894 268892342 179562252 765538827 545567406 797506237 43503104 361565191 810137181 689587104 392352158 763355012 75613482 229885038 841363045 134005108 68594154 841838950 168529941 502784092 766663764 782122657 933658913 385286321 34591054 918787250 60497785 634812637 482627424 968220591 419883454 214656257 963407472 533890013 447429348 166784316 710307493 133333360 350398400 691513421 184265569 220718232 689566069 795640358 455264367 530089599 569243323 837756012 804655261 306394957 353438817 560970274 492519241 582933066 506853743 236748658 68285885 727412288 687512669 693934360 443877771 823456275 599163785 551846646 886955740 473255615 262232269 315151669 673687305 429915092 557579962 591374014 541071008 281607689 936484551 507700042 359088757 730077167 68329944 438018679 342278894 224237089 6135476 440147044 822620389 853265660 988934369 566993416 812790561 706456667 793812644 197916979 645225072 143780895 575513696 210652687 567789556 708683519 405323339 876533112 173301873 986172916 652850844 877470095 25177666 863542414 231757725 766388606 4238628 988544978 499174501 60581921 356436709 701699397 427118927 745096451 573342040 480395636 76050024 963662512 262790735 682803619 230016157 487688896 886328436 534200068 741239430 879231481 185893675 503472054 838349494 602478059 492727204 866867765 812457894 588541846 731584628 922338503 361661740 274965371 601758233 390938524 599528369 124613786 920067968 294768332 96167082 589715632 839542418 746960822 393626580 174151989 140596232 69848748 286134338 497405997 174276306 456619799 89220550 466078093 261556354 377758668 444746772 49988222 713023197 677257118 952870414 145288082 188125327 327899050 90596039 842611364 395863957 931734903 736336024 117062471 825428551 243050365 201861081 888092763 332367549 290394585 89037589 71669710 368509935 883393031 324973187 393074046 555297152 64203592 701826747 168311288 448285828 771698617 1319020 516312402 737967854 690984279 201493115 629646545 651191593 621830098 890733951 214821796 409117740 556103596 30863864 298850987 932290299 84011052 292631909 542534544 728528442 213937902 342406699 987229249 841614962 930802605 652062198 151774751 293016706 330532988 136542505 46146789 163363437 472069589 777695983 82860052 101299853 963121737 145780905 605378234 591293082 323318059 126505547 374561317 53407913 750159714 194029191 661438113 291616669 318880735 401386492 887595047 694494072 839048090 758008530 77781957 627165555 46739500 520826598 820832032 64544390 365794837 455551721 13486698 106184035 95567445 831663732 836459877 292559878 814435116 403675478 735623412 58315781 367316447 422170827 254143015 644867140 873777665 496906038 166269036 823265726 426252807 397536075 876488144 949288364 467506746 827952050 357009848 787129820 510992557 153421958 818697468 240456522 478842092 349665682 574648885 180530156 392361179 74733126 536361129 25845305 806647214 412537787 547829784 37836369 496253055 174914399 471025506 921226461 776467466 498545221 228173010 103346116 424629970 886522234 307607762 185677892 117929825 495015153 620277230 842868461 662121749 988007670 97179866 126490778 925281909 698378270 591321612 77066174 280810802 580680601 20539400 771095023 540953270 337518769 332663622 606820585 979267725 323543710 966488671 310634482 480426339 332453610 685127594 648596619 579897858 617922458 102110623 912807393 274316919 819395805 175045923 580819050 322548929 616076980 269097532 552549584 239067218 677669143 754605807 424479060 849470966 964999970 457120898 12351828 776436901 153220237 104561550 186760029 806871726 147559383 619524366 591308805 709993683 18596219 177887880 101977044 906909033 128501061 404160254 806076730 137118526 842595300 764902439 660904533 787763489 392377226 500167658 741967669 273776509 850391446 87330635 372034417 336880902 674165559 595282216 693648133 747713340 379830079 888596010 35591576 569965963 482581064 106222280 382701053 683054928 910593726 27818721 73445233 763542300 985169319 472447454 689946133 687268439 912854689 836928843 213703071 297312235 659927121 553723430 191540562 272672295 759249671 712816586 28975921 416384244 420137393 305882457 301380992 909263771 773532871 128783056 917715342 138600889 23035499 482453423 839534440 758613975 154117689 78451586 659496731 869532222 655851708 42667101 674864033 95840050 692858008 475051918 921766306 453113077 311977292 286746242 437106700 937679172 611672153 581367457 497988309 34666709 435231027 741562578 894580419 186524219 803229347 749233599 509243767 556135854 316220749 7450079 735324876 832399041 847625793 510511271 307966713 789193260 924725354 445438072 423466903 849143887 321140453 852229835 613899398 533067620 141076799 692475251 911240599 360924132 791333303 828608100 120984672 234394591 916899912 941543064 876578385 329887605 628682025 699480100 934372880 201069375 773515196 84299850 689558756 209619850 880491364 998625693 295716556 975848071 295815033 30841286 81364593 482179348 768933602 658649886 885619510 121596817 694376500 373111183 863808705 274642083 868661894 516769837 455044090 289672857 718040574 435051501 376951496 295723230 283965805 15674226 962137089 844059320 422016866 858675737 858932087 965408643 602743248 733412128 347525525 812212349 378161994 62772433 840702572 960517596 199424957 305831482 457428680 47274678 64946549 591190387 257965504 51221313 136406741 191070683 342723478 971576185 715633460 598892671 376875419 783947271 458967267 14158365 473590448 438731473 604247036 422025682 162204430 784947528 82741656 235906395 946911504 395760135 288274625 45356524 761639736 356909223 533912401 154849516 684464412 894555450 46014318 910815150 680989329 985925330 843857169 319603322 763174040 372013231 547065573 717038711 37078261 700859402 493415421 537863581 271066632 541199482 561790429 221252923 578656645 228195460 395783628 451337244 753156820 36925546 348873783 469658141 229620391 595149474 627070348 454678671 94239249 264400250 312103078 715647314 400643881 57238163 75638904 794574423 91759392 374184692 544833412 328128011 712282606 880009701 900264290 684494140 888980819 427430416 391632126 638454415 617643518 149418060 112320009 837934742 88943865 475126975 261031914 839698637 667581768 239771944 118343034 300375407 327146586 480212547 995937363 870510875 248285686 435483477 758727950 792918300 59498291 733553596 712687008 407117685 418492147 158705013 657558604 202304983 20573594 286754539 764260990 992053922 164340378 59424900 250817688 416557103 714507200 861651421 607656004 304044930 254390613 246036688 843714300 906857748 56551286 897333450 207723864 83059223 179120890 132347107 43447239 987170704 598630412 509513859 976569865 35460020 892388738 363878326 661069844 651353635 241368734 148954861 757232657 7771868 927297764 373805564 673576422 349497839 755383188 982916759 792822259 872415677 630208207 730380712 472169808 895172202 523248302 771118843 928277832 756123889 978284039 449992974 841862641 152918296 357032627 510909720 546370565 844422855 69221729 931570916 237769024 116606112 856827202 260817815 49393621 791838069 613998341 674135240 578448593 393623980 24886260 713680213 136208103 209237556 590262617 66941150 537391933 339894664 30374844 903786307 516044382 807888392 21745446 804504308 291064464 971460857 245215027 932570060 75286783 402698432 673706126 230318570 428965627 1296816 247352572 632217691 268821045 655178335 910423734 933748101 550176009 464550462 253702702 100618026 512940204 825983148 378715657 369074429 895346768 178584130 227189400 451715616 165127079 556291235 897383784 629927450 208974306 238574997 2264201 532543649 498786413 804257668 899162188 253801067 178532514 159949133 834131585 762503460 953568238 280890342 860202429 692125487 778640914 542969900 291015036 17581174 342125965 353451466 157078698 234084766 512779690 832291217 827631377 19910368 496624466 562633015 823357938 170374744 479986129 534412568 348475356 783654551 127101799 245267998 12787092 718425573 353092488 676607203 822055593 725551600 345984723 409762305 818975185 31009369 690066537 4010 439322131 899835314 42651382 530988840 709522172 317427033 567675154 715542975 465092545 43917725 976128690 643370548 748393568 374733933 345001701 886539260 340604698 256180615 614689781 362189772 154885105 358369097 541408604 4281674 557746445 432110172 659076710 484731912 851652730 952341329 659510352 926766902 903652859 655009349 21152721 356000586 605795781 471312161 31033652 656109498 840773108 296505196 126943013 49351514 492528175 732141512 107314628 842034199 642992311 509805812 548771780 60820751 39947286 476015115 750777465 80494720 531732963 45408728 452873827 691909399 893691734 589110428 784448159 312297452 871650453 546829398 204224555 677393716 490935303 727315120 368846008 515591580 318488345 723497832 301898393 420608319 282711205 469682540 608116726 564899004 550018079 716728348 61550572 212327568 311725293 158019127 351360876 798408725 113526873 298940879 557345417 433290130 715043716 221084813 136011871 67736256 243710078 795379749 487626296 331596669 175462532 744277456 889781770 723732155 297725213 491732811 758235361 476541135 517932829 760154093 599106406 415201659 704780759 694555052 180251636 539971240 531571691 838380837 252839688 911973861 109123059 752517387 849337196 204263705 329851111 881839692 767900604 691480137 723058886 835521346 595144387 465252813 611145050 698237791 515869486 900387797 402399608 596019626 23322489 669791260 594119469 205597509 547082728 236568527 720231949 143696708 245253043 610665277 456609419 21818522 729947484 856234141 850554118 612251183 523801566 387248122 613138751 369957612 277835680 432810780 453721687 584245654 496174479 422920042 142966053 681175156 69158704 197606797 185809796 365821936 834461364 363340321 479578087 938171774 118732315 923528437 957683152 406615576 136506462 138060253 580769632 364719437 539366698 289858126 209995565 829926450 133563367 971642381 920799103 814342156 123313178 1192294 294082091 887159393 555193253 628483069 701633593 472372527 286697978 919839721 37195926 625377619 624781699 541122503 542755778 806198989 57688303 863132411 554556644 890491308 327205148 454983277 810408674 289701308 354623994 696670206 562041046 195744401 519784854 494251157 941972073 441296366 593237897 446774999 650819517 398060596 425993550 577659205 135688982 995415208 470463444 163096 723114406 324065669 510151161 424847267 604549160 426873491 797420358 727561139 8278620 45394359 553428587 175809238 717760757 563243981 969801803 249192641 846846080 980464668 776760464 336556843 329987261 961490454 492849042 909299054 638493639 721213217 949694717 649369387 993935602 931242292 791840275 832115603 604939506 681863183 995840949 484016737 836326815 555114691 515923999 355981573 530492531 214195268 320378954 276797406 334530525 4663603 796292497 741726382 200281906 213682780 496149057 109144434 661477203 355748924 866470845 360372531 686494149 739759696 225926495 218413918 366503308 319266573 237277222 561467234 460523778 458590082 34822749 618028916 451919093 701817822 108607830 634840157 606112594 689681681 815386051 38892859 864091794 631984355 935930126 726538266 974277237 284419290 45637299 554237742 902543789 5969132 541479936 37818249 811175549 634190752 426464745 671965340 112847461 693461723 512086271 487283243 524359942 597956916 435703700 143911637 121331389 327005911 35731376 502279893 36540054 126681548 112541679 341751587 28143107 120426651 688023629 884643795 937238604 831955861 211251192 200796199 878379669 893716663 524268796 540506781 75700464 100690599 873476313 799899559 472182204 610326228 959574660 557309521 7153002 840017873 338235193 65175137 204674093 797783701 17091253 140828359 337867597 181079040 496701853 537542101 523526636 877737528 779612475 280611998 320897406 787092675 48957103 415703733 637470148 397773531 908618616 100637896 587262627 844299650 236790447 548631560 265645638 363484482 358821111 171002691 870966749 513243509 828225723 181049580 83451394 202887689 144538925 532818812 689857208 862656955 672856351 822744687 880014384 623810483 461338866 327110019 565817673 253393631 874074382 570931296 284524242 622564129 744338433 933618985 243315100 933428216 71891153 325377993 450393996 161213012 18593362 970459404 735673746 843421393 247954026 39824868 898491554 722761534 24887781 175427558 387289719 422346034 411897786 577706757 989333902 369382095 396677709 511030766 688839402 157759235 13802488 463279466 538667003 548532623 416016771 77673372 247655686 666257065 493025636 251886671 886064686 384599120 875941497 26966391 670443604 756144541 352665371 536785203 774466651 301837936 773610816 14655476 890830816 273652606 906330747 823802635 306525290 665369343 542926699 481295063 577511513 177122290 200608805 137335731 946798391 270992460 697213725 739159935 762896813 546645443 464540986 23439101 866133669 479877963 865903353 99845272 68616872 393653592 843536726 126288113 850202516 216652262 825390101 928710718 388975434 728599548 582497031 799687872 554662729 626058522 750454935 111771179 982460795 813520817 60850245 486407379 789569171 141180151 417831224 637511394 375179992 149803797 593317417 832565786 206010114 244917494 869367802 663285064 52732290 794743101 103354891 646349789 813834069 507348033 690673755 213333644 731438788 936905738 380304988 90205308 713077991 474421956 306656659 685692659 781989878 128251163 135251783 328016726 927365644 852754059 860316047 336925932 1017639 255046759 387304123 771960076 274715058 216900380 777136008 468878977 180725621 901842788 278015408 974261799 65862986 761911379 261627289 2342466 192798760 149433639 929980641 622127071 806973201 567725628 939277918 526311114 265935838 605350743 210450259 76991672 569798478 374860536 636405442 901906568 934317115 444401945 621630055 556866605 246932740 630787182 462803800 271059103 381886707 571816356 107455786 549776723 348265445 955729581 564481608 942636393 483219866 709715663 159240722 251892001 217979351 311301802 942137403 423812963 190226908 328800163 528655328 61369068 968147009 471580448 760810683 510220424 749433156 9600833 729263121 633510331 955254450 115926042 913967797 114512007 439755605 144768287 185594217 182787787 221032754 379955735 927840662 175454323 991429890 231500370 985745191 172507608 296785772 88013730 51919713 301547844 590022842 142300299 880706146 598595235 723565708 391135621 542119612 94376621 264047447 296860831 11004913 48704479 655937172 760635899 711277807 662927774 212462935 261109390 771935137 580863717 399628053 712899802 890657246 269186237 756857635 921032044 97023277 945035159 556010995 648443232 163004235 265979390 565879419 738771652 571317820 903643009 293285822 698260410 601282898 626371898 126681911 569401978 815736424 268409366 802472189 270450341 669783780 470029303 134533610 916407819 660206384 76832046 375259772 403482309 542837631 9044416 418579614 504874437 736036421 604546223 40412968 717435242 164203311 953167916 432045719 552320035 601035221 824096580 21541710 613137531 771759770 840771607 203754980 881229633 74874407 181262489 696262528 995699669 165624924 850760515 68114241 140895238 60548388 874297473 558359597 146014373 517037657 850534772 519440247 161323309 589137041 598925392 706585815 796936394 407574335 491532426 404687270 236575401 446119182 505850414 877699668 872343520 780287343 282123984 756006266 230761338 251873035 467817557 50402531 296482842 21720137 807583011 669637962 853938922 990248678 18733877 745810928 683357136 346467560 561017063 67286732 46285 476138973 357206214 640883820 34977415 458448972 164220177 810730651 146305872 190141329 841132780 887348098 920640313 683028387 546533130 976743570 935672607 305854859 748507567 783123488 311360734 330879170 797511170 522944801 835877278 287196598 512184957 103276674 193392948 122900652 71040515 366197381 639758012 14996214 182683864 936497529 898317266 524767886 540899258 380066938 247166719 940896704 63366950 733710356 613622357 311691087 405856759 594031313 253824275 555274880 426971351 409288102 836109174 5784635 667530898 861379092 82347270 557025123 691932767 112274801 940815044 230551410 956765182 333112066 228493331 324073077 591241389 248751122 565809572 973039 804677952 58999002 632370589 569730927 383020517 549314018 706029674 710669049 810814551 603276091 224396202 188103925 962577031 540566426 39108737 761399767 790607110 17920851 328672114 573155100 333975042 683044868 592841537 67412289 890132518 314726708 928207054 178383220 338108674 572410400 647555651 825240499 718960709 838297849 734343672 161999560 151489640 688620410 815339742 631435484 433147728 230760487 669702229 239749389 284882894 595672375 294273958 96967022 718864065 285927084 181579211 666087515 124892823 70891443 721978602 976800332 823948842 734964279 323015835 598743509 865103334 542483733 793744176 634856606 987225732 789838897 696354536 126568804 460824137 512269218 190282980 63358985 733066506 728200771 818043964 586467762 824012704 656043737 472507735 943653407 189314738 449043556 674099820 319517083 654587693 380210038 142786578 906201328 675211823 576196484 316922931 981013121 921025665 955014659 159866147 598154922 461720497 363791432 837034168 902708611 83480150 446635136 438305466 716617813 313741833 472385128 816006876 90043937 586036213 907237346 432349502 74653594 355239127 507116481 708072629 627965265 73320932 956370198 795158807 169754161 772518207 292821696 409971142 465478132 511556085 856406956 993559113 11246459 160331170 771008066 179477465 566556516 704846807 876884815 179698422 147341304 774999949 852589038 723838448 799388026 231565700 780150835 364859454 949572235 138608856 472913508 943929183 381653304 687541098 633466554 241492481 105459809 143379195 676813163 82844402 339022721 260972294 421409087 503345828 217673863 21894300 877318827 552615303 108424166 560863939 10248614 210574963 964814860 9784684 433274336 455343626 607653660 518002587 952307429 942191368 478704994 26681052 628991256 573385712 815628853 999540117 939844322 119870135 753183883 331833229 102456103 528012125 320595056 27311272 249866868 746607739 31072786 956259651 853922739 505075904 74260790 657168155 136298279 324426087 919453989 380962915 461600080 483163626 849885266 341955400 899709700 336738925 90633857 54595923 295001810 554992209 791083058 19469457 195308732 853315247 426630326 266652682 991906181 731895187 411982851 37278125 430245982 492498549 409699086 718104223 875599418 135854367 535029210 884716057 817591459 484247463 919927031 841617170 366923873 160640456 358177104 402795224 93275763 157884781 411064656 540845338 965584371 307478284 331884111 481806908 320054650 568438257 435677088 435066461 886280477 701900168 521925826 460760871 441981022 563201332 27137380 222216283 260486887 960102227 563931539 306125776 261184029 404078440 53817470 436905663 107030241 858816833 355324966 982510562 650877153 910423355 973704114 434577158 876466487 638840924 795517616 476540702 25164591 184101854 107270097 90175044 692501750 353731237 525205279 871839247 751868280 561666317 284215319 178139041 498442985 570019417 271469224 389726843 272930301 604685956 709259785 577274092 202859709 77892286 136555534 139019615 76344471 986147539 883501370 427137453 849597767 118796278 841039674 77821730 529041069 338248773 51805103 512909225 268983664 799276618 142828220 181646037 168994955 154206527 942686974 526195774 794081043 149204818 368601677 697118079 203024706 139466138 927017778 684379074 608540162 940587188 916754642 400623120 712245447 129756258 189109544 980834153 267679353 560724436 309782905 631767595 440894833 820802272 186041034 694434998 175445104 440274199 70115957 514562555 199325988 556077343 374316173 445360413 742259189 709786100 624082857 465510939 403535447 227163468 711198368 263732407 225824343 853653069 338977702 145135992 548021813 262073486 492688337 695173993 783071358 21056000 227868242 800598743 864297709 587217181 815721617 257063741 400009597 384340111 873840304 585680577 635515246 453477873 550521281 920879289 587098187 952735137 514487300 283234839 647451295 59598862 434715485 207895184 453681726 83475641 228069451 325329908 511960164 682812351 303903015 855656187 356361326 586971603 103848422 553735397 573450081 511131047 979081292 655730047 270122598 240083364 885828604 510241938 20064943 731533479 435040234 451942325 860888632 621497243 302134670 942375387 169347677 22115832 658850290 565525764 949646739 481093311 628303451 961580886 90307538 321636698 749090865 976228292 5935055 993921971 541863034 668933036 849123690 660081354 429756835 685132747 219609018 896554319 876943045 892837788 154618077 706141178 398086575 904172054 460505557 723626766 31467828 713487606 525097406 962747633 603092411 251919655 415718082 497482469 35105098 588400888 110305502 890005970 392271011 535504024 424011334 980750468 913395521 813480997 372480120 623733580 724461511 633366263 615364440 123680239 38461667 697264872 460148568 813343020 672545598 371531988 309867224 622700598 736023940 475417398 934872841 767889109 270448571 14817030 587684069 50799154 13995928 472952702 633009971 634107213 511233567 73488962 380775418 715905289 904027487 638441731 940976149 530035717 339011505 520289999 532238811 686212435 89496014 528582607 532232834 667841662 879720158 399412876 200583241 651347583 48146556 332510106 392383053 954606019 199693852 885483460 286842907 445143501 925785966 872431722 874921217 729810471 332508153 879831123 901560410 880098148 840228556 116966413 980186672 360333830 526867880 859452642 521909263 378286088 944271134 510468188 881734227 990416058 956586409 964581115 347705979 453252236 439429947 516622031 794542660 176226553 627496342 755896355 52739577 296845787 886608177 718419801 529617812 110138257 400995154 942114308 757986216 93628689 102544318 976914632 481088435 456402801 565531086 719466077 293087827 308030488 783152189 276703839 937958024 575756478 631082459 783983351 654466147 929495443 924695882 994554479 518187622 501608165 127814381 462507570 842682252 752174656 944039601 776925540 232600625 216076052 206285923 469310312 532320632 758548491 299117631 575893682 849753702 2156176 458446268 797456762 234352956 865381110 633176 351344906 102935822 739312147 357399039 416539793 882084896 602139859 370371386 183171535 135020847 737811671 943677742 30214719 685772761 625264710 416273719 541176686 704461451 48397171 906437151 356820266 176939904 170649605 555511242 620737116 741358430 412697184 979259630 409236954 209076285 145519580 457979870 1865112 137514528 972119801 571477332 251944493 515411992 710113212 679903700 214553332 517514665 177379590 227249910 653655349 442836672 87628856 171474835 883233419 211150146 681638270 320582791 295265028 851425244 563316271 485101653 698746206 15071278 489963124 954585298 460547305 125912044 163978708 885432516 558525012 556884003 778776640 622665258 992790734 679999856 640446793 402291011 665692169 364541747 425226416 34389061 520938508 960433843 692619476 951070343 57836282 461398936 338690587 507153235 264005032 336223476 963479717 187714566 68287056 83567597 137890856 939408913 420578185 20908802 184535560 512296191 612572622 680673321 747398521 908838345 391051683 707253333 842646121 389508125 756876672 47098373 564792921 54714432 659854153 764348800 737950103 942140281 631660935 794850502 802527356 448389535 588293819 339356693 710812700 187411223 407409453 542547074 943457264 428507962 234459449 684585765 554066562 829454344 704827828 88684523 445441995 248274892 593816843 107457359 127613831 229397841 917126887 198197611 842956541 59568763 457366548 58439622 568618071 131297193 360625294 485914582 880231264 285904711 258206145 873865684 412975420 45854715 292800012 374445466 16153706 505865042 279009676 797710738 540777835 933863271 78414419 929934580 780171836 850506761 511920455 668748906 461099127 348461929 146658595 261132072 385723384 857154736 791248891 569424543 191229812 300767266 998068144 693282605 310968679 871276637 48732304 424109799 405989387 992066503 733549744 555435649 855494916 892624323 299729403 487672037 676921901 341152319 236410998 162317168 884889624 374044637 122698739 541258118 777904465 805827348 759617825 105123868 796304424 632221814 881795820 782160595 809936702 633899386 17336330 697718214 390016382 799352454 251354234 879458689 379362222 73140195 708547381 621353657 568841301 140078107 778024339 216737474 548668145 49709546 194716623 40910287 881093177 48314078 954607334 391720355 170245717 73066051 582875489 820439125 75068013 905109087 350704769 300946402 232551416 324786280 918754144 391848999 544707430 444743191 712766438 961540878 437265399 256820782 457608477 134103187 425762882 22390475 26699719 41505619 975184648 839182948 469733617 312348029 349166423 484561573 849629845 496055006 448735961 411005191 40104302 150753834 39686382 682378832 708799184 507289840 57678890 173867933 163607002 751115679 633908850 794385064 37282216 224746824 239656569 90289526 779109268 816885339 961773465 514084562 270722531 263949461 908532571 196743337 272740673 53814110 559536142 316425156 660179083 255591186 943105387 166885506 518249867 444204604 72353543 572834452 665408891 58395731 511441141 631017811 269650873 896808418 564253516 323016864 625827431 241515277 655554511 105836591 805504476 371875454 872733635 677726809 615360527 115597947 754025748 783014523 810887406 677183509 967830926 387799073 716558313 174769802 460491665 403813289 666392659 491159723 968161192 141530326 279805117 288155386 152057203 6720379 426211079 7647854 901705392 693241434 831409844 576649056 545132873 734339694 450039158 309153985 139167094 600870991 323507631 717707424 205024412 101770780 880017569 723881307 703229008 551320865 678189791 166734382 772912790 403975094 840883884 43209371 95315005 247274089 720250037 914729189 44516750 917547541 174012407 797551216 517853363 22690593 228853347 783231426 641444329 260498005 813056885 434148027 775180224 623190636 363891191 448738345 251171107 40615293 294430117 923988186 101141882 32420988 818346837 232261416 669874282 382669761 139627692 939763011 107928026 480381473 730531744 218577600 184030429 787396900 723764265 608982253 383423102 807604015 195890610 192828753 502019763 336705558 216300540 494915004 336775084 528166095 987084141 253592667 388310930 730872355 54824956 44630113 380371380 757817727 619501749 511460105 233534800 897987661 544076476 430090446 399035579 25314462 396652918 647367632 424008030 75541362 274915337 127572345 325336931 993533217 18914698 679337115 201564247 660075707 260008984 335281461 623335277 541842468 979278858 384091913 386004576 445602698 763808724 228589111 259641536 497545404 567045497 34401119 793216624 722847627 109657063 709673258 17484483 805843013 109114893 62563854 501778179 538407552 733538448 281700097 184892059 167927339 555828715 254563275 304251289 386313548 397055592 317457479 131855486 356081602 836439534 110701350 621392729 959411954 862678288 597338043 157231587 6085503 848723355 874178199 201392207 202992338 223663032 161602108 630953800 500157449 40951146 1808830 225840472 834281385 93160717 86622792 908626677 231294505 243296696 334977671 234569496 339689573 437927263 721737548 365544716 140119785 475204893 896053769 12916618 155031137 548110639 677191202 717703455 981790190 165975854 739135268 864673822 763043481 532750447 326165656 827052151 594283262 454202884 17084189 212145927 661852929 409323801 593269809 388161764 616277622 649851897 826943966 91135803 494175275 62994306 939211799 805871121 534337674 794588020 281660320 295648221 31834604 19208253 775622330 260372809 126101991 554878686 780592140 692512588 616668249 840498882 474318176 627419707 480458527 727935432 92658075 163611767 222780708 132593651 642847221 47872829 873098205 475227663 237202698 347852051 84776948 22408217 149034858 186079394 249758561 150321630 32423755 579455415 254010766 190575205 310158028 183925698 645882914 918565520 803551169 909966699 457092783 146739561 333031407 125948754 392749265 114003165 613149588 369623393 9750227 415897480 304477142 424408611 551112842 341610467 848822271 130078004 75067809 202346326 939149904 632759955 262921308 187882293 479313024 922501556 108938691 393973909 786519945 142145432 783925943 497731508 922376348 31800366 612807733 603123172 927024290 673488123 822986010 103408149 414975072 744155249 913492551 418159629 291665212 56144104 445838369 939398093 822879323 923703908 614756728 512651299 331189896 911311368 894697599 490247342 7400134 988778097 851089582 118341471 249459928 677706869 983829775 875980381 40735915 858797939 146951802 711284543 270738792 142502033 131824675 601732738 301553951 526120228 583747309 240066436 127868262 341761145 704206472 936443067 440137261 754848848 669269414 581821005 400341057 27938062 542245144 89492846 169859979 551252326 819554882 379519302 722311995 587766661 224357284 622694460 232447249 526074430 229042410 291785354 150179566 312200895 552973546 21355328 191062002 726216106 442445617 318845012 155264365 791389150 577900674 458648921 63824021 365634731 821169561 845878978 342396865 186672155 100151329 505001890 498605236 622488917 899889861 171355580 522162880 631085727 618267853 307976340 738552700 625696901 32489850 417872727 818737753 357741513 53237365 165951423 103340854 221279215 98405297 563579993 959777023 236176593 531552599 590569799 1292870 476930776 915154290 808630644 959772217 438704360 970880473 224854103 392274151 768683287 320835086 974986341 666110371 415070281 318304581 284038945 558514122 405107728 100412833 710836503 284236224 269864334 911832555 811296466 20561376 633374493 503542727 429357521 178115217 264169954 850084467 274828061 524183492 601869877 962150843 395888119 518746941 858487018 290427210 948246826 125826083 808479506 12369616 124761836 472579325 273097578 586606643 976742007 159960128 759710331 337809344 272390240 380651464 330406057 351832816 291069616 595570104 702474581 523551132 249256758 501097507 958482258 267684753 213243870 802517704 217720975 977960607 249326392 767566682 860306649 95662901 524781592 977530430 5303685 670739700 121547185 83963382 40241889 969067537 546971478 617426009 340394437 24903060 799453848 224536366 299128882 519282380 7452334 943600684 957710613 50588571 740516450 452828982 86372544 90533915 987046341 413765211 139311427 136365270 188241554 827699628 741125001 309193684 487346470 766322786 800664426 113263131 669754138 960898599 351932076 560823342 744513340 236987289 600341564 802164633 511507506 577352274 364546013 242746826 468055142 661184221 611997433 632939926 468815740 961648674 726678831 718533809 764214054 664025606 673468176 311829165 278456546 776273101 474558726 87059164 68800701 117126202 829511199 180717754 647626131 606929053 856456507 191286754 118259995 166440 378536120 582857906 364288185 283869631 413056176 638824172 754030728 479960889 384335377 863279890 555341128 23550434 744962174 567014031 403575459 474131038 93798860 675120206 299084507 569184751 260345141 958619694 108295541 251585378 273711740 673245536 419863594 793390870 872212061 524749046 176634510 280569312 638419731 351585178 535897826 454706102 630839820 108521099 304161415 318753334 836745498 69708419 279471182 451250482 236738606 238437125 435435017 567582100 683838963 865705258 431188289 198372639 768939380 380744871 532270113 131855430 343285535 486811200 714942924 468223555 644924970 479084072 730735022 987973667 132774916 23348008 775662602 349679575 300866413 654999185 326386632 194505616 769614697 716907125 123562604 127722206 335780744 450073450 867099983 668612212 355082405 116613475 997425397 918387960 328086417 353904834 588628242 878460506 744417530 728847510 234880317 174206694 363383816 926245036 879259790 315211829 694319035 489976777 14210757 718842265 31171878 928661014 654587437 315497347 939179945 875097095 16116176 146087770 319192630 881823316 6920243 801820355 697973977 327933969 417080104 288366733 708674342 751575071 512805060 323575768 498473811 746039042 890622562 658330889 884496237 597800950 366153017 282286151 827015238 643329232 177746367 518494822 942199157 27351030 901409309 911921353 235445735 488523886 790597641 877866490 350245605 16866754 944170189 783541245 275756018 954007302 548518033 337683527 885693244 604555704 441907847 1903915 182168369 364500057 252176959 369984879 877029330 910279760 840495894 336003042 549284603 769079435 122943219 883375399 766806794 893505832 938117035 434673120 744170747 963936818 483200307 973533502 668472081 824871094 681110159 892892966 794419502 84527421 510164659 430847874 17169352 385237050 831794009 199276546 26072017 325735236 459672240 258250886 925628080 638900310 391433437 312130048 606421691 298441990 228857798 171202494 354011814 246889170 329741474 595988705 497038118 633474696 180208279 423065812 681222793 698266849 747838020 165320416 811407890 553272191 569821594 667132080 229392066 635687632 171517032 525500061 236808541 122700677 553696750 67776110 749382607 328869268 925272337 421923828 114734254 202239548 226206236 245891320 664957349 1538172 129815634 164707584 218598085 46155508 559562627 492506985 476270939 708871178 964199438 801685109 353354357 645919011 463783096 267076357 971346949 390304172 370694712 495108926 499869745 293911417 801551970 586806068 82088442 493568205 743446872 794480513 970308923 901932910 694235153 382266532 403690495 877785361 312629034 537767710 85307443 263326579 201691279 877909293 175445861 927430181 72853399 903087081 133379231 445542539 262932299 538708061 435797186 156280352 819789650 937894890 594323963 35600083 502074849 823756179 35335887 203218402 763435894 313465173 189647168 714293493 804768458 66076596 102234867 774065982 641370575 52895075 188187253 828589749 709785033 501927147 713791942 918034712 604350374 558371205 626562606 218448009 731805114 235330546 101398342 468078703 73580082 992052865 774683074 364160305 272296918 811889620 589756633 575332576 373764870 938466496 311284187 750452686 492451048 18093780 74841139 97418031 772789369 169510643 722055817 488487128 354101169 821918021 344768783 865562068 657014338 524614511 746833111 613784092 871721705 229415274 391309353 79890362 790831716 69402053 929306132 105978637 399755232 311208718 195460851 364054829 400675186 864424163 397360176 931910245 242597669 156127875 324749898 716427723 995300500 566442604 653084005 564122852 570413856 530221106 354284870 88514861 188848858 162535649 864869991 340932122 785183628 410748168 546054867 20382299 91560006 36931359 711636604 93713941 722300646 65656866 245558113 932672817 897710658 219152356 434736961 960607524 417243969 73094682 184122765 829704852 910251440 590329607 387574844 399765896 995024434 511134109 302682366 993391698 363309174 147647501 350848425 450591071 334521239 989920746 742040703 644202584 824668648 990474110 170903331 113001113 414757178 152203911 822228529 284611169 436741915 631301156 195187955 311214191 246217269 629353324 276205714 50576916 903801127 222766042 760781293 442234851 443280101 472802979 331896516 455436632 160833864 532954293 1701414 417755440 532601867 903418786 959939388 806300910 951760440 422942444 692963614 822157979 804132494 784504015 953692740 537190041 40300920 566941184 956381840 479273823 831758179 550338684 762557366 510074329 774702621 276105586 760178907 339464348 513224832 974377609 813973083 972635742 160701417 74490387 837162374 840478996 206486663 844739513 792417179 657876460 204331821 911518286 230750070 938033557 543018001 358040585 287661362 933222941 836375536 387170098 136365509 419387601 354234935 543072452 989281925 901653904 107110562 317557139 391431777 663988765 268440312 401933746 24942195 658854926 121348031 833595910 892349132 328753184 542073438 236734165 967662570 879845548 860635286 397036989 865105566 697336350 971477139 595507836 23323019 812266412 989352742 50977284 790165755 120920977 13474947 452022250 937812882 179378643 866787905 502054342 394898853 322948236 562645812 719544501 274584696 787536861 734094492 692916721 627735906 248048441 58243308 301877889 398158574 44677497 697664195 814776326 632510466 505236998 110957314 299178027 125830721 675805714 71128364 959105172 885471118 82541479 524587868 748038965 824153630 435665259 878080801 319268686 241230637 435997494 888129691 201785805 205067425 192813166 869384383 318346156 470856848 897468159 570146485 54574668 523630843 301263903 276232029 247715211 120422950 601279880 431648733 207074503 518629276 10680532 923815728 153853907 584767563 361933660 600031097 803468922 268421041 846918429 28163812 646598729 388596175 413849308 317993815 651555830 176102127 195256802 168309349 791070713 898187258 443282380 39780633 965474532 802415679 258110863 176442493 639440664 153055374 853539037 774623968 246300867 646411397 22009608 807993164 437026055 209982276 511873643 122355555 216040949 915345425 804551846 442861528 728953930 991837577 565349092 585075895 983203605 5773857 566150365 925675252 413870911 723858817 151171666 952820080 968429979 453287289 451004175 980017413 334551418 959495229 769953850 971187460 802038149 613013508 91648154 686696924 87335528 625685123 88578300 402854401 33417485 200722422 561672378 212056137 183899727 549947021 668446023 249362668 848029423 245515828 526671642 933346987 829211136 903185329 366857297 465374224 791279177 178201861 833581748 401656050 235705299 382201270 990239066 624290107 724166362 941042652 49699551 625451702 164453178 330756630 836180424 865088758 611060428 912650819 440791591 807920471 539608440 404452 285353090 521585357 575422431 801581032 23554441 374436779 964449158 359190361 999962019 53846608 226990335 419448220 357253703 786444061 328402094 478229362 247840743 509796502 109575045 273548887 688938080 147426790 334282119 420951921 195498469 246711426 532429968 435492182 374116740 724429043 106711970 31522733 386137859 95489578 712476592 469512250 580985339 347332784 463137741 170126874 943645954 759021154 742396410 747328071 944466646 972409586 802606084 684757708 154052457 953547632 206870254 977993412 66079176 147919475 396754459 177514470 493937998 48999206 989760679 265631365 904019166 649926632 212540285 223624569 398540178 754718145 514681046 454153215 572751515 396800351 237033182 160390228 288545724 818756622 615746014 889230533 337679130 314123524 719721131 639232545 298353038 31565502 210421032 440252537 537649887 530960201 106004881 481860916 934715162 293058408 222756832 564619500 461616752 795574936 715660204 843988012 604357550 904719006 291293934 117456283 935882352 961547804 456317437 715941687 681306241 348727509 145057275 110909786 262295772 988851637 163384324 393452284 613113179 847860933 79047248 897599116 422310072 369935396 408154346 471243563 182403784 198657049 181567175 278926016 328269706 583106676 517643183 671313282 613105379 232387590 707818682 613445235 810695525 426580327 401635569 344089218 412253819 329785134 556988446 224371546 799044719 827290433 574602629 424031373 155341071 283809669 142162334 210404866 77215872 490580520 2930880 304287649 750882129 96572906 155212035 990339967 50595798 780146078 703186088 759105620 406826366 533546943 775223820 334895980 656781250 244785685 428178424 535858091 984548186 142563176 95913201 75937533 48752530 561399889 331091918 209693894 963301846 992781000 13309422 802479983 60147614 35591608 901058860 712116309 889351709 558864759 829244894 392012428 686680510 45860128 925817090 782279833 649664105 270555180 330360891 360744651 923917586 886160034 136656130 190663803 785965266 203006168 11773817 784970817