1958 8263193 532543684
547109878 459683524 249213028 663710054 911231155 107605785 167415396 858683657 768262581 833552864 528655034 437088802 246051360 399861154 314506504 197349288 296874826 1056656743 287347165 477908718 54538869 400365070 21895217 105988708 685134564 750789647 668787933 506171192 808012056 900776025 782512594 664479417 424966197 759665450 355817186 661174734 263367706 418647169 851709496 13686942 193266482 707691808 314112706 796426683 569084528 929101994 110904514 325042113 180525722 606057742 515712980 391442045 519437528 906490740 190816076 458106356 1071790070 6511860 16834320 710957781 745175899 84325058 810106825 864097237 954342714 453681975 57679885 1055606002 331277384 1765491 691618770 1011496077 737195613 400671544 156756691 1073253495 393408736 637663066 896535281 111180018 51304315 111000943 420123118 291981472 604621150 657352680 362851084 710563846 5184725 891126935 678008645 117862764 738069927 830491256 838983061 817425666 874581160 481505215 788033695 29560748 963192476 1058642082 892428944 160265764 700344996 332722187 360626923 962176982 510790910 778958972 439883845 841175410 734365436 114152266 599830916 679535440 990383847 644662045 221805660 90552667 564545895 928437852 647359384 485249934 63026730 992647697 136901350 907229728 31510522 606052003 228474770 30405690 298283406 459097395 248082325 863886539 253825688 809087770 353371954 283001134 434750622 976617219 769260477 170491981 655743800 128802852 1041097636 921703434 778271529 1022181398 847621020 839401599 901216448 250412060 775860787 479465638 291536743 301097495 747358297 1005293053 269296081 4586126 558282147 25164716 1028282282 76596256 843470629 647250136 529804401 1020149576 186539034 466588457 142817076 875822412 168357203 461269037 1033051038 166018135 877775742 1031850323 536244484 835345078 636064844 1001334024 165217242 81661376 918424116 210858804 126571707 559014249 403490188 950937568 683371158 280537083 707326079 305322161 268558831 921639724 657773231 228339999 477497723 172504616 144356142 869213342 1059779981 617625502 749060512 860477388 400339350 330864354 108648316 528696159 563783070 178004678 895750028 710408893 467123309 63403451 455163886 767305041 116529667 527005719 550441920 792569941 239375826 990078463 944384083 286166210 358524238 790386203 238189294 240103806 1054348521 854279569 529727872 300300067 907539704 338144055 704854532 213910822 779592306 378588705 394539220 768680222 768154817 846369075 882511715 364842806 993673123 12601046 115968093 505391470 468309708 831158039 452468314 252818836 1069788157 970645648 49670988 248085592 474892811 74318022 164850779 648794497 44191031 703443063 651202668 21000262 838964218 573498202 819997988 344069317 748386845 656372993 275395952 241543534 218538694 1056883566 1011721704 893623374 534684720 53279533 158467583 103196425 877481625 655613732 424545219 643130190 1043478853 99267160 747864525 55694788 290522328 155645049 13926611 162472320 514675417 540302786 975913365 918093172 522069987 549477129 459028634 571603572 122287173 903064251 51000076 369685666 425558319 6690158 631718615 372946682 413871906 712331038 222718593 158931533 803656257 374916243 700662958 123420962 409548589 929802784 422299955 167495787 175357997 463937042 880311864 953499914 924203274 432287672 144238734 350381960 915510344 633775586 888356297 125816202 201682470 895452198 839102238 942838178 643819018 235902254 43587682 774515462 996952123 616780891 45021349 977944302 194663411 480194750 369755652 615407266 306838400 1010669378 993689559 648293078 957788581 393008120 288221101 233447750 785597239 604798809 462935480 218301900 658487976 526884521 200243620 699328527 117449899 373782176 71232128 879428568 1068856090 395643426 446965613 161838687 817005909 303915060 290277306 13136819 806902980 149126084 487273575 491860876 872394267 520481032 484692677 572697738 416861549 164873689 708721842 936510696 688194992 564630147 211912253 337916178 592492754 762570104 699010108 617722111 581338137 348477660 970522496 983908489 612732256 694462519 4066415 463419455 461574724 7989352 475423401 649240586 523768666 811281029 1049663788 759667480 321686512 336337886 665945975 436294192 913583351 301258996 1022995322 724115177 206992754 784589134 847488586 1051115499 265801140 590109221 808164410 933575344 902994239 368430828 404849801 991286490 1003067143 247266705 694274729 8776606 949238644 446431254 306034414 567628718 1013256431 354540034 612878183 65772141 127605566 269440222 425719894 334204342 382001801 652058219 563069313 990658239 302549847 273860458 68871894 6497702 423902685 1006631582 28319952 948206602 173365688 593251753 490987420 270693827 365265957 633312602 448413897 1047822563 1057726403 971545482 694294730 87634850 329221775 705509533 65575715 446212871 615904803 34619831 437911681 251528928 426781582 293726499 1041312321 119155936 775795388 231068470 159862334 434944672 677220571 472775144 131387369 640818971 222146488 128381711 501320663 558054314 711942651 1001664922 532285191 174750498 331571321 476719196 536347210 445011206 994257284 414581794 508573003 504302407 389992432 873853361 831933396 894492485 713857620 516635197 742189841 397143768 897827958 931340841 867613864 55683914 908343059 381332033 767322942 993597784 342113128 116650759 485240064 95455974 192454680 537431006 127334731 734535643 363810475 976353066 301091258 897219042 753119007 876556219 237432163 298247851 301977047 686200467 686113608 252076119 150234696 859262762 376117488 160793694 242949743 904372418 759698776 672891059 180568623 1047047018 79125491 909663920 687231484 777855195 196207386 954609221 861939500 532943020 660330113 674497767 854198490 434627447 711873151 338190071 942263974 922909880 855272430 538173771 300390820 301399726 917003379 312231612 476613373 588649776 140593490 201215481 349930182 657376678 448317287 83529573 436200747 12063180 85581737 677435253 849025981 938500372 745909269 823306378 490364829 331114660 556622312 451854361 965732319 736900026 115966193 854948052 498044768 480759047 944545672 74073257 343848812 821897325 711569576 294220815 4151934 71429607 621461852 654688367 422201453 516912764 81837559 795914379 367290305 414875468 953625764 219997609 1573035 589980568 561430400 973444392 664024674 690777228 612861715 360315694 717717798 10739495 304070602 916908329 1067746074 151474821 928474647 78905928 170714942 738557174 695055209 926495631 495412131 789182782 472932505 381970497 1015864844 970033407 118226150 693298152 219662938 351443253 263228129 279057807 168483825 920641550 213740152 351224502 535058960 824273196 141891779 630634833 513883211 111416261 107472759 775393235 883513293 220315256 362051721 745123952 53078114 168998511 783241294 933138753 1024035323 556114941 434829619 106365431 445924448 318834592 857225572 240804192 2741429 796219910 363249463 602698725 385645266 463634121 509028476 245182014 169694152 846521349 547184015 450493691 77619632 930941670 727204230 741801918 653806659 307133270 228628720 541272587 267337646 158663296 294867878 84847804 482397432 849133211 42350981 227483765 359673776 47868723 565189472 528741547 2388805 99462780 292853585 687746550 239219987 399040519 980619661 676174288 690238529 855296580 173671242 734553469 491262856 423037657 253750603 364189079 636134863 689284279 256427921 1042002339 672711284 957307086 516031336 244326249 206089179 723200015 267344890 311669079 558649679 792776873 651484760 52611194 135947366 1045852852 580117643 212333755 803221932 132996959 531040439 797199326 864749434 220719315 226492566 1053777986 508551549 56192059 466623123 697946071 1006870724 101129409 113939381 1026432079 166558469 337675729 117933960 718927688 392069888 852538454 710944362 810977285 106257469 218968516 919620525 820247462 246874821 893001706 121320468 313396270 524227 1034683056 868766929 165077044 221842159 926751636 829340659 818306757 360669790 726582541 56502785 910127797 846674863 505913307 762967804 992035184 904528505 882173485 32166072 242476244 729484244 955255193 237939554 90438335 361541441 838960496 599676928 441928348 173645573 203988193 962037010 978803979 193254448 568723215 968371171 177421189 1073499269 397814373 228738830 188108871 592762958 982703158 887661174 273851198 742545119 538541022 180618218 86332355 480413025 429613005 27414954 942071421 31451507 444910438 612688284 803958977 59611229 670552215 763533279 245197081 135665180 1028608425 189998079 602780380 836818975 806315265 594790284 289098524 25171085 19421196 112683306 760737822 285279573 1046815092 826640475 487784545 956316863 586657646 906178222 564974213 181262196 344696963 337443298 602984516 705331204 24284856 42444633 957993490 1025211613 1062833331 559332406 673409413 384438807 968626078 615001118 314268162 850411968 503202800 317200260 144935721 182672778 661312608 74310231 620679488 298720272 262114567 481807304 699319012 69174797 619150803 1011976993 313840975 668741369 37271245 213712740 373698735 634317129 193366553 460234952 339981629 741676233 691289277 313575680 413652004 402757498 390664770 861820891 437508427 126852968 235670414 735509276 83090736 424665799 146806766 1071927054 1063289668 304334678 737937952 263248149 287364858 167676336 838299006 1072871127 1006619482 390700684 1053438446 845415289 928738903 1013244355 816878755 170913079 468940573 940343219 509743543 660596222 383278274 134992545 942034040 400907066 896835812 678487921 1045833245 737573096 375716638 836666349 603390695 346654357 484541586 800234949 129658480 310400892 530970735 669296399 632908439 346268894 1004131863 945888281 644522190 306051154 328688628 1000498791 798385406 486394545 621805065 701092915 500354265 208210127 729246696 796632577 767327668 88275555 725017414 855270364 869550260 590423752 530156417 238324939 991621794 1064159656 1033936266 512563267 883347659 581365110 530324418 330340741 1025185202 110506487 948513387 994612320 136452288 149533803 704566754 542068243 427754557 898004701 433725363 775896655 141073766 965737497 331175646 541422771 876868963 382663646 755874052 178086394 998157471 880142111 357210856 900904933 179330132 447960184 978611336 818318429 664515772 53463712 614660181 686501528 608318366 302132582 239673392 66302671 754200328 535411104 682344910 640812253 72443682 3078468 37043513 595619718 933656695 153176989 37822547 452919975 926819077 644155204 439879739 610545363 163053248 621047064 388990188 370708123 855339024 495275529 450380191 441472696 307747202 77383466 413042310 247365547 509425470 550515052 106183770 832251130 585628709 18662543 190308098 768263019 532272501 226065312 421641222 129789886 86621348 219880318 818248063 810161061 609645881 802895481 453638796 601430279 321220852 833596672 320474239 161869687 963961201 379193121 334139650 1050172217 172548951 1025827452 1065198541 405471631 140026878 153958117 150268550 1022625621 216155909 124622819 503109783 527245402 901694144 685639226 796619929 13746111 399266749 258260944 991143526 483252425 903732910 569106137 495502845 25840557 762137746 14313069 416313127 100690565 8618877 117032217 1011894808 372281056 394129194 26896159 963471528 832979935 530395759 219612040 411367566 551385984 110604457 143817768 459887832 373884034 382270020 424964249 936189877 106568627 767449050 250860863 902346714 291433444 246190238 141712874 469505315 374375361 202203457 350889926 840445582 339987389 230675874 431854145 689639917 937242545 1000544264 729284345 39613203 937453599 13549565 544250826 421545387 824442860 765652754 484742399 146457264 764185770 282674964 239797866 488956070 776639930 158193689 776772898 348079212 522292628 296906218 741035330 233070495 657048496 527189883 649970811 981412143 290354817 833492934 183984684 950177221 81513984 228953737 623846642 32361871 644290644 104996335 837903846 70429244 724039591 232894091 656183417 453124763 382729531 124270125 79682143 692972750 228779509 987170436 157147516 167050310 1011546659 513122504 683733538 527648569 407938971 1049189449 707715673 970013657 615630459 772953540 190691489 627768896 385551549 328557605 989857587 798274012 546770249 140262396 533458578 579354963 229108290 421128961 196060050 388398681 94894149 411487440 566851623 519570104 927705400 773569307 198820780 859189405 457668513 675207917 318804668 601417771 591680446 936669057 292848796 157700159 943199102 292387840 384976857 203587147 670132044 82691020 524188601 1000492490 541176897 371752090 15883005 233276967 367567228 334844703 757155423 83659033 80959500 964934083 519932034 57187927 424398034 183860821 1073664719 175668449 171005829 686464723 1029309665 313195340 97524661 63697343 204118832 201208697 565387085 226368642 129056072 1046221993 981163302 685572206 223735616 405956524 1010088740 11806841 396353540 547643494 415380814 671501662 76760527 321843673 387871725 759062158 664992769 258193898 622855915 927192370 871947001 901640909 739809310 730727816 50233126 234062738 823773462 312548717 229995411 876737252 811452776 184728744 971120334 782012904 189924578 536011793 964004170 405201914 382738653 312927162 738605213 665200217 721314954 920400493 720185217 741126496 388304970 983432751 52049347 757523321 719486178 211322928 434676985 588980505 705646369 620345134 1064299567 141667193 392500669 221137299 991887505 286353498 866476250 468492262 19980423 63892106 782108456 825756289 258079430 572351822 240898023 301560146 195100966 457273821 270865870 234095428 592052113 280729747 994797618 887470402 528334354 17869341 351198011 539847096 284507989 82344169 804570893 1001490333 115374571 789544337 1053449176 1017567709 194628054 885117729 365343244 950543356 981799142 144410269 832033730 759597268 289668644 304245449 1017900532 811622389 116798486 193535870 156221213 620138742 803055409 632843756 180747459 958927708 685388125 320634617 21496860 696420977 978387747 369012918 67711815 218705291 526742319 89340125 948060780 464833411 650670478 527797111 1001081710 336747350 931143397 605467562 557098125 264058149 551842935 153616357 355386177 148520870 525312569 841307337 985086360 240213393 239372694 840898518 679730113 218432006 945234829 960869511 683639932 248546500 176729638 81046556 37395303 466136030 624486434 179175414 763927769 34202737 42003531 765372854 28504963 638184347 304028977 651898053 314868580 865159588 219411690 603442249 8994331 507149890 704645641 973237662 364323637 852368828 550638827 92659841 603834018 804776801 774298686 559495525 96250612 772333307 774615824 367475145 422120848 95297935 708546073 59769132 448481798 119766594 303593037 242646843 188738561 627279555 711428727 286755556 765843018 149493433 899923212 279371796 172181618 198957802 568454253 5874388 58200710 92303843 812043965 84751018 901562160 654011704 949198636 396860578 368384915 941556933 993113045 504223764 771469281 4950464 56392790 2149035 446328965 49072968 376345759 173719821 361832442 772995364 313143966 308041295 545149753 466876418 194356787 914668310 238817767 52395429 219923533 189751793 504849535 353215632 833955391 1033851982 561498410 138004496 511637352 963040257 191265282 931789859 596198368 771533541 815902431 1016177377 253434064 620063908 1066439036 962619055 118937574 285932033 851476604 1050455355 127695949 303698566 968102751 1050653468 616471867 72257497 574435735 1016568668 1042914754 147925820 412354967 550202214 633524715 58537020 447245217 443409265 752738280 951321995 928562060 252010303 729557989 794678752 799384576 290336251 1022348448 543149874 509154948 644640827 427256689 312086551 228561421 1026931095 1016836931 477793663 370334020 877363244 391400623 639482887 1070424846 696624756 342237742 760659285 960927228 636287975 450757243 175852232 392677218 209623229 885691180 738935916 1055660461 477303374 250399217 475967876 109938819 945381323 613901013 169861063 945935933 652901846 7738966 615775705 263985451 898858468 447793774 520736957 417774054 415095919 759640704 898833053 140570314 361895411 563373318 113442041 858509400 677404643 700058544 845994458 1068374415 984745677 388451306 475358183 440240423 659419485 167966706 894773894 339278838 561488668 169560051 421363766 950123502 768567799 290533685 830347658 580459192 592589924 523552479 995788055 422604871 194870549 57303644 386235365 37993268 490542223 249399203 498343093 421446680 483891864 479265769 1010843238 10253648 309865458 654966095 240098003 941350557 383494395 555832831 50210648 88467102 162860134 1041164169 388059268 64475288 966804675 121176138 608305754 929548697 637915943 885655101 279727440 794690402 268488161 605216204 69873020 69386491 458242824 704727028 366445542 998296640 602955052 622377037 1042767194 367524750 312884361 652500754 72625672 789408871 314827846 383785400 320543148 1751333 656395398 1056024971 109769245 24560377 950102205 656163626 153855819 362948355 27958459 727014066 854977948 688124656 318476869 6042387 282853890 351271974 201429088 916172265 1059177266 914998393 300721493 373518708 249762592 21363324 613174033 379368281 973378131 6114158 1014843712 561158278 1064735650 706627016 403740896 339011514 86476865 531055073 987659783 519299317 780530245 641614087 818455234 534699362 949173602 903104620 903717393 404425675 310740120 90440767 85300069 124081261 542750666 454924660 1011689600 431678469 974830099 669702985 84230051 773058306 247505777 32643513 965705455 148434297 867730482 357074577 589712263 717838368 713549614 414943656 490964962 210962717 880123321 307865435 678427692 937273127 677219209 648759649 278719068 990774557 629936110 865514886 415391272 327024098 64320057 658080974 950154306 903508659 763197624 842359837 843018011 1021911178 147785764 34764708 456047883 555895768 830687991 403150516 959035420 923177554 582250815 207055302 675145249 742361671 86112466 663088058 719901250 201530508 229656075 155288086 758666072 339440349 907219147 365836521 497924467 81903710 898959547 614926950 79925481 74797850 201371162 1007821942 73288128 560327725 748038300 273841 1046216651 835715256 3677067 606003404 350240869 482732610 929300222 864611341 941953635 731706476 742728253 598727858 517998288 769086830 759726096 242911562 243708888 548824839 262910008 110425428 185892433 399484206 957753669 690378029 339291380 1041918535 294617642 629671879 84391949 732432757 360186887 22937108 715160659 386349684 4196778 189971058 881531778 493327351 830654091 951597227 157656070 5521764 370677683 919444301 1059104075 996822486 842101870 92664063 416853161 993555876 788862406 111361244 616431607 459535620 614250932 817103354 115474578 354457918 378953615 729995135 506966889 301559062 906203744 567859632 764980237 916049029 985241052 458588205 250658686 747288558 745725018 158532378 146309921 25659014 869761951 483747475 298551295 970414090 1055179169 158961797 4111259 813715601 1053509444 144484416 14191595 935048602 212263272 914275434 293428149 846674289 304204251 3312729 597276544 310702635 295376295 488617459 376323357 285443951 1021425005 636995114 302890703 910372134 125806316 87797186 124073385 455949540 718139957 120189267 467906820 74607597 226512426 299389354 507374665 269316645 843141665 845852074 997052250 479343204 462377720 722775817 65227072 664332967 818759759 695231369 1009012548 433330141 586328429 1065985286 864187011 490455361 2220806 994332650 261680394 31780416 885453584 679791435 416665321 611610563 45534371 640845355 1064495876 766884027 340951392 920211699 937456461 650713525 858161881 618116370 246641670 555435823 406236287 40842269 269895932 307920611 250842693 26638332 607990916
