10000 3731
15260924 879757911 6110791 56787129 319144151 656236700 492029336 782751210 256601257 629910132 999027992 719494878 138959918 227467468 158794411 409797027 137542106 73122537 529761310 458117188 53615806 703453750 456197304 580559197 140617727 743084192 468984191 703191827 878222118 784844926 676995887 960370494 967190742 913664098 102883945 69458418 926011599 625348636 859891936 679044508 695385031 237172245 714563270 597282136 429478001 844605697 744473189 348157246 953719265 688537804 303680775 449030216 232852571 366508369 120630803 7732407 813784024 574545331 247646852 903108677 836732637 255628077 389242777 765758042 696855621 647398445 50674652 384671166 749911760 938676703 488711496 145819331 849993636 678743345 556897813 270782413 575992082 726772596 241618052 462189728 524354585 429813270 875414456 68414594 994463130 353407159 720430488 778547577 194674967 450687803 349423751 34854567 947982310 775482116 256695219 762827929 735915463 934023558 528416195 445421080 748319974 514095383 149805713 552608900 247142450 733741523 156765725 447642318 429696191 326027805 623926516 366632738 523355887 809550813 972115 668809536 94802326 568909932 519240626 715020955 608686048 212363490 79648522 948203529 699990068 952205348 115418600 515665548 334061777 940172572 894967538 723397461 831277440 463059034 798025296 704195647 779933841 231639620 412547487 309054694 708393385 411195599 628141706 649746784 170969955 292916411 937149788 904424682 481599749 779204446 580326798 947637190 301632476 362211027 816109381 849152243 252867733 758727520 504862596 923256721 883909763 514304687 797904909 426703645 593955291 426432660 491539781 221723516 640542235 180371172 978999734 932107630 78149408 229693436 150940285 21582870 16788166 269276018 221901858 853470360 941053689 945824180 240242698 205338553 619221648 891818244 441812365 92312312 869486874 339281395 806931824 136100677 162091410 995135841 684274762 820779389 831123898 17162795 907950197 836244425 381611119 495629143 506852395 690150885 314553450 640296367 361875526 568441655 494057923 952418892 645189451 138370011 346475386 990610742 359866280 973379284 991921654 928685787 664625444 872279535 730513453 514176784 440601050 330919674 532235190 991633274 635013431 511768393 787988359 342686800 636163612 910139917 936844047 204249720 828242729 49975190 559895494 715639094 849934764 303823056 205633842 409957896 830066460 247688016 742538488 697790966 335477205 673769985 973602025 525582710 204670134 468570821 260790764 440461308 895958786 520906950 229668648 929326290 58877586 845227495 364255759 982250169 821803126 870584014 974482810 818797173 359090959 522888395 431756934 138987555 174064492 766395191 301184135 225371257 538545694 642286167 782307945 68172178 865849203 548182337 887568954 530954870 861971551 609483511 101680066 121405525 321009932 433232614 433643360 362362416 411685795 626416226 365708590 871968603 537011916 209982923 547658426 334695297 710711108 447854593 622510802 418189159 915174052 156150191 155557861 747050392 860370840 541971145 542874046 580897508 646074928 883826050 337797641 595825387 902700937 16201973 206950755 429181928 217678339 369096714 543247114 174071415 53588310 780876095 328983196 207919279 640969407 932981138 262465717 152160840 654805157 661917032 458725472 351851347 561741278 158149614 232411457 821755043 64807765 965269282 670375420 812610878 435031178 794067276 442682621 934129006 945717205 947733054 431826021 65130323 637852294 896141316 885625856 190687532 799251946 416766110 769625910 515113064 820618976 983677084 609658717 874901086 359872468 202004771 369637874 229949177 61462254 952290050 923518806 35820081 448444564 703944624 770795637 120897048 108989958 481286093 319967135 672063070 484490066 425016426 969192589 240297172 405980559 233554987 314169988 611213015 831928585 700062289 938568985 575630304 368763026 636330044 849477031 327203195 555426976 837243277 318436827 120155066 416921189 673825030 890422573 824875764 430556444 434001005 669941206 348076833 726168526 948491926 702034408 904698055 877831227 974146978 830496150 946151716 758195235 76360187 188849711 37493653 818700893 225496386 428466862 109949524 887323262 529487934 666633600 612617497 216639491 77711305 810901511 167332590 556708740 63743875 91191944 351877695 621814450 110408570 252646391 699877174 380719447 335169359 939592897 759372806 894007147 373703398 310896920 104943082 884419864 533098619 48832128 674336131 174324428 439162924 235715558 965438963 714064929 801240168 300110646 528680445 162116725 654914501 810175038 407347692 329432388 530136882 332353092 370565874 277889601 896720140 936317021 314912526 475397181 865142099 192151885 98928957 154394123 744507833 651544286 291207579 678062926 530146792 372993705 772722094 551838551 96242308 780414073 556554902 582075933 841912915 744786962 523708635 287445793 805461256 939579870 976473304 552570351 425309770 355602211 299510157 462300190 227884052 823285485 301186182 135662673 966381604 261552783 205159361 753408565 86132541 121639257 131586013 226646027 73828655 759552662 894194249 582794946 767782441 400516168 834448122 533025844 870956291 286543070 163119257 814378823 586188231 510743037 321502063 326209259 433410800 620064528 270481075 237941566 410653182 100668202 55968753 590308848 940289652 589675824 116686196 387083065 299949921 234637011 899075437 919028129 216094667 275496908 220498017 416588802 419858132 34322469 147354844 314690226 753894232 40206990 390727427 344554753 542660587 550126121 582320020 516811806 805207455 908411165 712040904 830529304 970517081 600972340 427554455 531019883 3396107 449394216 934387628 206205581 45842848 523411856 552125945 123555104 371223922 189507613 299067370 533032647 784529646 653201206 233086391 314093169 933997163 325442950 452813559 757279950 738812985 774213509 735682464 942715734 352504852 865345651 796718122 598902077 935870001 630224951 721129324 965394540 465817087 786377130 533153018 608286236 222634146 291729596 108937432 654526726 603594078 130639203 662142430 946422260 580369347 884889863 98456464 880255051 167796484 413014656 502660823 586017541 865924449 342422881 251448072 747791421 181342143 713860138 494039093 100706612 831606317 57022135 658879868 700767235 670910015 522864804 496738571 663193306 54993657 365541760 103547054 846805104 942991636 957836430 674133082 472471379 468025270 828000440 653645266 246535819 703663199 64940375 63288706 292186318 544263591 735019924 909863270 933528528 818850683 581012554 734112504 362452645 833918560 301397817 163776754 597838818 954207768 132318040 401725885 954612494 300342189 880711812 277536203 250231087 263365787 940398758 658519666 602052576 968858960 631281171 82285369 743066358 59294696 80471949 237575171 168823458 138605063 726568881 644226381 628209807 489049800 466188908 179076011 267620022 78767025 218771839 84879084 631466607 321319029 742324784 449559864 509413852 247456928 417911586 807056765 277122532 376482681 996751464 946675237 303778464 4402081 448934668 998352826 374714818 558709014 986713520 12501827 865654754 271797245 106391059 828064925 9462280 612860944 65409530 565534353 199749365 569919884 131730187 578274956 732953833 120898168 443655458 321622579 434767477 225806542 937863818 801309663 102484188 553728239 154399795 653093680 814893155 626709660 546342215 546507881 547394836 570178272 213969033 666990232 552905914 328668895 996475333 91242238 758372929 171387629 126973945 200607419 650832584 92682438 655694840 104120134 462358101 337460084 158291593 917527862 192672814 53433982 845237447 590872983 360991204 925854733 747725275 714073496 167887026 911504609 296071500 358150498 370685927 543859392 662699419 454535630 432206299 380918904 421112760 451952049 326986879 964789780 267705470 898694390 82974960 544218732 238453124 450413228 299727645 389334967 123017275 320728874 683851473 450997126 689401386 837128688 706696213 433582045 956232114 768382553 669878271 569897137 734348984 308421186 323370165 156686457 63653406 293096731 991081728 408668178 68332107 322545202 734013727 293449651 6508234 289480358 207689170 66617445 315609080 245163132 907821252 541228873 473537908 95008201 858578311 756637770 36067489 526009514 392154368 886200446 721987566 488864384 239078966 730899210 37734780 734648353 758857162 84904076 894375955 116941471 933810762 22558338 297787464 162379496 495546396 854863475 439179807 428907260 807587266 198099701 187884183 706982860 114533351 767424263 744240541 375006796 28353872 274168762 893316604 708387453 375621038 88182060 497018733 60453260 802566951 522097247 190877377 544159141 503142375 348104156 785938969 101557230 442453816 366997229 939721989 718213580 982277767 556251438 971192155 833162428 536964963 689970047 576340403 639715842 434882065 735740765 89060130 532158154 790437915 694680625 133956506 670209593 843244989 877526922 228188490 792764158 490574177 939914464 630033006 878830184 620240629 449458427 337026242 820557218 254332822 801074570 491608874 995301148 758458 819904848 222938583 684343470 827666059 542255065 412485920 448113766 467681681 294589053 251007785 727087176 346068621 19423588 481796843 977137863 710430828 844616196 914945055 316817679 900396382 470817534 745120522 34186859 558649505 374888112 380165589 84756960 770908692 668825322 390992156 18124758 400468409 8884455 559400522 97309484 133900449 588774717 274146810 295393516 348708123 505742691 55144124 753610443 351840538 755788090 693843738 289590918 845560735 174268918 418479109 146614658 228681351 451229309 181278676 738563283 881073986 871087403 295900532 657589204 469396663 56582984 343712258 737037259 858292847 1574176 526891229 45657821 594223269 71425669 552146082 86249014 135929053 268800081 597824355 496860067 357605168 509140384 311927883 605134516 101839575 322828410 224529601 107376908 791667965 125441594 108348861 474760610 633701362 94935879 137285593 54729931 628540350 802576067 798610261 322344294 936842152 245388340 277030058 855990084 313797300 199622981 339107664 933666568 522609117 879237856 248494764 654780750 56969224 76992918 691508054 247414588 191985840 462715277 437690829 148317798 487367569 569943556 400822565 919296600 458104019 823605598 445909635 563452823 468959424 871473373 775976948 848047945 980145411 281311059 306751904 745592934 359163277 780814405 696301780 183581254 310784723 523444872 212322869 856199566 970703057 390374850 486635444 622548989 454165693 609589329 717605127 525441943 642920371 343966885 430199087 297625613 556507297 78362481 801335967 119178214 839548315 24553666 529953228 854586998 779525538 357115346 859137469 596957398 810658108 918981514 632522662 580680782 597619499 259708112 177102026 467016276 777686060 485392576 626332019 631918076 315153980 916382266 341648164 825400418 710246141 764559124 942007309 571636185 515062098 750432729 302559669 311018984 672090387 672002752 398405984 779892573 279973774 51128567 802723972 939157018 432796212 656040911 391432687 782177242 552057375 835985513 907015212 5085599 275465053 999293799 863918318 174405478 966076538 998305210 31358417 383193699 1931247 231586352 51439736 317252871 625125469 438417977 668277489 506354128 856545706 549868527 312544325 15197707 808969774 696296402 836341244 752198701 733885261 2825891 938100633 881769776 677067400 74171205 906328719 637958457 57244366 202254579 772203252 426474374 280298496 98421931 933326369 967135354 265011954 102792424 668425944 644232685 51059354 169110272 7123408 731482418 370316076 931429498 573595654 984656850 621043730 541187763 932806762 438569142 477625744 846874370 383735850 213302082 919286047 821111549 98325229 197299257 897444597 668977815 921486984 385116872 709140871 788807878 435315266 419805365 302431759 233901087 445243017 176356383 262175021 435327691 399255163 845567046 522586234 69734602 77798010 439441847 635991324 213875133 794914709 836027860 549671102 151103681 103666961 373472449 782815555 43711498 497187678 988980380 201043593 501322980 358492217 197682559 831406446 46681300 34546928 856525691 242406934 641921859 845837432 432545828 797838551 466383687 268659442 30493756 55807262 558369644 238231435 2208995 162565723 514212999 887373391 271692719 346551992 685798183 916707539 53442081 158272267 278727119 107660086 905705835 588746575 739404873 857192214 103021084 783132852 114069131 903861714 819638844 965756807 666114940 314855538 920242394 917394475 39484400 811275001 877859516 79090211 347246753 859556840 234014478 644898625 151148148 694885615 986874637 725150091 282020492 600559514 445376793 948044021 281491193 607562820 470746937 325661121 657398994 557958017 615997727 635152128 714198127 671431186 65909726 692333733 660806796 879984114 574225493 16489066 676610406 898342520 315080364 532574319 949362225 639489066 96815338 596118714 950413073 345769656 926379903 877722411 65958492 365041393 540972023 306539376 547075470 461202243 605225685 518909772 171510328 508556070 563856122 764847952 490449165 716491991 25373233 68525303 390259750 72566258 497434103 159040103 569228003 513830503 315054484 667170305 795263559 795984191 743403961 76712154 729066775 249262915 99383431 195850331 91164399 853753250 912197491 325278429 397851509 490112592 650572538 248600623 350546896 74425749 415010006 363018231 872727953 178986405 902581651 181820551 832614720 319578954 729861902 796750254 48553412 737305324 378916087 789267463 689708578 382219139 950896975 227446523 96222859 598211436 554262473 841430876 224696876 239259196 985595129 672246534 84736875 618057792 985106772 802794994 345988444 114345172 560077227 777521511 174680043 244220959 820898529 472090653 857368036 587822865 909672935 685026493 327848154 727075434 645337603 996020447 311419159 756348778 555803947 548718728 722200957 358221889 856184695 706191426 7925122 396576067 402111864 664798340 435676414 82723696 876947596 850423862 681937641 991850436 876010325 300361974 709668478 220514816 845151050 449550788 469044033 452952386 479679266 665981039 475135375 968479985 776176920 641068732 150700617 223674678 750504984 756627633 213071932 557993187 195525733 170233713 454176333 487443728 376779744 886257381 897321002 849359660 159528476 568013644 545934039 219638806 118642693 246357892 843541915 321944147 360534790 196379294 564403305 498759453 663411013 591758322 516942395 702465583 213536979 232241202 506363020 115295740 408233319 246755188 644669934 706510134 362412080 723604023 894495043 408936243 751441324 404690147 154492810 436308058 249142222 904202010 392989905 551925456 892070498 327258685 770662150 198986901 326135584 963449403 769647817 628234722 603356172 730196663 739630498 775743450 825340884 664686475 250478914 519148359 523685569 456503699 811355091 907280536 335731826 766585460 455834121 581980868 694972627 679120370 335108757 617853513 273267665 646149727 805772121 155917052 847628436 189101482 564097650 700279606 823444382 710485644 384092042 491006059 13569552 255900585 123811029 85763098 169055645 474048315 193772688 651199574 808462982 639058276 52513412 16675691 756765747 452700819 693280775 748930643 863977719 383635464 23066454 544545348 419628039 874350743 231247124 511466354 323482213 437123501 709551196 498994617 957624663 805822335 579161540 243127273 598179928 727279580 863660665 944350633 398947697 942418654 490102623 396646272 753937839 209826938 91745076 75545712 677428439 943159677 509390954 606661884 601259896 759913337 48219912 245386876 373207313 558005940 62881539 801014734 401909451 745935492 153736059 390786875 758811147 854694972 876638660 390336407 446166345 95843530 650915059 384767435 820054758 427190853 113908279 560034433 168269007 698073488 878621407 290747177 579639962 869227253 90507435 649779194 545391665 463877113 971134822 381334762 571379754 93855323 518473382 976086100 969518715 205701706 350427806 224845283 218917164 242999048 667576535 272551803 485510388 910299033 72055527 709839714 771443475 618077748 404590023 590517906 757446269 172270340 844861306 738234689 314429953 117883985 373018020 112707733 970031112 875868329 870628262 752127093 501211420 192487215 851910004 819192886 945313667 849159174 971596006 971786210 177009646 412024224 463641993 480266536 965997714 932508959 217906183 318801554 725692463 145990830 374518006 942109491 68718577 1566792 787542115 570160535 577762442 516051744 810590499 703797780 17345925 603236655 424549237 961182933 852183089 222250805 518492161 219747569 116599189 401512040 405272493 157928845 876697175 963986480 765107319 316591182 886877002 262551140 721335955 162534113 54755902 652269360 865752707 430072941 229489686 372453070 581145078 622162675 622554192 77791668 158970683 205437317 889245636 762973056 573417684 58727934 990057639 188886261 105996266 483368487 134658066 963766308 127517694 141114518 576778672 36186017 122254927 547035282 715344830 58895390 156784343 611111765 578805374 751427671 589342788 41809322 413511999 290605218 451931662 330439010 808399718 269066334 218030097 161066026 758674139 702407053 167090098 617437813 126722829 835352053 178669144 183896897 635045216 838253725 215122636 266517683 137694888 57482561 314536920 983431817 717079357 546194570 714759805 295011805 380667858 965651440 940841258 524285237 154711619 603606275 256873775 616917993 327894829 677306690 579841407 473837020 238870433 866934415 36919511 318780728 273660140 573417766 192271793 860584070 337772585 78968937 773326675 270865665 404054491 159493859 761987650 554451251 499591283 301705485 867648057 853926329 420777225 740468803 389285206 956232796 480465231 548097134 346117926 71479413 565335408 195070345 525742535 972629799 592990428 993766480 701805355 541034405 164652955 856427838 792402631 28137091 511835034 127104412 356997398 842851549 984568210 721126000 107625067 429900990 82804349 743991036 497609658 285251091 316477979 84658789 918861961 907038619 715734056 473930999 530110697 185728763 776035795 305822167 469816162 259988161 133642460 680528652 851038322 144856160 709748367 436040679 648412812 205160296 839756311 827604715 95301983 713261856 705306919 586666437 144129808 35919625 786361653 602057278 240740344 851480162 505199933 236511522 691093368 277205155 230467725 20010783 585368111 342889983 456816940 110941160 109820013 108912806 425144088 567924867 803785210 494437282 86854777 606297242 347817214 706434659 444276961 763159887 200917013 347395073 791838500 23540888 693111294 561849604 502318205 581409985 511848535 28627057 410603925 718907498 234507545 564818717 635365017 23850743 599480961 974364750 214230665 225691168 512517341 613674295 763971808 905287169 313902632 531441989 342943655 405067606 943718594 782151369 481740010 46633863 705998148 748064978 570018284 709093809 116315818 322252754 503599082 861651399 335382697 159107566 238921403 257556780 70640819 485293751 967247355 871208340 361860691 793826232 739589644 228154396 508454496 499678711 575041215 573275847 934829909 855966229 222802276 983012582 692837866 754172218 690632126 898256816 982389328 550892120 868977882 439609025 911358174 359013363 465970052 682759527 624341697 791535082 203959739 950403438 585754915 184869538 296132084 713594041 680854151 640381578 604078259 794677324 31032847 897684722 507978336 254499160 939639271 930349034 342403454 796653594 935802299 510490154 434095457 690176317 657504037 679586121 989960199 197719039 405706124 287386988 486170424 213853848 857826299 764245982 455020470 178193718 994643363 822835844 585565568 180842180 117913387 784345992 756693964 895169237 676636218 73376472 247334801 381626814 214339415 66822780 87404989 323203852 617726359 895992387 567395981 283489365 272601406 803990757 90112047 595129636 969524213 48374541 582266164 332819520 875440171 79558163 41392030 138952138 572131811 927795784 174056457 656103259 559659493 65343581 348443577 31035622 173604673 235662507 795028763 865229455 211122425 775984058 619069452 168019915 203980218 324363337 873126341 85759625 838616558 68338400 865706532 515930212 238627500 789381434 434221918 396384498 232579925 76876597 581445603 416105185 728864443 991737538 808725097 586123589 505321225 99000759 388636548 218631802 91670011 258143816 672924332 790737697 51566045 776422168 721682239 535431866 149493339 383596963 508572795 411462314 414911417 78722389 239359363 988073137 828282943 499326486 302387404 75597248 447112758 413724613 864170125 765201602 496214106 751216928 253347299 294002852 275871002 109412920 530673676 699402936 470760819 628752599 45625002 963733818 535809177 63282110 826379857 284970419 165916271 76691669 794416517 21477576 378387513 385671484 736977410 879378865 376225475 504251577 140848962 824722891 964478438 13102661 106079059 865687183 969270450 996230739 888283198 728054 650028969 626324690 586504227 387641589 636911126 578152373 515711592 361202575 687155301 379766146 132683848 51508173 91055297 484816585 826556355 309339210 164068415 19946036 895316929 275400657 85680897 69561098 144003243 731951400 565548692 848739316 53925715 236994020 888502896 186853645 851264628 189927142 154753495 191784359 691075460 654428535 944122012 466088784 284403515 519007614 694976885 645233381 154764307 279363877 798480749 420919583 736041067 426692178 814163921 21633331 445821756 536817536 883870716 982133944 916163181 229440128 933837911 224141943 181763608 485683309 697094850 311438373 912337391 825632927 620834366 206330979 529177817 510235908 84421037 15723364 231618648 816288080 504772811 826241328 936650734 838236504 216056783 942447728 941699476 178886401 62211526 196991197 947607953 220772252 224257104 945582178 726570838 654499452 928873141 847974615 239780382 801173874 59262916 326932731 284402646 75982457 731950074 213913769 405608220 682695268 196766743 929349026 817506143 26265981 495800517 739283547 686548732 589563825 719285951 478220568 745243790 774516644 883056972 186555202 773451097 785419454 429127986 665979791 150796910 281443338 552101625 234508559 852635335 975870776 492572215 518133817 47193364 139309439 399948205 985498380 940031426 782965523 106228530 396426523 464476081 943005310 280337993 937829728 23372316 784137148 253057058 270993293 162553032 241495824 299358194 897074709 469259996 563743415 538583792 809635758 403096752 573709388 421392720 594931893 991311778 382198911 232008083 985489108 572308097 718603086 134349006 2013945 710733155 2180283 469663002 242541499 98626361 42387921 63813711 621335204 856506726 779275311 963007610 706814647 96778797 334108864 437599068 813056125 677814939 78566149 198882272 840052131 252820441 115718829 187714005 499108833 946437798 366032068 210424788 311446410 812020349 168372295 45713779 897864577 345487012 194828502 322153469 164574070 415238514 929778181 315236867 819003719 687926837 623433681 917775122 947732555 989491362 535779979 284225693 660725451 276672393 304984872 392855601 651179499 461589345 413646315 49268396 413420991 751021416 122857527 667163816 719878356 939500826 39673573 393192914 116801330 174726888 579814907 433589354 516064907 647506962 313124010 795390312 767902453 585676347 600144832 461095151 907189705 997362118 992250368 929188579 849468786 137103756 703880461 442057932 739121485 147890302 55789757 811871890 35398368 427048322 608184011 361133368 992415 986520778 556636478 29470024 671957218 96515913 317379778 505370182 691164767 717148632 175808016 442102356 371260541 448994567 423836792 195334308 506703173 584772479 455050254 42772757 534413654 500093246 665580630 231207344 95692246 545585636 185542913 223124099 570555185 52370587 362003218 278982337 7752379 362875527 741330988 463820865 614361201 440279674 924686 785493127 468843806 797437014 816479996 901444472 380641227 399921028 116128748 643841336 146521394 162869313 290335494 826113886 680523097 547684499 287172868 26522784 846956871 69284825 191147225 1578342 801988061 427655390 148088784 488517501 957336101 273993100 68179887 687496399 364367006 373739744 394326036 324187737 247866231 905756004 596195930 333698319 172558152 549833002 820588785 315876695 438569382 404623512 586537059 756265524 458833914 496871970 970009523 435242643 184435140 817171338 105088740 364820193 432519719 526579544 718145074 39628472 174170004 407960645 87700672 709094999 808673419 946396677 62859796 386216111 944286618 594350897 266829714 51931493 244072779 186820746 305918794 790378619 381570519 351403825 330292336 375506283 801154815 557526865 433521675 886320656 701586598 713186997 702994654 263260194 965229341 655498790 626737544 253731418 320840321 835294778 760508908 394860181 515537919 229548213 392714659 984574686 778610788 260099752 743057773 846973637 400849780 732806260 67844643 943625232 974323649 422268297 358889378 265909326 215620023 893939094 309244568 658535220 331414015 842407214 364059481 757511361 217796304 474463173 626985366 860660339 181957473 920877596 221943378 627695609 620122067 887646131 886907542 258846290 970123090 216157838 56819805 910607345 990721051 656496464 753809470 485924988 252551190 911090584 619896637 460515299 516042047 292134024 190809783 587633157 78978328 69004193 106775834 87660368 654096555 253629153 508362891 925135818 849462180 2836244 6156503 551118424 338647397 215279522 216306275 13908302 64493361 231405654 518677190 612177257 475601192 109016232 895629825 9494038 410427283 913573763 61837976 762684207 416103494 358130902 193542585 647064848 655736299 112462878 77044941 945175165 714778506 399417031 684059451 740710463 116399151 808164008 770592038 835703936 464521934 177294254 153447902 27083422 126831844 552139092 849119219 264027746 646857391 348809337 780643989 415458165 18416269 615067392 26672349 116116544 741301540 773359490 27711833 304032603 288398957 65930032 542502431 209887504 881605099 437146207 49169470 246920873 380259974 357707642 752863286 85773476 270212585 485257259 160353283 233256128 647058626 832918122 473714494 929158779 189374374 713654185 533987626 498546867 423382375 809389207 662805219 62884513 421301026 565117517 773509890 259317086 932864190 189833845 721745757 598877981 880903841 881341191 752883734 624051365 116536757 558546285 550057699 581458335 276763578 76608423 189629475 124996035 992178257 969182741 968393612 544318682 888181214 987773710 481273790 753357998 580814655 426719549 869484906 478252298 514405952 67611262 644740464 344192234 360384861 621060757 306149092 167246163 245618197 615817074 861920737 446600410 979191167 871256879 174453658 627615051 942771056 557845018 367874530 249625948 650754216 339297810 159814506 161703547 154445898 594699194 707131219 484737216 476106775 594498601 833819802 182223086 75442690 603501354 197931753 852778957 6426145 52816689 527669050 615215321 933990253 603204891 581025996 937520938 940091150 875976872 999314372 108009223 520044616 707037353 75740075 242148411 84565795 598379591 531253576 28981994 352699984 622792557 390163839 477694655 840451324 803781808 815447478 214172939 67964330 756360513 805457894 895815907 870247373 947528886 897138637 73079147 932974111 948945272 206705943 110391114 272810205 242983087 873864280 842499214 788986467 833094413 25898949 821009165 919517507 643142045 327991363 267237943 866942454 991449208 136720048 196762257 624405874 800964681 76464956 558271777 943818932 415276661 451832010 668656459 409235601 376763761 946539372 360775631 964635551 891174634 265145642 902397760 589391464 948734966 389790953 259941382 777239377 788842729 110121751 956581719 97594583 685419072 467635117 280648208 296258249 775268970 742829971 614584066 107429270 729658929 318027330 421584904 813332217 19713325 608020500 105952678 641176519 749823379 502360265 755944370 685444994 659405868 206853087 411314021 850542030 608671802 663148810 502926932 396964580 366614003 965906807 156949692 70360308 530360393 889183770 805051263 691318208 797484231 240918991 637755300 274050554 756739657 265718241 293995984 307214629 723244567 413035633 774583072 855507431 100222324 466522065 67999956 870462689 68904157 392654783 683515762 57153038 77971312 392156379 525387138 615473052 74424018 88480204 448159047 384339017 799180095 545769565 616800673 739891127 471539038 648172525 388678066 62813322 732672263 991951068 940336430 165127555 262347427 945926000 237878358 869760317 772424736 618657140 102973141 783376002 319747241 628939571 542116477 921043739 903494509 457757260 735270665 602458668 853158831 127896634 672393172 358335199 776932182 569797535 840805275 202772233 498155251 558939114 171257034 334766202 300311256 68854105 491520278 534665888 380577234 135500221 755076451 343255496 175549257 939303807 577077585 970321093 452989160 950975036 215618025 529206724 278634212 584036586 761282280 288605872 990242997 483103824 404371944 101240671 191392697 419728586 626058958 253441679 594337670 425291896 657767468 31161247 581595037 259567612 899350453 304413311 746082373 510901388 525390171 914955201 307348768 779172566 336622889 654082139 358808570 895155053 786881095 789206262 744453970 258277400 262925839 593224868 428502220 177359615 273062987 452595577 730564445 403314011 37043048 171051969 721362089 995950292 159050042 67187658 298051496 464878834 468496514 696650069 572165187 918482325 144793636 372204285 363638420 772732788 337371811 228051903 477446515 337739582 386107737 861628812 849155295 399125238 980896118 184983248 513439460 488401723 412411810 246130603 702304317 733479118 957101979 935405188 27707749 269399883 713458430 636636975 446157767 720994805 576439848 98809025 493854704 918134372 79497947 568966733 739389682 701068787 566581559 578296339 302295466 784210156 300781878 986608943 551815205 676414721 445322283 211797578 353417136 831406672 846956542 96395776 849413805 310557068 619377435 562223335 968562756 211543245 752640598 108740927 636409 436090520 627492080 77490404 399995097 460123955 857527033 522083855 277711978 91650515 478273500 442169400 511487860 135956370 77814471 170909242 624594185 920970107 17819756 823490522 673224858 153985073 582844966 610978047 560361483 364710232 351941038 15300234 303556032 46626578 155924649 584351196 688445785 61551866 858235265 28387060 889867244 543242917 128620535 629930318 246232198 125474017 63337643 85919893 82297774 949071766 583968875 736809529 139941079 454258905 214791862 600862789 75189350 882232119 738025815 546306212 832993283 78978522 207467610 320394977 501945993 132283845 662117628 127787510 934897714 320923996 883891186 136759705 238760816 865875154 680150795 306155384 445338817 132462476 318059420 628684941 392396193 498953226 915949845 352286634 907073721 559925695 139713438 215224333 170126975 280501895 130711817 416386154 253665317 889267946 152774890 495911781 813677960 722706409 876903640 891261257 972701562 388123079 95683226 109244371 461556705 182749618 122491001 239550320 926379982 169168559 743874908 557277267 937746955 739867503 291128376 748317575 942488292 249491218 724999997 680529668 137582825 494672771 733541226 731441071 670354821 211345104 487328127 582085284 408605575 788693519 958176394 969482164 710980958 900317778 288486393 272902698 390678609 64744958 888914144 616397390 775790465 467867158 197716882 719094959 728226994 87835777 448457005 421429173 323453378 800742827 416833906 529015954 560394439 844882467 589598180 991001182 779400111 67134840 298460983 507190054 468941305 351403460 199794975 575336059 713135868 407304561 651706931 53746825 439034859 635358161 418845202 354214918 962228612 957527045 362988654 880852122 524793828 914057530 297086831 690320981 365696677 705324368 179187817 888911483 14960811 131553979 27066364 319088767 65768897 113941159 568073972 589557607 28671132 581541098 258780593 626596326 312049489 202812267 502446854 934171523 472541982 888345659 30884992 292333881 113772946 414098538 772208313 23358145 270530933 72581972 884162978 740522235 548203272 298451917 202149583 898918171 12092236 733739957 498085003 906084972 542093169 619791107 634820767 870544621 638256207 159360000 380937513 985034417 590605845 120439089 725810832 696217225 632725686 627807834 126873765 209516296 447934446 727606851 511797909 837519774 939599056 621717773 910180854 566119605 739166233 947986929 11040664 801430016 909982050 756336244 227794733 750845144 738687184 423905282 542351708 309299724 464452260 32648723 911413904 707662106 179055443 294051647 488897871 594336531 998212213 898657355 460119216 530524666 22519406 277291765 990756940 86759146 845861780 579615455 769797864 929952618 355462973 348118611 832349937 721304707 308593723 570713891 859686174 72493014 622682110 976273811 326613324 211630273 310941006 623630512 167401630 460209295 846151024 769871483 600258730 668574244 482745702 241495785 637785783 665864682 819046355 912007220 206584918 603460923 266749370 854186557 792029091 464783429 541904665 746140460 626793124 516016660 548798793 836024068 83520090 278116100 936928205 505499759 537341716 905075239 317601027 335117865 88924821 114858105 520657101 426954716 664960063 415151878 136143100 877295001 435823353 820423438 581053864 748519866 167254761 208885903 850791175 518136206 936208384 38183583 943398356 969583322 686182777 197433411 628654033 327485683 814754580 556565100 132764211 376995460 513269918 354062848 923237156 787998000 358001996 482885444 338178174 729415578 757969317 751597439 948550807 952575404 682281379 102028343 723284680 920629340 728413260 234037763 499431406 458818053 160242163 568939804 93251681 749783817 430392326 863034114 120339677 933403739 170842024 40070175 905757486 797185697 857030335 555740928 200705637 944849702 806412478 550095221 75919756 415221105 289853552 654972056 912779562 869531288 611649016 742727041 423559590 407010263 603346317 346666368 800540884 806371976 71705549 398266550 544052931 31697699 367442488 773713362 696139437 412910773 461503532 779982570 304505221 140224188 130007990 107029058 482152721 624776612 667651893 126692451 951206093 627699462 164967299 37492434 773685853 895207056 258035013 43506549 243005246 587335286 98133995 317735288 798094573 506037653 689846640 505288560 351590850 643920217 416310311 877559069 278514889 817695851 479097377 28166083 94246959 798187319 742830094 259044767 708888852 691603983 801367071 558126474 39832770 304644233 185645749 882371152 720893990 458412602 75458724 456956130 37560624 670763166 477371332 428807502 372456374 445505740 201920602 727808591 29119512 662079942 268109153 139664006 15339481 222414213 455176313 462450737 505033959 482403480 714521271 476395795 414103058 908385571 973191252 686626272 659070658 708308579 799368517 59683073 870982943 688820454 610121619 411311271 850212678 104869995 264001387 977215391 12534058 372256740 266955955 375142252 287881835 932759697 518630194 738927988 872822751 736976665 189441834 267633523 360437156 757511200 981074847 37192088 709074313 721753397 861366690 48384000 73373727 530483262 413028501 428858088 788550197 137525407 200346370 354940765 956503097 19340938 624259102 779616990 449157695 742754804 899446678 608630401 500230375 290860053 76952993 718628337 283065160 874269540 696539770 426338404 452877594 713291650 755912734 784588923 738253935 22253046 471648333 313661028 690795548 553332572 985343159 501396460 709103371 719254761 464548516 173613090 602846819 891973677 789029844 481537182 194204283 886977325 515815480 232153554 236300713 981949172 245459596 36865084 654017663 845571054 666083846 959696924 59487937 448472295 325681143 24284423 928482726 440192617 483118098 386934755 989703535 54150328 979124991 566461732 89341183 827856777 715101142 10045615 797748523 824068278 864375136 55687354 115574096 825572764 161554881 88524021 343044587 465774209 311065405 500246877 644566479 55444693 20272439 53748008 189439466 350380241 702893101 12384641 555846198 473937418 583098093 786328531 243811202 415700020 10178409 710909371 331974952 328812889 860357304 736320921 816995657 466670630 9868847 320009450 346030109 710448742 277116802 609547404 340834788 96707648 888236547 851002854 622685148 195492711 520119489 129775849 649341363 768868146 522577283 124427493 881729725 657729299 396489009 263049822 427202229 396331089 844342589 137123145 223277486 175185730 174984688 28664963 782044273 303455331 374052831 492304475 186119597 904677056 249212282 298944125 880143720 429314912 19097813 873935299 913600522 207014935 513563642 27783047 322769631 777544970 949614424 931029358 177858659 153539428 609704735 916255800 819533450 118304004 781209886 846147152 407269354 591349799 242428781 947333416 536156979 728872966 99274181 128046590 141427849 878180639 640933299 303370398 589647840 433961035 885060190 409366590 947334530 154247283 442547845 823317412 754835532 346050366 265974143 699674771 902346227 286502504 737205193 497131421 76465587 642915726 961011998 634662641 743324566 374136747 454929452 355422232 636502143 795196209 170369663 501752212 636353382 269496065 514259462 866330362 555492825 314884803 60808403 331508496 166382403 846924282 223922297 870668926 496221111 253147495 426982838 971771581 178739284 881657018 152072928 798402365 506697894 787139207 788184517 785871320 604038430 570583449 282189800 672913769 54320798 351807968 618179689 176469974 815494502 904256951 393013834 354148759 172962945 505023020 165593334 734220685 439371461 232832555 512105063 629173132 38455993 152980390 407309537 160476180 487922633 227711252 932245082 355872961 687011216 149276418 328252112 769294977 741113769 18904188 328764881 452588994 4403816 811309693 685757595 587206054 131635701 691914169 160372487 891707699 89880730 92719792 917295338 233467632 268497018 722262889 616818302 856732010 642360844 14985830 608267910 159625590 537625803 287350053 706102131 984334130 898108288 411005267 784917462 281858248 119621550 962258369 271454523 347992691 423446911 707454947 759994314 529012090 406502132 461052400 232065943 762552297 375717576 632052625 914707642 648004711 903655647 613010664 75956493 392581950 174525335 656723558 301387515 80260647 864829966 896908876 517074532 384812034 441391271 138894660 299138755 770548734 601960823 820402910 245961672 635251815 527229032 32275634 901052228 838131742 478208942 630377543 430214020 971532758 61372754 628634013 172854888 162074929 714577367 363737359 274364108 265935451 87398371 652586738 183079770 393601809 444735927 407462572 350842865 966643758 302230280 336956969 801377188 315534193 487390970 15002085 702534064 948278636 298245182 432826544 729479205 971941992 11809652 612496928 913026763 974685294 908614306 663186252 98643363 501805590 81025562 523564209 969215387 625165103 545680755 295642748 58146129 682903136 949052694 700647277 440437807 123952013 441560612 120232554 981094697 968933156 865768669 284395077 517309879 287362968 670748788 600764076 380224514 966123456 809824349 789550496 603791204 155089054 947649994 115991049 38931861 851552808 140255449 336317247 725227752 335717942 426022682 662834378 191513860 394989306 243347315 915257914 937335645 649653513 333400091 256055658 23783093 171384830 48038859 177407767 986598987 802772262 499064159 503497866 731335350 117285666 918035790 43346759 11740034 74639046 974272297 701463841 608299291 799483374 994977925 172233846 90489940 83002890 272618135 273685033 508023351 697855114 46814289 700842967 721269118 820465857 714491325 882157787 220134573 748695989 820482027 710405884 258113957 968864236 749795783 954338827 137574200 286417039 869887682 784498578 776591536 167143561 75603822 435582940 224808141 74093428 193945387 651903337 79525555 438119053 640468092 683154879 337789085 218804476 319978200 826918521 122826150 486571196 464427668 470786621 325934864 78154668 774742688 736436159 731868842 525039434 300654143 40874278 587807130 43954335 150688457 182954862 389538946 725393635 653555824 984004347 17076614 974686137 493776755 28297452 550048296 282124387 744517903 83297911 324868083 844768653 60123520 66137073 43510276 519591195 494509444 619726054 120464420 607026146 689753124 48884624 735094879 509785656 697201596 502261693 780937930 762469253 811831619 659190418 50081594 787058976 598183235 315937649 894636272 744114126 108513436 267144332 917618723 861678301 370834796 374997894 405480555 951959191 526520971 443736960 583329917 512937933 245631257 946486100 78658633 876237890 105458601 835872088 932801900 652574269 72083774 475295840 576944167 718603570 154895361 444841152 931916665 909145593 54984470 238084178 452296122 361381351 519049982 322340918 72848554 161704100 741631834 564353826 885299390 847835729 974721194 642874822 993415527 455315749 819162925 422540052 697109251 421861059 269461886 378784203 761439246 36807789 291705621 108577874 207984935 567677299 417062433 254946756 175512459 566416750 3995147 787600894 40720257 777513132 122932948 376871251 141567080 447224679 447384546 60648848 144222726 599201008 306989793 347363872 359268213 178636206 626700898 695821313 201661135 680273177 760795520 540684371 616894754 256449014 963798749 946664823 185490117 317253749 617062815 239148545 243852215 845092264 713691311 128909949 969990666 29375278 931496453 809596334 161550055 383186437 738628807 797072000 40292733 225926547 266416416 13855269 170503148 176239964 895674217 682155001 506727467 834039154 607323014 539467352 881657065 968583514 112593360 614639274 348378657 369512285 536799148 884298301 489506231 952264896 403427677 328399815 873768038 106725710 924157435 331568895 8570819 347589802 401905736 701761236 468689493 871267455 762034466 484040966 210839445 160161127 872059035 540426372 472756427 223451202 508616497 238305809 479164209 437128515 386587420 656512694 421350122 536714361 21250261 126251914 182682020 396443838 582649548 339846266 940629666 452334342 640365694 552079352 992457136 865858719 126472106 555683921 452069521 142633998 136409752 453765661 582797328 611328865 893801948 201878707 489050246 810337247 749674009 132854604 197513558 423186155 743616832 347227163 927084965 543586023 752678080 893663480 137335371 599796317 684034424 901580613 134274045 255530004 320720563 230232434 720059288 709728127 847468934 697216127 240063338 540871471 617901613 813205799 121334942 715385980 475322752 919918568 771492690 869535001 415814928 100458543 947498181 631370709 799355495 703230860 98464543 503528645 502842959 276632710 75650423 790847461 207216351 983821975 181641485 423449153 290217995 686251088 635843189 780026026 795927175 666259988 698036609 125435378 698810273 236740802 957080609 36983619 104698131 404337420 776965010 493729464 307125774 60570193 41336511 358987201 439181903 674302514 555119314 238858028 842521760 952304466 731276682 938615796 163201109 117083161 237320496 257788827 801158076 713911486 216335831 981290580 934557103 787475774 804609643 236358621 841943907 112223768 715065466 796252226 922425655 744209604 920193147 39705242 103074071 867412205 683680665 125916002 907929200 342530221 776516534 195987654 892103464 745554234 905689609 521946771 209415447 791061407 359470335 682860893 206858226 401880127 498395729 573911227 624393552 821987973 855063021 182738035 98246557 194161399 124162849 235694661 428310968 618129086 295224380 832674836 803585280 245259331 457383326 543442709 333168238 702998001 341537315 735767425 822473671 18328757 428424373 730748872 688520823 577720666 60751459 579346088 885732251 273149198 895614521 497137226 992685880 443485695 462867784 569159094 280460049 846984977 898956407 872066847 932547026 803379133 288981225 778291368 449171599 89032051 315394933 384068483 715846700 615431610 733322065 114930844 442194174 782201301 522799127 678552941 811620798 538695062 176270130 324434164 304524642 360692210 581913888 642965268 608653546 366811729 923072811 533123734 425363664 626367433 383568920 96560472 584927441 844062316 390108358 135633993 54618535 842433126 719345973 926240838 384484822 523498354 499893808 214992089 921974973 195375736 63132615 794628192 171830786 482578477 519190183 491244551 322452120 454999867 756793948 326615553 823141583 265454931 685397929 936780243 702951617 653787558 446198758 713895362 427845415 395075469 73607851 682084747 368591617 667046232 809327115 888706957 603265155 600554290 862006915 904174226 367733114 432758232 28841442 494112316 642255378 762716078 161689893 182860609 93400511 283280418 480750778 939732984 439629300 883216953 595664088 418905273 589891862 965093622 785435233 610029675 481196839 201388986 452717949 658800799 193547846 613815557 649405861 605848145 963869528 210778044 465446323 36671613 495395046 412486566 152459893 430153889 403352021 833450619 45546614 740892577 641081192 936404112 437337348 192342492 236765332 566067147 270074499 184912961 991657760 612049004 217952443 881005012 139454953 941197380 366834246 99112241 210094349 928095471 312118547 426703386 479144668 862882111 998370631 980199029 95812712 624082065 426351911 100630885 172955022 369092642 106339381 855273217 364997526 342952966 761457258 588855127 717410521 602506171 782105243 877000770 440892229 200389565 402934340 575468167 125705324 558516851 558468749 401052944 641998795 379249598 576991560 12445258 752027941 812612795 854593878 372611894 940607830 210662435 917187730 415828842 855275278 897760642 812250508 597568100 423981444 837472566 747728181 802825756 263046232 763120223 93281040 442709484 886015564 765006785 406610524 32494616 970750222 417953735 688382038 206243028 347714306 3506552 839947718 909193785 754241425 312694439 487091078 559679492 541287189 755886618 88093655 593487445 568265160 241149238 122122538 997859777 565255611 621854900 336507999 656040029 408589429 328645646 131819591 986438118 831209916 465377925 913969921 893738742 644228243 364584593 174107260 160231017 111098848 201778191 16419433 885370869 502531500 269398201 747104545 934292108 680538000 245844719 116495770 460254276 191418282 463510538 675297914 686214017 819610431 662925042 356466810 989939878 234388443 421248997 722282796 111905865 491710072 793451236 530501337 113843001 738893474 152427857 896531461 909772455 660269206 847019030 667207105 77502667 10211089 453202968 942714415 217690073 51900181 568404123 984486642 385883687 670288232 596223619 627991706 662525961 84173527 201431129 560490362 64748331 933651251 946370180 528240938 75916088 268487543 898179796 646733893 668417119 40773382 241954016 5953539 719238795 532848865 126739037 68572520 741493473 825390933 800743324 582008735 555558387 736232605 148583126 300153971 740057214 809705850 413959163 686942595 284487389 480136840 827578099 878499300 770167619 259911762 219499091 733755885 945793515 731397339 36263918 15304978 691280483 409420899 731461165 331254261 343693210 532424551 156158083 430400300 46943541 924915661 199150074 270206992 361473121 652742398 874159823 2791056 707857465 48145927 656834631 677944835 344683101 756376987 770446318 930026059 401177463 555084328 115485537 73929713 899475694 19289168 785219974 186510512 301372784 268340516 420926780 726879228 678261814 813110782 688794151 813823384 434967214 276042624 19667494 591357288 457794809 344181299 932058824 473409326 766487233 7543039 154409078 935341507 519429585 689273373 131866843 535195441 622335025 840367338 931762784 401367178 388450359 147994675 98442478 903343669 614191794 617224693 198804019 38991366 373112970 187219351 177010018 310038621 815256397 933488806 825032150 348123836 180023906 73430765 820277302 98699907 330840061 332060005 561146666 972120009 735763037 212127012 305538280 384951478 172262368 445635472 556747934 837602231 517694876 853073911 470695006 29709253 65543872 844638223 509708179 117515710 228935350 622336274 350277272 362457608 951590796 302066584 608041835 905090593 848453538 845366892 982641160 730001634 847154827 929261826 797240649 888451131 860574557 786534415 124226716 631494374 823711926 105068857 820249756 63980022 343800637 127905787 590012530 404438767 683480669 186850828 674896588 246047299 477999378 733440295 664937595 371414693 731958002 159072970 797105855 541038867 902974849 935366192 713815277 994893160 616609231 998939680 594413174 280490490 360761231 406921073 875669559 18635622 186148402 827668060 410513701 212978332 261018887 206796118 301938274 705829460 73778011 650817388 420088605 722714704 199961943 87823269 797106967 905582071 500275041 340116130 320619693 939056494 484927170 681873627 746075175 1475754 362289411 400636619 657223330 789551085 174049846 231307999 518633691 903589473 846691451 622937796 292544242 721894195 567886711 753592674 274712222 462559507 832695441 543872913 192380440 858701389 374870719 235202155 293217642 647327128 210147619 357156260 55215001 382780677 336476252 1422823 477502694 513424733 793462348 854542592 295601193 598996331 384766815 42892466 45358584 180021897 73847750 688993338 895141503 552275620 166981368 17633433 949755909 331248513 787746454 97519249 287394894 300306747 861938649 710852615 422204028 815192418 536820483 866126707 364623862 635061013 379438653 154304757 666365786 522954959 808008504 588158492 913874366 692728517 234018074 937939407 978982619 288370900 346879046 770906691 527372346 513824232 297792178 583964486 915835131 876663841 896427903 36720103 499724314 499652935 253883397 287127594 466413142 569864093 477230756 727012367 554579165 837739543 520162027 901729678 872514769 514059431 631279537 709972054 284821887 557927997 683190137 184499707 595848130 139169096 468484878 100183741 243695129 33749482 97218366 459742913 311092657 190185092 923121331 620427133 958598079 624224761 938162345 801047459 96623751 242108722 49770363 863541336 796135631 862839478 561808528 627514367 928171429 377854429 859859141 357212691 111721744 704397160 569647327 459960103 264039273 599492840 169245962 116508975 364985334 832209981 334845580 49266906 663757322 885326019 592451541 852340690 238332304 611169395 121755944 659655860 387145524 559721214 131979583 325768410 703249000 746461183 986388309 396914270 919388989 388107969 598077733 771405543 961541120 367117553 426348858 453685202 833098420 878465696 347144952 616883521 474247247 93651422 834003901 562055209 192566778 710406496 280261706 55304271 662804005 121073322 730507789 425071989 862652264 528674342 73198030 720685787 759248030 206337725 106583766 619039500 2097016 670458165 492626384 578230928 295796203 73008390 681385422 935492497 73347244 246321141 423563170 315770246 630291997 431821418 858582133 477714726 960154313 715851267 927336757 209433976 54239668 524350258 63110916 665644706 799153711 709957383 117097385 574037327 545592031 459636360 779196108 728419823 336992580 532890466 178891215 852510889 278487762 637284780 644746558 730132181 548129497 511728871 793841215 493694217 332873509 367384420 475020666 767757317 757515624 18814785 646612630 495623114 376610118 253108615 344539157 258993288 949575585 669208619 926871798 671620369 185922653 507590611 794989366 428260350 245255902 796066114 845783049 722365657 591344723 165353684 984793770 411146166 636212194 747594507 399004969 274973269 607566339 581242835 851860628 684298285 296830421 651354465 282089170 807280652 646558718 810335011 643000151 364510375 922510935 429570420 525813304 918097005 921314677 596326530 124215917 863800479 174289859 530933797 78533499 149467645 374741374 337966224 808151568 148499056 646947188 248114890 380535592 960004611 642514298 977678401 509401803 891921786 728889641 601991834 905001980 851338209 934748781 624070478 334643935 23850663 599169548 480885749 73136924 877730993 375830913 934137123 63316878 297479406 516174382 696258468 908256728 90063196 761559477 106573562 984932062 188981948 38197385 712131055 3997948 721648550 529787227 313886250 184166325 79326102 583156636 731643371 814163452 221577238 546649856 360190691 801463924 563670002 290654358 891224538 960285298 693816317 757763998 246726276 62415095 713031285 735760912 754141261 557885900 184271021 388294023 827925366 175778252 95735209 146527416 472877636 661920149 768681545 105207559 689605751 900612437 314946164 738840982 709182701 214994963 639249059 277099454 885123918 855107028 364015964 951219600 984177012 255183097 410964002 989621080 506299085 624857958 357390241 196430926 871288773 191530786 843843196 309275771 774158264 69103672 432722849 792372032 243509250 886302925 531419963 88856363 569564881 605030012 772122274 203980754 53566857 528715747 11793054 449158629 147014651 366001837 270959764 163412422 535705372 71196398 893102884 835201550 44930535 93216307 540801317 923967489 938160949 857633842 546656273 581471829 511445971 671118224 172476858 454620943 758443705 832833255 737811134 722703818 699616289 89213694 870452347 867687106 605547333 112348489 897993122 66450723 860442754 335311648 775595871 945715617 64720557 887851446 381692468 928166603 768129501 177659058 599977508 877002298 816867016 181056634 695143131 386210541 632127666 323331205 108691438 531490402 399996486 610235202 443890420 251456557 317222597 336209113 988540333 973563182 721556927 533687405 237171270 969948148 358334862 995379386 795301436 498903482 480758396 549824350 56161520 514254065 205987624 22126718 649489963 981738570 109107157 179378675 228158434 639204047 532438521 778233187 259553758 243944194 993899422 613954179 814932956 19708055 489081732 487566528 806405024 624558535 414106902 17034059 777544955 277615979 77238019 453263585 258972677 764478827 468814699 386627266 535440242 214300142 425380509 202020939 751119884 296596804 544523340 291690568 869617537 97655464 541145553 940023366 872702531 937745400 290994273 62632549 364423956 958098063 982986263 168906077 271419476 280491006 803162733 551446928 17783596 971035293 189414084 837433784 869695415 467288567 351791773 458398157 82413853 32773630 899286441 911700319 324957670 5592134 595270184 615645523 759644871 980431004 115051376 372367058 652768026 701620865 971709998 563592282 513924477 998570928 701356279 953305172 886643404 502318785 902333476 96202900 680917536 630003288 345436994 868023950 211713675 983060768 136565000 659403196 483202538 961933112 26907659 639106374 295568236 453088136 841425811 28090816 174117669 556651665 624592012 988589279 452823404 836579600 388940406 266327872 520652274 390151214 482823061 202650812 616174176 304653023 668628460 772695325 852095033 231111602 891865653 654966092 464166435 498167208 160647793 32400593 939831486 190398795 583089127 887382857 998930444 576359105 600761503 318652249 92094659 728590661 932350088 299969634 948410851 384759698 71194466 683165548 760233433 163265720 784648248 831721193 526467415 177903254 974540121 900600998 10722648 819517593 704199342 759419753 174157139 29007000 65221424 742494715 24045103 66359683 288411994 347129178 353172275 882782144 805391187 111813650 570987686 122994015 250698278 833825443 289492769 866036916 739644530 470342405 976051266 39922424 227060098 469836141 672738072 66826801 428330887 643263107 514568189 713501172 261195731 125647883 422735664 138114614 403494260 672351872 196243148 825612110 498545254 474203209 300763022 828578493 919314229 588808514 485987478 497105093 708707253 998672350 951770403 547189455 869825487 573873204 910448614 281246318 731553372 360305100 7723591 466823933 692079539 948451134 607867366 969133190 870506024 903548892 515332506 202523734 823280527 85641088 849931760 217227383 980063929 688089142 311651763 466732495 479488169 4588998 159326118 11447891 444507605 817498786 94164689 944234097 324033324 330597329 646147781 406797557 725615670 69477288 580875446 51912484 205006598 99218715 634004887 991963060 711911585 925528693 355775508 153014727 110571758 252789568 567102888 352494899 367994700 843630719 321137211 645620912 950219344 454195015 162775092 880152755 66030715 504084254 968149727 714090904 231448496 360795289 769400872 161357239 377565165 937061688 720959643 626557579 785751757 765476977 735509053 909155103 49128949 547171761 726937562 397389893 724764476 174422351 673326630 217918269 725491130 658212721 677115936 256094159 600261456 996103521 542363178 950473550 215097385 117137389 311116117 657074001 309834646 103685640 772552622 632758029 658330444 114729927 484416036 178966651 667778981 688181967 390702719 605808642 813553073 919322015 635871538 318160341 985050318 557091734 728532763 15800152 17382283 221501363 487216113 982563015 407075625 173700810 377728914 144900157 659583556 754862894 376156029 739685702 521375538 722624005 995912866 622689180 847101019 102599165 773997608 134678511 303233221 27463109 502517498 281268629 645625100 118640216 767268525 501713717 788532088 157604307 210838665 354397764 145229542 838816989 753541258 528538092 612967465 283977207 451726338 491847365 786492937 153046035 425144066 438739159 242027532 806105322 267152627 16736923 889489082 446740296 970148340 113699475 995499890 687426772 319282196 705092725 850747863 651689742 21809923 84783811 561153006 173106883 583495541 563642830 368946521 458290276 767239317 41500784 209786666 694004516 666710574 457203330 987496970 634334285 761716438 802092869 262061197 541582397 212624751 630530141 383890706 548231574 583968220 596030460 782206898 850922560 72541892 705510317 931725857 462492495 673903863 508395399 997722044 594592926 580256219 586121312 900970273 863336433 745574007 786106877 109195200 558852667 146011539 261888081 934824482 777081150 714786946 899978802 630390121 492863253 986519133 819208756 614259355 515735118 462273065 174745014 799036768 342640933 326094941 997850525 685790820 336269015 48605572 722451622 887234984 803905855 911428382 633463627 573039433 18051925 409824793 518724752 290642790 748554252 827568498 718370894 988375332 585201734 545800474 232028477 48990318 52515518 408928774 138391726 761396269 139732097 876904839 555251105 983339852 34901232 638999699 125319696 449937444 302755110 37805382 125158854 313028360 365393549 939352835 604804299 165808790 511716339 562977749 781182005 598883699 969524733 765506 755053441 323844210 604226692 285728587 206289418 900787597 311502959 845168065 2807140 139554304 73882876 576020758 515053393 525539610 134862294 261802793 664754903 740347164 763176859 743508505 528031552 115541190 246856230 205623278 269330394 941138940 681174502 828588014 965023001 55621313 466449723 966532504 298224085 866275664 559631696 724767797 733411398 181058478 679286770 876413052 270103511 392655706 162726651 564317179 369050096 659645748 182492618 302752921 207371339 259791911 221910125 496508936 526282011 661415806 786266177 193576462 508173943 107445485 826911905 388850404 969713611 554792170 604883584 408438347 567096329 983633653 787971873 272672637 614431252 661822003 358365322 69233010 559435372 131435911 363329606 547705102 874617304 472047111 752311301 304055808 692777492 596075261 751837513 32333273 957481012 763435577 455036818 381821378 305109857 386470749 57957100 774801559 770531172 103657186 704174542 348269511 936012860 979536083 99975136 100024848 631251266 466605849 188699451 227536875 563600264 657931450 497740818 686239254 45893818 262271127 622393397 418404647 213586390 998423969 816578157 779148589 826222407 575894746 447136983 109330722 161457671 2774347 253173436 302356404 111382226 586009760 603948078 644470755 998779697 705379458 538229306 585453299 575657458 53509033 903967883 149636545 647687808 714100966 503023060 840679595 941797244 407035232 119357714 195402427 309453284 588520112 404398681 540078610 625326244 843796500 681909900 358588881 691654230 1708032 285921314 924840639 972083032 273195440 820455367 155815711 678314679 57823320 336915426 626972765 195676039 332834674 639330403 542007035 260883604 918038947 454145216 2482690 798299873 959177635 576721280 545044714 583652715 164844665 403623686 823969036 787475621 172050626 419679983 912064821 46013107 68510714 843881204 773179773 475879262 574832995 209868331 769546522 495800898 186486505 177958704 882289920 914296367 964411004 552674257 452771951 591403944 522526904 849900901 669154343 832567435 178101720 206041701 581905365 465609400 242270925 433808767 912146176 131915348 291337005 600898672 769253237 635603463 990617504 463144496 324321039 68843964 31059829 514793691 986850492 472773864 323143742 976474613 98343888 561288608 349674422 706399849 109234427 680567484 633436869 449765360 508412326 535760328 270653435 712594595 434603506 106848690 48466855 490457753 837872721 711104606 26564777 368420227 771517033 46978504 733421874 739629117 153427149 769777095 130335772 309829444 814052630 250930046 311616906 762664398 198029611 878630033 214003586 622401884 214915327 728466617 202241994 458504352 579423912 843041153 40211106 344160208 628046583 883192192 240941074 32056692 568687846 423593239 861572590 133433476 403220623 471688865 81528606 660528773 920104904 586440049 400920767 492291009 584370955 483958847 488444337 360507982 166075679 345537049 93920586 871750155 213681722 712256606 595980939 419255890 3493478 759412746 846038376 359264757 606790632 817282332 830862542 390099491 533173657 125740209 502113917 853686972 175506569 501614301 376054675 904836658 518597972 776477450 170521038 419898045 955708556 85522690 562310240 846084292 988083648 809980846 387683277 498963498 549761708 906813786 519601887 229476058 428564207 492178065 54536165 955167002 724634639 413156084 278131205 727775087 162932124 290485885 663804361 111200767 288054535 83151289 919259744 510789931 531183799 136772673 810765334 365442795 293669666 473436835 207283285 660741576 123163551 462565720 872223262 629147971 431734033 398076881 701419161 72251419 625179926 998816098 70531003 490325051 799527088 147615866 681158850 629163120 450828153 289167180 61280382 909792859 974201372 435412639 229304787 459642365 105668199 765538787 228094771 900058908 958124811 776892832 119149684 226399198 487043294 641552495 529953131 79452307 176684507 483785721 738532064 772142776 923402035 463549875 26625671 958732888 8550850 763053671 572676503 743964429 473937412 650326046 561078519 492122108 812926608 575617994 141399500 614947884 25775474 818263568 526952609 795266960 834604436 368683437 646526515 298145510 289776700 991969337 330872607 40957141 480162132 582245456 263355973 771594764 979342489 19149962 596429404 560582371 600478228 873513374 113093159 840928480 123000120 254491428 294455010 988037398 10693722 506958790 410131235 647888186 353056375 362992973 145926267 507580480 323927538 503622021 506410646 234039740 691347570 324439660 942250252 156811593 373314020 323188134 474771903 442839673 56575251 856876875 645182063 922709210 847390024 570636349 874946029 752776306 574444762 586497029 985486821 346253700 235629146 177462619 244124402 801248062 522750021 631763372 504453857 645925654 527043202 189121984 520092109 20568305 625284203 909670759 272034664 672088367 558847182 707841652 764221243 767222309 514957001 814625107 769222381 87524252 945546624 475299512 246865818 921301131 450548136 848449313 243312721 166591540 166157292 544925402 932856542 449970389 76771517 676681815 14713188 639099264 629623113 437592464 735877102 86606489 290753270 890661867 230298379 892131404 529278193 332341839 15765488 208432735 769529708 834852920 814135623 394338780 396109286 122640492 112726108 497876732 963663196 402584149 667146897 378990199 445397640 817225524 945869674 680010349 630160335 2780926 66969728 982819052 494741206 640936929 395583231 482048623 176262836 866281056 85751342 89526455 232498901 660411575 791561987 372104918 487704828 634884936 841817690 345734486 601226204 893752489 615876936 992708570 318232198 935962832 994807570 171598085 181528722 92465475 834854335 449466140 507442730 119856706 857632705 77203368 449155947 99413827 306575222 626131813 105522939 846426271 824885951 36266686 301575283 200570926 151662456 273124894 810823447 444641158 627943476 145375471 753921711 463073634 666596489 321231339 760532594 110533008 421899462 203556695 894019042 241040808 94891673 727729421 526561193 481596958 372190543 501421773 245963937 566245028 505994740 379482986 430528700 37950758 841565839 87171810 958859259 541177086 773493515 574079080 402959798 104310148 611163631 273060607 119640194 712071257 73341734 336919240 555242836 110011851 359352276 187679535 530218323 16009242 960776822 59307143 818129204 2956678 31840972 734152311 817874486 63983992 534027572 477256994 30602447 414533367 991620392 270776874 477074676 11831024 901737331 822836556 976682130 892542685 930215754 475344263 718567846 207682789 67280198 155557017 757759025 652614086 893138444 829771852 839691002 593186301 474337240 961412318 323484574 494668485 816537791 486945011 58016849 996244834 39158521 91760776 981293705 512983635 434160019 336806061 230642098 628427742 778203450 607468642 22738766 408207671 585019180 666629448 825001066 501651102 10906345 369578347 254923825 225540336 435473940 143708263 926837977 122159968 262593848 592535543 658287992 106826494 857823559 155084587 463263909 466791897 702921671 726560370 753308204 827850131 266909858 334712293 809002269 606499924 720296227 723939690 136829054 176673643 982050799 691912110 332577273 596059755 486401125 557892234 747646584 166578900 797079002 989600320 630320154 9632833 730537500 90768086 419252998 189358567 120858492 352453397 904411107 429594558 861521753 953789655 608552302 198007543 367115625 86806706 749647412 830983851 857374408 737929454 203145043 965289165 651968829 803067692 56498878 119671081 478765228 276843288 212237829 281498001 981301394 332939860 884933593 709292099 936671363 155396739 672726389 369968396 138282890 891601118 119113009 336063791 975952425 393822548 781626862 476939575 157554319 943524821 351664023 355972454 723093715 277969758 284509403 755488475 153409474 8136441 341326686 513428089 58523885 98004835 593817706 691838411 267829250 875086045 549680266 330252067 279894368 956738215 471822686 558869554 773060603 294689186 473526913 632091493 325600010 570741717 825636687 936099679 631720298 952013500 167937344 832195414 709780123 155444005 224204562 971632800 370327744 960328980 885836603 721843370 650117100 628814408 506865199 972568503 310625792 753448386 790951111 882995936 23986154 137979233 442560984 22901625 56849317 140899760 853360026 135873741 402835514 277862363 852797393 546206438 726514765 682727788 48222150 717061817 192605395 940406634 876762471 771368928 535799742 7161623 764794276 908185290 208217899 698500752 521551750 690829785 408973311 322930866 194618848 578924904 929608614 628977063 928850608 555659715 832238275 360439230 75017217 537982660 68925982 194203563 374254044 671768657 667848887 536900640 462160859 494714933 164573215 964531826 158184416 951249063 835218601 763551160 323123984 338778070 974251339 709848210 767712435 488456208 147902468 37346098 128118809 807693346 984377738 821425181 84382538 151956725 992745998 187887189 788771631 506274316 432024379 121412775 173863606 152439599 106305216 973670915 70967825 531285776 610523374 87823882 117922404 26022675 437423140 532893893 336458749 703888067 164066612 23624318 43790469 281109789 173088449 308791887 952250915 9243951 155883143 764434706 935670021 834766612 339094212 14626432 66492039 460119203 791244423 881132044 458950143 698767528 683159725 200818317 786707129 288168278 560872530 655575052 360866569 665372790 363648009 981350600 880045066 931654871 591529376 549409608 713303558 97357946 275258299 741436481 77097896 981169909 496180130 564483939 427535563 866903046 41499761 264687084 275447458 425711440 170036438 190094753 72941053 504815624 678306343 452811915 746417776 274482311 541021352 24672716 953559852 996151663 391485933 232754079 952183623 852010651 949584992 606327326 166797053 32468763 659967362 918777149 424824160 599294230 336297568 267946637 784120503 595029090 726167260 100182342 592103445 359319961 584853113 379395320 698321589 777913493 425551922 166384940 682295708 73224578 989695828 42543755 642725255 646484529 890650690 184277600 783674888 379403790 92524431 550387470 54473161 729729113 171431420 88948975 929300723 102116503 318842043 419966251 889211351 587615309 87272867 96255019 561711833 616801910 377228524 948916269 856721064 233337922 980108185 228265042 515083776 746676757 834050390 772021654 37091948 760176670 648347996 344705493 499225323 150447985 266017559 293384825 516502036 539934106 44176455 98807213 820464592 694559978 299577875 340212205 809148197 392226642 41096043 974851848 291793462 465320532 30015268 158071628 322237659 250764455 98566910 242070814 273264339 254928349 294529906 113980323 641817516 589942498 373007437 150698116 599966438 854739245 228608988 471083196 959292499 633454586 808102623 580785130 286903553 562091118 307992725 490210180 618815015 193332041 997497680 56929007 14657921 816388000 513803316 402669478 888483412 421470251 722171654 127485797 137429290 787743166 208804010 142987777 789427332 118314104 949638814 611590156 855284533 420247135 256139059 749235353 837658560 509707212 386280832 60402358 549203078 58775904 343208680 546428605 163388508 797336681 945983832 117612066 197690779 986279021 117422269 185498324 357933631 616907287 590867357 382323751 347490909 262311481 768447374 878306594 625513669 835133043 115456970 941368314 671583799 803192412 119253573 921073250 877113316 86141823 685689944 342304223 797342903 357030645 897628635 50155572 181678943 493317222 233289542 113153652 350485587 395576302 918060225 87479221 454307278 431161538 329591158 825883172 306979932 713129235 859591641 519587152 355640698 140754498 761753914 14865557 599902815 102578908 692191287 569512381 18710371 577364215 763809215 240137352 939046434 394128124 258305813 549901105 406490026 327669347 230850388 656458967 862616657 87390276 301359389 309029585 578970374 300848619 6334846 767192019 1865788 431995122 43827153 199398077 109209514 767071725 445594423 124811312 267336455 17368035 823290167 496431650 317630610 485222194 593644164 416349850 931943339 692719246 602417363 705766919 578684852 326329451 876700305 245041256 772558558 639672221 623962209 698724725 231275615 699684744 627329040 788278444 835482370 354420415 593557184 161911574 972733043 983223433 440519391 972115973 41592201 339470250 21715200 154735919 596631738 295581481 794034094 302970334 477156756 491576260 182798008 225117758 265517669 686269391 16752548 20202083 902986065 152863665 853581090 544140946 162798853 99982618 501953389 125960684 276426415 390971651 221715629 338137216 608536928 5020995 2000050 353259104 147066060 828147681 974943471 584018446 581042259 704207607 603681092 966241425 449981074 486085268 97062723 969827500 853718039 936689879 496147973 712059738 751957227 424911568 31470702 747053809 947280656 231321548 322533782 358721083 275683040 764943549 492609002 870020111 216126942 480228360 85129937 185825210 388400907 219705550 222479226 262643783 853498413 257724740 982648167 340427747 118426316 645507646 605145469 643560554 864180005 226863572 267724839 908350749 530072817 921772895 863895546 35492437 877282299 353582127 85434311 813014023 681826727 653257570 136693177 9293987 204385131 768669590 976184408 793224148 789784494 553041268 195375821 999703092 333873410 822755009 994924696 406335742 709033251 611490208 576683804 649808987 163653386 679539796 16619742 820366729 475032126 658031884 871588295 381783520 105353655 64067011 445337543 765388164 297427193 693651418 334583920 835599252 173130261 946585327 885168810 795312883 421692885 238393828 523579045 789025291 570464569 376502510 823888196 813618363 445234618 164464403 92870344 576592807 769402985 280269361 632654781 267670048 117684043 31834119 362471757 65750034 560386637 69550475 185102513 375919288 29354741 805359694 249121926 396883691 336969989 973071307 830278173 912721619 783611898 507913594 521241542 833458944 807040789 711700148 700430691 393674331 542301197 246814107 455648747 953336553 55326184 77097124 553039141 662108842 911307699 726555786 33739300 749820101 657501063 446241368 689696504 767228353 419288125 879654909 357822332 904682316 248812379 603279736 287941592 528942657 155376653 645728915 394012338 425902251 388298973 624658745 598290098 244103584 361455802 926535318 574745884 765238950 558513802 917591966 827143230 148080210 595184449 721532935 538736764 591561373 715911110 311058283 111775102 697896561 683760871 924787908 500844871 608377385 193846339 743672165 416094800 626536978 787241474 240183535 124660833 205546132 957564282 21909294 133337222 930664748 842667898 751062137 770571710 779108438 822050444 392654233 545383243 246860232 555758602 369136760 535005477 565159618 504713591 777957032 175339529 371866580 646501013 978237474 12718122 146003417 281349412 885288889 609338488 598177576 885846370 698658282 235152850 4045673 524311191 204229881 825508979 88065340 146511322 562125318 475877689 371863165 38934018 779070794 966495619 66447421 880013031 532430833 619530357 36815690 961155377 546570857 778204690 552233993 114861310 960825654 406280456 371317506 625095750 509983483 63698821 616324320 481843694 843639412 559067205 659868000 266631380 54112785 313915422 188925430 398236441 800889009 956235379 621371350 808734532 796523050 537032649 420378773 204562421 715825049 123977637 309238222 732358244 963407183 442702125 240992416 478774795 172807022 9593555 826991346 251394784 181401410 511785045 123568700 222270336 455087998 20608449 587040046 807307738 502588541 307620704 985134203 639848765 580736799 459744141 960368726 289608069 200188871 764420412 728037947 598824913 302912257 561212980 108838392 733420408 709349558 352632486 730131790 443249973 603734507 864570174 933532109 806070297 987083262 43111778 850656469 58676235 86125884 990957025 123816863 144555806 674968645 808186541 250579732 614112389 327611681 259295403 544952351 979026369 637771273 173205863 861274713 940293194 114908793 118334779 814499375 610170445 539706002 269430561 786659549 203236915 425144897 771769847 941428971 254978483 912299844 976865788 720329064 842349538 24329448 554499007 669215196 834111828 54766413 364967372 560988114 825245923 109873478 568855577 447796385 883279722 491835661 591223327 654794800 516624624 221121563 59846128 709895695 50744278 955964074 493867498 764253448 593354368 131916106 470539109 490619172 979010791 971787066 771915039 639657361 188486573 946269933 618891133 470093909 956489486 672472502 965220347 403248160 620309085 809024872 800468450 644246826 812195039 791414598 10453447 41560940 917574162 395733197 370974855 679760861 969032232 297235318 862801230 919682312 664491936 988988545 372762835 932319945 320201795 858449931 740513069 146193102 682803721 247391376 981975338 785008834 797624537 358568547 535808974 754137374 623668905 879077738 585505721 821595411 691556251 425889082 42603232 332069170 323131963 32105037 947762465 214267670 638157969 901664530 321491739 346058776 570985979 378128591 970920079 162025423 897757001 394773074 787925207 872730538 493214453 177469113 876817777 113116462 718941844 951985224 108479536 66666520 302309750 985722179 319727381 113831718 870341883 897179945 792592592 886046328 369071811 278202224 109228020 130058659 958742197 869750350 456119834 717967728 75049120 280310749 90885930 560444540 605507175 189457736 919397021 873006202 819782586 337380824 404872969 39830221 253368332 282402717 100325812 549737956 667087402 311941126 219108165 443065365 435222520 996142400 306313909 50648293 149603254 960525734 376551247 106043319 569642895 657503112 659800576 63355 997773271 751228493 554712658 248552389 972762987 445214627 245018541 805696718 641853470 68320696 546379355 247310813 382469754 363814069 689696899 730364534 194192828 68106146 338516217 123438328 412527767 936382210 656061451 907182387 948699423 830300863 351357872 611766577 537379070 6866029 545982930 89170081 621773925 812163663 370669746 89752219 125213496 980471126 227180518 239634535 842960302 162349408 278544264 834212333 938656350 129645787 960808870 709315631 448775803 38633363 754975140 859793963 844199022 799750053 832636342 49106621 544861574 129401631 560725388 895956009 310129489 253923486 469854011 415488840 555115729 660395941 715430642 501424949 765837094 776059795 649115843 208028721 844617404 990883880 370086266 912454187 690428430 772061049 837680968 510590951 640871471 274004135 910096843 904491583 187735161 982810128 609574677 790207641 251511975 883555984 636793504 884224666 240083759 680516627 216941760 146565 784728045 813965494 585742616 201565843 90027353 296728846 854762569 298263300 518560856 313353289 945980322 414818694 831280424 107170452 525393961 617457885 549595067 439828171 836003954 267939261 634722283 104073539 297588465 914824357 498035049 236563762 870448813 89498105 721048155 853443607 587648585 964385138 187645147 303867126 867868298 215879935 739368899 179819791 600054567 805882453 739865230 734945894 538715377 923152725 82664698 881906353 745656923 575749433 211075568 198335740 553971566 600468679 691054825 304186296 23760654 992732558 616153333 373110226 776419795 491623253 302480207 375031696 537418167 760669457 409082931 990216039 618758905 409726473 499197562 93582055 43757982 743385827 350514232 921736288 632775028 324581110 49501603 68882767 200034492 83752466 397089509 528828329 296250312 458626078 665608624 400850172 1289594 78742712 878327741 521765362 926235649 804340964 26529406 564174334 516745416 481669049 337290955 753608529 892994100 80305518 450327894 718615395 992371510 437764621 938518252 300455683 440247004 121274465 726839255 474377115 901799334 560727177 828120223 875318752 115916598 403705486 584290434 732064958 188225701 226886950 606836 446081553 47039437 236681730 189137961 927725678 110692770 484831217 109739082 368459463 597851042 635720927 874017248 258434556 10262809 567028433 856869038 149849662 594578228 159012961 826644791 205408075 365516208 160292045 783706911 73603025 977353555 726947204 60494117 569232890 647083034 932600881 724516847 169795146 343954574 335998198 457239780 226866890 845819789 380331755 903436487 101910627 233966045 822255721 57559957 988421914 586737592 627893381 378071663 480937828 206629913 659267078 159737550 340360082 35180524 234718403 646440481 111839701 212392123 16908319 21937006 629614932 942305056 254047140 861624554 793460513 549328553 763529584 918502983 499749191 448395081 925433210 332265859 856067755 895315958 384891159 69153408 590004058 350327431 581890385 38532972 861043266 752019220 833987531 367032903 769307254 669809041 39481703 36588799 858640352 7114598 663107092 716091849 787135805 138909576 854311650 953522997 846082196 735453275 610992922 975414409 319253587 952747412 538186112 625469712 415880074 355548075 958931769 759630282 275423406 690077034 197744964 168085773 806224331 743853786 222045014 578326643 967016374 36144711 255313977 325290168 771339697 948272361 79063039 75464601 945141412 938771976 943849417 8166716 186766333 189375370 833494578 180858764 23241785 175279439 590592158 863476466 815100423 841740153 123177710 147309624 328299547 338993258 457960151 201669267 775046601 892501128 772687526 661818054 248425416 947428480 246027778 320873670 542827428 310972240 209106682 357181666 52357664 494287332 290455363 482571624 894355040 290717869 115976298 560609584 552288896 12976915 705180418 103450510 44998974 383070524 294647967 336230342 19678630 204625303 103584749 659946251 64498785 865877046 870446786 195304658 756796075 92032900 29230472 201349698 639766095 828625525 386594782 299834098 952115392 90588557 777240792 988459753 808094322 833150207 268958525 314553618 993141556 618597304 986891452 78270762 857434755 190203735 923199247 519748580 877731577 551134576 964781072 777396522 165435328 743919964 619001589 543941828 457906651 501437394 854374598 254366342 199219968 704179776 688872816 209465874 149999698 948669575 547893418 499680579 997685752 318240475 747754710 522559206 82474992 799558159 484267085 145603126 172437181 99967554 764963241 113221112 945223478 412008527 919632258 39361800 629780435 950361626 852734716 963799942 28972345 229373080 449061077 348931412 1920293 933001430 722850241 306301761 542801942 171486845 116652970 810848181 162229667 60111599 687358161 584621824 241342666 382430702 91972695 253821117 786620214 188291590 104995337 621557855 107389563 11062693 87011375 273900551 924432859 255120854 650979351 338542348 901494829 476271153 295576661 157098403 236024904 616776496 538172893 694239604 922862997 359633819 516364169 83841841 626276939 718470575 85390072 463803098 56167500 941469430 14506997 404759089 933831438 85263304 897970936 641202952 262352570 869644337 885842852 358767106 43468636 462980216 515686546 236656321 235237707 408035593 692050676 724498752 378164530 876254187 117818047 638530763 847602279 753322891 795471487 672841366 119857668 565151417 860742600 788775109 691464646 24550505 822728066 788000810 979593788 633637492 729797731 340387488 835779786 816348671 489614670 635825199 359775143 364778275 314886839 644692584 555564945 103445558 89609400 285939958 208897232 398636224 160974432 919135695 649567373 138767347 468203170 670282899 939996308 821430565 769767595 137695616 459234563 219338965 268872037 563323671 743202803 888319650 820471189 445840929 299630298 318583867 871834276 223647547 718852615 776319893 831788485 94257566 108112480 270958382 464286586 84744727 845638513 581967803 139700359 82719044 691911908 390401990 526179521 624776096 270939517 49781589 377147711 261675984 342372750 707109715 696570250 115717651 102653343 696312419 801248798 288877929 51180177 235356921 752084150 273906874 584094515 291777492 949104685 573674785 256125065 35150947 649423999 328228358 93826695 538515850 15103756 489014138 388083820 376955769 158446631 106600273 138805636 16207577 655931031 548566946 601868011 333929627 353430985 774967917 915697895 830623660 644022572 247940755 847390748 51474861 533197278 514172470 117135267 140192734 633093536 52458849 41827047 173398336 645132548 303795074 952510771 530194466 466026647 681981789 839381209 573592075 333351985 663256797 129815588 322153969 991837437 922637927 649427378 721499430 37383907 344876993 856081967 528891765 464949783 840606031 571387916 30320506 318055116 433146616 281507544 569374203 401213712 103367898 810178883 48836229 246445900 807080713 746194841 127795451 248638285 407298707 462139097 422115034 684381564 557528004 699974993 217081461 847965782 387137042 537567599 879588955 496966094 693761356 594899977 682271176 676402565 228011588 663008409 525964848 726070882 785183993 848089766 657977835 301381908 897843397 143836072 21297047 539249067 716091105 489591013 165106767 425798318 811745712 956173760 496932018 494408602 635149182 413256382 759800597 198789525 396908420 221199870 128031555 677532810 299140617 660224560 658779426 322128430 37446059 21962433 677822198 51916709 950925103 894070295 721865461 900721275 696697811 753939431 53789484 753464848 365558072 273687492 582254733 438985735 606596302 735537274 979924044 762699920 191711861 9467398 344124720 643655319 916901507 936442401 157781774 829193149 335673337 632083628 136606771 835619660 541948014 331625670 646064954 472784705 916931613 813811334 575085971 664306656 169657051 261156254 889957946 304984388 363871341 387603374 678113225 73015949 515050011 70475753 950873320 983154442 933039661 559598109 878123321 98669848 765530124 535438394 771682807 239114704 862611685 228124036 136232926 584457283 473806298 718021298 717278081 382984524 547622887 383841828 880258134 859653667 692374813 965051760 351121167 980896061 603531612 823035201 879457517 134148593 356709650 543246620 725288499 316287834 168407005 274230847 145653613 557705645 858753259 522127822 388481731 387303080 303430972 867517186 139826243 822755312 19679595 538009957 257776289 489628362 658265459 319663057 108971446 922493649 796767842 911265600 210405962 384734634 104083328 66616346 753291974 781299974 537272094 796979873 186452180 99514664 591345119 122167022 353174781 742345748 329176238 336446873 406333786 362254442 101569705 580242178 893708483 202033366 188142010 915462442 977791149 596813174 714830376 2534265 243023342 218393127 820792121 886719363 908640477 271880432 927803975 325647833 817465195 560616523 853105353 743366094 284434848 150675038 506937718 628593007 333135782 972822510 555083412 762007288 157551403 995946027 582341138 4103192 582434074 752380892 634040785 559928033 381776735 428563334 868708621 984719405 323038828 685100996 881525133 705249323 779006114 13393008 337587829 855513642 582872571 756642809 946822226 853983261 304943746 358647511 184942773 451941215 51150850 745978787 480206058 264911548 691338430 605811042 117327985 443591634 721416180 919350463 149263574 403674863 303880216 223726633 871706656 350362413 555307086 868078909 554533921 879665950 964338945 846275715 411019431 611251619 840830659 773753114 626435983 539891486 481766250 859435193 242345861 560694037 54873036 65229131 417045187 731129123 838413397 646690762 765814136 961451469 676992243 759980317 619041453 352727942 899422768 237770043 485328134 63518714 627490031 271482398 403714038 248026608 406091172 442265246 519308934 127069746 563100129 550249916 366295750 326254015 690696037 747854156 85437658 589318084 788067983 381871860 563881401 504304721 966544714 104924147 536356645 124925972 623858465 613643675 798331433 764530906 323169887 207870476 539772559 432242099 209504423 605475944 715313879 820751827 177367766 600419180 826233644 473189991 695897392 570403926 316152157 52101972 509063299 848013911 760403816 526991312 287993933 225098043 434644848 797271403 479560788 603097144 665328668 249976772 181115620 500077702 940901573 14000991 637357413 306915352 308368642 370431798 526053535 369966744 813622013 218629403 303694833 60582824 894731202 833606409 279594149 56147543 319244405 453285395 135684459 6516929 771483820 213398723 221748363 639614891 375394950 621075691 688437069 130367333 798112666 443675416 724345399 229723901 612742373 350704082 396152345 687775506 327941069 355801269 597220327 671947334 81014482 268135816 74498755 937700941 533615372 711413642 8363839 984786050 735988964 53647213 890952277 703492189 21657291 231671141 490043897 162180367 663007245 660689327 127127861 567145108 961439626 320119918 607147045 924988356 940631249 238403117 647133103 956835532 435338650 608792315 433494870 628803443 906923651 263252736 508827946 541397368 68380064 255991494 975447751 220443759 304836513 212215166 907819436 692058222 861355633 264528455 169233298 333473365 272190249 75527282 465101158 401585897 763875864 117168353 476769564 971814986 247033406 472314130 668316024 963555589 646587389 412269267 423802064 410366324 694189067 613387831 856018039 182585384 227371629 259928194 418374339 503226980 910762332 155886656 96435334 521153813 521359200 204333878 643083104 841506277 805250592 244676267 596880734 887276494 720735147 320222067 319600532 216837567 208310234 795950219 526436427 587933178 750513666 786673429 545781253 178185696 344607261 562710055 710380125 792049156 700886454 405033579 188100388 252548053 555874075 567717267 228092172 449928468 136357830 79255683 503555700 136210657 184077134 826228176 501223086 365493486 192374163 335320248 846079282 63548376 558559629 278491437 339842535 51260054 41899352 670164688 502423030 492963122 301791709 890118123 500728668 866329210 782730657 871794494 411247505 67725275 898324029 53754453 338496903 141108792 268747137 647450587 55088683 279178450 385572841 239929214 414300005 44219016 645162750 867573941 11723748 280518766 246472858 673257649 260790566 743730343 821779333 883348746 730368225 941485098 766657459 699175626 621761882 99171228 813596197 244667861 165372403 603904740 475728367 695850530 773106225 808979443 79956820 418000575 607953344 82373727 986523239 537925913 116729766 452130155 687280353 942387324 391320398 780163616 599151004 598903455 618811128 743797273 347958678 711522846 916973671 665680570 975874069 361473402 663171790 716905342 565235022 293811947 162946427 852284611 934888799 316260618 833525600 229532599 443877964 205070205 302585209 704769834 735450514 619272416 546801691 312059025 463440618 197100508 17976532 542147488 514867776 400800989 662324810 2305511 486169008 425714437 642989598 575161264 618053290 16096409 530504808 226563543 188789730 989351269 689165441 836772826 844755977 400733182 357016418 825502768 659890601 754459963 559658523 342590050 888494682 646482759 308491214 942113115 539960008 975164217 145100866 659979528 835019854 605497152 162152823 465150021 239021310 612573653 839608790 399042181 932533971 681270578 762844912 123821954 579493075 129217650 558935323 375251289 628505251 36238050 351106830 907999370 632198915 879934723 234267128 956085194 609093051 493225808 775002371 681953023 503057294 991962872 700357838 898287933 970174755 893085202 549333205 647547464 167806737 406587500 879856356 368128522 458261256 752447020 332425997 258144753 92253186 750826571 775366995 120573991 32710031 628836757 850667595 752532048 698144774 957917212 926293620 286011856 798663192 580816207 98687348 671948415 540492219 406931737 936933734 456608018 57207990 370576178 415356147 533242881 10685751 452572437 945754391 737147169 951823324 704872292 69398327 9751444 333472581 720529725 820661234 53333086 691866507 991000874 793803302 333077365 414963910 513675331 450525756 567319851 99567599 810683013 442539798 869938633 936049116 367933490 477442695 699126229 106382204 98858821 448952838 111861079 255559608 845100266 92344694 267957709 236074575 100091002 680690318 705225664 665527252 25900182 332642053 434153587 632699966 165181124 848560115 651062738 193767676 422176677 919147786 759348089 843866793 964240516 33329353 555734198 751413049 2498298 400623974 212008588 21954663 597698093 133494744 909037382 605575291 435036788 763026999 949443299 76886964 258591063 873668010 96084622 757473641 68520662 639553919 417362481 105274391 577423998 163438310 612198541 653353966 823566431 808348072 337243676 498536128 3280260 30934614 603479917 751578674 569947601 972301017 142157393 470258151 562841688 351511764 457482077 747908220 694244806 334733981 983246126 217363788 55709808 782658319 372546782 145396532 857972998 241204322 316217200 96923462 289417217 33242389 68308116 915100171 803537962 147543631 282721747 391975588 445293627 286096948 149580244 691900421 72669311 558284815 961400889 493264351 364177700 564351972 340355121 378943021 280464333 688274973 158795025 865569747 283646622 610764355 231436053 681479904 5197380 254641980 833465428 946922379 366684538 573429235 926326422 462513525 575833695 94656854 348387461 513357390 667397487 5928717 655542521 96313756 211612590 275458621 9757580 191442884 490921018 532538524 173579447 31929930 833765008 723053776 747575759 203583737 571174591 700737742 982265390 750978861 749799068 22628038 870918485 992426718 925694878 69253841 322755548 272418048 474808602 211051760 645845834 205123105 661069720 346650713 154975590 153333253 197951301 384030631 695712806 56895258 196713726 744707576 926176808 28450320 928533880 615153241 104466203 590406925 293851953 751645319 499043088 334303789 775382073 772760754 297664324 427139890 631218818 971620681 406815419 703011338 462732800 318503528 32049682 799599575 619465074 387139711 676190031 152015520 759826704 835138785 507586976 10163349 614359832 292443048 543124829 97922851 222112594 388789526 658947029 161350837 602636367 772107965 970402154 94639085 887511530 703147983 49144658 403403220 147817143 870612497 548793281 991569503 374374900 492315758 493780832 293512914 684788327 818975218 840998668 794059011 759164357 667385589 891739030 613192800 707632828 823398883 582813482 294716869 551169934 491731729 296225401 389909899 337067113 877807057 132358144 249112015 370280233 533912350 549769083 337953437 595714688 641761701 224148179 927450572 23433347 463833007 739666196 57611914 153016 959065164 858908578 248238039 904829663 554204431 342930643 25154633 231105982 238236218 97248687 677479191 177398203 618043125 307371991 508469235 153739897 811411230 612001983 804880964 508716655 477094920 629507472 82163182 696563996 253336367 643778523 608156909 315296928 149377497 284628070 996504265 987941342 790397250 11344205 874645454 897356277 395957339 294017264 467430650 405415238 615145088 880832874 463301507 656828746 11424636 447908720 803637188 422180087 837055536 140336514 520478866 726347649 761455675 515619827 853458769 794832343 824680349 256755586 430558072 725547337 156713237 149112783 623276732 119656930 512235588 77626020 230015125 139378764 251305255 447234632 71388383 839163276 585540366 767112072 796125168 185309160 671226392 835689807 144562511 293948538 262618020 215642627 170610038 59243432 962254708 935031834 838037277 139519666 93131805 646720733 178272046 143948035 966011658 982466206 890835997 551908390 76884041 933169472 514106705 741025636 66442626 567765672 469690122 627799310 129916798 434181752 820138644 457116546 91649590 315124717 825739685 225419128 449130956 256154194 469610879 960072082 8186783 691179553 183923707 399556048 999270927 361492408 976854203 69291510 683399072 913913399 586856396 138676391 777821730 837174673 784878154 964332215 779764518 300384196 166803541 249607230 688873708 573738301 233716063 306264677 279629881 389232553 962254092 712583481 620405167 225792787 369041047 561117179 539991930 99840165 635946719 369392625 641609052 842972783 783876483 416807400 566800149 309342328 174073155 318988323 451981894 387750215 464463243 794363629 816735975 832026281 591077117 288643063 922433225 558504646 534554403 746581555 817853136 773116685 643292595 679529107 990793197 399389939 707927768 458932828 800192798 378577554 157364846 159782300 71071024 625185267 836315525 492028195 393966810 929677402 215184679 279667137 630926041 942976137 532134857 231939282 190562671 699636470 980544860 167762819 773910568 259332778 347454840 211439962 583015037 611423392 329715668 529456926 665489255 532678855 887826530 817287392 301642915 778205656 140176120 706506323 81131010 884192400 130470916 440436346 293000590 898389936 114526617 46812342 318841913 763491729 596350675 911645047 901388556 186159459 575086971 931254788 992315510 867488842 570579946 222898577 893911090 930784624 541723555 79902703 464118090 152774207 702076564 906978776 430898567 129851166 525837387 903028028 394515273 329363470 823668623 706027837 228216217 168344419 299538915 976825246 316984389 465141373 188236396 834676184 662743958 646310608 351823762 425668659 78390363 594507702 839825542 823195030 230153940 280538861 952310879 371563950 488089426 50077375 923737422 590614005 564796272 759471778 137985270 834940883 544003060 932120641 484905233 433220014 925061097 152445747 220622944 130873156 556912042 825415155 564251664 232353702 981381284 468271665 587959064 136505387 638851550 50337827 193450737 397818673 640773148 38127544 289280203 133305508 503249746 466144552 274970401 722571937 834591354 309710994 703966238 634535307 52353345 147114612 897267893 955249982 720359610 320280545 616271900 717987292 168332916 763439304 374519775 442713816 106355228 554001483 330485402 502238343 538345454 286255435 219737236 709483170 327432544 630684793 372861175 355707719 458824253 755802683 467316656 189081373 464636435 599391731 584820597 126987542 620631384 951875441 714979929 706804469 549578223 946552050 644762344 843504816 88842012 926729391 448990359 517363616 108203520 896706284 906945960 673084639 978731338 418401702 617920093 32597389 528212930 594271319 260395550 553065279 167265668 336252692 232428909 641810435 46327510 756427459 197577468 131492874 480339810 102546060 529538694 75880794 994076382 989468960 344098865 318964323 385164909 862077034 359972162 769655247 158427459 554734580 120551393 515043000 774643780 563347031 123073427 65751603 60463430 43933536 134812997 689081965 512223020 259415590 589196012 957876233 829494325 59720647 299928199 26797041 751710882 990399548 808741267 606241267 929947973 42207532 463012164 661852848 912944894 38889014 490619868 542149039 385727676 290633870 816988310 476800397 538485399 659794048 726050670 685293515 462576937 79478301 441867662 247887246 45284372 42846662 600600625 222094990 364922947 708558914 390628953 324445385 405068126 501877706 699539194 820646485 345007689 178759187 904101159 71570421 814826600 192139462 985777258 518483884 35845699 637082685 952414074 287276606 715505973 43710100 653018575 860901261 793151500 807024528 350649490 551400815 496856985 78373074 760445140 421005687 508431209 981313439 647206838 215910504 123735532 504570222 17336456 397356845 601355186 832495238 723118507 352600155 386917226 623215367 580814134 866968140 482140002 415204890 785861622 990899343 50045867 524418044 493183608 942445855 908733771 304761705 689161277 647714958 708921238 575077558 3652768 337646076 196657763 549238361 122068002 920230519 431147407 206981817 253108648 753013295 326921360 284969839 556974939 267561593 264851088 113885481 161150486 272897842 153337632 59369052 722439526 168770083 226117734 605875929 155250374 943645614 256957111 1204460 449954474 217497293 891616608 776950818 757969041 752180701 500976534 973332140 145030952 736031558 541773219 224708421 996628700 595990546 339273936 956567957 600220485 329379210 403708795 135867436 938443561 310554739 108204395 574543322 66353484 354398438 277577319 919841049 334796172 484398577 896970425 563664105 4177510 336587733 498098460 184099626 298923813 631998386 568585930 688998017 700421805 664388711 574867664 416482806 856621919 239667206 420736856 829203853 653125598 594881493 182964687 544096838 737749801 92310583 408824925 422300150 769008892 16736883 248112440 455701802 776084562 183821560 110051404 635091073 365163168 759462077 424152713 715840608 670760099 111309131 332922303 754534600 382455211 396439189 950232140 437926894 502453116 653432210 904104000 649968461 135221356 938125069 905994996 759683050 757068182 839506611 74988735 485322433 665361236 209976656 841887215 171256204 744342829 709798881 352750063 166772822 691795034 333737377 90125369 108712313 992347882 58001818 986191595 113423726 19689749 207984317 490945191 66453303 459918320 658247674 723118154 676284507 408965771 604633345 787202798 650211916 280516988 289134326 103533176 781109122 809101252 749170404 247046120 748600998 915905680 270056003 907718168 969114085 294550161 68121271 945341306 107580988 107185822 125098727 289211391 998879757 590263908 429340806 322443075 600953106 861551418 637212416 715310545 423748679 435174420 765443932 292212564 793874694 677960954 137420998 355674957 296963762 180143737 683932812 469007153 787200784 482477644 533463745 562509739 682740764 561085649 936973115 37622491 981604737 605334913 601928097 796468125 971923838 25064105 752645925 858954952 837654151 683499996 409871462 770401944 50591575 520144872 904029880 255307877 355052834 106405028 253375987 367538025 784783295 117321310 801533874 673160799 593095670 119013044 171860718 990748455 939549963 634177859 798482872 374011289 103602398 909932863 857971223 598667604 840734853 480721010 208557871 642603978 256390376 905795626 245867409 298362174