1614 1
896906764 823413069 598040923 821029960 458508545 825086407 588297762 295349444 306968040 870560034 544211417 758475844 58939098 215575960 213935914 343168729 768302014 895254715 483902742 95887542 177919092 159984439 659892651 846006872 147450573 848401619 665216236 486976967 36835027 296277513 444409271 595412411 432138230 899877557 413264191 567124431 858129520 713389244 641619056 599994061 437715141 12588883 141722105 595954504 107122405 806751170 345994279 393323794 571699864 954667430 841818961 233713264 946373527 441439347 968323882 367682041 718722278 992310783 487496807 408095513 678972645 214583517 978647655 208809296 54230878 106874503 295656270 829386639 520818963 44923690 384375998 155054533 450301112 205864395 672279718 563450780 404817087 207154384 638897382 612512124 942313337 614285530 830645586 605398464 265503013 410535693 477043594 443866643 754848448 975544109 348425696 446548761 189404709 378970657 871643250 800748369 118900819 516776826 496186855 750253032 452097456 810850261 517688318 107885982 952501384 29343437 878321824 22471697 421150403 307148044 452565009 509079533 547028774 157486760 398940779 222828482 359449850 983964201 700813491 530628207 780804104 640051905 813826796 56648886 844047070 977546348 671804471 836935478 436195245 723633615 132248625 127047044 222730377 384915254 738893944 229303997 7604529 547317884 498919742 685961614 270765167 903239116 226703567 263304915 769801545 2773451 350113833 923985503 181402203 146790568 973540035 426391660 949836876 28147752 347358616 78552466 234935890 746813352 201534292 291159625 970308608 447123317 439769184 481762759 519829545 958435130 942353842 317404197 549111470 974381090 907484745 157852840 942250007 376413391 933945511 474816738 537158013 795201314 498967977 13517575 833892568 12487699 478165667 200898032 74091990 521629220 909413396 942359470 937585923 961967735 404777646 112620105 31062552 242896099 221987862 772807028 827851915 292515791 52578161 597281999 98712520 230738691 289898237 75935420 956241454 805174948 387075188 289044334 293486597 415394808 704254626 735939404 187570802 615492331 376729866 806534007 250327017 530619930 878307551 954207453 660755066 539366349 396437845 22401760 629346051 9123567 376605906 46150018 977297978 211342457 272330091 130588676 544432026 479107993 708340065 52414239 662684842 38015494 42184795 953868931 696356477 835202327 74974989 126052253 630245605 933438047 189679825 573545030 655271836 323955344 281441928 3412467 44763658 868555542 638118822 68228886 906902468 725522417 74275199 769696058 779613597 566729075 878411566 206189421 868895833 912939358 131727238 577894624 987598441 532452116 664552855 116579969 144628149 504352696 283552293 211835487 303335099 326558590 997995354 833499156 633742060 458600158 991338658 146558388 701478261 253045139 251402918 221271401 815832999 514227794 541159852 212765262 729223821 26000134 515856131 404062657 705765709 359478053 713756384 553788277 280841278 813719536 130798770 266526673 783764141 27566364 88591534 31642002 628390011 943701914 524823673 261000743 939020606 934264 148734938 417728504 601554603 786994079 633795093 577948879 576671364 94460505 821012823 636339522 372515149 353684881 202920394 408950946 737508927 122632143 359964678 227852437 347003363 258448707 723431318 5735014 828087429 895164957 503852089 812110311 855571288 61311003 630448530 47248632 428071277 730973166 245131739 755644067 640445270 59424849 824186963 460121619 840038405 409590311 831265002 548409284 421587618 170775797 534507672 513702302 370360248 409296394 56573567 366522692 637073005 239870941 460940762 539006820 140406688 679990018 274027814 129302533 564995734 512089379 288395865 826046574 65920874 517488655 970061335 146151828 934564014 513164596 590141320 227563955 524020734 461094573 244802821 138227796 255326813 211689517 484103302 793360653 479331600 91339135 316688993 13306317 577880562 730029952 692608849 546532396 478254604 608751675 509822104 204444687 983148305 218199461 714068627 46324601 847035312 120953912 5655018 668878377 676030821 719761218 501095970 836510795 526285266 260823801 328296227 764525567 403930991 224360075 688964815 813104567 583935041 518761590 278827376 106772814 227340087 814112032 952874178 625593940 274022134 565327629 458170074 486449971 235022514 849186879 490343752 884966180 749046708 885342583 135573601 453051134 124467567 636417567 481332136 484491081 390174130 193289677 806070229 797868513 432151724 347498946 737437307 712497904 472862648 530190357 322513 926695123 617259913 977525993 257223456 229511754 518514334 290858520 741236253 850885583 414812982 999921245 302094766 620432545 235978440 773752861 724023846 977141449 613255555 539824150 295564250 951047561 239693907 879880942 889289146 428649685 336987465 441855617 969454764 392709225 746131126 826491582 212700669 793267688 466921022 480254456 384201296 732654361 998208084 852407001 93602677 905816357 182986968 597142914 418325031 591582650 533695189 981653916 114114641 684269569 325001106 163923695 757665816 26188872 150540210 154352010 607867898 171765678 712438751 486007367 435486236 270918473 914612242 699764324 211519755 587992299 862497370 434296168 381365198 981218683 401706976 55943566 891277378 298383316 792711056 632676976 207158763 904357646 32568062 332446975 994672391 573108022 128316086 691983465 353777348 443153975 419839028 360722599 822966277 30406347 885317475 18183987 578439463 757454636 693864076 868962464 650732373 841613707 127108789 412531025 333497566 586411847 480389084 301016450 374698565 636313152 52722088 104340578 890781438 266935022 535737182 248482495 327020858 680970360 700693887 194044761 108288911 17918342 949215351 339136473 300357279 25488164 412066980 47223234 773101001 199180738 961670298 90402226 578473017 594016698 160052945 258747379 792932419 274727803 397687312 54204383 57511256 163117377 368404635 214901978 936551833 7344063 441687788 326519124 601451416 770588515 25631013 222338990 52146806 19922969 343604821 519030986 694602969 224603906 601275942 312289558 628145257 219718893 702959427 347579848 560487967 800797163 977914494 21781603 922429697 643722317 268404317 467238906 531462276 183497764 983005441 304939287 364957384 281478582 150605401 682080002 561448804 265367747 529482424 347534359 717982703 68396413 232694335 439051734 192265829 958052765 767276381 198094886 717773496 862715025 655338354 844791925 794025811 849781175 913255751 639652344 487536272 713621494 277659876 162166403 663285936 588794760 159513313 359096247 996792376 309617879 889902754 380158151 261461291 749126823 383526509 709156479 45892762 70283748 286207882 202940205 970621475 295696905 536262462 737981437 279527447 527819614 501694343 329612744 388569956 820464820 474093836 343782629 308679328 592510285 377750175 221030466 616167904 224393355 803462071 787652651 234823833 912056708 52374728 180663900 413856507 414459743 606881441 879930275 749558127 447108619 933399928 253788436 93092515 398333443 25181775 774317613 615912944 220153786 201936515 142526484 143871186 981603810 300047290 720448693 90151410 326913510 463577471 959161774 416003089 24257939 654381435 540754991 98878599 544512805 533145385 567842256 540402148 160448978 785178874 120300774 267113644 259596567 74222045 762744772 380497408 831345946 64488892 949913158 751594019 850327233 718134622 565860390 223191691 902095021 501947474 916687001 538453584 577998127 258583270 428121298 873461222 149397556 55948954 26512640 391112799 512351897 808449356 393627907 376339395 274548141 883867858 20001484 137070474 99008152 365944887 840902181 368834037 410788282 373474312 427470751 720395364 962302214 898927140 526741468 495970516 636745336 373606798 948054738 48176454 592039926 565354439 439908355 771547784 75762382 249733335 485289022 140273771 8796225 578786823 227095379 759990172 513434368 979107147 200917334 114685743 909230160 255827913 964893877 654945875 490561138 935028655 168360259 484558498 177121946 190836706 394542133 401064210 253926439 514235939 490805950 593429483 757967353 97071462 710263924 99562899 781535583 951521660 991894330 555072724 923258913 981703400 455360604 603999860 151246515 574616063 728827047 724492962 386632578 567615648 253138069 493536807 570523755 901940809 91555041 677137617 996265343 572420451 712979865 305461727 797235283 958613086 832004729 669862787 158223396 910702326 271240765 395108083 245241496 41309774 973395376 89229866 837409329 501083758 574427733 374255406 565649235 733281598 519595205 386815 135006161 521347324 13350159 965817724 191880210 625528747 547879341 532993470 979522489 134457519 425790948 752683721 984778264 812074704 679952137 935029355 541591956 661181783 679006921 895276043 332997182 747105138 599939262 791523598 288113990 857968496 399519772 803260386 460741782 532900221 369585466 559448085 514866979 536696310 114689109 107078989 308104875 96210616 893877980 433128237 961542168 328823691 643454710 506590968 614035255 486116047 649135996 444537747 693020650 31388312 969114771 263067973 794257235 905153791 79940947 280942501 899926749 620180119 715968776 363063582 705385134 120017298 828428754 493984041 530617871 189610968 701275158 175498745 480036057 751838963 951995715 986575900 267643191 484614679 963953608 923185950 584511755 587123378 844887599 285455940 837614655 736625724 961573273 118514492 830967349 952280324 375116142 9113244 602090315 457159290 902856072 577743659 699207370 947727565 658211287 420713686 120136549 391020612 337959096 477179943 486864255 813854414 551433965 349828133 404480262 576584161 832127206 10016563 956283558 176316633 555624182 696388997 988610565 185080087 957297309 420096580 988587108 907609453 58523902 790560601 959667822 946429004 960311355 381633373 895380917 650947149 851568419 719112926 472769038 724249162 166076089 741598802 775277082 657028964 639405975 64038183 568221581 163978835 608335840 411974521 351679672 868428910 298155918 819072658 733470093 236868685 437284171 621238092 274679234 959110044 51126254 716871569 607309163 807905018 232619608 127719133 217673737 645846758 444512889 575891435 388082937 325385058 690340993 130881152 173843249 806385122 99111416 977093959 96999052 117942711 851401694 75988276 609565694 692373019 569447907 698900616 193217103 326797108 977274175 233509139 388315251 795081863 449698302 493387325 817548718 465952666 455413914 572087156 614313893 979963534 328676000 942683706 951715630 377575809 162157018 555608024 693136829 719643078 217158103 678685586 508550348 195285616 918045125 578477427 401144382 326321941 954489096 609579379 471599048 916801870 552818040 963979667 235456004 888255081 133869948 340874561 475246679 209063544 272162184 460854549 591319565 213788093 929912789 961748183 830925920 57839659 336331371 7188571 422224590 3234602 193986384 387223508 58489699 532673220 22120526 141966047 502108083 791072904 325895555 707805086 204163799 742395826 263158789 219585998 777390870 646241932 191082327 220773667 515673622 46173484 327555788 467576004 115271669 87139875 676412589 350996760 887724050 939410388 782173730 931193327 199001364 889497808 915862780 189634884 98522443 382079175 673436392 557638488 583256482 76524574 863109189 147154824 575262429 283046187 20196697 819351773 944757885 685384398 473475930 211083572 310077557 413750360 66663866 287479248 930388773 595735035 643503099 443393847 752313583 721908422 228500848 9167254 342529457 26948323 111686503 634952689 193465796 658060686 476485063 451345603 180261952 923952242 313379946 569959549 536755046 700197202 996838835 204752721 420358424 523695378 6091246 350015324 707021264 337287335 477927510 527787690 704181556 15829829 107702467 344948342 415549673 915216222 53638138 453636756 631747438 483360771 361197558 36649580 873884349 998747621 272398506 887342791 585581728 712080249 965622290 708385604 118748757 350390552 312899238 753027975 984908724 693396106 332799616 356523059 458616931 544410062 916918456 283548121 200434433 774498934 890649697 429729169 777752964 174410485 646768672 254508750 749419298 485135629 92868340 585750432 80113857 711067579 571539728 596572475 118601888 125812647 848691824 317141479 29236372 268580144 557531662 189590661 415830006 111662731 92973583 337389515 701469853 421740120 467230530 806463287 459076017 268041283 587289501 838265461 453550857 717053674 9787999 957209479 451412519 583216536 898937117 286298038 225450128 551588514 540668756 63703231 869771160 187611310 631502760 272498249 986746111 200067142 364546915 21207585 696399222 488933624 630204950 187311526 875904297 987574278 99926160 941005483 880853285 239232266 794676902 208817580 531775755 507988430 392801160 300713771 362414399 130642241 76271782 644918971 876852707 489019963 615067033 210882294 92374711 451500748 484354805 950052259 492291513 398091279 297732957 975036293 683457639 594813519 417647803 325990325 420614912 412700799 699705738 885586632 597269263 755808796 709529422 920806577 683416458 748383371 291721247 70827584 620941643 605560895 201226898 528920376 44647397 384948664 562024226 687298189 760960471 111670833 746207725 226625360 888934292 276521467 925266738 348150245 671640549 950403224 402523916 684585398 367359856 224077359 729832564 366298793 227367539 228838505 451692985 561847682 319953706 842054126 601296510 530493414 23704386 944091364 687643844 880293417 925328325 436797899 756790449 926255598 710710281 428224504 373313357 712981035 57020644 733090259 940196030 797203138 502657163 834892611 975996479 462222361 152979280 510834270 38738654 24147542 919010992 978187937 996393128 146109126 291325751 135383594 703857803 147018094 703864320 947058200 983455210 636274429 5897412 201498256 283508065 290826545 37246248 848937282 883121260 464007027 632462465 424438452 95481158 286417536 360853219 158241612 451137601 913798403 749027990 991611453 54402122 416087223 123449257 451639755 19238668 788399810 269055006 198464737 378599395 663191806 835833459 985047891 323099342 938443719 680672606 113684613 199353414 560019072 384888024 60990054 796653048 363459199 176522212 637479342 541933373 666949969 380373193 430699385 978188224 393889697 727180396 476545368 42564606 128268747 341141144 171471181 175339242 603890521 682749351 67011425 938239379 724894040 946649337 765926440 929367277 362714712 422020812 505258509 530599475 121512984 234341494 885814174 931691265 103449835 328920957 636079130 542512451 848450977 198321778 576473870 777319421 907219797 842451066 143544471 90738726 621972476 417995872 880784482 398609842 424397649 849196201 433347716 335185710 318667207 336770169 631340240 935378726 43565055 921687985 42909840 162597351 626575445 287981386 706797481 230513303 267745853 483408500 124358964 732539684 730200805 123362457 420147456 567012561 519529491 699691987 473749977 11080936 20548549 373095232 233269577 674541159 59094629 185389334 422537661 688538770 358380450 25459575 985408905 849422389 269031406 697659434 6383006 815215623 203948387 610590641 888006011 101286979 798420464 416362439 200433558 533242273 995620289 872563325 679905511 786516901 210728271 364212104 836795046 607810603 631870506 308637814 495175768 111778013 105066656 681508919 418980348 315330393 121685516 824501865 579290449 803490528 303549462 524578590 507944541 853994472 475329151 637288599 744168071 471120927 195833449 979036337 46512050 993633130 392452371 782944810 671464177 599731912 734762665 680925019 690760107 165508491 63979390 888842366 932703226 559859555 88760053 732038899 181786209 908242518 193649998 909947782 366580216 639789220 428099136 875196746 950098622 371874015 174267802 965230207 624935557 597188916 516442032 107290014 895186599 757437495 460690099 417524940 819380929 287599829 913171357 616737471 802125193 314865358 586730212 11330674 819180787 716430555 915214707 202802481 518129269 631431450 992174730 444624212 58274075 826361762 474013039 677993309 227988844 740136778 93311024 323638893 296906607 265540016