7500 300000000
473120533 878571341 919729872 467426291 398303882 725340142 301601088 55397762 141775244 482274046 653478633 875747088 576161336 931456574 200583776 858785750 345078311 568830504 940441756 852030622 338944451 690585221 661147477 732452393 824068719 330119223 667933717 168108947 611608482 633535307 269116648 482092061 194748370 111142094 737686392 897443869 323291900 295244818 979661481 479500313 312934104 249052117 528052323 810176105 337143147 730627691 138275693 866530410 350955192 517258890 265051509 905456476 485677462 205929650 763561772 28727001 941985693 901433075 554081338 805750079 812632552 92042978 893127278 826427153 530274180 767582308 31858698 472967330 731622932 851426646 827837516 40922658 853059842 58876337 777887525 708388403 498981650 250384761 688892344 962606313 761348152 526643348 922043073 5724401 453545235 183826365 256109474 971553997 736195594 751504528 904985100 358144573 564944386 980751045 471222854 28106682 718033593 846606458 92117533 55884315 664450754 168708520 621767785 448435803 138185501 656365367 93591922 278946418 405696558 596285592 629604447 911486954 957071235 607682565 26253895 385018282 478706961 466326125 112788151 665819373 202150696 375749341 891462150 392710077 699017278 525055435 466320342 918577742 954049465 444463607 398253841 754201119 338106863 338052558 760418306 398109141 458453582 792843998 38997660 623136159 522228027 430162440 110693991 245649971 330458324 273418099 569726432 448075916 715745328 910152113 828663430 441288085 259770046 580103792 432424465 658712689 837741514 680160985 462611650 529760613 706618910 697145224 79242453 683583843 868610501 118147625 5064468 724083252 958245866 203906219 619861637 702296896 82304224 784303140 895647044 341994749 353474107 763625793 310706795 358955250 377798427 518334253 500806247 814390920 471255916 841937154 190465963 96238585 428465388 356865788 574213121 38907375 850560841 666623033 769167401 456774334 675388737 109666694 922305900 836441645 488296367 341062641 157413042 804174803 173069853 418306585 525939744 159564777 100465400 109211284 821599068 161000743 836223906 676415879 135739786 781690375 892779990 313347310 509794504 880432924 626038262 603209609 716884432 472888588 337899136 287175268 990712257 623229996 226802335 697752567 851590582 190353886 406698531 752988694 935338297 628200998 944622142 625517514 862788710 421417688 779837033 410531625 994775015 192829333 375279952 700322734 933774490 601093629 344699570 994776752 309785702 22940839 317863662 53874185 232774064 984259580 789005856 413986775 144590511 922887580 305156820 156017229 275058288 853587514 287177174 721700883 967181811 579283732 297859877 488556403 380801293 206641157 435679106 617805251 270921576 748963380 742901598 111701972 809517091 606148148 754334250 556900947 332057582 615154375 499095307 960889711 889196486 836502905 662983486 791171768 215569459 952181335 647517921 125104931 298360346 7650493 718790747 284237610 387142976 92158568 62223632 683627100 565720828 960261828 738459458 964005590 171394886 897415385 327759906 493385090 308683947 872673340 941440692 129274192 641626975 972377059 171125919 62949934 345820778 756142390 563501518 674858538 217705044 626883549 18686898 50919875 780641647 865607061 679657607 499738240 132128660 552128514 154792400 291512101 215594632 128329011 882656587 682796385 292478478 41518222 811499422 79360232 488361158 433441997 54334412 104991993 941242351 698518937 989148099 753480333 215648589 424685761 709465105 192485145 174756134 554405143 549580983 841668198 52591335 677578518 640723609 988858082 972076053 598641414 494531288 765719481 222737362 511987462 29214875 764709847 651259899 425009549 876698003 732010643 355710478 915844479 2710989 497682552 161039817 111299515 514942684 194576929 886903649 597946833 432547237 952787774 322177883 431727569 430204615 205661619 235198475 36703038 504806821 826103007 724224167 493182242 603612177 671421177 705166343 150128443 919928982 497064087 230029052 241517139 745909090 207573065 401875018 756741037 391276642 331555907 701429659 982818444 492988630 9489921 250802477 901566572 604168511 786964031 898019588 864409547 389251322 502131157 839414084 852194456 765635438 439044558 155842216 571922541 776972583 753893039 56640198 65115826 776762919 800317172 551163656 144718474 480053589 988849051 903492337 876378768 338484251 416430311 454521551 51686033 247626485 584096745 93716110 632857942 459301971 558354111 377683423 817958679 99490155 169005159 724070004 346150812 916080613 294413367 829367942 758894629 126021790 897411725 18732046 474934899 241876281 467924476 480348932 66229388 119835945 66102246 676922469 886621475 842333915 747940468 901500874 673853049 874610830 811553843 618714564 374064473 341102086 88600743 961304055 725086214 669989332 856927270 722051584 549266153 292675708 205306742 909401185 339341715 721974412 767041862 165520853 151964329 68647233 487719723 151311300 359939180 361021770 852436532 670482898 589077475 220286884 141401388 177815186 25638056 271984804 745193067 630705497 808287565 26012947 453697881 741586221 70572649 312789363 21718401 422474971 628852802 433280333 116477479 555194648 123027218 521257572 605172766 456147468 206832895 398870941 570525832 359575723 961564573 993829022 590226716 681028933 577852693 170231815 521253601 661086771 642558354 335544397 287794346 275231744 427102031 699636355 476855604 262673343 294349104 937870374 990745863 564309855 680738364 814444706 756518020 69541370 861148242 446964758 705445849 574454318 275497437 45054405 278433461 435672221 656595896 315359867 592544931 610948589 961636761 103698592 462749500 630782721 436124686 330776175 353032048 719926435 940723017 317524732 211347189 918518658 500966600 875362198 160715518 838356835 118314821 895462045 302520693 296185724 389435506 895287986 312063937 78112244 206313638 768840079 27210176 983466732 553095787 951721514 80039430 401447247 369885949 323326237 843157061 794399238 311369854 538632557 751397294 517344431 444277558 256288342 578991708 742432559 272985985 966650464 679900565 118684090 580316897 205176970 612687216 968984318 948517567 25902821 55696163 997376574 78886246 602741741 337090103 812192280 355033685 869950371 15159913 838505837 359522469 841909524 705215485 804495855 67028647 176634928 175834264 741007920 805799702 39212535 741071417 817955320 875562469 356924486 159609690 823258262 957587753 61797238 772982502 273109591 115458723 408031265 731824087 863024917 251603438 969293060 395184240 183703527 796487489 382373632 752211446 663646946 62747451 67386562 989314344 831832419 374207790 641406868 361138987 998230035 188809340 675660013 33141770 907316046 212459163 360524445 359427800 320479015 742956604 303292367 613249315 956351107 341404526 800704591 76715555 331341784 133339957 128421500 723756235 813829266 959973052 735464624 409857568 380393376 149914928 413544996 899441931 867577094 318145229 208372645 817610654 394891127 215290165 282843450 145579939 615412914 563309865 232857303 692724331 5461081 881823534 49035799 285590169 197381056 315045426 770439304 115973576 354901625 481064055 299221442 41063875 655725927 489174379 421619319 122507378 884736069 731956274 595458259 860892914 748841476 636542369 979751520 854506667 855284587 779912735 632583816 526545773 29575737 13239558 193923814 399209465 284024539 899661525 432534883 822307245 876312378 597027926 608343310 927438288 30821557 53627128 383765126 213034848 188221461 697340654 316035106 428092813 936357823 985257420 886035373 366939132 927624926 52456634 652383160 211190957 414838565 298279451 185287917 265324271 26096236 949322755 941138196 491314962 945255370 122689676 403444901 778139077 789050530 563666057 790831020 506506660 95246728 865104123 617558812 684931797 449248530 45183118 499897217 309402052 367233019 245765136 185979660 520069844 226143819 495867255 364775554 339908536 632159684 703933386 651673926 645720830 837037840 669516291 151937427 431810242 421048713 582704655 144241238 747994755 304448932 556231665 128372390 314498066 13350907 901255431 769988321 782438310 464427765 557797733 512748900 818802445 758483220 223834462 876528870 898851837 391568346 291657505 656118897 433579401 79172953 895484031 13407999 33910959 988603990 83486922 137734829 947070477 247883545 518761177 751848862 341696180 862661332 433174313 940423279 49610773 401717165 335191070 238704920 394041706 618589287 189842633 54166092 761335992 793349503 952132865 383958329 34447128 49199695 77689545 203834576 138394983 25343984 813597997 673445636 644835080 957570739 611500402 420694448 254423658 200037169 200717627 759220982 344311625 503568370 490885524 674738211 146896771 866361265 734770342 870597559 634043141 775795782 15113943 733326833 768325003 103360697 408101285 548853083 364117715 818025443 37873410 292406502 89679232 827894874 826999924 754537978 471935666 660081699 87097507 147087386 27688515 72843006 504306156 725506210 761262331 722656392 849056243 510448347 412674939 784276332 476897726 95071096 929046987 206468170 944269816 800078706 8323527 900473853 481226966 74827456 928515737 811617084 404962217 265944448 670350239 885148373 904104851 318596545 371332459 377255816 16130902 996733419 79470152 128244171 770646665 494622069 635227747 365167679 142715349 606794064 499235704 721611131 853785791 608956804 991771125 956069721 829692035 299073051 353120243 84515736 988275524 545228033 554426287 246573363 244719000 202629592 377945123 668666787 553385332 103936755 789365879 776549451 16686729 946287944 143782405 309668018 768744029 725942148 134920453 952817387 601891847 333527097 592667098 262374422 980080519 722299699 443937016 377657599 562657984 875353064 995323107 820726290 845135117 185275929 776724051 970245784 219990341 17574237 962890802 39520763 756649716 637453213 512819417 392211441 941160754 838855234 271445337 513257948 119007585 720581344 340082917 685544644 178239028 756927379 316210696 95276334 397699421 363736712 245143424 90557738 751717728 46211259 10407761 992639476 297211941 299538984 243297695 271740896 992410234 639562929 668110687 418579728 858864176 45819023 692914762 762249590 16480867 77430253 714889607 742275032 838888765 201796573 843791231 967380350 282961751 466354440 858312010 582946071 490087856 667212327 993519382 947005936 868543569 543503184 729100403 520493004 250296989 542349480 831719459 151413727 130686761 646676534 765195396 232013814 371356981 980967063 460257716 466347463 887155772 15385004 257100790 1471587 370977865 772844460 503368792 246569321 352665399 346856963 252889809 550264843 217382178 925139752 629520249 724288144 173510346 618700396 160474698 155493415 952671384 824886214 725456121 680321406 720192941 302574541 880691386 366288535 256233775 910052711 541371213 64278018 43366828 905130698 232686086 760942373 315423323 39919513 993449263 340575085 227193268 423387987 99641055 919147670 823845523 581583917 953629480 606139268 51808221 374367668 854521235 541158323 331838811 612344303 31405383 820620984 828290408 363765155 369241279 393815097 538606699 623928871 487439946 122694851 347069234 433488404 152511190 495524779 576839457 314842508 53089029 114294126 168257758 308359120 172113190 918038685 973541264 822283754 306430633 937845485 320624496 241077827 923472298 379361723 871551238 189979188 913557980 121555907 745815062 566290597 158976501 261122337 270451754 626455347 436632837 590644950 731122840 178699438 770068934 241386704 313917828 518232821 100774632 100267913 885060867 11079225 376305698 608090735 93134377 559058623 929843889 648799581 605497223 61339864 744466482 483472443 210130120 65047453 151785597 671892648 158141738 308137024 640330775 602567938 608352906 347525534 924546039 953427236 965303787 658445403 4563623 708162421 462568386 609287162 822420855 179380801 248349484 714885461 33012085 125128880 809479169 515076716 196328035 307768468 381142128 167965553 367904610 88023238 957956791 874111744 514690621 643401646 808956542 299743596 515963360 289767889 393613621 728816145 276794083 224080825 532916885 171460675 725873678 884169845 38252089 871469494 690368396 160327514 819118861 842272948 783700350 912896580 733882160 494701325 90639167 869832888 320359360 241800899 782964376 477043053 128822082 495644184 603207297 810831368 37598317 140073231 920670661 37859511 184314376 65089780 290362880 327528743 198012655 772416632 4271705 941203333 476529375 767931312 550629463 78117198 751010784 16393270 873380957 49041218 508002157 944219767 335650695 280455395 126142099 104898185 268502828 546362575 174286045 863343855 955822867 415084217 866613688 967083881 135775185 767728185 607743445 889866207 283544535 454132161 346837409 164844903 411838994 728028599 641954843 72759982 745448572 523858719 493523741 900748199 36706628 857352429 446352714 672905213 765384983 289634670 522555430 146673956 475774965 118889348 50321278 736407182 416932192 588055958 833459788 295077447 657455951 687692545 702945874 500224449 117180949 94596365 427073913 415605968 532969460 119886175 785366621 853533802 713651169 594944631 91633907 368950309 878673436 347126235 728057214 143279790 816202480 545569196 98303429 43601426 844278634 995246249 798904816 261344889 967489044 752832860 461954052 476881006 315223386 85696098 481129758 381324783 853450604 473346044 345778754 325734895 405029358 112954667 707302383 277407302 75528200 147823997 375137387 75538329 216268494 617791647 438704078 97253771 35091257 115752712 144106453 154555201 912377759 469185579 541112688 515112749 588872272 481832730 448079963 211306942 521566864 374775792 764944888 132882404 921716490 468720038 990370269 208918611 320316175 289803562 7827206 179777243 936749457 48925720 365706518 56996562 168190572 179288406 111055813 194413323 973185549 896334391 412684074 882816581 32501298 6192217 352878517 553629980 727918980 483389512 158992848 913532067 164124449 644236350 613308912 595905878 399132780 623773400 138839334 670046517 190634177 248123011 113613076 512919807 345166874 114216285 790569434 376329918 660973417 648507122 539166820 810480593 820222988 784510631 769935018 68484858 699595526 476651637 967849537 343289246 162657514 336990909 77517976 651570643 770014690 490108843 296256024 44715644 942070993 916533066 430306914 103639297 499460186 900721865 829779751 491598512 190399320 490602607 126466756 27407293 631236947 818987036 23185669 196776409 40385040 202656375 630431243 783403629 290335808 252635321 353708360 241749619 893663576 906576661 636917745 865252480 19427779 313325331 868966056 499641704 848766693 261731241 433680804 997396191 336306602 881802426 675107703 95436227 567172827 630666688 629985616 551635882 710479551 718894064 416229620 539889165 265424291 351779198 343449992 32256072 487059127 607247471 214600443 426769854 678291589 804348556 770654226 851672602 857704050 325138193 511055280 778314183 246272771 515387905 144244125 778935431 121227175 697560669 149114521 410420604 361804279 744955043 354012116 809704396 444063061 330292991 133812140 716972885 491695782 973725694 645278771 511533601 289894499 262683209 30031245 418878195 560705665 141008574 153803448 667451231 391985200 996043127 84597339 207795443 181613341 936581058 687002033 555692856 857083595 75441099 76841987 214624469 478535722 626787112 430084815 680281973 287207634 297317007 354807444 724559814 146917340 829550759 840517021 807589981 798687739 95627047 612481078 418352512 338640907 594477521 773032089 908693055 347171197 556497183 64275993 312881342 567358833 88194123 296602359 538743108 571128306 884399977 585853219 425384662 460380039 455458965 592748834 527582066 562540522 696610747 450159883 184241637 729184720 123664130 588764075 689854282 613516775 378263510 315579848 860603935 339228382 277270403 567278853 104196253 47499460 141886228 119019670 12018728 885767741 200843224 151849779 290440220 512506482 44024557 12003802 309587024 786445106 464523649 664793404 541678041 521068461 963733938 160639012 444199251 349552635 227183755 363336589 287876722 378045371 968913194 138428479 855716309 951814044 261222590 840342671 411037363 366762038 494045692 197636528 439806556 694751444 808953873 29333925 432602497 885158754 343537620 191392359 894915352 998039435 943894933 203203272 763212881 398704983 609606713 525510982 989325690 752011325 556442984 647093900 489111333 832895953 105532147 72043011 472060733 65866369 297522856 207188014 709409620 9690747 830323699 391430819 803069465 221590332 757690785 910059431 806599141 908763062 604279744 647669092 471526516 870231325 975428003 301244337 532335695 79366146 594977791 540556713 779513822 147662653 565229699 473678754 257406651 640024001 5872868 404131909 555102080 899261571 785340443 365512438 598679129 8294314 190738050 902227012 983798160 416173385 653284979 135633788 859562677 830936702 136718680 113162342 384188774 170799430 285131733 393200321 841296976 605750520 894456098 396592739 389800553 476794292 82283035 878190798 796848588 522423670 447431472 664747655 544317708 920793118 409132107 466902905 623588300 10333851 246841091 364616578 778089209 629167530 165996547 365187812 548555784 993598344 609555930 82317379 813911505 3323999 417361096 101708552 502530600 185626815 494485096 325142100 375217120 814740517 790819391 633710605 731701142 667560196 242588055 950080515 435923541 206503521 616260486 231547606 183821492 445971030 633627849 930133996 46818816 459387004 68549343 619155215 783108864 268904191 456106983 136972677 295763030 773410474 528170765 941175862 252626173 633005417 413723761 794691732 366056014 516559671 164714990 14645234 36155099 411114768 69175094 732009858 437097951 860101728 2031836 721874365 209263838 763312401 327623896 801309541 295074055 937228999 550222774 481470956 348494031 182136877 347935876 663406741 386964231 440213209 538716656 864236977 849478891 797426022 261169606 623231719 887600538 348178909 693736566 909099851 447410579 192957560 339370414 462024941 533306327 825096834 958273680 785757579 621330877 992611674 92066709 25745510 921859410 260290966 971670014 765481778 639400554 219061827 958233842 987713062 608516680 647585867 304524857 796379444 986480101 203111920 189798035 74886227 189882081 670230644 842083766 319514359 387081987 800100315 926761443 514500206 664372516 143015572 126755427 523894916 225566244 802305694 883957421 408109342 103708330 428273941 386610093 686317484 110500788 571123169 461325058 659827375 678902572 266981557 749270740 306537109 412007241 991337561 34279870 870383191 878829347 873743190 747468355 174100612 968054618 243390676 935355340 921393086 165349752 183452605 508972710 973800889 109398789 176671377 711336409 897740684 583825483 103053386 552783723 659433003 640452638 816763128 558412076 565084601 43122300 203956222 972479718 139711530 810752440 202890513 644054654 644779667 371345084 69211669 315350989 824983772 595227852 946671983 453801575 39996591 628169641 453542955 940885741 632362116 875968963 916425466 132637701 636268517 890488246 641040098 718940258 553413826 178339425 415504321 869045830 334665486 238127761 432165895 900699247 390993327 72212359 316518106 299210954 800712873 380241282 308720318 349402598 881651155 63136694 416392316 733627225 16407830 606974188 866434750 586884281 546197301 200854039 556062455 431193420 338646742 265676561 955592756 583986409 3578417 511656599 786094408 531804796 723547308 44003868 16357629 829905798 821196197 257656791 843134373 572572231 261556238 659418964 409788900 148996118 19133526 965904472 449088704 758660802 834422416 147554353 782313976 118443823 80403468 284530379 869421867 506774956 416429291 718095384 75508864 986826718 196635967 111084560 954788960 981003653 221215688 165938424 424227118 396559605 562897851 778307831 13490971 936839416 913722632 613910059 467291322 613143304 473911788 62155216 315140197 822358764 718285746 289676055 620801465 74572565 95425672 925199271 942783219 137104828 204917382 418007736 294182484 274946952 924003580 771883910 97065922 345193272 548595533 165455271 95723672 31043573 120905588 558525801 744328544 271374790 760592257 526296209 194651591 593660123 194367291 554280567 265933025 323354773 976657417 967524880 812287924 292838598 999881347 639838071 661937959 442573295 569281279 50530884 492284196 183292451 506199497 398010430 988814953 107090955 925410559 311173422 443374828 119112194 679615500 236559823 754801897 879135072 407098559 414582409 582405588 837186567 203985756 977298480 140972779 742053965 526119779 738999213 271829358 72160909 513696341 454818918 735689811 558910920 184834061 621278850 839973935 413111226 155670837 513905810 800192853 567602876 301460353 557601204 802857516 3050937 370298733 759024368 837161850 901671525 978666721 578582557 87569504 702786837 862789244 455698478 926712394 128013057 950640520 313441859 319520260 144941826 415790950 632563096 523857641 644009414 216078155 153220470 925718031 493652038 970011198 690087752 543179622 826118226 861553973 232487307 827988677 813604305 503376425 720688097 26524559 650749477 212234450 682097733 329775362 921128877 740820228 327667033 355149596 777957732 20703398 882790876 389009961 101561510 5019467 640756023 15049966 227257107 18511214 637751606 80084108 278901583 874424020 643605073 836852059 434448228 750361647 850219776 919947887 800595070 161444762 749168187 473247172 794538874 219625323 607938785 166153375 112646983 9425549 465171323 136108699 800664732 488958519 496298261 925751850 854529870 501409165 77630190 286238399 41009087 805774024 765706266 433084405 217602324 176851036 923537248 717183276 332457475 634439977 240827550 243816418 985311079 566507975 278129605 617468029 650110716 749554513 590493162 344446267 157260743 308787621 831004121 268853237 314860863 148832344 891361823 847390675 811285885 391394397 981047348 414490366 526522374 578145634 936140058 358352470 303936215 435416555 183185099 16578833 81400554 714469027 491684336 202489580 913007492 67877092 555776824 723398172 253619542 666042971 756407970 91535023 767492268 819776540 588934132 157657752 76417876 639697465 702052122 695442608 279134512 39875493 340447288 18639785 389018697 997971554 584723033 3889808 742595308 91926869 598866987 728674818 67286556 402871931 419149770 181919650 552056271 466246768 374854247 496354653 161052320 170969123 428037282 825857905 713190625 389574066 797498633 98801956 715697828 810788188 48629824 422619042 647561590 237085891 144108763 905842945 262588025 909475327 972950034 841617054 423807007 287215360 772267942 224749957 411099883 557606040 18836913 460590441 87856757 979256869 836874632 24004810 517573005 237785211 794390535 445815579 791121924 610375103 739678494 625787427 729153064 830519248 973655412 521924029 506381649 55030047 910513029 919419405 200194389 568601120 476392559 81752343 571095973 997611208 750260800 71020515 834180072 459152128 668091381 944952336 400284692 439680062 77430752 705654965 215536510 508299861 810916081 924482992 183374849 282534720 538131468 25846430 312102714 236386583 861287317 363047599 357566673 296003110 895000197 578651474 299306197 312816296 718762140 367745407 754147909 983874085 209058229 881214368 774053804 240095845 560557109 828039709 666603024 296448130 540239098 833170659 599307328 881217359 647472434 793329553 577897230 89266269 126874657 785760564 729025678 917615080 378144249 527073390 747957738 316563005 692706530 643959329 957250340 568131585 305465474 369511878 762118503 945062683 227646367 424990574 815701112 244085823 948008412 833978707 608514379 721808152 965800864 578967322 819399090 563768594 989203476 454638760 562014000 206526657 749054282 350023838 620238060 723960955 2268274 376355009 52780619 997596265 576748075 627945842 581867168 44416483 468389305 580680699 92182229 911151719 314361838 203945474 322255467 709975265 384932637 740842349 540246954 92516498 215089998 467440909 5242218 446042124 409011739 643123319 57483353 422454314 809775860 468983229 975470652 142139974 749140366 993956782 36474255 384819740 953794123 996812495 439230667 478190224 714441846 546191234 806151846 188936634 388060696 692604053 412457431 700986497 518835846 468644717 125565173 815929364 629667534 530609277 875825532 39495911 433330760 500177138 81819819 616987368 412193857 449946399 774062078 262459605 156461176 562255176 572163185 60954628 80876959 402460896 860465628 925058007 891015938 56263845 728585725 145045681 146935954 773925915 119226259 253453293 432310010 405674635 854342576 466541772 684216928 573213828 114599636 428823226 892239605 757667086 278886513 691731209 834054574 243648793 795592008 746154313 21866242 797591722 9977264 988129986 699323197 310160176 276801158 686255748 975905525 411418290 771800166 678206801 129265823 918208282 340443703 452420740 483707997 674721371 884313937 931900629 869295443 941746653 202246058 285080897 583048670 16911210 284525792 687129124 198870686 889409978 217106762 128984729 73183803 648695672 345972805 618242717 59719466 152924229 29289613 557854531 545271567 663361737 74685404 445755437 293823111 40634587 307029952 14126227 665680641 556562260 465114622 999735394 370318390 941317886 336950180 688722817 333272902 459780780 450214570 551247662 741572464 854870115 746198084 515566702 510799798 144666567 612579621 695744107 176912175 328860213 508374243 545204642 618491113 206305895 695952828 891274132 119658043 220600790 534974674 320742886 246542479 693955589 589812619 658928340 699856720 461247631 894105046 730101590 374665473 972487625 405260940 747691214 699600235 644384275 341458026 88993007 524112320 795168345 539561500 261883129 354123679 975572275 88483733 212714534 912516721 217875094 489154075 148112698 607271551 696229533 954571526 813320862 769872498 343295116 1828597 276910274 208034733 770428517 429110133 98636384 537370121 328666005 720678442 760275002 845685286 493246692 570415837 139328016 322727143 644542143 46766644 955591894 78643281 592605038 535910368 291948608 43098210 446548734 427012796 888863935 397259131 581393596 309396476 887042145 171304282 896538084 349512823 222308773 811078855 927153164 977712737 800452072 222834516 268281884 897291835 361044360 807510445 56606623 826606753 546987024 11551193 229964231 736492141 947696064 394228146 149809109 619006908 150723153 4816395 143267481 952517342 805684229 21308398 914257796 171960422 27599689 823584766 132347755 139971168 375341827 236798459 457600219 789768354 819820414 922533476 803436051 185317435 125055471 111578679 987816098 181383689 663351460 196898004 330512030 317782472 773508096 122532222 855069698 157423829 948550660 315336341 20487117 55462550 196440053 827335979 356433419 740189144 391314447 437190714 73835657 447477421 273177659 788692930 115239918 786308272 344613833 490222122 939267560 72054965 472213235 445721612 951070011 267515065 256455664 2216687 260931401 451252629 715468986 355615820 313755386 158975757 435799155 384235044 465015147 742424781 15791557 472709416 111467575 345748708 723340399 75413483 118738774 235876681 65720629 952973020 269889299 482773837 936540007 986920460 566337957 690768431 447887627 481744654 107630189 711319758 309681065 2916087 486387403 920072313 226652596 22335133 621525218 75726480 567325788 858369622 356417348 970493291 505000630 806174262 739362238 822872430 449575979 79059382 631907005 829389196 130194150 652991583 319841056 22753230 354191862 469962901 251619341 790712516 729635434 1661034 785960857 350955697 443332471 925260373 775082578 81506193 317828576 872549508 849138177 194173372 351367818 196205822 208918338 793016333 966413096 688661206 536219195 803177896 793187684 448433585 719156932 304251092 96338048 637948645 619419452 500275694 664654743 298415013 49870085 819285431 541752158 632766188 557953880 792176765 836224128 227438832 312475593 364234244 4805773 97948364 202302673 954638718 189120489 911376346 545671850 66187528 986167981 876286096 600498316 114933260 98335441 567190655 988415955 85943337 875517027 10269961 241762767 492400175 758820196 291475249 577889320 461960006 706498367 487813259 49114670 216886758 405806930 904078135 29462176 944414347 280049048 641119614 692690644 276341753 310958488 304329336 138920588 935850921 40574894 836668371 471140937 782632588 482291839 335159232 696204512 935152476 175322954 465845642 401463168 589315199 897301423 537306144 194748047 787702649 135973449 809080583 261754616 336643676 399507563 627455373 147759513 81026168 362627012 914475076 978920227 195049286 925223439 993624219 951494299 682655687 346739328 374033761 897562714 516013280 108160703 615700922 78534474 194784563 637693550 826713663 342850146 640715830 786162754 339908540 753573295 979686253 26642223 275148116 688569864 870511201 565312525 906664799 415974272 64385860 52575012 47647302 173285936 430630324 431188409 104642109 184919677 282445029 763143157 710285956 44252875 316302445 998324452 410602554 449095759 677159851 757802649 126152963 727146453 796831854 748788306 366667421 966118598 345089843 358420352 1592798 162124210 36166059 732186567 492843305 306148490 203166188 391640525 352482542 10725214 3448467 149693657 188249643 928613357 638211289 625357801 782963290 603247197 181466719 285728224 313101857 422087411 790852812 521073609 293720582 413302448 274671703 280863733 209801129 415112211 419219373 603547293 13213564 225461622 556103813 484069399 722727007 715245007 74805440 166970074 619084151 151628408 897649908 930832886 829043411 408403676 791732538 222386104 299900029 146107195 555737132 984356469 46279273 996822340 360161883 842944549 878842198 689848231 954544638 889390205 248291129 595107418 574998427 222013727 278964487 964893461 584898748 7381822 762846638 221755839 948819390 541115555 98048577 248341049 287976650 302506440 796275062 886266887 734108201 793349557 546889534 939725555 941724994 237348274 724113664 725729707 417258871 31754610 814918995 272275621 801636049 922878233 395436989 408816615 264691417 160518377 766540286 873556833 723378948 26781983 392750747 138192222 490595625 676893106 348415667 516697437 632388028 31640844 20258503 40416676 168306257 314402132 823084862 608753126 510494910 217879481 596192494 370727073 880444535 257646686 792561081 381842968 237339384 837924578 424813396 260243176 882948443 538247563 467702307 90538058 570754825 44234510 316620352 129050596 582553485 759319805 448563867 646178636 384599940 8851149 922607386 861488817 667596675 346214307 367244200 797395757 884632059 169765455 419968873 694811067 204152789 897284189 258463971 771518266 816147196 467362377 460941386 929912627 482416596 691309754 751931794 645158400 619124983 250976529 469702514 454638029 772255781 717034599 147685137 975455294 466753642 155353315 604991924 566179555 406849500 10851778 738553146 436398133 964112481 330555970 460425323 482916662 334029061 470625059 429025792 791486379 221387281 653458656 884718330 177019692 866731271 576021604 219939944 212144164 332785785 654332636 660783062 46339829 119349125 768089767 530889810 983150904 787863278 471212394 673816604 156635426 142516695 464865601 882491113 953175582 211514640 864302292 2687718 472602194 713783799 175867362 624137821 370924883 13612004 82340912 227099736 431874437 985788738 459139259 193074986 523843504 32312271 511231180 253837999 224778615 658033803 670112254 308044424 521600371 184899276 247791341 952916612 885468396 36139630 955116669 252009242 831159092 548443588 989244435 11131039 341457147 548224149 802022690 656944067 11642538 580988281 766899847 361656304 741242733 555769710 895663690 356563555 612222198 838888212 369465088 175985718 951445055 828032977 606376331 324095069 260153645 101186160 616443406 653965674 954283746 318198838 92187024 245245935 641881439 264750527 601914226 449882638 470527300 124792467 144226819 671702451 176776801 628288562 690722545 55787091 271953883 91997790 292458575 660352880 184312621 969221706 441435117 546372672 648505883 608773164 619002527 211133761 245429174 408110883 180311741 893262266 172727626 675057162 829107567 445076359 108424864 288527936 43370816 184361146 641413670 390544443 743592490 660876136 82786253 602465212 386411838 738526710 359200259 635207237 527821760 161130648 911464621 697960472 993807984 367661156 732458291 100705767 164935908 924676626 999032244 569171741 255679248 641066579 149292891 156202695 450749160 867419594 715496905 748054305 759477931 345499058 811265465 289115138 838824943 262876804 889023554 706798482 21918257 565977080 575538570 105678888 711318638 263856554 408073394 567350466 823442211 443126889 712859706 192153817 767784771 784338635 385179711 274378388 326214854 183213276 625455724 45827677 848290866 495132835 636362429 713909114 931253289 155709772 662157407 368946762 94266395 541721335 693138100 612644383 934266395 952795420 923754610 563997362 378365391 936207768 231352043 245042503 229526658 589561945 315063143 53183838 663961684 117931427 508406957 338397841 719642876 122644129 192144659 456110366 336229050 350183431 739133499 470254351 438244391 145283790 815405142 24646734 941949447 314712915 959521431 931215717 351330332 531328777 978697495 337818326 148635902 980532744 480458194 122217964 839461519 73737462 530894763 977292566 109114559 143738466 943987134 81407963 439975977 717995968 981524827 772794589 729694722 813245930 989429118 446583097 544753615 886446842 919916731 569040112 654871906 635946167 695088775 967341613 776955527 325205080 729361104 272181017 871122328 151646548 961531350 50824948 258198540 459861659 577246936 723734 693546322 567102510 715208106 730726969 496125840 816839290 375339556 422501346 339889797 26439165 862953375 643236298 415895732 45493970 340433888 880762496 276213302 516511815 732521584 949377125 909074705 869472324 411385998 266160215 454521543 973597537 408406188 842215484 94519204 377253212 947948995 236576337 726027207 859618897 679455134 757290507 220030655 553685745 819201418 774308464 298031574 537516693 262283 399201451 81845010 807032417 252213749 713960487 867047951 135215399 24312564 55994358 845076287 84136571 987495061 983829624 832705362 147395838 183980966 326621873 307323645 389445054 489156092 724257571 601222109 431994175 76570625 648508307 394508865 172377204 132596713 571285247 11985172 896761108 699856505 939365660 771326988 459655465 746268792 919834106 839171493 953251060 300960980 37470363 470492110 686263964 64674070 739272212 123149112 32480088 955756703 91749599 735732836 847483056 216227256 907896400 390212995 689725671 480685866 729517400 316291388 954028780 305777253 796495931 887268284 533996023 335929243 349022521 372452662 184599058 112352601 230275085 165710745 421589348 374029050 777043836 813230921 374990948 277395288 206881640 898066422 906795565 375439518 531952715 540703982 146570100 269963768 797773443 836213651 562656072 103177110 202349589 982927120 466203627 670480318 723085963 809877127 58999267 40892238 835293553 311869746 646591039 260452826 845307752 60066056 838728440 85590374 81703002 206716423 261489522 979893697 967067336 172068900 989108002 257127804 144644670 863855565 37638217 296758918 653007592 185755415 765820126 848384101 462471231 87124873 687119753 230648851 414785156 632432493 162213965 105637436 802389614 929080517 221054905 492220909 847245743 312777997 856690292 390475245 829606424 898939885 871090662 641123613 495439573 604590306 49733863 951407526 421303773 281885571 505937724 801747452 26892588 929001030 470637689 599379535 970326253 439128982 686906373 107854190 488821337 845951455 657612339 337164717 490297854 938263977 352400934 134290205 592651051 830237085 359205612 961429526 575024927 126942038 859267410 944183328 820356145 314025068 228590310 520151052 680267655 949867696 485971385 60702238 686779909 427306180 266380930 526364134 634303449 672740281 164847687 365983498 337110591 921075255 377920279 426275149 598487211 454620778 889547127 797354384 613601865 162829894 905757521 236012400 870809594 832091387 256701820 539185932 243970539 304315783 852377572 306352356 734395604 659631717 648066013 832924363 8441955 981532139 232145761 549284802 205210769 955629326 555498403 261158819 594084693 470567979 27520000 77350918 323695260 214102261 359224193 82947469 237775147 502710868 21434749 251909853 8743187 776319579 450476857 239733571 463949377 678455925 147804348 229463095 481324691 805379353 596735027 621693391 647515956 193539497 587774101 12106810 992221600 633736418 927834144 363529233 598327069 155333689 374116624 216868736 667724044 215004513 295688702 454737567 281196498 589819370 237615572 252448479 26299485 279093507 154581865 423516063 720111189 741908832 165292733 285645278 896724791 445955026 23884043 224789011 260606564 247632677 379727097 559611121 887616172 172364232 482855662 252017697 886964766 228786461 411761115 32133936 814245269 728405553 171002789 177478783 785172827 449915297 578584010 958725096 941265294 203276831 570132310 856257736 636888362 99428125 241215415 945403290 306857788 597665309 59436603 310029620 373864518 96670993 438768631 290740452 53390512 609263730 191520108 458527185 174859648 112109679 910523093 192609409 900977336 112267587 668811023 133301876 377971020 647840549 730446317 23017150 814357063 155721847 628838352 400583768 725778311 623648679 540212229 346008929 462368190 809744077 40471750 236022692 582994799 56743660 92519711 865643312 995081592 727672717 487925762 444312430 703979144 258810920 204712059 432817206 605987801 664578933 821514013 541278305 690937334 315932171 739552666 57175277 957284254 888058010 777626485 579924166 258142913 366918593 595757518 915560247 301848999 735223181 3692269 224316976 821516154 204406691 544072502 749679769 679167832 433152623 157750286 9224981 265638994 196300457 302246446 871085313 163743325 229871475 264350952 894850187 131072925 38739434 27360596 886660164 605622805 775006696 104943181 899769348 982473846 339920242 352302226 421064539 835690008 290491077 738830092 205043631 342581254 954632952 485863214 246283767 81313075 752036686 614925688 395797523 529265611 404769050 397441559 53623749 277039013 225820751 128087975 253374420 962184728 121331115 925574493 542014304 197758894 970175074 228061442 803619271 440534562 785352458 311692861 188223521 195728358 319672415 862887241 798019427 920273798 76026108 69281881 401848701 884364074 408762348 818807359 189353016 485483412 623538744 730595560 549614358 136308079 218422723 642558029 435238178 703908113 203058761 68237423 937102200 439529449 283462653 38377326 682212111 218317812 80526499 196364978 345739205 602455320 577700449 763974395 938489742 741927024 677827975 27567249 273313207 456327883 642294581 900802627 869610843 717233459 470643738 397247996 69182190 61614107 362300759 873060606 640859382 80784676 996011393 487852478 627415514 137192332 552617925 227053916 212348115 394519860 335447335 535189694 490962943 308333644 771008995 819403080 464121236 240965533 317703412 214477625 313939505 936504690 797990322 174667173 464392272 168122148 470899211 745468120 186472769 175933465 985308050 614158543 991657560 915903163 962841061 600465965 962346084 719960864 213007784 216634315 503104211 827104917 620756273 69820464 119982385 787609206 251002324 830378051 834410590 62180435 743551375 31242333 657104046 124910703 428095664 333255942 998470899 527740537 625224499 351550561 863527859 69742427 572880502 344106534 676033969 697679140 563540030 329049541 322780945 670687308 468487100 843955709 490407275 854974494 735705896 109322351 968553100 564201025 630917954 254086626 832822205 397392851 433599173 464743366 376904072 225559294 556091132 431809638 458082202 459503155 78539118 296811945 315340996 550528775 38036149 988445828 276907804 893349542 750985325 925714496 456838883 702948794 517554510 582990207 869353929 419156448 795549970 971634834 286846536 506268365 840105056 727762374 958347787 485185086 692663500 464840352 331325161 510063548 991339181 965229146 768115498 911227634 739194164 515982084 881447682 151773342 237814134 512430790 733851563 652855968 568165911 427044672 653391389 643197237 323486613 401866514 137914173 177130286 174788471 154688703 525885368 25892463 882529804 146053865 966448207 160220507 420877487 452307366 720720180 907466114 125725300 132953576 477096207 354196235 650165524 554864155 693854342 499059578 934157131 466907681 183517151 94301395 531771304 274662824 441198530 184971357 906450153 841642768 192465678 724489930 577580520 85918527 946628782 528790709 810355525 995398891 413829417 763018673 627153312 798917241 887246707 638953046 765011168 780956053 890825235 530958308 40375140 939593080 359901900 780414010 607461505 203490790 819821990 254228828 266926148 745328375 303022082 416259849 689758023 478293183 454284396 304327922 106136512 145737848 160166027 616828569 317490199 355151053 73930687 150364721 602102811 778042229 508838879 182497221 683883333 624883131 683120550 274490256 740052612 521717641 9657105 244125206 130712944 748746959 148943861 904863756 612311279 257634947 808345716 777872615 421898746 547339576 429853323 115996671 145429626 104022874 415351495 321138272 449081932 287498500 100112919 160561454 788139390 382170813 796766898 24171021 1844310 84678751 272103941 849067086 519723863 249995438 165916790 660141789 548604541 641313104 333308820 650012757 556866379 557563431 722797827 98739511 535224853 143435137 962382802 765632889 461175202 891898033 641298561 928253695 932777823 520737924 916403102 742985119 963068765 725456761 598901708 375645187 716877548 330419993 739101669 727886837 785035663 370965705 260495388 887707470 867965765 757216235 383650044 239559448 719659083 313293280 431307930 545620589 968553301 521649334 752267354 381825386 285861119 852731226 997136732 782083260 794983806 595094496 77326051 201569144 219249433 704882631 467572566 194510706 922061620 842990457 976876037 560450035 291774079 131220021 809339069 497451218 710697541 769597113 518336676 773189982 686971046 330234153 826688822 637212020 450947395 788958402 555665813 17853425 821572603 61499610 483972198 250007878 455456510 188621538 622156832 915031486 847318697 299337482 49164472 455316057 966497955 378770679 711847096 879822157 397327861 348468047 83525576 348821943 290704004 229607636 656301237 451377636 538076498 235606294 691683646 524393046 248741452 446199881 388595322 398709988 643961808 173219377 249583593 877217277 541152192 496229945 284647701 355220492 48974396 587224228 115399140 931927288 551619583 742132443 665467773 403997123 142388452 864168917 277890642 240985794 870739443 786340309 262202402 39372827 633083434 513718810 187042206 739820829 554022056 859287311 637273877 259052641 43987036 450167201 62294846 246806019 530957868 895240406 728066400 538763524 218383917 303974842 795808427 572295329 824888194 267084300 997109554 280401601 855511787 933239430 130825095 327170033 69542400 270074864 671606279 317471404 279627252 366544458 313348118 7721008 630401568 935561082 357977915 620864914 683223428 4338060 644474049 321695130 183717950 393038699 219798766 722454791 634581252 84527932 651474766 67384185 588220622 901012056 440118312 219035903 808463505 164013796 677442322 306737213 72796965 746092193 569962298 298095943 654364133 743936312 712080580 578689467 971522005 127780097 82987136 802465674 384508094 868253946 881277842 693452905 733274545 905272103 719866341 423204666 280008678 415948823 622131883 217316253 262135391 572511236 449477117 565162223 743436270 94628319 470623146 766392390 75568504 796884995 351742599 577706521 619115396 530840825 418925049 266931226 272260502 48048872 522990385 402819144 627660155 501738373 76654194 600265276 479961791 106250334 989543441 357271253 546598569 898866672 340681761 924375484 482267680 599044150 17243986 695398538 298643687 847875141 276008427 358268472 425777670 849005028 284938015 244907963 374653543 546898259 180361100 592638494 541900777 706387952 55825817 860554299 737407359 246495224 341347861 942047461 806451738 491551819 312023509 967713867 914481332 890828771 433338976 599582795 961796771 891340689 104697373 201725866 961150488 559198138 77550552 37630000 885917934 175829133 142042401 234596177 577431668 909451175 7101118 795370213 166106408 701854543 29250888 973899778 422190934 219511525 527398228 894554737 232465543 477860423 232223213 825941821 292818272 28316916 205047097 7744784 828692260 216175927 757716903 886522281 537976412 782726503 439510705 936284789 675086025 417822718 540883695 899174118 163186564 774624671 240128616 804146844 121750804 544420536 977705920 992194857 749909002 196799100 314831523 47666331 118997963 701929336 915478364 6073001 719416683 352351700 603185538 417979512 988511411 281072937 99906001 27958027 919707973 661405177 819827990 31837254 503080407 744703695 866973764 154835613 537757595 690866085 803103070 511923135 371589323 178276138 6565783 209239824 155812298 806852579 116363173 347635221 396065418 745707354 959581482 105333049 530374858 722060308 551015809 580682812 231076786 761731216 951849336 1 469916038 100160095 269573885 838020652 509004310 496180556 355448444 627791815 10480348 658296750 222617806 157410967 824341220 900711690 122865199 82617225 610504024 182235861 20031192 127806027 374594215 938190649 636011512 719889490 927270058 766272981 343418707 357860834 854270901 279158342 704079002 928035113 489025925 729384637 338870154 424219028 560762506 408802116 200355671 227779850 667574725 602140316 426491264 53936859 971664297 2353665 137921749 861438501 533452229 805538068 194289322 686187395 205950852 413911002 463398327 600014819 820602784 800247005 742025871 885890678 936455205 398093168 37918139 611264 787721502 564642320 110591859 858556879 158906846 430887654 658294008 986404744 914247786 413294993 319115916 958170145 658582304 617572762 922884582 990055814 154944607 158422230 164667143 253772989 848132904 393803855 655272230 714530767 392562312 259588460 265557952 18664052 142610036 336201493 676338539 157255050 190556476 604373240 742371911 738812181 352068879 987963671 122975797 656030097 325533172 702873114 524318412 95772719 34309184 391195090 302023341 38936591 416411834 455557014 560788601 98056894 938363667 600626786 63924044 202901039 313215475 76737307 989951194 654494155 412769182 699001072 944586020 160780099 403131862 855494324 823815393 44742985 63433024 987932028 584504790 971878127 399481192 748816390 340993819 712814055 16805527 483516324 364250240 871546024 782703008 949820979 924201946 287843760 894141613 403463012 194158847 40860231 41524462 176072389 722395027 289005245 950292540 306163705 34678330 299845994 901731606 173708195 882668166 56383523 396110374 353226534 170583195 233241801 992794220 8578692 450569314 661422331 872775784 960969830 561302251 70884266 695425087 666754638 910685006 249139855 99797120 125236845 16991543 263459085 491912281 559865514 69540273 289017863 203508796 921084003 741938889 140768221 599300810 929204951 229927424 313247974 88410581 31284902 416142131 839757425 924773632 158858845 567454067 700193727 31576459 482762470 292262440 465852284 389481294 480211597 704106066 159494360 312563393 736437227 676636742 488548408 787317249 713248105 959653329 793060396 394244474 966487391 863588118 366085811 211833310 845428291 150915298 965935634 442629706 390354024 370482281 582209300 94959135 943015686 106813844 215086646 282983922 52266394 281825471 241282741 975934919 963590021 776013106 492689692 2833332 73935236 8174124 331725374 317360913 952058378 574194183 328041764 793319727 246062291 455216548 22855426 998164327 561527023 606843036 149096698 830820001 773453250 843513626 609755634 491477029 868510034 861587328 329478827 797101483 874275490 285995010 977690617 119330302 722261059 794072523 394209080 282420651 887267704 929036250 595447148 23294083 743060832 497069245 523699347 83217961 448325206 271389765 183675745 833505912 586222969 486204366 226663491 212883392 417223879 902717313 722664356 706838588 803998900 220090104 135256754 164594679 771473971 690808185 842352847 266504 836557313 494572661 902808292 50133724 174626955 103125546 263423660 24913533 758298728 841503690 367685901 905971177 30276976 53053705 860869285 383792375 332472624 388852731 349057487 528975179 123307519 513249896 205855912 983263885 735676667 238648362 610383468 485985308 606216233 979482008 805517698 77643882 100096879 507451863 965521128 672093550 77740106 209717347 371503413 311106390 727824176 661279572 818156435 556588010 867057480 479047330 887086451 109498535 487298188 113029943 953901130 715281276 353245772 658512783 360706847 547285206 493643274 12110758 200374333 209898800 163173284 881568976 270636597 385312644 275871104 644693090 522567135 80927736 818980299 88115156 436896856 5287970 289023560 880408115 912906402 43969480 266807474 362789560 471182881 928214565 203708452 414232089 554593923 392309082 415945127 161846119 395102654 562788991 723090828 544531505 777145105 448057076 203385974 888253329 763165295 767839561 826908356 829091654 879459970 935476566 870366886 189657337 511310035 338406669 25274959 285163362 661447158 390916516 317016976 578552381 19642771 939742699 896233746 611049559 552374871 849581788 472382001 872872080 316990569 846944359 51606923 759605783 918008770 230272126 89936984 420630733 486907457 72695469 475853629 550049064 175384464 564629228 70534804 409027599 797323786 678303629 367714392 836469975 803208382 446347740 412615088 869031243 708115198 435894323 754407004 170233806 914699765 20478737 589998559 691022119 503281329 605516860 899973462 80084098 158085615 852663081 580283020 781340545 473494189 547136562 826532267 814570760 887908398 253686135 685912591 734781604 181484057 169696590 147857462 255630489 736305857 376742100 249672838 517422464 197524865 182971651 891415223 805486908 815098051 1813912 727374343 793114891 409742520 272641937 902078064 515699443 166239978 606405034 126707249 441144010 780126234 695276814 709356442 862895932 48388121 216611115 313016695 618402027 607145797 612638878 379845655 872527281 880576931 920323918 111094520 907852800 359046550 130257813 317463824 910027371 992263738 125099160 735441338 807248702 118378848 899350967 740642876 884032583 125427488 381318641 137685688 852496689 166334846 888479012 335457674 628629711 983570487 981025191 565941332 528563757 805285411 804067235 692118433 138035411 914551460 4042693 621270740 18715214 567780325 741209098 305236450 360983284 650043372 855731719 632575245 223809497 393066192 933867759 495151218 101905397 127229851 498069965 682742462 574880243 515995466 143843165 222309633 328764568 50491889 540831624 868789147 165551611 940650619 64614482 486038605 173848976 867722083 110342534 229032933 104353295 844020423 324824699 105349738 505597882 229073025 944749782 520110908 780986225 681635674 340582179 499039089 441014935 509987905 324537491 849869986 177392401 356032808 923706307 421531215 463371629 984307068 935235255 424257519 402877727 658550847 446345113 670509286 267357635 309817966 612900168 990171908 83198312 103081166 439768909 521223331 274851414 524666456 635993871 144014715 191848633 707078554 120890064 457241314 91113151 729404311 488051166 312386174 395348750 927944127 537586113 436632044 884066180 614702448 152336642 108096222 515586283 640850123 242050617 424707664 435751404 157475842 455282007 69741994 858740950 741595975 139670080 441507025 905781538 81543310 184349878 848301986 782893930 704944643 126409992 238202694 459285780 21590770 625376395 844107915 183171371 807110527 344518529 586152149 291253977 365328321 354081911 533111322 636854257 883932997 453006994 70349395 967325256 739693877 57743438 543446828 509279116 610967950 471526609 494795055 9976479 407417535 324998537 549516281 993073457 799790117 348962328 968272922 421085590 382275705 630856565 423353999 624009651 964645593 178849071 669471705 483918097 66224241 467303634 741379769 322418707 460550854 7511906 671853124 723082399 951250180 99195196 131543498 855799696 528885949 581704938 995333112 432645156 917530705 625218838 249188095 404779686 486562893 314478984 266875075 654780556 342286369 88969408 854285004 494610561 45312101 719727636 909727571 74500365 915097451 666363261 120881636 298485462 944665236 146969252 931134920 778459663 594857028 83962576 129738523 821525813 382098090 808712772 14791429 580209383 425605041 73977397 908106046 524115736 320630994 210965142 329855608 548720691 425366674 680900366 188186988 807463001 28887967 307035915 578182272 296293573 52137347 420319984 926122002 223757137 857159939 809973354 765966180 22643217 240098326 469397789 308933509 887862934 74246253 686258204 573760151 496565856 104020957 422934410 73744656 804185074 473980239 971784410 457780414 145008784 625496303 601809038 605059773 605655293 583886738 590334037 320037682 699283141 216741176 967737450 929866279 240770992 471847049 455054912 944002206 958689114 151587981 800727497 192574475 882438315 169257961 760145537 427578878 792842053 930651704 100733612 904992025 275489388 982164511 59177182 903501836 852275957 684932332 831283384 925994437 632302902 563501830 494390641 241711342 881093470 844656015 246562670 959481139 651810430 39700176 328500952 136306696 476493977 89498844 998088114 958126576 458819605 913061090 765224855 869041681 154055772 702838581 874158107 158103413 987574093 90483603 574629096 140621341 101010917 502640515 190744953 178829104 383103703 392268403 40395340 802844660 117566033 842652315 560996862 275143608 404472930 35058040 76715852 267147634 754775566 557228422 126452847 40619919 17065963 241376788 919267998 420808373 708465992 933151931 9742597 672016079 945484137 789951099 827789525 106930417 495593587 190253172 162995331 199745881 964077117 351350229 881269861 65208476 297102308 683332067 671540288 775461109 835291522 646845719 651565516 895910080 369164411 662828330 887561060 652638845 288079440 399142372 248946027 807381236 856067872 586147417 128301426 688039873 749175701 104273765 787345457 666941303 411303319 239539665 263048917 937469263 634500569 633189581 27346707 499739931 986142760 299427337 626467692 591270410 44482287 101434586 29655575 536081123 280451080 558422013 858984414 990156775 457021490 799073758 172503071 166691808 536173790 319082385 886393040 727918308 418461217 318556520 777161178 118786908 278505191 985289138 663660095 240635740 870208992 598625882 69194263 426966545 583876359 724689580 836307492 248767574 9724880 105710904 142064404 198148197 976460270 264569295 974637140 849405098 459914430 900262826 334323852 144324019 691367763 79945658 154817860 173612831 819139259 721259246 976284808 737087802 811721810 221708192 966685025 111238738 277644565 296552617 841126624 921649968 452513177 158503140 847346384 95243235 150866757 679347554 726987373 221945174 762236740 273397298 521952451 283065341 411468601 833126096 905833132 865456035 155303061 786123578 106085011 165423180 739003402 395999709 54123070 260333849 532700165 414323950 347806936 310137831 460650663 228424155 546763382 540351766 945393502 400581091 896340037 343313252 823281089 20866551 69135428 703944182 574342265 811353341 838652282 382495581 515857779 762742602 862881457 404758593 335217791 592568353 567783270 472911980 994611203 183732997 809957925 112922486 768607205 410295365 297917646 989299207 664098982 56837905 869961772 558465207 598945186 184598054 656311737 100481813 249898401 725349898 947514563 340262057 253994485 646403032 491619007 461336169 974940664 826709933 964917436 966951844 600390168 656645160 23815342 988609071 893537962 299257580 859568229 110443573 541240675 426317355 109858129 239995344 262390239 579856586 870112356 609337917 24826207 632054578 105241621 248535231 728558480 27586227 438139520 140856083 74742406 386477972 900256682 500981704 862030267 157879267 718749386 162788996 505223157 567416388 611066651 183386339 407287267 996496750 253300343 567941762 77837271 118368751 869877201 47674709 113021837 909967940 89649456 25887281 879490650 204501860 520173140 867566501 326793042 971668239 373795696 522804740 939998213 431482093 538742589 908351760 217169368 892276039 617076779 60487748 415893394 982050652 132639922 6277053 196994291 751368033 166265799 278970494 539691545 751444587 695832920 714826764 679633757 644911403 961667401 36049511 467272176 285022356 155777759 920265072 815015963 769031331 673848540 347038174 712294593 731530350 554293712 317881991 103174907 481834268 330260271 410550234 300730852 631305111 976721901 465672234 235300192 137793840 567149824 295534824 986781672 84397204 306559557 219991389 617206377 459799348 780751561 343295754 93065567 844759757 325059221 263055553 378201897 824084161 177511316 572006967 206588643 87411757 155156261 328367339 952092363 943039529 956840681 997481918 336693977 987077030 964042375 736430125 17104349 567154912 64716467 488960986 468097338 941083830 240209074 832359661 865556752 806914194 59041115 287482535 309165242 292095483 348404236 621916709 682055867 89891248 994616293 733172177 790293020 30995945 534835139 418001583 598677535 705235865 374667087 979146954 59311078 140892461 706073527 174438530 557531638 522361713 438905857 750033993 936569659 734382564 386366934 534155663 888688261 676656092 787473199 632990357 196706603 565618781 626267028 673806275 392725826 341671972 308696086 841779391 396079378 527447464 120411442 231963696 443088562 535094191 855567102 357098909 818866495 855777534 311927791 226769779 243441592 458123844 376304933 3231609 479084680 889960979 565560686 668537938 272002890 568560110 736008882 596905028 800011171 599291954 538008450 999508695 670633249 67621100 318538046 629704731 773661981 924660327 719525077 446872889 565119052 98728534 546071465 40718516 592310133 977308058 796234818 249809725 703059121 202967792 862791233 372597022 400099517 427831315 235740888 768376694 817902380 876897398 757575851 205955259 546065928 460681553 631500090 786981325 824069341 247487038 697378519 796570690 405143106 811357864 557678086 281233709 422189026 491889376 935575545 999645353 866046626 150068290 314558292 390016332 189446246 398556649 215902405 198314851 474580009 28278500 882287387 916553141 51482730 973009035 879457171 767073533 847272748 10559133 969522273 610096410 898525635 253525686 733222254 543617248 656462409 259212098 225782045 85216003 613227901 107485483 827288686 777214011 236934623 554554335 913421501 817029421 315156770 19444034 723578391 628720625 791885698 655487669 448453491 903765295 937410733 178766518 719273025 412036832 977236556 605805241 960157565 869123512 969703210 519257129 957466289 626125118 122649906 178154680 157186467 310245533 613097846 87374136 106668846 510612999 954030105 924379438 151024531 824300927 691437973 736709601 907538687 533563035 542119783 155471106 478405879 355974162 550190171 398171811 102178775 526807305 831907120 882686308 153320751 320494074 600222983 160342659 98572747 390399214 552930453 696687389 637617025 564781111 835572273 677719206 601726010 253689260 553011680 952895263 393687771 469358568 907833508 485639336 984854775 109167189 373473697 404671937 17477131 748991321 479702036 872398645 641922546 467495176 433175528 878108232 496010443 20882527 128708967 808193404 892639993 669751833 713270797 853222912 504917315 229202737 362653817 266034972 95142645 636283261 616275652 620585044 204040294 250433892 86326259 397492165 683518246 221054466 509818232 11371928 761144519 353759943 182862271 160877500 830690505 168216339 557882388 929902627 120853752 944807768 96907778 17783608 511223062 539511958 243015754 365492969 262731293 719230191 48171094 758754720 631835366 34210926 167530319 86877880 484174860 124386077 73023641 616338775 398633799 729397848 406331500 374892927 293175406 587312833 120236824 674513783 375444556 638058549 124300369 714638310 470048000 234850525 728012115 780363343 463836648 932655412 303990048 519574204 351835830 146925797 915376034 54439719 668907131 925568741 780952815 611932285 166534921 87436586 974001862 662660459 674426822 723870277 598871929 192024284 601227744 992724950 172481062 991546472 395805527 891435274 974367395 161096606 85378866 11772299 413490698 415493184 857376102 462920501 727095537 266544716 383629553 325686546 706053334 824788095 347816353 943966871 935910168 112230226 552394552 994430658 115437496 551117869 363299404 803049785 415160993 331787891 12977770 751219360 719149887 793624101 479710783 864999323 586844179 989020061 357114081 560053438 166548160 564216690 526868486 115438568 157913145 36713698 46573387 188018884 693192730 218647846 233878560 119811435 291233697 733789153 980098343 508415051 472587442 511795513 484236115 752205327 48868841 150435188 385718366 971266353 914839637 7155555 132700910 965196741 157284923 293725739 345315617 799941825 917738340 338864477 814634478 921951933 130497614 748065092 576388266 979289730 408650701 718467239 876306411 198309893 583610615 31582643 763783144 977829511 782511694 74760829 617936378 3053497 164665093 676602782 726866885 678951227 234371356 550499767 959792732 647579221 822772671 414113646 435168551 631137579 345672695 252257905 846024428 427887522 934381753 781235281 511648110 712356868 725850857 564229643 665893241 622373770 850091880 19081132 616474618 427278216 161349912 236181030 394293997 483061844 577684073 536227458 568424850 960279817 988082797 284759479 334868695 854313123 737757255 440935405 865654967 952896206 517386336 33335398 762934721 775003600 433435627 585279815 245363889 123818780 170513682 47890807 171732395 297156867 39791042 621854880 181779219 146550666 645164304 849010515 401945611 546763350 974897990 592731464 240422852 527667342 270113731 547064085 612859669 889913402 593972753 647245853 840498350 454505010 491263734 874900479 84147179 899633041 999672943 351429153 903002296 429237230 287799058 439038338 791407727 785688668 535636729 843755061 814874465 761227366 189443403 410651138 314388813 572978514 75970165 679542278 986937709 795602746 535907346 789136317 771165679 5316981 530195829 428879032 734398953 800065482 925024710 793746975 433781134 934814677 956186314 964890541 989792294 110712978 345882830 595101119 674008835 295659392 339382170 843088191 252004980 508540414 844734879 154662106 159863962 772022364 479411270 186423341 839124591 194681560 632772821 355089684 331062081 24510424 522012376 672572876 108094616 677075145 680160337 379316518 722956616 869045596 654613669 618325542 437179657 186547918 807438206 996594532 412050499 58405538 12689570 844989384 879783368 59554862 427658376 270428345 933755719 942303036 953714174 267056680 643127323 640229620 98126759 699791581 235711405 147299231 110857107 11126545 417432987 897556102 909292154 880418437 193950201 130413205 626487611 212471155 607923564 209319450 409225124 862615014 442792379 633198418 324818802 962996346 669899150 535226456 744689133 123727412 806442455 967110256 73014995 488113774 235029112 218068225 129010897 960271106 519976762 552474009 684050203 189978592 405074452 461430259 913834927 585659553 633403441 98858623 542859303 69359260 774126877 376950690 446900514 375771986 579690780 184176991 74744506 5383561 861740567 900657525 175465604 500434436 606416630 678820959 894857944 99865574 871864504 446238226 524772057 915346604 304680285 389004900 899741822 800079862 605827848 349008844 37238188 621940346 607092370 639917788 281754171 241287461 999869788 416632452 214335229 741492976 516007910 590048165 598341510 135397650 280623377 160583740 843985755 909148365 402397207 548985646 196807229 450509218 141511084 784724196 300295570 634500457 498668599 980697960 70285876 403658012 305610232 967746022 485825481 695118870 615744625 635046052 736811589 307315030 201379423 936751668 538355985 208114628 822466899 607530158 343406793 442398659 62652767 948016394 944979903 646327764 467153218 390897895 780855142 44132881 365603505 195950514 846271914 952346311 442835512 287323242 595173605 537141567 383670918 256957889 359301398 178424856 734647165 186966216 458987593 545276673 10037864 190328889 540986645 776759313 213222220 638593633 615411519 372860099 503000919 976135592 727422588 250189969 247174774 56412094 438136660 342107435 853561858 41711460 562128418 290523220 777702042 478969044 327640120 875752282 334710028 126119118 471403295 810244656 625495148 806104129 998738940 16231977 696518471 14085778 783045390 724926547 541555186 873343627 481063763 500328302 532576251 238141411 729321034 184013192 711476417 962643814 587694902 822555424 508591041 398078004 242187889 360478788 50252012 12790325 916964618 966426527 500587572 408880491 737576139 719177205 404150500 191849617 528854828 829264788 410978191 859428370 256132271 631686050 262888957 97472163 942039000 613038734 312062896 925753869 276499916 719482280 679105297 170271240 621653637 266968013 987182908 558745923 161563312 483188027 950042213 666354305 648075556 86926467 213137637 765742557 369069054 292665500 56534757 782102062 698663261 21851667 51351717 232948357 658640823 113739616 533069674 43600851 331428822 997705813 605082882 36001960 402931315 162575024 493064693 713589526 420655981 189198410 513511092 611196582 333194627 837020914 801928894 832430203 220850172 513691605 998062557 605457636 865063032 699230965 859530257 351118217 129740104 902682316 26392576 479820338 6168454 623933831 106751291 439430802 667986382 200397567 773901456 783440730 102823749 603096096 195792449 696602857 122031966 849467882 463363559 575476511 400300106 902426258 451224035 757652559 608948933 314786428 984528723 630811090 692049676 700521114 658150585 73626347 181205786 318622981 612553315 162300892 785138827 107542536 150927863 520384822 547632181 722213452 499854166 782054112 201247982 739094090 524886023 643242004 963888670 442635679 528646193 638510015 540748870 159811331 111504879 328516715 825688357 333281871 656326759 171636483 246123108 209413285 298110749 517004955 937718539 272365452 876056452 990692771 373844084 211184556 300496889 522900157 269651711 27907446 704273259 488490807 924528282 465341542 416361507 356771211 349334584 245530257 788320686 755591927 502482506 54555824 591120551 266444726 93916802 330230615 982653188 22047358 331607081 298214719 523294972 214165024 514468031 929385108 28606809 278436465 37683290 630013381 271241878 204465041 961197681 624592716 27681302 761224500 819313689 226564622 729779704 501622989 387137799 652715813 536159878 611826856 477854347 47861906 512835207 436595278 42041954 990104571 606754622 72792708 93522141 955951183 746231658 621067650 869469391 416385930 376732348 945222862 322109181 784562526 62934933 301612618 809852777 203938097 14719377 671052940 18132675 10925927 512611232 35118995 225500886 327978757 417368909 314054578 328501263 823633552 737953088 379488376 93994991 703248625 183626291 433259329 656648464 380369479 532249581 853731523 571743830 114524231 529009429 298498237 25292452 581673221 45667128 602938061 517291953 357046370 444285673 932090606 667389941 271362579 151330819 583637394 9589181 372905033 491501066 402603864 701734750 671466242 463967920 79248490 849730182 253771756 755279475 801231222 741609646 763914481 249620323 62626375 31394475 537415523 977972738 427765759 140472676 624942534 314393156 749770995 221927838 30690356 452384949 930992163 783839475 3778929 404673978 893431381 572768226 736145036 691511023 913768652 369433343 724702510 80201392 540084650 482409803 617073587 569213407 597349790 358224082 599158477 443235137 381795559 660361082 729568152 110664121 132163793 304102769 200456956 17328315 773492627 393604917 984159399 115381935 697265306 56492131 780856264 414629888 287731743 513018211 23663031 812305542 646790051 610937546 212518211 253047143 391295056 5608742 293781930 54437150 659191657 975789978 626371418 715605738 704152962 735486212 760933203 569701955 401641433 393221071 864365996 257091878 704186105 693586260 857694912 318592977 109421557 549728987 624975294 813027913 193406590 96451566 15043680 166026064 521520580 527711388 712016009 602942369 317511466 732445998 542887227 478815387 480399662 729162346 765933933 165425927 974919167 798640577 504049690 498579732 360106562 208532634 579461484 120485043 973172971 766743888 756692296 202178425 562399372 502682612 467434238 2489051 433034991 176476636 225267468 950598809 853296091 323928370 646414247 241354832 60417239 300466838 906959690 482136937 647903931 405393379 500853144 899087104 651655653 672768170 223419183 905604901 33824029 170645807 224895192 340227902 859607052 572372514 130824730 631491897 642587267 808761594 683928452 407509526 390932616 776353301 414147208 133820516 109660590 445907209 45435947 347597891 267425936 938203620 650718812 284189484 470765564 751248526 987769013 405834715 341941107 639323032 613013795 665408325 772074968 152515740 291527078 435218629 688040116 770249411 38634405 985654638 370419748 543392609 693434604 220143231 346153824 681528564 776841192 722377448 532055980 971002937 242542924 434346708 151238200 929554937 919901593 885055842 56519046 70762773 870261339 268400297 596446937 155210673 215860308 692950879 725926504 672108471 439345748 436990678 579165343 33745697 637324821 779357421 75515895 895394069 568998577 542364024 792931890 695039384 476219229 560753723 284464628 75051422 426922467 908695120 812561443 569857823 548815661 931440285 643574845 318629459 420105462 818687801 644559173 785586462 878506937 368755359 929176368 365785440 498970908 447260837 762751045 771635694 381868959 702889372 590463196 68997436 171404192 542319165 750037395 153516557 615791353 795125670 658847985 737156148 304984398 418894699 947065981 688985270 611843047 490246712 29251493 826576573 578613974 915708285 595381984 162386876 11232727 845635559 633510244 357010070 514304186 544096489 512092703 314538657 261229252 464976326 719661051 387067553 990556531 451305682 84776872 642050254 434880489 582077002 815551908 348992114 342935165 160560354 452571679 152943891 561983754 186458704 446575597 63430748 762974415 633473029 951741866 43703358 153424524 291229936 556168031 253234364 592921035 971236217 482332150 599543858 758724593 704576254 336394117 386049713 116601944 320702013 262139241 468119467 889351537 616488689 911745056 633065225 870070383 604902706 570504928 142142315 591246651 866367859 980601466 619856228 51183655 861536565 350411353 644216228 833617280 358501537 918784570 492387851 985872210 88358039 999067661 222144203 536807702 352114740 518566738 492483999 341231115 663131310 45105624 330240375 634139505 567035614 261818117 617764108 617423323 970452254 802107454 196560229 270454417 511830602 35307533 540901039 374133884 77664614 26101498 166006117 975547748 953684373 519777458 645806387 734604327 509664456 39467987 313429500 261118613 706005393 785169494 72573687 28223723 121860250 738719732 565822699 229874720 493401865 535454909 160715412 999513683 215743593 589941399 994433667 505017976 62666433 751023080 35046374 551229157 23602674 695357464 515301728 35204257 844806845 376013279 867423271 775043966 627904275 663086142 521585008 522562725 923570934 360760065 749380268 582924363 482135712 694446420 464733359 299721833 368037984 171838414 638699373 792325447 545224713 382715956 607461492 55742279 350331982 683034459 538160652 98753491 242816286 379382540 161699092 964950035 649138159 898801728 231883712 821095668 858063082 991204537 156118947 749029397 215840513 100664417 253144741 410342654 68564012 775168052 337853074 105941359 742471169 580687130 764986617 90385524 686063280 112092749 484293271 616922536 230335573 536909607 95400797 166645016 147520995 233114764 355003239 102269363 891495969 369306669 892303575 42368453 709460375 462044814 984819738 939341070 49856418 664586163 747380290 716563582 746188967 748796007 690577811 738700688 932128612 966000680 680803865 430760768 647359842 241072050 598147190 582146730 386232455 141677606 458188986 541194561 557961672 823580887 810281323 191177384 3919611 208699826 610007716 101835312 429133258 546773063 740931417 729516015 764217283 253300088 339509944 17752441 396794253 227662780 449040299 887877182 554008886 106598929 490117754 333550503 792782716 454601870 312286703 969812281 13889342 378997840 701954274 582963040 537658773 336545072 200391988 149865349 87114027 284146626 396433849 682529010 624612639 647411714 39192924 154027495 570872239 543370168 141776598 344996297 277610879 474333943 679580173 251508346 248766344 2065599 606357255 194077892 829252546 795536009 443822574 712485281 188299588 178772560 560377969 267091769 104140315 553799915 771730373 667391054 220425174 884492083 837368844 640251898 746201449 977313424 736275596 579052391 892431850 98582560 113009954 494505434 593120657 969580597 304056643 350155148 645284777 697555451 162831377 734016759 671508877 389194284 766658181 963343032 257616863 239517374 563220536 79988112 278445409 644141501 732991182 229409924 570476031 210413861 79586857 507006531 671937603 71652360 716926805 732278298 448683193 208242526 67730795 730686340 149475643 223805586 971672772 264877328 139952143 228403573 480327965 19746257 672523745 786093068 228572914 295169066 371949937 304164447 968439116 421868755 212922351 585458022 5399986 658425219 371637513 661085027 225986693 874358828 374985690 114811895 579156999 554158880 259018322 975546189 697273232 957653453 539057069 238346994 543470371 370803534 448089757 768479668 831490733 352319006 96860694 457179045 103117017 859154663 37968565 271267903 62566802 245239928 102305998 679214753 413305878 946055382 384362257 542344696 168919220 25563497 783290839 723538937 712604247 212987786 171063421 120799982 261862592 197618560 57744349 576641851 316769338 781784963 484626580 355321309 247005729 133358981 201602195 59929370 473814119 858306961 127881403 882785643 113175230 260509839 440616395 629804521 599267281 327011205 649936162 112921109 265494238 772847839 314468309 975254331 691327984 239822239 203246417 415695551 848386342 666935396 120007582 879464143 569110673 150389028 962576513 963337233 755428023 266564323 458839339 135058883 982902720 803985847 254250754 416065401 704019495 195609176 648922583 521577310 627865717 589813744 652202860 247558135 17225521 212968499 989612691 156846432 818659479 296415609 754304777 194969748 405129055 432318353 495756826
