484500099 937216632 676434494 323069930 277432689 922893610 786787226 650065999 966282804 318459860 1604208541 1176972230 338885191 1292172630 106406696 91768049 474327986 151483901 1249049738 147600895 520105847 407863316 269839426 808698655 315780771 215799314 738872515 701988730 413088544 1414204365 161942589 187429545 391447859 889237853 1013782991 916667656 762004272 444122106 344313399 807263865 167930844 737172716 795688189 459631535 310876417 475007627 85387087 818105800 532957574 272935776 1167206776 852716242 365688979 964505062 902405708 891569011 559591842 975269925 492469558 693515332 409380338 194486084 1043307003 326817970 429277722 315683357 911297436 184874451 296446857 230470665 518546281 752073915 726269801 814873798 565239282 453306696 1109393984 127219395 569755223 438603431 697139443 82799926 496575795 231574361 326981285 280332777 809473015 791496072 439017371 704241191 118783008 753798133 689139334 173434342 371311549 557466043 345108039 430153810 466586751 915778502 574280293 181796652 1110571494 534560804 1045265243 30448941 809406302 223889628 511011553 198739418 198152670 172196696 651300637 416060945 314445684 959472310 403949602 205087627 1517453809 783621036 474440621 691767679 375990648 1231601912 686454758 1059598119 1267586903 563922323 778844684 123932070 439718204 281551197 605803712 170688171 410070464 877068944 39759391 240030164 1089241418 1473956409 428894302 1108256772 964242866 474080038 811299165 591805785 1076393068 881351312 229898266 398014434 932565586 694239644 219158194 1318022320 397899057 54754683 87977637 317892823 1214913526 637130708 739999220 1270017620 986272908 1015063262 626671274 440561997 289158165 884636595 299124842 728435104 917297926 700932581 701514502 468689427 468085407 413161818 944673364 488071619 285069310 269548366 536092568 345694058 247452996 693807826 636012743 402987751 1509835372 340608671 412908462 145521528 418921481 361055212 829307876 761027835 911904450 416530013 873300656 975132414 866883756 141344620 495738461 646888824 783234865 575567896 822926787 1187512719 877899796 759476100 887160229 553677081 207325473 604849406 533012900 305779678 474673314 768668328 207515866 312740694 1021359675 337498725 761106772 1186711305 165037939 383245011 275324096 633493738 730833118 735353178 894718990 861805143 464022399 1257254149 795187267 602970205 1523963453 439075007 972549768 171249143 256296064 168381369 753555669 353533438 501992651 126387232 49406465 789082284 392042612 790026868 793269664 883750568 1130440658 752280289 630131519 1368896555 491595621 294034107 402249125 575070350 609873021 327273671 1199895025 365374554 1049446849 871194719 95255855 508639118 753229665 571066975 520404325 896792506 316380611 708299933 538729006 111930783 368353755 430496995 541313658 497794190 38911951 508360887 181035334 1087962958 546279835 747048663 741271226 1352317617 647014396 920701754 216171953 855253825 527589648 675347027 371614756 1059422170 985802176 624245471 252836860 318734921 508967808 1120014987 1554703153 277030857 902603227 422313356 424959918 465141850 474176157 413621320 466975836 214507754 365603884 450656046 328531792 121255428 500259682 443640746 467903018 645505634 916033222 1158545279 283642857 211627727 1090291769 821844199 71240853 1176168840 575206709 520872938 699972505 948698520 370313905 473831679 568619831 1295670594 488962541 442709186 760901537 510996245 743812033 694328811 633499036 605210230 182988625 477733028 1415135031 814781230 154310420 87764603 481707050 380217269 239266048 264321208 381378338 550134157 1178057601 472289544 792217943 588415966 678371026 282395710 831158498 1037860995 533864038 590463433 1643980306 615865986 516606817 1377974681 995399371 280912223 544893279 253519522 889168931 516565831 277802888 317128802 229314716 333654877 387163946 990926999 485428673 1270647878 756808243 141433510 1192928131 551844815 681717804 433421478 93738256 192211178 605445162 365781700 323578811 931468987 346348014 1298359318 365681067 468049977 1438220974 1126526629 1012945512 460692464 862273950 938704115 782110138 522967582 456593513 454429071 383442848 278265625 694288001 136275351 686345622 1343342064 844017363 832895847 395335301 358212327 516002365 671245017 513280445 211535572 1166616245 1507758780 822552849 389929311 755788518 296532245 805783717 542148150 726038303 957426031 639174697 528108511 275512808 908747903 1193462303 518311598 306996243 682452441 295510920 1340734715 764896687 842415112 1269454300 916558797 59384135 1186332971 1167283218 161762876 294705334 299496100 824552684 641797167 460793902 815952367 957183516 1039613359 502358810 300608497 1389752877 1048140427 591454931 373680604 1256746240 179897856 394188095 554077519 892142049 257552815 506635545 421338651 359076057 201029663 261385078 623652299 489893155 562158338 307804382 333239990 386739429 300986556 488554170 469051727 184096253 388349577 855719111 40819934 402227234 234027055 727873064 225659309 572887756 624271492 738616501 674481548 837704190 615701968 887989310 665742028 1122760641 718645876 1333087461 566308704 715190838 619622249 155463039 395271110 338296654 698213343 846766825 1054953447 910679602 115277674 481095846 1015280313 455206882 871019746 88770427 414861504 635552688 139782464 621588752 858831794 388700853 748114498 524011013 668679999 1120936249 864408712 243940670 85058094 313680616 570418807 333004034 449030432 1263587588 695728013 403623112 371871815 882623704 154541814 147150464 570745654 450869134 487930552 932774487 777197982 1175898935 1230204322 1302215052 415140424 464156036 530753203 380038190 248472363 289167611 517504598 457598856 1136422897 573736017 628840953 1170068700 99575963 165967731 395130780 454307364 44436795 1089032960 932914695 1170379964 88048931 294907126 392773550 627432010 633174050 1033224618 85748390 218944096 238423322 410000406 845606780 1361856593 220366492 568778399 346031304 661583945 761310558 1045091297 299977223 914995346 281812881 1022003137 749013584 139457285 677176564 1445325523 494274885 815572441 461528461 1317162034 593428831 310661897 962451867 500943114 347232911 659093580 486734408 577640824 1107345468 445032369 421507620 885703618 203792050 921258689 846657743 230814573 891917870 213383949 344932680 505357839 725947804 895716076 231429588 450206669 598525476 556059665 984858136 287542149 786669244 225545514 651892604 795374644 213745835 1317381840 229519037 323559342 780772606 1002359274 757482376 545009916 1208699522 269256046 254373352 960564756 887861370 859228034 156081347 1041812431 62322814 284656032 478204539 720064229 1369886933 904730429 1334559117 627205213 1474764628 683604193 775760416 565683189 1239035976 175584289 159224588 795069641 1102201064 507703027 1024071772 579829795 952426447 410124906 943968462 829823904 692251032 532333036 412120734 442779541 313783406 581685044 856084126 253901103 1169228779 378417142 1102178999 598838339 279173387 415539116 556981845 464546574 1495329218 467063274 694312089 819154868 166868880 65243439 342822549 880508515 133111104 518869126 192860056 547173234 742061924 658724391 727983728 134857379 990533186 467425724 586372399 891032041 914308195 863088012 917744814 364424801 707482486 1199799093 298712129 946687728 507413223 188174505 372215647 564698890 838788247 748937259 573530155 394554345 427816063 145558740 917514880 921749552 503841185 51843157 120028822 537405446 1179736944 781012700 970372086 802258199 1038938100 1138609662 622191901 294624378 284527239 970384192 242749953 762220671 707030045 222087388 308968908 922759236 143950053 629710299 262392886 169862505 251518679 411448466 308191312 734856369 259452103 472734923 911669120 1358793702 850031275 545168299 49196030 336512137 932743729 586940600 493513467 351985059 463627043 265211949 147029874 469678670 279398699 591549893 270577085 318610255 74115096 690339816 370815996 810003093 160767760 866227914 358727941 179956522 165693947 479920846 190333555 1194214985 784849951 459787100 129088208 942347152 480002849 193324274 157684552 752492383 346626980 590896547 167631653 1768982617 564177793 403821928 513096754 960650988 844977394 785264131 1255138503 1095743700 320927131 480653176 566508065 300692173 1028611970 987191068 237423690 117910600 538316276 514151099 1395412848 553182531 261694058 149698839 751844180 232007115 760291135 215621005 568966041 788400929 470516220 196032511 711701113 428162041 403716544 553499836 583536187 232427129 1185627719 39604273 391665997 428149875 424826525 587966158 236059034 944477266 626548988 1037014088 690783769 1100484412 227750435 743989189 1171639504 768762095 552286450 1234457286 546520555 351909148 159509396 590333536 910523404 515268898 491984625 924886782 1211406374 170954348 813925154 740710371 677770626 727075796 1020569749 123837105 765570667 354439391 458352988 872283051 785136088 665925120 1101215644 697795007 551334226 372831163 707901480 647064744 750590125 181593230 808605725 652932515 1186281005 573127670 560982633 327874327 622236083 285719579 1257724945 640413223 297568592 389841314 951894063 492555490 316960684 646412860 1156793865 1584656647 631533830 396650660 172711467 159309642 278113483 381201089 469206775 512281857 1118091267 908897549 389372128 287533354 750377534 988291439 684323549 598042491 193757111 619693697 1342794641 129723762 322836708 81100498 662487559 167476369 367350458 912888273 892933632 783401838 377796250 561057550 625291844 207863876 164790777 706016934 370452636 517136158 799666333 179005429 1011382175 222316024 807603176 415349004 1290402108 689768856 712923357 353650235 775752075 225651155 21426978 1203987357 673739605 1038844288 1199474731 496199343 698078880 593122202 200973761 207092211 718699132 1187287950 432116213 751726814 1480077196 258815455 468642636 704170710 66672690 724237531 815377422 313910824 517178955 551307268 255379690 658797522 692576309 51999532 360275555 680156469 337188395 917758104 903399208 525644411 353306102 719141636 1282643080 533549705 532856843 594720341 93579506 901982981 712963465 296734916 1016882554 158927729 474770864 724435621 510600013 1014981630 667600599 856087363 156173436 350755402 767035954 1118972638 163134350 1355133043 774110504 495004908 127863555 450483373 178733445 540284467 752026734 281079063 93151404 475436847 302629236 164362243 617813446 79408826 143714432 1469032450 764536225 1144790343 359766245 958987630 823619298 279642405 654027105 698274439 458764738 177980123 372042015 948719755 1258742338 628887311 101689789 37492816 79423301 367684381 258904192 462590476 551195293 1230386339 746395301 277389565 1189388992 627576055 1123206241 757344762 1071018172 485779233 1368261604 854709270 999822117 765581120 1114644000 251641583 596841953 44625888 465757268 795388745 456194412 164652620 72559445 234891334 1066790663 689982012 592190479 855319743 229356159 583355396 289600669 359271246 1168113957 411919233 506933269 423374961 557551984 141983397 971614313 641616800 663288809 323543825 288378940 813237108 340808663 486207685 572311447 738660260 424907097 576240037 692016510 398847270 545467570 431109559 395773825 111338637 465460492 1219623671 263561677 539475504 822342374 616338615 1138216259 695078612 300412551 704235565 520959371 309773318 167238452 408469900 752367868 356695466 1319930293 423420201 514758163 625412999 570033455 273875008 997399051 664822049 482120610 389592181 157284362 317943070 812178817 469417425 1162358509 767984642 558557376 263303692 419989660 92301532 526327299 239527441 1491590325 1379413551 847316170 1371862505 1083895908 540964971 536095342 906138406 326506305 989387371 602465595 316686983 999797016 84663816 507786316 309494147 649658143 916801826 1294396351 951518883 631813302 480575812 268605726 486518914 756171330 256393432 252196157 404598221 340925641 530857123 853405565 312662503 585834044 1072652231 274670397 942938613 229290350 212532451 673456458 769751276 356432710 362748932 426940725 734424857 816222997 1034429828 1303671552 71084447 1038811420 175746782 869561920 749067610 434438664 889911336 628917570 376186725 652287302 1270622230 430763293 330770893 375144393 450253084 492761504 544630974 693661689 468150580 391844486 289328656 584887539 700300664 777088122 1017751879 1008402006 626329866 484720569 121837487 258502467 267619306 405375084 430758290 472774249 749558035 462223003 254221303 34611086 1348701268 639493588 620476218 406694624 146694703 1074119775 178966202 425626129 935357958 880822579 1447845623 343677910 1175735675 1122291503 443502968 697162082 355498274 582770131 396754342 147266310 318734883 502660636 285829718 858505775 683075336 552203659 947013739 822302783 615285177 742800982 1060283718 76701386 459988279 935134196 307027193 818602321 751329649 617571632 924407799 997855498 823480717 459678030 619634903 777801475 645625212 1276851686 530656015 393808055 1110488324 706780172 512139341 438277471 546260895 506484079 1117990232 267790694 455152719 1113219193 866144261 263038548 1218966345 599511284 575376338 513487387 635736728 811676543 259419762 174573971 372685853 425855701 703241412 429857218 647775462 372229803 138484285 456149719 531526111 403980313 721365757 650554977 255421389 1051906006 278609604 823839486 337603085 596077443 144615083 503967116 391996613 515074013 570718887 621182817 556411938 1231498747 707861985 221713921 542574840 741141382 913038066 682937693 331513813 1079357596 434552264 458286763 592834383 493529475 293771274 172980163 1094155558 216762323 805777090 335652404 375299875 423959939 392012530 592263390 512281125 574000845 662769137 494646039 1013568290 106823236 145912714 388533116 196839394 838865441 231602913 399010041 664336898 848981823 463833816 256575742 945868747 916370902 735205302 727266482 204085789 775802421 748929862 319198534 339735588 598275534 391749537 427875517 563974210 880486630 275861522 164666498 843827556 393821664 706317600 360253057 612692489 821698152 373720673 1085071632 293006031 370145186 463628884 418971738 223167760 254934569 514722585 127351072 349481057 471335863 609659371 932874899 494950462 1058629301 172648545 605286319 831598607 986426981 306952217 452577716 743929258 336978512 325963952 113794144 318172435 246739923 281145690 816959879 456088104 253545503 369697413 384535816 57397637 413081443 550024318 383117366 229363877 713140618 488980794 568981892 394296841 579300202 753515294 662434992 836534633 65489712 289692781 1299183797 520073041 1007249819 490565435 792395373 430776951 840424354 1000463043 1053107209 543436282 367741603 553608659 639033121 1571792744 1291362639 420771880 504942900 927248340 867682815 583028432 926109232 157514736 775824833 320942619 364212916 425966158 222268006 778413636 566215694 787518762 907430517 1128943113 272468220 718237939 1184250813 969837963 476234281 685572933 821389416 164026247 628640968 627351684 682244053 413234079 724686249 594951919 169877144 738630774 478714504 198761121 603634813 1044740140 1090808568 523621297 656380802 529650170 259989133 904765094 293126664 567747747 1022258741 544543116 334954064 1113997500 744031403 757081554 892111973 757380059 523354165 211338407 570840813 380092150 324448797 441284664 101019930 995784373 124555922 432518664 201938085 502601551 247017951 442765698 425954195 601845308 705512313 395597298 888969786 930230464 194716927 277496584 172705098 465301769 361571321 255239498 867253934 1536335318 626959270 195736051 895177607 1317472666 246675799 889497105 574039793 765490344 626511662 958048154 523135377 756351173 561978371 866210999 180001759 145253788 182877325 744169263 995274134 877668504 434567526 548827047 1163296367 958947581 560056662 387687093 978994159 354720741 856961378 714136947 534171096 732798064 693513798 602137511 1057140706 539071767 606566174 260480368 216760798 866354784 709617534 871061235 788382890 1210153266 846488770 1189640604 326948533 1250029511 500106852 281214125 470415342 385496002 669760843 960536303 1025233010 477434069 699484897 817604226 240211953 655358251 149430852 583531576 917900338 994901765 699050448 523760291 460152627 539027038 203864577 373214252 410268353 149842870 516961996 688223682 373303064 193477453 490573070 662525984 502898845 885835402 516083964 1002292551 739449886 649904871 850172790 1148604123 438590859 257018017 478054565 405919346 851967899 521204966 117292573 270288945 796177321 313413754 527250272 1105809784 256178997 1095660060 701985357 869125742 1124793661 741421468 508900163 252119912 455550353 549442544 717261100 911686886 611523547 1209074162 573853857 309910933 1235580693 670943861 1030101512 1118544696 895936499 369205422 655102741 320574564 176978867 802772454 303949559 665953110 280214977 71854297 697812661 1188720722 699873032 627946571 483700890 308743587 1351325893 1059995763 606177162 784089007 686142969 450994933 1084388150 560425796 845255969 397574800 328231662 420147828 1192460953 672038434 533338257 981041313 673814153 519241286 272138915 474205274 507277282 1018417136 575615977 666867808 1385165289 555970410 446718394 157978099 82825831 1073662320 730562436 963828051 469469868 333104026 495323022 61665397 731817224 1163056684 892886117 458083822 1254571521 1031336363 1154067720 448271045 437626299 349502708 352143492 1365951061 365235955 661003395 719976074 617357547 759539780 836728679 598960948 282719299 530083082 739510646 642239113 456740242 585569452 650896563 929346360 379084248 1555589764 622186508 611339595 845958451 863151274 1125140598 239768466 332733648 1279512427 675128861 437710760 464048945 114281956 441345417 373453661 918674465 1263565947 587738631 303031621 215717222 916035035 210315815 414668436 400793200 458712429 957114781 643818842 1152279105 1621771921 1139985679 721052912 511628875 837273207 41538972 164108713 607151205 561161587 966219220 605713531 913948132 619846452 532990043 511223109 262609016 826500945 416729063 1241081979 212802366 367807361 453489325 561618578 1185735165 1317619769 896905736 1236676556 1058857431 305460029 154737148 632685042 95611970 724140168 1109106589 430228011 384474893 563265002 351458572 849518209 979340013 587532520 763256086 305744590 225473354 267107951 546622907 588080390 248221492 630370021 280879592 347003129 368022653 328846906 494524383 934870764 1527457757 939794051 226510964 879818229 567881064 1166501787 78871702 527631735 285918968 732645839 108250974 316663836 719836090 1531965338 925513560 636658197 570435426 575349663 1513054151 703707921 390318820 974953427 730431174 166948970 493209892 301071290 354512947 379596956 461822304 281757020 679305321 629123690 1564062900 334564541 317447357 1208332922 671451782 147886354 471244665 176750208 728481954 1573419443 73864886 581880854 783331168 597117279 752120015 225543353 952070719 396939655 768049205 719520908 641726970 451656400 483632287 178776520 555422381 944773943 199353834 102232430 386685362 648667742 110525579 340650511 1019383502 322056084 694427068 906545991 536910384 424464131 797857028 521486090 955096553 638445100 193144541 1133904854 988134000 361170221 185031951 240049943 1063707557 570596174 175099153 135589238 1375547057 1430374316 779621505 636731744 667348068 569918708 793472880 364481121 434944171 740284243 824358730 671802488 200962983 1160982485 207524608 720048957 380732596 1416447438 179271239 296526825 333452988 566538913 29260777 205307834 873766883 854060123 273088488 745978858 307397143 217215362 451979138 754337186 404913420 693629300 713879804 1034042322 639509014 1262231936 254527948 98404739 612098009 336385006 357357968 305252637 568653365 630323126 316879965 379057441 356157842 418518990 908683837 237582669 284359026 743196020 1038445215 379774042 760037634 516952778 858782317 543391975 92129951 813960829 566263813 759215416 984035774 1071825733 710602998 310764190 377629794 575168690 468915216 568517362 87637766 375338541 669549787 260780336 390346367 284365736 735440380 211374726 343189991 707778764 902554147 250400568 314662424 921958158 840827452 584529097 322652115 789930873 314767078 760258562 693391048 755448737 1392822986 1248472638 378606095 749712125 439243309 668172525 594223477 482432203 120090585 1045457387 481813777 257780433 1201298286 611403926 517170649 540785579 382785594 659758262 716396278 187480738 1364624609 872459098 180289413 600570116 218894583 737258263 398842717 296518428 977581888 451538934 327923904 1000612893 965536040 603573997 267589642 779050064 24911464 814998123 423423919 973462424 377647785 1072278870 395597368 678909691 535524610 487854777 115078196 219722079 333195303 933922748 597841310 548893244 465050865 1007954575 245581134 164906629 675372939 737438326 631712730 410427609 1097364133 298487300 453827530 1126292139 546780709 605589181 429415244 508905862 51319510 917463290 835491858 1221725579 782827225 522797744 275288906 212529600 659115619 407166840 705213617 117344189 692518749 591903901 784758631 300531802 461180806 342265773 891933134 208484845 395041096 450683871 108588417 43992594 137334427 229292159 835463338 339664997 533116318 614682592 171001627 976912552 413998675 838040372 703687729 648710066 328607540 484315247 192490770 507532626 760229191 270623193 580285561 721975597 463764719 660083080 286237153 1000555659 1057848144 660664483 1050650071 516201212 266505852 627405274 769122224 553629729 433108043 328996781 74551939 1279016536 491264346 364331284 1625904221 487114195 572755094 404458734 49864303 920341358 1430849350 451509152 829130823 867527244 305902975 847176310 703806709 113711647 580066464 444916762 1743237854 860590445 253227726 1154226402 655902874 530044500 618831881 692317568 1310050205 1022314933 314529170 574099563 462456286 458349001 444225821 879597189 210263551 298977595 843367773 96826930 194575592 607931736 562629798 211998063 1098443919 420874764 830619388 244409118 425031977 289537800 304808909 337430321 159998715 777311840 1388683816 163564060 699341099 522972357 330156733 1102534258 240034943 185250424 741203575 425440550 426459150 459849902 388680283 717611832 608360835 394039286 495767327 793592870 569015377 334926237 290797413 527110001 752953561 603345794 447095685 285678184 1439706995 496896987 1237413792 560956991 494024602 1279370296 530665146 921086696 365252437 425183832 1267291908 214046252 1420473619 152035739 344425778 739083639 422554386 1425824473 508241148 900224948 1219014140 649214937 1138808195 130478236 705709644 1036815262 941560784 509411474 643400601 613170607 998074830 942600688 513260758 913652801 717632182 275255328 197528019 595848779 834685225 484580931 649029564 610686124 397649427 625869835 236485281 599455874 283633231 1429913940 363284934 514454570 777537444 231042185 669675146 556350222 206902943 710626839 657882906 320703939 447333727 198505756 243168374 749396471 754063585 1078593024 221222893 946549253 989956835 554502369 951794567 492761892 389103966 1265997239 797436764 814422021 484898299 532411290 506434603 1266578521 791205351 56295775 461516135 350082001 749435702 390519636 431872838 619558899 298029737 1343013016 37285570 1102049276 574189511 774887440 217705572 35177107 459323575 629791283 819715988 209467140 499482985 401406848 420979011 655221268 309149496 224952060 999614762 866750662 1066069419 520479804 250593102 355053240 583323097 1180076992 512496812 679818463 743628527 770790914 393712267 785986395 275401038 195777615 562151075 1138400109 169531019 153198072 604754381 329898532 303716581 1037412951 824426011 763963813 504392660 559538850 573468475 354693209 169004385 1070064988 350263258 755730098 565870244 1128066364 1482632713 618625278 128321701 861682916 319357352 161764999 227714781 770227167 639813545 301713848 554437123 856645841 808032773 559290128 340554632 163428235 869527867 864247692 555683127 562179429 1119554584 338108349 501526629 996950060 430708199 617478091 308505203 521323437 800566759 271948451 713072404 988635583 1409037277 408229379 608113369 989403514 1453876989 142470236 555112640 212066271 988387886 745374977 258977693 892446587 876948101 1391875856 720543578 242693759 221691780 295094087 528918907 1360137257 837564114 1008007460 323730202 295244229 612210914 815177471 139098186 39293381 334721758 571691355 939614759 656692198 9211716 110310904 150522119 485157188 466363815 708440304 272769519 734515557 1109575046 1293252236 639123195 397727569 974196397 490712241 260746875 698206262 959170880 381472524 321827062 872340152 484360121 1117111006 394648263 180914615 552368281 970490752 571682514 648729674 383070467 148542011 391332256 145430911 259805812 848495824 728293445 708706717 736456263 580944002 282308188 561109179 262383840 781734053 281556710 45163926 245747947 1104825166 248981945 480707501 178958508 439065637 1280897135 582374985 718427125 1009127053 595256607 437115007 231605215 118412744 464665379 852748219 521157238 734391880 1034872665 143046283 718866086 507903806 1128553925 209619732 145689029 169191855 427841457 811782702 217674594 230043732 396836754 126785384 702774835 1059503577 218384187 170496983 441005135 954242765 196567060 368263590 315547138 171796281 782500414 504487665 728973919 290890806 827563415 664099158 573495347 850807213 473952449 394134249 743741585 980674927 494405281 530872444 907682766 202110380 1160445262 1011112910 628357347 278029549 335898529 546019000 451007370 1173909014 866739714 557890204 103219977 130091535 922401721 359186904 912882002 710051245 846952862 219312660 43197526 209394004 611405962 850039031 166991898 1092124164 1234559796 145677376 351406060 360874008 806565639 866505363 484868330 640225285 772064810 545326427 549902903 257729828 1044194408 284394583 1297196319 736411385 718721190 290204511 546303333 311433335 1213782533 428167450 90141731 197448563 461546856 1227357898 526103772 145609989 142626960 980962400 489279611 844820099 172006798 84781254 779235836 973235798 685888780 473876211 460801558 637625919 496815490 126341456 327492258 597677558 763806298 432152394 1195468482 360239020 637108657 148230023 310854175 518832631 101662997 196968424 270018477 487103403 205062630 839824590 381574201 976578854 1055409248 785101127 439144712 456015733 604876166 940722976 238900183 650601264 225306776 398594386 1201745208 599186272 599779775 91721343 529817339 839551677 522551346 743703838 1493304875 518504861 703461908 959113866 549695117 637663942 913306654 909730638 734984969 293948596 381516410 116266225 509474381 1013576496 469686464 611857475 201396347 128912338 468443253 480513809 749051976 492211897 490149637 510847151 669971956 205852860 758848845 512099870 489375187 176176895 143459835 1088832097 662351747 524371197 264444511 272287406 1224189113 675308057 656535922 1056224710 703522416 317927976 647046452 653990127 576483546 238364463 514769190 852985128 692363615 402717417 280480711 160594115 762348107 674660274 521507832 1165752489 471072977 1024073489 786255383 203324008 897654382 734095846 794208354 559541886 459574125 515802603 1057950594 370821573 310848368 407326148 682190891 541105504 970249174 478328607 963974202 359190665 255074496 1683723585 996150984 352547838 598028010 88347038 592078825 821175989 938561893 459215730 366084423 300946463 199213375 856384927 361453070 506153191 293775666 360377190 424359235 658420691 699750421 153301464 147548293 165907599 396221974 693965332 499653588 705601885 880771935 364964451 153303632 670833435 490495276 588390195 216223098 886973664 848691537 775860507 676461690 782217973 1000393585 517475506 564463051 696348331 580759298 503599531 489864030 893453450 829046489 848419957 89354104 574416751 290845839 983606440 195267431 1034146038 716519482 229697648 280698490 54339304 235309664 462245290 415347130 751399189 532077340 854502051 187598331 567710590 243215621 318197305 435053175 1080636844 434851914 770731170 652637275 783161115 918445459 765713956 885584772 230545805 493096029 681878929 222935282 381977168 281286923 953708083 548318602 1530949986 1014712688 746916755 408800403 389319229 249754924 263227805 1294947136 286322726 938212166 562311783 475187618 42685756 676804551 310946000 156261140 358469983 422251620 152544993 713767549 1056971277 388026959 423301265 679284816 781064703 373295882 732575916 538820119 236951499 761573785 612140332 282510269 457209099 500180698 611688838 371166726 556296727 1133746420 624418709 754495073 654407654 1156581133 851841173 727633586 950187192 1305496659 798624694 561306709 495674645 685834556 136490665 685147981 688510118 449448665 838802140 767201546 606983574 333306975 897421055 477203617 622175688 333348005 271218180 841819439 375700703 230113636 735875667 1074573912 265671639 284777189 182037150 148982978 842626956 668910134 324788898 226406048 289172363 252840331 787036225 430800238 498497178 118742415 923931537 635686076 773975656 72985048 585038836 251330102 546755067 880210820 401510495 487753887 298278649 261704277 1152826217 624299260 548553938 433968179 488283718 665727320 733779687 479194297 1416299353 1360614789 739420217 257709795 451745056 170149872 255665395 1232986973 537838254 1024551554 89990066 619153039 457187580 331480934 892035312 312769642 207970319 786762219 639574477 688538965 255217826 254655476 737458391 589846668 245552497 219479613 744974016 1179975684 979558065 536924872 747530804 1423548100 811129859 486736118 560450259 300694896 756003983 853269563 488341706 410855864 132632438 465467693 547683882 603591602 380800514 986836423 265385130 335634181 320682274 790288727 378726802 277262638 672699746 89828951 313099023 773417483 32136475 1191223579 262168359 239008079 939355699 710001730 981958567 799332720 459914364 310450058 1170339748 563205076 252233190 870389989 465108474 716268576 384452492 914978054 1055460960 870808520 665412640 913183794 808862566 403596232 951516816 755008884 1275005831 769880431 201599791 969420506 720158460 364773750 367353105 627763246 234234192 1463701999 692333664 688621009 313929194 575230696 611015494 840434835 1485524303 161913656 219884563 867304262 630071925 244090884 400715918 100093892 382238325 73285003 118792779 1010348550 1037333679 465945932 590821739 818377493 653157052 877674103 485646728 852623077 637363447 984188353 1144282640 721399784 881572858 431589664 1245468279 577699759 721152536 867153955 970290139 259389253 755522440 452042301 330279369 162388667 560698669 1102333573 692784520 842033492 592022467 432235735 579416054 657224153 1247602591 1284529809 328239518 380582048 87013778 1652662788 528036100 440324931 553267757 1608279706 285226607 251591948 553006363 881733524 627652463 1407519659 411845273 1467500758 1253524296 270644199 525053889 868681283 683148521 889074665 680438046 755139469 459210926 631890302 585672202 666654247 504993038 205704337 1537304964 602483339 435602594 589975035 533549811 912587786 267616433 170545391 415498391 530475857 315172816 228145761 395753087 925598795 635498405 1570391479 526663208 325430537 637509689 1368424729 345182135 676156680 863145876 380674891 351340964 427723618 775633565 361179828 250091038 612889832 203384695 324803257 433890019 637387037 465695519 1224047604 620467183 1531845281 555010906 483761264 554848923 936625492 304766177 664946528 463275596 732116925 1290251811 580127864 725581014 229664344 577293282 532825374 910969540 1198785499 315693438 300839275 1083879082 765606150 163543900 503325817 666096167 695923466 773484731 1255636945 254468734 1369382383 165651673 840298809 803867612 394704688 1109479462 712677222 811516622 210750310 520086711 187090222 852412241 1247510202 732763753 358751040 399168204 303364215 849342540 377929670 197704780 257848104 512504630 414690151 373832194 732227200 170486229 449485007 394361769 531926036 833379626 633333564 464629679 1018953087 1013789491 665928750 521062137 324480574 675113804 323080346 425013226 288651237 1189242142 289594802 236555768 1133577907 767897661 164392762 100753260 213474643 1233311171 1118304293 474100055 706000967 285926534 573225707 689593251 463773706 722527494 579537962 1193614648 500767598 334842771 857131011 198620098 492595913 1063947781 923016968 1307869752 809265205 494806797 396401536 861704114 390620532 741692498 1267976058 719018431 925291974 613973916 761711488 951269602 287954838 1245260934 477257544 105830907 792166852 486755634 405585801 142848979 1664316596 794544052 254492800 146847677 653596479 164871395 974611885 1116299290 225642260 378648489 878432576 815916672 16441542 1274053622 1458318199 1295694442 619165716 160787039 560480702 228331341 696945428 314676435 697606373 943598213 792525683 640520582 98367986 437029422 959115785 200633375 571055957 352237960 171882422 1012473394 153717154 208316761 922599688 942822800 964142632 834629718 303947523 1031806535 639725487 524274093 452751975 792422173 283156655 158328530 408287034 439457659 462886384 796235097 810047843 557494194 934759703 727108716 816356853 589429383 1034952043 642799762 866040926 549680087 273427374 657083195 315197763 991357945 649632848 777903216 659129384 614991468 307910033 595856527 835066298 392521072 731661077 750879784 688441884 1138461039 353282323 535088487 730789888 1089789316 744270216 382433049 271477981 793824753 898682179 572202083 489384084 378728939 170949629 817261582 328374835 786632381 455831711 415099504 528585069 503243529 515889880 1012265399 123052002 423877551 768135570 515889177 329526260 683261535 291595093 1001942583 305833656 1021268880 921497078 717791682 838586953 898481702 1051074543 516757404 331278896 164076550 772952877 543705543 394321267 331059039 696859041 1069022704 1331275700 427882775 562635064 367828964 817004247 397351533 308396813 850032379 1560238957 659770525 1372013807 148901796 797475045 1139849928 184185764 135200429 648576660 1022072193 707989391 286120081 751924982 639250692 405338317 454286174 388110205 983139101 1285611371 335362068 913831545 424164796 42123019 346310159 430826755 1181790982 1345584030 1129863043 1008256730 680889297 1115267231 528124853 169289943 998171665 199354771 125164175 549130124 1426399416 196542744 808155727 619527025 1416684064 401534625 613172423 568731141 1576111852 1049848998 1076943953 342305181 1175802457 646058634 399501075 840731361 452681463 460820925 680148987 1093793492 394510146 789292439 376135390 450153341 442756339 949646143 892148381 162055061 518384401 1395044267 364067787 289413496 1186639456 286912075 212585651 266481323 25507946 986489843 596510066 702472793 421373500 152479738 951473613 1098693471 491303333 884065718 1423646738 320218665 821059753 371126999 400712677 765688792 265424171 334339352 1333314338 487077852 322035132 286129012 994786186 422233166 804982850 475141960 917401472 837062353 129634723 204819942 451933969 1024007526 542718696 1373821207 1221355717 922385463 707493195 438373968 275334668 686533092 651683012 1281364287 185117468 481360888 416750956 716039893 921732229 578614721 698325109 166205925 147733936 643617725 596920631 746717665 174591081 567828523 1138111120 619737526 673280788 1329038705 516488517 1143156663 668045788 650083373 94917167 372307992 830543672 892690452 571991087 1491458705 370136764 546510346 1245329624 843789823 202195798 299174174 234647430 78832036 171000771 274310617 177788544 225378019 187585674 522210286 206962879 781265344 652645850 824819315 436713107 491181456 864520102 1726935334 632053461 401324518 504344978 473464904 382607528 339526812 973324237 328595053 228323722 156241851 540063716 819480407 299603235 644281957 1230518062 84345793 380601508 130396236 259294237 637279119 610383849 215233061 522887389 888997907 401249379 188624798 511242724 624833798 452480741 449682358 697083877 355479975 359760344 959728365 550601037 499967817 363054199 286035165 374336555 585719435 265518282 754583214 746864309 104152115 529046560 651112194 1084154697 412458218 330876639 925639903 601822574 1524728912 205671161 266129844 454747667 609730616 762701797 315871029 511649388 551311007 751321041 381735775 187404845 898219712 585439738 265801549 1163103752 259265517 330562663 706537080 359315480 102049118 588881019 612486601 616055677 917785824 524629060 162102565 89068966 352508096 752657569 117862041 298484584 337017563 782196355 404670120 786556792 339198579 913504279 473084417 445048752 1208895635 354472296 596636640 212616683 181783322 590126338 663880753 50279254 287635192 679228697 595425348 810526275 650827519 20299097 44396412 739630877 358938583 1262056653 293339379 850141907 552788574 695756331 801318513 795777135 470547985 513346424 936292762 243905029 734857171 745825269 457179645 844977534 661230387 956222267 1003673867 1003214125 264727089 665930737 413577434 78604039 650056861 507044863 97710792 894714435 267411415 1114195738 520324701 506765027 805192739 775456419 731999817 704927428 478471918 558998467 624180901 818932431 264418777 438797254 613438759 241590783 322808248 557675499 564292130 227084242 193843132 465403605 457212933 1038259679 129676570 878413675 552354234 545202723 553956499 352214079 962694299 336297432 387727792 718273467 419383468 587699115 446646677 844706900 352515663 735392583 611475182 592954023 446631444 159782351 83197800 407360146 752230320 451311677 505087933 984930318 1386931161 573375145 863112012 693290432 473648298 814189100 336848645 508715005 509931564 731891453 108303103 245122905 511580665 338121258 283351551 574478348 953110673 605512799 399579886 660339945 964621329 1210669529 276583363 594423966 216911984 520347949 272903101 619022189 950574611 44529721 747771349 401103399 390903032 638485221 247490764 284740989 529715812 569533478 611428014 810757516 105660784 448834904 671179799 1153725288 489479577 485774606 418969719 670213404 587204627 934145077 862587676 841014597 1365358350 1236986473 629628392 597135021 662157719 116847945 821971142 662540877 670546591 384229245 677936432 1182763066 1460953608 769542682 149971588 842591101 734404856 445369185 858526954 1259934895 617090408 429743654 167481190 748747924 398464944 384472577 461467359 961353000 1226799567 844936160 410755098 861287107 327410447 399658741 841236369 439832904 430106921 282372809 63448659 83803956 565233008 927514438 217326383 402350805 585998626 323468599 421230893 626838792 353167503 1031801227 887554768 625504335 775781211 1681815629 881029713 519417843 434000351 468923105 765229291 331018498 79443751 367258398 562056453 819170289 870205260 610185295 377419744 1084574765 1545368010 637930931 374613611 910371892 481908445 282562075 406280159 674932764 682914933 542408101 68153074 786623051 811230352 822819502 924408239 786444764 603240063 1168356807 316970763 324232021 412542034 70830717 214986388 638862833 879498396 711411864 367380423 349575765 1013097717 945116272 732382958 536660941 198876522 294019324 321519282 811035421 103361843 362818129 1227751603 388370785 610754966 203185621 88522215 1456086675 1255910484 485862906 262230788 237240596 209609978 655421608 998698403 618234891 470945299 594188036 701504417 802235548 62866572 959601140 557116457 651769515 1318639706 1161004795 1562924281 457758114 588833720 236618264 209069666 450953161 384145545 728229247 1117407607 649502028 396217892 529011201 747545561 855558188 1286603436 478860560 256936496 732243876 265116844 862252500 303776227 993655211 704947462 253067989 730000432 234688762 279952108 542097974 478232175 961304668 387112532 507979057 285124367 108034644 297093092 458646570 1065066188 416737665 358601592 852623956 1249843842 302145288 676041515 788453542 758668775 477160098 747066065 1144098055 944055983 711227257 1059289275 367916668 551845984 249989850 242945061 399593701 537612609 679087633 839707843 199821760 484027453 273825593 967041679 497253373 136808465 511161784 865110939 155450530 454580723 210335460 264540437 602869518 741794406 219192657 787552669 1099569356 189132122 518233235 888274922 485810790 461117916 459828890 475339474 480756970 39894034 625748524 763216048 362175577 704029933 450542280 1089215452 306864373 1053466982 127005563 564419107 174903850 392936754 161128521 694663203 683157520 1367097893 788819084 545348100 1168971546 218080247 557903377 378586680 526065297 947926769 784069752 599435797 388215787 184466473 598510368 977135910 750938061 1174482286 737061973 220462352 465197279 692256403 434477642 1154606995 540401114 769285640 319354516 1415646678 1386071431 584737503 359437641 524220282 400833736 424427656 403643140 1234090763 268643920 390048612 654180817 404619959 1048932172 1009285074 928090921 748622115 241279210 450236017 310901429 837731951 553923643 697861350 787573503 1181904182 524624009 289131262 801864654 330292956 98729053 805754985 715196937 411415302 247783752 693337799 342022371 56110732 712222572 524865897 1025949905 322095488 727067362 1083742863 684792115 934057840 669081469 612596823 73843113 1197978605 945715404 939993153 769399139 536298215 398803943 240110635 241222138 87782947 374618640 428524069 623239832 1171749879 623049382 605831546 481175789 475869057 677056225 882342348 927908318 384059289 242625300 135532276 71421773 312452491 1253174743 1411924876 494995741 1035791725 336763165 881446696 302819428 1092314823 315444222 763183258 311719150 725036729 578865107 507392393 268481347 679789032 1011171088 617149219 722232140 657664628 721459999 398738473 203117426 390467289 867634437 470503572 1360897105 303311756 417185386 940810638 768872044 556333998 635051653 737396896 227316217 251437027 445556039 642168054 155368228 995260930 128529569 434737841 484278865 588019322 309689851 994226185 592094596 485589149 325179322 61362122 1143748712 755438864 1375839743 84762880 662137870 836855548 726687040 368250167 754774713 1073852136 831090667 644706482 571848933 1007026391 967754433 1111710084 331437267 178359225 792762928 610678349 835574385 349270649 437933161 1168638974 687121535 361185755 653593820 247190913 459580744 400788705 710117942 335872908 423767156 1289813567 545354200 588321779 300138199 611930073 617834021 107611104 379134488 760309331 665767803 317745071 753804020 1045670905 396911079 444956103 232017607 401983733 308166715 372041679 1099136573 392526722 844739363 1109313711 293112576 519421052 231435267 454454439 167067815 603969652 944932058 172787671 298228385 259838010 288579679 431469410 222004150 412524624 305290635 732514023 1055209159 541795749 808964329 479055338 539699792 819826403 749231655 158828042 343309402 619054042 353957667 237612580 800746931 474236549 328019646 695349215 907971568 385273551 203264961 397281828 666386932 237417329 422533977 874736147 1697125970 324950116 424092323 460195772 661881190 528876289 342787135 436715689 207315375 702616417 366881478 334141236 507475377 603482296 601467257 666412051 329384712 537210454 846215095 593046793 208702811 1346183671 492952148 398921583 480530801 946794029 381435695 404993585 932538937 487571403 307078879 899927487 179545235 131911625 506980815 502129556 401739449 1351694269 214311967 522273782 1132664907 862301372 1422100691 859042133 1112369223 411585826 215145995 182797396 618209185 787507945 574591672 925488232 460259609 165116648 1105951922 446581288 1255789915 963756427 622527067 609991280 1076683831 280643622 549135165 1433319117 591762153 189035203 459762454 658934529 324323903 715639346 379879582 1116757611 970846260 337454734 143170000 651175624 132898662 1433124333 865503152 826544319 678383941 301157605 506618143 704084128 513524748 541038965 583933592 549085962 983668989 839468380 771900144 417793855 806600658 359787636 765778407 518208276 1077515892 646394855 423395311 636949390 574286639 145233197 117286561 309990359 475045491 169095968 877547373 585419281 288648424 85817879 603103932 225800031 1280917329 638772151 928519536 803440496 254700513 277027643 1052222540 1186673005 76000813 673270865 592233874 452011971 475225532 436147125 305353446 179734578 1043464525 1322766465 252550589 254330905 822436082 1266359329 303123522 415895904 1002355564 854557959 732268109 538762613 451847714 1160750313 1194275502 569742937 264759296 983445559 444052088 191035540 1037877280 333287239 566594080 260589589 703094351 228780547 506995280 1166825011 130593710 622820277 416440807 1038628521 622149541 480634575 447583098 86695086 664727270 451838904 70225881 57499664 89751152 540939760 621520647 427932730 347494452 216677792 731232032 865139099 527253898 146643310 444542763 673920913 122648592 339890359 1212513059 151014246 770595645 661477010 437852220 958001111 542457497 461891981 392552097 222822373 115422796 441822909 1199010405 404606050 981197413 1159371100 280158774 379654353 1126799916 459946168 414962112 278389903 245861277 429859911 549854107 665031350 236706852 1473915173 499278496 615741375 311711498 1033589512 662783253 783217869 961823097 1048618337 811223368 1061478192 483456443 703385546 1036649399 359179005 1016648755 376773139 778790057 293691392 269534329 866064004 619889723 947101962 1190570006 917589983 487092377 702108431 384233392 255799051 335823814 186840816 758899770 516336564 908165219 500732726 877925836 542624335 336518760 416189909 990566969 466612598 1122952274 382307746 665945268 369552174 431579507 462843476 666143093 699622379 1163928526 401165792 675964888 1174725979 360008240 1070791159 302436651 455521746 763792879 961808225 643750723 668456430 910413246 1134137989 1271651345 932623717 566420116 584091611 1024089990 217510922 911048695 137181292 761782802 550338979 421804746 719247251 301461638 254808394 183933390 592589526 884553569 581401088 424108286 382101143 945398961 277841640 931848389 963445983 881295117 358405336 552398969 739280547 523841158 1045112531 173638548 531618658 505080431 957200936 96657474 333084277 469292272 475563084 520321456 586833593 710712475 323357362 1132878306 580594935 998338992 845456110 314274012 607891631 237678291 620434992 187744931 832896692 537072003 557847679 448804075 360719340 642258467 214277813 325927129 633097306 418050349 643353126 23881473 536561142 149773431 452716327 648081847 258130232 440160352 783519050 700454622 356139976 164506793 97574928 1105868282 605834178 593565859 612649123 501685246 144135741 538227308 492724931 485849456 263872043 225927926 1148815125 789903336 948908831 148378053 408090091 280646656 126923659 768040025 551229836 68715078 1231529657 457471593 338528893 820832615 103732037 307296284 480746574 387319068 587445146 791239404 848025792 149930500 786665784 421746277 184651635 422086586 827998044 458493728 427743324 158263383 416092985 458479477 1307648409 689948276 496476430 801277967 218661773 343104350 906280780 67935794 403128754 1109459302 738351808 497067981 698819053 93918357 269431527 655991614 381912976 211561540 266311423 1245373587 805403768 38348922 453096498 849352811 398820642 460087170 425506426 47117957 564982320 731839423 1427403654 662140108 369605834 155293536 799163035 204209111 834505767 1028631340 629127412 516665135 718280987 754536132 940732805 940059236 270946046 561676373 441490552 181031893 951983687 79730467 613598261 403032300 1064644595 380603245 454368197 321312935 511781648 402123716 637293892 494642747 563295553 1198585604 238375019 798696624 521874331 648112935 328040805 610107406 217424522 1401377868 290803843 459276233 998157005 29389272 304287550 652192198 184833793 1124212057 1018279741 613438757 1427421732 322636264 382578486 377340443 682463155 637809872 1057085434 921576107 661537749 377218722 448057408 1221318161 295633635 722177127 360012643 303893343 797847432 249193533 1177835625 339730290 249477965 817515005 264036437 532250146 852643830 236385434 501737550 740903018 666581022 776488837 766813037 1137447772 474774356 456743981 469733077 154604681 952114570 937314671 68588039 762011098 164205290 662540631 522820331 1224531024 1175183180 260052395 330774301 465001433 281009258 828165685 766647530 1244653563 753107039 572968152 696736099 500480703 291887196 769807172 398312662 686153818 220120404 574565121 792883504 987483531 700462374 753761470 316986732 743759168 780197188 293965591 1004497489 361448365 702267981 410810871 936092398 645564304 316208151 523663533 330985952 51968712 486278166 429154547 761464498 610992178 1015555348 693302579 643324382 311378161 56696191 690420167 962251297 1038561958 699316751 513213362 568980864 271788266 609921144 1141495542 1053149997 772894711 391900105 1331977208 813392475 566405483 371557915 528162298 353446441 606528179 216447379 868941181 59262965 749496790 908537476 320523515 358264893 459615503 628432424 910718376 203070007 1221365171 604200022 555445027 1530930766 1729271749 815590089 91978280 217006762 147369627 555229497 809004721 861628117 908819022 883399951 983112854 237248074 363438192 923649348 999230127 1188956042 778538788 576344483 153667170 675091130 223001855 399789030 581946996 630600183 1488094115 703440550 651296108 247149801 449124966 540254297 506154790 263203221 561261942 1294236844 623340856 251144987 532120653 812458344 958332042 395873016 472781242 688391529 934226555 941518108 652785832 256175724 1070704966 824693745 324640766 422570996 648394124 429824495 281193607 220192261 1273667071 484887772 621122393 404611632 908644533 979277058 202206198 127489002 442188486 559076095 991833991 250159155 575265272 183602290 1223696982 758273695 238491688 126136490 1430420814 486766045 881523196 1679254620 583918038 1303993628 838507397 1121563503 715771550 892210810 1070807830 572919208 482687817 794308533 717815078 1326674738 238271390 347076983 258884326 247941733 710946924 581010825 169675843 677269679 156042130 1155882075 353435912 615037200 302721210 615330683 529386631 763305678 806270643 554760454 982397037 473033521 685286455 656564401 654786344 86139782 582000902 677704414 1119643057 345381411 548310723 887621379 655558939 681600677 895103558 303412426 250981177 176363198 888670339 441889141 237132927 541636085 581400745 462543723 1166523952 350047368 541945621 210799143 625856034 322266044 210386518 222271116 843054643 1255871417 415955582 564017633 41572927 330445960 192454602 303056182 316209085 728795178 140697699 342329651 1642880047 692384981 177357563 993408045 1110569576 395129505 444670489 202533666 1611124770 393266008 216503182 330177777 413001018 270234336 731473465 787679424 838816803 244316388 705098367 521158462 220063992 771194183 1031134313 1388826535 336122696 322835912 1143802649 159772596 1296888006 307656518 420899242 573317219 549059972 605334882 82953324 710653706 330791288 664389117 400293747 906189851 330347465 392942273 798931262 811821553 591191568 661880935 727051384 803660398 110232708 367561757 297684444 357960916 702897729 1108712018 478883393 508557402 343597841 195063146 336054600 589483995 570925056 283024262 911530503 909670641 580589118 841370560 277962371 804139324 166012232 219982357 421308930 744608919 790943411 656509032 162881400 476262467 1045014143 291155144 696828748 191597928 367925599 171610942 374426559 1146219373 716051924 567228670 165558102 629898924 365523106 323751280 981228861 773599578 965044920 922571814 202335505 211929420 210629763 124364091 386624268 287465886 473009540 476042036 712658443 166491062 743517010 253768217 245383857 1717123878 461354818 212318055 755172819 626539868 698945510 529263250 550218121 394540173 1222063153 251599805 710271409 127164899 469017957 649036784 499275000 594376007 383657719 55875561 434073936 295632139 458077474 379826983 578501134 504565618 352138980 317973043 312048154 596719458 326645590 613382687 106651897 883188946 581449321 243154285 616573305 477475540 345152640 562392097 556546774 596836911 372885332 332080971 1008416784 545296519 375703919 449884362 201828970 277534235 270992241 1037941005 491666850 455698300 549387101 646467867 297560113 653428003 670409669 66394395 417874471 358542057 753878170 483561922 542729510 492157399 200551566 1043885407 657748524 426480578 182028441 146316505 821108282 227157329 371547700 761822253 485256359 430807486 82254184 925376452 78309121 509030417 778908808 509230792 817052666 997240125 193377936 610105844 831813029 478879133 1287810096 688346761 520163906 614800736 704399589 739435542 364936043 537281727 548097586 875594192 975558523 425494493 380767586 461768699 598489014 438454010 1000854381 1457108717 714450585 82696591 540903859 1028509869 721259577 763149537 750334708 548866655 1058770700 546813595 569023175 1111310243 705150481 617361397 428123909 625642467 940579783 203378440 617741227 738221333 485501096 335970412 479308828 1609699941 230071492 537938693 1389337791 356740799 961996686 1017524373 745164169 799649745 979649129 1069419914 421858296 579109996 774124420 861453275 666194282 489183514 918259467 295837625 854330619 307086057 499924852 454664161 834304070 388709565 390027755 684598500 1084080818 827328068 1125257519 206456447 888968917 788973651 1151098252 254167539 328832923 654853913 586851814 409482683 511338260 65219640 362961585 208564403 360473031 545736094 189514191 696272398 183258820 590991730 961123888 331477731 235539298 498145534 697021387 366460396 277160533 518010032 766781745 550458730 864202975 299239273 290245430 166937027 890068724 605714846 1250984186 728894879 153205571 511484529 196503652 848927140 649517408 915352802 524997406 506605562 525134218 240869274 530251848 472177010 410638885 494683207 156831491 187097817 559310803 1070732927 467002701 160939632 506345867 738907899 394530554 977836322 1143920150 602150309 961895592 576003805 309029631 838735413 675085276 868274120 542507435 838437979 473919387 424223838 833535330 193759830 344446322 384356793 590150223 226898053 890131091 1574842256 691497261 625357572 530284927 806344587 403315378 878523449 526997941 672876365 170574251 675210173 371454152 113336659 54014443 291723955 153982988 236600863 509398093 483818811 420118834 1211526516 956781570 330442251 206967947 342648120 471602345 308095354 596990731 702775701 345065560 1041877358 473538763 709211184 920262588 858200555 1537443102 194113823 242991030 707827391 452939187 229103646 715370920 1345163968 1232717124 653936259 1232135105 211274180 787781227 1069925840 675646027 727913951 778762249 900742688 566629346 577329962 731037170 961736696 526269782 592340609 250267235 902177286 524584777 627838057 896791623 707598979 426866636 243653590 1381229419 886794923 460628784 474149243 751838347 1024072779 326216650 1191781303 437374985 446127753 1538890139 187722667 590596494 299019825 246678950 810857842 715193544 659045445 574970944 859957549 261697731 676167749 880557584 772919207 424896009 651152245 624348594 306516593 659194825 892884336 399841033 1265677445 660681917 593567605 596788720 757208492 562839907 590964320 472782067 96290378 827002626 515443626 350496596 562090477 362300856 935482324 564919714 101205041 367102178 651173853 764496581 579179694 616574807 346965812 703959217 896538571 660949463 171125889 37805320 1191838202 937053369 512395891 426178123 895071602 905339559 357634594 875002530 1443302106 483698069 496488374 682269283 242862529 475022133 321969092 176312832 143246647 440798436 711899184 534304006 697673883 204580114 262923725 485109147 619005829 579129957 250522735 261804409 717202761 267539325 637755712 409718953 400147864 87116845 298349806 949342233 244556028 1011686314 1061564519 150901401 1422952184 24640585 953129226 1062909990 235030672 902189265 1228529827 160672146 173177335 1458292188 219420671 605038397 735304325 476972979 712995314 901537469 503940646 553822391 931080694 155217418 762291245 248024631 377308554 1524228474 676824162 416687430 781208546 493113882 685437729 707842649 602785355 828577766 952685233 575760165 200139131 907559272 474319531 396900013 509702297 186130672 295325772 685288406 736481897 138467933 567255141 754654948 1005754606 363507868 611429394 908287946 487110228 246217229 882135980 259926360 345964596 774974192 210820802 1113042098 211508604 376378625 438814912 972041214 957088897 550116395 755209670 375883888 1391918726 811971588 299776642 943215859 251345378 591733105 1370372101 134480897 868374051 244068128 709147106 663631242 1320087543 337191685 558224185 405218394 217725734 305798192 322571354 980031308 1077890082 881038448 1064934977 632870429 381853599 777434265 325802989 558478766 809010052 537329655 405596869 367866924 572054516 982542477 405053467 599183334 741586758 496239792 431544002 332013500 852667419 1106940760 1151328475 223237516 1304243450 848467779 149940177 683223531 397582650 637649945 1083134309 663264387 569378389 562607427 1111893020 1085308614 651468741 625930564 398277926 597643245 522897367 734734478 498481412 916216497 146621437 972620768 650451139 595595806 1483086210 673524363 482675247 289707718 577954404 432831732 449218544 1038970281 438776147 491129018 325469793 330667102 562695101 502098677 405448706 112163578 402890484 907710724 732433331 756702272 356070329 923902941 179500588 1164132839 208072427 356618453 606500415 165385828 613724474 159376534 474019128 96286457 819059034 255147364 252064719 275153433 619729757 471546213 520385311 570865075 1068234195 400454260 937243179 233205031 748448729 1024620246 642157880 329140709 382936388 679590752 578996276 314237589 617826799 1391058605 807830029 614427746 1406015658 415915716 602100026 1236137160 1041068534 423458723 770603537 306697113 460532279 1136482551 512261326 598375696 362361840 95537143 428958582 1110923197 724302653 204076005 1422882236 565357706 839618974 768504502 1049451488 1704171682 518888607 1198995473 639660421 329432187 40092804 320130262 324116063 1094329988 498282600 986194454 721919141 646866799 561285123 483364357 242458663 702653144 1111574437 613008310 86619576 458672361 347146979 611190959 230887392 682318512 540232475 587947701 1029029276 881915984 626125979 436078603 1167250348 191535222 838094192 1488063451 573444672 578773861 968425063 255637344 692769593 655811654 679015372 330924942 256023831 195266804 1019491754 36926283 557563411 521868648 1052652806 685008690 277596163 404959854 709438638 1516210669 603118884 139070177 776010196 855618937 730945153 164834518 972032544 621316613 679596806 1535971242 521175090 820507227 737741380 277175827 868042952 252751555 468876289 282791645 256504407 513334202 1462718290 677619330 557449236 330924375 494973352 549858474 735436021 22937140 1063057859 358414394 785279354 500451814 527211435 435284137 132039098 622679415 670682692 493890564 807401067 990823914 806062181 336306201 426950874 179196348 659520328 740106282 480177771 392365493 804782759 337621890 1199959393 1056673295 415237212 742639980 618356295 316654411 406506785 631257809 686752045 347574020 613189448 495093039 798349068 1061791392 90397284 812283682 730495154 433682875 913039090 465166823 751982722 880376432 515147759 339743194 232089725 1242535854 229581835 869467954 1005076538 924281659 537666323 353003317 149907505 917882934 1049841213 109452426 1323130404 362168280 473615345 247651534 1118733757 567298408 517633789 570889814 695111251 963556475 798562715 706716933 349286789 1538876820 1018638211 644386376 465382176 170392543 367639616 905440613 245488918 410144596 208484491 1040935645 193477545 532377149 500706931 348850157 733018496 1577511609 378346787 491573399 656614103 883425384 755205399 613910297 94905021 491126891 856371919 637421965 1145023636 507089430 485797976 579653022 1162837396 488785006 851621458 115992269 632110243 291890702 601908442 755756714 790253562 220907132 206373917 771829297 1003567200 832179398 794119904 444794850 560404967 182739109 218808543 758352362 486218601 1213357898 333883341 1580290833 594024781 661104986 479576646 311381180 1035060934 396870514 711463363 1087324043 230835460 1043867755 315845121 167796219 869481243 901448613 778861303 1028542312 985230374 203816251 390510088 487977244 381481451 349840922 404824069 680765141 283925555 858138637 815917631 261055883 943772837 999622582 670263135 442083917 187794803 411529170 1148413944 547082459 284492803 464071637 973498011 1147699794 915552598 220498979 732835884 285066116 567850667 434405102 606856572 486103559 885442078 1127545952 467299280 390183314 371940567 691330009 329143903 1452464290 664041090 404622294 788039094 720982151 840609883 668234122 768582157 46141174 698853990 956273617 1098056740 531368652 736337180 354046391 466564527 917120105 988477136 157018472 765622768 1019065934 542892769 440036988 1020573211 1227553122 783916636 365897011 162270597 1157741248 641467668 508987385 415571977 531180944 836518078 161130117 504015198 677947250 531792178 1359622020 758623042 403665309 806294130 475652482 746493928 282184472 785299646 560581916 233525894 999469665 673616358 583989191 671961626 988421213 503036125 161864403 438128581 297381609 127801819 647397439 1066089160 305325710 364788716 770343094 1316272158 161948209 666846752 709954706 589719741 193577715 537838153 265167095 1496433285 580343128 1091789136 1135357044 416512223 204324654 279851016 239291904 870699179 335857697 520591729 595231323 502626904 205342271 290586470 399635760 1234331519 262348587 699890118 476633899 636386245 804606789 66546127 106459863 421018066 166368487 378822563 448473255 551341543 762428254 568372318 610984192 367848782 286499622 847452363 307513268 66091686 621295755 1200679116 1140675630 219364889 57758577 1214875536 763261790 667056142 655707266 498425723 816694353 1133293151 607940500 778416908 517451593 1426680111 89128265 9738281 206228608 406602145 261872433 327623881 698885053 561265639 1556837714 115338025 600259365 596525112 408544922 935796595 639242606 363928178 514112322 752831348 792976124 1057140502 1027177914 1026866285 1047071059 1251742449 567592901 648719082 542249691 379680600 325542279 1108357640 513630427 568659373 427232417 583033584 269307550 433391621 869835347 557162880 78407246 530208986 1586399664 194736119 310965337 378874167 509085810 999102401 627675416 579298238 1155887664 533816335 246481814 642458644 509644556 426313793 793274676 602137867 572230028 599275159 619743677 376155103 159822504 949769482 465800987 415450460 849900541 1125900239 459333392 1130349005 396824958 862204618 424852285 292111183 948473709 869826048 276060100 1169841690 1431930426 887017871 437742494 684211311 1584531583 591669404 463194598 297671104 392660224 823404277 437247613 606729401 693752662 630015177 149725751 214849947 986040888 469148729 737189051 615111804 533776196 1549120207 234782345 171205837 740987757 574904044 1332899284 175660475 588704885 688711594 902826969 603279217 551100265 402331058 548715055 877013319 458005328 335403537 1092918067 42761386 359935217 347507264 882541689 518321899 782617818 684399445 620307232 62236505 1018960622 341274791 1040325588 622508731 43478936 247813683 1212138456 306145462 873485222 611451675 1191330435 231324908 381762041 1099541237 235595466 1104998446 408626000 161100973 306700649 1017877553 1041855479 738448481 549194832 584546594 696869774 504628221 549005917 1118040421 1198031050 412820103 484514417 891877789 419102686 260439671 1034964314 721062787 1399859133 550786927 800288792 661695144 690069505 441263110 182216475 399937514 1006830215 618340543 663331110 984224285 697945515 770919509 260185037 673528411 268447557 461187819 959692299 492865161 719150160 393741460 211288795 373957799 646266586 233055244 736799754 633995120 479954031 1208036025 979160215 711748547 761895810 139395208 1135177589 215216709 308352030 566722290 646048767 737200997 333165586 294853886 351264667 519888601 540077092 423890008 701244266 416545930 207957536 812621722 1215738273 635913982 339089508 466347146 801375203 285146759 873005827 772456682 525194436 660118804 607707623 781623466 52188262 179352861 1362554671 723832591 176176272 1066768388 240493839 833990337 1095007563 536042060 861574253 320018728 458139372 636334424 1478915354 550190116 822493487 564736907 133427258 715972922 626945708 244213598 248221690 328323734 703827989 859944612 862831223 156890515 626785473 950564111 730169937 690847434 991822350 737858744 765717317 655560861 565825149 929341790 256147002 633910395 765529311 555208154 132173302 734198757 540937520 363459545 413152680 576336843 391401769 650548521 782106178 95659148 297642781 498257232 455560585 576105074 859876777 1045291283 799675316 753642120 789266524 989704831 1390104019 916585132 879009065 357592712 1223635078 420320369 748188358 227241823 1507889265 403931693 999002362 656296416 611039789 1169053784 103407108 483773308 775508013 620553261 282682880 661218339 662474071 159185805 380093658 613567891 491462968 312303964 212005252 71061953 331264905 448325551 827218369 449864314 379942295 1124244525 538383808 1051666887 633526527 1147605207 175530335 281416455 376416106 473508757 163238530 397445209 671122028 257548385 356865508 1387613929 600682022 1111377904 706453963 1106450532 502288235 309527239 1285479435 149725517 1490304219 252076952 1368963802 415496650 447315548 856560204 238534369 588531334 555254873 958911688 486921060 934996883 69464586 497783487 475665932 360550693 447372843 777006319 239577323 391264913 474416526 261805840 697775986 540978502 861891665 657837264 597990370 828816291 156965422 274742678 623862314 311672896 662880071 153545250 776894009 101924505 845664273 474969897 762603332 199565137 188448359 210219069 300744159 238925585 146964527 482162242 524914026 275714116 1025528655 935534806 583933721 762885796 805581956 226306759 388178740 1055464019 785579852 974756445 1070321556 410464467 597849217 946478372 690943981 1212688345 694774212 1225290236 521605206 152158086 485777125 237532666 639240860 363707654 495604345 553913354 868651359 755569514 594104420 356894586 345036986 281387349 623909895 315833193 579886975 547502912 888051821 491099140 1088999827 903673040 148775450 366734757 236886494 241844414 1240730965 357657218 864059029 532033772 321992650 594096787 892967351 547887527 453711371 1059720179 538146117 703699848 1091221894 914193251 346749777 500969738 311959736 518523337 95905476 139957102 207685499 699115884 278728166 163136525 44193370 639684749 594569091 469430283 262878069 728491471 353838455 421330643 786737034 727464136 953389915 130008406 946751319 1538015959 754513966 685807180 347683797 359362186 567905573 423520060 471541261 1094436094 1220127080 784060507 930092376 748344510 888181684 354637470 574489017 584730502 108016567 1542570280 667858854 550194070 1077079488 469828559 442101041 617749157 859867651 584541960 769335470 258779253 699938072 816503569 575605766 1020902457 262340824 866186034 411544642 407158963 556932431 647262430 432001074 398010081 703338901 566661747 30563027 851938128 1174904910 249481838 429467154 839519883 167857232 411216150 445459656 571265963 73914751 507027617 656010174 453704525 555329985 972850976 963759790 483517874 151259795 536110592 789787396 765980664 981558891 80015076 903100414 998420391 839173149 996473509 229530940 230148748 425201998 192237660 773336925 673039543 572466623 467596236 682377459 111370922 259951535 65049471 317582787 390549450 155219655 211469649 467815400 570257041 327402568 446132241 426421351 550426715 215501157 758891616 1145060456 302509590 1056005056 344464875 736978729 580159847 928676600 727153332 463531510 652244403 373262789 447236723 963090617 398424517 380697919 428929284 717069810 911428788 666709266 389883284 915796643 832406584 383570253 540328232 1106508923 127066744 288722860 311355161 671158990 522565663 652963461 662535841 324784264 653602002 256516627 733457381 627485030 682555726 577787919 902363539 197132638 1124924726 516894261 1018216817 406849399 826401543 405353300 73008084 517828396 708370141 468102521 226683065 366923092 456454930 1003059685 457462289 1008641829 1301778488 1027516952 107408709 950845158 1410014571 254159193 288646906 435957678 900069155 576082176 613928560 1237534323 857968951 1054704779 661620479 409447486 161269784 1146324015 493760299 983480062 1275315298 571259290 555521530 231090534 622818978 906531749 623373809 533584578 492279830 1266923272 1354917234 631552160 909156210 192948898 431585048 202868631 465076287 1077956715 529159611 159007608 1229814760 817661349 1338651652 225538125 870313353 427565472 374521058 686773894 158852833 800569040 764416640 649415456 185393257 670735284 625362812 1447759850 769197052 567706462 196711160 1298672319 468485026 827207385 291569043 702089964 108778565 641838679 444930327 336844301 342412801 429697720 775254656 1194887197 828757006 389649032 303360375 46515957 1273990388 310533540 1085092957 707753654 61540218 121351911 604113992 269133562 877586257 392686884 1050846030 912858440 665882110 739522652 439138531 160709903 214353105 461766807 754832749 634945942 1248511376 365180978 375897711 285738562 889398326 472396640 160949653 753761654 232326346 555650970 514820716 624326212 949423386 95179203 572441472 844658469 439014628 534105264 239936363 358552771 1117460329 962104807 51006048 840602561 624432143 1187390106 603232936 592668375 683554885 378657047 135435129 309108514 483177756 112372960 139215932 125937293 755589644 336354488 564626121 805636806 1280273198 960144622 576929124 435592990 686543697 1010421302 823515242 350786827 187634705 1005831110 424193805 1295300388 494109395 774352822 355508249 324814735 738212953 600472321 888515975 456771822 562697325 793729514 535835715 380925227 894540547 834953624 934015606 539437203 216497672 595117130 1008467380 897172232 594995834 419324665 652515393 130184669 423623172 1006713096 748626864 1245976980 219015377 454530729 405410931 330576250 703770015 527390204 156185094 229959548 88861861 521477024 748546890 827202619 392211752 427526223 732989948 346793302 413762160 375649492 919672479 252962387 781950368 571113868 953992136 271471570 1001541077 722754522 74491921 601112313 77140243 921310108 481142674 822864120 342236378 469123926 776785232 409541890 151771493 1414470543 736170180 931204350 659437765 339602705 401451840 469953521 446207800 1045728748 769667050 45195717 419362402 619739644 653209679 1009052065 451065480 700362169 443142701 330960645 329832572 1027499915 757676849 829231610 801832633 562061112 192022211 320675092 450158302 519989033 829176840 779134072 337846291 867952114 1224559817 384622684 382764195 635428320 382869368 213984574 335973711 318514999 268618530 462633570 863179047 1210714748 382311727 146561906 331497591 652465931 666841756 749982458 121916604 1227235402 324127201 138319054 829973529 211082722 302250467 1243411432 571805142 598963517 598547094 400053270 785485794 644851229 193835622 759770734 535906534 758091946 637619980 1002384048 139147380 46381990 1235858494 128275504 999319312 269535537 354822241 1023927087 705399274 348603828 358657098 436579642 137643475 1257779578 825264118 1056947634 839535542 1680162040 1016405855 959760127 311279776 1115694812 747341276 924425851 629394602 581482962 812600417 493903790 202767468 601273907 493491680 873589302 322971541 907454946 763701521 302668073 325417109 220230882 1048741445 631403153 901738573 444359234 727697749 230760016 571393937 196937367 482538851 298612620 715043631 519339885 698403213 840433601 251595776 1007101684 41850567 481356169 779257086 833972493 206070932 537471595 368403328 467586152 315577422 1602365320 353119804 731042849 364870076 684208180 1017906077 175593244 382221942 427178962 988953215 1079463952 1541863874 667136682 786540335 747288614 383734641 624291405 283787612 152885470 641589938 1018532820 477936441 148740213 232328255 474283697 629832350 562905233 681537069 37332011 109421210 723352481 562745725 1063598591 343268480 720643452 1136031621 847506042 583629270 262803555 868831133 747415762 828393672 1335859276 357399234 943051902 788136122 427835194 910520998 1282345950 584547420 581160645 1062710568 587926023 680398305 550935718 1034014043 110443396 380116751 394030783 607639469 638786835 513633858 719604402 225782536 278105657 557885348 214392546 913932798 821440338 359335254 181234392 278427465 1366280155 879233064 1069680604 1085281592 775387848 623405164 521245258 1233030817 516629489 512739578 930246780 116995253 475381566 405439963 959031611 1592849640 657505529 259705412 663305566 1022848731 145089877 496837791 363098404 985446211 653275477 1209354794 260611598 1055828752 702690647 595616453 448568846 1070586489 1246966193 684689313 1009820553 662389222 153155291 724590365 252325636 407019976 199628639 377574842 246186781 333402791 642532626 315776058 524400053 273277771 1425592788 1028085184 1100027711 575179501 1136732802 931632837 68621871 733270985 549383141 740070734 124032743 861779274 1049741477 653513717 917774467 795099758 982046373 619948072 628152447 1067769253 55416319 200865513 484270408 678055840 128888307 445152392 454808818 490704515 106289802 831372690 987645468 49248094 483898174 901379500 803023866 557641843 217541811 68978615 144830270 308048836 351016432 1098621152 794641876 172083881 623205964 332303689 554849946 731131069 126383327 732606584 940728205 302074830 295468230 633917761 507666385 788589631 1031580517 108999324 306451199 613876242 589647400 1426307622 309208689 125291233 461918036 1330072881 217358627 254260497 924627553 1107941560 519219008 403413916 646369561 203043802 435423830 313563646 365815110 927983690 708172775 543185189 1129309674 1064894021 676302435 1383496115 253009775 408737146 415916971 53870544 592471664 595508599 651831528 1216903208 217796626 931212351 925829147 959564243 1208644517 104945403 389376858 772571131 336151480 650060574 380534263 450017641 298349242 414694918 1119661325 650792887 898459713 527492074 347899366 242879565 659977902 527978177 247343677 274551012 802387597 416460117 680202033 355334634 491805498 1018842664 332122708 649802961 532517622 561198895 258002510 246476203 175850432 784729677 135043182 783085437 568105723 1087831335 358309148 1021559525 710653689 271817341 195049713 485909025 538169163 162747561 686110988 600373174 1372744770 92837709 427264132 792563625 1353478123 802978803 1086639081 424939314 203147794 381952319 207947765 332716477 744955889 518569945 1001221836 413942035 552560034 369499942 230486253 196615682 1086615075 571013566 740022901 474170676 419858333 387734618 207207470 508008175 725437726 707255121 858776644 502098449 167134070 1119577191 899671929 751507412 770389343 271743262 1014925396 720359455 599722595 510120548 39996276 402208932 366857159 1359916433 656914448 678485029 810922147 448328599 662263518 330565238 825597297 627651900 150205814 735058210 266494180 423401057 357378458 433027544 252676163 1214689028 856588865 875761162 494945316 313069117 870257915 1294807951 367099050 319423657 942313340 240121114 1052468978 696377902 626552619 551737434 1257227119 280857493 186372923 554552520 272407977 1253244463 735255582 364917907 809369421 1166518945 745535292 519623489 407890983 178388351 185521175 533874113 146959004 413902613 501866199 364091599 129087118 462560485 602031294 410667763 1007602306 254647878 929008465 307724829 1148340490 778872851 378810980 503264575 691674750 270688119 592865390 614467191 345069373 233701839 545105065 181474128 140876508 867494883 731429666 508651467 308693648 1284154741 1035699675 421587917 270605832 587565199 848887877 518787977 178093607 335773092 175775895 770665243 1253178086 525224417 528122277 583261407 339668414 1017178747 72758648 360392149 698201431 281027316 497456024 554872472 171718749 1237160636 207400641 107348530 477418884 1382195053 341263180 215526130 834693478 631065347 733660434 653597642 264462559 771661505 1168492756 981114699 390954659 485694434 361112287 461191897 81696341 1509003883 802868060 961829661 554502002 800987864 540817223 703599896 562112606 805978084 387120012 49651611 438375949 757306965 638026537 468846375 915507791 548800280 318592947 472870109 276234657 750352743 538846841 940464785 932627746 590052503 300289377 328630390 695377057 183928568 122161336 334696060 1007209218 675744724 941927829 622149112 800697274 164288303 203492399 326767642 108309384 256473528 494523187 677067916 388045026 210608930 692981822 466989599 894627762 846862717 657463067 379365683 204697809 375440485 174820816 884212593 822990258 705558082 599701942 351771755 308582101 334956160 671477354 709990748 741917664 379022813 280701726 365335924 493640995 1156060793 924134762 434124701 1328159366 1266461342 585499637 562145909 165387505 219830611 514751316 984871659 551958518 249502536 335865160 92968609 1324420966 716089138 996424121 1044860266 155558786 367158858 1185142071 350142855 1108406860 541239623 335441525 750189650 928301484 396135493 873287272 543888571 376067144 277845911 108274455 541492843 1170804485 523465909 577799132 244840321 456529983 465413263 198451242 314687242 1022949000 661536558 1104848609 340925212 1384363645 698506915 511027366 517527680 776123646 146423930 377776959 619476129 1302973943 794876701 368768009 356186462 884976018 110712171 113428345 204278456 507111546 762016507 429925872 253968080 384193887 279153710 134269565 1160532291 923702285 293641019 296313233 275456438 972922503 446293837 512922003 303694709 1058503299 764852783 441494742 913816621 316708708 494859743 387466746 1069726022 571767986 403860569 541738657 517234869 776913501 859249459 609451748 1100309715 662722195 1174233557 1544661311 978838240 939337450 730320616 101149520 518834554 174542731 202148392 640458119 1400784692 828840948 173721293 746192592 259294967 650193507 333280885 342883376 1260914392 628128585 727909851 887721824 291971913 633799993 420017044 537061568 517937487 991393590 455327556 715771220 1541327484 484960596 260043002 409641071 767223094 860164581 518470460 264128238 508295987 664992943 937595469 581935555 225313070 282627643 685513265 195855396 438156767 327370910 1009901643 636735313 947695536 700335087 1231913155 348728877 434750223 388764130 893243163 457123311 1078302138 601869168 301289122 750464874 822541038 810370780 753806220 1023832378 997206574 1245305374 1140613291 1521726676 516458733 672608072 347036070 736624232 610220985 199719405 881388392 970097481 1297650250 292512119 467469834 919883427 541793329 800918554 229399752 206634929 407908658 244667734 397961969 220078401 509629040 461349228 565105834 861666081 442619847 546871192 1074263336 738439702 326353784 202274484 637474420 154800570 118265198 523407661 539907950 479925320 1309602412 625995628 564640844 672043996 754115237 266617449 313290623 495317885 636066938 370773178 697929589 435401821 195737041 932518188 852754022 499863007 1408218893 486727514 741414176 789789456 581196692 1013327689 791100748 537690654 671717185 483107298 605861811 321475084 538481097 983953634 107559378 553940651 454543501 266658421 546277097 267555835 1015559519 171904291 345115307 591091222 743256277 744882073 560072716 467364401 1135377059 612740853 819804700 138107835 426682161 1360514345 672697450 945315716 689814354 711812236 327291739 543637116 913583876 621040723 370589259 539625127 383299586 671083344 282702401 748936700 422810483 227002114 382484886 446643422 591357019 295177485 755815119 1418473354 145701650 1177822868 826086313 189973773 1092423261 348188423 959492661 824507432 1060132931 459326204 263979165 572619025 610039266 1239556257 41329866 620328702 256773521 207001372 576225652 861964957 472039728 319603287 371477515 75309761 626389288 1162221218 610907113 639061874 418819787 103117034 212555593 195716299 1023482883 433940094 159758497 1091379341 1317618632 1286981844 445654029 384859205 600663777 390270711 97401476 1207399608 806663498 771292090 1134136521 504667564 234783250 46581963 1142148783 687067527 439940884 414447546 946203762 260097609 844244853 493375053 200756897 773659240 85233577 740853678 613373081 1096670057 485537831 336716568 754535444 626892120 1009332675 1009115178 964103490 579326439 707199754 175502349 430976091 765314805 117209478 772704055 478904243 80049002 1147246347 173143340 204061548 520146765 753229597 662778878 471257678 1378183300 232068588 545749586 332540835 1186859145 62205093 259453614 451469340 680225480 294273019 935505428 675643257 368604531 898684425 618846412 891461016 660143094 1016289887 639485482 1380370524 1198178459 1408635222 189984531 781743518 528240825 708149738 501787110 1040717339 436055613 440287504 784576576 375830512 633049824 958718852 603790826 486681825 290416997 1369015328 608362144 451049237 669749147 844951137 763651008 764092872 397093847 288259339 538183684 490657311 363513608 495634203 519863016 80412815 211258808 323429591 409052486 613478016 627790414 584321950 566628568 634047529 652280016 535750318 586447748 885621169 349744380 209290352 567394180 995160454 630790213 516954753 358729209 607431139 931156416 615078564 607764022 98567349 960499229 627123944 130618021 287931362 155712162 583514822 333769033 327134295 1513782541 149378600 453509471 1117851459 315232527 56404365 494807026 830123112 984648761 327374147 903542045 231856129 184587805 541165075 368800321 76941308 1294063852 971212022 374368717 466076726 786903511 411418913 490519633 203571939 943418607 801851268 213629599 1237729113 886289915 1033969249 163114972 343892270 355738088 1308172438 435502050 669408021 867689688 991560281 913421201 333767432 595421245 191221410 1275803632 692502076 749273806 998676177 424168090 907362296 1114429751 904714626 724493848 268788605 891560158 633545983 495614099 646234850 707862154 166053626 214354038 778513873 801979408 326726895 591425130 1179145425 321406989 1176193286 539185382 100237617 871404400 83552567 735066022 815089430 255756491 718631545 549513146 668533031 660986294 450803229 526626235 606733837 293524688 1502333410 459745754 1115494463 1033746486 427016240 1303417896 924552317 750161751 848241294 159156656 924852904 129573424 744726987 720625601 301703570 774453886 565251667 1333734455 520406328 778613879 821087822 419698751 31767295 581696942 689387946 598861108 634448468 146740639 393682686 559349672 406066001 875778564 594613295 457426270 531983209 1029112513 568923674 487741688 943926649 416811910 1201290246 566987485 643904297 284227952 715668556 1521236017 1233049563 440943763 193551386 215819127 98631627 635424376 736772294 182925387 820772135 382173302 270661703 497712694 674153610 206927938 1351677872 922364779 789659446 960504818 1036543778 1103270153 33534241 756759142 662731990 488861396 656225158 328574469 1367765386 385236823 233616970 792605904 848187215 468004513 695139910 929339368 369014435 1187417106 463488664 309779508 622723714 498880875 475861627 1110484257 486963636 180874124 280672431 520345584 598717727 143157881 165136870 721809111 118995939 211779489 292211366 439688259 823750332 1379845323 647837228 360019553 546613301 1081734605 297258213 582908255 658170772 390332932 824377004 1085386661 1084645881 397662942 241788935 258087679 1048426001 823867080 430322613 814203598 402647785 704799693 689056235 1025186212 183697413 411761800 762988491 231130722 535411959 296721440 468096886 624917128 779993215 177486309 832424534 893462712 410537613 263913368 178573691 37778890 613025829 639176630 543349207 1221547272 568350171 835437625 1522486450 799195283 202279498 368319992 272071067 362058047 704384888 293889162 686686623 359364030 226143736 266218738 609573830 1181500660 252551116 470548646 57427030 779737090 768338666 353553475 512110556 618014869 1090531263 668013194 1036035905 712403974 1392995678 1180010610 889560911 641424802 294983409 497717318 729362302 1044558292 124903483 1300195649 557078889 929403248 897521214 1306003342 352037648 38745091 920047832 404338737 540378558 1037188512 251060601 172515416 279113388 676862193 755482260 854933877 719077660 592245183 575478529 591320167 1239876435 237355030 373304398 800919452 269178943 1128431275 381893560 446920565 857936946 889553800 318054126 1625412484 719296053 226340562 924803591 567959680 1109864331 683926717 227894709 445332383 1031730439 65559258 399267524 556682329 562561252 994483840 822541508 911586835 1072572152 239056168 355944640 496919877 748120042 259923887 577950619 828011822 444168940 590297410 267440389 63734123 236700917 319626265 436052991 1055501829 390083742 382645751 375900481 711025154 499779998 770127893 461367336 912494429 1024102979 484721340 1075337944 275203156 732501850 870790552 335820235 575254725 322231090 842158752 642039192 800865594 200899709 690158230 673674853 834522657 1350332213 579523527 197873312 613146257 583160135 64855205 832288332 241387321 893249845 885049676 306377719 557604763 1235220159 662321472 444953483 550280838 1119715658 743516912 1203049464 523968335 203038331 699347396 607609973 468480183 387291379 862346687 472217109 316391366 350976168 910724422 583280304 175102510 198262550 697488146 996593178 277893884 581183251 270144942 357236360 446874720 1122278777 374438286 245444405 1412123616 360239823 1006821036 534576652 27506027 666424824 232944506 910419163 435160227 108302018 417417148 450982390 787067481 513504461 764051655 357587042 115931845 498841017 191013571 591947046 1510614168 154814708 352998279 904938052 1104893685 253925726 784223658 389081910 780098465 549731439 948339936 362714656 498617675 992424126 895241332 933252446 1006195758 603963550 863915056 301820806 246485067 342996838 496315946 699656167 692496388 640925184 1093388445 527503365 267673413 618320898 270749670 496585088 466532998 443991854 648737739 517810518 128942224 1077663660 238545272 743952412 407186871 30492498 290581752 784622616 1098010007 136497536 523749809 641760456 590097939 783592148 770156387 618108278 522183312 667497369 173535723 814556334 704189408 807329171 344782770 904216182 371719556 155586157 636166695 447762807 627202890 970918803 482321192 433695626 184070487 253958523 652402544 343803474 498757692 365895279 863141738 561075829 378399865 840359861 423564809 551993892 235138150 902996192 451722929 831357355 157073156 413134540 722482222 251318184 582456826 341695403 516892824 300500213 633218109 1205454365 294900247 357185542 320344454 1256926103 613499483 928524956 1520737333 358617198 896103183 625168915 468499191 797493005 150821484 84372699 1097181039 409407754 442075554 923040504 388608466 534046589 1213969188 548112529 425323756 368892153 617161840 349636477 500859938 347487386 596227163 726857853 531988387 483075478 293613962 662323339 505035346 1526022510 735386396 168044828 306539692 516985486 457689092 844822526 1115708917 780081060 761979357 627280893 665525507 652181289 562589755 114434893 147115509 228140983 135649781 1075794548 254516176 228713143 730047655 1214173917 153146857 750401410 506183689 103161132 724453308 730083147 399381756 127770923 410176857 940902725 420673340 520062183 994764523 511962144 539843806 421999589 834129401 472407108 746223872 827017408 352922185 660822054 1214206293 1039876145 346142378 696553589 285462249 1496318894 873445879 551326612 899822569 111014682 690217893 370296263 1067597227 162900140 1304704779 150153422 884151302 1279925807 286520783 1250333164 543598161 273148659 707458921 625220052 491492432 355288854 231382092 917327367 456728241 455051125 841304056 503296891 914433272 556329410 1238311402 514477235 1107373687 819219174 416341287 74776670 448007447 297371508 798288924 1166447754 271159841 83560990 262358097 452705304 1202086879 1399265257 210705268 745382251 466351835 334116535 308543261 773391801 601748058 396895908 494529778 821627656 422091040 881179537 226554206 1067765697 811821443 1461451301 804572689 238379276 1209378425 1048126126 260476980 556687599 425625843 746780026 318947136 736540571 365437660 523133685 735077801 866484016 1291933973 307614228 1176097801 456873566 563950776 97651790 236356827 739095946 975490548 278303119 506153191 931975887 993138122 136407983 401985967 630114020 901040206 987978233 613928776 591833358 230493374 463462346 592904020 178571700 247071899 382047810 121178338 357639602 329161776 304743151 853261758 244552423 923395098 472222338 591832038 241745924 640130714 683317030 783474601 438009397 1129530700 413349236 663203923 447343623 1208507739 439717585 352792587 232671462 699015075 309898058 408201312 731317348 371576871 121151812 377620472 84702523 252317612 542535513 833072224 734701509 798360455 795842166 478129215 666964891 661230193 464535868 985101217 414682279 607855563 636785213 383121193 275130743 790781424 496761363 749196822 672055545 475113341 193534374 815176836 230430778 772735029 810486954 523065486 577771010 446855413 470655029 735883831 883504096 284680583 338820337 985670055 283926674 674433175 524219722 1049608796 1080112701 480256074 174715994 896591890 1195810132 1115972311 712895810 687883090 428154155 98605511 298582694 723279263 269722022 646835260 1294771280 1283908842 824728042 502411866 1015479308 194415768 367882943 265636841 533475133 776591603 749075334 813325793 168761277 201443534 485160289 861956575 1109094648 437650628 210370490 530492614 404832835 36881326 111354433 889659274 338075998 846495890 312381300 717393476 535178654 44752166 541507764 172252225 1093611099 936895476 358975154 931749378 612432277 495793945 150426182 1879414741 378391713 336279933 216423331 543688848 704797340 936704016 1077548857 521909684 691681095 243106361 1172235695 397648271 835456726 1321040549 393868002 1078704112 807543345 448826948 329700090 188156360 385678960 555921502 477757860 190913662 830731866 730977538 821347705 743731144 852082974 122267463 359945664 688540214 846212412 512930210 161324730 577470685 277828122 768995130 747620583 656036589 748257588 670739902 691357568 427172293 804513098 510890041 468156845 687017811 472090331 797659845 826153388 1092862295 179626096 257021601 988907981 152762175 159762906 185305060 559229035 912353703 322815990 587212562 779832644 1127457442 863516857 1045755357 191897863 1233530916 65848405 824693486 1010955056 901710762 299716821 772878346 388841926 408061751 80321603 513988291 1444269288 191590971 418013343 573426981 686481148 206157175 513815601 435111767 520162973 478256901 746118452 736829493 1476932838 42787044 356104948 259188530 613605531 651004288 397620041 747825857 824253985 1006345694 365635562 477331826 336445739 293099958 546716546 512925544 151549513 839912876 679783500 1315227790 373926863 1241386156 472970353 1118584287 1220063504 703721507 990350664 447238808 311913438 341844799 33480409 421765019 518937706 787775012 913624031 1053302089 680785488 751657320 169489542 420380386 634898852 1280386022 223467330 244049087 315708762 1167352049 345501595 471949836 391645324 500443946 1355701715 368739082 532094547 869456583 137855399 211712217 791388832 1212263120 115105551 547046793 506384361 389645500 396963040 303137746 286707556 392116150 858630994 993144770 725955721 840446151 766287950 817655718 1130643153 309394914 607676755 413052227 178131639 452116343 817769686 837761187 404409207 758412409 206589686 668083735 272563217 451824651 398889129 382828178 1130039741 218332488 329396422 871333901 1475819274 326810942 880377632 411029556 298244044 545307266 410606060 942492602 511687092 1034161624 335394840 488031700 162778026 902621439 615674405 395727673 385369588 607759564 111479659 523683916 162464883 1272243294 570206067 876999276 450058249 873457953 301094730 1067984270 479902477 442360626 341555211 485004711 873207258 753767586 395199052 224932158 236640799 524486833 351255415 1034469061 723118954 1223458485 642880996 616190611 765695240 1475104146 980163313 245547347 345114815 1028114442 202430054 460347128 564722656 988444050 744827278 969452347 652764715 383779162 1326597670 1125873364 99433954 878851114 674628993 186280820 671190810 380878270 591688388 69704971 1361521252 318715803 646584675 395803028 277261301 447861960 701686741 241991024 617684154 373176121 430208908 1573141092 299105332 746071833 1088520641 758025046 343424509 316040822 127706985 465443106 112321074 1245422465 660320639 1223959390 479463130 90087022 279193197 855686360 587444311 386148274 93581067 69330978 605650844 128249401 669581569 1260289817 821619474 55682539 1013284429 394221605 268686645 422282816 687548573 497253009 852793112 333965045 250053740 678347953 529451731 834555089 777090270 524272004 410235710 744649702 878953954 113052016 872256191 830598329 529064551 273033512 333777438 714965912 434376962 859687214 1139442297 556395323 416468184 287159522 223014464 1011949771 943747995 627797502 895116707 790539855 913260295 852182934 334516612 201764310 944215604 474620804 194706187 429639509 751246010 1065764497 805397202 678259033 793374907 725826616 777198353 1417861177 723244696 406725306 480086979 799257531 365071816 740853573 902671693 678089878 395276964 1012445500 571206468 274555497 627208691 562526795 463560776 92551959 482026185 1211866104 355869195 640454467 726391223 1047125289 986452280 847922008 389179398 98657537 1076286629 646035128 558224679 751661912 428204413 924978395 922668642 257476260 463033081 164442604 306138557 434638920 1417105202 647451891 189431128 508508128 996865656 1001917841 1053727710 441545840 107925576 634948809 743697870 1045337933 1009059353 631136467 275831106 318072816 188675034 593620175 791164893 426489736 1351451823 1089475413 735693060 163999901 675314344 987883908 684258773 725819903 1180823732 334166518 1406252465 532770480 641449473 524578907 462879772