10000
113479673 902957401 66231593 185323982 89805621 669032387 230620749 700196343 400881010 455559357 393678080 118050055 748200335 214496059 469897133 237053072 411515547 23955308 365197277 257020713 243525212 685582210 137989002 863379952 233611781 141395096 55854595 693519825 397228218 967309676 820494297 510707891 870267076 739242244 548548228 960072697 408274631 779168977 512785393 661671995 87244687 906463474 632238404 687961377 120959532 102135536 925014449 384991434 978607199 142728080 494528501 74648764 828310290 632517503 938028717 61922071 626428954 846399666 607958250 23657171 813709341 428452546 386881417 536492770 20211143 935429645 349081820 428485774 567114975 861867214 90157769 506876016 620847041 574912527 194837392 594322927 529564418 119851841 831830715 508171616 115096275 326359216 582820381 943406565 958876719 373365451 857844990 437822026 72281470 465803239 313995552 885990812 746772139 700876969 274999935 766983283 488822967 476598110 47985410 908454296 190981677 138143179 415330311 811828718 565572061 462684058 258667998 95136478 435052253 90498713 455824448 550148528 269374283 38644828 493555092 80767355 264526633 203916436 518589382 336808104 669719675 832584934 75315269 269008168 385978256 202831558 35991450 727317577 679429668 83976860 635771872 870411345 74636394 903618537 534756416 640208455 366302594 793424415 587861287 801354847 736439482 43685734 204019728 858330119 934846918 697574821 939097474 51889904 901491257 310203209 388698008 423727285 995304497 316529631 692735453 233799106 519361190 581243257 961116683 198790857 665220118 449404908 69202202 592372866 353023445 456474972 85097674 571842393 102415740 672958961 225713594 838855222 716644695 429733322 549701694 504007966 127308142 341315522 555897871 881315753 651518731 944595879 157559392 499339582 113641864 702811199 733138688 633003054 284054456 694255371 831793911 801790928 143660278 753512467 394163793 349200077 62503793 479261467 921042471 164919533 4736781 146756064 3774755 721381476 429005740 405992803 77905796 408830237 747308325 633803667 142662343 251343410 430915899 300221735 750682992 544557763 3032934 483821679 177560816 139603744 30593403 861871082 941394672 26770036 467899902 188074818 228486467 530403695 519852639 2045291 695323229 524589420 1317709 551614338 98487249 430323450 957607141 176393045 839153687 704915466 810196712 981816030 956258876 241112611 134554119 559458221 785670374 137587053 43279899 815747545 129707151 926389658 677618626 923618177 953159694 145518527 111692994 34162514 528438577 484061987 36207806 223761805 8651406 37525515 775376143 107138655 467848965 585499637 283531701 307002651 142931456 93728412 141335035 99190331 187357377 275889154 511164906 825544106 265992561 406961160 641291650 395699712 333350817 171426629 171834242 139026864 169461510 136043590 173189378 697900087 620105577 209397184 774178246 628756983 246922700 402070742 588411992 714771665 987570380 871943693 874290671 130501835 818188460 15625705 82208521 858062191 291514859 593373427 683606296 557507420 334586 177414299 805723486 186201757 201357282 977557728 177744975 370818793 113601317 350934354 921235234 733706894 412847892 695413480 214980230 659770592 97484221 803392222 227058611 937570955 527852269 101349281 68072790 198557082 969491341 2797665 56619272 113522553 448687446 592741923 671029973 301538387 622672576 329269812 487740144 824029859 306827539 665485120 47365005 272945210 868935828 968600239 6652103 281783719 516530072 74148687 794070666 466530648 730057263 21129276 404101602 110425885 974994912 324690746 308982967 797002606 180004765 218118594 910525159 628692212 663376871 434071485 930230599 286049446 763341297 270487096 110079304 70168835 935972216 9960663 195630399 657424397 978560903 54798856 939208117 495090974 128947543 585795136 961621622 859004806 459440766 218239578 969430692 286952031 395446678 130930012 83954636 575451444 201564960 994479795 204143655 864941831 281067633 134374253 3507631 44408929 257377703 113586935 967094119 45866273 123547599 162724517 703290670 954624856 217523373 495015140 302232183 198987270 80810275 116370159 57992075 540251041 334609737 879939121 827203072 730056415 863385488 763674062 158024212 64950447 610670210 362167867 929892279 891737843 349058474 933399910 936146772 606436178 899503199 755757244 652302451 875567152 918481761 208109474 682708361 988521488 703124615 984940545 187508757 783934890 101310703 98017187 176702285 288436794 830472662 856421711 18493208 693858149 620095773 29033775 611324951 83282336 391201642 393733583 975020180 592776471 179649846 763683305 51729002 79153044 519440549 704031453 807236551 290438663 912140927 342461265 131476505 467781895 327401809 318985262 104233139 281228866 269518803 280935424 569665660 99991465 137357134 440675223 646365968 609969261 469708998 257690918 693251598 860910640 651424501 520788131 306203464 831074347 284471435 357932466 762743746 656428338 61963918 422496650 946867002 826621200 764957915 78343506 146919448 944876079 249845122 251152587 226104944 519363926 532088011 795770605 471871745 521961500 88962181 118237712 984447115 558671179 228444985 530215066 272098172 879869486 51003196 578301637 563460187 187990986 936234103 178720286 844419324 850714376 453733290 643802679 529851929 71207558 574662539 676771377 16083636 824507662 927923965 94704935 196387941 312528329 890475540 668259686 834489829 979437721 639013752 671453298 390625253 867458737 201668363 662723425 599844577 105187914 241025061 15821117 293178900 29775518 194541403 137598223 880489894 648274693 781400903 410341822 719482251 208579795 87113198 588082242 33087456 867553517 682787177 81991751 180081846 425779070 602767791 867088029 257733144 241781543 538541326 648358397 109240279 592726044 311081821 561601210 697913958 404623237 577422327 991092858 434398755 771963730 128691080 314888648 272754776 762608337 577746824 844753382 971188133 517376376 432835623 856791943 384929893 115622799 791300049 417528093 393918223 394067839 284616121 651651367 488365736 675673802 300009763 450122370 268399845 463607938 11723579 966313803 868231175 589145907 809923014 302629929 213625990 791130448 470034931 338897121 406255139 47781754 183650502 229959625 565158131 469002479 86751567 802604378 437141632 730567970 220132470 831059855 124635809 357264945 482711221 465517899 32938746 635237338 915640269 153854945 98845275 927363849 120168747 967076451 369026109 782608115 122222733 435168453 573738563 592257665 774065574 979993702 492555773 957716076 62469680 57713903 279234908 1737601 712834635 716376540 732305572 932967105 547436394 709457735 142748404 882663969 174975633 175687150 517901306 90615902 329542096 469262936 870496105 302227197 288855740 92038567 84835312 411078473 527207020 511090229 855852492 153788948 343600284 348408265 111505023 406069964 258638522 243256286 407807565 971473158 959632826 140113136 756956616 359585574 702087225 899705020 242249542 877062859 927908525 612667203 820195115 109966974 81930138 543207573 412194171 370785878 487762494 349545837 634380705 14969513 713152420 490233197 21274815 56752703 691157816 132779839 315339021 949796338 228552479 575662941 773785849 188185304 568292431 383258819 547770878 270379656 135480192 642536775 999958869 63388716 255203977 672670337 25872044 189650469 68394263 438066216 560436347 556156757 640128407 47333405 423642624 353280827 537566602 444917440 262549884 81240771 430213633 430405260 31037109 658766112 6068200 657339312 846951416 574360631 893114485 247238648 697256641 28594677 889775423 697215509 944499748 997495754 222402199 970371793 187146222 290796462 260954362 600098923 846953219 901082769 647432328 270595843 106879949 37515284 715513283 221946188 118756055 145726915 652351448 2309518 657009381 658419648 659648831 356477150 85296632 405279669 603715798 782553274 286390700 346007574 332285136 83406802 196019681 554687336 53778594 383165903 845483798 167249310 983264826 544953371 920848433 483213508 815549214 27728382 520728792 383578850 102190924 639484847 381822119 754542372 641794366 38831499 265478373 153959550 247825003 350775005 559239219 851540802 985844633 845629920 50064729 170646123 929036722 246084411 725333459 835331670 481766668 423333610 2580979 317547848 968286981 775945766 800761356 636352548 656190502 321490147 872447752 758381426 960974994 106786224 512923797 455285713 145617723 778402170 609245263 245959081 981693530 168484482 97499882 967538162 14114401 80965 138184284 795667477 98681730 716034097 630999146 580448399 991884062 486096479 897996247 812687396 114558598 698757602 301556298 770749101 872764103 174004049 529130526 686255450 280790274 894570678 141541163 278924351 525489201 750786426 524883432 507182730 771787262 474899668 327237246 638418017 327496988 317937884 434085493 426178718 886488336 917600993 6627116 878372397 256213825 904623363 543576146 370772424 455897318 845132444 141521524 181177774 19136493 523168404 867433225 152443121 417739081 8974387 283883826 943228283 612277167 808767259 302927366 236580783 136183280 482680966 874998800 463680268 800618851 161600647 889858987 539623540 79201639 749002457 270512290 335415465 506142174 814088436 706187889 962039492 659220880 700225767 143217266 530873727 223394170 863166845 535833202 493649606 724657586 819717028 289394242 189451106 481000640 592321608 426031889 617183921 75002574 301030689 933380543 728137779 462631336 675755883 120277672 394349329 424758340 390789962 729764794 930900514 204878397 288469036 745456359 716615631 988694803 741189979 100005711 64605327 456873177 635838913 558254933 181530762 455555941 847649175 370981869 936556581 292487136 797013758 406256855 220006064 950560801 192153752 800660197 265708490 867909635 920937869 660057820 145184328 311727830 242338967 76084841 369122582 530808004 674057555 85738212 372019160 267763887 185743924 289140841 724637065 821582837 847395774 758684181 129655131 547561302 129666049 918728067 692564793 779196162 177501275 912570857 582273316 369655027 565747408 847981807 237564662 486685276 508039626 382748990 650929461 750378593 311350186 20052042 133702950 837924095 105790254 358238465 105687981 144050532 647379306 682841400 818149724 347291434 294041935 947804855 894852736 276224338 719049275 439933882 55420499 896550551 205021093 490210170 266205577 770768501 338191976 356286593 109970130 698747956 739035584 760899591 301642902 902902124 780951633 435345853 740826218 739258242 793584318 699030553 735825128 293479977 234388307 553974851 640771411 528430242 354296060 388140501 804654580 73345334 828074383 712591434 822412239 33095475 55317957 88617816 803863976 393509933 297420763 913834107 92257888 36456346 527250051 246417144 791874824 160718038 681762997 385217395 899976280 327863668 84247948 488317761 621343646 171152609 42292612 114631410 552099205 249105026 502771911 209270138 174966714 330846294 921861572 997378954 216458123 977179529 938513124 20322099 223205815 88450240 786672560 167980057 124906587 166438964 414397202 769297765 327157002 948676553 154515160 79649635 129056575 91279462 567967397 750400221 114948425 462776363 865031631 667047630 711881389 220319896 876317768 739364457 551166190 650695694 589259764 767624313 480391576 380289241 640462766 703597392 468739482 279651679 724093803 446162423 446090644 138491004 215460187 773247646 939683912 222491701 852897282 68740486 313771163 273381032 671657061 428719588 736157395 389205045 95767217 300555137 609524941 824601340 39919593 13207484 475297033 629179358 780831798 955688609 9468598 273810917 511802354 330724434 405978951 88412511 776886857 852069595 79419869 992347045 477833594 19103780 67355099 183247229 87844266 381126263 456628261 612017681 662362205 45302009 1222726 610645777 345857146 610747667 435247116 385776740 623955152 763060503 867472452 257303303 571265465 729457404 383630574 83067819 60181838 789609525 23996684 837068695 494195473 103416553 681932093 972029068 122520334 749287193 7792650 62880954 982929810 316937266 674898636 645292014 362239275 528637716 108454144 708096422 139385382 543701260 93873161 615856888 159278116 813861967 725676545 730543582 543319370 109307119 666127755 456017562 898916644 690124439 145602611 245628471 793540992 827534704 70173892 916061326 429338250 77966542 831458635 264784413 394903808 358873624 910076428 757143084 887511340 18530571 317755859 879413076 414748186 264145374 347786318 574026302 78007340 73462862 157086237 473843064 35286335 823213992 929860627 934202980 513338430 75463237 32347804 159395776 755514295 102521696 75457101 37368899 180488238 759432090 302153312 427908401 118305713 64746093 37567838 5817052 83276665 355323697 737746483 350541205 619469071 85532800 777083861 697476411 11512016 934170099 23835828 46798352 757384090 953696455 981001332 123238874 29159691 13349135 282634650 637190341 115870831 210608105 674559240 148875423 970040196 976712552 576783824 940862263 41458645 614351662 799195670 977251665 969675359 536942152 180309223 441660783 474991306 957393084 139137193 486503322 891563182 15489376 533301674 501463626 969185831 366819359 477218854 850861877 232684848 759853504 488052217 201072033 822977963 15127810 349947457 645534512 991840362 779247635 586396775 33299006 246115651 238108798 863067025 68307363 775050950 43376247 509968147 102558609 769331 501621694 589061931 744848867 517111070 122363605 98828846 486296901 489182964 576047700 189675131 721867813 188417557 677727348 922939846 11395520 692855158 125403656 509446386 537211873 904651292 95843160 423027234 3283296 186468312 286094258 71590659 961519262 181986860 581558806 64077870 35272545 83180500 505656156 780121412 600291570 628019761 731466613 939104825 969719079 160030666 128779955 544103245 348448224 659023657 319559445 212360098 204395168 444963101 721806484 741607042 202130746 670165999 164634275 205414042 856634311 303244887 277004702 670669927 485231747 858563508 587264151 520504292 794260362 92920306 153142058 247068286 573456421 884608671 186173110 395691854 44639336 167469420 939795099 245603914 826493077 259354543 457964012 30888245 556833999 32286850 772495287 758964745 554969203 789645916 816895142 264119867 92890802 93899843 934789794 578122550 804979705 374570299 98626841 451756421 320006959 104285253 698824707 745979735 988893924 884997817 141671588 33533260 52467236 81466686 131653528 731476668 193337584 589617541 762364913 750171583 474420745 387376553 361652681 29389947 29538822 31064176 293509814 122429624 124964019 80815962 553068528 782460079 307902615 504211724 86732853 627909574 608496977 785557560 226405662 597390901 523071730 368077250 483440515 428055321 302060291 615094043 159531988 347914229 57227937 774413255 98085811 531648682 14306161 312254846 413554983 43844983 343319023 707064798 166274607 320799396 640397114 719343136 955775829 948299729 76071213 42508681 428725656 684568190 828066241 655131319 134475444 203654325 23208568 617915959 631709646 177785213 85526356 791241634 525699442 142754293 418171242 476301607 526919330 432477403 641072808 940474313 476322386 984391831 500055464 642596993 157707580 140452577 214456482 113483409 941268660 290527695 8508444 369994316 975095886 689091040 25125634 109571329 892745365 900850557 580003643 524455010 931152125 518046353 168212997 309367920 513317000 586384239 785669528 40236329 18861641 279258689 833226997 347700381 116166873 185798814 990297374 273874453 178767746 57270210 239874216 120036405 200314259 100899015 342547075 27926498 789990055 220189063 137497828 682735419 973555975 570017825 59706782 904708099 88064177 80436133 66592372 453897531 666820372 852261900 346650215 538198367 131520588 32393565 885898748 100203815 218192379 728712475 374078269 249476479 638499039 466468839 222029239 838813299 567367854 564576314 866739797 357357908 637281732 856753979 892609681 610837706 279288157 952316463 368062158 219868688 32752595 434654530 673766220 552089321 139432784 20416434 942804042 123469726 52809999 681219143 223673542 123518732 262447972 450268165 372995212 900947011 916737004 595024451 739760309 484104858 12117118 459016460 693979120 649398850 315770438 586588801 112752909 595058596 391421617 480815067 814927284 276690567 767985952 341209857 681296242 907418736 361626291 624100284 883404816 266952644 157835780 107078357 390471377 420283752 409862876 763466589 321230763 326599880 358491039 913507426 663221092 370608157 372523885 357200211 20007007 540810678 796305366 132759916 135869273 40243337 466091338 803312911 316933904 86593643 144522768 998230146 994012379 358665413 474846783 729933548 625618058 632682564 689528260 16089434 52966315 99391135 632072377 226713432 278507369 990563416 140220858 941728461 213687926 365261097 151445026 86211287 906071775 947750392 71487558 894457402 987993729 390095250 550286667 157443986 476688893 547325789 8190486 323217625 758507556 483037269 53151172 236641967 968236187 742679432 105247755 873718857 694586922 737320132 100432288 973094291 580399901 93169500 914822752 794087828 310946952 66267777 732815469 69535080 866534523 804303027 816508837 854528252 46914630 219311857 11972237 523603523 766637646 20162723 846821148 377661555 355716347 899972321 614303523 176468887 495168106 719551278 50187743 42271381 456871410 3136386 15365672 37271310 948822241 782704778 683875492 112285546 701488909 269207315 181820627 568023431 73510341 998329464 275068036 120424972 70157674 139556628 496544849 836795320 12235705 343365997 66973228 220468406 95854671 681276751 396937294 443539131 400828029 447125037 485810513 710215793 302777777 501176185 600003457 251600018 136397316 136395303 363885564 837886225 405602618 398222545 258426009 331629313 249068362 533494046 304570639 319226036 525567028 801115489 8537709 537802733 144481485 75510938 758271140 92852510 756787689 7724787 536391641 10132071 454849824 22202153 720347864 757627602 375894692 320351321 861743974 512292008 456746624 78145891 202694586 862349242 476368437 461120596 46494908 725436799 994614642 351065548 44662835 372698023 152181036 53200544 910500756 149178875 128711482 521288249 94547739 885499172 529013036 630939380 895631243 836379215 505657888 468495461 446523170 734068934 788846782 308267143 98877296 98109759 386413034 301571882 812975355 862781471 762692478 859470263 440734624 609823473 210535810 485397459 982521496 215233200 391114357 745538606 364412075 519825840 119343208 458959814 257841365 648356245 942415549 5988961 337251813 300589790 474484422 783774983 34658723 115847557 92042125 133536019 66473670 330971513 435107902 879449025 46269338 50316733 738919288 487003962 660140207 801971452 824917775 642661702 17204652 216032131 240716661 234133081 588374325 360059870 693092896 846215690 8416114 488024798 704721006 198184281 788614588 31721781 981959264 823273311 147569339 926517743 809325685 214043009 110005609 96949940 93492034 156274947 147266673 684927676 495795263 807406880 339415481 320713037 302584936 356620133 389261523 543301597 590753215 977635848 903361467 136362464 676367892 764293935 624387262 381088897 962478216 265518203 412810678 944437479 88791513 412896371 723471575 750633552 626939381 833477185 847583492 572947769 989752132 994850166 110391798 338063749 802257045 449807279 658776786 104841980 658943767 48038308 500659932 102213335 878190511 404021398 238575799 554558402 20831687 715479415 788163653 983309903 980997618 53490684 780263736 922305485 466387056 503735310 672939037 93326436 189728848 373038882 518790559 31997334 367889047 481698711 370061083 22662446 931505990 28837868 980020781 442966110 929392532 480680712 545179445 660099396 737218465 783755244 67174151 758050152 351751012 855337804 741360054 332748629 908828488 374140143 107570468 375215543 877875454 780509505 321058333 67604301 6064740 692365246 99601635 373953788 174063956 322179072 249132588 958086301 203533295 229153368 401052410 132925826 562350435 946231856 645541576 299568899 582503453 712715727 57619050 934254466 568053530 651495458 119519448 329398371 25635601 227089916 704613915 756027409 860115775 878188602 676148064 866180516 570553848 628266054 92650657 597134158 950445126 341783245 555220458 6494774 570936613 808789223 139420600 133287047 607537432 637478530 285372300 42557238 350194256 195507704 976811704 770764140 699519517 948847507 100162511 577671472 28453776 657292780 186215234 888569552 535481381 862363298 754750067 958551583 343145705 847400724 555685741 146107185 41700322 963422553 152601959 612636935 772211775 144538914 598440337 232265560 782017444 736328991 274822799 984728055 931836696 104150856 755492194 483872566 52998362 708171059 61544037 81452139 365463838 247759271 970021691 753461574 962638923 577288111 712013156 158300982 277205188 120215250 304408167 318905510 83637803 309526480 784058799 708365932 454065394 235015489 940631493 88599192 971344481 67970645 73327246 755697530 172121501 681335794 239570095 225119864 242023207 153630486 159088357 607487045 401389757 129110047 213464972 216545033 558914512 925478129 374846015 688636054 898209733 679254182 7541563 834363890 988780663 644116716 395246176 295362410 879132206 188394022 236477956 850476686 256364667 162321556 458690569 428486168 843657351 698260664 653606032 85680557 851891150 812694389 545683956 105797260 794320790 759148929 322342293 205751655 537143411 697188309 894387709 287869497 228958844 754445626 122233387 70255860 251078696 517479563 218134625 130210901 705873585 454612581 833203941 962238252 616934138 291894509 243240773 313107842 842671527 896846806 251304753 547079030 562057548 796988709 652876290 208894692 408653991 827734937 267162701 798313756 377439599 14066764 86183253 606398444 768512390 60932994 529170658 19591085 578412557 747305283 2318340 136802495 201917864 835522281 951557101 818852002 979933144 194797873 131959843 822604670 944161033 235780950 222200053 358734935 32769658 875076343 567629627 293940004 555327634 834792328 92253759 932767233 848859092 30953366 391682030 469887836 91886360 920852689 341995275 522815271 668157971 196829970 659617766 722592189 32352250 463691220 393960544 864801749 658489094 378436741 539922772 455166480 614217691 762122826 813901415 499503704 489715522 234047395 793443708 45043155 68839723 738213821 977810389 770215169 621683542 222008772 92619358 713569902 142861460 287130988 88901527 663535786 483960958 748519293 386127974 368829562 64726867 780088519 233631310 723215961 11041613 773554083 30898794 625259305 388193262 844800210 124763008 877908784 78847604 770723070 922951940 203681 361453244 753278682 622935205 983136786 975287454 715554563 549223042 970665269 2685550 638124569 634201054 339162862 239160215 872845382 707992425 303887082 505450254 941623735 27103042 516491868 567694171 58001837 141751172 955887433 755318401 119030534 686312571 834166005 889753604 461780864 686886041 251206847 67575899 309821245 86859987 42863352 877892162 636083029 866044975 733094067 274207597 352762382 72256928 513367812 225607764 780249353 817254895 731058018 574389442 696874291 100066239 994599967 607392482 241817411 803003754 215227236 360847945 489316324 49393241 103117902 951097188 588795636 354324750 18673086 898616881 441184737 914052793 629025396 77267765 632614122 362119462 203991716 985376504 286892745 569875882 63500621 67142097 239647130 794558640 494047893 936521422 894624879 341164214 396430257 988958645 144167967 611657494 202322943 486000645 513567089 305440846 289614186 102362724 659765596 160803626 853495959 953466687 74856418 335037708 883250806 559986894 697157171 87242521 545363398 984049916 509634757 608864019 903708367 749281888 255939012 250272614 538319663 3080245 591436828 934749920 992038890 588121149 398923767 46878186 74121793 765007210 352319032 363735979 719886288 12084627 524539605 425898600 818067668 451912377 760936309 701318473 11899271 310609833 641077348 409779023 147176102 3228459 871159396 50884468 752510347 127098408 153673436 290830009 982695008 597626618 78096282 827250251 185747766 329536404 874128437 112385913 94543613 226447469 476121892 814429902 91048450 853177851 92844855 909116119 157606582 853781164 462950945 22022207 164390996 956544648 431801230 311567098 959773107 155476979 214967921 712283453 135091741 221157711 855629816 117786748 818784330 933726098 945036999 4532095 115778855 671681790 116918009 210322469 898129259 445556255 877268725 841694063 151250460 970113580 603326535 308857042 823894744 66277480 330879249 840802094 875338482 762680479 4885546 835111588 918157458 219853467 399911394 53249199 441011178 108057563 23552301 112311861 41783660 821105655 116843957 10078870 492787444 86278320 220401339 243433056 384350929 97670063 85127118 535601389 920299997 540970008 844458431 596711094 459763842 27854033 437513188 335102323 790534512 442398734 22730264 561208324 514768555 275158012 466973877 955779733 383215575 343042532 68091594 277515589 164148186 37451905 287594459 509451984 976246580 507995798 752885040 213113862 458182215 690528513 601231606 230998566 84014874 298206390 827709660 543778716 326060424 117739201 878881039 116594935 560137935 754127657 530319613 74906489 29285668 849809844 883202577 412501243 192852376 803810525 690016832 209516916 693778784 977611292 718968901 522541717 338123443 324370294 588171933 648822013 14898806 189403538 879820579 98913680 487609929 707530238 495208750 813670353 825269440 226606142 782781642 237923728 980733799 165617609 165346572 10019466 15427452 901065503 275037063 60796182 557392381 817570250 270313099 103687518 647697895 989282000 626229235 985821338 166168647 66917521 487159704 33583808 256321060 366980282 132497488 596447343 927026875 480222593 262634049 604812668 706828735 45415690 842736396 687562534 63549653 860599322 550098354 931493461 761664824 677651772 992289643 171573558 495222021 115119095 275261076 142919915 956917449 901490311 981257607 123086096 968407833 320933665 156669904 77245246 687913947 141683746 673692589 467457175 621906339 936326638 72269842 181251428 834258682 767522593 868813962 750324690 628121914 271428669 681818150 242303092 949080441 526624146 413876650 296818815 494259596 689137727 292255084 451177044 443144391 126029045 426779494 264068577 446962710 583449398 193830177 987393011 577649499 867522766 454850186 52072191 656365757 379636382 233323619 343140793 147158974 102137580 93465482 627797243 226082604 627799986 870100335 27679398 6940485 136493338 177014568 501200081 678147419 469269652 804893480 121291810 447815051 231672973 237876741 894777761 667638726 431706919 734687126 245288224 151746038 42053665 297360415 660628150 421690047 530684035 3768942 568849022 485337969 949750779 49162618 563936927 430067118 919262953 591616326 289523957 908272645 768630894 790724039 586420064 90416899 448133872 560228228 538231951 679806845 650621323 285526065 199961924 82328241 20213190 445250148 86590634 62266855 595126918 747218784 336473257 125810952 603504080 905322279 463665275 405771212 954484897 27602202 688354684 726264203 471734882 977878641 487053201 92882129 621119033 73473264 35815382 69252904 486217846 574047333 601576104 136839169 712089753 801538028 71683764 584819297 99304530 10790752 499602507 694431448 610525890 836075764 672758754 66546323 593914396 136424028 472317535 400915646 16542584 13188572 127179848 340793820 991067214 466749403 286192303 612186246 392739022 322007686 533955505 878956868 896055019 135531608 868312391 460661125 937069636 792512510 45480422 36374165 655819616 545082929 583321967 266345506 233675046 256080720 332891829 827589442 245021103 657725719 228505087 114080041 670914291 208201289 307390216 661981504 674950692 593582519 126684104 67689713 915590205 660639609 799162936 664161578 648687571 519991680 124822702 438273560 165020543 22819478 327164080 820840160 567902407 910486047 939702020 801577453 19083121 125110202 481683248 264104224 782835921 710188335 230700619 453750212 770905978 538090835 968248070 298373024 131673354 94932173 218579091 47263558 608088136 17742026 563941490 109292060 390250061 688764193 547565621 407786958 711583671 874729701 81143471 132002432 785215747 20845490 786096239 804298868 145955693 267779487 920919446 928791614 830484176 151620065 235058179 601390154 689710900 55822603 899763178 673900608 3271130 118342268 573680521 611359267 988600650 137622010 720651327 231367064 678902557 120733301 639154022 243002582 995463002 720297494 375005014 633195103 593659338 13617606 290010324 739615031 281397093 210929770 520922999 111881269 215066189 608497532 565787777 904777089 664320135 318067308 431194051 667591266 288925930 4874571 131466886 130042933 142496581 852118213 213926351 673915493 972851515 853080374 916918075 820830870 425894221 144439442 454025972 19553558 158057048 744036297 611684944 439454142 807482421 985124297 403851765 22548609 593621828 822155896 779842052 110458317 140223203 211036102 778049583 281665487 68427027 909516469 264224775 63439963 614151035 478151126 737355456 439518903 183747853 654273530 260349773 609642074 798712972 566892099 481711987 956770020 163444749 945913285 248740515 970927170 931037581 505108634 993475779 377175762 327264529 625834185 487634079 320004086 836870287 118200015 454185928 905297315 27716483 718410703 968737278 641867519 196561828 558609087 81386421 380309682 65398970 194252548 842468110 864111942 761144648 176696450 673398315 924589397 122609734 774655185 748032921 906163669 279763818 594025053 135855785 459544702 219859237 623489864 779548788 909245879 741689880 86251069 667059547 621922717 804661772 488313178 116306589 1223600 46922264 50209365 234049636 112321234 244461913 76517745 828949530 858122915 105730550 354864198 635228666 228340284 129519382 383261586 134503953 261799555 977286639 122876092 721344257 49662230 746365956 353409398 958908109 340572189 439660468 478484009 962494907 244322239 966797187 78801495 98062193 13719450 129010860 184628183 978557039 225989128 113662283 807506568 84112042 219392833 14887119 571857062 447733117 144406502 955118648 434753424 406206057 784921641 557629516 127550313 687100225 156511826 333476065 498524687 349600369 773136533 977008696 164611629 17458772 943805882 95929479 968037320 810041686 77456693 152665503 641115078 303445821 266327786 301137999 240074218 485720619 316025118 811931280 785970090 460431620 619566282 73239868 719154031 257004276 630869384 699220698 944104501 639897564 32696763 295145541 989497934 805833296 272154236 154109562 675808422 68476471 250039041 496362096 731034511 327495735 649027599 372149588 483457910 767871739 673287587 723532128 106108711 989312705 387979762 892078801 302260679 860062398 965318669 21414709 117066673 448704407 573151762 913687528 88601970 605848525 61349422 78099903 264198174 333503658 84725820 792522951 254496483 187281215 288885046 985530994 514776950 790428999 210196935 998234861 558300737 883484522 574283342 664409448 725313580 814779458 409004602 880090613 674841855 374323271 754021677 644424882 823027678 327173438 410628763 764146002 785538317 471978185 694762260 49736490 657998197 779488080 694775795 912494680 966769295 983660841 898025673 334062599 626606193 108222607 184813813 37423283 844223483 611613509 701832731 422053417 426392967 110837333 154660383 953751176 337676958 908682060 450692412 13220989 88371851 861321175 777366991 873910168 185815714 324645604 776163013 843813911 104133683 470938807 608824945 923419333 307116002 359366971 109998285 933722195 320105933 147328452 971145479 16845769 758941961 525494563 438899186 37851281 488848250 593559570 991602458 679041562 354757983 442294869 692262551 443129835 156132397 322145896 317040002 194464465 646791500 93203014 38278376 603441538 416658176 499619675 379377224 576290532 858986646 341891863 362529080 179092578 489220315 186190912 195938348 248162275 711685476 487353888 286013557 53050079 80913457 130132368 732091642 288187795 572427237 276870546 731317630 581075988 451532796 48357631 775540454 98324296 994077001 666335184 554282188 263251530 165954858 786175766 839542062 24941503 128067628 54587495 56550436 617287943 240778408 105005138 717966572 952463884 592359026 3980128 858030317 525788838 134112496 442638312 813976633 559056087 719508859 545294262 140132075 23558008 446168247 768188883 121882304 292761601 434524066 528680846 408529485 452995278 167372965 100587900 330453135 295440593 155175396 387003571 765244890 395953804 492008709 483211462 200934041 84367735 339707944 58964357 462672927 326336795 501602670 276649559 737909236 73627882 674460175 730557665 97185890 120628421 498746547 71584549 265906377 785786967 452781749 674435862 238782244 620154715 775023763 569235380 915595308 930199159 808755305 533356552 178669316 153280368 16568013 379603357 90164457 208792311 438567714 552837384 387645460 792686738 829486943 125554696 866314620 356463471 856112361 816016865 329608246 207375262 887601414 595514623 993162229 192899516 122466839 84460827 813054231 750006956 506212561 581165893 532722468 314967865 114522444 711391784 468248233 983606812 90995140 558412690 44915476 382079208 111250073 432560937 174765946 793253370 558115633 893596920 2233194 266744347 709613784 331841441 326635963 449731551 927356064 172314546 642631068 902339257 256775373 308201652 652346212 762987934 889367545 37585033 930472153 3889988 748976817 251236740 840013154 839971957 809649430 884928631 74567519 773415858 317489567 249333465 419185581 728121554 142930384 421418776 994865901 705060523 753260217 174018218 7308427 533132634 346332764 502455849 287988245 603108137 810657502 940334457 218612424 700025046 977919491 1600930 556431389 579412661 252837670 248960896 271900972 62487100 133889526 346468491 688419312 303895447 595801956 960121247 32017000 591248694 234056376 879399256 148825570 987316593 53417473 8650352 372965581 399750237 511106201 660953826 855374728 321763702 453804636 73987151 874305103 284240480 75588081 283252845 863653142 180942106 532213741 135554113 95945560 666103268 334538958 784364872 969998715 930340914 597002472 854532070 374105961 831058849 733931325 375447886 670891795 639865152 384098238 43857375 39615388 895204439 557327555 747506470 69484495 863648546 674009975 943789598 405379 602114410 227042442 864058521 783056516 759256183 852128988 879002076 277875804 39184299 515883301 100390873 969525213 112885773 954922943 196147528 943944622 541370621 571595414 467352770 33752126 955693652 363726500 73367514 703414444 921054055 673390338 772898939 637218954 347400312 716688536 637624334 949514722 796247332 354199208 585087592 408019869 58844550 464089667 685895673 98028849 979972969 638802900 67554062 945375096 446242196 116217944 741836071 987612817 540329712 209188840 21364942 348539717 572915340 947248811 51954160 346485749 473155502 824853100 983704703 820555814 394057989 473845390 622586890 42821675 828044599 60190835 450841544 886889149 524280502 136737216 984917998 356769824 628056471 904988414 154661273 74298666 21206357 896497344 914427838 414052423 105686184 788309134 762592140 531117878 588074299 814546301 730119981 61229800 491915754 566341038 734301969 738490097 40186427 209405212 781311772 868231026 269596047 232153315 607636528 793876549 221406886 592554526 3162727 849463357 350059293 157824000 776278377 223782005 54321344 690706214 637834428 12523882 331531702 400426568 396158114 919606001 67489222 126278095 980835801 411921330 545135487 567654123 150411426 585321914 777059335 931723199 306069294 46655381 16392867 913705822 693048285 90316107 358776701 696211012 939779464 708835995 706551366 568574195 932618000 613389064 111796762 422968781 478429300 443328464 823395349 874587415 362934464 743400925 853381864 196286619 155322254 251033704 763940742 158250035 836355618 393516431 89973233 994941266 440171812 958882455 761163442 133220096 49198562 119940142 681947462 841494380 681292491 241015182 410068574 466426844 854404246 521865337 889395626 332833546 965193801 565307328 59937314 180644619 161224607 765835532 229447592 316546861 16869235 993388334 474796896 705741207 239421118 417286483 700682473 679592931 228685292 314362268 665329381 277883854 286818764 199793197 119378233 968111256 440808379 381963162 287054453 147728978 756344853 28966432 480562524 574055007 446790115 393016192 754699626 608014722 158851723 984147218 924561583 28237312 830051906 251874833 733978520 69473023 521677670 287177346 601582308 750362962 601539614 119428043 28246815 888358378 171737594 141403 708985987 612545973 234620919 996040441 760274951 990965772 877523227 93353829 417537132 324313341 486370021 24753112 932328063 497738099 8900329 709406000 525975411 691468589 813797187 259953930 613457967 335474856 547131276 67556628 85837818 1187243 39501025 966600988 889545622 211238619 819258745 598531608 823784592 906396018 447088402 436575897 749878143 177127983 382446080 167415275 501441324 868816101 192168387 286285741 219070553 53585070 848208095 745045965 597570014 662005281 4999894 63544334 849996491 404647525 131100962 788350663 405834768 170601988 607468005 147896743 381840607 279243103 746428352 58141553 185639121 46033107 347233804 935517264 223161090 729679884 955448893 577118769 451012338 133633 863404510 670082892 53718704 564128958 415128856 651288718 78650592 272645104 714833052 928647083 529808983 698450368 716997746 935643752 869052356 176982104 83540494 103409317 456225207 682485200 14067224 641864328 581034662 361301028 429897946 804195752 90980911 237863192 233830874 541993249 237996826 97235383 64592494 291715530 513880695 479721350 795520602 592531287 604882809 362870007 521178370 134691791 61320374 90692469 922851897 782889085 267674573 858908746 886298402 723899780 393910299 900365626 218280462 974944961 114183007 500694762 631657067 205163918 738557954 865487941 599673521 976554780 815239679 664266016 120786663 329120373 143987365 916307265 921651661 601386528 279177271 295346384 736078320 193014000 238555207 511446570 975903085 506229780 370355315 714717840 82645913 764265615 467599819 153442729 591726929 581782826 654137491 223383995 786946744 392695445 88871936 239136618 221766578 756627969 903402634 342553242 85748341 899906354 258860506 859916356 501292881 390554132 7779093 89887554 583568132 246334300 601334125 559471216 605080434 824205794 126705409 687726348 440987762 594305228 841169077 32714691 176088053 347822922 108615040 815551151 740518367 50003330 54687768 962284945 806631299 958090403 157354540 744895995 710513110 416215047 457328704 64322344 806769179 465107798 154209899 242853664 563958452 608060378 802324880 169038886 432266171 929030289 709281588 873253934 375851870 402967018 758484979 551939923 750789940 867100019 220007427 343824660 917103350 274695195 158625959 723734648 85301951 315980499 321146996 795815061 732195546 778475701 860137406 391481078 96099852 866863659 634334742 660058304 474924036 289175975 829097190 759706561 70722617 390895131 485476848 446574487 793862150 243961826 851030764 544652089 111061845 71038190 888476750 880681549 198249740 47102708 456932550 283551691 215599561 778079547 931883107 947795108 556555247 644536866 191792539 652655099 511400524 678643636 165229756 838840914 967819611 994326947 598547474 891058583 237738431 84024322 190149423 31600580 180502502 41180187 428769024 144080701 112218377 169762127 24762249 162984471 69381189 334211154 446536163 284980750 112290700 230935623 85292211 521362301 875472489 277084751 26533753 239389366 955728387 191763509 78230279 776064351 38606809 529294107 519639287 276345241 465834783 709788711 307945821 646337286 750968898 736714845 642934341 715703629 906476972 520212945 878688101 975858161 854424099 177740617 113355265 966714799 408676240 198647476 340593453 136665082 475732227 367127206 376054448 283976967 558890715 454284727 912557673 597497525 983578834 432196959 873842766 301929971 141985669 34304940 948267257 745470921 771019786 443717951 313690904 530013111 963930896 44895358 358387626 818354994 75152329 471742891 637586146 483828569 670390367 978179599 620493651 998638949 197823158 996548099 135132269 756713874 303349179 47689941 354211398 139444366 332403255 80570517 441374337 326905278 114875457 242157947 72376199 885895243 685875899 238583457 268424708 502323148 135995169 479328688 173194496 211147498 951071579 810780642 694976067 473978299 641476595 167986071 325133601 839299753 17050523 460265871 448529980 172916056 507955812 802741378 312360422 840359067 883311895 606251114 19780699 998187353 848409061 92156898 736598949 386801313 183256709 857540011 889124462 319251878 336868698 62318957 530399376 140456630 725615953 77891796 466951284 219608901 98394221 792084885 911425009 115444744 252350755 359954988 288360800 612822922 15212720 453237576 305698342 751040969 59488689 325479041 601744675 760414105 270152293 190859978 147215417 453409002 48399988 888856233 625177234 237785041 803691544 8092963 378241671 381823851 85984759 845192955 453949106 184378980 489794194 365374114 152340078 742144949 577845457 440700878 207484224 593058177 893938455 513182567 196615499 805943498 838661608 798360175 566357602 108813901 989220153 566089374 414739257 37620140 307461960 39916491 127921535 963669859 48009454 506163207 198010063 133994214 203872515 651959169 170889548 693666709 17333283 323229627 288328012 447695094 616446859 495812236 40753270 362901667 8994802 89885123 168845165 700172765 888245298 587719121 808986666 877465450 6324848 76242276 767601945 313786809 116158767 895523480 129973021 16684576 254203040 327983084 3195144 310591910 979942253 174084692 4258618 849791890 349830673 145102984 297486983 966277533 493431575 190756607 329179199 354942731 280641731 350540718 55115495 21403382 938259840 716618515 898868833 944584688 792860792 518987131 110887850 909019559 267026964 240860871 925704135 373746359 568843955 928899279 684338269 548786208 955500326 541113241 251094451 305330998 686216226 548581435 124124884 32164154 591854396 453304084 387106885 872496127 803844802 442222381 893899510 594620995 11357249 645284696 539205683 804218041 16788180 650093533 565753954 136331498 890954405 343974442 510077857 312314713 125390075 194416125 861100921 80890400 735529367 112195372 238737752 274261946 513293161 362862637 306426100 105147556 816166721 693532985 830160038 472527876 988271720 576575901 67148871 999628970 74376950 458870908 803847010 91165130 961480795 222117317 80012982 704951553 566091760 590090840 17266266 691481835 784506965 730883541 772372235 372552685 695595267 11109986 499330985 61404781 226488977 805757085 19068692 42655697 351806424 849228730 367699928 192594497 278320984 287365153 192223466 205214288 598752415 848586831 148895772 560233209 70704147 228908754 117701116 636795907 818999594 134967382 180794095 456022913 865850923 953166330 828575598 413962544 816792671 180422937 475367325 43281647 986180022 494436017 938453700 190502799 196181100 158669981 383097297 474502084 298551488 427837117 679716372 897303903 276423947 828612144 310053465 199644449 57520898 427754581 836440356 729036846 562721963 17234451 185059758 281089240 822917135 866151711 695051784 492226159 46574647 22935462 388024161 885271023 517371480 178994214 75773822 713552580 190180549 311387473 40571018 488732037 739224590 720287390 386035939 868164892 401415888 696089404 67809340 311453140 123843985 756766050 40489985 539082302 626516855 78066098 672687896 301950344 944217809 220256033 794176503 843308810 243191496 34717017 728579832 760562976 66227585 656870008 474115555 256408134 820773835 514686573 745140171 412514779 87490317 131176109 280679670 341422559 679781868 201005364 652875699 656142207 957771414 545882038 47740862 584288269 476464490 720428759 886238613 273198652 940684792 532931469 116507461 36392641 420164841 697603648 796955617 486392426 206990009 123587526 742800561 27763844 638274099 487940731 440278623 578280770 471633195 573474647 919703329 3931416 774480011 425095381 512589977 732251424 970977420 560330839 169056046 299958263 133275951 907811013 573156916 926477098 293258836 689664377 962869739 713423677 239784378 759825356 199816102 446774388 883412882 942616663 474538232 374203334 283073748 767333209 952484105 607223297 340807855 724703787 611154713 115287865 149799168 123744689 700055643 973292942 536591882 721628044 273251204 522384188 629439056 846408120 448861285 922697892 388588851 264247377 488637922 628373229 24072732 688454025 75147616 760001968 483587041 402202202 986721657 619177143 22051764 791722115 226400439 362859619 516425901 690071506 330663838 518741423 666332549 883235836 492034364 55440785 604863879 617801923 577824973 86819288 316726396 26686257 862033535 705315247 143449988 350671456 186204830 20039075 891641835 113868800 780041043 227745230 368587357 619279053 846922373 390639121 411001167 73322812 753498741 779943423 615910672 936678933 298684845 282243221 819914768 643235564 337684006 277295000 261037486 915508979 216630643 577763882 794711590 78664177 135595483 938161578 281851987 174316667 958200653 173493822 288185467 590758050 401239052 656772824 62553456 100677778 47411945 473554624 26516944 653427040 106014400 642427617 442622326 404699245 924670838 115053448 47934808 114871197 392348448 161488648 882896530 608979091 591768885 530124473 540159622 727364368 320802404 822011610 901681035 131519411 995505432 42382855 722277461 249260837 551672034 784830917 349938615 451600333 110901894 376455560 105027372 216916294 18883176 400166052 474131894 796070368 515219500 374583056 763457919 907567949 536071705 646354448 369063393 127840589 28995274 909223016 707721311 349797678 583750979 461918699 481317089 431772764 356817908 56110903 681033601 908489942 840941821 883488570 360090274 804360069 112460483 317634000 21276363 131343659 717800053 347924611 779930381 85535906 722507667 395904653 993103855 111095725 42259100 214683602 91452668 71254374 976422972 799173979 273568407 560173950 113609031 754885496 991946714 470426940 810996400 525496668 231433235 504454574 261501591 591523510 308814642 373962075 761673864 182607359 357822088 331990270 530531970 137752469 417526177 105555991 386173476 263146385 216651716 280948931 477829987 308104385 204719659 306769312 107278363 478288066 866943262 73403749 233173562 711406329 396347043 44169961 89419350 627780278 401140889 350920942 71820141 709955531 724883017 833494006 745079245 82705104 165484275 128127568 72973927 583010452 233683559 311663758 846156838 450335276 592612689 176503178 758439661 797332348 483272491 718234378 275620414 202732106 791638127 361310330 766654790 40501523 257996645 856074140 668281802 659137534 59511435 740101943 221609418 636910806 573595948 966688663 572132265 591596578 94816231 497622546 27123383 328499790 809286304 873280221 778835066 401898992 902299754 389791080 51747694 238088598 108025458 327368108 440820704 752179939 688678438 59991847 792681463 946675083 916065988 460963264 458328970 828093777 53581560 679938388 465004583 627177509 646627051 37136847 71290440 593959636 387275747 98413823 922459426 196562051 971694045 553810846 450977397 726510152 943601926 502725091 964598750 904143738 830093199 257935807 656323677 371287990 317927655 301521493 170479426 86509996 762484757 628808396 914603773 816066317 161263138 232124709 295760179 807890189 121777910 367050619 254366178 509053658 465464443 29341957 705615709 289674841 583152803 9109459 16184992 379271083 511834551 833300096 135931174 194444103 91235902 792254851 565732094 409163557 93776343 588727874 495673553 708777454 70052624 262793680 377360125 231315762 494918389 525636658 39205950 616696300 892687278 146088482 125749957 210668074 175430439 683882020 352859269 758583243 692991479 221560615 990370680 204826029 54860710 126301853 399270133 146096612 771073059 817518581 407776524 717365756 406246454 755966431 278659564 476299078 18760110 656019689 707614840 513678500 34172700 599337144 130374799 926859978 745425626 108641110 990044406 920856066 792523130 342903674 531955662 338030962 564464289 374842695 542856992 471841353 501144548 794643479 470454320 124733960 612162059 878230844 842099717 870924867 486713628 120759280 199740299 505473739 629295323 907355139 871668593 663468023 359208637 854559746 442844355 957150617 963200856 432888760 730523036 608240339 628308789 114995051 946271301 45289431 489837746 341644646 517130785 990982295 136288124 987585105 115716254 600966537 718332302 810332325 324407758 205045929 931091605 524148057 563036022 412903281 284019549 434704614 76371304 643228186 141780713 519215659 452895157 104981568 804620773 183418192 565738261 432929561 298413244 364525916 478218993 788250990 558686916 995349778 631749638 547491395 835451236 599982247 974285 553783537 262830925 325382043 611345820 46438884 849530100 174381842 459342165 133549649 461602810 535713469 629294189 603383524 907445482 82189345 560881446 712066255 118123892 126619707 997512170 416537136 343661977 328247516 57304479 902348893 176113647 541570472 302356641 11564882 141552718 303330927 417864773 256899997 628712970 29210593 303338881 478243070 56108789 762681047 464309073 517711599 150910869 93603261 121095122 58356351 28308961 681976569 622938960 146432853 661112630 620451129 562969989 857290961 948698646 472790822 612156207 124812292 14361293 914512849 988893530 8430365 217843775 406758302 265330363 846556745 288485249 568669244 177316168 344594038 183866644 641625241 862305638 334777514 587744857 983400760 393133865 616053818 517893682 16072824 762486671 31522665 489040307 177973013 888813626 290255306 650763835 353486187 267583953 665125129 267999035 108993836 526071848 338359164 515752138 791402211 37432262 804237388 212587809 214748431 1347779 396454453 708890026 863653417 731231967 296634882 699570531 976882186 912688700 69980566 845471364 527691724 101503232 187028025 705664737 842833212 477283331 356428572 196319398 597383638 874070055 316834787 706377474 400141902 655193951 74645966 44060467 692626214 878883354 109164630 907374645 880231133 505619083 468781024 596400904 89367404 765415907 295971434 66249589 530620960 365952000 764237308 58312684 319971586 951265333 616493775 162804798 281065017 972922347 211640550 878448656 699508755 528475338 584826129 99650657 183669288 659472095 996227479 876295502 390871802 105392108 636186500 123619289 463527545 104967524 720020193 552894949 722899785 868507981 471660893 106037098 86976334 88414554 16866136 406947921 39679886 633359912 569752719 320744903 458798612 781393269 51709912 10823721 162384960 636536042 110474378 346054249 148524490 959218211 74866104 391912647 64610318 563568959 515531936 380654217 521052837 88068482 933549167 96468975 956576463 257726413 202506073 43552796 346140967 71888564 303017071 238337207 705248476 872769790 559082110 16563441 506679413 610792023 27387162 669064373 99844418 990377895 867634976 100885262 949596105 942501081 492797909 866722777 358586393 8329844 99893348 879639230 948914681 33442514 976108205 758007497 143685281 31130631 654076648 342342602 103019195 957093719 580679809 808267671 682379863 139761918 677347467 41575629 603070295 704734629 710640002 555431067 547628878 430791332 656316330 349741336 225808766 149114238 68980467 584395159 9960437 168873815 464034388 958875118 54832683 292658946 569398969 198517964 323789577 223475616 540860566 426808773 33085688 121540374 87592797 715465551 113818646 764940264 757041180 569405296 322191247 320197536 124836362 869820125 750988868 633669046 219561460 976797634 782783285 288541927 561192792 645260076 457415742 877743534 456651547 512248425 170402479 26050515 563282743 494192056 102042485 104143308 921000829 135128174 78200036 8593626 850593725 44535037 626050244 607634905 466456687 948241491 927832441 443809403 818061615 531337662 77478449 890139430 508135295 712778088 31197710 921844441 210554517 488613453 799587974 667206064 853378232 822506807 693256580 416660975 169215216 795299065 373320637 90216045 930427239 304037028 951326026 633537318 201088419 429892623 93688576 520061460 378134114 21521016 963870863 48712082 405375032 893865666 938851512 913510327 459160107 970049223 687871121 669714624 311179029 339975448 189437042 17073614 162482254 882693622 433734589 331697470 530509040 659571581 274429869 313452633 963608609 78272248 946989951 17213381 508164872 40678526 537274841 738815340 914715897 353662057 787527422 172607282 100044077 578895288 86117608 411720538 401460864 626505083 81435162 565156247 966480531 123388558 582229861 128962784 6082179 15964450 313176608 389107573 528052385 440122832 555076560 344177347 518395080 354582864 361390728 879076306 247777744 751181923 617891645 15009994 104843979 257935421 187617276 57404410 689347063 126251238 469124949 90807926 752756321 403076465 508480527 719236851 526465023 90710387 700715989 385063556 959191192 866408952 626687483 487243576 306531783 181764043 831420923 677443217 536346907 45328004 556519523 784124652 796509927 26927521 799134646 753870261 137379296 986751923 663791025 826726359 113003160 132915973 770050639 718275836 388508792 278531165 290029040 767490169 221757907 990745030 5070078 180949098 709670335 631757562 520709029 16202117 813521605 204646305 546161688 202384865 249974310 102681210 839025871 899000591 982125087 490676871 505387205 119504382 329945147 169178230 946230742 295464661 154610557 568797734 13740496 395635704 847328900 303769537 163125872 69086806 147030920 168195951 102552258 856701255 799953513 623261287 725419726 465991471 827907593 124097767 520892690 930398257 79295332 359918561 829398847 61420418 850595432 187302406 33441154 33056932 356480636 979671896 328521593 363607547 400985984 342262090 759243251 100831237 498547981 922369124 22434397 645578901 943081429 124986655 354796509 595551295 600764297 932732589 61542765 281188243 56830355 434951809 211586499 136125687 794870370 893501700 50062459 497982155 80804105 83503614 531039087 289801095 63175509 859560681 653408643 316677847 54339124 412651893 417509084 552887105 187537370 439943481 50982359 130618798 564930137 258295222 578686447 18210787 191027810 492745566 299399030 100374519 927697376 510985529 236500207 575084099 257003582 286562666 73066254 337807688 370066280 456621695 627608783 285758144 168698729 133533779 602435991 75554207 546185673 19945075 628441312 586239397 312404910 531940025 569374550 877335047 790235247 148060996 895545834 981263057 640806563 47461217 81637576 421020292 558446746 170654137 996104391 815450329 309733157 921686999 5774370 679799438 230825048 485899507 818073936 399523777 619433287 273026280 475077985 18135313 145487709 956035651 604374710 457892620 487975676 173749259 187744020 130727276 174326610 83289854 111990333 815133173 130751071 46144263 88669818 541714172 69314754 84774208 209680854 379047911 6461207 67971578 911363703 89802609 553871085 729437638 489326386 173304371 2463918 816920725 191439684 467981 772956376 795814395 458360601 113448405 822080008 646104622 244175681 996406618 581910830 208682368 664056144 565178255 107342985 752725962 106892426 29174093 837500171 169089634 408222005 696477732 237061212 172102061 786280341 790932298 901539700 128123080 816753023 756519972 945043806 8192707 756987953 570516535 656523456 67864908 536481294 331119817 713969530 780656975 327526435 295880359 841855698 991582579 861058614 949198683 596824895 820467395 978372777 286841419 842073383 239111135 983319151 79134595 411213196 622115845 722583247 165269249 602755279 391852623 774305575 400315438 252561684 383809882 970831973 909085140 451674790 359829620 92721311 165644319 140486595 420247746 314041032 834858647 264346678 27615999 636573683 861171573 848083394 467462813 529345 542673131 706573948 983848496 474324080 970303499 458480694 49423680 135572747 61235973 441276303 762394677 314067765 693837988 146204558 137416092 455439481 597879348 497245712 548160792 616040021 490248661 968408538 930081053 325107307 85271570 957697052 961680991 798959497 658296800 281660157 799488843 200969930 988234106 635853692 675294010 811053958 94334386 724717690 799143059 8086713 18510346 561537735 174670832 712348334 560258647 312086924 167787815 10654348 809332637 715948607 626694369 299581297 536873499 556775421 477204959 474661423 366988827 291402303 273620919 25285626 573062460 73109761 78771910 413812919 561479808 754065920 224866876 508330548 331299963 24009935 368933615 349810309 438064024 543604447 62158643 998322672 855691372 82462812 8977019 665024008 650927773 488187743 817121659 40317625 44963163 294326617 514979048 264468344 585728920 788599968 289753970 11307734 714226083 368525880 425120653 128222244 975108154 649987530 636552792 158924470 526513819 5486406 508734780 817094197 549090854 423409777 667933222 257298579 358388943 529426596 922322587 9316715 17614338 591960599 49634341 915093856 886287217 564613389 179562200 324532490 205729710 321832524 335840224 772472148 690358405 760960878 900694392 517982912 263464761 537247184 676907383 642494934 395249944 38158516 459589130 944340798 461568293 127522352 54155730 819957236 509465302 976478317 681790305 527079640 420955270 731424646 294689849 159758840 148554389 474252049 484291330 206800453 796084574 672647909 979272601 338959332 286125140 879966993 856942244 549589901 269730530 386365980 44601188 664980474 424524496 504190318 461837626 886092789 484229024 515993356 558566378 993694326 344988027 92873037 373290319 765943297 824297683 667980169 925702137 825368426 994748572 262509820 32168879 643349499 935157729 11441479 982308831 73799222 743924826 691767429 623389123 866171710 78133408 667990311 383668538 355174259 24696983 845506164 93783401 361442361 214015873 652349780 207653041 411520254 745222817 580943360 29979904 422036853 101439882 955682041 99921633 96188454 70708215 132090512 592054307 858382298 996048346 426879492 932181521 592489526 118646920 408086997 458661235 49296682 76077308 842329773 256987295 953290646 540352290 350770697 314733006 606884518 3120476 522386047 18404771 600859647 955845762 48384676 875412854 57285643 856583071 975334487 5990451 927291286 107424998 450561113 638189938 955989699 877440605 570371458 548479224 848603879 978458455 859656813 750416915 907052117 554502940 7404210 712859116 94855229 358174907 27592122 554256101 213811737 402494523 572660873 667187738 210856638 473561903 542600591 120658636 330144973 370451432 126649087 109952613 330392784 429726554 748142551 286382482 307167158 171030362 687378060 8287390 2005170 547034873 758704306 761573642 101537812 766108516 474432757 48909395 976799777 354541233 455681851 43127867 609552111 28342723 710315605 820408749 354420980 105432549 941067385 684565953 475883981 920232827 647034920 806276766 349959380 247693824 92659247 509642893 418724186 632553662 517930283 273245711 32104888 276634588 34819352 133642700 895259458 361768463 35068449 872059234 716309697 343266654 915187101 178378161 224125731 478019059 998786910 578546711 583451609 939854295 115629018 59335589 712603475 762663938 865612355 62562854 10357762 810787957 424722101 281598302 295857972 942652385 554844013 327962860 71803326 589663365 314121914 967062785 951431829 201706717 691638372 520257879 544973372 459341827 698636040 769099103 937360886 549939303 347645814 520812494 342309951 463274832 432664438 54913425 78455123 150793146 969992635 88812885 961581103 394714735 370411188 109955428 189883473 925255201 437918288 261686800 367434920 752040202 228749584 171383102 953746920 920387956 544157335 498720291 232246136 95309728 120335747 169607022 645249031 467981561 542935870 987558983 783772747 975600308 42472407 862227871 126393454 864981396 951040756 940490911 112212485 173968297 50446339 302095958 951739853 488364627 563782758 171691126 92921183 792532342 343074228 46668102 565436652 887231563 397904747 797682788 982541291 518240494 819806164 480306675 986222056 362742034 467865657 622511156 190858695 362854419 484739026 317252149 80352168 288296136 110259414 192564653 314780787 160705753 494660612 266520639 501586734 58443369 438211765 594507917 703492066 633802347 641176019 121445071 373550263 39080765 919127859 208607907 409837614 591450377 688914583 248576023 954192411 9296593 871087179 145051105 372151012 208342559 314819609 452503181 496638695 425079023 645067834 811419482 438301130 139728445 930456476 939887864 50688169 221184594 534395781 754180235 854986942 28088153 875625306 228537204 919685274 647269518 437145112 329522887 91236248 126059694 578098910 45428658 135356287 301702442 42996118 360023654 510045001 210332081 665043189 6683695 487927458 162627376 670619532 926228588 154872176 453592361 866116451 205560345 674776955 253028585 812256934 529763896 133633093 540398593 610817455 53318366 40184464 47962566 235357607 131420713 26538614 813456517 29365725 14411255 115158958 72361843 226951263 477720314 135210278 891994452 336920363 623137736 54621828 7539894 401882677 62010358 313648609 120515482 267570703 988425565 373544067 79827636 370705814 507177160 472742583 981523269 413011880 512927047 882002189 648369487 644347760 761057157 314342357 673713486 627984767 282017670 598591683 854936030 759737984 733801962 599446836 96658346 209456051 506585018 956714596 611338729 568595376 270363204 731854211 688682433 111305122 957914632 621026423 482010937 317608146 93769005 463534205 730620026 606696052 198052748 378989513 103560166 959109905 693331870 777273652 587094671 975349540 375865334 294547055 587603877 962183650 746510245 684262224 24156055 105611616 493493173 635494784 674206992 763856377 219865348 215405778 875161500 30296333 836432201 209688790 347904479 930201206 673222995 78524505 389413611 871275743 310030372 492973777 682902002 3362241 122763782 122513026 831228136 498629117 417060081 271348366 313329120 16086679 955610590 337485175 121698295 301620116 972979959 795905287 65476493 45361660 11311064 793154347 75657994 700259619 2843136 423562473 482977178 528582485 354603332 872390790 252374582 664633704 217880920 935276584 520512300 340644703 57789609 204256789 691790174 327366045 475605155 5119293 343452724 283732099 342604469 465151020 585352215 168100781 113572660 503345062 65978796 977400080 149015762 141636790 677659698 4375252 417715617 13153230 532957738 772318950 885544020 637848674 436952653 955941294 425641611 957464953 149102350 335947574 14238095 840892524 663313619 489843251 846011818 859282698 773575350 41132640 176950071 358927564 61749775 290522731 862272627 127728571 120439164 11288388 269365361 798098863 15663641 687080979 811252093 401137733 311916282 549312466 38986406 748868935 357770113 317144371 558850242 506872464 653091945 573088337 347764987 168921918 62931587 46293158 28204615 689023291 87425798 205154686 47950855 1691928 348193771 762739836 129420499 468632936 626544578 398785861 119248152 494724573 938383194 930500245 748378660 250299475 332329064 639881420 851684764 690099177 957025791 263051359 49487994 610117736 836139697 397252982 779039654 751587638 296062494 659760623 293127283 236004647 864915309 193594492 237696575 65625433 956334328 367117074 534258369 435395259 765902935 653506521 782636187 556802482 436523119 531014846 807101957 768852183 23412620 511303075 311467714 980438411 774354434 360955708 443072500 463010484 610725044 74628507 67114476 906787539 734389130 360241759 142792185 451820792 553836251 380488760 517446226 362686932 747605834 51704594 798082191 366025123 705211116 433234731 922827605 141734234 964249578 582445916 763102772 987662198 93748990 927086840 820616962 720619778 140558901 263689462 183630262 751283946 338317969 250744738 658071484 72707099 610986497 653380023 377044245 17339101 33868782 894490471 380026033 633990970 946195066 30624577 852532447 503922535 463859309 627876406 498173123 280625240 62838675 113792248 120803791 9104019 40879087 941420753 729723797 33954343 57626568 913354059 785238289 395944538 16615150 295826126 321167991 480118001 949206149 698212236 497457102 835591285 445219061 877483135 322098608 243930480 908107713 174631055 747853015 371967021 802507461 98542491 652592261 865346136 64851094 773396052 874450155 105730181 567333158 456690305 139684524 624959727 222560718 777439167 20904264 239175868 73265292 194588609 719293870 22471440 745317199 69267325 710579079 190536259 946750461 32677687 434466739 854858173 59825096 34836107 79341547 862332557 133378599 584450162 580195046 50746047 210362567 307161554 8992582 777695725 763851859 1193461 402655451 986412577 778632628 276076069 78104799 851897921 323181032 649915023 726885715 68498231 719182348 289981148 111550844 665932808 322658835 546017584 373307334 382483931 433370045 305165235 97332841 419264998 889615397 530044241 470011045 99977963 837205795 479003628 877673689 453574007 480197089 132845493 292502938 258829716 261437917 223124091 963243991 584618949 873039114 542646060 653117180 592221461 832627208 764668025 110670623 7802396 163201962 336494311 390286327 596572007 641659547 340135522 15837005 531274943 870179763 338364404 483769261 559901911 817368032 213959303 13475917 297565120 346804796 158495209 408911191 608242713 381619300 372155181 45378016 107174767 914801241 698495196 699396229 599944802 315679574 662583206 607747198 331397890 999077517 998033525 927969898 640737063 190685400 796323257 24528360 60865162 134687660 508297621 620767073 804572047 722256924 486759345 102137166 921578074 497770908 363564711 382337141 879390209 735719893 427715157 986564976 503037487 126210352 538477558 102982289 294406281 53577117 563245841 625804171 52654634 413795720 406290422 545908051 604481120 55130032 570436411 665346283 42334047 931250386 138629709 846906094 506023663 477905408 801559614 427601737 975676317 17640679 809938878 707582879 753360572 90170388 546664208 108914412 68897094 85141766 64413055 363303375 138718883 627658897 841623901 43889871 41454616 100430676 589797923 498452090 155560709 12750687 16314726 50411110 944001074 154944436 897317204 302541090 632849844 551393171 730142827 461042514 569033850 392598058 168625392 174910775 482768446 715289601 136341542 551665541 652947721 200754597 767485270 644182958 680929848 609109170 540589184 574900818 709539847 130387106 73352908 717616910 995654148 89667634 768028020 792171575 97128424 517861577 94712665 729978269 69254747 677371846 43537136 490804952 69969904 212162529 518232081 405254704 779968484 654573623 809436599 285432558 855328221 576921869 929615516 388774422 38547392 322721053 963675241 600603593 305624513 37028148 318220502 301278661 979212137 86248521 93450235 76340561 456626452 40679254 658835184 378397554 718051101 702372320 869202506 640537359 914534849 239950940 898308417 547019686 894524564 707745016 832452244 602369138 137183238 614584114 991143560 28246984 937305167 954818800 628850578 242929680 844363302 947071080 396724695 676091793 885835956 342691284 752432354 194978761 383370539 263783891 573376315 953937994 966156211 295095174 446991706 733207414 535046115 345300122 280227099 429570678 905561492 112679343 31939815 42744729 579779811 875599729 70991714 517084977 682934883 552358646 612531011 379814538 351946079 9255705 55906330 90298388 351946990 660855038 285277150 587833883 924638929 858653465 541771876 890795140 153748639 988763582 476518907 688794754 186580057 756746006 970881786 92141549 721941703 855337955 987402633 154237867 730937683 910910701 671322845 266388919 315785700 136370209 646203458 667731780 145625915 702109788 758030168 350089259 215481180 43307317 937923142 140120108 901960783 332211371 883431602 908225776 173491306 359950508 449536883 360071363 969212869 420418668 304729266 543670925 128272976 144648253 697908793 859210659 908075308 221747991 125599578 223861008 358118200 624319390 891592788 503744115 178945531 502139309 853833374 394426711 545446627 644272869 534546820 299923763 976484240 270494775 60665892 149975545 630445284 510202775 362563263 452174506 930621443 667292529 995845431 58894418 664457136 693754223 770621431 572532444 915502214 748737363 648909806 126136768 225573106 393018947 629880883 404518638 895158256 336230611 798945349 293121236 980503480 186008522 593044999 809504074 456503298 653710891 959479619 86948581 16430019 174559235 391639441 947051462 841851765 387484871 858462234 358825254 933755449 481600019 931357698 701774016 82853735 432783857 827910784 308426842 825802804 310308021 712945480 720961060 646538632 364407182 14082295 479558465 550415705 459643649 141578892 6919002 965870894 101058511 946383938 982300914 128134100 338023378 781868729 969985865 578024603 492847317 181327473 511780051 974447336 112685170 66070421 909817425 397985382 893981205 70760620 223788185 204289225 783706100 797265599 703344211 629636 663864249 35419030 551045341 123507897 176997922 557964343 941895145 130572787 356864634 924196058 258706888 694888012 558581141 81209106 125428968 51428457 262536579 637209020 878392147 227738104 703279441 788209571 625723486 449776999 858970192 849511671 654066225 495192645 499293624 209926789 495822281 163157872 245345819 46867621 139182123 422343742 457348318 81077267 552916529 814212952 857789680 811623417 361617317 268887174 892832524 487046286 320315631 155369102 976771660 51224131 383107206 532567454 839433702 8830691 982344453 550920247 710858717 488927031 898629247 62668694 698853821 246967881 225826566 944199640 146351857 217525043 366543381 603700175 151118664 919459911 270429481 8908343 583599681 484563152 130311871 476432204 971609438 450627502 484317661 800897451 501851633 867424867 333464904 193801689 728771913 168325711 597238290 292146983 657252742 495867536 354815677 356106562 742835418 433158597 152822556 889187275 650683640 519365937 345403803 801802304 291342201 468349638 663227002 874941883 952912791 793538873 203890440 777038582 96682729 688208101 577936033 598534362 408149322 763917291 644852405 989437589 932243002 242090695 134100925 589495744 590474585 488916602 798118660 185826356 922075199 950941216 75013630 425275192 322823507 272933788 227077495 614165708 741283426 890304497 341623944 546712570 536359724 398030739 323751152 633042453 86238839 754203539 84093168 346904515 518120829 728945574 188858457 302880185 971036269 322959382 892375929 414027207 811875984 543010942 599853564 586467536 493952158 527383548 11742727 816775665 800317336 91336577 283457726 394117116 834157428 477598025 940829686 370517151 875628764 117097191 3559603 814383957 871300730 87652772 13804826 241937913 669114700 202663283 544818098 492667322 525622666 289710380 906694529 190015003 832721322 506548092 776482540 179189833 33931640 640741621 848481852 686765330 584594552 131939578 933398800 418751980 462053957 726744840 641785485 337682720 843842031 497861443 4583030 567659115 438030569 18387856 662113382 107145268 221051140 59447833 599812590 746673806 349158213 359023472 936688809 34395888 865571565 565687702 66102076 752019559 58945677 914583928 291301242 643540229 899039860 77216396 62292208 361093816 803961236 556594048 551292890 500319620 54455490 555875921 67978734 492486059 574263777 582608470 452147681 795314917 642056303 51960270 541988722 991214516 263500096 331193885 878126759 129071660 896881587 944228835 733607573 955827264 858812762 877425170 599367493 610368976 954641566 514176055 971462792 758602801 70770102 375272036 111438774 977741947 931147957 31933863 322744359 505411733 614542333 774892040 153243004 256598636 679368664 695231726 100329505 942868761 26425610 978456264 924456775 775823552 775201452 510580702 731650815 486530568 388005871 183534661 96899543 195163790 550227071 920878689 953766591 473513527 296150724 65205364 451255474 79815034 97139227 773999833 585226768 564197915 401408227 738469772 820796551 80776890 286217851 773642410 23645650 165159816 604615028 800618780 940983368 379816479 311199481 525150536 866347047 551721706 561201552 815762944 746885496 111428622 736641633 553168440 584942149 885308711 470890158 888713977 965123746 420545740 515230164 402866867 984743655 916638391 141336638 658056559 997415281 280070843 431698968 873577286 297747013 36313995 526712419 91246734 268646829 837911900 616397271 987510230 242149959 30115176 803273174 989035455 141543798 392431160 542203894 579002301 130256224 13094051 467716278 95379969 286156145 982946442 498246836 270899799 752101186 492099828 928956358 602032820 624687026 213171680 328126459 922434039 102002029 854838878 13680773 223165212 545267131 482594398 210675442 787417090 512709574 866464970 776452544 654253372 111412483 171172791 85772026 241668707 36783197 553488304 337048677 322939342 388951099 687811867 446355496 141052284 32428049 227828207 595601459 657115075 440999887 923727918 579549113 395518271 778566796 445746240 618683483 176350280 928340638 829358925 963767371 441050211 548340248 592736268 947819937 659752731 763909060 33591963 901421439 653208611 439596621 90986469 976147953 828547721 778798336 275019802 822116359 811226385 502848010 270234171 468341459 943847897 193962089 900406927 191882521 825045239 346153166 810566005 1395518 127010158 492441283 965162889 568060369 40781531 410415511 368396660 700534262 26840924 401988623 454472054 680049535 841585244 545458523 508713841 522649318 324256859 783733644 197282031 135483243 286581653 467516202 456341057 82945903 513994645 209264337 274828425 339039883 555417503 85394429 192951756 682427661 430352066 10630998 103004384 471133597 421046509 471401044 24184213 447887433 725906021 478656267 127936967 420007618 24114790 636650809 942656937 200888003 272900806 992455322 188887600 559482459 312487877 497745011 494944716 826482523 707009348 769773141 18038759 114943205 707683924 210990515 797370866 138035990 221621514 752891604 461685941 642668023 76809001 338386508 90555456 802715022 817042776 71008777 222722640 693673920 707659586 17895930 747078277 980560392 10351251 935965877 392559204 175355482 286227242 887503921 1838004 993236590 509793415 19876764 108179794 69993693 230867279 758067015 60546037 452488793 510958618 374748332 95156816 587767620 713134841 38228626 242998995 382693970 109237403 465721635 76367889 669413344 336133919 675962520 502490089 199001524 464444750 895049294 374357007 750671992 635069568 376195011 743908582 997379337 248588129 704604730 67373029 479455409 462671744 980435421 784460556 826146717 355183753 732133726 266430690 68318593 770362352 509429685 303528917 732116110 975151321 232413160 401529453 163801593 908375680 904019542 362803118 372820429 651585189 737160125 123492421 139171110 113355135 719917357 136550447 214459619 277038440 56439830 693915028 739710185 889391606 330891937 418373255 97091712 63025663 684803945 17926659 685904369 194233629 321455576 418020478 21901303 553868736 672066285 185702897 462244415 428602181 548506015 687581198 80187369 138182493 663589973 71874834 104053982 236023683 60941635 318513601 513062124 969897820 12428628 105288662 859289425 195836920 523661917 956381137 258862583 208465861 974307796 944766952 255215844 148279725 215303784 277117148 702148461 887370069 315336399 16909229 168488603 863842414 704490428 101192327 2024906 368080400 173067161 106078888 604104084 86525150 277108844 117166207 56422969 142053826 74971223 768228749 337890746 598633140 577126239 596753329 807099001 403950389 394036635 62314844 552230114 461856773 191948346 254378575 201743195 507284745 271287804 370231799 223643512 975778232 471424126 78184772 196374986 644491287 36780015 652995424 731016437 313888859 622677985 639955760 455942685 697649208 408184508 793833432 296282347 985310748 243103114 955897702 241777490 489656103 870728900 794007604 951512876 62677246 48386178 153256071 422478345 172190337 523487870 498638212 484922 994911996 576822984 49376262 491919636 466119353 702371686 75452426 780008212 325049670 715408186 88467251 22698877 976109049 734817037 171497578 813936150 977920151 127395279 55713639 320092608 850640534 849721243 271605483 765834134 750623776 277377908 40828832 775330467 800865778 539467044 775815389 648294127 116290028 825191652 992730117 434925735 380079691 68182542 67450301 705129362 636107083 155917552 580344593 464732485 890734589 604358526 278668634 721171093 584270159 186898627 41263700 434910692 36619869 165385538 53261179 639759999 442763446 94090012 267606819 96145578 633557056 43422208 596956059 602363438 721130214 589686176 37289173 101209904 510385072 104739474 658855620 999008509 113173380 91716567 463740993 3907968 696075093 594925981 577595415 132861605 781824608 471375470 567772298 670960832 489277362 621033477 163237184 932040808 715123489 430844004 880702740 201196899 326782566 477658799 803560337 47912779 919861329 840849510 1639037 282762754 798105338 513011012 281771263 911278718 457243933 598028610 767703040 5835379 192954591 197814809 138696984 974779199 669190279 706469282 498256384 10983994 180019113 661493569 943024802 747658956 92337572 676243896 948855855 419120138 6419048 752416192 319549271 926280377 445782055 173704662 209043130 96403747 539232028 343330747 7682464 996475961 941359358 775385505 2311339 134313948 973200314 141008324 961609501 494906946 699993960 312382239 505890940 880013073 973875808 301432095 480188383 66213379 977675991 429044237 337849871 984095039 33976782 509915496 762891769 332275192 683620158 971934900 428678939 75368540 167782000 436361403 71844500 109141357 64263261 74155840 95971659 889979929 67680518 910097515 237403228 767674478 222479753 743294168 500203905 48871914 897242618 980392288 115085293 727434962 261952878 305451518 564046355 148446015 815367014 326938123 480721207 351503525 151389376 909400146 426872065 319171377 198277902 351232920 280829088 262541164 277905114 376800748 5037446 345585632 139414616 242440675 965776464 361894369 985734843 318496722 410766283 735493814 151405363 378367930 462928776 413358242 536335802 26975130 561804257 204219169 206429607 42525463 555722694 210335338 804441963 835111114 529506715 2719864 186344033 810335803 117777382 464249147 39652904 122814829 662351133 179067520 365255504 628127596 393478243 203506700 946624319 804244526 939000515 98029681 35128809 254445644 363904277 571464611 133937128 778224888 775683780 340366735 673266705 183922828 550702073 477708667 19033941 932725142 332944886 57894328 595577299 450722268 374659829 635230203 573537097 37010961 666814078 938792601 517654911 60292320 142299301 316795583 717053201 81299815 267341619 752182010 188261813 631245896 176162975 322198941 261987138 804363109 662565676 935253843 988285937 65784103 265478864 859836232 998509245 598423750 770246914 446602897 49146017 144906742 81833100 622683115 34434057 601163532 413992069 552088969 661455852 556291370 868884552 231025406 490107539 136226170 983207417 678369352 619988421 11886745 568292 881975559 816249854 515650323 817229401 657052145 433950780 82708264 369404730 284976378 533648368 139651644 731579276 582794386 137074740 665928730 57993854 171508798 267092261 471985923 723597767 781064467 880793648 444998672 12089873 223417540 581224843 847813644 901786893 53729617 859700389 754871539 935705176 528466596 123038215 605450930 38035094 556988995 540675549 259956179 841965374 74323916 252124177 426061003 509634656 389198917 91989732 567628510 413224069 211598347 892130788 136821835 992662814 772924435 434336862 4752686 996341975 15561704 705082684 750645221 69291321 417299426 358033114 857512851 945766023 333587683 462963780 836317471 890576679 3639328 96273649 585058406 930479600 348397826 11119408 440114255 590113098 955625495 860259120 3337166 167223841 752389907 992675357 12403008 377830695 427012218 17155695 226689023 295090276 574754733 829850599 216897951 992054160 40400066 74410801 790336536 373987749 389890935 626654006 117080781 246046618 575444010 702139187 29042571 923841836 565774949 469156826 366471287 373916797 181932299 369808454 541140638 934322206 215000164 553543647 164669254 642012382 423215696 243874632 789619012 997970429 73725230 6516962 842540942 114125296 933444118 632877477 488113045 175851406 112047837 605193827 274414378 687491847 159849367 303456949 463850036 578140671 772613776 830321324 952057468 954546075 52646131 345714460 741384635 267646295 899258107 758570243 762175031 174990156 2444874 551794042 25476938 76170104 410827358 868017881 42811754 196787829 353411711 383441154 225155589 317975902 988634981 499569968 5467748 1000701 803026917 321834139 579141372 428157046 4671816 383715194 235219475 57317947 729429654 976604110 177480596 481204114 587690706 939655627 656194270 590135581 343966022 534187562 518822039 607309734 254721796 414150148 804097563 608133508 797591302 29253151 926109410 638742636 381339473 784093513 639743337 184366390 958444006 71401063 612523436 963115822 455116257 847742911 872950123 37062264 676863374 902947073 518266378 117070434 695119053 26977001 707206015 39085074 561164563 78544407 498911162 815886360 492694555 155525078 276536221 142802210 37294583 55161984 781544846 418634057 839255497 273804537 603000447 650215856 345205600 68040236 465848031 652838211 768299502 191314507 689900475 297679229 94261579 208166852 414749663 789380632 235143853 121955677 680982060 796308416 53016439 32409575 464711129 398227348 187934653 741247350 541029559 225229237 796409335 322574404 643863294 488181185 596378941 99380094 138397041 794100895 167420330 604245072 446939105 935719832 795559580 136839579 85915415 742337513 197522785 500665078 384234499 285182992 475137110 65216558 81491408 528153549 97626134 398718891 926380897 138077141 139966241 319926809 363306378 936375576 642501214 7169671 277073114 91396508 106549765 415470155 885497404 126486450 872231582 184952862 62206281 520307515 174308796 638050 262645027 224347935 501303129 646879526 509530928 976440239 564612439 443538690 357110141 514754927 842257581 136007391 652832068 982223822 455934201 16138446 771115751 98435414 875824472 48188865 42348276 982374238 316175374 780362034 108860687 40923309 965314897 23583322 561230824 992140047 24221373 823875852 216487981 378040856 323271731 726018909 354481094 740400524 22073952 711591235 107671804 864331534 847598626 760503873 699071709 156049180 629158673 322703814 107000948 357499498 223409033 149349225 192390089 539584407 929711259 153767130 580507717 747542509 29866807 141738540 592198909 54088180 818130746 808686891 284645390 993918832 387222153 639126484 734319355 409296106 203234072 841991160 126143993 903349052 455011386 825215702 59398232 936686413 147919515 166399180 294185910 371328548 168264759 486576000 763429310 97976018 640343130 196453380 698034881 670209937 190708274 142750144 576814471 8839020 951437035 861459861 855274206 191175541 353102698 442109914 452988001 408853124 136617427 579131994 312202176 591628813 404347696 224116762 380831579 404783565 390515942 675017490 776112114 558780702 14109843 392057777 509273074 506969327 588511157 59824308 29695618 779219431 202574452 606510089 640574805 6527840 320486304 495849010 50219736 526105356 937958925 503207737 934958481 74576351 82339731 99677010 518721519 339203781 323793772 899553098 743987346 714309714 427086941 372615813 125606769 293713138 764673590 487396197 800682466 353184746 547220506 830378084 132404177 602311312 289404526 625495336 608839153 609890830 121344346 659058889 135996186 911819625 14782979 923471021 838912330 97122710 23148030 210150202 436326491 346941802 962219655 32830191 913767870 241822949 405446004 39374639 535536088 170119594 379287190 336218553 375820694 926507696 19112990 360741225 381335362 308517516 986236562 990174515 918408347 960097262 501749757 906920887 724433240 516532736 682908261 415861923 466171801 706056291 626012126 902498292 905514447 440748134 935328483 819282316 682571083 193290841 711173309 218107170 363410435 90460499 406842077 739231129 869484549 425955067 99972354 103336264 734472584 938725270 93510778 505397284 898822531 447776889 264834524 475772124 816825980 947742785 891634047 282997780 506315429 370162526 38012425 411829875 810910660 825857263 83628544 493481743 19148103 647318208 564105267 235074892 590295061 970947345 974306021 312295963 396902411 926794729 415632228 131374994 718036352 361659360 489288632 469375236 809436250 754123156 945147360 478778583 701865940 836781407 761776363 60697722 59460286 652305142 472527597 870370947 478162404 408672496 216369043 349826861 55990703 780474310 584901753 646285764 751421654 411724128 958581727 840419 191035210 226730308 984731768 909071563 588389669 474020400 378446798 250342272 80659909 176110512 729120855 782525850 12891918 343413571 843223572 72352204 995718713 168267523 795239505 326397471 576940019 11608547 676224332 485447076 792082858 261126085 131732839 396020865 672850213 942830920 249377638 863885423 22077582 234109406 625473339 610467251 560646160 3920137 860809523 641306069 32547003 589930377 276348272 45438921 933343948 119571844 970307480 781579014 140355721 618063339 107976484 569812094 629671886 784200817 55259169 274271097 897843256 39508362 522808317 423209822 834855636 772185955 139611598 856933218 6295360 765084938 467400468 419457874 621521429 180726344 60763943 654068432 770656721 337112215 552023707 556517022 309200413 374847540 190612390 302072488 992910879 298588874 871884582 475099119 935306045 927143751 749370216 833149300 819168467 124694886 108875475 654024103 896880842 248487074 363473674 755692556 13572011 830874143 175150430 635093440 11600486 88430727 141678225 634773562 425542942 693701932 43806937 587259710 68549471 234419327 889332198 61460350 385524556 761216780 389075823 320830600 540876884 138446038 6496254 212561705 115657279 115371729 866585808 12538120 363858803 82575835 768230676 229947168 913449978 795897460 865040608 777566819 884328187 6718832 264856734 162387483 552937118 161180025 749647193 621486590 395599353 638979390 535463294 781123909 252712523 924539117 954470863 646105762 915501509 960967117 858667467 31158787 928855201 577769628 896213262 145230357 660345463 516960292 375177526 426311795 312857751 92734487 56394967 49702292 99453320 321251701 212089775 504906792 482431726 961736968 126393381 730547433 453232711 514373029 364187695 705945235 291428499 318658558 204567350 59446362 132142028 63234816 943121504 60997228 641004444 839334766 58743940 153866260 208811411 433921466 580178055 521669162 526655953 636573022 571371454 478625627 957824723 783461229 983532420 292772803 597714550 962442155 23320235 50947261 329331538 240024285 609408850 620760037 558682843 813976200 532722753 543341225 877211016 475844257 456854808 370731813 167695376 515598748 524598073 376506787 949520214 104776128 750692303 476176166 593865504 174580111 954801794 404206581 958041340 790850567 696979384 408272244 753292721 572815973 459219505 82624258 812840258 68628354 555900650 224039454 735120908 88623402 767380680 464848277 416984013 76751841 835580090 437195743 592350589 212694516 813702530 541870802 169986998 416911187 870563322 763852503 591491298 677881469 20575437 402048991 468732035 717554821 810321235 74541110 142887147 122057093 9681722 808243760 43201801 418098726 32283213 778322709 359238483 652180247 243170985 776222496 728932088 931267429 65934593 173799030 143961945 879637123 715669832 166465297 149064663 438749508 782834154 740555961 116630976 803409591 142604952 437879366 373480765 952926187 512420476 516367913 74983280 374618552 177128026 118185081 792717279 61927593 749024145 151955761 714107841 992195130 780694611 295556282 775978913 846629204 469355313 772457212 578782681 37541498 938922509 727847344 476291006 574273017 468403305 445438337 377682607 463524611 883317703 751163373 268967151 248254532 120047639 196466785 622873084 297175665 167168221 415590362 359103258 916192366 420062477 925727453 760903849 200757088 73800089 536882761 47386291 543155402 161856326 478685326 433213254 100778835 206532670 909504261 527568206 527452329 207458951 905250813 990976940 90776653 508930539 259944090 339031185 481494532 456410876 961904269 778670197 623579097 230010985 990289810 392287816 650073462 916017262 153191664 703346904 989817351 542590780 603249550 385489106 704447106 81934875 818702361 657742295 140983899 580722975 185310500 668436228 788181926 943077668 659413167 731474933 304524560 771873612 70506117 786019093 80800841 884926740 417205643 704379938 967454079 407495452 96667753 470043895 176029068 102375771 173390798 18362772 644966551 776640348 256368233 201930011 711091578 75070593 859672306 852075477 508309922 44982806 520511705 149008201 840576828 32441225 880483134 145101387 804314837 803505605 931120480 885115678 540948698 200842477 442011969 360919131 608337929 391196076 830963026 636883351 346088202 4353823 655246124 991054753 633510526 911614357 45501117 197118457 839201304 905173424 49193933 200027579 802672584 422221992 201552134 643249411 454663218 82035267 640867152 111494408 738057226 424503986 849126441 131522277 625346463 143654763 492441408 86200745 534850840 175920787 723084097 880939042 32790965 230846574 724510148 666301491 142460930 770011266 863419948 834178588 527701043 765130235 886722521 330373626 187352227 88274654 826139391 494531799 22826275 467006542 606026207 613399855 891510528 307669001 744922132 369373344 451323765 89879894 455574090 986174605 265800681 178658186 719630000 298591646 409504760 296656501 817409491 404482044 919184121 533345792 91176985 446885163 298476027 977899506 629775143 338344608 918690514 455914533 832876407 941516789 775437430 291418967 407432997 519464311 599087969 4871482 888837656 50411733 94751376 344411745 889102692 213068412 375586285 461249045 511660058 785091045 757905546 181585903 42089442 529606021 714931695 133266427 976491184 13407721 963682287 458782681 204268683 734889154 914697214 37145089 528922296 542650997 328564057 936355293 62115308 927652026 941226775 950952964 830580113 35978151 147881062 719682804 101562917 523467347 33448202 613222975 161074745 791353748 794808878 55680541 173476122 362256927 41463322 2483660 228181002 5145608 461266341 432449686 592551116 228479908 469594775 121473411 771130906 650675186 57828703 833246214 430843565 851571832 636715531 261423677 740066337 637112947 833622835 841629254 13096647 867071037 307368583 174171392 510941139 102177460 229851933 684417261 316950741 271315255 686900921 545131744 128977217 148167261 977581430 721528333 376647170 299692558 695518098 294429 950367745 605863155 833540643 381211309 457434986 322772527 495151341 50017677 959885474 328774175 891646931 972982121 48361566 199015513 999669867 559302705 153709328 82038153 243719965 470660069 353353408 930620887 15791812 334846979 931304502 845889596 56375311 160468025 145582154 604409763 160762454 95949898 210272917 994303097 329677561 520224257 169591977 824828902 570241934 981993805 6119431 461888865 807492279 54480997 513420732 807162145 613783702 667130060 889200298 710020021 990306484 95070059 493157261 858614650 429917038 424461763 704504246 338808703 584929788 702602754 943218466 745692243 651069006 6007736 592511693 980746567 526231994 614620025 658091823 96473927 596613829 516727608 410879146 256622462 571208605 924299879 63784606 37508660 443946292 805501259 747528681 286769129 753087672 93202296 145383779 35521064 517664059 702404379 374329767 955110201 405007132 170064587 553318797 56076137 28588677 145830490 889339058 554820671 612966869 399947234 503810953 62097051 916674842 767206453 318719513 340399800 544022685 235020474 230424814 987968978 40521732 977953496 127254460 646125758 71155791 272638239 681646822 441336204 975042618 55976589 248962758 232566103 78557530 802281556 141158594 107146207 800628400 883014007 514483233 413595268 135477594 18294185 475692319 52152436 638016992 794411833 245068590 182039677 29432306 475493405 22525008 922470393 305963254 149779468 421112504 229635399 274934062 102759326 523487957 102493033 11252269 772450715 335059137 89809799 574732270 328734085 49472360 227877023 211748091 563955593 641472291 347225686 434766132 969680965 251894476 72783124 616609151 349479420 107339155 498557811 824972825 129864163 273544557 983452433 132159985 694657061 65604185 407094047 797416387 589092142 509587081 661185010 361542857 697162572 603511163 788791481 25896656 652983524 16668504 90161102 69455470 510657149 437386788 356737957 480338113 541797618 282037435 96947263 891277038 389376590 448021428 568766217 371757107 721565985 552218649 356433446 416223046 617822835 763527494 66155786 59431330 125630928 727340797 420974187 822793500 183368313 62282022 701206510 836351837 78950526 791367612 758323662 589607675 81270753 115061618 922462143 623068371 397099053 871925760 514345409 638991997 319947188 83111625 10749103 41513172 487846628 219698903 310252572 958185817 983226397 228924713 17617147 961373679 956265510 291107688 636683532 139633822 353389710 337890042 828502014 432340236 129257653 439342029 874464266 63044761 554403647 796926408 686113132 804019054 521368521 52974894 443011050 841315709 136086519 306276507 735345236 476449502 525975410 898114162 287151672 361718161 127038874 304768819 175608193 935820738 595876508 812291726 927970915 949266218 2698121 608989282 234122808 131955774 48331310 108587073 47516889 455251311 758029835 733630022 259270364 131914709 786604916 554797768 973230419 775207790 861074275 561092008 104173645 239566038 311722523 391325317 453800553 438761398 696094137 629408747 227098489 144486998 441700472 155069403 946269570 444398593 764058685 32908731 428870721 664906349 141495804 476387611 120157659 752041993 62533986 231944377 883956703 849138902 786742145 709703475 624346691 500332773 123311836 728520336 739898812 435034359 119845653 46215718 726312111 668456144 675624465 953410601 665459496 117324936 108480003 611729065 414239883 725055043 644637797 695626959 242477745 638649955 24530923 362635405 243208302 87064909 594579782 979681359 936203811 233838281 541901187 413066856 734171054 665213023 141587191 326586219 952763736 113949198 372801938 679075847 634921696 48426402 485002801 152897545 18267693 445999158 764626611 285023930 23570554 261780761 980650889 266048300 752947070 5181811 628683705 996155372 92246720 75779840 828353084 28450531 309618121 370254270 294033741 43789175 887983647 288137286 222891748 840747383 254602839 595693686 372339583 889524535 644120089 857342384 42422080 514904136 155857895 659565045 799928066 179428450 773862160 780578955 445476750 526809229 638277120 74160454 375480955 730523841 2456648 56350392 611490726 164591124 426604663 905524467 60896653 167104663 46178106 283788401 7852045 300780945 879482088 232707982 42821834 376118530 942566720 85243914 891022666 98424615 597325313 690950731 277853065 223703826 324046039 723329815 750513055 962323160 650006623 978510364 545363354 504979625 34860756 9370433 669570749 313981773 767411254 730467402 481086436 813589360 14255803 341454836 114370305 893737891 574162818 157192139 122372774 369245892 94952407 13395439 467670507 544794074 556862524 598039926 768497900 880908564 173886094 371527308 695748077 823892717 350037672 93627784 181388695 237414782 102998217 850959445 551396555 722925825 581426846 32482990 536515184 448199003 373937826 503401843 194453247 800616999 660593982 316826021 169862890 608062743 330221460 490049751 152856816 887083985 88089676 921354716 620508902 261975770 145398378 168773332 938384841 495436050 114917470 119773535 732850832 70432041 970732980 136763740 793357866 404676180 169246730 182389403 852875183 395700911 685791247 47328430 196317909 198901582 216670805 218697153 806964326 546892266 708746904 959821142 286492604 796836580 733692212 759517860 911328704 879090590 928291192 849713544 227042993 43208661 822003433 812410179 113640702 645252767 949173919 759514922 49928946 118420648 941904325 755320483 366637913 627695571 655165267 562955822 826597154 871836073 781652975 486077833 271244692 342916232 298415328 410253650 139752811 32107539 169771509 903597869 763714483 950579055 605827766 843273830 846304070 427831199 655684008 812461126 73083965 457374280 571976047 975529266 428311283 366396725 583366102 794949196 994092297 91047723 210421372 673205804 815400150 992074347 11799990 86644841 187506933 310215318 349414845 179776098 194839212 519186354 83373967 958553695 322281762 689201733 654343879 168585831 969549286 162544240 981046957 895149605 619918521 405539357 723195224 48229803 771936082 159077680 843178999 618544732 250125403 53600370 144266889 65525552 898191072 156066879 4686747 85698004 466282198 206617946 117990456 661121410 725804300 201364423 472191458 48086061 743082511 126535336 69188246 712631796 141595931 902751557 460297755 761514452 160807267 183492978 809744255 932743349 342570658 505439607 403804435 445212415 411556332 400587678 363254321 162263757 556654558 220457422 100478115 875453110 427075368 218468571 389090873 5396021 272349349 861282331 53482082 15431859 840334022 975186683 580580009 981929953 877938239 40877763 595960758 38745505 76887096 258221366 824005209 419457754 763660973 80325997 864670170 27733658 480913675 80440844 42513769 890084587 300898267 142991884 765537696 727973635 213976810 7144922 733369657 486326159 868427254 639368093 501758018 561277629 614554776 82338026 395723935 345009368 975732145 991684693 236271228 52619240 102422412 912792791 324593348 866083385 993118788 41779871 746333398 326548816 122220716 788847167 69149757 423118983 931839052 834687453 151092617 145815861 841832376 884462274 484658374 562775983 376346721 986416392 976569966 990901497 921270772 224810254 188427218 749519270 69011300 277214800 802138510 171433712 190007590 126731858 37517096 35642731 21028083 636366848 214707902 143248799 425214015 283857659 566367782 209569420 118545111 717460400 207901635 812893841 454439027 692560009 228186177 830785748 531492754 57272496 674203598 305279879 282082750 715147171 54799149 351094050 992361971 709454013 522527762 34885915 688702225 412561213 70528646 709730309 48928060 285236548 852979108 326658429 569094207 271863244 536227849 540155673 989323644 596645838 205565867 296279024 141722200 286268399 979581127 673214954 343540895 506301078 831011188 625623646 221448248 738326691 976717696 66326573 300297057 499245458 101212488 988999283 911806671 171741134 551245945 813251085 309494037 256741406 139909514 878588244 528604650 528653717 271260270 370444647 125299555 329342492 519240026 267021755 615610891 498821152 792753064 959151786 5122229 623764251 584775431 79086832 214607295 414009481 145413405 514904352 913254939 246625893 356419988 677577963 270883381 907665933 343345401 580377418 16923693 483254915 311482016 398044697 11908632 582742286 768489345 989724542 912084778 140245724 109262650 380212022 639066876 902015714 339363808 496705459 378296318 776655593
