1654
660101481 273261451 985223938 316971770 262889743 216837385 325436346 808941735 948716368 902692447 132219491 313494624 643910024 13862614 312824859 609787286 968430882 791271410 646373525 184130305 661393285 7272903 785248218 184000028 736508993 782348977 343411972 572870210 510013693 983445124 392932035 480796765 383541010 395478481 830812579 537308414 197319488 513128039 833710890 638379351 830653800 703153373 960082146 240949049 487340322 535979875 919279684 455475454 756351874 869797932 26389870 778395301 983339173 235293451 342525832 370092575 923422060 113178880 284568074 159386264 930838995 33236188 975229934 127034973 477809613 363466082 592475474 85021235 512660570 179305158 655008182 945639996 259383409 408623685 456661819 853760381 791274836 586091383 386360735 714239369 588755390 484132972 740000379 753516784 614192678 171392252 688806503 835039765 983455305 90252680 272284753 760885837 363028590 871799474 240225941 444683580 565842506 719694726 811229560 393622530 485080058 2646713 242986904 220857358 830241636 11314633 139182072 717980784 398737513 672891763 437817004 182841757 951267806 601104484 460906952 350251364 576386604 817807762 377184915 9575376 35455250 373540228 490008412 266086645 661548244 972870355 742761580 613355199 974932925 585621884 416787994 529619385 729668991 610288382 514415136 946008576 792364451 388551709 586519695 809263484 132255221 987061337 470777152 186124537 839605341 483915389 577454346 66295131 266785766 760628862 891311962 222569641 783553227 991627705 263230074 909987139 684862904 402693367 178172925 252554861 151906129 765442797 665918736 948030033 820202902 614019392 149359609 379342065 8338046 354149184 602781871 907457480 146262703 487266096 102999867 154506128 458590455 714222004 444563422 784406372 275291261 763950735 30729304 29747890 198471221 371537687 724545688 555958786 299288425 735611545 302669362 734276941 528879218 224128230 274589001 873209051 149064317 235965846 378652977 33852873 946541046 682691862 32608927 232147265 522409053 507328659 889362278 836247640 228111571 542586815 508439417 537239178 362492512 986089336 93902480 972782960 625935078 416878547 134897295 629290775 566308532 468632210 789931783 578241199 584700003 943685073 75517441 339855278 503024170 676186086 254162801 147487806 940439652 382726340 564260838 932876473 721957995 807320116 655047619 956863295 397954715 504643122 70840109 415422153 779636437 637704357 257051673 920840516 49446903 375206521 982415611 552551401 613943399 13380783 603983299 598591055 89443224 786750008 100924635 212429355 112538688 660069141 346471225 290767591 866565794 222486769 563805136 436920533 464295576 273342372 702264480 201592305 708238917 458529340 632423048 705176108 135301934 561288923 926686103 235381134 887530861 337931614 332022306 239977783 709581357 698222493 872904599 68726380 310489679 182010336 498500054 811774002 635472788 919508929 514842687 766239517 680109095 970761233 812644059 45713497 464880204 462679748 366410089 158359624 336894266 800085197 266155407 441950607 689410077 172439588 532056328 636787575 893195276 417656346 460616885 151937936 123888039 825720199 573952456 876153542 857334509 500345449 911355497 972147418 948932632 168145575 146574125 762742931 693136138 194783224 671122940 694705294 406533738 96973330 780355712 392216820 615133275 609479294 425366524 959460273 446304763 225871025 755660409 136355015 118217273 451408450 192146065 368138834 433854060 941466468 237720282 97647859 105108643 111282286 91854531 809853652 29459419 104156049 332056202 874457277 613390861 894704645 149999748 914317684 336216591 359681219 617437168 832406037 332266896 585210691 670981589 576520980 708979204 634304750 83204735 141683972 826904068 82185316 272320766 56597983 555640180 904698397 699557830 304985703 376996038 443290887 268826866 913364157 440953880 245044453 209935266 710491823 51274010 355083573 278155416 813007144 662870339 685402996 187436422 211099169 510151056 107185781 927969029 245757635 300414296 112492716 984038552 519362247 190439017 867284441 521172633 383873751 40210367 562319906 345208121 469132180 631123281 43594070 242149864 362531606 51988384 827593804 450360392 77301550 35870829 674511000 878095739 756673120 930044982 705910552 233819836 764442054 111532737 255573339 811414509 998394238 544269079 308261514 407150364 563292786 682483173 461447851 178906213 598540938 310231525 717489688 482875127 454481673 345453268 418903566 362801716 339571991 210808323 68068279 723129207 790748584 492918143 812847733 18145529 131374905 989761059 536809144 324906771 294362594 924534385 385453058 257371822 88942754 947893806 360895791 107113980 241091564 327311471 130527365 480635809 76571138 433339194 14765184 810850425 101385678 789383944 757323411 989112733 541524423 849101967 385251521 819096829 894420295 92770198 871083036 480062742 797352752 621479788 292643569 678975782 197621748 503639469 293704166 51627018 715841128 462230529 86870899 285464973 373851777 536504447 170439620 415821536 5096336 672846357 382220831 826873105 468117806 691696607 950946914 706188767 865058666 194931301 828941472 43813546 359994300 788211069 923806619 458506847 900816034 776539936 717940244 490511673 603408542 738538174 174610831 242809085 74881378 276699530 493303449 520011750 21516363 218935952 991606495 253221838 332434363 102257818 548115088 618916066 315297046 550973737 74226877 4767747 16934082 557064832 766419092 806222847 397846813 22279097 928360076 316922640 555460428 901836722 674787010 376129660 664846807 573967620 956577779 166320608 451278649 264378786 392212694 980329548 562393102 959682226 612264869 80655812 810501301 479341465 448532965 653478501 38340897 603384516 38155347 601810673 490639798 471739753 495143153 510982529 856750768 622929029 662575011 711444407 932943537 499432149 598907009 432068975 161586873 294004817 998315862 17180903 730101486 77478334 492251869 675547550 943776929 491327976 870239416 635191644 18270511 316122972 638800902 610823157 743738740 779418700 447922802 392740555 169025997 376428172 557630252 836957010 480935735 421531441 802787271 716104223 36498287 897538136 203765066 210500501 245152141 10398462 163622598 20581100 989038082 379701916 745623624 2535131 800002450 192340830 763196424 278246959 774883571 129460006 881904298 308435419 788648518 76663483 844735365 366033947 633840785 358624796 430651410 562044405 883457555 351837366 536991556 607082341 627888295 420801639 671508845 121948288 115294353 10674426 134351066 732051843 813878001 873159012 350383704 684918252 408336914 328342363 779028052 295618202 222290227 329107233 484322467 714028683 500775176 372615940 627786986 858746175 496315520 878704875 485000920 121493975 785791675 584233975 175067552 632211160 270923893 133095324 712107791 893801051 722340682 195184017 303437094 212574795 53079 859038922 585666468 916949418 629431845 165999476 788880882 400592829 474524929 233777606 677951518 54879563 50462721 260059417 981846311 980878821 659699196 989812908 460627726 936765088 737254354 535808363 51648522 284504236 277707206 148129726 810539832 757384011 200521412 341631302 576411761 330087462 3158204 548286276 802691053 54528729 845294142 163887268 235327370 461876783 421285045 965129334 186684018 360865724 262076357 221759704 986482676 273218843 345285107 627978190 986770153 288554727 36021908 348445413 213327009 386049212 341340541 379776937 976502253 144858744 231501101 478328926 949044838 616444375 506181856 640581511 636913250 72107286 963255668 927921640 863300426 671214580 338326131 413206139 590797684 277307908 292643275 978529978 270689699 151789238 57812872 640884713 455960848 678806385 660594397 42962744 597620536 608547645 628970675 919820556 870088824 357113257 257757421 765027627 642238511 346768132 951156147 681658342 593908330 159047369 982237391 596619761 642444352 478708622 919397180 366197978 291325342 319272791 385454166 78745654 887018562 421953681 325371146 92601761 983779168 801108399 713336768 275361534 888996422 128303171 160992576 990842337 756947485 444546942 56510835 248415003 284255109 564668059 51891536 151582860 691869547 314800318 646166521 970173738 588349636 242327717 137715188 407458605 164079799 484636866 746899869 649974164 357171711 362572629 446800152 591626258 685100409 52213471 881014130 997650313 629416747 922459386 752046032 370374652 906785937 381511015 184022203 522090996 666956901 441453621 344947696 451082659 221835928 827519422 137245056 109791848 999186396 866480779 550857298 588416335 71681275 265171601 624084502 497536977 620688992 460666216 674041641 981386689 976234625 882068651 649573883 234804915 807273510 379302223 163980849 510376870 261365385 767794824 560483981 688541955 767167296 110020433 607713684 159892607 101398787 747016210 263939656 626944678 410771322 664505765 718412193 559545054 424218589 167195784 510349983 402539761 936848500 63669795 383037456 94518761 84559665 46368765 252233471 270006218 311536334 830679239 140736665 412242684 925335379 41273617 826604764 733799642 481497797 281895109 38079020 470632273 551518106 889737075 297761718 106554438 622476086 109943691 537288495 188718026 668247680 33201792 967636794 987347733 740833395 94276514 696937053 396809527 255374774 89832321 265800634 204625312 887403666 183883377 854982917 325533269 947424113 169766290 699238291 403630684 74452959 691313314 36674319 752022956 739850275 957279308 519664977 584589364 147812928 723773265 364772539 383225190 984028624 918269043 355361711 958807806 550053898 587197850 305983928 529269694 475656867 849729952 228325131 754631932 435760388 714744579 268207477 974104318 224941728 756032231 892483968 84940477 499534807 892700093 474818806 821188571 344850175 988395807 116745879 439883012 506841685 761373998 758956976 19781220 267486815 465476499 221679743 705941195 269333574 823181116 834991582 39178965 764641846 482155833 768772598 917159259 129970147 157761197 26652211 460614641 734572334 669959002 186322463 924381556 496483542 42733145 909914437 676308229 847284571 94955720 902419365 497879636 600175550 404159686 221542309 601473023 964601227 98756242 724669481 39840233 449524747 760572746 630244457 666080114 513114566 427432714 789708719 810245417 7551385 385779729 323704282 985404217 860049922 329841255 933161473 328393452 23151304 295621084 201022538 888336188 628188394 921653893 717645766 711148454 693961178 134389876 260898722 951534804 954275095 459068417 523020661 803320734 571940573 784520041 924088173 936941815 603270495 629060211 968334458 13990125 824704482 24616396 92765951 396606168 709370742 334478775 361202700 95862600 803935500 856339464 485410265 747177813 537757521 93132982 586942320 827592331 425028849 392131094 350762209 433358166 810925024 822906554 69752967 67507685 536587241 615371051 637098663 965841677 376705614 436071195 257862870 506433879 778685169 563176245 568457715 63471012 402839606 26626141 310248201 415705811 431751656 353419711 827217619 94791495 881260478 455321378 848832625 522864969 575781345 859301081 137099116 879637856 791626211 421481887 943749118 177386748 675045298 139505528 991991324 700316428 283097594 120850130 654949010 189086689 563405984 377239697 906874283 255454560 93217038 296700505 56345919 926122438 192450647 29065761 414516075 421876782 248723608 720720146 663744169 627043710 822141717 709815822 580394179 114926966 335845312 422700923 141488982 545064257 425360566 922971448 325250517 799379355 822528229 208729560 498166973 736586395 682664872 266158702 401268848 110441337 166238159 508031299 204457447 834392576 141182392 104626415 39024368 886662907 752188597 290431753 616441331 574321596 591795612 774532978 888849871 748839544 934050012 759294727 305902681 485202852 164994835 985940399 379861004 416356403 73094653 125432338 540882210 607380160 670703183 622158822 311717754 49397255 994711367 425032492 602952340 364720335 549131957 621793661 887133243 918557381 348348759 130840814 958284982 504273280 592305158 705739691 950606855 651723490 182153615 828846764 616289064 866547518 12047646 123492023 269537770 443399770 537256140 526539408 451333905 999864976 268654495 214919335 588814864 143813691 29633381 141396234 576774110 553465996 364071302 109341109 438108115 386203776 334708135 295230182 35812599 964694110 662314966 913336625 522645674 304420680 71218475 145635955 273001949 412184473 887056859 576780576 325706050 888513985 810654191 504739231 901178783 79520916 344518954 488601058 452654677 136661146 42908594 889395421 349660686 937143134 350182886 446316395 210288733 897767234 501201317 211210991 650278129 690261010 539991480 364849099 442158331 995225233 128284445 552127443 27847485 690784061 330205623 472846577 39469386 850641681 68641555 196153950 179834932 922314753 673695271 198532768 734359405 185870103 30036963 707998368 909659966 921096350 540349973 625329958 144982027 709912102 169369575 953572288 852952046 841725645 555879001 342929214 679984661 370782442 866644976 229734845 970592105 509137597 824935233 874411536 231240111 776229438 918729474 530499738 722219459 15649275 416804767 96724946 707517509 337304317 229273373 160513316 543291588 207394449 771282204 492799397 508994375 118882683 275230352 191129288 216124687 847020125 708574360 818305209 928400205 240941160 682933685 743299921 419844042 463351274 608636167 86762918 684681712 514852080 318208746 642615018 147353521 688655382 948193255 199093408 776916221 596756797 172012449 604670747 764039840 289688640 958292438 320535216 196276484 884708083 741669603 398189764 902445732 468689814 867405413 620527768 212815328 252376996 659417064 609261151 623998808 737516931 952580048 832795666 128970222 98196694 299821041 994030779 661542898 891536376 27526624 317377496 892948382 903551845 585508777 472312989 672198116 125588229 814254661 42547374 416921124 724175821 935182773 937659243 748658000 286732579 290143658 202564057 903534521 279141650 440991901 386659880 513502675 856385641 532878751 782861732 566146713 401758053 695029357 947868773 263149193 153759271 167086860 948770696 81674299 649468495 832971888 31800245 631626812 364550803 33125012 607500031 666743613 148136745 808903740 727455447 308384518 799507322 184606952 476545793 892896418 35245158 468655441 717282966 239908204 889521734 984355458 436060721 510227191 572611723 181464520 126505680 121712465 619675338 955737469 312267744 695554354 28966001 135667713 609541200 141409526 187080126 938639743 988096593 28672503 534170121 245842901 89051655 70362697 136323072 131447455 548854209 322557682 162849154 329229053 624698606 963501478 726655135 678648225 31616365 914913492 441990639 860698584 966198256 680388533 789766262 935763461 554950030 699144061 282267759 628484307 943069020 995614729 56143596 301421447 410421527 21815348 475787524 992344326 773141083 436427074 240655505 906861964 539309578 259022308 964000762 504675087 1419182 689788042 804701391 375182720 372376089 600904236 628222481 116658535 451242416 48628693 456884220 101634566 728023328 817392831 618160470 328020411 88063477 923386176 413352078 336164044 971523980 313912543 49669086 179261496 751712936 86187481 759778053 335767713 713610418 899572362 622506711 340000290 851417262 247897317 485353308 14433503 499858060 888206412 980577902 134285225 98150942 638467628 31844668 877947842 726220965 130482501 395372631 625425529 654772376 908412302 242336899 30393991 629389054 540145176 609698783 112223207 594718324 411068812 313206014 696504489 797190073 465886127 328588226 124842733 257202740 845438635 184498626 247072432 549406443 602270169 338709208 151739709 76545332 854374594 492643010 702776893 982149072 888301004 397411532 233086647 83305929 406608935 106119172 413389090 160171985 711452404 730912292 717888339 925117676 869951470 745784186 353774510 684205621 857472085 913868420 406827561 764125746 230216545 970524391 600900863 504060166 739059134 940205060 323134641 513189842 105107903 807589852 900674936 634515362 577096306 500954815 659689232 391315249 466509355 612235209 837286062 314608652 304210067 336013824 313635108 454991772 832575446 902690810 347742455 334272801 106169543 806707325 528782601 191511434 535142700 789352356 28002498 874458912 329273726 843647311 719241074 798644946 89414989 412973922 674500234 249258475 921154109 666623413 774574268 319856614 233348927 998565657 561389343 162125700 621513675 861763941 400991285