11
270184191 676663751 933503388 97319101 151748536 265439691 782142857 352144590 91109070 100103569 552735820 592159009 288941238 196172949 712808255 822408632 208964761 15025769 28449876 416978619 586047013 306818010 64137136 77775673 527669948 92889668 649081343 605157401 703653845 639851670 835352006 694264533 210582503 457253151 782852852 364907763 517088633 109575128 242992183 125067976 180156566 877385283 735400273 702486290 886035047 204098220 903144765 806988836 598138865 727633136 179777921 471287301 640928453 104208282 580305866 222339627 737398452 526491223 188500369 104525274 994256160 685875173 425993551 123832794 455271752 698406157 864731810 958652418 756588415 474490371 461360121 892891224 696220976 448155344 253073915 33635348 775077004 242293434 989950273 66132475 83616490 935791464 721695713 983924407 691207347 311906251 433499362 203195626 92669771 118806797 228667426 811031211 166766998 854270294 766879359 798051367 875877148 406294524 23248493 835766359 262675539 723278243 622408099 544580208 662788754 947695180 603626839 747413984 791863771 763812818 556486115 755500786 585613204 862869718 389139866 924471823 885162318 220701581 890545555 503150225 825328645 667539611 185697818 456761456 84108928 705629747 877369939 404490110 819519849 692198477 232016963 434682053 981118178 439004521 830722670 863010766 495102572 193700627 85688062 428507563 493567178 620377638 326929033 319085422 475414765 1803336 640768576 642420681 777062985 126400178 546851372 632655903 477943596 405280301 218877324 361622915 818306769 202054254 931788373 480201003 995913862 641705554 761324148 163556877 148017245 21231779 296980036 812936088 843838223 641127373 315234792 275707944 973896122 965630181 527984470 907523433 449086140 830120285 321040053 373529704 905331350 916820898 839554941 867653964 892666542 138993081 224609260 34822683 57369856 642877730 321512860 771783869 228222089 397999472 417515867 407948214 732773712 691529155 335664574 322727621 654201152 195484976 178860042 147943416 360670213 611018509 151404297 268205300 217375161 49950359 561170633 975528339 881919465 376300094 136879158 489831818 994621539 838929969 152990859 616910983 491903893 393003889 924162292 14331343 257761672 540984720 902983295 963197324 546875416 218687185 146765258 50169233 489807291 286868862 848879778 606076551 244627349 672321083 592200910 78925889 429198308 166375255 862093186 706063952 536250078 207583200 766987051 551932221 640747318 542321079 739019911 343245892 84307523 144580190 877276466 146965431 665134291 591205977 655683681 449289269 10449027 937765797 276646234 857454911 474767030 386022709 114384376 73551692 215500994 448745220 725844854 662795003 764197748 206513068 818398073 510294407 283246200 977769781 778873892 600416397 70682318 475007676 689319336 404959565 79786960 961069174 677300169 521649449 53525857 799410437 243919246 836365243 11407825 432695687 337856122 836517501 57212801 841452740 50647957 261734046 225600380 270349728 484916809 139328794 218550323 571541338 228098406 542051184 679204300 827964219 51149546 830394397 170577170 12214086 227825738 934892509 37137816 102236079 197535553 273859130 993567699 70780550 676726281 680854492 867440542 653960749 228722004 252238009 28936919 476311835 316798685 516636877 926205182 394721031 868326332 361752520 955491899 734852654 979972824 563704773 874368138 380938517 972347640 609321937 452268505 605538077 33770104 366188039 914845567 423889627 74793746 584805822 625640439 786004962 969281018 679386153 220495659 375691802 26686677 409381373 924557214 842792172 268834938 616313652 765241961 836618419 532875284 845926459 402590811 421003331 886503902 546061822 333781004 860522425 729745965 102566097 202435088 740008678 556392038 610366676 418882361 934508729 513454379 666162409 125583918 740036218 737881765 981811309 802376278 248523440 79546184 616597102 160342610 764541387 722888137 890005241 142062308 568535369 740566305 813901316 56745908 263875249 79928326 162649674 721400093 88282995 253196169 44606144 243072912 188721352 140140225 542751183 465358078 44681514 77451589 977098271 885761898 764258891 653316152 726676570 171735773 97487519 147751906 123478798 611819217 893698342 726562760 925570248 545717180 228383057 349403593 95393273 235975262 832665230 406309051 997838528 992881759 694386033 976287366 288173141 277961993 358393615 770395671 96149090 875673887 196059814 732573694 219438732 796205301 183969934 897608332 504266944 558346763 290445076 420219845 472476694 323363612 259819371 347928148 631105597 151507958 926525254 314879009 8107227 86674392 672965003 157323426 562208799 690435092 622289683 71627524 37667707 603267405 167144046 543895757 419712554 274873728 341868114 390119448 94242718 352732783 480608472 905275366 466414717 320720103 437165192 613268804 637717079 136661925 74990556 692037402 366363805 327191249 551899313 521393567 366149763 436861561 204653104 378745965 246857680 659073671 179227405 116600107 497402749 71669060 969042762 634450421 337078759 554824183 941272928 833477811 927202955 489980412 291073727 236406091 744994863 421957205 649800952 574719941 708229565 71332645 2073494 347460349 939938638 546997274 845783225 404091962 81932551 836473069 663825636 721069202 295894957 52605736 838317444 472169779 413062472 862224873 593319527 883178687 879263187 350184884 167172472 399805659 421348230 546274194 482821002 428891940 933121960 846605947 934558417 39831994 465008537 360160205 397651570 980598022 909054935 991090416 676293694 605602996 362941366 539308965 682994120 825346892 782313498 883099456 570409929 966974831 818482342 137783681 953512790 307336812 84864748 191396596 866018582 635053361 941515900 687681462 367416910 741424525 120297520 605688483 397737241 584811425 199543065 802668484 675994048 717169471 625620371 595265980 89890705 636975316 76530046 692797259 878052770 71294613 809339350 509466885 242591922 797467758 460562722 832142640 4512797 40051765 717375260 655523596 861948295 693451407 306813646 105731174 426312989 82244848 780071094 383929447 796259342 417891013 831279342 904515436 143272438 365755589 753437877 294344150 314059429 251773379 51374409 749469846 660759731 29236980 332718530 669727324 268638922 880287802 25346778 299574415 410604958 859933196 51801251 46372333 728206216 921183182 576622182 194102283 248948230 489339496 966773929 902898951 889553402 11044727 295156694 125941424 544384894 247051591 776207656 859203514 381238608 89572154 43288457 130391057 278646868 224200031 480388673 92693639 569464349 240163576 548841819 148359519 535592965 52295273 227343507 245334433 979433363 546441802 267201362 429583396 148095591 107531529 375955516 783578338 883539118 773176364 40531660 182775489 244552935 5083788 773655556 695296843 795932433 185023569 228295606 469312749 600705140 157008063 717180863 387032308 236522342 786525731 174003096 437333678 528779136 869688530 713621514 962994927 853845627 878068758 506486634 918394540 426570443 942975523 40749896 191168830 440353266 400867566 754882217 802518234 700136037 170786335 555902731 865068320 663263093 247950424 604967924 924654533 562046231 927178520 137915061 35418308 85339004 817755910 741633165 668975842 774557943 547102172 626842392 485004111 993525494 112351462 703096301 961789796 623995648 109147470 180330490 233870800 286985670 575326898 291456190 216513795 881899016 702535540 29500838 83244765 196579891 700282919 318004648 145680508 767816222 729179523 517750651 961543066 782464149 761949172 685400686 788411050 226090024 401706737 681672295 350290967 503418143 159060003 168020161 870115710 582545227 449429597 815488551 2599902 712662439 175531799 54664863 278249185 879158291 524140938 863295790 262968854 107616022 270190962 339000304 382427106 826382769 75003614 395119480 358113386 805301503 495384815 614395755 828602959 4419228 425339683 668361454 229935388 565257119 834910358 836378491 88812458 273665902 639118915 500128751 287829883 157396263 504364925 893389749 283191002 660687787 709411157 186409120 525776514 642268580 522472198 193208616 29369627 172284192 406561127 571261010 570289294 351836704 76401452 462385789 766115122 64434285 89007742 378662873 742004464 447509423 696940379 732870186 676817883 818620449 320959088 103056069 704427776 284686451 528365599 266375420 469081036 903117095 418704053 271527789 898812318 408935170 264826337 520953545 732091436 980610911 878177507 655607188 737620893 755749624 780405294 378145419 180836268 824388017 867095399 610235447 351990492 419427560 744000856 128877925 119333595 170570282 336210276 758122570 851706614 345363928 503281123 757021127 477996215 700785136 467050875 141812187 478116097 857262260 555018281 617164673 75902781 941432116 133532093 16054084 907157348 907777338 396681694 86164960 219711073 164796563 804988226 31816529 123785181 248960931 652064677 863293564 540699077 552207725 54832637 736496051 601472208 502290912 561558972 486036384 894826990 131738318 100736332 319020596 825662968 778386078 656288043 451129793 219847395 6445855 532518016 476605557 710667304 624517651 106815800 302007721 623380823 528943135 231842970 288623258 293187282 554790635 480282823 432539789 757107102 235001094 747561402 721682508 713524363 976957189 725814007 551705786 365549971 5975289 990174517 918464524 814350867 738011173 612155891 691357090 143051894 544559562 655768444 145378948 305703971 186305405 608120768 794281977 218400147 278915162 811104577 447231941 676494447 295966306 493967586 282674589 366605655 903554955 224641803 3980517 969815727 815669248 28093678 763356077 753521751 613925490 809218366 624277963 623134222 447641637 783597408 532036668 811101748 42230157 213233746 656598966 465795063 224693404 45421933 919954393 565241862 129582538 287268111 700455797 583226924 593403853 536821399 413309969 611545053 580139387 288922073 68239909 766753244 49415294 972622950 409201395 352722191 4910279 460075065 63575460 264185906 321848090 200716509 381688970 537234034 744364993 258436387 853165407 142672884 542013422 595449637 212104369 247586270 584452075 896016678 372419564 828748519 928388301 787086733 632299604 606443343 855777272 884864157 846895460 318074477 632317436 903583760 405854096 678733184 943369550 607305366 253337034 215301068 633762803 823788328 138540037 233539468 418106634 9372235 273920593 736444953 550243520 592984320 114336598 438194253 231540474 886378548 866582197 896605495 428168594 663186831 296054967 404441717 985654895 407713734 993539248 96672550 964058848 796763671 392175738 680931478 672954508 525789173 865456396 231245789 124371357 596574613 912500061 743935617 819724225 601524690 874491031 510975069 377324777 215191856 471877072 320569973 559639810 953720137 786159844 152533085 897261927 501919524 516768760 515964084 535161583 468339837 779731376 589779364 229155377 425851887 725808797 117093478 466688202 590523121 253867006 547223400 619679051 806412396 429595986 260334054 90920673 137150416 490141254 133671032 118994997 331226169 255667863 644191909 141830587 842718067 479857452 779448123 321975911 970304153 315407839 931098075 882370526 776590531 204783510 945279890 509925110 410523209 238247109 487751792 576577699 975235420 83006515 7950774 868355556 903599594 78272838 675711994 533880159 253594374 139381499 856388934 249629010 7119873 4736691 483656297 3193490 278484071 566986113 317435594 992047870 127446016 927280167 32983166 564516827 766432876 561552991 581175165 256877524 28232038 321462250 138475510 382962066 426321046 283475531 557447938 258376148 795116840 846253078 653579852 38027593 929238842 836785818 852611207 304388005 604187669 543544403 907774857 481174192 253867982 996785152 390098497 161830730 924930244 7504303 933604617 202338658 997762908 621718495 452572881 977921525 809413416 819836315 522932588 672999345 948361687 369260151 879651533 161157160 116131756 118394592 187752776 754275910 68349809 208680132 462428076 322674273 659287179 591799086 100496700 169463519 475931604 483953763 924897646 724095562 631207932 675568541 743684156 924624125 443304880 80029937 128836841 477311571 239464550 804380841 735612487 690819627 188899077 800189512 854418349 858964775 34689564 559236749 466342032 866209499 494427972 799194899 142080272 211931171 309915657 561611537 233746747 611355568 552405728 99784738 6107381 398588876 745837116 263534450 17015918 397925828 551166762 652360655 629938867 571994971 811648580 917107823 893353652 996683102 969530261 78205053 521984872 910580443 848222602 514276358 634568436 53542924 20786139 130845890 784929190 514784083 736543605 819529132 531056410 106560644 681684750 456165939 65000888 400561141 549639830 224034584 133422533 428996746 920962393 989756793 354177507 408713403 564674978 665038241 826821861 584406065 137413660 359370641 500748128 711633989 444498241 7104502 285207290 243278796 567734647 750391749 827639879 565277934 342383008 543881420 431780205 826242933 891693725 714661739 924877117 371645360 236205602 655046179 669615211 640796692 893811219 438594607 714188715 186619119 781098247 114118977 403697926 687925337 865343 908736727 439310677 607862931 148922159 509454045 249583581 80829328 475793884 986744058 303839453 265612077 888405858 718517006 105186908 871434263 972260726 937817877 726461871 487553827 488801840 707570910 838065091 428369597 895361746 702627710 214517511 792960725 573643135 435053790 328461617 379811403 584289708 407402172 375480955 936968233 716471608 429471270 423215438 530335039 367880486 77981485 781284232 49657321 722455200 340361556 271098826 960849172 1073992 984534975 922722286 456435831 815331847 381737938 286996623 618585696 870950796 138733347 439255305 169027915 540320078 958557061 306342199 513392342 307869150 399044035 975858702 342146461 709931224 77681902 511315800 227144678 18922898 750367365 244082304 614778000 306755214 847168203 213532612 232211308 971374193 454596739 445663907 766378057 644334459 700229657 552880712 935753773 165496125 728346932 594455395 759200133 74948141 188340344 603451387 278530504 215597762 36439514 579561793 157197727 565439644 754184124 490835152 908411075 926745571 72799055 722097607 237464417 291122180 530840442 129733057 737927821 58139122 519685694 570031026 423819114 867433685 921031864 700230039 39771151 576094326 694224096 627836916 483383872 787268727 369001306 44146582 140814178 926688155 855760148 820035207 616916923 37829379 282804647 897521574 524454950 216288373 356130691 646512013 607871333 776532667 854448254 960559765 47835144 95317923 554764308 238184130 437689656 204549702 881945297 844471345 713492737 637417790 827206112 441117548 687163051 618666776 955922238 254538402 877644734 642198558 852988463 326032408 815665712 996031352 508681524 774737343 85410034 467874613 260694709 187234755 969702213 686696850 806822602 324555325 160160298 843127985 457964806 152095653 41762246 126407443 290688135 626138018 425404562 774248702 425057456 117837680 782738872 698161349 916650465 300729483 961532457 555251450 578280376 369697989 813834148 977998998 725717306 76023282 106563324 270938460 563737818 588730469 276712208 961823015 342805933 336626181 343496876 495640334 871279356 678416202 182682431 172012107 314718064 334848395 330365829 790489787 401328896 846073947 157396090 799961518 311211685 676633309 637580600 515605541 963171074 826412597 963451698 872162793 555538152 468854181 802717254 917527944 261097778 964505782 297619797 799993472 512217866 547762626 259630184 942747743 884440412 486999484 602974666 642473111 726385330 718589615 60866732 928370426 394588085 273063134 70910570 763032932 104316306 997546664 168164569 128468669 651486924 944658428 699820850 323559178 506497528 474043671 180296636 861620869 733872146 696532625 441208007 881410494 187030630 741219544 320161050 460211980 795893135 472957804 864928295 258963443 951365445 112560463 153533219 843633261 639202681 487361270 525503199 688652563 157367169 116329955 657593567 72703520 908446131 898070169 924065591 584163387 362214769 532355927 480729236 784404090 96949771 321215723 368870096 511035136 792878835 317478840 661353132 879552657 64655564 320903698 424650308 671541223 890581403 330721397 636604885 74597602 904073940 249444903 144237497 623160867 178436774 316145660 505423958 889323415 359413463 515362343 494665385 776025757 569856264 459480383 89564419 817832451 577209158 421842612 840807770 828959112 8032855 953340138 101903935 959188347 855776393 354766238 542322376 767101532 197915013 99860437 123310796 269602527 668753954 861074714 44242593 876629755 154211947 266870194 153538146 327480283 667341108 239070909 616585040 436702035 488064142 68235367 572655246 701701837 262503798 485563211 406840880 120270607 440314209 933065925 365850951 437374069 170696365 180241433 251799677 901497293 2423880 970189181 429214137 570940204 69854286 725599191 559647350 900393034 516417555 401027914 351211557 689874839 919608618 25139011 252039944 263000365 808895036 448641993 66375385 212362684 513627892 423549428 296462463 960951192 597031525 404758793 344387400 778014881 690465231 266349332 66519004 956243584 610437352 577287285 367222433 221663179 543754417 643542048 404677985 171906429 841221428 745180526 928030878 34730925 353338258 176834077 869341778 742725357 748952028 419360871 820304280 336308529 77556799 447312444 397995603 392497985 757076318 528273543 933447486 9329534 325081616 818412428 735661376 330026071 255803842 937798982 98025612 472600281 219666709 174778367 832506618 232019037 743905090 238589359 216599291 962883919 346837775 152307356 745111925 199709757 131158657 645279713 509556480 690728627 216750668 991236707 964533159 478426380 607809826 174530893 684809399 58255593 22018066 947711131 865856346 534352436 557020803 345051628 84517210 432832715 218116392 479103093 720513837 695364679 36971518 284087772 90805044 529812663 189841376 379460187 560198852 202270118 460137034 198318971 618145157 226742520 705888797 414758356 365371514 888530257 811387775 723208669 817659365 965113050 728618669 68610528 886264281 293197005 779440371 469287786 279520763 823571090 955662342 983794075 762596829 628210223 924219176 528977587 722766942 72204976 525536401 885437676 471136116 561447504 377118453 202306448 557544090 872608451 519106419 983187784 503769087 31954673 920278284 17919548 552576174 926327097 361052887 141157 889584315 827788276 659721051 627493923 916636929 526980509 431892232 339509941 939902504 977859031 581733302 478926059 835793817 891605357 605145939 433704635 452024101 172965585 260556214 184286740 649756135 73554369 666897505 352019403 379677944 189922509 236066248 449893403 203651081 540597982 605772510 515955272 211674559 183753527 274736690 234822761 173100805 65546629 958052771 747551381 558544875 536025288 620504565 42793307 887013453 773970274 346790032 885437399 854189561 782872532 917795800 783209137 556596942 403175687 555237254 401445406 914317279 29838365 261825938 65970331 283197274 143931548 807142401 657208346 444795909 289844335 878240592 345984543 866549430 381913977 281154768 935497805 712511719 389354511 156274943 362129099 883791552 178435268 603370743 745944923 235845870 273133102 484307655 140012251 894734926 472974290 378387311 616641538 759529666 66957002 882587652 795795913 36994888 655823778 317205439 773434077 520998872 780852095 640019043 807279514 692332682 529551056 551127499 138679123 382489039 570694896 768206272 948687682 788869676 906014069 922324428 401277916 841452268 71162958 130035676 327722406 837338205 435105178 207770377 181098980 79588807 965196372 865358503 616564752 225176740 592650547 109158648 654251541 27034266 905596592 839203984 439804971 906684610 382975912 241988803 617593105 555038975 604613721 441725292 761518011 384639709 801065194 958483112 862344012 583283351 600297336 336609996 339347590 879205592 649686141 869494314 385899378 689794552 786246894 598253329 825794425 58383036 415459536 312961231 661987792 400965201 32778722 164096956 676821212 334545973 64998327 439409764 469597552 210448820 997247465 294776322 992609817 174663654 770842090 985790016 541163414 314529873 842099043 30962183 734239987 617847139 172886389 460040887 41207713 176294470 568594365 736228473 55752861 396409582 110206045 675014914 277334313 482732463 450276313 500355370
942441337 411636979 787535390 900330513 295389930 260101465 27865637 600514675 964402348 462535856 790987466 34264771 103277926 295609742 405515192 222347490 838161320 441651024 818059384 751081033 150152711 358383693 894086911 361622229 894195868 834852433 681479366 947568044 653838496 737536426 352633467 428333934 139006706 524897547 363728040 82958685 623186514 950517415 425476230 983263317 756596111 1649092 324563687 836687727 549081587 391421007 341616397 861162386 562993463 113402180 172751151 630577181 861733027 612559114 691694818 768715874 351333974 813648167 913642084 740419303 964084658 765819005 27491929 323315378 823608778 143237676 973158094 412246772 48608466 398248075 844897537 919139002 724728347 997918620 34844970 553504286 522276918 808869002 680216701 636234609 336705618 711227689 308444962 702927460 614187797 279327315 37082824 107891984 446723598 910240822 869178660 134190325 230021775 506065995 478618782 807135758 706769743 838836608 286128598 688723515 275718755 737814798 418792750 804628077 658936046 317834526 405526295 793216169 959098301 549699467 86168249 391664832 416920776 338298129 766125078 436886338 626823290 564839552 194932545 836225647 192316311 14876024 557208227 24236569 170583584 290999719 384834005 171913364 302193799 978646093 71318465 134426886 68696340 704998195 880786209 948338183 780387482 555736596 173934737 179806841 531747808 71758428 939976843 5084675 792092349 993113512 995972574 893631855 155923956 66934946 448256299 62375275 978673935 904979126 784488539 994437999 394997174 971614908 143344112 102359247 205521832 959755578 674950774 596148575 806993021 112099807 707181780 678007867 309477685 441589794 399958898 926955640 23178634 763609271 9403570 474967821 844441564 403152665 92603162 592311743 622464941 543216634 665997019 496698060 777865677 526899471 84531956 716370502 542644408 928045827 900296469 788656010 699003366 177477149 54497314 295671906 443544363 992974519 193186229 941560452 46133237 609780151 470532358 324847602 181195396 321735852 268948174 336314742 454658344 517452362 604184151 981879109 138325816 798287729 754429918 99516084 795481856 929999873 440475282 163575814 599448839 319392579 314870774 70676561 746002873 503104330 24012640 948942654 624023776 208859939 758250686 404284697 820526382 733303821 737535524 452042492 960153838 553869 599014981 750437958 117736935 628463116 351980780 574318907 717262899 534856559 179014955 454270671 755879975 696647435 193946155 791863026 647360946 203247150 301772765 135952810 706147523 762825459 355461981 526652381 848019177 662437375 156526852 229593328 233813016 403765740 707038051 459095895 528335863 853204579 904888236 325941775 946686044 203781746 627094001 229612012 406963622 210153505 209533683 998217025 660248239 466422462 12000568 513573967 507431842 183712303 666217419 883849410 627811573 1030938 895967002 617480203 394231849 450992827 291367340 1903557 614021980 78744606 360682373 876184953 124036487 920106019 666687482 156727383 665036385 203023789 218509839 268735850 392908742 217930691 642329283 751636576 684378232 813549971 412866021 996031324 706253299 852434822 804187609 249715547 699063557 10577829 926381458 722484789 536913602 584113274 664496402 882718126 962803289 12526541 906646987 24361385 8851640 659953075 22489152 169996810 356655492 791448940 53406271 142536794 932706909 290972160 791486965 97225209 41089076 319797590 974348914 162078851 455182271 39413987 941563471 310902661 551859464 87744954 213794184 68215717 209276770 175585498 972378822 71222005 724233958 37502558 523596397 257381037 365239513 10874411 517381060 390664561 301063129 105430164 166691176 378222855 518292827 382334499 734712210 58722738 56633797 556740400 21033133 694122668 895091608 111400130 323623664 930187076 839931080 369376628 142462519 628437833 778457896 674709040 749710707 282018086 993679627 922750705 763861118 795811162 531930349 319775145 563680818 718942893 665852707 242567260 955636070 331976927 456526251 108736637 468024579 981603190 940915660 289134728 304289448 613875944 646683197 519391120 830177105 44408176 36971514 317004897 929512302 222633138 577234112 957067669 738783764 73665760 919919486 818691445 269335305 797310053 369327565 462755835 494357305 533178537 44742244 725539787 359809968 244561600 746983942 104585388 871526712 445369539 543656747 96426867 96408769 824893886 704473465 66727453 355521452 991702422 695369923 269619996 214613072 922878050 224262600 584476922 163325535 886674655 116713917 730621089 11820478 342586249 384409760 625101054 989350997 138771028 797835883 694410953 21678327 324199111 813043272 462693705 570931965 863863453 216534718 493583042 364946665 499625652 135217430 135772084 254000482 915910147 460555080 851760304 606108612 747717034 317366355 981073770 152713334 78948082 514697550 770853300 489532197 930139151 915994729 201798792 66910953 729615434 923676101 89169343 202889672 200568015 776416034 897070082 286816148 139576612 846377265 726589788 214476219 226590198 710012478 203016474 301146686 341437771 94645551 24121669 207982457 721370783 288778705 571412125 313204102 214035929 930721254 838383886 155096400 100807209 400443978 137229041 302994697 817556788 994605377 901363027 181274251 923139457 765257937 668449993 798573584 243548365 877427865 299949438 133614322 485768393 147485701 801002202 803988466 59916806 983963338 10577496 532634050 765291120 352846505 512224239 530341310 699049046 835401369 449200518 930182028 159747620 449775895 730489819 522454287 817440002 716945369 886717298 247047596 958317013 237909002 169488648 950424109 820023808 816037539 16569043 929993410 462052300 980319659 840499213 558018396 745818556 761589289 872298028 237121887 779824383 672268683 200797642 682360232 809181124 388119939 759382216 201082664 980925880 794417283 954384803 40412557 508676076 557677277 613716830 227299497 810890252 720485907 361420183 384738102 918071370 921918562 570497131 690462623 121807888 278180964 449175379 993384588 48817458 471517275 297675100 169151802 401646651 821984952 912360689 722486505 455541957 782845085 714478600 844441508 958213189 488053435 983368817 234960643 661468630 118826041 36697399 558289492 528751235 468635318 7949668 502125172 586934366 479203315 116536413 444003352 743310817 567579628 382895550 982743264 484849947 430949053 909703791 144398469 57079720 623173693 71172643 344351894 978540483 541472717 33274490 400903469 501188998 421404170 297582244 954603439 597697582 277882759 528571498 543468823 815018845 251710404 325357422 121750604 291788737 779670320 247394281 132019747 273243949 162991197 973852995 93041812 968400887 830374734 588030405 928023589 378198906 743965224 232773358 47727528 96107434 909366768 425231345 619632646 318883780 255826117 542415529 802358930 430957914 385278405 75690991 699503020 297233932 648912173 840421554 652821468 308915824 34579447 674346707 359577473 646422180 500123840 133129701 802536814 473369124 661328073 547855056 545172676 237840039 704044320 318997996 72240632 960610129 734082002 435935616 817090227 180435789 861867638 349122314 984573281 387908548 721212898 184482333 981465111 773224315 217147585 321810218 939265986 785815598 512397713 708630168 414717780 429174790 178133001 35544144 13602815 842253859 177714636 56592734 768443568 59117334 784151446 98267723 963214066 895750597 600394142 689226004 365432053 742347642 329618152 636237845 737332880 939734199 186465391 274044481 718101445 738041187 858756934 24127799 67099181 94635087 445432400 810125892 700223426 199384573 851865128 897086695 602106772 603241183 66116787 995428009 598042133 843131863 360307870 453739606 800605602 548571961 731300969 738004276 480685745 167797895 658800719 704762958 762782349 834911646 558564984 599840567 157418764 472309925 456253263 544009071 752367604 352656776 530967919 975699148 807723662 956675510 517464711 734137444 831762035 989634759 987942855 238438777 105138204 99294327 698844074 780344511 3785253 552901619 908158080 307811486 630903028 751445559 34722383 352486392 501380386 355092360 732963427 207774697 270076790 908651858 544666277 473112098 334016230 972735144 64531264 675410210 461712969 321020967 860766556 637589563 831726439 409016740 181203333 400742989 441313735 269019750 251528500 748458230 762828178 294954586 680485715 216471918 563916703 432030901 888082493 454095078 821155191 859077486 620635976 899261398 575036920 583364554 357777201 949597119 725676059 84918233 380265311 615320833 901913345 33809158 433706990 396671927 983900843 933588643 342881352 746155147 990592792 472221644 49554552 712753723 653050176 618998960 286108397 704123604 965921924 819263883 531492728 450870796 210720778 395089069 294595883 459557731 435222804 624389561 695272967 644691454 317369450 337259703 610860798 507309092 557589147 661390256 973052639 549813505 846983074 704739152 722664645 942379324 960333491 491952442 415701594 166318440 42876010 584503269 197389410 590883028 324553350 831015357 381927187 622415300 602253511 485491568 21316120 969014481 313803052 357633357 387683006 44464824 870414276 6998186 912496744 181086553 611262037 811119633 920790971 145916190 903395964 362342729 153914378 823208335 16148010 898968709 824791444 741341703 181838526 876484205 867677255 485606540 779674187 584423174 931021985 631034159 617675964 490356098 218919640 474525776 68114060 500392160 740849436 667966426 700584947 91472570 51683433 356956546 368079616 751741215 855463439 490448675 54777774 967146465 815533397 344627583 182081438 691192333 95153138 350015845 662568149 118896721 458536999 735903093 360904086 332973588 282574849 402518976 894039178 196611174 922795768 818761701 315116166 69974501 796989353 637636208 271304688 354201137 928956773 393375139 110578520 946925186 126004560 118291854 141589529 426484675 789910945 903522623 679094063 741618437 336171360 80997613 701447859 116414196 837420455 189079322 937735834 339442866 277957404 958335522 479419291 207151475 736825296 127577437 934895727 509830478 670805924 281826900 262511306 582206347 753495386 369976165 678266896 477539981 666176678 123915246 412208852 750893432 956170780 306796087 770555132 307086310 670903346 330166171 266250560 429102184 348317099 948141224 987532817 647686019 784947866 622962168 743290986 510417253 407592401 708848721 923734021 401619290 785846682 195104060 266906771 841010566 842431356 425867214 786193715 985341421 774933932 894184559 696963725 680027688 402728705 948427328 219058976 186959660 168523700 864524565 726816900 994774786 97955765 532974406 87647591 30300057 677840343 197283452 115895721 319706775 832352023 184990663 389290519 603296422 657873930 22328851 547917094 44246727 505908267 380665778 336620939 600187489 583785647 519943183 909478696 895083939 439556267 96677224 74359578 845515221 911537289 303605664 146773955 119541362 544191971 760770331 981996975 589169021 834208781 642859733 154671083 649087685 460526271 242580 858298133 289965365 316297897 257057129 32786351 208994270 937645366 921373519 37661099 591200982 450800457 334213399 733620908 838889202 927296029 522080221 812253512 355938443 495692142 920654639 418557944 926466744 723602586 972344169 684028882 39330676 207885167 22263855 301359214 283262260 917144306 568850511 239866493 106765226 987822200 561387548 968620641 672729540 557320128 22555520 267675763 580576825 251339518 288249181 587617161 127352985 534056560 984719504 55900883 246515151 294639910 397512147 959978392 940492740 961452963 256883267 730190425 947269583 336925928 357111957 228858505 433036814 387107165 786545599 675625734 628602183 408511561 658280443 508767506 974261993 174461058 711898783 687846285 118213454 368559179 201124189 895634218 364092584 974769689 545671022 644600400 633540553 595166770 438970198 727997455 817169792 470044020 752375624 38133401 896830930 690965916 568767928 552860227 580190710 428646181 425840329 3607099 113206356 262834318 571206963 822031417 253574708 270624488 613043185 239444984 309244415 145248708 221627606 735068827 344923390 63046021 494657251 58678415 321211877 12209431 318687387 772052223 622810540 340276350 15924326 724407731 994258663 582600531 468723054 429903764 778556096 950677071 742513883 121861618 434053908 816359839 2655832 430497120 174151925 905921195 781773999 706722119 810088896 840389352 532073231 868233801 825931669 354836304 522277040 709416052 795905827 608803364 741652412 968893629 492027326 20740211 874752455 136498995 84195287 19624369 973243828 583323433 985253713 441585165 280782495 460876530 579099899 116516390 125502060 356741005 671627536 753158713 834616628 404858665 982689861 232788081 767830468 421702891 718568437 578306445 967647489 748654666 909674191 794045976 699952304 922981954 771158442 662826356 709579960 151029356 223209714 651371676 37131293 212096579 159922842 239802496 933634347 354460084 286587876 91104096 633560838 990773975 414559586 150682644 151768814 98804471 491751014 807492474 515952811 49293508 280109354 560428726 45686063 301165226 14721682 875502108 875216096 522208627 792390752 287338233 211528594 513705125 897340627 459581871 253579384 885115850 852658502 486711372 243218855 244613193 1731621 267344337 682467371 148587887 946145934 738382096 222055875 541584318 42409445 880243372 168430572 856697546 42216483 362653015 72307288 533736584 956137414 919782 726317264 165028650 628174576 535234285 394603252 383713216 499330275 799215691 820672297 474710401 742079410 810158861 490677547 40732739 617007761 303728107 805792630 399584796 325443421 800002470 28712857 197203208 899335384 232309614 295752351 587131403 814972015 983883800 112812759 797455943 44391420 903698955 446669397 373926457 685187087 882430543 972918332 305044272 284955154 903903153 212171392 353967735 748213220 424230386 547666058 806606119 957229733 7451863 982714069 203032848 938270025 960294351 681607936 872231064 172789256 591831391 224336947 166184803 223037618 960652653 997672618 106573987 263159291 991974059 622598199 427645244 618461113 637180475 812219981 426953572 497683653 374318792 303509663 596268780 153650028 532320533 515745394 946965896 191851388 908934464 484619114 432017932 288739145 803083386 72303751 727055188 431707953 503849671 861496141 767232673 844364699 407271676 604993062 809101070 327714048 939436146 609686635 667825037 920446190 585587692 67256744 285135993 879902060 810324747 367983564 588267292 236525387 495164928 592493610 987077743 67238751 993344173 469161288 150450879 399526754 586296079 912599313 318026713 406503035 66209207 180891741 430103865 715610200 137051750 810284677 73044309 366098921 916030943 394440583 83724589 806982729 911946592 962901143 661908294 279986129 952953757 52682965 439237017 18252981 330469154 338754856 894276557 839687860 727143963 203030021 225059624 979647782 124369991 932131331 773947220 551121927 191673252 199567052 280267714 709049088 661364435 31142766 43854476 702879510 827425699 152180633 569003404 667717339 799065341 437766533 81064471 398480322 300528309 589664324 797614759 394600544 697929032 971999245 838558433 498791374 172857697 671880896 833553832 988544166 539962327 423711363 571054402 633275623 608304134 462893018 803200040 923704147 923320282 360821108 593754914 949897913 859612551 163366918 501994566 129551531 33254750 160671597 429103264 561299802 842011401 193608410 92964974 746380099 752977476 215178533 663757566 440134686 611853565 518989098 329989282 158229890 283359520 33322791 517791407 238337290 418290124 45381729 469907758 749647656 908196161 390409656 22180973 351734320 661376165 609660603 952648264 555236309 130103597 637838443 741426510 75186437 892661424 685009270 152204315 354981577 907315132 344134604 354899537 362015271 171736198 249459977 660001986 81436872 805501793 521593353 654457980 362537840 656261977 812058628 510683669 583506377 70400191 459837343 941612100 298850555 304141875 638719624 117886574 42733106 452396378 830601270 62639999 554243815 428714115 245128034 63068640 505839713 149446969 940658160 94399830 837002499 395056146 787995149 343986552 903613186 420297878 628031629 602461239 752314837 298541373 706940213 976601368 409809836 186125089 805100688 484152840 804400544 430321943 732845601 653848264 953957339 292932036 869064323 512189714 49775442 494225424 974200964 831692350 801829760 465568623 711077741 955537376 263445940 355262360 199062642 194467134 654540226 965588831 50516276 31269797 53522791 135511975 684801969 816339779 854631267 316488057 992581432 515310276 766955177 365183202 472860354 425648288 439280702 1133552 332858304 975374016 739770947 871923474 757265565 648454694 922637965 633554108 272677520 973306114 891893933 88625471 576515968 251719827 684709960 642812661 434226122 317563540 498212028 758166173 417079053 358857368 981529335 671424618 484380492 596776071 341693020 154042230 236420677 898687299 32949362 704606776 441973355 521032920 902010817 974394468 718752622 671379965 129232925 40708779 797929115 595639875 930282993 551183371 30252282 521643733 605500076 707993077 361321751 509885040 775151541 976013645 444179152 577727733 193011773 113825699 504006537 757554400 468413239 306633460 106151691 482199633 628089315 914215205 750356758 532931499 870925387 403160598 834016919 250827021 587928679 597910235 436508310 431901999 21497499 993138457 63565256 190736175 754463815 216226372 55238801 709267772 687477887 629085548 434329503 95325541 340589044 112423506 195485138 840982679 226921329 774942933 368741379 643111149 234715643 689197462 547911312 180032109 363746988 380188056 829449362 537636311 212377348 77271143 854715605 409862398 98100446 945461656 965989623 35510009 762593548 844958345 20007189 842462687 833454781 184806980 784054694 857176785 313467408 461406567 302235855 693067140 743389265 288253618 434983953 280246669 261601890 764978300 258750599 278283001 393897448 892398729 736252922 591579648 209423371 420147975 469573443 397966469 47820466 320675066 903902491 434898219 670169962 493411513 142826829 861792122 712754248 477786479 641544817 192022169 360800829 327863362 228591307 968844721 479636757 204112064 512944403 150758220 584622224 917910616 145729497 978971292 969678726 174670487 972992772 281617253 946387079 906826707 4593155 829936338 90131095 529241318 510107149 957599092 32568039 229218202 339284748 745592682 808518466 470469891 846662432 35632110 650687132 760205800 650916847 979337782 870879902 665995693 211660553 756753171 318993295 497930750 913720962 416521447 55431476 166735739 691507548 332077988 551736367 681692771 909878502 883187821 996298167 241789999 175602830 944259405 828805182 279192577 717740252 640857655 247504636 449538503 591634460 492695919 967357552 378345668 333619504 575250383 451662667 836547470 985765133 71103896 735446872 47216719 942868432 812754833 334383017 549780777 434011418 420390105 675139787 176957800 23055595 623113266 362316596 313354379 744389816 554057559 751473973 324886453 251759604 603508790 965372784 77756281 389594020 195695830 660202604 478006960 840797028 444598685 842630915 2058367 317065690 853568328 172689402 616616674 891078109 915639327 407227716 293491942 92045951 262214889 22542572 793478856 396136174 952748560 79470902 525490906 441308866 606630793 90195331 401394977 154486716 569898703 990042173 996971217 823574083 856530828 821291417 62429858 247243465 255627957 683948959 415327172 399668638 527850374 191289518 411784087 188393632 845732290 511303456 434542558 232711323 905041652 319933427 385334683 105013544 389925876 232186869 761923172 232187430 612573784 130166674 308418237 44250063 853842862 766523328 824037662 573262919 533470927 752104512 260689020 72747396 786372051 701486361 895591598 30104385 183600156 691806588 306653142 159201845 431095495 983892097 159723553 363872604 459485308 329615790 312772186 472524024 473108768 310090076 8924322 962793534 532236108 760816646 390931486 597463549 254094353 666803880 962352477 681857885 768831851 762797698 414982930 368745834 460934749 682384279 791237995 344666769 190370828 299393701 527210532 231028668 861693129 139827049 176442590 359258528 803932303 298401005 550175287 829089984 653360156 836943027 766331433 225132057 516867973 940085403 42922588 336448118 975156314 919808747 808234958 804717401 534792082 936438454