2092 321916900 843357117 559826575 407157076 957960450 214727577 474760157 801805234 73475486 674090599 935423612 213407506 154285883 91021445 867746977 869166246 341320543 306518940 854944452 531169444 455857495 885521003 780529372 309274391 398867410 453522076 709080547 807611671 787360356 119405465 491817963 456899931 867648207 586079927 528420876 468766375 118800716 517251601 982884564 245116448 66078578 717795622 314043606 485284017 179863721 733468139 548784001 693669080 601487636 212891247 134642690 450157546 426549787 801351399 119171404 805815636 992596629 529021790 104666208 347835015 464040021 926942546 811155646 689043929 274216785 697546206 714860960 275417269 890934104 668989746 388844978 10340675 126251202 456512793 927951507 946461396 623727503 142821036 988186013 310972892 755490167 53440232 493012486 245601432 993034090 197551170 203465711 956688780 687146794 994992482 115795748 468362402 643506335 104630060 256802440 24326123 496348279 886080985 1170479 263886084 93322088 57489926 538382652 802090385 321418859 725777892 391362133 293000204 245559621 625795067 294701592 88902567 148520320 207673999 59877521 49139161 999012195 452261982 368929438 321025841 293508682 894612563 752047413 830719455 204950219 97114891 691789418 81888112 896909442 141092037 598349249 282491075 838643666 656374095 709462362 288751146 277321250 37364543 726046331 821208584 919798404 63190844 323651812 419664099 657702327 270093887 755607886 246260241 549541378 726462289 505558708 980291907 24381726 743699518 872253730 626831119 107938503 3448045 229302819 339852035 672052643 739705465 61991435 258666596 268426110 513151330 710008012 298261196 334335498 35262532 241649492 908318013 939592018 422727345 369655233 262367225 99564740 445284827 484340606 1005887 4389611 849653941 12537988 528488761 405078299 876372888 723403598 573629070 817185589 592010014 859013316 545733976 729116363 190318980 280891683 520180073 222870670 356550217 491987517 50910992 609859529 189186555 735744238 101233248 986101599 219208530 452549306 688393180 64105983 753203305 586474953 940713166 751456239 304493826 612180039 181234670 950290665 394465247 524053922 645902462 586182807 703380709 47544870 998522701 872599461 322505342 772035912 450184290 121287893 103329208 106580589 801797125 791714707 665522878 966261172 740670663 972315540 464045078 208750674 918416225 845564395 791295807 832446293 768945231 101756056 568118381 328333176 359018403 101223165 581635224 592194959 907301410 150689349 915403226 833185442 195519706 294079275 290927583 799850849 401769499 236796551 37523722 39691478 957432163 57958482 783262906 567957586 574681639 798712809 588179892 617216073 933840254 282897741 659882501 853416231 579998054 907445750 838402648 858851618 478583572 577377653 19512696 487788456 691615600 881079516 266703531 259508605 361888216 367498113 37861595 530707774 809075367 260313955 567650810 648658520 909789295 934405931 740147205 549247670 533538980 885054689 226458395 389289000 999365643 913324579 880363802 216737099 538572148 807361527 691555212 518438511 284881633 955200365 756835123 877987395 56675502 592099145 176376345 604665123 910659264 493575010 779374696 897885708 486030239 792242902 41291484 855496533 319447826 96122138 122927037 344388892 754645483 865252778 876693510 610591615 925666689 197479119 282724634 272381058 890602967 274044932 888465089 439901469 632117327 449104304 592597780 567147216 848077197 661405031 266722202 987445515 195425951 382248301 18301354 396322942 514946301 491437718 305863377 328798729 786724553 907654853 250697940 859303189 116626822 884099874 749823158 181388794 5146285 118928853 356681495 517133496 917226760 167082269 977365579 867971199 403409573 364006814 758683433 703403082 745951602 229879170 190000021 212302259 858177533 285000903 933422350 184630167 352645623 86354544 29302915 358109155 410712467 833232954 692562547 774949794 668251340 342434866 448180006 200021877 561597702 688144029 297326283 63830259 691218305 142167053 20033311 835111865 476424300 912210385 366266397 356968430 422034175 1334079 843031781 133469552 955307089 643926823 10087604 551995926 47580381 694447917 683261964 884018093 101828226 289351713 296332194 240614403 948828473 624917122 269802310 173372307 582811800 48832696 224073451 22642299 551861700 899733921 84524416 197331175 512430458 28383422 821137920 15631185 155339371 601781390 709964609 466027672 797076662 652289383 231250480 923883914 182522311 734897755 893701321 424606161 645582655 509719507 76916481 127217633 399537436 564738095 999047241 674981295 19435892 390887943 476813608 81298621 845904346 32768612 888782873 369401360 79704073 948875196 842317103 956642425 3666151 159528672 38129933 145098850 921475950 703631544 406827200 99330520 224568394 214506269 866525260 627024 403182415 360926100 591804452 208626909 104178609 55329668 655294673 353227836 566522075 463538772 764825349 71783991 346297785 213129346 223089469 940023235 782972200 225511467 63127316 333547206 649876658 824906608 425508210 445374735 514546619 695736505 329439739 103073046 107335623 96361246 631026407 29189914 41183561 891383067 123550457 929600185 492973902 169303708 943337199 621818767 305567033 167742380 467426096 651778419 356677226 637444441 629579866 472982813 243745539 204046647 882506066 634839477 521530770 577488571 232493577 327934489 903583895 164948815 242846506 521753792 668577471 898846002 929922309 62552256 757324678 190631313 517974029 150911159 379758269 974714691 328020520 125074206 880645597 84989527 574844781 477454154 162796162 613125982 92463503 497490766 706638315 57428377 431155801 55036753 709699613 228285341 660961226 356623044 745323820 485695279 991377383 915348626 687227842 545730307 724181715 208639916 113826130 721323518 445280598 3902093 108385223 120778318 962487898 968204989 206184300 794836808 787456827 790185318 977598784 609857721 289903380 413402040 952543551 981527632 969209640 416809749 203287883 574347554 235061428 475808325 217107769 669569694 986116472 516182377 562298592 865941313 329434806 193385557 498282010 150774662 522619585 823972672 180412821 56783623 752183147 992148459 624650587 770667300 825379770 874399462 616553943 958905918 691825493 338746303 525245444 728906455 347991155 225999225 459519298 226782297 690089581 801707697 625771829 120570182 773352248 824096946 44844523 300273402 400558434 487842776 316449021 959451358 246888990 848838081 174358669 534054433 927769285 530889526 842200110 177773746 826470176 722847411 772273351 676588 682721070 42957172 936410693 707789443 675669574 26858474 698754081 345181725 547207880 171719742 971484617 431330283 192608590 385772299 672297641 648520433 106991448 655980892 413656254 277543599 713148511 418538572 741307684 242415860 276727806 711113994 763297371 459534536 355901030 987945615 591674945 345481226 413915120 551383843 853604671 566517540 874976556 605080617 435245317 658601557 885272893 183465276 775157388 277441503 713507523 582494934 513786356 999504710 444975041 965649075 431915876 704655463 737567325 432044267 588736022 479729345 542303718 450761683 954784829 931877911 70081867 932985074 164993844 142258024 847866602 660448406 170402797 773925033 66121059 976201426 486312753 165943804 286137507 414052973 848505310 313918601 69815498 789579008 995631326 625604790 739553496 842136844 175392198 366347505 403433746 502880725 553636365 705475219 145019323 656254364 20256248 959911721 108874325 832967105 160787386 100881484 905631349 929944193 789600790 492580581 526864546 970720069 218342758 718403002 75004924 99820410 174350178 302519176 555963744 48995692 497341771 775152874 54170025 612234003 611812716 443813420 225040833 936986488 971502503 866135654 303879476 919593750 13617172 107531611 692516180 385335741 543432571 620710166 915982929 743500148 746351508 385140409 622713739 27104404 234164898 419558670 418823836 648263559 310836940 42929909 777397543 34027758 674331542 721891621 571921022 204807265 462186316 657828659 741228866 179014835 951926293 933641818 499499292 618158757 627612435 715603958 193135429 278194957 533977521 309438676 785822006 238345150 211663140 551953517 755938591 21240293 1263787 221637397 611033383 982368254 477959309 456389931 863422887 435414220 271465685 354339782 683199717 974557536 576433312 461831372 578222097 577169480 372373515 377507194 738867908 308593756 733751473 701758611 606177069 466294235 125333570 978150771 247171469 274137300 944761162 523315102 94743804 189114339 409135577 620307320 211417905 171978309 474211261 441045918 374006606 735290893 848805128 536107435 514625562 792295958 829686603 422362700 65095253 313292163 834527214 99433790 944751263 917877939 263655129 372809213 159642510 858224743 262079316 603464387 454132657 291760857 961359107 528444135 18193988 869688312 860439052 142286888 461503961 951986226 394381074 432609976 604419879 467987048 24444859 572368081 850350861 898924003 631659683 567386158 930401320 283330175 527699467 292879560 248286000 855876157 916583850 106630543 566128935 663728233 204018839 46047182 217157849 92247663 668051110 890357228 355704020 517148450 326804803 496454850 406221334 725173551 945168935 952281529 734979665 66021284 268776610 128054812 26333068 636865635 310107302 260910164 558471925 922732210 203837434 220185673 333430344 598823303 342840988 576221323 69279021 935051349 68733303 11976964 232531961 822572181 284667406 645723040 701279122 878301789 141372197 664905430 430185340 182205960 720813692 510908559 692150536 599963318 189639023 814263695 567383089 991143943 764038695 739271044 938362098 445445475 830513672 325640655 846210467 787323971 826989678 385502329 199662422 680024380 471067925 344562668 30892915 941886273 981762071 632794302 283598009 245193986 758590674 779214135 214723209 783371371 973485553 850112760 260865713 335603662 565651522 793266650 737287981 10223436 656221837 788190997 797826530 979466159 409000586 122662779 565928092 22556161 284190500 62121405 39120545 949821475 580461231 270436019 740938235 427398530 4551930 147165393 959179126 98753840 586462680 190656704 694273193 712576327 660669009 273785744 211199563 345642086 997452638 915528739 702046198 20051096 133811154 475450500 286682542 87558816 118607884 620009453 380887003 701694244 443118200 319562518 938952236 249703337 14383717 182959119 587182059 187980967 151904787 117171890 909414066 596522114 836130368 585252859 233006914 558830059 350866373 565700653 262173631 721396517 744827080 81275863 301471548 912648667 403342731 837006834 746302214 227561348 470987168 974006782 396715256 791497779 270883897 621561137 632183121 231770510 871904730 329878009 827992231 937035807 853753230 301071941 964893025 403168921 830249251 580063258 276479522 541574848 908338889 595052584 892482023 585370930 373649580 421301061 80353268 698909142 857928463 151042816 95257329 419908578 401316526 172495595 241501596 321551997 434441911 666133804 720724270 845983885 18008580 128325724 582210353 634833751 581858132 560101661 996199381 566395478 784608166 138652745 715880903 783780028 959192409 586973819 415374633 693979699 684315605 687464861 204677080 156002417 823214730 10055992 574467496 931295247 397255990 37320780 365105578 475883593 184791884 393743253 338210664 122266045 547274878 680685523 692450034 84950764 907225152 177819104 344670036 335763566 28551695 968376534 770829441 208908344 123366573 522951103 957452762 760744627 422209515 449905963 640677550 536828164 184427117 396684143 622096572 854462954 295763631 372273178 284108633 210698359 489601441 749945025 713665537 653251324 261392774 830475874 436405096 591198632 86249640 696110282 925337298 58605464 126976240 526552139 765654107 960514891 274506165 334433447 949422721 934624595 223921505 40731637 554421148 919116342 881379135 717827603 19092315 119557430 696175921 615363193 384232261 308684047 792908039 375243399 160744289 89165294 543524136 744192010 38267331 598829837 464033829 399709144 878047063 184256395 865306779 202134170 561715801 608341734 899852130 62711212 652790945 322160053 395055641 1005416 855989575 319742501 53761088 633616308 279805931 221586720 833355166 380208698 492041661 134452673 490597132 6232441 705058747 154336466 351277453 385433080 734677469 676774713 464297259 844388683 832635875 500276344 360363584 267788540 159886855 29752368 219727684 35368206 390433250 868118123 657755135 27844801 510378802 996513451 48534391 925359541 519088774 859228727 115209028 84478212 17088805 136691087 276184209 875002340 604112164 406650785 280141515 752186683 82568074 26866824 610819943 945503097 435917938 366678146 417675617 105381794 172451803 546468547 270749568 81507737 801722818 704103506 337180860 968061714 697559687 939406929 816072311 900102702 438993947 812062430 954113815 344150311 318860216 80544414 708916442 311098387 264513685 431855332 226131823 642947803 251978544 386058654 423369733 509256644 912304943 494085744 656517794 988106102 389235406 194282536 6416038 339637797 921829567 716956483 635490078 803011852 427377635 272718283 584267797 434260526 187636277 384773468 318561772 69163658 966315564 476327338 343003111 971969695 51789022 827629793 984330484 40217726 136811370 507308760 46137948 696920495 505119228 87375140 159134450 970639043 379666016 717169216 207864559 337790676 589746629 597570499 972938765 955831362 626245755 53168172 475243530 159358832 142625017 976301001 865310763 343759626 94860651 612875121 917321713 850170058 359907921 939874206 894555222 198350861 375303335 298369017 738446932 916016568 101242724 909651021 886051154 334672355 487929238 278167096 787558081 459174112 49769087 987221261 307914848 883414334 546618188 345518957 52878904 501899305 961624441 745119841 724795015 546795679 897126911 884177443 167917045 591363072 633105658 55555802 300758151 538295618 681264703 34545633 494511710 735795917 975363103 170163917 357457218 753608288 243969143 295932872 487852530 967557450 608076122 243536802 203373392 534000218 784711114 985750667 927897941 943677863 324512695 137416302 690832382 670862265 275225799 876423702 545272305 654246408 167016640 334844443 452035932 119183734 513131936 57439425 896489581 696748849 264215694 369976708 133508975 204892508 60805905 895558242 555309131 499160549 787320671 737073369 565713247 22675226 70840521 950164840 795082282 168566896 796220682 179289639 474335988 617068026 591488744 486374083 743651320 415918953 634591777 741240758 893096468 845496605 774548919 440661928 272680968 659481669 403350977 486381882 451193495 514468939 391487890 833517878 917368078 384595933 805872406 62333583 375961268 986663973 304768715 171413355 517756677 24812532 120307969 995386269 825343841 718739903 901700610 762913348 785837507 227363837 169748625 205744307 510771840 41831607 423573264 837929461 994692986 513622011 530710496 727102556 275139159 788586112 343204622 722167099 833253577 344514816 308675298 627128810 342634009 301441413 802250651 281272438 260119362 44940093 840143957 452192515 387119399 702967031 608125441 959512951 721067602 556294170 857827491 976638841 463036014 418217415 768620073 656721726 715685723 130828258 363863828 465536680 900149759 472277362 315284954 831689859 761823893 697031135 965516730 989431391 617061929 982200074 99548144 221320039 657191937 616387378 970867647 620284706 834700736 58698380 198871916 589117285 780808654 607998642 853205096 853707735 80877667 359893074 839911173 608225155 567654576 800893553 621719454 168129694 436101571 484268850 563606294 131390263 371781635 423664161 563385764 883184154 685317636 488828010 302978845 978449661 454787990 520207690 593956482 921690717 320188331 905411191 228328830 125228816 348240597 445233712 376483127 393535085 931868227 565428894 582671985 88676881 45436190 526310445 550251255 936422227 212600098 938571453 780715284 670382234 859167518 44800294 585539114 601141878 997131783 994342240 798656059 410705003 391984157 927146186 585675903 882579121 281231679 5903414 251595297 270639159 424911781 447003971 932336147 228811630 593979134 241368403 31249878 2051672 43460435 287075407 317223211 270551918 552759447 641793831 409405361 212182605 878655934 742515831 143595999 44779080 136848693 963921603 731481764 277200362 463678326 680779737 362809892 375817779 216317767 780869989 580252148 791203391 757025404 546862200 737121092 888761552 554382642 95928666 56828882 428819149 404219425 892877786 75749458 453497883 456875221 603441598 852071107 55603529 10315825 661855728 542182721 554977154 258539613 317302288 793037364 974881553 177904578 571454818 715254318 836580959 820149356 460593256 919600682 282761028 379733799 195442515 826475357 868053823 388353368 704953944 856334878 600141461 681273836 204190259 57507036 590504323 1245645 987204848 130159577 186507150 630623736 72297861 71432374 982109050 952283127 891114106 127035408 146283451 909696867 97680683 154385481 330215098 636074412 643428374 658324356 948247074 235846811 330600373 973455677 42829516 769630578 743775566 397319849 822162119 368242500 999040299 21436452 964754257 271084771 662663459 799427669 561533226 359484491 243914814 455201049 513474074 305327514 715191777 659417807 645927201 915884437 139415261 361059359 667192690 767103027 145844361 914321154 547549568 393139328 38783372 460073040 883116720 28611254 938182293 352241745 620911989 938893715 604034315 336536616 390481277 636597678 410933625 179793844 534585912 605104149 999999015 397097823 767109810 318242604 384760613 387708854 300216208 32186815 912253550 333453561 465104210 799775478 73041935 467667148 536568615 200670859 427421030 921865766 545359995 955901735 299927223 804725308 796067142 55033305 905501856 382510587 334773726 586685466 934602448 380946403 46387906 88361047 979137038 553254931 671934624 784080212 728099616 499680911 564202810 727246518 74181100 492252968 98546919 288205943 726164589 941086421 701170055 275422550 526386743 600975448 184315497 482115356 243979980 213812423 354704140 702793523 842642175 123619513 540241769 571982567 284783422 311997755 950861867 586063731 659285992 418728413 423662924 19577696 516167257 422185984 497247019 77088494 553530502 712073729 508040588 224074851 860406688 252493779 635676530 928183636 894459439 954590053 388257344 22977859 96141056 109584745 639638800 545676668 872620858 553386547 783214301 103990299 818656494 500945621 538653627 572646482 352263564 136023785 49675259 342779463 586120778 133498608 102960954 313351580 948371747 516182247 965075255 473299840 509250504 213138609 620671848 317777571 687438204 829588498 3687994 935411208 525719531 484691869 53961002 388052694 510305467 889379226 632559180 715907089 170195115 570117079 606586495 4539474 526396054 913913448 875825052 373776875 170160867 803864299 991175581 381579202 250681649 351960094 304572748 931849378 950944170 857583973 864691889 866637523 971519329 783929163 712600359 522284607 437882791 492411853 765971968 464440107 97332546 338229207 190559190 164445118 839636969 149673436 133073787 308242499 557374253 171990298 240040608 122202047 211906675 89272954 985439918 43726461 97222779 535931986 166703455 574129045 397542299 512217823 147495524 261602375 875842145 19662697 856629228 548688681 674276269 307731550 956561636 842915639 71415701 229642393 392519196 999479699 884040514 494196275 935262970 507528452 484901823 382995416 980853087 898472958 767826528 635811790 515978989 789798688 572155192 281914457 398170051 789082103 833638941 761939126 115982258 436530569 829534040 928977424 356399911 929202649 982447265 82903980 624552847 303164470 737599591 986546654 215623155 696015984 842220097 976785194 42705960 375739370 606859447 164343415 801126927 451779163 589072195 597370678 548523700 943157677 91783525 445009850 543185218 395852174 261736585 97045220 287923114 303256156 715797283 661673824 287273973 500388676 203634701 407646066 109773135 416632078 812677154 369044444 791877879 834485174 561967418 450236952 836844628 968916722 578015058 827169118 175739843 155441124 495106634 581837890 817284973 992524227 284105688 90093293 1737264 665439330 783812570 929028458 953126078 85671199 737968423 879255365 263733359 97900164 794458103 634316148 628948823 265711776 98242312 527895352 668402527 31205189 10840909 50898038 696157012 849120890 564999944 581385370 554760758 819708734 26821878 985916473 920122817 122192707 396086855 672181738 220062393 201492753 413575469 320893065 319587066 104121487 657753279 610459656 316596867 999440989 479603020 325697307 89369321 254878155 447345481 811134316 753130051 153148683 241335490 311779798 581533271 571050969 950665256 712884825 346519115 407703646 678028223 625137584 147710391 756970552 192988826 769631896 722325992 3044297 967765708 899100800 762822812 209913033 892234040 961816021 815305038 429926909 229610579 699136081 738278126 736777527 51863169 600522629 12985971 253925434 822899985 161035265 658549680 348913688 572354477 259263390 506945813 694582337 507004889 252949324 693401756 455937086 787457410 461654686 224718447 657690331 953544821 742812905 397055359 936942179 571950049 804752264 268247567 161530103 237353020 777869195 76768632 92052932 220536345 628028075 717467372 280116995 781579827 640188934 269991541 497833286 526827783 860482148 865062944 790548586 264054159 213947231 498317867 388013025 876422103 191905657 23619932 681879875 96204811 251499336 722296633 246546596 880799693 35999790 477058048 370510097 878566119 905316004 742254024 838026730 677600432 368929955 331165981 329118340 823349839 350872746 169244237 28052959 666527151 764168172 968429738 183250528 503461040 543648751 747406820 165501016 172320046 794425941 858693293 272415474 467102472 691087732 761208226 353548763 822758225 211160251 755802209 792609696 821051308 811792080 306425363 683230618 340833409 540353387 944120906 35598333 541662026 643147622 953420278 901638032 463253927 714883693 146717424 334380729 867239755 683678537 271879586 279296115 32368632 598179506 823079900 758053218 441927468 196294328 962080050 791489864 17632922 81539613 734894896 427408688 889493912 498367691 113563958 935424819 630175051 610940797 344461790 864622317 493209439 153745769 267215308 646108400 112807398 511122848 744268453 859130795 349678422 644134067 162771383 428320250 473015028 814807101 752312472 429865565 872403200 167172591 692843213 386527249 638176565 227162768 156036786 550521883 82605988 40848271 28638513 353132064 512650517 325152621 784193706 159931451 46289705 16439293 743774590 117572957 626383560 641975191 986179056 943267570 754595764 177435088 259967850 10341705 785085106 934386930 706106880 659872327 423658081 241173465 982789013 852165083 332369208 237088374 219016920 633874936 588490086 806174791 476285167 950515757 863144830 129926204 294769186 506974794 56830310 314625409 165079105 890882476 637263628 895760572 184186411 422539222 234231616 895034649 503765145 569501988 232060773 103555000 593142423 898869636 76706690 410211672 832578203 308343258 474179475 313364192 431196994 512152033 811445869 443228926 513267335 971124738 634931244 670178447 311597875 856806883 113106810 127557166 92922291 923015300 199943337 203747617 80023735 716142738 332200645 22642827 542641241 995987833 329790668 735298302 491505988 284155683 494626942 75181736 810125945 54364355 572850615 954855378 914802354 715215790 392532848 769620716 425154896 505558000 596636922 728757951 748330353 126960790 352214596 754791888 435621960 722139796 425377879 62172824 953652602 852794040 617958093 64704207 660091689 302898640 558696454 573252675 596192873 229075947 308404224 309602044 295361022 48123930 666157261 186075940 269021565 631708383 215859883 39865608 345103312 70465115 716676941 496356908 891416578 381628385 720233862 461582462 725836117 632905495 592148780 12194108 692087511 482413529 58698937 851098235 615587574 965868657 789847275 183444452 249167830 380964379 750555170 66192170 903855582 90498219 498613935 930331573 300062578 370697419 45894531 115794444 621377889 912266698 137270395 774578500 591665674 752306588 674639668 596029133 932949192 536977155 623342312 86250953 368691083 312210680 129540213 320543669 208865205 375150837 281517735 238810095 19162917 398126841 391079328 754673538 364742631 92271037 428862994 784850928 493262568 384941793 540467524 761343056 306005283 929111883 943873004 807324642 940296485 687402843 801084677 77717677 737784556 3883251 332106106 976803087 406556522 717878036 987431351 349198964 263867102 509443158 480036796 479390755 775263154 916989830 380069685 587772323 933552968 476511471 684888446 29427493 845510330 702502343 22734573 607484822 813836302 47926489 4125183 754794254 562922433 439825657 611643271 295500867 921026965 7787364 405833712 838532073 811298360 355638763 172689330 40495351 569713725 609409060 783277465 352635648 463817856 106071931 175076507 481976879 468160908 408671433 5143744 1419109 534827294 866187095 199196743 47073557 229278423 23650123 848398536 119770431 752401970 158356213 657178422 129825812 641347890 406866237 634242349 250862242 928633061 132733219 393623604 204487514 942581432 675695994 8811405 502851067 475527263 472108553 972854745 654676528 97118203 122401726 814957860 774890928 365620365 592335314 53372864 716497280 357767472 612620094 49636760 522193233 388902861 610342902 162278872 475395671 155060976 712296225 123321931 793544487 89458417 217201153 982681759 997512313 838709311 618911966 304370777 837286432 125634680 869261869 537223031 81807606 309584496 56931663 281388869 328507050 536632498 237645033 654872288 676030026 150256084 843813006 830192164 851798712 191995033 16524315 778296138 437654650 937277101 146006011 523040306 912913694 274706125 807720310 155729768 167013584 405955100 883481139 900863083 256119953 636033517 167400817 203183761 923310186 502235674 942962395 441677241 298239288 914902996 19945266 548535560 909223820 375628289 904536349 174188049 783311520 708120418 602679990 564333768 411126889 121777013 279812178 973218281 781625382 173487564 378941187 971489585 86112284 808782434 333968877 680844898 634864329 78823833 808903396 484874094 437243494 419719882 31457078 207081209 780570120 868400820 227276145 199013267 961014309 211337953 42066110 569842639 825568777 329499571 33795669 693566577 774047899 790249421 879481426 935358107 652824631 832389971 400987292 163844127 909624177 488051213 46789721 885624693 887413449 192519850 354563672 203269054 998758807 922127236 297726450 513115782 313775413 772201486 180597621 226414790 722297970 327398006 205007751 245728162 792944592 525020384 246054267 219800216 542327133 64600356 116723073 682436515 240671299 401184014 322572299 502785841 917814344 417441915 609442389 350402425 223034237 75624066 619954791 23669640 949371161 938786981 517126036 536887951 149948788 952313631 196097341 434963625 775745787 845145860 324333866 60808537 632367452 219618347 109950262 629229221 30486080 114110079 333828786 425339215 282465949 606671104 652610651 112775726 947267428 987998240 503200702 433691847 576573207 654177526 621932352 160076636 386744260 260045696 472278290 882096193 489768878 424164171 995215871 694826480 385883746 715238603 614629170 549329154 133972130 542327800 860560606 963887300 211776225 792306713 204160037 870726288 611705411 459335176 391839385 974299652 511506103 6062624 73506058 444419077 362549414 572244514 609708906 966318993 539788880 976309106 659868021 162960984 326797485 623275456 139406421 660777527 872848306 550123205 531960801 984207909 391328714 508643758 273278168 807503831 417345362 517832323 401625802 571972662 908985790 701480863 442068464 786265742 372545591 906736831 441836791 704073404 726746791 680092816 161662280 290686088 877087514 428155064 504625771 326842141 55574843 208040962 330830464 165659603 258157818 938710154 549856609 851109733 228779237 721980702 796703035 593580933 276913576 788660621 164205241 975666194 925377187 329705637 195562814 51243045 781350722 954882693 720707572 926936782 217890497 678338490 449429516 972243146 359978181 902042671 187908252 240490807 685333121 380522321 575589105 246032178 566961156 742826016 776273139 678617712 915310062 406167635 773126809 556870547 848994349 912714167 616668305 940681194 378658220 975886902 500008830 228130194 407316832 308898037 68356183 831818657 914438991 277340728 719382200 490489790 72075001 723382262 128895134 959095684 737171663 123085220 874636982 262729273 51638877 321102925 178880788 211506495 247210166 410354878 333658158 726768487 905027941 725326360 639563658 261668687 181499429 783924572 330980812 826369932 494317119 241890016 292065235 84170820 771074044 45742230 585057399 141010082 868157383 658590850 241455334 723833024 997944938 246103462 919998931 265946682 244879801 533098477 597885043 200725015 382250089 296755204 285131196 586146508 649108993 608085190 810567106 499074714 935041206 379619037 402428883 271387834 553550841 422128004 263883044 687502153 920873580 504033206 971047759 556922114 248171632 132340146 525914932 356020370 922973841 170479486 833481185 646082269 338796280 705409861 601433674 282152270 826031943 444032859 799188901 909980764 341821036 209156737 517829502 286413082 440644311 282430435 286421233 885461126 630501791 585939571 671455382 704823464 950902957 372695891 238296963 230293104 740552978 233943736 598613596 787262228 819630536 347370918 887272837 819584658 951886780 195312783 965321297 880488927 883407886 437665936 965807174 966361726 176726507 134591630 902380232 201050227 829563160 474697156 65615501 825518696 147161775 989518151 138016202 64839311 324024105 907240417 217788114 663072191 808823804 992090689 112791809 760673493 147214710 991031252 666626980 808411268 118777557 753623214 700039484 319187076 129824876 355926218 203376810 847437270 394646455 179833273 857624042 775483476 793711332 493448300 352092649 306784319 850239223 593943977 257683880 214641249 122783542 566111140 632083810 963306669 169542898 905465382 291013152 839508835 51143099 666094236 144010474 586181871 891198000 893079357 984770866 369243255 41832983 111546271 420613993 713188355 363504486 143442632 657873854 731029894 418021196 940048288 343786496 298198036 441375968 776471205 583953132 311579900 356473578 352933848 295348230 910655771 864636122 509264839 482131589 739601230 818208660 748080404 119688617 834325960 892417839 73498637 885322125 247992782 164729276 478234210 632148182 979021278 365483309 161178110 219144010 938398621 257156652 718666241 55749314 47122572 765215711 959305722 404650294 845270563 810638991 84473565 646061454 282636283 137361678 967777633 352703410 74961689 867472587 838751307 232126033 241349397 851787535 523024834 73192068 454476164 5307796 109386965 786467227 965318551 110911373 469062396 213425254 697046007 38143642 996463878 242417915 251316971 928498349 104054335 174890362 180991027 643034352 677990155 184213287 882817661 923720890 569068155 450431961 749842451 543331790 62280046 639832245 308883352 304855844 314909307 871843365 713817546 121598325 526360621 213668473 511617760 158281523 419467429 748282210 387506119 247346189 886853662 280500156 585246741 11826877 568397982 823739115 91180805 416427429 654389052 945958704 313707855 140040935 533699418 238730984 624836775 981895644 655690370 852112348 799369179 297913215 593003365 902545852 687116165 985196101 319425279 190957805 149753682 14284767 100355335 308316216 737329181 122570166 886781421 217419647 819134257 287244809 521462881 439382249 205203677 381684988 274742859 892722254 526949428 479205576 970467099 883711738 92080774 230878927 803424213 650063793 402512764 813252209 299853573 446842859 977252250 620042500 991301230 136965538 796713351 123423756 104428159 581411742 102695521 585551962 653851380 363556555 208629553 904860783 615390847 847936247 340528680 907981812 900252961 919490905 438599438 833022606 349120558 17434102 559150950 299354664 779141139 856194400 706487564 879241943 315679028 447629853 696520070 81183282 235843477 471393520 878088053 123850377 4425003 196645725 437887915 385336182 15842289 113059673 535662970 897170361 358852055 76510419 379223938 467571658 523394712 145111705 54681157 364913672 495530780 958730079 482377782 972896849 133422620 688350840 628593243 860553308 672843364 977038000 945909901 331442605 138538284 155956890 458171087 339559875 667216187 157692780 534866169 112516836 420318828 460657095 989389027 392724309 206022734 1902082 454108977 545716255 912458380 110219232 109687972 480142107 286610720 320652630 976314937 746067679 693818795 460043380 897891253 775158240 131479208 302087058 406203557 585358659 816459973 720953696 165797000 905108880 592027454 216961096 349318275 667853711 23709270 405095316 147506752 146146317 89389279 25676569 366330343 598167881 693977726 688760477 460521641 661300923 816008542 466026902 327499952 707534103 262491572 550473124 214122853 896443122 423938640 853353112 420128106 69022102 611467318 850943818 910181296 590233247 527325538 865980493 549503145 497593789 955095390 167694741 936874310 747269583 615546142 784606677 165876579 668181973 381809568 122879086 365337536 43338357 608478940 634050885 816132521 458264756 794387299 228612250 142576703 572264913 793550525 383923257 616814211 390428741 567174130 173427873 746266900 752905706 533148942 664258352 739148374 10056656 971506657 396105335 527916210 277090634 619831125 64864190 614933900 830543306 682546725 222733356 537238137 915232549 910106107 571839237 206219567 87175478 754321145 541181021 982798519 250496301 113115774 669842869 564588446 318814826 95575535 688598598 213272582 221761716 447466773 627230166 810844306 852892703 7450844 552470764 844402779 811332935 840315039 269022961 571693474 239323451 963928004 432880011 199993960 446344436 710240064 462532547 943577593 269392612 785650974 918195627 213435143 128532267 543825072 675323523 184144246 120467032 568631368 664023371 852119524 652271353 372740050 269162019 980154321 710060740 715871321 642592653 274056103 55783171 847574291 137601871 417699085 913532403 79114839 415746888 364015343 681739682 654150702 973486294 500875698 434381887 97521563 251275012 871940901 435660278 205406136 74816937 599641378 447072581 724987692 853879476 823630147 886801998 151379530 734141713 809163504 585821118 270726809 938859319 250445377 601277646 915802075 108197223 105441547 753748466 106875519 43849156 447409874 341766977 336746466 26349879 419938640 943536039 30301038 858322636 216838972 525195217 280119255 893565618 306804580 327495318 350468663 288303874 123523329 965194372 980146536 928144424 950862539 58795777 141559761 323281899 407176274 899423950 404832315 232997344 417412834 517294406 710044105 924199962 267519559 812391667 458619435 954725549 100617186 303477907 253871684 761833396 424367986 294930158 286479717 32233144 433311406 13233077 820084728 454404577 747008974 286897145 571260948 25053220 920310212 109236728 555686910 737503048 801889174 867939885 639423296 617669034 439463568 691943279 586242285 60237669 947788970 643342107 870776259 754496271 362897566 305349276 43392619 717885671 584265970 20105274 519040531 177900990 963768727 20375301 408264730 131317223 344763813 703764203 765194526 731754606 915336693 415724125 17174924 109754253 479806510 274539712 617509124 558117770 805637575 737609396 566718725 355031039 418212047 483458047 529269881 456938870 773786785 206998254 594550187 166256568 636469247 322562637 464767027 360040125 243941368 778559330 599452785 725354946 69649041 386542941 878451952 317436062 495756328 724376864 896289344 533857942 774760765 820943997 1732086 549890481 804200758 548667438 852013427 50767054 331256220 369137823 600289072 767849187 121767766 906121945 921880085 507324017 582575069 217997593 403918721 18056187 420761929 103325072 235445879 337185049 714285452 347710081 731349059 137813780 790609069 31710778 189821363 204192656 84924444 208379994 94784002 362384770 115542635 403774116 436669426 334375880 993209031 353041254 846726219 407198227 727585276 962162766 533857000 367284209 94575495 55893686 78202749 920598960 284522011 539204438 704089700 28339207 36925154 703112915 31959604 999933016 350553615 988228758 340067823 452671807 985223991 591357675 611438511 71563785 521783424 900654615 602383972 426645780 561309839 915862582 515488494 803411509 386104399 195170478 761326046 760777477 501605494 869624885 879449411 46107812 651280875 599259873 679523520 196752888 650594379 511028250 201385790 287857806 201051334 81340127 600654865 991650211 605156799 801148483 575472164 882223922 761760151 512481611 87583865 858672888 897006454 803234520 798329706 583894076 259326981 538709421 324318056 440416738 34555089 299831167 952523849 432202900 473864950 59568089 221148795 321235962 522715231 647962744 147975597 716990502 213515992 38740835 592213486 949867347 398726209 141672688 99050800 280311094 406547538 227277917 971169181 849993233 439078257 531508579 48997697 985681866 3649001 870776999 317104220 893503730 31988611 35311115 464350068 947278295 425308342 773403340 382223703 732004893 443691967 659094537 551607751 820256085 686951608 739077583 324653551 775276435 507998355 666827130 892336741 241578715 767605503 873231023 813863028 569218826 771358740 836633847 691734040 647825098 355230927 230207843 342591278 805694846 923860389 41400379 294443759 270249763 143034953 428493129 569355146 282549147 706296463 572181762 403467795 93502739 147527662 774700267 908485535 185027511 949304464 896865450 502367215 434226622 497113849 382473888 290551167 84141520 246551378 160102287 439997241 825187070 217545598 60917153 544536740 542531816 471853062 759751417 798209015 600141672 230527724 509058609 651101351 322993908 459496635 768404571 904637873 734392942 704432740 94979983 483663818 228465513 212007711 971905220 220633767 66297075 233927866 58014119 8371787 559856606 835711296 432300332 593232541 437131262 143560648 735140160 892217030 830588733 357609469 61931344 557506326 734036433 866547599 571653491 419404169 44579368 858055909 46055935 92294544 966913105 605836276 554082403 567552224 187533221 493255786 241094591 880826802 231893187 984976966 902383568 786932905 56838918 693272733 95551393 350410863 901621836 327554583 222442621 628693830 625247702 397467264 419055331 772781171 692288046 302490581 158812174 870088237 523203761 939120375 44129478 315543522 992025917 539061764 168496068 335595661 622700891 717671607 221182245 92383362 31177378 412445384 399937792 35826864 849093052 604718410 557796026 89104052 844571336 866116396 569952787 231623038 778441120 706607481 871009908 409794168 147623488 470077203 338188067 536730475 331916413 388455385 775228908 935511920 450782726 938064111 684181560 212001459 322571088 421432107 105259393 128569351 17312459 603753962 840677789 84489997 147179215 567684012 346999800 38369889 536656231 459100195 147374948 734055179 507481815 502725738 895576474 395160696 109766323 239520110 331865755 29082087 407343577 24662463 372855989 26461568 542242442 463152133 841223517 444836529 535604460 112160674 32497042 88586952 439991422 823148821 562574598 890286394 676319711 911265332 964788084 304055757 51850073 740345686 627709939 560309990 403074145 733192050 698255480 38295910 151753453 237755016 329590542 690992077 889572242 963379556 831866745 980729219 715952865 615336876 358781613 684830870 678839137 888792732 768626426 690787876 435886133 217405176 645890064 672644674 886004737 648433039 58814404 717045863 176442680 843264564 88526106 270857660 626644560 194972564 98451333 716089048 139856548 593998183 473477090 884840488 283435750 862349646 864057686 499127730 51925150 201263342 328691899 737617478 887702875 954155400 863568753 276740119 931394110 796746557 488612402 351316457 814013878 194708676 526089997 507613155 796706107 133754317 442391138 270173859 276364600 613987751 87307354 99553223 847121160 922301755 701051630 432411096 566953565 574206702 273177986 526531039 278275482 948194558 368292607 769825235 103083800 294153759 752389758 510433732 113310825 369941380 199404723 481981144 152293842 801156205 333391894 392975746 119588501 688290235 269052191 976207306 20594153 30452585 230635427 201986974 521057446 466401645 990457144 3470936 102010119 628953986 189103716 587232780 808647980 657946602 781633844 608504417 845330938 48944398 567713729 167450782 74032903 272130841 292203505 160574727 877353302 964919236 297195694 894415167 175682935 604752685 179841512 540291541 23786552 572887015 261452446 120416601 821811348 488053358 720436346 512861909 253256524 901345860 738391114 674042912 967834031 306147800 298668699 688800375 539963336 745147844 252526978 962617618 468785416 122461145 418691041 121305920 901604049 489082004 401512383 712635326 328703829 670745307 98537168 222086950 909555578 241929366 821963078 88610349 568502349 262171930 284654606 647810280 40754705 233911266 122421242 564749802 477901531 287451796 908792459 577852702 168788615 938950496 778530131 656812924 253851498 124645286 959648966 839853102 218415732 736650996 269668916 214176731 534918444 724143809 184796832 189511214 900911271 5606000 585898776 326541064 665287104 447819071 872562898 450854096 727413431 627332341 131612042 400531307 588628587 970374483 844990392 504704155 953226077 832353970 530896534 994686827 145048181 66187279 669132089 531099211 574189094 780098358 83705164 496916579 750515952 706305334 664545065 171952775 913046713 421798281 972413445 587047693 25335759 535238160 909287323 686677087 441223234 780381719 999783855 710703296 289031698 878746762 3752274 175208361 455836441 155854139 213016271 261218407 358006159 811053063 269050384 442784866 774183065 11827580 796360773 656003715 760213787 32282295 767696770 512127616 471298065 902040670 854394841 49466264 864175794 969143129 569500798 334075594 664718364 260849198 244721575 621460421 637383332 515623612 141833618 179656146 674272258 481950965 605117585 239019327 144904195 709753896 676378623 476599412 214672364 240069566 227070785 343587391 90139933 889665923 664599366 43771990 33122890 53512375 7956872 401233674 738521498 282375795 658671649 352149773 86517570 88163490 706957207 982589696 565216382 175862158 844496849 387215752 202427565 309604787 95908275 899140808 743944133 618053270 880249394 107536061 294879437 443650517 387205350 16111844 484815945 530525835 433799824 174504188 867037795 189206287 664384261 413418796 746865258 994958554 956903595 615479616 798315519 320135327 244440596 687879999 485626568 325989913 101235658 55867246 706606014 776070185 983675431 212487812 55932050 757356998 476014864 402445997 548255099 112933092 49937597 873008988 322962575 594343733 549331614 456363338 912600909 960965983 813197714 914870101 220913206 598043929 16209668 198196146 257600794 437623981 716818438 133722914 793015313 285393575 612430643 401863883 647799531 381789716 493873952 58466769 247212534 244447043 241961302 387044274 579411017 557621954 920417723 662923143 784664698 60663475 681225431 190508210 289148727 640259030 598966697 26207368 180953472 334432079 762832880 203548679 833083118 629588379 110049341 33216435 115247491 317924595 731439524 48547277 186325953 828756955 680784246 944780462 960073682 146248870 563153396 912365840 279166746 132449881 784393446 565027924 735947051 524531258 519782094 503362332 907673240 546197831 248637420 951622539 307850066 133152820 966219880 568620750 206906715 885988770 896470936 276791335 910401271 54486793 289186456 666729274 950890253 354466049 943895321 815425477 58446964 834822437 743259765 617606468 592558883 691939847 863459634 830916271 586297512 984098041 976627906 945212744 154609461 704669209 6985373 241136187 605731877 391123214 12991138 780058097 469626620 597669520 759090901 156248628 451880153 185766400 713499221 981418143 24355469 121430580 532759884 167309038 379658350 774049934 929964557 280277483 159382726 580620057 498650006 614140228 838873240 611139939 222591061 509440657 619363375 218508654 624762304 483910238 798226005 329613213 775330940 35444470 190463791 640577998 797322291 324878358 475348837 423403913 256116998 92784431 205451171 37270189 126726496 397632707 72642497 975781617 445125422 112531765 355439210 992893117 975223501 233387843 610654984 142056802 476931756 174303199 597345122 757636734 545990136 553543535 838389221 245232474 358655235 439948717 361006834 776982232 817382317 300797224 54182274 648580169 545761649 517039137 998660425 159605574 770912017 231257345 829295868 437155308 511910780 914106652 861388632 657921593 251062674 471781140 308250823 189204961 939142971 935689594 297046304 885744950 198200946 714940658 623800988 980444874 404168036 11536512 251445518 597963369 800902768 51161386 799337420 386706531 904564561 489313606 688939603 208174780 908842970 217502788 588091809 787949700 194697720 629754423 910039685 693969028 961329521 478682994 944572192 165683401 641650527 40593856 920304333 361670879 339427931 225658475 202103700 631095535 132857816 70098805 145001389 804091065 823666280 536049141 971542586 443504325 812329953 559480354 474383208 472815726 617150197 437496545 360156376 24600152 450516485 558963677 385194341 554500405 868568963 163018699 844543526 324658717 210187176 343656069 113462054 801793293 296382698 518041151 754002460 941510780 516787111 288034563 582051148 228890696 535563878 928926251 26622950 604972461 523968329 502186355 934734646 400837473 894540496 247589312 328637171 255216393 450225248 605566074 15352632 968230265 279326177 311067237 794642108 764395277 555392815 395502711 33160543 854201931 204020038 336234363 45857183 976961180 302862058 871613281 929788890 661255731 521350281 265124320 408888059 370133934 927788810 342202900 893934495 127096817 779227912 935225492 705231926 26603009 898885462 219845178 836730168 153965262 629975553 373986314 754332838 29768608 334867029 349553169 139172487 432067415 939700827 685283791 695550493 379213385 922532764 951622543 41518300 378837425 745464731 203612969 711353833 657777098 958909223 137890894 558864491 469935676 26065860 726584105 109850986 476625369 739159144 37253640 558795503 410616380 526513668 967806334 559832127 523913457 255379159 45578987 883251274 28509309 907708978 613247606 504084868 416069180 959065273 366460990 727146786 131632855 727362000 369673097 893426929 310279135 579247765 105848913 224287040 330163858 685294650 165943551 494333787 163521059 488372737 852608310 996070766 772268665 752527025 554918919 293235668 94820800 570660045 843360115 890680687 927603173 972390210 487679898 877005888 839777531 569469211 655488550 374106027 419341257 63505723 419179393 53494872 554227318 972887618 603729689 864432188 72396389 776236162 250352459 709121820 253158636 721913021 420891326 891530957 663449881 849367693 33238906 871070235 768915816 109740076 130590945 49529791 105053340 782827935 621153924 605119257 552871091 162850753 478280585 261578320 964836343 263962442 303353869 623732563 916569030 366083267 385407604 868232102 937537663 156458594 233245020 351800602 376542289 76137796 471506758 858295473 971739219 906746481 625013845 612637465 402032290 953649054 912506135 393810597 717295943 986736637 678488326 34310379 463812509 489256654 998156247 775950548 129419311 574077722 88837621 272215308 955822458 84706218 326730382 427494916 637847985 942331747 147043377 922760169 491091013 279577550 752499941 797813208 196795777 213656189 136805872 496531787 811276841 314658216 949192716 902675683 738702940 14035834 659431062 685551793 846406354 892792606 57044588 445159145 812069920 951549595 577686604 906214162 803760894 514295274 825166465 844860600 842073982 61555912 605441762 692779530 455480409 450271950 694139464 671750247 34333019 90753791 998615791 883193639 891338525 871074257 412198369 662125370 909681062 740423801 231035600 304919311 458341341 452038476 831152634 432100774 674641236 779761855 400603637 907522006 441944942 467654203 612504002 332502722 980995958 360302035 680976619 297914428 553950111 28513511 86457340 43404038 388044595 205303699 418003738 89497133 356938497 566778069 909539146 71475566 243534723 885087901 905477205 502359560 988756801 444696380 789103026 326263179 226093173 603059218 276404236 708870836 651992753 613318368 922464956 289949778 246316143 289855709 838345147 165651500 521240603 518987901 124041554 375808413 320997228 58353973 890036483 913279300 517182241 931819288 928585438 340259590 926060434 800306475 233769588 385771746 188466563 394412987 147874601 708785596 741710788 118402057 774019054 674719731 641288676 806247949 724927696 960942561 413924270 66512650 835273637 740185710 921676307 38910933 479511938 462094648 207573588 746681331 293782158 722533589 997117279 630508015 921137100 346766764 251292223 76686157 999954044 430529465 132192745 814464643 771106545 487919010 81008542 145027221 218393224 338454661 746055147 124859833 123414781 881167039 95845165 242368750 11757985 523653718 832782754 384660855 747617374 951493680 546281392 129490318 48987548 948279904 640072889 255505586 147263706 795398076 278508876 722649661 820140867 167873080 530454116 34822179 776962880 557538260 709890529 364379145 31957732 764420047 183105997 654379056 47026396 720555905 160402408 267953406 350573706 235824873 46219691 82450174 701458023 987385154 27448643 268061803 681019547 229056191 272713151 821540222 71454208 190312473 604796809 216232162 772649738 475852158 180641355 433347701 996744654 756264074 802809014 980597588 943121260 743389337 600285721 299349601 733877307 170702851 61693396 615318667 869917340 247554358 320506808 1548310 525736811 342790125 580333163 87284160 610756342 455168504 447942010 891089391 655260434 531610327 362269636 307009447 217895309 108039808 917559442 873705932 12723100 327367746 261784614 77344852 994668646 544331912 421623776 169079442 606625529 343138435 835701391 904501833 630212776 388042894 516605065 955014956 272490507 515011853 545711662 199880261 285107868 626600246 494189726 107702905 721182890 962049113 156303471 323500300 478736676 651147605 454772969 399517608 71971018 927468638 666448368 250249428 261644735 797893751 298259292 385836701 519558765 68452933 972542397 469799348 43349088 903213833 766961653 793033817 37844808 681406260 340123916 865408468 609579017 207072834 980428888 312017245 389679892 659574885 133036641 216047869 102119215 346269850 393867948 200733022 104847381 225239448 664167661 178386902 911702524 20845783 631204515 37482242 905918303 926828177 671259358 852535713 288996915 981246435 56096468 611238311 374410700 43325135 10131392 571593491 203410029 647257458 729927795 970950791 347697572 745766687 807504142 933198822 712694362 42037456 160337259 832934780 651348767 923241909 211992982 765906350 146414892 434738813 523631695 886979375 145228865 886560942 685714874 479672600 424132677 434290749 259343122 973183519 241667630 14070735 779916616 722751102 938996561 83811725 138314475 263258445 243130230 180074461 885374720 960871532 57374778 173006620 339963687 168801224 371309725 662819173 762952269 49881820 255514780 440294536 920931162 99699313 876929414 153842572 71921559 320944405 710847980 65734454 837360819 565143954 97907453 35658814 543096274 489557540 27210097 901108391 433621242 363463282 331196407 16591055 748923210 916299042 883846017 910553530 523929303 141839436 138554394 152829960 419011940 348258385 707633714 761392714 886494810 103650770 876345836 718808031 668020207 762732455 698145589 458238181 316684123 25567394 525364822 323768091 971160173 476265460 906412593 163059141 583523234 328857837 612734499 437584621 344725364 697739128 845307194 379626923 346207318 874305665 209279487 401584366 371217011 403396587 596400198 539422828 336647902 922957584 428939362 509628279 45193406 911354436 152039533 696658091 233597595 203587845 107664048 343651859 288153766 626778794 185363392 10547962 835654735 287706683 396953768 150649034 881151882 332517256 296908868 577891991 377984332 573680992 452364146 788746573 368663087 690706757 305072933 315669312 214624480 997341911 295776616 6603839 842504193 30779904 217769863 238426755 587249720 843740270 987613302 335888258 950867044 502222025 342971482 557659483 393893249 77256860 585731270 667971761 313840958 909848899 853236307 93881382 530313525 403805600 736915962 454549946 239334965 972816676 815449381 264405691 410637630 446782102 377076662 898266031 720591888 68009533 696291618 947351166 373512074 614108466 885730499 544219690 765440576 142476131 436358730 508013414 968685517 581163287 929762441 720913305 159111034 23045604 725524754 78263958 598931304 25031096 143319812 498435905 62726434 722893630 356626311 116876163 711372455 604766167 366784092 905691498 238971535 285332268 333198890 499552063 531588157 343906110 565525453 194514062 253637348 92003588 334819745 444470112 572023675 692172670 334612793 370081121 736439396 80357776 280745044 385767499 577749711 301784582 683630984 13203532 788154336 765597811 862526488 302296330 685896059 358026270 409918384 467044515 75044703 695684607 578701910 846993767 331638962 511026668 117835570 897365175 117921537 849528544 848180152 410120249 299598517 473310842 764105503 555741393 815028080 648074025 497670630 671252106 339106904 420522436 76271396 310544912 899103244 86887661 324977118 992319274 213051712 866586475 449748024 316957681 172968973 678509975 373363341 920421806 690125024 671827946 513358916 720837285 781152966 619390932 775402721 800064028 643077558 558541851 423758923 579157527 743775282 795146377 554078672 866972392 693465902 858006174 156967090 272220096 497927430 826321976 295084119 561236051 553025823 709734069 547045046 42599627 572328668 110188518 854622891 187966888 434737803 542363891 62688292 793495370 622080817 509031225 905169534 230362620 373369773 571039032 175958721 369509927 76409951 295160551 846315941 698836645 273392307 556947736 761897285 9003365 108941141 57912494 388087450 199691537 781604279 812624374 161466511 609797079 203587199 596200820 758171214 566372076 487481683 222043046 266490356 920632444 890511380 758374367 470459092 589564245 354197066 387686647 903360435 637674127 710166318 726393514 401637099 189292530 388495791 403088675 175188664 7688979 77335279 159047007 872243642 117955599 831402547 306340028 551760486 541271270 808887696 136187468 119027242 442966728 739080087 496578549 321960279 653192715 960274468 408719938 636526132 723941846 361084232 13981287 554445884 632010886 266365921 888957249 87315432 397316366 208120266 946302076 168014157 176703410 560839113 856111315 373201021 489237868 89253134 619945719 573819220 920477659 119485869 993943462 809428358 694260667 133426196 353407831 378324529 612710396 667948345 100533711 20314179 799209423 218820762 216419439 209133138 362649764 91396394 91603740 465800331 699296181 512817016 475496228 420393505 561721198 816608316 147994865 387109542 941977540 480840675 645114184 698552578 46727721 261917993 770319462 170931681 72683711 651145514 331846684 717422261 511953856 525901426 335581222 90369547 619010048 86753262 675856133 939142849 816284909 374352376 26984351 877675839 648661599 388821016 432165467 577019515 447314436 857777058 769379841 285212958 818254561 645239037 235411697 871225466 774960310 446199020 695021734 940688553 552243349 723279545 376767365 690355259 932871482 12493089 470764271 859649828 284600154 8739288 104645136 743401225 361373708 239697688 713438795 766832548 72429448 69304521 759930762 984066576 246659364 11340926 726706988 241610927 74157186 566805850 123808276 388979661 779366437 2394369 986149974 868534248 927793763 832704167 72336234 236953354 850857041 588688293 565445253 711862939 724408419 293857364 734659189 99811817 340740335 366544522 492995165 292279872 61889412 696913737 726853666 866435280 727723626 502477078 258733810 946308796 261330371 541321939 890836190 839270071 717907908 576813322 200401714 145943502 512213361 406278563 990840791 592897676 864110153 783929355 481303142 876479566 734099415 757363288 541542716 664584182 377928244 846579832 657039874 608904216 971816582 860749837 848276214 779379424 442230522 930578371 572724209 431503695 150149495 123432723 810872497 718039443 16331737 412100006 60713186 946458835 200730596 477705276 918848191 143762922 364247919 350368538 127808188 371215115 914407473 49815216 279132215 567384329 980626805 739783827 246145568 157041621 975759003 911859121 215357074 769688068 314846123 84380995 747897334 454838571 104626830 845992319 170851637 741736671 83108723 344453724 786882968 571298964 765518108 406710886 898413326 916179687 152239761 633860273 859397891 74308677 929501871 790278489 269431669 86497785 842092052 595684812 215199709 745490802 362674171 188012494 325441566 449609985 413675149 973369536 116865424 667109434 680400277 222237708 645107330 343333804 363463387 1946824 778127125 598701230 715828943 665220118 574515596 886177764 166950222 477270288 597567073 847280945 847344990 318921547 463102046 790801404 281728225 264551262 466865810 830620632 185719741 168198886 458782710 643779485 647119406 268287210 194916944 404775822 955356358 926724532 328600532 501366608 419759203 455704730 877905147 801807509 998158221 880905272 899154614 61310936 310954115 893844938 509312662 864765088 887234121 920861076 109507545 930633797 192468683 496567195 840163946 692133829 851895462 322919031 701103049 267892453 428840448 781482063 48007069 780200224 866291336 879247894 942645278 318505011 374248057 792811195 638121576 393070771 353817894 190532394 885838593 872088339 162166581 148431726 863620944 810451978 795331525 866443362 75094799 21634880 5961865 522908354 348971192 29739429 592763025 803921286 866379927 524822798 740601969 445931038 561372455 124770358 504864519 935382395 894318245 888606597 375007602 347952366 469366884 687287187 710853451 956628662 602948145 487167412 27890576 895688276 662737679 584221669 102970949 651303147 326987412 384722820 690683272 122542413 675188880 616889113 383029910 487197138 825570915 347625675 432183721 335971556 212230283 831679641 19570182 232929246 890379639 585935323 369414036 710128159 635787402 673318234 819507068 643681547 26644913 937079228 119660523 761115329 518032653 671398058 161600078 98598882 865675172 353765506 820111342 452833237 906025643 199617927 548897833 407639168 617995421 754863177 896205558 242465490 947688255 725577177 139084647 189757732 808843512 523999362 43805278 1540671 144027292 448651876 683130162 766844632 192089584 795733315 331848378 400019563 212844823 38315578 356764057 51020507 275894810 390886342 500816329 470618769 182555942 772555560 815945336 435909562 697953682 698030012 922488253 348255339 822428016 854695684 403148634 295347197 701857606 89540304 448239122 131942583 57371689 917281003 26403918 550454447 968659812 527848366 662192418 675731481 802996665 776421396 422332451 62522104 230425046 887932391 423261719 187578680 770890539 68382133 797551972 551940789 433888974 125033174 703862422 650400577 643463363 523136209 684747606 2744716 753983771 854840636 278616182 904615527 196707015 957385601 874199259 67142675 957202058 487900735 302130307 491009753 63856714 495113817 214440189 424665611 57038669 755612888 409585404 785341176 629476924 412346738 894334728 85420096 411024647 127706734 795516155 517886135 583620766 696269832 974430642 648857273 331799226 55699630 23865201 219129733 37900933 248188798 302657289 348424387 334648509 488959227 963959410 575244125 353188791 383338084 844513370 906779025 210325720 128778542 772884249 943276055 884300673 159465761 275922947 41054937 249551498 479543698 389718830 195547654 423666911 203521114 401194475 959789020 751783157 720317961 234326432 848501345 812724095 264901845 431819624 667068848 193103249 203228593 910383237 972127643 923040509 371616550 548079054 430575672 194658454 470570966 51860589 764912042 528722992 243739512 736124806 470747612 15710694 502598774 834763076 110699439 814776484 708283657 972960309 273321938 489332659 662090850 807237762 112211430 97518996 7466510 733441452 20616914 251774250 644498115 315613257 105512781 421847203 643484350 767135219 76233129 598149381 388203915 744663484 687414498 866146724 872644863 744173682 42161623 849874666 421921331 46725071 823137128 787773159 839710009 808312602 563953393 409401583 86681771 510652997 327491239 496453606 778349828 330586127 255745544 9327392 152184291 474310552 490079565 59452099 105004035 733622256 438331495 218447375 24531170 168463115 919504268 454450608 574524879 840556277 510140142 878794011 557822514 151446679 577146666 312380078 64382330 649405790 867763908 531329003 365736575 405590646 636316116 224063638 244890004 891160264 466680258 596357101 638285527 357619969 236343758 624073939 154562049 515484651 212685173 229394360 947631593 720834046 432497814 306714453 973427749 465017711 75046455 802095479 61007749 959399351 802643527 890343656 138804468 677051799 497585338 650564676 172821633 381408173 690878004 526505456 622224659 973031163 848025102 557214601 257815734 343595954 508021222 140334169 397387046 646024164 539408412 959944797 917287576 194669093 714336226 690385321 904822321 368176353 955654932 326213376 947374955 432062228 139456229 153001624 95231238 484871969 733441651 396065679 127843168 424569521 446616990 812883721 380673199 643994906 988993445 806131074 648700586 392210152 173017416 801778077 807872258 993245913 774910620 412376031 488939561 906365703 387621783 599516376 293742831 139160608 267091168 413539582 1188501 667313064 814487476 756162677 212465176 223626351 597488409 623719810 441397088 837585996 441672951 782091902 252493074 261992668 708247602 890029787 731835925 39557274 545320499 759446018 980245676 90011856 197863295 248553673 679420065 168637493 26166873 151854886 752810513 560908937 346741573 744429412 387363095 759004840 450569633 623160125 66957287 548408358 849410427 829232792 628870543 608503671 132693331 851466357 46028084 401714685 807877182 429443010 809971188 743166722 9868090 38221969 712650596 14575076 251534600 159840326 905224855 726434117 6318952 127017944 993994588 970368618 830234955 185457435 211256103 591539673 284059680 657768965 114728230 262783329 77541354 721575104 583137849 821763535 191658844 123384324 380909583 287964646 431837250 86496321 84714587 97602482 574812640 883011024 754708212 830708719 54758007 401694220 918551152 745141295 7807132 177263995 741483232 643126416 384050229 250142965 333377064 327209607 729998982 858878643 412595519 774594401 642229188 387165508 768402022 520235142 279051088 744254424 61247398 624297952 842118484 214833365 981860134 722095265 428554054 606964477 485964847 487928681 477979181 146665582 575257067 792411106 756793706 544737021 970303826 379857649 895226095 225500969 494839110 22625170 356794690 841713875 474307410 573775047 929071497 641514663 633265222 472816134 14208225 201869624 658288946 762780296 524468723 588080901 133439039 364900403 742046503 669356554 283298269 713217158 360271115 9357189 853499558 178610802 849406081 702155155 881964454 675589717 232354599 780995419 500375061 713486054 841135674 802335525 526952347 947246625 859244244 909440526 951364627 766045735 557565892 422638423 148678354 362924898 30231052 818671603 938108591 692604281 517550508 780799833 34638637 456304344 133743975 719106709 668083661 799876 898026903 335432604 325757798 718916826 237131815 781236827 773452086 40640212 353510319 810898405 951762942 875623316 965580945 826176803 381063317 896325040 610875240 666713234 799427125 914349589 521576429 412739879 64794268 940940194 436581773 210014164 964539916 515156313 236043225 278903621 850763970 54619235 815807373 622775150 881837818 734921687 123743512 756597331 957738231 198928862 91957799 316708875 427575966 321778528 264693943 89861929 33151417 807880212 772525981 579919067 924015077 934727499 803718558 586261408 104672285 712397183 304148626 171583806 726810639 355724462 246226034 884558862 806446135 450717964 590066196 925022335 403256261 940690253 147127315 745592410 386020064 759662024 777513818 418317660 141394172 480231642 27069589 424182066 722456794 203884246 740597820 25901444 145941 69937434 28190698 215060993 920836871 784756781 531713053 371817613 211829262 95523771 85380093 292761882 140593259 13167568 760725148 403209148 409337706 59304117 641055508 371214826 453393597 578197358 395429711 853382649 804609338 694291467 923310197 283875584 781522845 894503292 28405655 235014548 701593708 100222738 397401892 888058203 508659780 792359961 158668163 805402827 447520304 858401388 417517885 645442190 550021718 478607646 517370132 321378925 193037324 250703724 863365819 60958515 988803047 67768316 90180579 378225194 385940369 149769206 156726927 99240083 855360055 715802602 156662925 333558302 980093966 220848162 710944852 258269788 634543129 268063356 16571124 39391251 956597566 55080919 354849437 288937196 420134614 48336035 431062912 743392288 796126604 848575745 286155830 787537618 711750056 402951169 510520025 881849009 181070152 425501964 597688087 22238892 612281134 224930206 434572824 748009258 63285498 564909739 216232232 398952214 364131071 746912516 574925533 647860229 10685946 534008870 366154218 982466037 605422290 252802673 252725579 173772622 608057579 920713174 422791047 319129863 757955118 684167901 471150710 956074783 884840569 211051848 479564166 694560866 533531530 672032613 568518681 523002524 815772063 587990382 102918189 520875983 225278629 838091104 681786038 93655271 594652634 765860194 135440177 581932258 798241419 19297943 908196728 250884330 87042292 190923610 391244272 296000865 803112581 106612478 724461673 243415820 197231890 646062954 944588234 671827301 764247794 628903750 253783483 371832154 793370781 998158320 554796522 330965757 294946384 961744971 640886013 779628751 56529608 560024094 819445504 129399357 875998228 233094177 609240334 110010032 879812275 792424472 810527154 440382829 83048358 753102458 818484327 590064917 725875803 731164438 997400142 473568130 581646488 96261671 840530473 299865539 281049217 69136230 999612735 200398173 161201948 681097001 396930498 187654535 776884662 320273613 250314048 304923528 27084462 153889560 923270934 686700594 55610022 843621220 584431599 882594007 289134849 28697120 241034261 470346465 328988367 151494000 391011767 910629318 716871644 370180422 877038615 562882321 954990897 316339002 576584694 512922108 972971344 348029346 111311580 359099060 884920224 159662348 404740079 498499366 494634972 497479182 140312567 638805977 737899525 280019960 10931125 937731435 406152497 122687703 638789046 912732725 604315828 996994866 751400281 61366684 382967140 381930845 103412433 73041684 690126529 953605828 979758398 874838700 77219609 576126324 877314524 253357833 95362471 242031473 113111194 848798593 92906609 162727920 670068609 947752366 588046025 67894303 499433913 327308072 743801525 77403105 898598544 426486378 580912131 49781246 267429896 904288215 734924831 797401084 543408113 907868709 756652273 895859958 910629587 188521960 575586873 650643732 199548905 944429054 274151563 677542282 244696302 247325168 259372755 805684245 850897278 952878928 451793194 480697334 46597877 750610430 293645374 138506786 368596875 831657252 802815672 246664412 974479414 479358961 686506214 19292596 371512253 802622232 848296050 281843182 963395226 955334716 961030298 968504289 379351718 346079767 349485804 530632097 762105011 281850351 792907081 796367027 579724503 313033216 966097457 992726666 227965670 481124541 220493915 41398752 922665152 434387451 290634165 159275832 888514632 563062967 432538241 931640009 505648222 901350163 918011361 731169032 260228084 158963580 642734946 851596569 584017151 497594706 55715213 241868505 321073561 852010937 850975516 127248986 683962951 813413358 412170334 407202546 907137503 598617960 857202185 32028076 394325855 204437113 130542669 624031922 275688893 906294223 793394941 747235152 519537625 459421054 680306280 298173176 973370640 365793067 878350838 274179246 58915351 675513458 734707810 278449726 139646344 417246145 80405426 255127413 207080973 910430644 746353949 578526937 941357956 273899212 621823885 440209226 550495379 910659516 463679472 74302946 302146480 541642319 37880639 252188211 953054176 853992142 12692839 894305571 661425387 362100086 928164943 489645002 24631825 770747253 7257646 465788297 258007603 558862166 231352716 917384826 183421290 397273848 437228096 320154249 516724743 355210997 841553773 937154053 633529329 778534498 616071485 576377370 390662944 848860418 873702789 789913187 989135921 479533366 607641163 632589595 208795836 307773667 18117040 123560571 605355612 662806863 955513575 267218131 952316183 613544963 435634012 258443892 124981095 259062894 262813809 293657025 57367571 251232948 455401621 585056475 759963873 730487856 913293337 52204982 715831536 663872500 507744787 227980498 761250767 293560093 294473850 500673505 338668381 728785399 950619429 939857109 844250770 728808183 210725382 211192328 85382092 942124347 650011996 260747667 358843766 42996333 35060906 133549087 923664296 610658556 364194775 787521165 456990920 149402301 117975180 174325740 75682968 107653014 657739369 849264617 444403928 263857462 171411952 800501033 648771174 743596728 452507279 56103380 744237962 518806940 874790858 797138053 641545178 641985220 513444308 135669476 837024457 91111500 300032309 465220452 789947327 317709163 755598046 89496625 965365057 644394933 407980969 835087658 804732809 699065416 674178009 164201996 384289082 749897152 814164222 631896072 596648370 794277463 618466207 447771412 411295649 98028819 87586895 759348753 600758400 718808426 901349263 373069591 695539347 124367099 874863977 746836433 234137738 227976834 95411123 144657506 100594734 509960718 940390941 925260408 634283498 854539603 769207321 325649929 667666271 522956051 206619529 784270926 944443281 233780274 588860333 693053089 490440287 903472227 439965951 197247301 609452884 431898154 372301800 519778585 729864911 993944211 219079490 608445170 879931011 736688131 991298114 392344530 462516873 910641009 929255913 112246907 705562215 859246997 87423921 273718869 738711662 771880801 838134610 584608468 825994927 173481161 679537551 554722291 415471708 389407717 867597541 617303784 784918515 569057735 838808775 745898831 514316748 153127665 125883602 608754401 909611452 645684242 280445739 489592071 751855415 480928108 475121213 935892679 748926623 885802416 866840801 337293836 409376441 404726110 981946539 330124930 278765683 75474065 693928723 344914712 52711078 209672740 904089941 362566535 895899875 256090046 678507396 323702260 83272364 872732549 707713108 582788537 49140642 72092285 767538372 42343232 738850045 568490900 742633370 51853896 845351389 464128240 998518517 764163241 897682572 115382490 24736522 671473382 636756747 488387191 567210318 850989628 475729405 547405498 939215105 657659394 602228702 280975047 625431359 829761101 224904668 15763134 46207281 53878394 156558838 637988199 256539076 496022795 620707158 284260861 773486754 524293254 922454199 21726453 74664926 851192229 103595497 499281854 581038178 765553757 753953171 958363001 495258524 764502606 370460262 643183962 463132205 667575389 406006078 675166977 447877317 494263795 164588196 475366273 441503719 163454660 339155257 955615387 576354219 602403756 578676277 86196007 85611219 830685182 218178243 659897085 853742735 474033135 44289572 589527101 425034022 47742536 936386542 915740694 561568888 85369472 210636049 836172916 48429233 757958841 281821475 372833733 74549939 100748680 24229689 324674447 370203036 635249298 285241757 292695521 238110175 587022643 693770279 728852049 5907304 892771284 695234743 645016942 914609106 289870690 855287460 190716321 612715820 505593441 411330336 825282101 821415985 721627058 670748072 674437663 743654919 112240187 117378785 151870711 903070703 757299753 979045153 887622802 956420651 405905673 896838903 999608549 521466088 397414770 879631997 99053948 908899508 666521216 833905936 591114608 774148620 534653441 781849115 245382517 986190684 723764650 111991005 747646397 692405465 892714897 954583714 152263521 450401849 75478191 639112191 305858539 371052757 563437918 268215002 914951424 949939391 225928357 407138552 697254860 514298014 594452223 776096536 934642286 258446187 532743979 624167616 946411384 981136418 650784753 570523316 320363325 607916562 628184748 137041365 319137468 552636948 727015858 237136391 520214692 848241428 57347274 458167319 367493514 21268240 515934317 358311797 158854977 513999842 860341105 829258508 850596654 333542174 495524518 465037562 655699952 530155944 991120094 974184640 88662388 626405577 586144641 213700291 416348801 736243104 537759085 21479037 367427083 933951810 558479093 460726835 379043233 590646879 278645859 271067444 993341865 289579748 787732727 710442916 708330209 138815737 291153889 955120598 995314741 622522410 83861284 500255633 201300401 37374130 782415640 838237517 862292515 258677385 93927643 940841850 123565917 492762654 777760654 405344668 226967561 966641912 176481534 819340540 198495927 808471387 635292332 813903877 829150507 498094564 790654918 229741807 718067636 578352632 892693740 359908661 400247836 936003389 13680725 294573380 742628341 384945301 266344018 706249347 152237159 197725104 864399301 387187582 233543253 989126561 666263337 471689398 233388862 845671002 808057573 168826622 91795793 496194036 107631261 237151545 650520547 195473441 279717594 350422683 266033366 788495113 587554207 151283861 86210398 884126031 63996811 35443064 621946178 909213130 778678514 344766515 968105674 535124376 35296375 851085725 476562046 630041485 103085894 654957076 284133688 604079905 291937324 855582734 842952600 146446548 957893768 319009408 82342487 716939942 767836120 773165871 728239991 837865647 238158374 363922902 816583510 338960284 912754428 43364661 218473407 711653373 264574667 614351017 264862222 617834465 93822088 893743019 599459197 993046802 317464900 367900063 534893906 364232242 75290632 412730418 778533892 904563177 493800336 304430751 594404782 761531271 471356945 513689665 105287882 178740256 971125562 784658244 168617062 721288891 919321411 338953631 564028763 341489401 891746184 804047038 499805077 367059275 37884071 803831784 734404089 62531218 528434282 515226146 640780376 577008119 292753260 741301127 598346046 899156759 920126905 258023129 290278568 329421876 560104052 882098432 238727930 615723089 884762902 961928338 899795078 158508797 198062337 690113195 949062138 596001721 307288995 800820446 34247672 67649540 789528250 995104857 576710040 733350567 734705847 558389724 735906381 861314631 225987647 238280386 25609390 541172154 395654203 937891553 920770899 133387904 207210535 956350716 918299418 820251173 836167426 925482340 729296071 817307561 169042091 763731931 946982761 255708852 599315904 408690167 279411198 459332549 87693911 82301896 364074474 30843224 293632660 388776793 28914012 778063336 879803729 827210791 21319829 588980551 709119438 580303760 739307365 999845484 907609558 696480371 494295597 229975149 613028726 261217451 356126153 575948611 790115426 231084772 322047495 359948356 35982432 488140084 194107861 267428524 816763106 714280820 294562900 215117539 19388124 990957562 374355337 830428212 668838222 497188302 659090464 535916018 499190051 331534001 314339235 519359437 523479735 683848505 254664519 966797823 503109453 462871806 161774477 219016080 3095639 368113931 407471706 913362089 653921230 717130537 641637634 199483960 502136037 421519797 601286331 819692614 136391057 3423307 680028590 160326734 229323170 544658649 490210082 983036315 666901826 557014527 388661328 375762068 731328274 631540075 399069719 277061173 169681707 344100663 872637533 225125606 774558447 126710183 986339387 61777157 315107201 903685067 631127967 178554920 302723148 146598991 509226450 836303030 514165467 12654146 54861413 282812842 527748049 99594711 46341820 385066941 541258547 725151648 742845107 651552521 814074711 828368996 584865384 43697958 810538929 316920360 244086216 473291061 3249822 61951959 565776069 962844908 220215425 503923176 706246933 900663925 518580773 952073916 257645652 87159907 891084099 164567756 813937400 721506505 178077283 786712505 200891416 354409089 616709798 597454617 72612531 848558079 598543986 148982442 138539977 128540210 401820086 468731311 807369105 850729738 984257777 597975991 929378640 731199354 153949620 638368613 709006373 856982670 417759850 524357815 648753852 69111030 954335295 364415672 659030079 382792749 671311036 617372708 991420620 463298233 918671485 939923947 970050867 295106506 117160801 148232702 355056144 832603575 607547286 768365204 821252308 139436421 207549983 199798385 644017604 757181013 305734644 891341370 265181919 497517162 140310910 835334899 173001798 438972839 890612256 170414449 865406875 42593709 525581557 371917541 521898794 584686913 438541756 159164312 3681605 97995489 738657079 602403948 715198074 84977394 761338032 805496077 408439333 80274399 283019870 798249910 765499393 229735677 718953590 267604281 334801007 651783324 423863684 157077233 13588868 905924699 149764439 731705219 636455435 709445411 559567750 849319895 141953711 969829916 505724240 87173308 735695758 229438379 2904493 992319047 369374134 693900617 34295958 486151700 568361465 612428622 815931062 867270909 179530871 466400068 835426192 713549052 895196006 193400220 908908837 563018278 775364659 819080817 779164324 186689240 332051740 623650737 554018152 858590743 615793867 824883166 496168294 122677699 432350254 869933531 181997785 707103969 443237752 419340530 480343175 293002058 104950249 859515917 50731635 680181343 320304569 645715938 868644226 91867748 525865986 803326670 952829458 574419363 2460413 929519347 317203934 528496884 181334501 961031114 267434218 618097975 72270874 722469644 704720738 802716231 162419399 389604203 609610796 127228355 725853522 153122317 184044328 235679541 846253619 105565496 982417830 202522707 107162625 9898805 11451955 881116893 465254174 196890342 299158168 610957106 535632470 424434943 481199613 151935127 920354950 842846632 542457568 187697280 920975543 293838079 591614415 394552145 92718588 844458848 81706208 423287828 276823384 313596829 196374072 618550880 853674117 372945424 709769676 726335774 86331336 974911612 295009666 234641032 351074252 841061747 580567675 992612763 307163488 746558681 120798043 315935996 346125986 303916526 734587773 241628400 774517463 194161126 622250701 21034606 419112434 313201306 738324578 683627985 300819902 768428852 544689779 919963852 26262873 174016309 883151571 466103068 826906292 915655071 517129309 782597936 421251266 708850187 713118697 634600928 649617426 419399072 128086473 937034973 372422985 604691052 635605424 301483166 621732041 288683492 237949195 737584693 806654829 941905994 881855692 446243077 13062204 564669927 123979678 257031702 345746227 401420469 722359193 555833455 651120021 68472953 7701616 140415830 673779826 742184951 222192768 720306524 153370191 856419296 999073660 69199641 558457572 315715753 662918904 786963596 422877499 381389247 970773868 196008596 363825254 476143092 832768428 550839235 300234854 692037578 66644076 257722320 623027402 223505088 493183619 366843055 896057939 826609206 364750488 510826927 717654568 439525111 555331176 493175935 732269626 267069750 684671495 907367892 618000097 282536946 491332804 653950448 290372041 337855907 571662555 895166473 435683323 39923594 995914397 260535294 969959039 729464528 487792991 886436888 512619608 600503701 659854891 314527888 561281976 682904239 160413016 198345852 745750770 529661934 883726523 380130557 199829173 317218775 48632431 822816035 1498788 334067057 41211944 321602812 844937222 594351527 342851489 313724069 776943434 655188254 919876109 891517757 768627642 525900798 286119542 250202516 757946677 378687957 142192349 122424900 152698331 233221244 299327771 352559336 605154185 483256536 684647969 224693557 724812784 793533396 302930080 680425502 595107324 554207726 546362415 274395614 493343571 734804147 170737587 582774464 154684527 101999098 649046377 947943300 844247455 169608094 418458750 146329039 178630992 773894877 152149943 65844974 528412662 462586691 575722042 329574269 541191797 720770108 195899326 762523030 766669964 111284298 591750513 262973107 412361124 770053673 812598435 991139604 336516791 161948429 481926789 743824847 479668320 375306940 500252444 7861385 325482618 424733193 209907009 184458548 630794812 344182069 61884535 998872003 495436954 458505660 617481693 984116425 978108820 347839412 562872901 730986195 906512339 299960374 733771744 263845116 633184595 283778609 586784929 71268152 255891185 195559364 195707830 351637992 354031800 888879231 163302171 493336087 165045466 87119170 929432125 796738962 869715115 657954507 157745518 815438973 900212919 74360195 338775201 218536331 324367993 748668458 17692816 193246627 954843268 913185250 820543618 850626785 703632841 641508186 959214346 719170604 28396515 641194672 220006281 647581131 389868081 386973166 732575184 827002165 878697358 192250666 487171398 623457993 137879900 99840739 431029764 980021978 649291813 677703071 200342025 66661632 322606125 392130321 997676271 591285549 446154592 222994930 140042699 502705644 439303208 939769570 866541293 400814396 441122070 50405908 991455724 46775039 17671840 681996152 214251392 26012934 415745807 487372818 814784960 179571037 496367445 347661828 821825118 678556390 556315256 398008893 831039931 951035719 953171461 631183656 823674459 875620418 228565794 725824416 517184502 863578760 769776671 355670498 384756632 351326958 552384103 353160695 150811409 592681099 404593448 152594806 974276674 752776806 156737368 907386651 798824475 168388696 894343131 878636052 435338661 928874315 311132206 637854826 307765592 6405866 925420020 21014694 88735891 16155081 486807101 979810313 48703067 984328396 438004398 332945221 85299313 500717951 138005637 250347512 168158482 950805494 736738298 928202097 42152083 767647494 256866589 449303797 271536489 171259586 160239621 475094265 322730695 846379946 153093987 326402836 268619599 857647681 367959793 393702973 540257715 105134678 951877602 108142071 493896642 511973578 701612001 392368328 186085891 413253428 476458114 486726938 509033156 34580823 43104091 909205194 798361295 777815954 615967127 459895927 326098404 161868330 30424142 410922819 9133731 930481145 969485491 503875386 199524649 819632058 136373493 391628332 318278856 855754747 117457318 634124734 535545951 424463676 82601776 157185756 620626680 255251658 638041687 647560201 650120759 827686662 146371607 24554124 632061983 683257523 140529352 971210436 285954085 255742840 100617406 79638904 477030487 120240208 562169657 172897355 10908518 833991863 271471079 719300584 918745718 765574981 320183332 752599214 72648566 792179689 112658170 31645531 959707450 181317988 411840080 106470078 780023427 746024199 837847172 760920580 246509179 520730749 699664588 331200445 371650843 458049642 293495105 763350521 117427677 920398849 832196019 324105300 396975609 750207533 77131258 967915250 786179066 108550962 213372901 530163191 995225301 984509285 214864277 946997319 379419083 329936880 722696733 481934825 914520869 607839394 770828651 432572040 661847471 2875791 447212870 147429480 635805504 719119020 117236225 21351045 944258104 779982500 666882803 330363216 139113338 84975025 381108010 704560808 967750400 676069469 291227972 991431737 16451760 588673229 388613028 440291452 356462920 830881954 577298743 340915947 382184606 9479354 244254341 804224072 736586037 413156759 429451795 627193751 149084944 767942072 632317240 415632255 285584999 796233177 524471352 887784912 318622687 778399147 942435574 168179006 847154482 609737209 420049979 402254184 33197892 417339589 690876638 797171656 560413620 196725765 787793899 760159550 730408920 843010393 673094597 140801019 58563035 195081014 385290934 831056136 669987917 26127255 798231726 167245340 301140031 166330048 155016346 539573348 646137059 906787247 193734891 311914747 854619910 540801070 830200380 929203283 608149969 861022317 141119705 997513612 718093945 629067198 516200797 926088801 622188009 271409252 758559610 1506387 352309695 239180044 980639098 553508940 59580194 740364822 63451715 926669257 73448299 576114818 248756336 391206785 745594058 444183816 264403515 652958106 202310612 189397640 530913649 675299573 107859432 752210616 938486489 272039663 503511579 532500866 594353857 654654306 863609468 385603433 308995779 198488632 963565794 787681642 823117222 740057862 29964135 45395889 833224374 498780162 870032868 229508745 615235500 453950662 568132610 638291459 795887282 270843796 533169383 594980535 351709307 493517147 887113924 627225012 138150463 978921826 773006443 534424494 356525496 383322159 977845232 696355117 156517158 815953474 883135034 695313957 158688883 531175510 765038633 9194297 955715173 419975635 943936459 68988912 290404353 775165904 871096001 488823087 784994313 872788292 281751559 652302834 403953680 917487395 650267034 201176105 292129958 183968609 603086046 274868689 895068382 685906205 53180134 603590404 482477164 746988844 231678683 876095589 641862077 374955563 933979052 789314109 294060387 4297485 853295234 379587909 968689958 734740012 51502639 273734572 499198725 16879331 410326085 666226230 486914274 955676069 482031683 270038228 9258114 782366257 335621752 469918509 882664924 173405290 660996825 570425038 486147173 775189813 810285118 585612019 823544719 650139040 845882195 533660342 75566942 937114563 646998648 642239039 696025686 925304585 307706204 348551383 264719738 368064197 876112973 472168556 497109129 458984740 200735007 155426836 494768972 601916413 913287343 27135764 625908017 579115475 734721566 103808571 93265010 48341556 924274221 863955545 896600945 864490289 418889984 484011026 102590609 317542568 573590501 188487271 457363707 847935540 195308729 879273923 773631807 153516331 142798582 749738243 387562422 327222999 628641426 372215767 221750666 630084771 899181802 807121640 547391383 417781797 960431462 369040250 506256068 429062269 806570576 805260450 302652565 246148156 516528346 436251117 37916047 523857293 301288933 216967967 848531630 968482204 160778516 892281779 532654700 498914499 116861308 578436763 990726946 660465577 704405545 186938114 112499011 955070462 613677130 918659336 227072248 608217850 52496747 583449890 868979749 365070091 42191917 941907863 883369161 86014040 281476345 329919131 120368991 124509712 406567456 285612217 257810618 104891433 968468143 846085865 846904605 365849980 911494462 455179653 559943314 507163092 561544917 464871126 961207796 237260883 865022172 681115698 147789183 571099917 944105250 96708985 127742672 467886360 882593081 563562351 913265496 340673871 710479940 185349332 211163926 3956565 235550064 282810516 438410100 882941275 546665818 453665474 792233091 918628740 659072838 410021095 429114137 69255570 940195809 806017796 155867015 50905376 660016604 474343443 844473355 161477833 998644507 769314242 557393105 358196214 516644113 921800685 214525613 83330387 87917582 49166157 553920789 918008061 756839996 439916400 783047184 304630011 754306434 59806999 670670281 920651516 645492482 113420051 994467801 769998458 674457139 136088970 65745165 989409181 494794328 899026537 549760130 886144827 120295827 887693738 236374042 830589375 747363775 870537220 900018068 617650999 347688625 853929813 235686690 796952530 829044646 695908950 794154088 804336116 429095633 429451529 611405011 523922014 195807239 255995413 965563889 570134615 325952639 352838383 200199978 885797800 272626083 477143876 992643791 106059309 550591634 94527056 255037886 421750681 764981321 77649699 855312280 478586095 325803915 779666744 768481041 332417187 545386121 203678110 886196051 966098901 890739715 908950167 843910320 329043952 963043116 371284235 668761201 539986812 723045038 753530098 158460951 99989201 187738857 301201306 328128105 858443452 535027127 305610900 103484349 990983160 397441354 592810442 501208412 553682996 987308890 914455734 525591804 796379786 670503544 865699036 670657893 403831803 61429270 659541405 902880713 476576229 566595403 542823351 404157634 24511265 787436312 439862128 822957178 324821670 718064321 245537508 19692316 274901036 682049028 45040990 849935329 894849110 551405289 241895560 570409274 258972663 270131573 684311438 841525721 356653038 133309225 938358798 203845090 515901822 713174290 511217027 928082308 817328429 104316687 414608617 307617967 367146666 173936200 975817152 12275052 151499039 19440813 537275496 443278474 879822013 309934390 559822301 683147880 178308205 103581835 561526385 418879569 540875891 312143497 154342493 279650731 551628099 364569066 406029428 426229947 45253176 448956005 664854103 958791909 336824612 119915441 395235486 188452689 744200218 240347271 883212037 68312515 357029435 351198307 474420850 83312706 680551848 451054547 412405090 161908632 644498403 89146707 298926349 261243870 170563168 421679769 825714829 715603997 181584085 62694241 788563996 959074594 856946316 7400382 890952113 153721109 85875166 198922401 791333792 382420501 58245053 387781609 664302805 4411452 699298948 939372417 217971523 691549938 285488853 327038567 865670670 264069417 938588485 266221704 790032570 53473341 586512819 293653082 285581313 175341117 667458968 339938490 487224852 545739389 164648977 101854505 14206557 601239110 835723868 92499879 811453004 809926065 724531345 358455009 346651770 540712194 715234226 308171886 68953512 130681833 730919631 485282298 310124159 609452664 278357493 469674540 477237113 958072357 231347334 995239083 980917002 351576493 874371216 168774178 684639538 74331452 389916184 106306975 14650251 535282148 622996529 445178314 625494964 333826052 768573213 95220624 569750310 502378122 597304093 386662428 824865312 879412563 476407204 654342603 161837496 55859849 59545978 67026284 823872041 117687406 131084550 219004456 142546570 955443191 77939288 556812970 493398044 608145355 126170112 571577934 280727008 628823344 189651233 542915210 272214463 939890766 887359439 672014774 176466174 219233566 398322429 594401508 145979884 287223406 763211332 553486916 997798917 507704871 627085597 78144484 781176074 842231880 847291089 284506941 662749177 482066111 632947389 307423308 687204004 322837064 623926592 294328689 753667665 386165691 430086012 659818758 497601616 330664651 302995927 396290497 634359327 340823132 251160174 707548785 948763539 629092875 751708255 945172867 253472936 426301731 566809155 701975211 18647433 948295524 303964903 748702849 331662812 679758661 257346789 422803227 539478516 216239049 263213089 41839780 355020045 529132158 914663348 279002137 111458387 32745161 51105211 383366700 39883549 209639386 798770335 854141191 51816531 211287797 101334995 417939839 702999206 620812315 974584163 551406547 55461880 758791571 655838657 714029991 364467272 55118776 462751029 887381163 131333528 607957435 253700825 844351053 747661511 597805305 205371268 374270330 752912539 973294947 303921929 60158202 666586723 813409938 410566831 39046726 516432300 484783217 541731388 265485843 687178413 659238181 356980499 948180621 532327048 23297676 257630281 225700793 961910606 596537038 608369062 427106775 132090720 359784680 595225004 930401121 107051591 606332532 317945369 247946809 614528556 639584743 341883007 252741432 354058337 303334477 540883640 85904053 792242687 359763472 825643043 776869227 887278045 967370053 37752328 417222304 31185602 320204262 643914416 499329782 89212187 64353437 398084530 581303402 869311594 375718396 579813614 446355859 437714213 417945218 480239044 138469298 878428602 962933930 787585021 261378718 720269819 290309782 152894607 993011537 818205304 457985802 706294425 760450478 30580183 165303817 642621208 106158011 665976081 923336827 315489823 203493019 789455238 588783070 693103239 96652959 978176299 902455047 861415968 118405795 870231197 767759489 17352251 119008749 398765688 990701431 232381382 570644892 384092593 371915322 255563315 115172190 544965490 925907300 853002702 189688103 964334936 279156256 886356749 40408859 719274386 414003688 561841184 650407858 495214643 371086225 693499630 504770597 853469178 225914575 584341140 659884631 335069755 362053783 130841141 61478910 638428966 804678658 856581314 867189456 610377294 759772846 247791438 702404520 792176575 780173230 659144487 156370655 200387725 124539099 931243209 832152377 712019409 428438556 169531270 181340111 367542758 930031115 758815515 868415476 156250000 237943648 471107531 921254188 592157100 272155266 329767636 102314217 33115566 409044377 553163750 49844616 591577435 456734586 990477798 321047508 522845694 238356880 42313103 737960125 420608564 580943112 47754180 238767934 836925937 191881317 508411753 276735040 636670722 383176889 883364632 712400872 106562167 755045761 8379099 493862396 371648075 121522454 553164071 99136037 112320235 5088507 759195142 100161459 427871508 662498083 748203292 33241845 848285085 53114592 873166484 771204781 249073680 959712075 220120277 67617865 119780343 767356464 37466430 891871660 962036677 941096754 455496919 946622546 34953300 549353692 465646402 288312117 607118463 427601498 560929825 633688233 778274424 966029706 500218712 782012276 699245241 899187581 931743451 455941815 500064484 85676391 128942501 711476092 512291529 169810064 790864806 860733194 157723166 929167839 128574823 593534935 437873090 104785162 281566794 297410263 758354797 845297474 86513825 432132377 932801128 704550194 558479994 772264837 464560635 759054272 224167666 741518963 272679564 518178129 709848989 480052995 534733229 626397026 336274954 357784904 479159008 886398040 902393284 354611950 312196052 704975931 219966582 670830288 622877059 539061493 655047678 754119092 900231741 776731518 953932850 683038507 615945542 807121556 599830748 119265578 633367726 100398289 467325125 329463513 988482119 274258387 76746775 476817748 314600229 935820217 694880051 876953223 103293804 903449874 911982517 558042486 62895565 176178218 235816818 860648398 79496873 12688938 699820186 164875390 592623237 873074208 695366156 919857552 365187328 583591239 358036139 967714193 430056841 790896479 855958658 291351008 817028465 566391672 939471699 17224031 399523436 305979560 802499210 377515072 253120003 883196200 809024108 288823655 311255464 532656112 934847003 414052073 760248283 823399253 379946380 976924673 519644108 181482965 503355822 377867236 683453596 467250811 100167329 623519346 177504538 797651880 574606288 151917772 407363251 362005078 328124803 760963143 674059683 161695800 34185546 690528015 67533099 164135528 881309416 44943732 740766874 809460635 989572851 42631411 555808660 563497013 695922188 641209301 424409775 562039940 741793177 728825143 861944794 80790481 724616120 837137438 469278886 246058203 220680410 182262994 340669518 303415117 993189875 143026342 782229880 136719927 978497375 805221091 945528123 795635694 984918380 120608931 507632103 703393805 929152367 185231143 27147036 294269011 978800967 836437174 874141724 922582606 636394178 928752213 396929326 387080539 443447392 979682093 756021209 99510360 768885994 455537223 152159265 289072158 990150967 30875528 901556346 911061124 783821077 393160385 833210634 462911298 878266677 824852238 367602139 185507019 625124086 676975391 540488925 391963687 789570919 947850899 846145102 952963832 247700056 739162652 231381779 13405948 434669452 235112505 367350351 501166704 836648325 409510463 867626989 56297320 756227410 908625291 268669384 398056374 15874266 925376394 180212536 97175798 444683457 248225664 415397258 979790661 71923807 974803931 791102614 427516735 196094636 571370732 426275607 927686573 439843381 346417796 620320040 15091828 706194280 954830285 333217940 709922871 577484919 282378843 527187957 969574902 981374435 377804904 408175159 959026048 585708313 718333639 466958492 350470789 348781287 750975953 306138054 338151462 226810425 850687663 360721977 310128937 659878471 730184939 633033708 995455324 643056937 42868983 62900522 125975267 676433739 950037748 521849896 816534845 174379906 944779489 694074507 824470902 327090803 244129798 506512318 755818773 928388805 846797120 982560036 486317683 695901049 894259783 325912959 188728509 394906113 326746993 360367514 18451961 246123511 357653076 162867537 421199802 820711894 471572554 121349240 212035072 42999801 96049644 188109141 604126373 68781042 143460845 349978066 357999186 646107928 151533009 330517349 398830811 934719688 568902347 458587404 801551354 461984629 508024203 494436828 41271353 520676774 63389790 316848602 535556019 90681829 634636634 414264512 762594433 842931385 44227117 807361181 894158177 590330466 382056236 734190027 574531618 977866335 306085597 812892369 851946007 521797082 180052091 418762428 530071446 312300046 513685420 337921428 156706077 587863638 571098972 807326736 95734673 473920790 886019524 532541699 367004613 442139829 527825064 756837799 469738215 561545396 830743448 606851900 371378094 609410150 864472059 798376136 933187972 231340147 372770300 663691187 946824911 119364 329326065 539271502 976557844 853008861 406344100 70648592 192931554 272164516 966532106 71996195 792195888 414072800 979900632 612797762 219472711 979425207 740388872 845993776 180401487 306068951 628292629 362134321 95874716 554196427 971280855 547875459 667343937 404992180 163342086 470232670 971251656 21482493 938791143 766115422 415541846 694590993 388049265 811912459 593305938 564991206 909298489 208376165 397735609 799548303 752175142 284064597 958666896 577680640 89500715 113388574 981512423 472647378 905550696 207900672 365596586 629207073 693087576 341416642 582114513 634271259 210567370 287405743 216557390 891602495 708007009 178713022 34283335 875510152 528959696 918492435 133639275 837955563 984191533 98688028 645701509 190170709 355841352 333295515 519404466 886383775 697720319 664712455 891419086 286732723 438107649 412518639 483663873 970260699 37901839 203472425 193896756 270121666 498315374 16295926 961920283 762304116 238718973 994312477 916721835 418824722 817459802 25661636 863632060 723756672 56058244 525160124 712721033 158522167 825777126 609270331 859089518 140155408 911962668 164126232 745318496 554429251 711087216 990646472 895442890 223474342 670829350 924919776 470247231 546034094 873125403 384822272 115231920 833681059 165807418 117690459 576396147 858493040 68278656 149387351 285925674 988730716 240207669 767559437 293936655 864937800 143725271 61359212 289374677 333098115 721629637 683110998 245845724 118009069 719909629 950928310 857339013 923986681 138355061 350592356 186047008 229506933 459215416 531618413 704527749 725198588 284210694 152830506 473630975 676523254 851212073 749509989 648032208 409885691 314906589 45404964 337531521 700874131 353102705 369978313 743207855 967162796 200861903 229965670 79092082 827113106 84176673 589088763 543565362 528253379 523445999 718539201 904618873 664592738 202233992 743652235 708728481 546621650 709405518 648327336 118352926 880668285 929051585 780338548 486879644 117715960 551227468 35273249 127889407 569209753 595546965 253358773 971668774 424862988 674869190 201019778 926980128 251061943 766329380 549967168 987456401 820917785 572872389 781186650 770903225 61570578 273399461 938841319 774368442 896091172 564080557 535306028 791456384 157912995 468532571 552300049 539121220 808523453 612476077 234740727 446105820 386239033 366874769 474538430 33370432 66956868 147781835 742937461 20421972 36849513 253867279 721794247 931229321 106657091 163465782 561341743 176049683 42905657 744142897 978714615 784100515 168045451 776122361 644724760 714779887 29876751 102346610 51515320 543472809 333537183 450536225 296539430 24604049 810960569 251315976 67641569 499780913 786194418 626476126 726544971 740048349 352595331 20414655 218692939 73728771 715431519 186989260 989821024 528848740 350038642 789580556 280380958 223551092 433467246 859111941 420223341 988214907 899011617 187093537 512351248 73271599 529530799 849045825 587624578 768453167 6250405 795126972 629153428 560234548 457460796 216645405 854503388 217816033 513325226 53661699 145871471 924060515 642944407 467653134 488295052 527892730 778718809 321310182 291896263 609514764 63109459 295126011 416622913 30160228 245353875 904028086 330370856 748982898 124808382 641607771 397892407 428273945 260726871 353851065 806720684 398164643 401909379 901552751 36237289 608516778 312037192 363526604 59389018 436683742 271528222 278133115 846289335 604387052 298100035 411638412 64308846 600404900 522584334 559995085 506830786 741145831 476994036 871796019 626486198 244548168 925974565 666111387 363995176 242360385 126619938 333690737 753611346 553338308 699636489 615558528 448567229 416734487 687242693 492008124 703968373 483007925 182683531 338403555 347703133 725658471 949627798 185321220 462020750 478411867 27974377 569449673 175677632 915208249 497358226 259474120 209344565 295696616 153233572 576721844 845358726 492662176 580961663 870055035 271992771 451316714 267078485 624553210 284554414 580171469 302708257 846750613 702614278 43030776 785416484 850359275 237793556 144012373 788919819 132820492 599177556 674568249 306746059 696677880 557618031 532745617 551245015 67373977 998887935 434333144 267629051 268482289 788179360 8622374 886835440 509063110 620928474 453389249 721277677 697830281 310385410 836841956 649328536 110977948 815743776 581083681 999937462 178567517 542033066 6257656 82342308 275054571 378084777 883807906 871563724 831653281 868946951 178355014 585392916 372363843 696249591 5537115 281816853 624889150 447984473 156326574 530220714 328409765 639977019 417317586 550423725 371613658 237784981 844971729 268932105 339742921 539012080 938288652 645528713 346307376 72135279 776256161 729468767 319133044 5840956 920083218 67738491 25316618 368788505 515463770 227732616 763960451 633168860 592310969 218239724 864152127 129992275 529971376 248631716 706093362 735320444 937006898 79773873 382305174 300063802 952807258 970631088 339424305 969620434 238386093 808462427 974220632 716534956 244629608 189288048 392173926 696537222 44438693 714518402 506694156 7393633 815382616 515416048 594429551 227851299 393317007 635152057 950481715 55720003 81306246 481826994 126670954 292844698 621962353 184854246 153493528 944153158 966883111 791577277 467876057 284207749 992856127 973342139 1148422 505531973 368885189 424991456 166038834 645600874 906711381 466048453 384462536 792789242 991179179 225769240 115186944 886996587 745506922 165584336 890956730 758524727 611686940 699349038 220386494 513902835 741611233 719677222 306839303 643702068 391693187 620555309 166764196 7213475 587662961 160957735 794181129 404723302 396823366 141547295 305776005 797785048 307246233 712544305 868490603 20278703 344572498 374759703 948191894 683899965 418697329 592053025 549338062 766075877 663862283 154218050 157928543 528854208 685192024 804924975 856961921 42722084 718471996 518598834 792293933 680301693 613126621 462201957 837665078 877577346 705283630 530615313 822569527 101605800 158578366 473278186 136317186 38222331 60217797 355986141 218855499 138216887 28109351 927832467 588074910 53300607 314980742 503526667 882468361 56987204 828843800 360366387 384345604 167860735 549046540 469872107 515971271 530470274 902947889 536423058 390350777 251922303 970539924 185293948 573675944 289536061 630423882 62865609 547666694 463324435 582226677 445559240 864388185 835215738 552073050 904062411 119300966 115944755 100713278 958899373 791624366 48404608 955502124 635393953 851743676 707813593 98306129 308314012 264825707 617890390 997398188 477195521 729757374 883504061 318587645 613873842 680743152 206138728 881956920 808282355 570173701 771341648 283877759 248462441 236743990 983294270 161322957 648871161 933877605 670183824 164041173 754774758 970447574 457438892 229012693 649628364 598996283 193011524 467835920 780638127 956071086 33434552 583638417 308256157 658028568 336306085 370247428 582228255 531455379 160633014 779149963 335041763 746587149 131805234 857452881 221357704 238323087 516275312 55566398 982993949 672328762 216833848 993332427 795189166 588631503 973305049 506643878 453337276 212169242 687293449 147415607 564770406 451862834 427316898 213903049 791221324 912840483 516721649 427288572 764191401 52903697 701773109 430941375 789559931 631605900 127535835 90084418 41236085 348050951 415751634 231535732 364747146 912657643 358687089 232841568 196083803 166279188 416731517 769105931 729762205 611102568 643803382 838915326 995676323 858046881 863261450 177853103 389778969 536619445 488168466 62988925 843197904 187062675 872437271 491686289 13430187 936351306 231908656 657900112 161840209 19796899 332977704 493337508 413371224 758051289 135380887 274849777 972737531 859614640 850920610 479390776 692610029 261909075 701778364 392473423 88324657 346011233 577756511 803030346 191337935 688149585 156757237 16806129 537900151 612595379 74573166 175422046 99732549 385121031 882895766 132474016 21173468 188680710 493103227 700948786 624185333 199464007 62600218 664685568 704464592 587843700 161054526 82582226 601198113 544945027 440569861 939377507 933928934 933201305 221688048 796143825 914095225 958750453 641365585 430163580 820860335 950729756 968448169 87064971 540579101 982471246 820281765 527971323 916233312 266564386 776158791 506354393 772117237 170154127 194469543 125934874 462582268 508126595 612190096 421021943 603084881 769645232 350030933 302180918 132001161 483920314 108430261 725410131 162093223 98709437 638705878 444776887 634279602 467449446 744815017 338275845 504301299 326935681 645759576 336235067 611503812 209763393 866356459 962669189 124860540 817424379 746241551 880140898 941297369 832761499 913521478 845217760 230142253 364895370 232707520 62367640 979235176 416264002 362994113 258334112 588804208 807216664 683874620 727396678 209895876 693049599 524236037 373652103 471798995 927511085 759122148 172338059 24874008 444641023 931388859 552086428 106352526 694833531 953128136 713672014 503873154 362268419 432448579 820904104 587785297 208757569 907581058 640802545 353070060 441988720 942267022 804870111 336840027 875613357 659445097 233579271 611925501 414687964 237229384 850411650 634539910 742554196 447195355 265669215 230195502 4439769 574718900 155041756 200582226 21042100 339369895 292211246 91126973 613274906 48611153 10589221 584561210 128961598 314463774 684795204 537506512 202684188 884363580 445366639 492308848 910047865 964089371 990594658 197484034 462864276 854528615 867366030 717056437 882310812 377781509 381201499 324148194 86034491 896022150 855512871 123425073 954414044 68979387 51733292 361271541 164183467 327674415 945499362 707490495 335546285 231234820 251329925 729561255 734505 367575526 962953219 71927185 504532058 721921618 169443821 5484117 220263082 775762404 169228320 13606164 860837530 47999495 136402725 803591542 54751231 344835987 85627068 828083350 365683008 475436092 752609056 968039121 390166923 70347134 815088954 595233497 272634413 959716998 269105950 164010880 388304800 714821902 487537097 627316113 497663637 29696537 631261689 819173793 862985979 279146456 865595308 729142318 990010711 44678218 181704717 606975089 800849319 660825889 610349857 455347871 566329453 135149629 881866056 437597347 157397344 199333420 382811764 189409007 923566 779297417 790489301 322197935 186934969 500545031 443559822 933227916 135343095 955807629 954934234 360307591 839521543 309030800 349678315 102643446 726126822 847247651 361577223 647242237 183655394 133371219 206250323 995789522 474508759 312491887 664521037 962144330 354893096 420639761 362490522 33270896 897787285 209349944 903642630 107079024 982734423 648599386 188899310 916364814 18485905 241347357 286887035 932056647 603929869 512921659 156333877 701960557 42547289 982171702 344052288 45468680 745575544 514314919 473747104 907037549 818613661 449002576 636820950 769470307 185255422 896994146 108475091 695055768 51519819 644238766 530526275 249087371 542035375 372735140 427609989 973216618 157600274 467107790 627968254 199673909 746318417 524602608 495783757 266584606 172592772 295567954 646179584 768457189 377133296 182716934 812038513 606996851 788758862 609460301 181972220 856734455 892893507 134960080 956883751 745294603 624059995 608847944 964810035 320291848 891816930 624087566 171952590 969973045 549681108 100560873 68632998 113732372 744559198 445284342 334890450 732954324 339622911 224654832 673882065 428858679 308940243 132570649 53007913 420993574 355240136 215423993 675440509 411890966 374432146 93318428 330178897 235001601 153958478 596097321 780492943 687903890 156985953 36607971 67197062 415622532 532767028 159307049 61095542 83819515 193545485 393731686 810451739 540312307 408995299 736872585 919446493 482584874 558513959 310905550 881740714 624131113 272979102 880368348 257396832 140007835 328388032 858960253 459093874 968948957 600871803 357991513 70458371 488025131 796887164 571786782 596194514 393071600 655990955 210499523 539589722 179084376 183114375 252632799 869656078 186731231 380065639 262047887 198711137 187350226 514483418 749123457 221052490 3469614 684791302 280321278 597034756 403192921 742834738 905240186 385466750 127671092 898587988 994382824 278262018 739582950 308959642 394260844 327205468 81651441 853894842 169223426 213100580 44926790 320172021 468203952 753149383 324079358 554396315 315522762 78421975 205416756 736681882 184115494 739125658 105728422 392651434 667661407 493798807 328618416 446973084 691420273 361645438 564981889 608385382 714725173 620095871 55559775 789934166 82981235 26497480 908648676 637870857 756741611 478512951 642775684 887579047 997643809 835602262 970756621 416639117 20362270 201441320 64644329 478306530 262627840 599975702 495361677 817690426 960385944 238310052 924931134 398687284 660912181 52961348 208989450 402993760 513075383 628427247 589111338 861073156 463395431 639426485 293254025 690598526 775787671 703748715 145489300 514461445 320154281 752175407 323575504 447198157 202561801 344099655 67459194 98890692 284337368 427072798 894893912 578824594 583618169 508120125 789760487 16001105 424947435 232532256 162902787 764166743 140428717 958395018 940429529 4926407 849906356 300006178 609492957 335267978 908234299 989907708 403122628 563316361 530155361 381421557 73991174 720248216 338576525 810976876 430836241 199555955 505111020 738628356 782451477 318346083 738696888 929719179 774841933 935490969 104236396 822048517 760119024 699428497 606617375 125270498 185656852 977541039 124906376 53672337 971206930 8141667 19953835 266764248 371932753 708252505 442221817 254689042 487775982 17875502 179913656 698179916 967277003 381399292 274437250 827550797 202508794 434078136 395388690 850277598 658673430 917060406 977719262 549436505 420946849 385939822 900151353 395905555 46005801 981162423 42667240 147948578 600522055 64090337 87278215 542972514 334546921 828942236 377491012 777838835 42595255 756182459 171912878 186707651 921838590 879424987 991632370 441204415 897817179 417982563 215865543 316900820 337027142 11363649 538738717 58416442 58600647 717289945 951267583 757632972 836634215 250177173 793040435 85146214 145892186 217813761 167771509 762800248 800448575 683152323 330300433 362435681 696920441 819112243 658245428 884865921 426409210 240341444 32753156 88908894 573161926 148762780 901069850 781920454 396761519 931862537 668296697 994843705 177737631 209823561 254641747 396636185 419897956 220888936 773907 580624637 135232238 486748632 236279516 540874222 282182277 477542181 555081704 466702230 26338323 191819450 761305139 447280525 525797593 174612722 653739972 239516204 117324070 335111070 515771186 284694573 998518613 715840736 716786287 791002377 837506177 194409169 306035055 976098268 672993903 983291851 288123355 284468559 675732350 269036046 476293736 797908953 710216039 778014939 367964077 942940741 817157713 760364104 720632793 937377352 523457527 244756033 324115187 355886035 773349115 14771285 56669154 811061206 702835754 528244272 596902412 654143843 802870217 632228536 561332155 797715756 820852627 350284706 277031313 465021793 88471503 769845989 265580954 837590157 704117379 3914859 994870553 352723392 458638458 851783456 376297960 525718309 718419387 14106751 675525300 777820665 625487574 719209818 87344411 280276328 372205353 483502742 915127786 224521727 387525817 660272039 128183580 470769349 787675565 802661000 686678136 389601189 991297782 42577534 147930039 352115458 332808443 52552496 523850704 829590967 591360119 283063411 999321677 54077907 629509328 487245969 80416789 529826893 792830749 881188499 207352895 392173082 896777722 871484668 587932720 255084863 680720161 762702366 966877011 996210191 5590779 308889216 470858403 415122930 442539225 916249940 83326421 106989776 682343135 937877302 194015508 480921484 597084943 415990457 459286037 809027896 85685062 566474733 309912842 72492213 963812295 461619583 550256510 294828107 260594735 495373125 743611691 607901708 714224135 470490199 700592156 488956886 25240286 821157847 97534340 163547317 986686713 214694213 770714679 204993251 86838763 512289592 551445290 84829078 583045552 313971650 197903039 252171134 592050156 48718017 706855035 401076246 124115660 178644612 473836750 326664310 441631881 2112894 743402380 586439517 185273240 245880553 299031536 702911092 423737797 163416613 75606560 711447024 233390972 908322741 245335994 363564072 640314106 331294035 762302411 471388150 802591849 645394155 42406847 683645276 12138842 327818372 17426505 236197802 843982547 412176765 88638609 589695454 540689090 989968444 998682267 666915154 575436731 967804135 982326850 189732132 647925559 518645154 141879561 527656183 243207502 918107271 278822644 113755863 762995498 186717643 874883380 457754570 239233770 20450562 165245772 764533172 966862847 827729168 854217525 10194964 186070011 449881436 146958538 947423081 214844934 246805699 595482403 514395981 298266484 576014528 743091934 125112060 724545325 487467952 548366485 295191249 101673141 752578085 934269394 474384259 637613123 350714614 53059507 421191020 672427732 738753446 817368577 407521 210580965 741111495 565936442 154259161 375549174 501225799 967123619 890396469 960961339 630358275 518778776 640220837 531970862 879578665 949314566 795643444 105551135 563476579 341385731 236896258 413984519 981545231 208137195 6988717 965742197 760535686 920904264 902548021 98657560 528930700 337807949 739292266 491156906 745636480 938143634 716980782 637116381 423610122 937919466 318807120 558225358 698359254 194543331 323687762 420157015 792393089 399294314 193380092 355482408 68989381 660806688 248931971 566351618 907373863 159058415 661804667 509093828 110316813 970684247 739565993 448116024 875118075 392708899 883555158 257330489 169109003 924202373 516220955 39960559 612656097 276114210 788511908 687633241 993686602 807457621 994702304 771415784 996373248 71266283 674439528 581972674 107966410 173808874 517646401 154336745 539937559 33617197 904649939 309424383 132814130 400103829 613452222 634139938 440097860 193374508 525953627 42353580 520130159 202686 451971716 139514137 254149578 144545944 73665520 907650873 557399339 446597168 10834268 878257016 219014272 260781277 877278470 303999043 32776020 335026358 525627427 551031662 942537351 690234611 575161756 83958416 168453504 913093002 687162961 528591759 441243801 243154733 201378688 982637507 706102708 713938301 685668283 824056196 345889617 569904441 148282783 914057551 483886792 47531857 404968082 986075573 952312897 326168186 789809884 650293920 484994522 242354631 567265181 85187879 821360267 479710919 864016054 225751680 576024894 708297530 531733416 399701281 65641527 258312528 7241195 839921101 763177638 553875558 682688794 852656869 862664424 31633824 546413696 268399250 992827535 246083253 693356765 495745669 546613585 688754980 353607448 847605657 770219441 496062870 719537039 564546542 553168340 38857489 444888279 157658267 902830972 636009813 735707961 534497675 587451471 551794380 154860035 692841154 443982334 320492838 756852860 995779681 425977028 183336459 659378144 700328424 832023475 716374003 532072043 267844344 930637406 763807184 297579674 949571181 306058828 194066218 691747496 348411661 789218427 476269396 395563688 87069014 642158586 294737379 290437033 620448942 988969235 757492336 920144415 880953881 465065006 317096902 780739164 259098784 781882423 771040190 778737355 468328399 296869038 949890794 240779250 415352986 578280957 231763722 403521630 947459112 573852123 176860854 30403029 941116483 36767104 606738787 826057235 721908455 547028823 477805383 654465737 355843784 640350087 280981760 364092608 636363889 287497704 220112503 231387721 487441167 339556654 499047029 319409125 337073998 996583037 714923957 986186345 314636219 959095895 596043507 865964198 851595305 994188047 719142525 703590139 779403148 681250425 869825777 317643641 348381417 616674027 438328647 708181275 210486398 971177034 674573165 926599541 841133681 650375612 470344435 894750248 817333392 753655283 509087420 905878113 256142653 330979270 251765327 548920285 105326483 924000705 909292893 164412021 558099977 571824133 334990221 129717641 860421973 99327908 306610443 928129702 800933864 694932427 440567722 892159808 908104781 581782677 393540420 105248891 877417304 117854072 557867483 19037012 418601196 462649651 380825478 870981052 408305 376057973 234006274 985129919 328985664 461270808 723546410 389969898 987342664 448730631 796172304 18909438 562694109 324825791 993765738 419881614 374151141 835073522 853318696 189531976 871068986 507734128 188146491 204695024 704908348 440750896 150494733 942723776 41082537 719961643 848921376 418920930 602553951 196753449 865409977 673806448 132732329 367122306 91204786 702394306 61670340 954977417 934543977 827807120 384950110 511875498 597373198 215119139 421667414 623484655 561032444 665630389 414547035 115484938 715007941 844421515 11887562 893238359 399566195 385567727 564295314 579177916 772138053 507475322 272158578 918941729 660897477 217740126 823917465 138029607 784631088 410495331 336827081 237248746 384895614 845145104 933216675 807958283 273108546 850738930 810154380 967041317 793861396 839416733 255444275 839194304 26348120 864643050 618758298 461624181 188153714 769575341 187725511 600009458 209001509 310013819 832752926 257756765 584932929 409780634 606859781 425033724 598576909 988732910 198977457 647530550 370412962 559390395 849758213 328021230 3920877 508303961 663542834 489254905 520536653 316781564 608269713 795259477 499460333 378396935 23166005 657942439 552984911 277507992 44621056 951099473 181460988 26015133 128588856 793103661 35568483 61470745 931691996 861220342 832608727 487668615 853062384 656051552 155363966 86301134 906153444 664458772 688512166 116281597 247326720 531461826 634693347 412096093 720735244 586828276 65411071 684675360 437571087 74739814 317382668 339274428 658711333 520779494 387449973 916876902 62538887 174959535 209543511 154487291 859828578 936179548 946890106 848983613 507532524 862260302 112489157 120924118 88902201 697552316 573510620 351242447 655271760 761005720 607155315 127417815 229750112 412397836 145881859 576408894 498404928 348422534 731057808 761371568 298352548 982557174 181196687 5428605 914403598 22488293 925142634 773018016 550870390 385292152 51504732 194917752 104192641 400626170 160962102 256143216 282315752 78295608 460819510 813350218 957523983 205226151 458420245 71566052 657960033 540910868 723067128 271195638 585265737 961743112 63548814 721474794 933217552 736039626 845848641 212382903 593106798 487732891 889294827 271039925 302717308 933722487 809917268 962306978 718832497 779727230 374501359 399410179 255159791 335652927 550118665 574605819 178592280 275070489 457041726 296608078 928732656 201041210 612301009 485436058 890652384 623398391 882428975 469711775 320856234 495290043 13406223 567954712 208001595 586337600 806394008 142330166 382741306 803487861 988727815 113161021 838620682 476170341 538929132 316622417 551098917 207577544 829795627 280712229 18487188 184042065 443247963 329327759 348441506 250021759 818336908 384791127 518019320 902217263 26880385 473621880 797067038 96587493 165289836 212593989 613613324 365368765 349099090 597641033 943788986 104988125 613737344 458777889 540032207 670371380 754411984 799665308 851015945 308931896 185218763 160236952 379992312 475612968 854269654 549560380 656561267 755673402 45790213 537511187 715434760 512362526 646977067 627169104 770009283 847392008 518439754 709401146 87881809 388647694 287025280 867724046 704468094 992034699 681026708 378633245 590855777 917485853 983376367 656550782 226352358 364313072 731631104 539737543 789184103 908283412 312927219 749665605 228412492 409367459 614786628 587504571 616928952 539384692 318149905 594796259 347331578 447449187 262106003 486815982 41404066 941225424 569373982 157070131 639756440 371784029 861461322 423462912 757836633 841659252 894010619 738768982 119744569 663448194 338497480 315880919 166834688 192060108 131100135 794266745 284731750 264654973 350950527 575164766 291353148 651159310 204160527 267283334 776828660 993418121 60210939 97478910 161098011 466661738 743138575 255872389 406247248 475501763 310256630 199097692 883382839 187543302 781015271 873657227 871171690 671969753 185880625 939006667 594052766 276687208 491285792 878586979 960854914 779976271 993548627 787866290 290865631 176990675 715469512 894901870 935363902 253620740 172691380 133981894 607750 760694920 734830557 366894866 436803498 442131539 779388382 378332323 19087627 313920441 64676739 55694665 96654578 870638178 454300923 29858882 526616350 814247593 396863409 790638645 733333146 755568569 574218932 338779145 907721331 442660763 156996151 373148330 47694886 192247742 745245185 313672673 861859698 726280479 994666342 487445505 240659360 140347269 738845811 360208470 47570299 314177196 907967758 876637738 767778756 873006140 632541976 833826479 446123246 103243106 452552167 733944795 424828768 379855513 361990988 206365057 291378584 650955864 367761485 700550930 538627940 916178413 200759598 627662634 646863334 377403718 946473143 861741256 508881486 409746033 101143450 862992355 140284601 103182791 72247284 520005927 115810380 131486730 331055064 282764170 200768577 927575612 583230723 927318413 337139502 839657889 323481659 419768182 57394785 702291990 203570113 575339901 832162667 903622425 840432361 612270157 597237855 282586511 49205008 44330594 786271264 763930981 556872357 763407169 873924928 212307804 767291608 38763264 839322956 953512301 231777558 943870582 401570549 140079006 243830942 539112531 222538890 397734506 577217773 483839975 494480284 936736127 6041370 759753512 67464123 419149131 222210712 376446312 636839338 147993708 940992679 144442594 129502664 568734360 851193516 435444669 918656676 822236832 333866916 769406876 219636905 829687364 805182561 488021673 284208635 717844025 429524483 731622250 279766646 570111971 919993420 442730622 627183336 407257252 212315142 711301218 619676476 750371770 592231508 44350687 217546550 609811066 246915635 715006964 388999867 942669550 94542649 750722741 865145830 75979504 566310069 628158495 515188222 363744330 735389114 363970627 939411374 483972514 985363543 467992738 89713706 273193337 911142181 678651466 887904839 472658091 636850153 51097539 943542488 473375129 997373159 300159998 99140323 386518890 686585147 495950824 755158515 983804753 898137073 284290675 426659029 314100487 525218653 732178394 12172898 671872639 281686327 462809110 144880373 927181200 429333799 252810342 102413347 495406287 780826295 786599967 575567741 572524650 994979657 182336891 974918434 539980483 100156828 935661061 392096910 554416620 569961097 306968788 893429119 5283119 242324087 432129098 743413825 383512143 914957668 154101151 54665039 111596057 645862453 725117226 280924217 769153817 625746946 396406316 802322783 257937019 50281658 786713412 86047468 487114554 837088212 418291734 709129334 765717930 455809380 488237487 330522753 58577435 493335760 941065556 234492977 569524867 104952816 393346332 295363218 13895303 631598976 905144088 255162818 642420960 50780588 410175009 67412543 258443643 723382446 815074549 38725042 393583224 585049739 950621737 895127292 896731179 846884585 33854734 934942830 30753546 424937812 234201885 472570168 251917527 376031508 296801715 725074447 72479603 816215073 437798366 793612124 379678484 695213220 270655653 182433222 550589048 656890886 202578999 686140731 206075976 281455195 769629921 524409482 56725534 765250256 757392575 706089705 194421417 95353997 162326293 484507882 962461307 315229539 106872069 516496777 993296434 581545907 953928807 692348040 577502891 941434845 348374707 594767575 851764090 989560147 626905477 688752586 497793620 423291212 3552321 4006806 37454911 695326894 994601188 358189415 337169750 357166614 553984938 375107418 919037712 206568757 96498340 693666182 752903314 930339430 449447421 474992636 631453947 142182867 408871797 332741109 881411892 984388095 730157272 788597378 680446262 631047490 915538434 944056638 368652225 312219792 750238992 235025892 937015854 607310163 240662461 623788630 252247839 191689911 501893510 975102281 703494061 976303232 799252503 756638182 766704610 963647833 395952028 666480159 893911093 746525965 373139515 794243147 774358431 994114839 634571067 618498922 808725221 709769235 522973898 672936096 499818065 60377983 585734218 916592649 25547892 800386504 191156002 161234350 201473867 374863828 81274233 875739449 100808117 743233841 689875487 338179940 221311061 590616201 173344636 894986162 413857238 838042019 633700397 583871331 264421066 893551842 313122450 434434136 60117011 817032516 432285738 532125235 54904650 39699177 381918756 897865652 838053388 64420399 320994907 216008351 987823141 521540133 936274333 404245735 911683538 873597980 247199118 620479437 956184533 877467526 391745942 330005906 30964531 769693392 781408687 759201602 180763045 781887012 723659966 183112212 2823253 156324826 489308697 670883204 273769057 222511869 41846632 454284568 698756456 910259189 812202181 312137481 424759179 20151308 22289182 138033696 242846239 941759183 835333387 213187788 563225055 230782695 874323757 633321926 509056468 933885530 900828789 411984944 846843053 901430944 690984768 26724032 960734756 922335650 475092301 194917056 15580626 793244282 326807889 356329024 382135550 421120243 578013065 773560477 712399570 763372752 439573454 929424453 621073250 887700672 873215069 823868072 112676556 29704000 660821089 980194903 169263500 679752860 722509478 147780671 909513841 556297601 159866651 422331235 943162546 918475229 344618404 1996168 459371584 870265358 147353402 382526658 830314685 837397673 651563742 664470813 621979522 407345411 655231544 341102333 116535871 132206542 441013649 989388053 666858868 323826968 120260239 252636979 409096530 363906340 888012436 987874003 636522974 524783131 20695513 106141002 641015711 634719849 293917829 236810135 237900292 28879133 846745932 67862575 883481180 437428374 85597737 198511578 80444956 893622950 987727126 854482721 379878751 547295437 942311906 679555237 313085414 908917819 216389673 479282890 193373927 494074097 269165417 394800976 836943743 595084379 547689794 632103279 931701808 402217317 551358415 256246965 407265836 522419433 116649480 155834968 449476759 305270611 305409922 270673801 904287780 475250345 12372011 621462514 960983354 898540137 578872236 956743014 573044236 90619198 873676553 723505173 936631775 754029763 79341866 746236208 393448502 845873969 592388862 379601709 719578600 365268096 199270810 159357899 415772226 757849212 210499943 996364220 45436648 877674286 301869915 987194001 125668054 915296208 635939770 583724223 73240560 890023403 78227470 281920317 873164288 267344991 113530484 191466926 750414413 980110668 704667228 904018284 831777351 171836249 252537603 553991792 151392114 782881098 910626866 922028576 67230978 776214726 661553258 799253406 169190176 809010274 29816320 937295118 196186954 290073339 812276660 46099716 546290931 762208554 116173634 618610294 389775189 559158877 479404352 55234115 864017088 904076536 179476027 705707584 297985792 424584625 191670981 130705826 156394613 996311413 422411577 21424272 969682789 299442192 453878957 479658807 485296855 923688455 570863977 110070199 533992609 990474799 756292989 432811549 414172959 145736610 689941197 966692865 138403255 617411335 380875756 108033795 489042142 973888721 297938419 74258354 265723690 69975655 314102493 63644482 186074991 646735902 82234763 147263106 630897820 989698399 536250795 922116728 4690749 426871725 191113186 156565197 862700133 631695049 546876870 888032511 795197676 19984946 929557492 916460925 890588819 545014096 586217738 235292044 11350275 688927370 521947778 791811485 46531405 343547463 818778750 165549968 942597183 917121392 682407589 591280082 331849778 285017258 983573169 965982510 307810354 385257900 991910282 243892059 662273978 222102904 871899650 389865771 989962917 992115888 789641677 932263130 858646756 249923606 869688699 935999635 73304132 830455629 857090628 839119784 221519884 522905950 184354605 140547699 552981066 40148439 833072230 537477703 505797803 623181291 780135140 360025591 828200979 552072093 515657089 51997168 953606550 595112508 337800998 358972392 31345667 45764025 727174160 583001890 802413975 977860778 68137428 954317359 892295801 122777437 794732773 510379448 737849745 795739899 706592348 509385640 61372369 892598094 639684568 6648581 786879712 83475598 431793570 362502418 140161656 290599792 372043831 95195079 170732584 816574583 560552602 458180438 469633903 248697410 1043083 739148038 460832233 192856051 23536938 689985760 709375021 997143015 566889509 105331115 118573837 408757430 122446868 865572901 663680769 322908357 432325267 955471180 592878402 618499224 605636959 997072380 292055835 665150248 626626496 615410975 155276122 319069071 820220780 333499060 984611455 107561766 191075914 133849666 282240589 684643919 8968966 148866085 442057649 476021311 793027254 356955894 876964283 393490608 61206880 697574094 543196168 506379225 283722658 554925831 472833021 178841689 871788431 602934885 405383195 263036174 326007327 866674654 699395523 48499677 136002724 284453356 295136655 302222644 814918163 211161083 968072615 260130037 545790027 603941155 902858653 166825602 781039568 178992187 443778557 49878263 644838565 735997806 52423123 750729545 88270833 730048495 882275646 261568090 15339880 871183484 582423738 122020918 333910832 863252145 407999166 565135791 107487083 965352664 903248241 885958090 600534755 889458222 796983071 382590620 133597567 949491516 550581897 818772600 955933901 617483404 622609388 494347607 335198795 726963980 134667895 935506697 70245275 740486724 674621236 200390085 761785056 360724871 676543992 365512595 566694490 892824605 705366935 860746006 948439855 143544969 48502755 705604627 991456917 628290489 828257262 428607333 978283282 720096661 356136611 264041294 14857972 658793643 318443739 954098265 514469743 499927819 627015908 293225359 365878873 4619064 152205748 865740020 382316690 693422608 781239929 574977447 885590900 749604396 915816047 141954586 648643533 198032283 496439628 835255127 313167862 417459596 119983589 633663125 401764388 541391210 990817770 430307042 779213358 577506044 845282921 757382561 782057754 16043245 158715153 447157871 735284182 890576137 545733587 42403568 842155535 452519076 543591515 630161874 351389684 460303996 109501682 567078708 965455915 419467343 984238590 613806081 480273362 836755104 33599533 261009692 41099949 483099160 760546637 424115061 722377893 875267044 304291782 981848273 634118617 873103732 659142642 664245118 487781935 434732000 332672060 895062126 220974804 931482133 141548101 153948099 786279698 449315995 803971462 268247793 724521483 676917054 636872187 268397097 676116578 351717331 684734779 376486498 513055790 735504198 633725212 315003132 285457418 666139452 523192340 285705721 304914769 958135519 807783295 661336791 4193796 594345884 647533526 23831542 716446392 280896196 614044117 871412110 991270704 715381859 608978682 215330891 157401243 86415009 952249785 706594006 351646862 42923445 903857648 488288495 478751098 331367930 288697059 948361571 623705778 93470095 777552835 155942050 935397496 279600432 468478819 107303594 287220662 970562343 604321813 388235216 28765274 469657336 10376571 760545162 669055034 528113379 869745880 119079805 260535762 623953989 578111864 895175608 990243347 715421332 422063424 253758396 767288545 490150709 77710171 286309225 647001245 333290130 354639252 502763220 155187463 357047830 78636709 987599642 809813928 514621019 490003059 497938236 775603268 375896312 666510537 823913463 181975557 854655514 817703610 264770611 115580409 22243205 927821565 3712097 121566634 405116121 419311867 471332178 932935054 592842424 864909412 458649135 901651732 175730924 136570775 870169548 534724676 80380486 833021852 222244793 330171554 418070970 208016191 852485659 683451526 479208768 989005427 833648215 239364357 158140003 265566106 112044731 138002533 317168715 766728320 103925218 983950368 794655005 549136896 703098846 465693462 24364220 662792593 558744581 393922038 756765428 471529476 847145636 391745327 597017301 632449754 594589471 911947887 569132373 304923929 961669776 936213207 676233001 287967472 262635227 536711773 99369992 11988582 412483701 586570921 922111739 618171183 52440390 78301989 239228687 683503140 354668102 143772130 783334502 102144931 652999865 581001461 642219253 322343497 537146521 484561390 959332626 480676759 873673546 517406053 858394981 93054911 960364065 119124665 62519569 925810208 317359082 713749139 290483507 502317168 46095783 437787514 920639336 906372732 498400859 380331506 264619084 496915462 813772078 643941292 313951006 308736105 120382525 477033498 987628050 723454762 349417937 330278349 110442165 177230391 852434367 149251506 530568583 874802037 645543372 344103060 877234589 381919025 323915404 809964617 820730129 850721426 224475335 858528314 37067577 40938373 426605644 155170221 558300779 863400606 337485872 367844489 282489119 374227181 895766200 484683122 116114740 900902067 974465509 442300221 83633857 700693868 78684930 698966203 462461114 718336930 417538582 673990543 535337934 495990221 913523402 701449866 886417343 534497059 75671644 857738855 328117488 583417577 762030859 873281601 225196690 955690602 48870911 745526344 399008110 540857853 936361074 288336060 112325598 711013359 768643206 931583875 207712470 997239690 40635587 716238320 866751096 33695730 908093166 105883217 180496247 543863063 230710981 97350683 129198205 594206122 19166636 229594474 245889009 310611659 506398951 728755867 851607030 726601185 187558263 61052521 36049458 298051025 994049633 384046228 570103582 226504877 861146101 544140028 199860188 352063999 904810297 153960776 60344149 453764162 398547211 568926258 333309691 428309889 648021022 367668320 929221577 137119169 99499286 353343534 84120738 319189287 833076649 665105468 138662476 842404671 285706705 422196476 764142647 90157655 186889415 132119464 831976791 748837963 312367028 823848005 684166412 314858024 555721160 717644729 162244128 899778013 220043839 646562062 666168619 526368339 970068179 19077047 743829075 419983574 352553213 536239519 787255804 446826760 332390353 591223010 183851844 408500357 303180759 566669385 14893822 889109619 335598887 770756043 134793119 662080533 165350636 539230342 297443941 934691261 113313069 872503289 389372100 9642144 936736300 79465719 197219804 545258435 110656432 196220940 296194982 548632519 424990674 937652601 666921236 219846385 837488023 969748476 167802277 458582847 565259821 321110335 207107074 887639171 72456016 563887529 189633455 703058719 493297816 699699450 858957058 896672447 280149874 187334128 505939110 663587057 748880682 174216046 659491962 758882325 427479924 346880989 810972140 720916675 316174224 720278319 74861240 603068766 677090839 102649841 3564555 640591443 720670027 982721222 69739344 790319598 927081883 116461198 99936428 91015480 721944517 864624860 673461919 134508860 216252874 553849762 914152407 635315670 249125425 575772606 532021147 707333017 47601031 384768173 701664085 210499604 730385276 716342152 748334388 955211214 61652245 889782349 548362227 956504425 361393636 462461024 899632016 239371888 875719323 957444481 187301310 987591825 718142635 116792301 59586250 592761965 946049467 842548798 28587026 970166727 878443083 379723330 168294001 803864088 160786593 172905597 239356359 779704812 304287950 579550998 447440032 624138264 135741366 456832409 771589409 114633006 294217074 167944596 698080891 744315526 372800669 527014566 852250608 533469573 60230985 254541551 2227474 489455269 993297278 732891020 406361756 660327096 3441098 850332112 21228421 886148691 736270731 699450460 958667931 153189877 126399703 473827135 4657406 746577197 678044015 803468405 838611642 192356946 829692420 757324765 514880255 734363129 647234160 533789281 546818925 956161845 528879133 677028652 652988456 517935418 604930816 130392293 61787752 558624579 228070901 21655943 43091870 90843581 496177918 659099771 648529850 449801804 649067231 439164447 79429120 81756046 40326625 191405160 824120162 773925134 711437262 833138352 848566797 742388819 259270019 621771002 255882445 632155072 129545072 128092763 341278337 551636025 292611945 425318951 941868792 333480636 351878190 375245441 555248863 984572768 732561715 537963819 68142886 762309426 54613950 640864312 702101679 746699072 954329085 577899000 113744010 297324715 100881880 279555790 392059387 896731841 486882057 431930839 306113461 869465814 470257190 564864158 990142186 764153994 489134851 764545841 398560651 726035240 386558341 979281087 922344923 578499948 996875819 20601208 554022779 827883145 40225642 894052698 617611094 525017742 40362479 885413548 478393297 748707963 285009271 171748919 224342493 538100147 900902513 546147569 582615844 588490888 736244272 470868887 486794015 200887923 393742898 386323377 78886582 576204244 930579802 247304209 592069630 147871118 918050761 557559082 292608773 65815940 441313383 241582288 561738484 724861614 633827151 751544865 657656841 83515941 129793218 382177501 956689837 577035351 251798580 661181538 639583148 960517389 833189283 656221596 665720029 734045603 464237945 312557751 132679638 711466721 177055635 901632438 21334573 255162365 284819541 149332522 677535791 194557412 746947207 332446714 349179755 278517977 343401868 448691156 469365766 674849862 108558689 237713569 149685478 914945668 207188001 544481715 285663074 276593822 776368402 915006245 284134360 482991226 82950079 451411451 701738093 251265435 222592009 36368711 606086149 833019885 790828326 426277143 26238939 226385463 387873587 83615926 447242959 440274442 430581100 428550387 657256343 766978561 226941638 281537697 866076066 47680599 290975519 352740501 251722397 13957232 375943063 120281803 785168256 866088791 363355690 591697441 521018046 701132030 435724845 325055953 726608423 536015499 461488772 905649959 300992554 662838266 442586184 673646125 318482646 550107234 97054762 489324424 949851572 115405852 480250613 505991307 27387616 568925067 703150672 807012161 873453676 25241091 817984156 695550599 332453412 963344078 606279653 679440625 336026769 40118020 159550235 799637753 640895129 723888315 849288065 85951082 361968605 106543464 199975111 229431660 23451009 144796272 358208344 705471331 543580023 886535863 847275383 724878763 582430311 781834183 32558774 607287223 691793545 494931400 789926777 624369172 217237432 571630296 130696887 209240023 546206358 781677996 118618149 631466317 451454540 155123771 612923022 863721582 956889352 253040737 229108972 218539308 315783224 80707982 545365395 149366339 535765913 786680559 637789586 689912726 266056343 403243347 616756623 872628363 544322057 189394729 803143616 798594732 496502765 915879767 94943212 795537313 420211148 648074091 516790018 377424441 502615888 863741900 998592322 495920164 526863807 313642672 84355330 175153514 955416196 273695191 966395046 602345069 856543495 814477894 418588133 887545152 446206411 697302193 574619368 211546449 693466817 207497135 257018027 731234795 950826703 979451800 837816307 383061456 145917833 876208051 60593242 787712165 440875549 169691141 20911268 27095256 238225318 789489845 51170617 78138048 213665011 156373369 658047495 741034103 624224852 850017223 687348724 189388848 133771672 628618801 604678213 844379242 803923795 493381338 993510307 20306544 212228171 452101387 131926822 424820195 64642682 29571498 359726785 934692514 420180093 772904041 959938088 446972323 343422241 864254570 329507460 788984159 605270505 249683744 913197562 91232952 980364081 462703938 379051142 43604066 505102213 533065195 62827080 802744782 485507501 601947674 876046898 434944843 452519729 506828770 717133200 505649549 147028039 702553610 923752339 34698494 647031454 726382794 772552005 960642666 60249288 390061918 118862308 810242415 923923844 335590693 419264824 289897376 349824148 52330057 477720900 506786101 852900116 493822476 550681460 354786089 300636087 933460573 623393315 985128777 538833363 606524494 418201055 261785505 464801149 73526813 823778620 407792560 795829455 553345806 248404521 22959545 22448297 535715796 446582494 384335054 626417421 66428105 813913517 475611472 221551580 136224625 121384579 106393692 869555345 73275146 782511413 914837640 381858947 319233085 723873502 827312199 589826992 701906807 24534868 896600857 702757353 894158273 227787477 10710613 621574970 59977567 594487999 393658372 26249867 25977300 428328215 606302317 45567301 593174046 173802986 57395032 940331343 17646825 318891622 890916368 394242098 875437380 682858545 278350655 558952307 456045335 832564930 888099231 914873676 899435193 431116450 743405026 293387321 552960784 802419206 870634852 740800000 385546813 711391157 933453496 543229153 315835920 709575827 647478084 338892895 881857629 388300219 661665700 173560320 51756195 250506215 470210000 796952212 860939219 578659865 618101858 795591005 609084168 302346080 743084884 643378767 178861884 268967881 4093442 538292779 107098048 607108193 652141634 225814178 928649266 113688970 746638105 118802949 937570314 611589075 670392377 965996101 320591451 777215386 949463217 198854231 418333298 177947067 864359045 106579311 931409416 909086161 573760669 332963985 209967697 608248485 986882521 45370148 75241009 212639417 379727044 462357948 834729585 266634589 767429745 125206077 256047024 454569221 980589587 588480811 790464468 253825952 752869971 709463102 303562732 751506258 83147810 532934546 879612509 36171587 851572667 885691216 44843060 746104838 38087743 504728967 992008705 234540467 26176565 640538180 855492893 573836647 676323806 821318844 450122977 522427023 805669734 689377035 873859233 978609100 695733553 137748067 277180639 977475971 816122299 394548419 424809992 342051936 616476937 572115971 27548857 627443250 209664145 984837972 834603281 107614480 733511795 710594889 773591707 103897520 289222266 875834002 641480064 782976574 645013477 777246875 211642578 314655445 496927729 263609311 726344122 405043043 420827244 975499637 60372554 350869228 792433255 139116877 956654588 829652276 904441498 739418301 232555113 137410634 552742953 845213663 237766501 822392130 626881169 158277633 343000190 417051251 646471900 577298854 121108792 354719113 335682129 762164710 55499966 382883912 120480484 810596146 929130068 734447352 971146783 564121495 483827971 303030537 795493942 55147998 433794146 178038590 467135097 698098836 330463255 797745196 685140311 829899882 383689324 882937957 888512356 164899457 30863276 719599933 998556624 493368517 992284839 352710413 608486867 532685849 826673644 119002267 158206803 265953605 636011671 613803074 696107841 41469608 337737007 750090796 753806035 378288457 15002638 571181837 199643760 972246013 385836786 156332897 231560166 809728230 180463348 982798109 442324085 54026612 425047510 883218304 270142048 388949043 401162925 652931678 501668485 769486772 711842108 275557274 508042524 789453799 770504762 468773701 725845354 182528029 555726920 402401269 116014677 642836736 323224642 968565320 523426166 609223610 971801274 556565530 208804996 447500863 458941439 580801518 846386602 134778889 654670598 85972266 93030181 493163830 158857004 650905593 471517486 828158802 951156471 977497568 984632781 581339437 898074178 775636500 107388571 956866394 294772421 431634698 148230091 246018168 854864025 543289895 215090994 890234966 263181311 791032261 130672396 775251307 888394948 287688056 664442908 98098012 537391549 819123816 689268312 435217919 268165253 415589146 254801824 903233383 617007043 900844373 853806067 488960350 127544813 130731409 95073482 156060700 795976312 418966677 497415622 267160431 483067965 234976428 554833795 592329814 104343601 137922447 553822655 749411851 138000346 679284621 107302148 909112084 432060791 343862124 704697946 278351162 998119600 467645268 517652909 93249612 584267083 769069732 688542411 691989643 926693183 614116295 988877085 478837275 348789841 716825709 525065930 219348259 13414668 343855658 764599112 885490223 825175674 23029412 107570274 421847898 544143 215586082 473408835 285102279 69135296 230787331 837608558 315184737 176446378 575434377 714268662 570418854 56658481 231343267 407474178 582495103 16711130 132130388 538731992 53670522 97493882 223107527 886260840 453329917 109453029 520914623 650241330 567522219 378598371 746189100 699094576 676726074 74198535 816298664 388382022 301414918 403866791 511409757 430469467 558058830 473263342 114143684 76850226 71253248 66309878 707775254 270752063 178851539 70910502 973351147 473294135 681875009 444812309 824174837 188339066 711611787 80250642 463958537 969085683 329896332 388482702 662334633 399020851 907100900 755209282 984969868 556334296 345158571 382771156 238932968 452621943 80720557 295185945 885300651 907770498 371035298 799599946 925432616 705742223 661438197 179227641 438568945 141694426 420696169 542857362 827083651 623196863 516076263 203385662 459332072 713145572 706936880 987888218 217648969 758770475 66460906 944815728 66481426 378216217 160543812 756657321 546723067 77796891 954427175 262693811 667480412 50868095 786681781 975595837 3747558 1939117 113055210 648431848 774648251 28184479 470121415 755849717 29081553 328438794 188042769 299856673 290021404 274755513 267215506 439962388 530483808 448372164 853736156 795801646 764460137 732642198 2877639 907759046 480086639 868590320 192883542 814342330 658451050 271174948 609139318 74170117 658311691 267600365 352983636 184727244 806431874 267940291 378856739 507609979 798090147 44794677 359721087 621179988 864538754 67228570 663397395 494637012 404775948 86717787 680432697 742230435 184915072 898798634 459774174 327213801 231245537 888054329 420238236 240838747 440840299 430125233 291603077 839242510 784336549 61516755 361404321 130229064 774600750 767061318 978886857 443939859 36334362 577745974 702554678 79211685 90910726 913232550 661936926 868657803 365791754 528329940 514021283 677291804 996783887 645954855 727647939 752915254 145242206 849038291 151580533 671310692 589192760 793158356 314137675 5666242 46129089 912848010 559651231 388604111 680331238 337410508 73704198 649379158 761523003 999770914 585233447 278899664 910646202 4862956 348891678 288804598 380536014 383655395 955611662 36184316 963213940 701594950 771061962 653440335 112313026 339432372 131327433 893071441 464726885 885618532 773255815 782167005 353429158 459296302 674391847 828987641 486125786 755223633 23505261 750128077 718790647 669485610 97675601 903441465 13100178 43957928 386846405 523180995 601257524 405060562 672626375 871955780 424291281 519181652 141445211 207901177 164358010 947576468 529786477 252291146 106426612 755413290 694915946 86695530 737051948 209787949 396972417 551877586 551347757 467982948 690422694 635623390 774444569 878732200 864975846 714810217 260627405 872294972 294228497 749545771 510019860 361720459 295168239 851728729 55524492 368126346 88169400 289898394 388451339 546696585 120108393 123023818 888785289 558253083 647946349 339013795 370551601 740794508 49716853 746147624 163876210 290084757 418755651 471095815 349266690 884262643 211519929 221831083 924622270 410638518 471357520 688625533 756792069 728135528 346021489 926988790 468847640 530332644 52179407 712374819 736283265 890586439 569589883 943821341 579531576 112726459 54531783 730309624 66811613 623437176 412361828 967548753 783093305 757871519 802954921 936105136 600171714 132054238 789676581 77439893 408667475 464431706 266773417 72580183 394710959 239572464 944086946 512784054 78380946 821946237 878400062 350634901 185038704 600816589 13119377 413230336 224976038 559021742 337828636 610238525 92211890 348817704 737944149 301853128 925440381 115325842 242082482 401524848 706568066 699757957 103364530 13663792 915574436 682951481 373976092 312448885 669600564 222174858 452328254 236842256 930606307 282760734 486414572 76138652 801408814 846358538 397099039 265498298 168132123 27813157 264020031 60074666 807793997 120675279 414426064 560814837 793388520 786623500 892185700 988921359 382690695 35876082 982776488 132356677 923914119 105864251 370758608 362742463 642120654 78266520 616998068 385016674 32521798 836382200 571462659 420219503 568751094 231676512 267515145 613488293 695825374 395097467 43246973 438486651 668242863 751837178 272193006 594463536 343371821 552360 230509853 677430606 823740431 775621469 977298837 155422429 189097019 178953716 354063205 250723378 350697097 427947689 82860233 350256531 530778583 796143845 729665067 988157635 341806734 236323604 155137417 275778736 410181719 969388334 285153986 931244092 395161204 218356674 119709443 387623707 796265341 749225395 548750220 577059382 931523496 328109 4572615 732160481 747027820 210038399 703147133 686988951 851231337 984304802 289327123 101968567 576849699 502138987 611112280 535875541 785711036 132587976 403437618 769537798 718272501 538313887 378319174 558658685 302462215 946104024 940883163 150953744 154578701 908294728 424380088 78852833 198215779 423176623 725197774 389378868 479446945 26052600 882809579 310817770 103251276 373911713 449136009 42252264 635649105 861978801 888346941 197205220 102112572 908591203 564635697 683437277 816082097 839805488 886795435 452274891 458724892 499247958 661285413 792578106 668869446 711143870 239137734 914120364 577812316 491945430 216642293 539496444 402320492 130445412 420271437 889247991 747325354 677254241 445292845 251172016 997367709 580569103 95401586 528428002 259650732 554660081 544145394 672393927 550812473 301243464 986388769 948091349 778591640 12480864 388232998 717810990 711166641 269648310 429679126 259743475 701300974 935750812 219572459 713056968 579063834 316036375 673499239 737210782 635583723 274914856 44033794 555683536 360629949 458157205 713383948 487463635 615320734 713270808 645868728 742469857 575399975 225622230 267137465 837076476 870975324 868405774 181536762 843723659 505106879 19113247 74235064 695807564 468254182 268695545 731482451 970177744 187372614 165129261 790374970 991961666 400542272 725746754 513330526 996819951 410136401 589649467 45692821 635237452 471435893 536199718 59072631 424322008 53455995 984088766 618394914 63275037 159734921 375478067 404414102 161157266 465683850 578337833 634926005 212830966 236082521 607447918 887909546 495922428 604722766 477818009 937327134 777531011 470303973 909017436 839823037 242229044 812496385 110385745 572581634 749630102 974721275 676541037 101589218 299114498 396898984 45508284 726188222 653054111 463726501 573576689 591219497 619232291 384313975 81318330 632073479 831031579 316868561 759860883 874226611 881257919 924849237 710590263 342213523 65913403 448503654 650040112 466661346 327917660 541177005 639734152 297290502 701143972 827893426 223768668 798785344 526398297 820050172 744512049 775257332 781746113 411576608 409755222 436659689 166129563 840418472 546693047 168199861 59477029 962240805 881615892 56937782 554136690 85663001 673683622 172246294 638411262 284317559 734432575 52462217 459776364 604440489 485001660 522345009 858960728 138072920 584803221 666862428 120497777 147189694 517108371 207668870 221074307 597127214 519814455 214269678 54760292 886427888 200668486 281102780 750680931 386881243 902250693 584023977 916488924 340721059 681251999 221235460 140799477 938624436 894185948 718915799 868909417 752383423 64475165 589200246 347227642 731984047 266701643 773639324 981658151 624952284 526255678 557222461 51239184 258696028 710256607 194539903 412352439 654839488 803157761 452187707 562817152 523292187 547189186 942653894 966962367 774619155 7366366 583529825 929540704 132623282 652948186 573311843 838404971 639057028 568196245 158514085 301362602 67236229 922299407 564185795 180896788 348968018 986866288 142618946 323384185 392092136 937912268 798707515 477231925 351050956 803703172 75979743 626151517 405972319 235662865 476252327 385360375 887358463 86659573 90991319 283964837 164273228 538093992 370924003 345673610 774859522 977293098 630772052 99291385 833316348 601402207 243481062 993408743 323846497 444013332 151357891 24306887 619396794 36093927 804463439 36802257 186113669 651803571 277687181 494201784 621372113 908830323 826660819 779746309 959697309 352850766 282248697 406701892 457201690 445945689 143993291 779048686 685922245 809266791 659877847 704229118 275076458 617315096 782351411 547488918 675060457 252372100 960352543 178070400 993590540 773425 171336229 567859789 148736451 267542294 529304684 799187110 405562683 151380807 965368608 628647442 751361726 708066068 946765360 448570404 373341668 24035333 182750320 676429265 41311444 132460946 576151429 169737146 222493719 833680959 857187013 646546499 15593816 819710585 368450507 314397652 816269529 460264004 935880068 235910457 486590166 318382139 799484950 192267917 256442008 813351070 385543335 368426270 374008696 187798099 869004745 38810887 777108266 913094799 873267481 178787764 876419849 789658988 708917269 102900809 544897198 23680082 723845274 782244490 348276491 487563417 632886380 174572544 809359975 870469483 494397337 279480601 657008616 391567411 542581422 166021957 209410662 747821129 328992191 324323867 172376467 519493204 548214975 785024632 281694590 188747925 549314773 724580379 930959638 125577346 200466863 718921854 72084097 913644467 465512919 947836775 37568710 166685156 355494640 43710849 694288470 600678101 410982263 234808541 64245427 142800139 532338607 812509798 261752570 511887927 226587017 818112761 313117905 540625076 214461598 33083411 681243650 156355573 690209816 85529685 793511146 875331434 134692701 183329040 735865398 52004003 376970331 993447880 383695293 363989448 717073917 555998829 984414057 182400716 526687199 252124192 616965130 989140707 972629094 112544794 622338482 13176188 206089969 632874195 89952647 889180656 371480922 880091620 218268825 346624701 874441600 231285482 708586493 799537882 193216483 186688649 520734756 753922515 83736416 159744102 892984990 416994927 371819669 981444790 903911682 357520159 64676555 483443489 729002173 63944440 479324601 293498279 438754786 820224592 197927217 498408887 256987135 941371161 15114645 867671055 367266336 834709462 793123982 301454219 747048081 223563 40271227 151901677 875157394 906640359 793824294 621164216 486249448 152468099 970264363 608384594 531052717 643046695 262507247 519117314 453006986 115188521 559346331 572138398 397280696 671329519 148557310 40630816 13102590 520409719 442497467 454243822 922001111 748608005 596490516 127051057 377835395 903889747 834880292 98547772 253461932 817222121 671198565 33275235 202351012 547578851 29226417 921989926 638885771 242615988 55415 30777958 54425433 137865031 207278959 572569025 905946710 84183531 424623736 27290372 826135940 168660057 341602154 185334424 315524994 506812753 849855181 702145992 762497778 183522607 9479220 626950595 23999731 411882623 192881474 264069204 735037201 135632171 918517937 332293830 763151034 300936402 124193902 328174083 974727688 597633173 24756641 791605001 681466578 874062258 676157067 164813823 572045702 661605013 76690969 544446473 964829265 949843903 723938010 740386929 690221221 41321474 669738015 893739516 84706536 648001619 197953040 10302205 82533360 427236556 387685514 253752598 163901655 359695627 530185684 183336325 24446591 925984392 283846551 904182939 885004761 196763429 747269195 148970920 396330775 622737481 223149979 373294188 281031393 203094944 280800508 922651590 872090494 647798781 374126971 145302016 991084040 506095543 947088304 401474695 330322862 413364667 791291784 624371282 646547307 692700256 706762000 726921092 599795707 392586521 713675540 346552665 654442118 435119870 591007049 857256039 690089896 369941106 865609705 976928741 191900060 870169690 411732611 243466032 78522944 419906491 738590151 359910392 775437988 957746302 951270658 223119579 952741330 187036658 555041741 516150024 196215578 129575951 387513189 748180994 558464732 150428781 509023515 387236905 718422311 36928787 654573044 527948084 516625437 25747792 305038332 720169654 62739509 43072616 276690640 953654167 295473346 525777101 863996559 182356383 193499090 333861070 763191903 77538534 149164960 437777214 447716531 504269970 646735270 710068951 749343783 660137858 625344244 981889988 590591209 775260456 588707081 661212306 199456968 74812821 621364729 239166142 267793192 209680381 479857117 866045572 120154219 705341139 798687737 907220924 178710622 643346835 938120323 14997485 854176828 86060855 986982626 818260574 659648265 824061513 216365844 390155640 643458726 4929919 268485808 136972782 924810794 967555097 903805799 556299317 434223192 550134143 863871735 600091881 316658657 829654573 859564636 798923870 5092223 410730930 309624568 459872328 284619861 637605347 93083049 140071656 874950346 481181266 27806869 921758781 946627231 673523890 360131416 321053373 485364361 947966860 340394820 65205358 586131057 930537336 76555450 820144862 975373050 64656939 450697515 725715020 10933028 197199994 529588649 936314425 493898435 504085121 92694927 940138783 943612092 700585071 312877089 230656254 829380677 357929986 546931592 757453524 970706473 665125245 514554921 642455254 192076717 991063731 846288274 249037584 623140794 190248746 244938077 537037272 846847521 54403037 466832771 221991954 956811920 882293420 354160554 641011898 234213953 911508475 52850773 379215894 379646138 176328814 684835704 794080082 363549105 275338612 145416358 90242377 988178457 652498167 161232024 831699817 461688556 424669362 296418278 542922709 316138366 732855025 349688711 362667783 388240483 808169252 861352279 237718867 432835962 835792881 26177464 834711614 726627728 588872170 902499532 413586607 404213495 307357273 568169482 112774246 679802636 543374738 813805501 752788331 384365448 217174261 81554448 603705644 329114288 428941389 597536921 396023184 651693093 680250346 138398250 123803662 34861670 461458288 35402625 308761438 410823351 801209841 21486654 411210071 655665635 680482694 190366338 126067852 756485932 214368492 274087343 325651673 582759415 342471477 680889871 500263082 931364379 553657216 348580848 364869907 361001523 237342436 47752977 81997280 14437170 685793884 454134506 620004380 671662197 202050229 898359011 594341867 179061966 367781426 858311097 410352080 888920380 169523952 402271543 868983122 529665427 737646848 913663395 235523361 673235133 526357559 686604999 970927356 680080933 547898113 124774755 212408013 467354369 966753828 98801332 264121121 97041767 870561621 802222799 965819077 643854912 57233470 475981398 689926817 599044217 464448850 689285705 206202041 546963999 572857818 875312335 43138506 887125698 898103111 837426447 941942984 567146828 719473538 922956286 255876293 6075141 780124955 839678585 617267406 968937539 362581401 797899995 12361881 127976906 277378486 38218492 954443628 798367260 586180394 218818299 799517914 207858565 313735716 649322363 776811882 108808847 994237184 297572327 226303976 563099970 962640449 421787170 717362928 24302475 927177170 425610129 818061587 552788691 657074143 405654341 162702283 873885333 317419441 753103451 325217873 686777999 206938117 278377426 926400240 258560287 753967726 603564793 407558584 399960276 293349994 415996317 497688099 101564421 24222953 302973364 506485032 132588434 484875007 916286545 215746597 334478946 166797293 787680665 388172763 198948643 970354844 691518457 859674339 66648800 586197947 568372071 195824356 882743064 367178844 952839113 173543708 473960280 983967900 204274770 69547805 409040650 478908245 410056615 15575289 947918237 533581398 557957355 543755607 302641313 926394905 228466192 998950080 67644681 448802930 670875696 320591571 914990080 515228568 999589562 192813414 496994065 146075686 805396393 475960228 193874464 36321404 811742903 265903284 113299722 445019587 806290712 986392211 804707190 145033088 208043748 727854695 261547977 448666628 304617516 645042565 580110769 63371368 851475184 152321677 142604432 944700249 663205081 366350869 272645688 347160409 374846877 8915832 600564026 283580776 831372578 698155555 251381258 820027072 879006028 639305950 848449304 793973583 116240721 485791411 89741295 477009867 279575225 225310663 367295043 777919772 537738269 728316331 394219889 156902129 812383909 338534662 192457546 306129971 321418168 661859759 146611447 906710368 916096592 359785918 409481438 416689155 45643518 206000923 165420202 308860038 214912694 762304192 678770408 931915776 522522137 599589589 165537994 223525343 275856833 531079620 390158720 523431066 66054295 774378175 685527590 534986878 423573051 937615819 820502059 36001550 342769721 477318344 49340450 101233992 245551379 333892413 594108906 994244160 9856434 664414638 998742086 744091442 288239501 175325147 87139489 847286996 742298461 662631238 920097745 829317043 6093893 355738563 337524404 462622789 753302750 62040945 348558079 265616816 727910340 518878477 552814371 657360436 67602115 502471002 687751341 756940081 755288725 336811382 743308534 104353531 447494361 816271834 197197161 236313835 323134728 173087503 496848657 106418111 858794303 189615711 35349716 472057812 332836794 845999114 755304729 163023989 563858370 936434765 701537538 293792054 362446093 438825679 872364939 132259642 322244705 531807536 251949894 862746743 162798064 714422408 642683830 304384042 161397135 762995588 513064645 207627068 539884251 475800272 130222911 779166032 544662696 306441780 676908880 370803979 516899076 330673762 933817966 297019561 237863650 814114260 880272162 429708653 193593071 59687648 572224007 404325093 949292032 264281962 175183029 487612869 202650276 136494234 611610064 749749859 307572455 121053732 758657742 614211296 411636664 421665075 253146186 471664824 848133506 904832926 505794955 491887867 189208639 794564329 718879037 911960700 689429471 656050656 212296050 311266932 331649577 202525651 974773508 786139328 982344166 501611164 719562994 187981462 573053438 956691463 580207733 372564401 434664789 870490167 852327626 256602226 849082892 812811357 133090423 747840903 237879954 558266849 60463660 916454395 311883366 436115885 637498250 467705633 633933617 688981352 100642487 240362903 302219500 362030276 249847962 213131041 27699061 408738382 561525181 380511696 765325445 101378967 238461368 175901447 158555763 685536073 261007833 702510068 331887339 954747033 964772240 816284498 792977757 183854602 135527760 844951810 340577126 883779574 283254404 196124024 998591495 697589614 934308445 780760451 772449354 32267044 272720476 161772636 779438781 281653301 858054930 378153648 611421062 517954296 494891349 34907393 719506673 653788405 312903652 853641718 606764521 429521239 748469575 916377700 947977492 5124137 14615884 555851430 482323393 630993101 418110561 909402238 256060320 229890364 131330655 789349087 405205542 491215055 392101984 243045939 365205556 396762063 843394980 754151836 579729130 57189669 117934247 759600945 879759041 105104560 675229797 226953425 949767971 616064443 937351335 652417545 509399945 109263101 61246860 870485939 83234085 139535487 57556267 526880715 944410644 501949026 57732651 215722178 734036694 835584168 959831285 643682018 599757358 286526194 627228172 766445485 511889632 711581159 831363148 269276390 825536529 986473018 145664520 752128664 482062846 591479583 538721369 143002247 925478415 9527469 201090249 29307627 186111004 825535813 28767949 756541827 139495310 5211069 786072818 51394321 617329265 608080978 930459511 697189147 981688399 856641605 288446891 733867642 495910457 788059983 180185684 177326913 16897894 92899780 222450285 816018959 414923786 740338450 135795719 16033488 455522621 595654311 439423005 67420249 128034874 473022966 802893631 998366612 464510211 499340191 983033166 300316030 325560662 621832041 592268919 565104246 536173590 108887762 442951305 863057742 363479539 949050687 244937046 446231180 111430228 386630075 147127626 73910604 468045842 107872704 650020900 690461592 500464893 94424362 644934862 129508217 681514361 280643929 270817663 930126471 981473195 827775860 523609342 17121533 35421549 587677286 891788280 723306236 888018367 950026704 369660288 342568928 931656885 754705489 773106960 18949226 376052063 298442335 600519302 664047670 172450704 66350542 383479331 499914008 80693987 467653783 573407373 105541253 515052434 268579155 938320398 186297103 731262390 517140789 647570789 789411868 814965643 693952621 957210399 731555564 965669644 523763318 988646958 518885909 835048924 132609302 354288178 835979261 135349185 671491759 25537859 852552685 375114097 537884457 90550540 268550709 960746660 854536523 205001044 261081000 612545571 499531742 206731105 418271869 380945920 540705914 804383645 585442965 446595436 422313045 838868052 673140329 236472938 720132427 859577649 348423477 434750578 496419122 201496382 769941167 172652787 484256228 298618749 945620154 539766758 988690922 786803826 859374086 473693306 760650215 536547534 598046593 918258852 908748934 176680607 516442185 458486360 591768764 222164767 676376486 976997256 157149349 246425755 619168346 99387289 98565981 866342899 393982701 547410486 490854124 164894748 219159504 862007083 297149566 38065000 632647755 74035999 832936863 662579667 505762318 766527103 135811644 603241721 922680664 986690039 591962802 848920056 101288044 966827044 584655311 145151036 959692614 211705862 997337454 767410895 974418306 579998747 444969483 277514117 612811396 129493564 706880334 866856805 442671723 63864369 841103991 350361474 221101263 758714156 557501415 703017580 671951856 41617098 51751885 334341927 551168478 764890956 487410836 993345354 591155471 585452469 401142288 161674918 529705158 530907241 536351548 856983603 619214542 736481121 824224594 312464273 695214099 636121592 377171353 587738302 888365158 36744160 721069663 104162800 871493751 737911384 463313874 819056439 384536959 320890826 890734852 401338229 174582520 640762914 566271142 404251310 802275475 682604351 288424739 689054316 825907480 815010010 88978768 535624174 295237258 388252207 81909607 378223227 625242302 575515707 151120866 331550270 120188603 447716723 862777421 845626421 577084705 625753802 705318811 95592627 25282180 700670938 54366311 680080368 266334436 679166689 108931708 189397151 240999232 504140926 519109353 163818528 282878288 76124488 877901639 482879510 169896426 369640129 502143842 42564527 808762767 295430272 544231868 90715491 987765786 11156216 233051129 258980383 540397549 763129338 513876202 756727707 860070464 380423199 39113064 243408724 155685100 383212337 542904125 212941551 908809173 403996097 449487968 853114313 962156131 388037448 885632143 947164465 22219402 386316790 510101399 182072406 572362099 30429682 479754853 51052420 51821827 553914477 685878744 155672234 875881665 223991108 848319630 716355105 70947473 500014001 618525177 866054161 222744499 300031445 600911385 958090433 147420321 956046841 951543663 337264534 819284783 334697272 299816527 930654871 963266724 396853333 98589601 866011161 441055175 160685174 548008105 676542359 935670138 474488904 183960736 149130250 55321281 776699613 621711098 68490471 374413489 279752854 367613239 609220551 440601626 359734979 367883956 813161905 912601451 306234118 144692424 147544639 450476420 143660020 13601994 274192398 523712781 756559818 513883519 888504194 169533030 645702150 44717681 43032615 84781186 24614245 630163688 773332336 112389801 95716342 202652365 428893607 421277074 366159645 554452303 982948285 383552466 182687869 577537084 437021474 211001897 9970665 346738105 159009340 664005066 196095398 20246242 443598137 241504936 395722932 282798038 242991469 145609032 95339864 507775725 437050432 510024000 192781583 753469923 465105771 190339101 636858176 304756055 689516137 934247827 854583102 301139065 347343855 919134493 859092819 927079158 905174132 867532709 875854314 473671581 927129905 650834586 910930380 126455110 815316071 873893158 830797133 523318252 680523511 935024380 100226251 611733002 953094311 353401297 9048197 529481787 634525020 599747187 548868091 496819484 900140925 656516866 297739755 574639232 704044712 386496856 975772502 922662074 599186600 177854275 483796439 465560321 941140732 656308988 10257954 656249440 129234771 896351615 798081606 860564693 373499765 18435071 479812722 883210314 838142725 295272661 248982973 588344530 246534094 757243468 425039897 940280286 386121078 326647945 500189597 315288722 726109527 283663711 148559255 292154048 558185201 192862251 881227081 928775262 700583231 662780868 941777551 355285711 571409336 506741010 777830128 197848991 590737423 281508163 814865579 949755090 672620057 67890266 208269245 417233078 31314994 729366018 775348486 66352615 577310762 354911861 695349099 993887157 616007443 364800256 444045314 139408204 108382102 915435063 866358832 990488573 998836523 611653813 563790415 543325196 224240743 685950512 210253763 764798216 458447772 656802520 957459792 788733838 248665328 547362057 915163343 421317373 121240096 126800757 614860914 18103345 900474107 477649412 163494603 438453888 984292187 140811027 626016492 783194060 969758486 795707516 893511574 711945630 766103440 561379167 969983980 323993162 847631034 223073865 417426675 770589667 813416618 246473149 301496219 935226488 603269192 543844007 515872020 932832538 978193972 802187591 621352865 854051237 235500422 832459625 188631114 856240930 332895217 26679506 821493478 384933165 58292697 704765607 959450444 202630498 129907194 781532797 313224653 101111028 843954084 454972545 158838010 940031088 482714538 95840750 917538369 96601865 194865615 576150788 559203347 746363337 241545240 430294923 713017653 444028773 301099029 56303303 569640618 864068469 973635291 267290886 920128397 826786720 357056146 208406397 420771066 816225931 445595850 242565383 194073483 768872802 56740885 951799650 357910735 467183132 801582615 660131332 944051394 889106570 991433696 803624956 963002936 474485229 549626421 268955991 835113077 637592675 25673173 751962005 222291256 454176317 165223973 142672275 831664397 295528022 75202436 359618315 395535528 675084858 735284011 655631965 359225554 644356000 535939439 810575358 632565222 657049636 698787055 187243518 141067828 87043104 146436790 455935521 484376972 756083738 604333163 707574831 746726308 299325386 883281107 536033585 683511839 91355301 403112933 394191441 199679085 259870399 662639130 78086648 253384120 155735675 808519653 672901222 916021309 911211907 755291620 48659130 493690716 123924877 582699723 157124035 398142205 722233423 761447199 578862754 361372906 126890004 254040309 703771559 544469044 849017791 143089239 337492194 843200014 72694377 999719790 292050582 203450794 355432487 1542163 754183106 957644073 781971904 143811375 452170616 791294041 177161077 804839541 850318621 397276523 999707288 865799880 695387299 456441376 652754155 998649657 624971580 42536572 770955698 214742463 702635985 907003765 385467340 618510801 813683337 257502766 17392369 668825900 216627318 35833900 251435686 620286887 247201627 538707948 704145066 962398187 752212591 323927511 421146634 220926689 292566964 37648700 377487063 529546556 305209296 783116179 240237417 516747270 695600386 898227058 92493480 807036519 829941486 957153972 916140905 646054531 169400316 400061295 948240301 403629507 224232334 580748206 869312009 136328298 378316168 356838813 177023378 754011985 334342032 849449402 721465597 873425868 590604212 685641759 458993865 89211208 952199885 328661754 402324947 274225549 124000352 590218789 836367880 525363722 356743138 205185710 315764998 458504388 443784725 885734093 653184648 794810780 274068312 494472874 902903177 402749286 364072916 768350784 777101383 652635202 900059552 889795684 387883938 382138866 20755778 864747187 75815484 108428653 287647486 776721575 999177249 959489277 555292584 84552132 876753166 809813836 510988540 499468839 896500816 59200875 878736213 179153804 398676487 650946106 785905329 322842094 831104875 322283743 125130323 333831680 598533837 980932571 32562817 710255125 196541822 223251493 968856797 548989998 55569840 42278694 365242724 528298379 114362305 477002045 480305460 669643262 42438343 670151755 81824585 757693606 953168052 97708606 329568320 29644005 699310718 607955689 240597559 562573616 10827690 227139069 266430036 130718336 600746138 491727858 942375077 544903382 33768048 203319348 248181809 821994524 210881179 845162831 678325153 919557579 464518868 316105384 896610119 261783694 467391553 543829919 523692355 651702898 155303167 118695154 600168544 182644187 935322510 566315052 676136356 716463402 459212690 813057178 956279198 665804760 940059435 536634924 994893537 830798682 307840885 182973607 645358610 143335412 76864258 518344788 93210634 530881260 130878353 886624016 185810959 527643451 307826336 218119164 482558126 611589820 257625458 877020578 60768109 587655133 665478124 503828126 875413545 998819988 573587627 240198296 966145507 56080590 375035080 663136283 197451556 702491404 343158632 34221833 747536391 80549288 229571851 555566363 584549914 715061325 448440980 950131466 941689154 87102032 929233099 233154281 38248047 162957891 905792452 257350197 748782502 697995795 274056290 382786995 63435308 621463849 658369613 710139128 298579188 553515853 841571242 157401953 218079842 775040713 400152582 272721782 683357708 738903324 307960513 379746010 314505046 353021189 623826788 719187374 104800334 478346798 523936263 382142839 7515843 944389023 886328269 93988714 498147694 808259940 550144555 474144411 240168325 5042917 395123346 879424965 896655908 807178382 744922302 627496624 768006254 659788110 749580779 533810988 761721224 698153130 351020949 765426681 833031738 564910529 454129858 862931629 618494975 202040523 487367190 901651004 180099159 396540945 750527910 358147860 899398579 759797598 627614988 418290982 23303906 911046630 904140881 602634081 248882619 532097406 676174361 31141104 91836819 453485138 617224738 253952262 298490820 586300461 758698395 922544981 700871141 777600950 501991940 823698700 488086739 427072969 6785297 577249375 65387108 349529048 321486686 208924641 125942680 284939024 446385327 95215824 901375804 335275095 365481964 345581374 5800216 669847888 837150790 829420571 683349102 137808107 229535208 866214015 254756795 29808762 886483678 703309700 930568492 443307376 608283323 231698309 128753745 725952438 802188660 13380140 424484848 52238380 15983868 919593373 700294528 955733193 496523530 363657054 295813077 112122850 740289923 233700649 220241263 593159364 940712929 648044458 763119759 793061905 42840673 168343280 8101787 829331425 391289898 743539116 270971233 395436747 697936405 989800980 237935601 385823474 83522812 786808687 473707636 251563026 80035312 512511522 931849387 456990255 59365622 42229471 712526792 19834373 481987618 599648918 115368416 527079003 39910097 136230061 701726838 797874392 108689545 294624436 550966969 462494622 281598406 349661252 304901086 478426206 190460423 203154273 23344920 899613393 496262 874415236 876594944 541565060 549120343 757815972 817811455 673634670 605897268 894137980 797031836 969750522 386143270 279115619 437465704 151018241 889547200 767655313 779636030 841728452 166465811 419416097 621471966 389998212 622548123 129082788 887252494 137190372 626910358 118045867 454844954 962435961 209444794 42910447 985857873 131452948 994706888 510118335 467236544 439825104 79838786 126655324 957418837 539343243 987201470 124082552 208331496 677559535 160621702 637758604 448161109 344121638 497384391 400380994 645034021 478306214 655715709 163385681 534392390 923443085 303404819 839755455 89632511 238215252 934798500 104503247 978532075 276916820 921843977 112156011 668412955 400337167 804410978 921496051 210210334 659924906 865480137 283203548 990270177 100682770 303822654 580679307 350647303 450928464 178133262 917123680 140755740 874394156 853496109 8130994 39503005 844299134 384463698 75082126 407570912 163378263 56000713 136476964 845540483 929988208 412388559 973489486 103685720 634014049 533167110 485082914 576223046 498878745 190437529 16156769 956080783 46517373 265643222 892158520 753421579 483984949 469616970 851686470 53274746 44424386 368426966 280517252 725784528 615107104 757060019 128217098 739816522 958555082 950597149 51746050 582988325 910387572 443897356 431030116 359113498 369923350 521586200 305664156 80695121 356979650 148658952 121767530 639809638 790843904 702699312 250562171 203722716 15986782 283843121 679608387 62786431 428548672 834980555 416349545 921005018 757118202 159376748 118588492 336433075 684472348 615107921 253026332 163655276 741447628 712397453 180737696 921022241 269954849 457360432 444192547 794245889 593337237 470986267 72837045 846093459 289353481 120043241 218408398 108969958 605850304 70866777 26105316 990256254 527408344 109542148 239708808 221609947 724596553 941231916 942236922 145213405 493516545 651784607 178528164 61429218 579619317 925079376 335438615 9016008 20991222 4158137 658888074 858930076 368908550 377066616 216540652 128499884 194632129 115120566 571588546 385499332 927190463 153192934 595309988 306166826 285885546 157020249 46470455 490123453 363511525 864346652 362083535 542100344 469350302 95667026 292925423 422974914 568136663 320509093 426090087 900274364 638585475 971777810 235024994 920168432 231581639 53841993 598411721 110224481 267814198 267238072 810264022 402532776 972337763 240287950 25456184 780316223 855658441 49925300 490913781 128471605 813156902 276622820 821614834 417119380 761724544 401301023 279383318 466415891 999984090 786684585 383472977 555558662 808613156 98121457 778790278 859800786 473489541 414830596 286270223 797203910 36952091 661051774 245150631 553014232 256497489 263800268 600957754 178648168 623058903 38270815 797918015 854371210 94459734 115795851 677735231 303034394 767001001 692341078 565641629 555058124 930268461 935749627 816974991 579166604 507727402 405003659 408499410 593029186 768656479 673000512 57318296 156912774 982816464 881896180 104843538 825739147 347520519 492574980 303009831 601027050 658968474 47779190 913398511 240175609 858540289 794098187 579065666 434273335 267908103 416918432 419742420 621129093 19963996 904550625 303318144 501148217 685830977 710736702 381652712 186986945 718294564 695234240 705456473 158978599 434671602 882700007 979844755 363310479 541549979 715546203 269945179 548122773 573763324 375781963 965245658 518181649 667834180 482442528 648181759 518882463 443634020 810892443 627453943 98203105 306223259 156999795 379305889 445102802 648871230 311694013 177448744 887351374 477368479 92343617 776409017 486122419 127107457 592898590 432296426 8639374 705892527 258927295 623352943 521527766 215277909 25384556 238062935 32725353 156960702 448347472 188107211 617650957 425732295 684974245 22416547 970954174 52020483 437059549 211333578 136296334 467653668 756875206 132094075 220945972 667316330 312244983 855495243 182209408 333112167 885230334 360924483 799744452 671988056 385130179 954630943 143533813 127423616 338625669 999069399 568239303 351963020 970455498 47316820 34743255 975758517 299624317 190506307 223039508 743905377 944149899 522988750 492126174 170494496 556505743 421219751 711773982 845039020 287582966 562643889 583373300 852124212 389808194 996118439 846753070 22544684 96469576 527297845 733866787 258267757 354687173 183917333 996463550 711144218 353967055 669168561 574702700 199949771 814410767 573863127 628620007 352475756 138993252 676138339 828759173 676575530 536675035 559119923 109248593 145543634 151053489 323782213 839175736 232057335 75766946 899553444 593951071 277775913 816158137 206249513 774859462 162630887 987687364 593493198 121985515 193368815 528935407 247268595 738449626 398926930 502632502 9763340 186504682 306375648 340550234 242010559 47601184 944324515 885881995 491910309 922009839 432390203 94651376 697644771 335262231 53403683 372474915 744212518 756067063 358305021 310881881 905740184 42420594 758236570 800600378 442028696 5115441 313670418 276389738 724178309 535185741 409316396 199880260 11817198 904164920 2503638 526994874 894213126 368728641 801016529 902451327 534031148 891436923 697626228 193906757 599108364 814469173 902048502 90019647 635046012 533318808 98665855 749219356 396347898 537333449 952500098 96605917 69806498 69454357 765681986 742066440 191644137 922625400 724989809 636267869 990925770 302751153 635297753 62028143 524473245 726071150 116041868 360473176 340615045 739968295 851394923 367040259 983000866 365905135 99980236 936724429 156687 400722207 886623550 481106970 182728125 257844677 91546896 427074944 932911963 69230548 661833655 3667014 368682719 710131083 102754170 797530250 315396031 104627239 73744504 98646642 991986137 835241845 625245581 127866271 893219863 632461712 414927738 772510233 770456688 599714742 728507633 298399384 313053595 338585098 407230976 190583629 40964848 71768065 745949215 245468467 7582626 985635445 25719277 629249258 368734091 493199166 73440076 879083059 589133359 534337143 817909961 433545222 419578006 835439986 554197092 733437923 756494889 14717378 746304447 897096654 245645836 294421124 805565343 941077627 168287629 789869845 332925226 376445258 601782149 903860283 67331571 467986835 663762879 479328972 337668363 87374407 466771434 471122202 8497515 361383585 677097917 785646393 326322483 184276483 270552 416397235 280093702 152116251 903645129 678158263 501155834 849593424 550737152 756885335 906134285 129822517 325167836 551720964 909982186 839254594 765637330 679912 856028840 575872266 930426690 772961766 945797077 845781125 772903185 246650193 136888023 708619387 227073019 676293001 67866564 878731239 434850104 601978122 294723934 965647691 490243023 459778156 627164014 80234115 761324826 834714232 610726159 135397890 287292279 682220340 212573118 424486326 533258581 915274140 43214038 10794518 33015098 847757049 166045647 315969245 479705781 105946986 770730153 227675194 770806730 577760624 968749533 997232269 705163176 636195356 340652397 673822759 748658942 937246992 291749061 213839201 832246834 146693815 8400550 874734507 850103178 681519631 782772650 822040738 144614300 853067820 405140555 992902318 72732156 701416707 940721537 547749156 454803415 634308405 986889442 784137935 834411766 21679219 211186046 558841483 89020225 147565551 608641101 893471680 178417646 125790749 960968471 653403681 725086918 97202749 841239872 676571013 838446775 763766009 217692935 255761816 936568746 328404810 384616777 917143875 72594252 974491845 175485769 566366911 533839797 738179455 855237175 783378060 391176889 142061131 190612541 123082763 124387316 885002673 642083393 699373769 426610640 723148846 770577183 999010430 561007749 312322844 136549453 299827332 518492789 919407696 326615272 298754360 699232343 859978997 810419904 422835265 299149286 20315487 625966786 305086822 618012710 654788534 94937609 281839477 481408139 182171748 96730612 625287317 17984295 603469379 886566117 409846613 173762536 242470857 844253611 942351441 520083219 481581375 214072169 687857983 654510369 632739465 335536037 936880680 208949187 177844790 248183101 269260876 521046925 312980388 821695713 815067440 869750262 463749620 728265720 232411475 334149886 185734461 646999932 28019684 304113870 615081962 53986314 597687022 230945126 150764350 746109731 762551785 131603919 777648513 751483845 209830463 734818493 28970119 867127835 842266194 96620416 853477609 641410484 235122118 358938076 971932790 421785854 808586106 597586564 379322231 321221838 987390528 270422090 742160876 464172493 537378510 850533992 232067416 294030015 253259650 316948920 767964136 825070305 123755498 286659015 704837026 340956586 658849112 335036231 506302717 274577412 750859675 766251898 105972642 566244498 244432614 432380538 894943193 199210362 504065964 465251470 280583194 192943036 924195521 338740784 405512709 584153936 532662194 814315993 492965966 787015174 280284924 873746343 63582626 218802710 257900351 130067588 94420148 858340088 539113513 221828216 216281863 271405364 297379336 431760152 208131510 34030857 7702827 37143818 636679173 143398780 540093187 109934681 812761584 225855985 363168881 752768096 135226519 787306456 625131671 278569716 672546086 217515865 691047521 294445820 85053736 821403755 671856491 832279034 224065867 691046415 306662606 818740087 289628986 292819047 514194194 14570912 638424642 717556378 775110464 812456574 959617056 976320842 484574211 753489866 50708912 540067693 99516584 694482451 507669698 230476698 7659629 182759374 630233344 568388011 331135443 891266358 762715273 476286354 428947044 403433458 605900869 40741346 251567949 358987955 103925145 902279646 505136643 187660495 619718583 267913598 818445691 398474697 155831926 156914816 427059991 163259847 425523076 990474235 8875054 295494818 824012366 700429859 993019694 419119954 299881197 257587230 837908360 542984845 485724988 604359331 957492735 916706131 245991495 215174384 693592856 123399745 206663250 435002983 169921320 698697027 718042498 132862671 487816795 330465137 140179224 974984127 295960497 900002858 235602955 317761841 271174096 731138550 389514571 960622128 260907926 672599946 83994384 439868845 249268982 16393531 351094499 433640293 763392678 813760098 944566878 251311455 353564873 936604902 122814504 251445350 951362801 626648199 756391433 330279581 826327282 597483621 324186190 380192693 152069594 786035270 302467424 755488314 328786498 201727078 232835593 128242108 382939788 38213016 248326336 582191032 298956338 97022898 312796973 139194955 321627810 346129185 791641613 670007795 396331822 691773166 318825112 520272328 709933052 800348715 583054713 611878336 18112831 514966251 752220777 897557599 918944171 868013709 986239488 400988817 743931279 250239771 576320996 339216385 434727415 90064980 435115539 253697975 953231414 7049650 568923214 999944819 670557668 901193570 223964796 168393553 821961367 359126522 169511897 789885610 5383169 463395648 133228287 491247973 381847670 589893117 328830497 146036786 638359621 608254012 423961385 513661289 605631778 69997702 57683423 608403068 672797850 42248513 156889197 46636801 313319494 38947283 199806981 156582116 371195307 580140382 58512894 355978826 340139666 394329873 153882992 207634055 866541180 988554199 561486966 824813132 210500130 652015313 719965328 209845401 88436843 936151482 128445554 155357796 534279681 776716599 662895274 316092061 514077659 22080843 288989404 170076850 587878578 811688981 695581200 987087492 530635114 798589086 743486140 755824028 913003840 600645638 878153860 340404709 480777982 519758113 378015349 36907167 573196345 961145675 652245728 791662434 7821967 641288667 74004803 892987869 543237114 644312974 14676303 361502180 965227941 456636283 127928618 713138279 667865567 851167903 968030339 891579066 237888309 541037808 327194910 832552354 451156448 501961712 212099937 454946217 963253039 993385089 271423428 519413374 984296845 729271179 344198709 832729679 872842864 50639760 633278890 990958153 416641965 145433772 34828701 870278839 253324104 199130303 635712110 794402696 768698152 166973613 192538098 535141628 652918282 318356974 691555467 285841178 642666912 999860135 952272577 453215953 624973519 815556049 991306169 510062562 877547518 826190556 772305058 664594400 43670814 850760319 629557091 132967431 712042422 476705818 901108020 776908888 673194034 550624220 457399443 544501225 398789373 148585500 981801382 461242876 395316938 640669543 450888712 445432909 624911723 306756208 991990100 695558544 530089710 49888872 521955815 900848982 337931953 184247387 804403759 527687206 893637344 787071514 476273816 288084759 590939415 908058584 885013927 468869373 444999231 850570813 718397694 672102011 425160229 73740138 358944021 471448883 615873059 620350671 427707803 932698589 86590972 4774375 805933062 187607973 21509665 667160028 790900800 54874647 227018448 182832118 180771586 737302971 277429739 723965974 219353368 21395075 14497814 43726840 454005220 749460391 200829461 548663442 380854068 557397192 896923881 624349398 425243912 814945802 92980941 524809256 117822352 834621170 907830206 341312339 326899187 910421864 797634670 380568242 357448824 357864593 763509990 448399043 687409447 43740796 690101820 379548166 688480979 825009303 553748846 676149566 818816600 55043497 868880524 244682734 576289779 166433387 537553739 180226878 568606022 162320363 975274217 707582753 498966493 82523660 582142526 343375574 382807591 140275409 718793279 11295419 486434422 165677299 509434686 121619311 143324955 290340331 314708456 252362681 510420816 940680619 44466977 786428506 868623241 421384684 438418118 761430255 464924327 244267052 214777539 283229829 85727161 155521637 266718860 475412541 922599719 407764174 37681607 339590032 924135356 533643101 282600580 415161329 985532053 858880679 63013069 386911827 628353709 64431073 456545800 216878144 444084130 34557835 607076924 752357565 439523853 873768269 447263015 569164911 82294719 333462610 449157134 263499521 225540670 229153707 764641061 206272778 553141927 69134291 882836178 246752455 933597670 47169689 581930094 930259403 13781368 256890005 882700374 84021076 515343739 168675098 248400195 185869914 666636616 824470947 960015768 242312019 296068048 161262381 499068310 797524634 797300854 759843098 295470241 95948169 163722126 389243855 616130456 901516809 799228896 685724944 636643650 322162361 876645821 255747774 4997008 676967369 289590911 858249793 680179190 220604822 681621243 430179986 800535871 90665401 754719927 267571810 779119776 442015713 848809974 20312505 472411220 522612208 861962719 877175259 561924254 131295016 693075053 188374834 716891041 461191888 56929718 565326678 952701042 375126516 919167336 502201658 464888795 147948002 263538933 49122359 528740028 898739984 387269789 812607758 32378218 469081246 156896856 433562406 644255760 736229546 324827034 295549552 174939404 717886723 486226000 801524757 47621827 176183311 727553589 985014147 65135581 113704102 82592787 774797308 379299101 692409898 380683303 627080306 608797573 343069773 390556806 281381743 740416473 156040198 972854819 400120236 369930388 387610852 89253207 201558120 225275954 208444858 248608777 660044777 44853258 761952947 841275136 17564919 326272695 346234431 618558501 160997962 970151672 418865061 797966351 633474757 819879489 247975350 132946938 889089212 235133232 422471051 396505790 892235273 751053177 59834053 252441467 591988858 412453275 356541780 536722852 377721696 971162612 36971650 955885128 698806923 990445740 592455154 774521552 418582482 390194775 241068958 753201578 322737481 897216584 742812428 710649799 667524210 479384698 618118235 479362393 750199958 112195536 127410660 989590167 684862462 365173565 821188857 298456097 287155648 582711174 683126278 993565864 289591106 389536154 143864199 429714238 739709496 980529167 899363649 528161535 592848591 602574422 805876838 674944215 850025177 578398049 259520406 190244103 352971090 209879527 490786347 976183362 537476972 783129563 703252823 569483339 637742991 499795930 560102381 720449273 35703016 732893024 242336970 597494489 620116574 211447074 746332849 898725933 551353846 119452893 771226014 482353379 790375944 843109835 523124787 277249977 3638189 315623650 258651032 497708626 115785738 199694774 574764938 418744526 720169832 914739293 471698057 828979704 67862462 867501771 566351917 341907532 951156778 523282965 713562926 571498160 499563982 557221229 950468789 218596616 747492678 53524906 789972045 686220601 367971983 676125728 277701283 349758286 799367227 940695066 649964085 962394712 987908760 604968720 916986191 507048893 648274544 380231244 730154789 361649434 760094467 75047990 206818953 1583758 841623856 196619546 397613260 419297168 668721907 782521119 628871847 252133580 962558369 950894533 510200854 994945792 720745139 86525585 12096267 515009894 679575091 920598887 117948056 274891081 665543320 538487107 985877159 837817948 484541719 530433867 186106927 832309355 824168050 187551919 102456175 209378005 80740529 463109044 537361488 573477996 754295539 285109382 704414029 233738418 738517870 915547222 594433798 471698655 449055685 985206251 810469779 969125524 454488513 184420301 670140731 903829535 148247278 444639997 952714430 433278247 111142963 410927195 913591970 244976409 378140660 694469450 259005760 442446969 126638525 914426266 255610467 517491272 982147114 380582332 284156977 666772439 3416358 392418824 32905407 45882027 969181403 866184860 647236240 152679355 247391497 317854197 686263775 524783632 93688596 990685909 519161439 609020866 1163490 303378075 345943585 156240517 436799111 412576251 888818669 141085098 591110075 441410392 768853893 311379546 56698967 927684888 281451898 55605580 786057051 530581000 797572979 823639875 429468354 796182291 183579021 495808916 920236050 163966646 730801372 908769118 720325085 846020076 377554986 511413369 940226681 372025949 291297551 537348031 589252723 328559121 56169632 151660790 300570633 79238253 618232116 358327651 651817306 601622583 751055860 953958865 989151351 915438872 145157219 394090471 491428555 883595223 955018890 239366739 203843438 52156985 792827203 769434621 727256609 532431374 187646316 399241788 701861302 569289569 896571328 508814665 674684170 420992333 60395215 816732793 954886720 601993772 879930885 350736930 359832562 94371303 265086799 628710917 17846970 352380796 78276305 539848352 545577627 112743394 190964007 667772737 645751673 588645811 944699394 104904100 688041558 481895124 803304074 562572029 705295006 56291086 112029432 210694582 276426686 36378866 515653735 554268269 430604912 110369113 833169412 761701258 767064301 754635941 148280134 473340591 837935289 706188181 868184762 688939409 535115871 692040838 572078422 592584826 891972827 925746640 830360515 994546161 462510898 582884373 204346421 463403214 893228953 195919681 964650382 836872976 430658650 769622097 502452309 669240698 493337889 142206661 114314671 572311121 705398475 616445525 540647396 899083096 127453458 131751322 492893733 407107029 936641104 286890516 712027473 950974483 568544995 171449580 766608712 655175581 878834290 148892191 402398753 492839962 457806643 406387139 406490661 123303793 299166404 523871619 356399668 640762517 774054111 880176176 920380876 376533633 537143245 631426767 606528551 655291737 781279403 944860628 634772096 990314948 592648273 279701458 92688828 555938205 981805814 761970578 660913127 946348591 24434259 735663589 438421875 825688760 684292952 761414012 972633643 105290994 191979361 441554505 734937277 825324668 949794359 132359713 36613585 733068857 460721692 627864636 821563079 991630106 371299407 90013525 258890 736716735 997318151 963981724 931388408 891486737 236002560 806740759 570790677 242408479 321774313 883370913 59094896 724588466 352555139 680905716 61196463 886530047 628129398 575941361 225086629 758930525 449061008 745208908 226468232 558075357 952142812 711398742 931353834 598986906 971775103 91040950 880391840 442182794 952491818 743155087 38899822 442899970 228875295 556951446 25105440 893660311 326214177 749904923 954995793 822909101 546871769 660995725 780120479 45559668 40285101 616146530 449217921 570392296 419108367 936146296 991628507 527042581 75324903 163988239 465580644 182712806 95928940 693544815 252652053 873984187 138224744 172197395 500084708 702274420 993757997 119084601 930197950 87538347 740079195 549297282 350926557 569033210 136116836 624769790 136507085 789551553 198062323 450439851 920275359 118523694 765663311 769953239 551324889 318625480 218888139 307467189 660417489 149049079 383733369 821891030 195848363 917763695 378148948 271134066 606358096 312401288 268048248 791810102 996915771 948429667 666164882 984044174 682876753 720518544 62960376 397833521 971111436 336064143 837930586 852165863 937210311 888978126 586288979 252661052 880701384 654620033 707453341 883586369 821019673 84835217 330296050 885045495 784347297 406388737 127326444 854230588 29502102 328194193 438177986 962981880 333642596 65279809 892515922 694750291 554717728 566401022 630444441 771406722 29170747 178391041 470331777 309153329 85459551 740412689 199309580 905337702 263378182 717378708 292577883 200496637 124512654 265541418 335150611 899862977 624972321 506922471 352606038 320880864 736952628 404789183 735332720 345036411 245653809 270195065 600062288 147603396 711453245 615375897 449527531 652944993 955844974 988585413 446729215 586138729 636870580 582629004 709421392 554873518 997864372 811446729 453316038 806959578 990592206 502437715 939678508 542138110 702214529 507763482 901817376 979452734 774719097 553987682 704396640 674702698 188610340 418293358 413080928 725453787 67192618 221668148 543535740 748084090 713589572 884555417 178129909 496015545 267896087 116833232 58242692 174133573 173753998 470495942 25711899 519712792 491302617 454339407 492727773 877578172 867851499 705203749 228515890 964879266 632887531 401509149 752457735 354434964 507558196 160583623 911330007 514037753 738782072 486064968 125094702 544568990 189343664 52044719 619255553 893073910 153315829 870371500 968000979 719219556 507622320 796791888 970548887 284385384 941958697 140460203 250216332 840003814 826917709 922672732 775288753 995751158 755936721 537890037 238618038 268763299 19005164 138495993 149110362 202842539 678806310 387043845 724654461 785402786 499844457 348840032 867539363 267825243 261389168 172360497 928248324 619029470 801271512 461227617 413556265 519069970 65237337 282574268 239119454 658525253 108388419 790983262 543928996 502256689 804315230 298190092 595139436 203023487 270391512 92055451 226382946 49890500 821953229 47077514 185730974 79009862 162229344 810168594 755989787 586382790 464245189 488736543 508355126 179523110 410035447 80919676 323030027 61477737 984213369 299529167 772555744 190028212 230728124 477125760 131175124 339314926 797823338 241102900 244950470 495418414 80679315 822646036 94464011 623485679 537567805 778960973 790750674 58382864 150021174 37558218 62870617 901948197 889471782 472986736 371191740 486089586 587272804 951497253 160928896 758121222 272112409 818905629 692013402 467457979 424941917 77137040 19863090 752320777 939246905 980694671 963019815 529353871 37278620 955288598 687146417 891661540 181812463 133349371 90456265 872720354 808746097 197810734 451085520 948751893 176906383 371738133 967231463 754565876 679165618 959511650 210107262 234862560 929776183 917226275 512542289 40663451 989787063 73193934 374640323 998286423 108129547 487526159 47959803 461636523 158718346 818559512 867207413 484246487 89736733 444177822 303935673 372215599 200055723 612116054 716769810 313181628 404031258 685194621 339366483 423396447 742805231 455374075 726513709 594730319 742103555 788594465 995053162 441029967 484360532 192597928 428816343 60205542 628647477 271076028 661607894 111189995 917625146 465471742 5249209 965165189 801102603 406615005 679519549 336398544 155852729 603409575 323914653 864473428 279215438 74914371 998086763 333056353 608520960 966402922 586089025 943463086 734340338 522425652 127339396 69575086 251176740 210576980 142518288 303247463 553686266 176275311 477588497 375652741 549803936 176884934 183139588 975860002 300055185 716502827 741185038 978054155 99271764 821140046 454695994 783590430 199183019 290070172 51844730 150614836 172515313 693052812 747671997 757406484 440793517 432301566 860933933 203028494 565225419 776819786 956250549 788100254 157793415 11697019 538084243 28401299 831804 22895169 706367637 81880644 994870868 282649619 919256755 169465916 939539128 761626444 573575270 514718399 892920330 789516808 415242383 489519563 118198986 610432621 605724369 121220958 308113727 24942719 331120631 638646138 524526549 646962393 515194138 829287771 810427129 235989095 722335969 217572047 889014985 745072345 247516869 633122846 122006808 344657158 85784208 684405988 713806369 939477144 379730084 547613978 451541755 765074271 529741652 482840330 488850442 51329457 983487660 980646192 888944793 623515909 448686404 221924021 369936336 684675121 422212407 144678277 777345385 335048040 21126277 209384562 902301691 14331380 147568144 956121013 597628026 646689709 176819209 994606044 572616665 821506254 723354377 357484788 508791576 179924043 184709444 630669739 430144203 451583796 979083507 979262144 760340062 38747115 784357761 341501909 276202525 935440341 249275075 861133888 950778014 612020580 929779425 286734442 138935117 801096516 45404442 468297959 672886677 198462455 550915896 817636851 418050624 10549387 267578782 331654817 562694470 471137491 384824989 802713967 885634512 645313466 887485831 387652423 845207792 183515659 17935436 620018925 711513987 536217875 847037072 545091648 351258225 111128326 933825664 15572740 520787247 790299989 214784236 296976509 50322077 112803332 699470747 352588478 396777315 847944925 777443024 878115334 70683829 908619277 448620319 431963946 281509714 554934497 429170182 90023668 68456875 617583545 472437711 784780677 780584433 382682625 792935488 630799508 107607712 935691782 344834303 26111191 786445640 723443594 12121166 455879384 697184047 589949887 256680014 222254809 955602922 795848418 478369871 511500434 813310549 163971850 615426988 621874159 252540598 937372536 843983215 197920060 726262538 973637365 384922821 189508496 737023206 396452652 497645519 856173734 547717802 892228065 449840464 111224591 708959083 388917664 879355180 514911596 811783515 138404122 54881996 277944445 640926490 135745658 882322237 211188040 167196659 679638522 451401168 616746615 232521248 844464973 358355769 144044338 157917055 643519801 990751745 446973089 449760486 423963533 417241966 558897233 355566377 141691894 16769251 621895486 337918834 101943491 694843946 711193609 793363200 293275929 501676053 765025705 307001112 937829057 167737462 864704809 285015708 676704925 109175611 893058087 979880382 692773129 130787987 279958851 917173623 363867281 906490547 599670900 599132685 282523397 538554547 64408908 976083558 830837364 61682813 449805386 894140813 24918205 220595403 793494770 922611479 118514177 305509249 737939147 884999033 198039715 174499609 953181962 905710950 79587304 688027059 144120685 572531340 888830056 549263262 506366849 624802762 506598509 427887283 777569467 996166797 157205665 573547320 694850392 680755829 803583293 766696470 312936708 227712944 544744394 485983440 811658247 869845720 669712613 757444010 938504752 730088159 931325973 523889219 73155511 232667023 844579851 763549568 318567306 984713589 263107646 129023900 1897128 773608125 647656035 601602248 216118533 663490568 544174742 584009227 804648336 631212140 298888404 312374593 671574406 282073774 840673461 922793387 300184126 922373389 1886795 490533758 774377264 24083075 701410384 338834106 537392563 632823796 358703902 638925894 471085174 976367757 336418619 367295325 476937310 273956717 67203070 101980948 108885555 208855857 871317497 566072972 697249195 848637646 611201334 413932030 484798506 70435325 115156449 969340936 491954873 954581890 180129384 489652934 886592588 587959556 708613523 497148878 671592029 320216558 329031015 836970471 997783034 307627054 513102723 571704331 317945498 439252037 588576906 947339788 980170375 128009893 306291008 717991746 738048593 479270058 722528130 612245351 382182051 777611209 834963134 461321422 90628985 211449121 530305691 857706335 801704300 918883854 21546719 385925413 370231363 933507524 270188760 405521433 155291157 947975966 360656968 209561336 455427234 670043418 820877491 655075232 200606917 604471533 853314312 3534841 67698579 829451494 798644098 816518096 853116021 15114574 416475614 825772887 486812945 446841708 878260764 835245144 201658126 458342231 548245984 784966161 509973679 559571168 330483384 572009624 365905025 986908300 459145550 386918932 278556464 105838812 380375293 152203215 765402612 637053801 133589246 878706776 263503667 488469079 543880553 420841205 436459001 375759971 916044756 946501592 10158515 208465887 262542289 907184406 95385862 267364828 17002092 610317591 754973125 301685176 863236503 781468836 795836892 559506699 887860489 442995252 652404207 729906328 137617001 590154030 735782265 974138482 297389285 711747546 381099903 882104709 228273509 438066232 202970619 951131542 17639337 196274197 538305919 658003657 17852546 295397684 743123763 971063039 22463953 422613203 385507086 243762053 103624151 194622291 243570396 283795138 87557024 768299440 470146335 794899580 739774292 706834184 179961580 815034624 570475712 245162797 946160564 410961805 115876837 545089809 341867577 171941948 986888883 215327590 389456367 438102367 345127425 634826653 281761907 824094766 157314896 668845050 936052439 831148218 49057678 265919707 252176182 195515710 232909109 870361438 118594683 574028428 29378738 943917578 912165602 871032313 63012961 73674966 280515679 594496048 61867585 961955727 609830804 831218303 227138562 842927658 552441693 235983817 761074154 578933853 62080484 862535231 390098902 557929531 361952098 501803091 811468277 239757144 592156980 660500150 860912987 339035298 570839995 507020595 417237992 458884603 971306959 702154483 196614095 594346663 995713236 101383554 491795979 137101715 622983807 905672299 261611282 88044218 453736062 943440327 175980498 317243995 793929097 39764486 606164132 374098551 563599377 203464398 135022882 84254102 544410247 294540031 897580201 192253819 564818119 609656547 83376126 39647681 196572916 686073145 719252068 218043890 93769416 183603943 20839917 615284009 988909866 470877732 681758935 444027283 999363382 602049520 754024471 843562270 313980303 67872537 942571837 631778059 378956107 585464060 534294409 697124364 269613655 760822097 949563396 473237070 785833642 570246526 7513205 355898959 788422695 959325995 810031285 464998863 457590888 50475367 220592230 297619248 410752179 814016088 792895625 225914214 830150440 573082038 839943048 500323053 909021793 251754728 682177021 578832736 601027418 700322167 635299343 425889541 740206084 493345296 696737950 375687102 784419331 943027862 311883766 965686636 44379460 560403711 704044624 43669495 258109407 340959244 886028930 573953222 64498021 928817027 861141469 323260035 11079242 263050480 405114925 314271489 885967339 585391006 904639063 991953172 995179328 789291444 147140370 510838324 91763496 650334776 687677044 743077360 633226059 910735036 380119601 63904075 249911743 304999102 953238911 254067282 26029698 523740174 938095163 590131748 228547843 114461523 949368204 608851101 815021099 112695667 444726224 823132749 392695033 524934679 898405316 568509839 48869215 572305701 324324914 705875433 825431774 23216416 405594831 700529119 336972487 12261607 587329488 204179572 481989579 426159617 343384376 939545494 708932122 143633510 522990202 900470326 906294279 80818455 461403187 765301465 313096979 665707080 629832607 222543606 974053962 78339227 53983424 647580089 15789025 194176050 969430324 724746233 939978438 331676797 294822090 73778409 163224102 536719734 838512690 370605304 573324593 177256924 314681318 625479041 662698127 522574757 5659754 735317898 413070161 275583355 625316993 88693522 297700026 994501834 6463655 801646047 823475374 914565427 820840099 231334784 257105944 853028789 228934130 725808650 771098780 759018121 617307121 827495001 380468101 656553387 915817183 967127928 614110049 533085501 2278387 577182623 454696950 647276593 978356522 566717762 253065946 169866827 489111528 28413099 929453450 292390248 445137653 995953215 47307839 22458655 279334558 209709102 319437165 810064671 117176087 733128443 727893590 753269265 5481809 97953705 147971842 149984868 77774862 119844435 956923840 709209813 108451281 180400548 340714503 772383000 311585110 267499743 468055416 105114148 596591314 979440315 523500133 295033626 37179802 669765678 117169731 996502599 855915965 197663990 745067111 526922224 403967553 768223926 689974674 940288519 782741920 584877314 345391258 532580420 474906587 411630653 739369743 636546387 565763280 165688944 435818997 436722830 57735216 982976787 524820100 759729440 359839342 568438294 950959881 420229549 624432489 372325697 328703571 770048273 125536539 39244250 241615413 986025610 613517662 901015513 573583482 502704044 164680424 288249048 453441158 486665447 811818363 639055489 967676772 911173100 549163009 594153018 886754502 786994583 534936604 93917219 103533711 339926549 217906193 724815831 375699661 588255104 621486801 641431760 579634508 570687056 363363161 278770222 873003599 867891049 120532559 961281854 359789858 6472758 695310025 36123334 946987129 566877360 903793254 547650968 589854548 502030631 280935128 694299126 835073672 904032306 518092805 779814192 791727479 895811986 977653430 924074605 347040302 859397189 836484127 796354121 715592342 914482904 65224733 802941867 360850484 912231334 215388416 83749790 240636166 352243239 108497498 177569571 109912701 864707969 973045308 598457216 229397251 366825172 346317668 105783084 394381971 415453338 445189121 518854452 849620364 125005382 400885473 310023893 126106446 698707763 794147768 736772776 54044043 951328239 216485461 505525819 153834376 180517912 447968863 654972638 775106467 483692913 968586752 475261728 139189712 490598178 66272374 465372103 791619762 467597871 23897537 960498390 101139144 713941268 599321414 906696131 527678875 334003131 572939712 281763106 545960696 284902041 86563347 146273011 862354518 962412634 799088594 201679462 688753892 2995509 555993566 236860154 432219732 560620622 846223013 569423095 857069313 360487718 329409539 972628063 797700054 221019984 526804830 508912813 316932720 840989097 949030451 933404836 214933307 893071825 299189903 619666978 436311642 591321404 692579110 184500192 726688311 186478711 17788446 886386876 333190780 913835697 482408808 100633262 967816849 904310818 524637615 188845835 303316552 204277375 800833708 191835771 78248649 92710797 771775813 298292294 602609383 204911335 993922288 269317749 403807974 605316431 500908568 862898650 941272401 656511270 93851167 648174058 61601968 346441448 214385716 341674495 165086955 77135655 415227405 748264126 381965707 13177836 903063532 137074268 952432808 8114348 782347255 916112075 547622152 469000886 110443929 460431304 961760211 326076021 774264757 817728534 334497801 557398802 791289271 965210804 104478288 976039926 944593526 867332413 253067016 888391928 693304941 816532544 466606404 456413723 694211960 955352077 749922723 374617474 522212886 441431114 252562085 582195674 886217869 988574576 233949183 322340466 60700698 885185731 716683563 967936381 448483652 217425934 463928642 787074615 717474286 101136757 36505677 919194162 104932495 936042923 203084784 779565003 856741763 218417698 132198657 589384278 247020224 497024254 313158110 482627255 937612565 871459354 120688588 792318603 109514928 377954023 104894501 58104843 175767465 856597572 752881921 703005352 676352083 780104430 324269964 680491492 527818737 736494355 16994927 726133638 939392596 45687695 825889209 98755715 962617147 403743191 104738327 3827777 954985712 532429866 78209571 768931616 199992883 930376558 979000671 962436377 471192379 779929765 285580773 59053772 126588945 750888676 583761580 991774540 642062525 413129281 959395923 915852247 250174160 296866104 59183370 86363994 74024861 17600798 367261686 137873797 307972399 117325481 440851649 539285186 67568745 629568195 452446843 674304884 729230941 347040189 935763673 417378955 151382406 285507360 498572749 606518995 563785566 921987900 270479338 185619286 954494731 461784555 43124054 916495898 511758899 920294168 356385650 430983 520311827 622809397 615269025 791272235 706115381 8735154 944975638 594600772 875418015 158460660 540080340 571089677 837822892 288037216 622619781 880207503 361818482 713928066 711856153 212641538 246555129 315403128 970131280 789662246 891137863 418328320 124516133 874615363 291313258 592466214 680483664 154348285 182371642 106057156 253633126 495074832 418383125 23243935 236854440 681789452 471715222 815791368 493102611 980451815 568928800 892460374 406580747 362902767 293591545 621766869 532340055 465363045 285918831 800617296 170519117 606788338 286043588 322047041 389339107 433359265 734621967 231124510 901797991 629200792 531670376 606880024 35770031 573992653 783639224 294888916 750420552 504479583 554689529 646389681 451222421 855759558 309741632 15447578 414994703 527700053 309728387 295476037 617170557 305918181 736211670 289392334 371846521 729562972 966366854 14744327 398429244 847045840 784678003 409345581 669347462 301756491 137313983 299378621 791271541 150690180 480604 318983637 443157929 131786205 725127321 833943869 853606197 387243639 507627217 956833962 668150329 392821618 926401141 42049832 166957078 969216917 336703908 496281557 528526362 480954477 915651670 145024200 587556659 564480018 271960698 684276112 123106559 918990477 83802400 151278442 402587743 112856400 81071140 545529890 864769289 570924807 314477933 359810646 675688616 336966128 950117365 295956369 621748100 100698978 182988220 779570500 619368199 473467971 947379270 543153714 339136838 905120972 104396655 480399412 330707788 347938487 801594187 117110728 15203976 841705648 198986497 51609610 319693437 450343664 313777706 308281221 236410316 169088221 596672286 818848164 959849001 542455453 719793482 644511190 35614266 219028823 750563689 290075037 300230652 980730723 362681776 6522192 869261243 370389014 388893581 919976091 539479477 145175982 489185530 733470878 317754058 464282008 698853905 183622100 536573482 370207114 451754663 715145490 818978303 821293551 18616589 148654280 734563742 879488582 396832842 591168617 479564985 50792400 864816374 598293695 888681581 390253927 727428878 307388849 491179427 119267074 973150012 152944776 888363907 428419019 142349627 284587626 322776999 301616085 830438922 17890946 819274886 547281582 75389710 912542988 400301308 593328217 153773602 617299632 644064237 517748369 758380417 314759929 347267710 320944384 600871241 974863255 567583345 932650931 433172244 394843116 450433011 630467379 178173131 646523563 780170524 521305788 874694918 847959727 587652493 562590620 974572628 65174570 190232622 306120186 425179793 188122196 195226111 219563890 729369809 917170144 421965612 853665159 89939086 65389896 609303931 809334451 495092865 637833877 519694351 392822425 240885813 916730620 911762929 457782553 356533367 248302054 917190899 703481903 310778844 257908198 348506080 331469455 308487202 599644647 554499847 689105631 306594535 226205109 264051157 558323457 463104027 502480207 682802020 347339968 997735355 619760478 920619305 421379202 310840300 679539835 936748636 669026664 115000414 895545660 90308605 780677970 404448850 149328512 133629900 887438320 784756128 817368329 498333186 664739286 263012651 13135241 705927194 933325481 401581771 882678986 827056032 25805949 264265197 115303773 395439861 789283347 665747663 331326202 296698163 639122835 869281958 174611481 838878311 34614972 915864695 567739384 671562866 721970042 210992539 2565192 128727623 547138318 155712503 165640987 226038587 801985762 496570168 848994024 204042972 891435359 774461825 884112523 73735983 420269766 864108068 804993852 365008100 215564181 871559926 62481022 390250861 911599229 559950027 631980859 577865962 191033984 121495084 231877282 261219893 417687703 411817767 835621829 539055870 438204434 193035943 279343357 164531356 136439472 638535653 36422595 724054273 35622812 408955020 223147941 547890028 853961775 348859990 886047807 560385226 828370901 552157283 649514767 39683802 238614876 994653909 304607502 438956420 203144580 150764910 594893441 561429437 556440814 412748492 748995906 829261821 285515280 188909482 896576407 816339825 459254050 193265550 862535690 472585787 861452033 857422209 502185937 98213493 928422746 472141949 958301483 266129401 256000091 919351954 866499025 228469753 813749461 63559546 832244992 172973108 25937093 532715008 363271815 663068883 889888559 878721965 273728305 493060637 962654973 690611915 793774433 692613708 474211074 332253848 455855851 983284123 878494577 246344941 325929652 923916723 420361307 514509204 425296071 220775135 981396825 462921320 507917046 455258759 927890082 500440604 805923593 763324707 180383744 255368133 755433375 739261253 689714488 618500355 741283022 729618017 141749560 416337285 163974164 236211586 630141140 631636228 519912935 87151444 782095388 658982238 51198066 887200021 848384845 198905500 755611365 536773628 234319527 154050545 928211562 46873554 339738169 690732513 920958488 637801107 696980478 2685594 352295055 118115697 994542980 378013431 281124697 870419719 719258505 115934506 1295309 392586133 89713263 42072060 532245463 760394257 361323053 696343972 572926967 607182746 719842691 419740548 505281383 910439805 597460487 550249296 97997379 390288445 994465555 679341698 975349494 212188872 215364531 945691026 596122588 252719901 252408520 831238067 103694869 456369120 94244247 618357547 761878886 378577168 626351980 986022602 91395630 393184595 40477877 745652478 892091714 585093921 170625348 272469189 907620504 245025936 389238764 673030242 457371574 734107094 135293523 191928098 31685109 193665609 957783457 83788083 595491549 626275172 472018090 983874829 604464857 339573153 771282000 57919229 100586856 466658615 427079802 348118697 699746610 261745951 795516362 958957069 425874158 476693270 819490829 6863178 970499100 646034948 145006254 383736202 81569876 267535968 897894682 500775845 478613910 799800502 218190569 746543326 864892096 324158408 171724166 237921434 229045733 444345956 319227412 347524784 78314594 301875189 945491734 267203247 903332271 17579071 123471465 308031735 962003094 306493807 706708461 931199743 656630405 904482327 200865583 390468880 599765025 698970967 889362939 313086543 652150488 961087858 460508546 33178044 545143192 323347463 879248695 970860641 121652459 861536199 127881396 824943230 83605234 72912452 410660672 899960792 298294442 633597180 797724158 592025663 877913192 41920010 62389057 999796852 174544790 666705736 874451314 85498764 297288375 166287429 861588362 202987374 44591849 973379792 949917096 927167530 49980762 905356259 963229980 344922303 349413772 708123333 825990187 820898657 630303623 635245180 28072193 327465233 281896731 803076901 121989516 822407807 770795102 685418666 26485568 80582409 256244524 797546478 823225764 56641733 883611396 281373613 406646610 741695283 254481674 195198434 514973578 423527321 620034913 441213794 538960036 609204710 690129383 406392306 313917638 948276145 131071962 969743294 713902750 418354858 120329779 21204022 669072123 766200544 505401032 903310929 38343045 31959105 382658590 319125529 692245022 338555883 408250972 423376377 119209348 80755359 180865153 290144163 698562607 496915132 372369631 573155618 439201717 125352093 24861774 965372708 311764433 474776135 188763758 64661899 774458458 533138268 48454344 678523905 639230311 226951930 776252651 287020823 743984553 196031142 138767188 956005926 237143465 923905709 318658156 764175610 887059862 815177366 989513399 787781753 165319850 889851980 954363018 291760924 571121759 449348894 792216878 611887054 678029421 394820979 660513044 767409874 613054434 126696381 218452721 322633272 569876166 609649752 888223960 539802729 946018889 593013170 533391050 956625101 43569968 502615349 142443816 776874442 551277711 985893130 667823797 750783880 449921758 633238921 215685310 699637744 420542943 381106992 706764624 418000202 539077724 821065231 112873649 282702805 346465520 143456709 159367953 575103923 405892013 645052917 254712363 978096155 675873816 247719085 511113814 103327069 813866028 496190311 299922518 723163998 156365576 122317355 179492900 601945771 111321771 60699253 902335797 666200349 860597902 436414677 847681066 417179864 762919364 964504551 959850114 570552514 611845128 375219690 995025448 702875205 26344736 820974930 653866887 649385213 882591942 457480520 298183970 691619543 9185761 433966964 189781696 457350904 443633874 544538223 286050435 577193594 536325861 413310513 359175408 242429407 356387015 524018056 500043404 222829045 437990478 371856206 785533703 913134155 837372417 295350993 952621606 725318490 101219075 220149727 88809875 707045023 618753756 495265279 857684959 579981346 236622417 329859239 195735507 61199197 781532849 317246925 944288644 789055354 577889713 328979556 773005012 612788398 829999212 439830826 86521009 446261264 798595826 509593559 144310895 138075537 767480129 594542082 527273509 516860316 731208717 989418658 451253937 387886963 697940210 42353549 156532192 179270727 733028302 321461813 890402642 836734135 264785655 249416642 483979728 866203794 748391881 259098846 938457246 877419899 804508031 36100366 925824802 841454691 47435901 563076046 346217894 912395176 740689438 722692055 497025773 907150067 203624583 128957575 697265218 699607153 654531601 159096145 685854280 167714196 244919905 658938877 467047425 506763303 661542501 918095414 710018056 489678400 488033328 640233642 125499453 462360459 590692404 460567372 56354834 202375360 575530490 652519953 385359181 204670654 649376967 223264865 696356807 690360671 966159150 35571624 161588128 217796602 24775281 886988936 506037750 760918592 89221624 529973210 231111342 759714476 991330140 404652181 676528926 444078342 489134119 72088892 468946954 767229495 73735882 882092359 109096520 596466438 55999625 227999295 851956675 416418936 300169454 880741767 552539977 615094968 572386794 371823967 208567139 976434840 403166468 836426758 274830146 542927907 203041550 74648077 522961955 226445102 776656773 138900537 564908629 538641044 535597329 933305959 177336867 411559156 149807238 375968808 36836911 387030701 355276503 22432525 738248429 246853478 453957011 925174013 566548274 884784396 82719785 98486647 171197118 96529599 315213009 149730591 515981420 787161263 494173152 580354629 668348076 494121590 88741882 123519558 967509391 438444942 683878724 298000480 973659485 73307084 644065456 998772894 884826412 390315226 880268483 937697276 594493925 399510669 963048397 1712793 299308445 272149003 616417608 782934789 768367302 683125924 356406463 322127146 484984149 222131258 493289345 196337020 781435412 196161907 511195133 804679649 596002961 531920734 978723189 610130295 593648892 504154191 848664661 915075784 843312261 459112180 570197285 795098755 138761162 896399219 944523683 720819778 688261845 897781686 833101411 628278607 816187162 375368554 383194570 389247533 305980270 164200560 810855067 859506085 704742295 97059403 292472188 148242515 38722081 423197705 622635846 420554709 365105218 450012025 231666183 395414474 295285026 20177220 944002912 323444834 563989152 179060847 720025145 110717681 295353886 528094871 471866483 262705321 280214121 138858411 155499146 407446990 26493179 851560598 736102646 412941208 809880281 324588983 150408293 185018885 283727852 452995575 945048432 579205494 471212149 556801583 761582357 236276291 725184835 652891470 82266111 871330546 481169029 796290192 927950148 757991174 17421871 245952884 394423148 812422100 672732125 31439685 123349599 772039180 66637228 540247498 480795807 827425273 782095407 976169767 204721424 890443498 491812995 2720342 204045463 922492191 571291891 263095850 34843971 510648446 748891557 178497459 156317866 757274084 869255538 2526917 618299786 876574260 899840182 676251498 650967119 135321099 471041723 472251790 935192001 146125606 680968258 55247312 17113209 247754965 242683334 595411791 880925411 938284161 114207195 841539344 870215402 399485963 347959256 868758290 494671427 44266435 356513764 291823924 113281556 109259190 422486423 309449134 305826016 944791657 312844999 118391183 742973116 360800124 261835110 134776334 27691062 287440865 682130848 189709488 479838621 823133050 536702301 518506653 692779568 666552487 343835141 191495748 457659116 881046015 298188724 78768494 428395190 77612062 42721268 975213220 157065957 608104701 520925468 68636437 865704914 133274612 238426037 725383232 191216696 850778893 68044562 313191127 175254162 323974676 807381053 64121213 359377274 628830337 437655434 397237566 805065145 554410864 548732401 274968596 959393297 264882723 73564252 596766309 104526942 114550453 910949839 972857028 635209052 693489624 543574431 100654186 128862980 142449486 346913681 762199810 343116899 775667482 13732784 223323303 401591257 546993439 14189855 803026457 244308309 268232096 105705227 161144457 898661598 516768218 14818394 940622699 723716216 615128502 372271312 544526097 224588839 240316617 19072663 495397945 54902410 759890229 337659939 520560331 668755736 29145383 563214008 986159872 489234453 447733151 207821603 941626207 631579178 885878776 200057467 515644646 85253932 600623090 404637425 239905814 373433668 818181156 112681346 228503216 404595161 702936499 603649050 594143893 338371879 933635732 603643811 562054380 638561357 600322061 738997050 330277659 405368120 836351491 276352657 455372074 119726817 229851607 298683702 66786474 702415353 649372747 317853402 153286147 7273454 829376893 295443582 60270097 20584753 357720408 569001250 490673755 340558739 502396053 950506269 114754415 238701775 890636928 694411016 253854676 840028284 45536907 269988576 492496938 771237279 398357936 489845366 490068825 520353549 486709506 133476004 823626995 513333733 20430946 802582027 512081309 650383407 597878771 815477744 591212437 535606443 59656545 261066799 16423188 465090354 382162355 480619436 75512238 693682006 909986521 384209159 69965217 869086700 726280148 353244075 670581462 95234170 998903645 675621498 322434770 202665031 577097031 59877425 977583710 393289528 4488404 114864624 722355434 182300075 534496111 551038003 910649446 210106102 486164644 679475748 757830786 707030550 578554064 81430228 542455114 9090119 393219249 553391472 291781499 365055792 626514172 936609609 166757884 876117054 65480508 892644897 350714489 400765814 265156807 715462723 496799039 816754932 432165462 657736739 46332560 667899944 843610668 811095816 487721147 777795044 535169769 939519167 587137402 34030036 247591288 404644793 106619335 155982508 829766159 383165573 490097377 566218183 756549787 673440574 158352213 872183487 590110053 809035928 118660235 777109048 177356880 924972384 204023523 625500229 791202094 189003782 231287831 96177944 966552187 400307310 110942931 211033109 482426146 245519973 45825908 257135755 188751008 29328709 716760744 230684996 368207940 174119380 651675147 753847033 782565942 333148193 149018026 64637781 750870143 563772604 256815145 551509206 525832586 406489128 86952445 210270778 995193685