1666 271663219 961189595
225749014 102207409 390567143 187257046 792246294 240551251 589177490 577722355 127568803 333114096 119931281 505011446 310901222 63976883 507323209 323771232 449441913 5465937 130956910 827874091 706857289 576279713 598348593 496295645 452801121 27275887 655573958 814437210 680613077 105260167 313539755 750517347 404145742 436838510 772563205 936681362 174244514 104574593 377231391 792544645 44953008 570942346 425200696 660792433 918783650 363702557 173096329 956703621 2394112 381638597 230773752 135097510 503248176 731444463 390205899 184990557 878997404 340830262 64774116 120628652 823018880 298504518 954423243 111397592 64842212 26568260 729757270 81488725 779509834 587605360 813743825 619808312 932315514 759562 501778651 156755735 694662022 184048480 630326672 666064068 473745739 959674837 143609820 390890187 582830718 565675557 748195129 371105444 431452290 783137285 654454143 952469531 493735684 546642074 4812089 406547914 103001353 546833355 635478132 791900317 420728416 323929049 861118101 885994937 417096648 709482434 105883507 754550491 906188136 639309551 408719796 72356242 357340488 694425992 308605888 930597401 322433839 717658255 613072291 904132831 156119874 488429476 788843575 770622079 638773383 10041867 89401371 860816611 219925042 74168854 256579617 843363249 272908771 919782016 695782944 359700469 440640267 655263783 107135924 724909910 259243820 746909827 826857080 482358250 924331945 30337917 200642173 454831086 179942841 697793022 105964530 777044749 648371624 536221358 219899777 532135333 391267030 458750934 199758302 239283445 45915796 731410229 455654944 244031757 187475016 752074297 36315455 74626082 423115269 22504361 682195674 661366469 691921928 919593493 397164917 302420916 611331513 296863560 538637222 303722385 59338702 315230246 639477436 311572972 146607622 865787458 814555491 286851268 124983842 338069022 898002727 733877005 312906889 577743637 666866439 678061726 661578660 827056487 585834640 217926668 271891623 721365210 186122706 705034095 845700953 429748964 934094918 595795056 789691314 576260602 338308335 903691421 621615961 261504259 880266688 90612042 535165587 155587394 108377058 960430892 678915770 172101730 643261922 230636704 349978797 144742109 401125504 204141384 112033500 96066310 549982813 11314470 216349855 795513226 951113155 607641200 956932833 405590791 935413283 693976531 571736969 946072308 481541132 622506619 715721142 704670161 435632011 659245622 605458051 210806871 67039060 589864278 7339609 601723522 724637448 233147852 96359598 193467910 485935156 469610452 145715914 421423379 761208628 311061718 352794774 496233759 353310128 770340718 726801241 286342140 98595161 642012081 775229543 518772378 302504146 176419206 837499664 268676252 890157274 833118784 758035950 517118924 566501178 758359608 619846019 421062272 958002658 843687622 920764882 46186209 918168679 341696134 424168880 9737597 250131866 453317175 757658900 447068514 417987890 872677495 604357624 789313622 175532348 42581795 220589495 364509285 356446487 954072626 273968480 728502065 765238877 114681613 837713200 586093673 331570613 658881958 899430553 709180735 376645155 596106645 893711774 375300030 753308058 474508620 537185685 264443204 825204344 175784888 847000413 719191499 236715098 925887465 168080433 367171987 791678670 67030533 351112200 386462853 670597762 712191673 88434791 46767645 12990235 742227879 839053868 762337300 742337463 140996204 903853290 857033242 316356309 673532957 652426701 872591720 392848479 295184281 436354206 185005093 662371053 640384882 330668946 698752842 702753783 56715294 947799096 808491795 480652081 624938691 955712101 615008306 819894030 808888433 280094129 31643794 72924554 339287738 219010338 639717932 501623880 624178230 115753228 174111075 570774651 735783738 730763468 341969094 801513140 411905077 689556902 121135576 18316425 762308997 9602810 267721736 569524153 217831320 390906989 358235001 279218163 867109871 662170407 62387348 541168588 666808403 693300345 163576703 756455408 471353095 498515304 201087262 185149592 635003853 583647218 377433402 948471816 414743209 316272446 764752357 436618866 40036958 712813247 283367985 377510556 795139365 697392094 159408529 448222137 550651787 176084841 542090458 513363863 69567648 66345311 764099665 85915211 201086236 461887355 83375028 366511354 109048682 861838348 215437869 57348362 106402124 372024651 914200115 646876526 25047243 612126991 256072076 665661379 60744633 619301644 595838471 240416062 808906448 543387898 325072517 80902398 540678722 820341065 588921349 374392773 408673468 123948238 295554214 577663339 457526971 287921846 450898824 336489652 246730840 608328776 142333527 382403911 433444443 291128051 589334291 826825779 765504249 674274128 282754446 995827 900831220 499046579 252263792 68033987 817618479 183008282 220524115 619495734 510832934 830050980 54203295 770178050 909416747 172319289 717517826 421752634 879554017 135313732 680840283 537779576 824168151 926864320 163771598 867942630 861299222 140949176 183772477 663181880 32942165 13997115 515137962 693818680 370370067 680606797 651316127 521971150 354184881 195831541 608851226 249386090 508951636 732230615 1009348 779832575 282420544 54475607 412352443 50033686 786372515 842563285 342658715 609777712 855770700 378951534 864750703 920712143 858794113 133156517 671748087 273937266 727888595 717094733 636209348 78303728 692232849 939872921 251528115 795201081 558536796 155306684 100438790 741042474 921940622 242606179 861917814 791855796 229084938 729499301 2275689 903272378 309983058 63012707 859697904 49470087 343182767 234295524 141417201 227987720 412025863 256706382 927542990 510672478 489959717 192817264 436692149 927997552 895239904 513876941 367058141 781253147 275138165 96288045 145854755 947205024 221998239 155863714 293225191 483175835 337198987 755541960 64566090 285001077 599797053 70553551 868987133 914922346 259099203 649513328 678947661 916739454 283145631 770028986 960645204 884960058 537506565 353794311 393808185 689462830 77143041 551394774 727465426 411312456 691280375 200842157 712810885 117398539 378154049 336087491 232675744 25800454 494120511 930734093 56851610 21902606 902755122 767280743 517814750 379424354 471236537 308918760 579556023 147260228 782012753 309089018 332539968 76815416 540452874 157472656 204104217 374745406 563199167 662577484 534721932 780077874 150948140 39220948 621049065 316779443 810514638 460630201 581659985 879026297 265223309 374699026 769136469 818961904 256397662 604784599 910859368 460379256 297956085 208027056 744596981 835718267 17889484 226206241 762970614 299959822 409867217 748206364 306146149 411391322 468617789 423294561 931649365 264974441 311332814 599868490 726886902 405835622 633331012 586425012 439039521 901320433 174415385 283042671 224937419 887485566 81059729 845063979 792174228 299539952 772298380 837630831 693163435 743711775 880658612 855709643 797414789 554551431 153103939 259766851 518150521 855253254 173091735 342974576 696442630 320819038 30929390 773590728 309302146 625467250 248592879 417316924 652237489 291329460 426432906 89219291 24391714 256302548 40296293 460195575 771527930 455954911 363709857 165687176 115687054 746025550 6119795 10946348 191824156 708778071 305003752 891479377 189605327 872579748 792192612 850769366 504962039 314011729 359829329 678441258 905318017 156382522 813130626 391228103 698282286 535222489 79444631 637387585 635627125 12112348 287644855 75628105 695719930 69533162 202090074 949880756 139509367 61591192 410663707 950023985 543159118 126604766 715606363 502779706 871397817 179489355 339007190 53125281 206926442 674119320 679318839 826212095 341266858 274273294 879222259 737212109 951847613 284763464 600717267 399395035 575714463 659657286 368571511 826583996 362297444 531639134 261709458 197296510 702553433 472791825 37945077 794077035 660130674 749953729 37628350 608090195 259135321 500213553 574368875 406033438 438978432 508346724 736606087 162514994 437949225 496111390 869516070 591898443 593788364 139951818 636623765 344138592 659942870 313806695 539370600 907101511 571984451 6561958 820725778 160022488 495841273 335456469 245144277 362524787 206300210 855795397 743424505 474983024 375549491 173444025 723506690 703305608 157456206 189383480 849921643 321741548 175563820 215334505 203743684 727798475 597289477 541214821 315158491 14264968 607188743 757970596 756503970 192636422 663158397 280584761 112031223 110565846 282906565 640158542 921171385 597609094 517458127 269789247 700910334 428175778 935678995 143333501 918070293 859891376 676828936 550311423 335359959 499589512 185177351 650410335 239307403 508552865 714384050 464757947 536501576 46927277 600958468 856704508 111045002 591031636 753413756 766157226 589031032 63056556 376252013 507606236 444844008 367660834 702220868 564674747 470597704 746139187 275178131 631545857 788777495 928035136 746932167 460624255 76360548 146477490 921914341 671381604 288878426 898065724 958747202 520414035 47451370 21396946 616733871 217712095 915873341 786505312 778195313 282530134 82464517 521476914 365840532 835264333 49651976 410373006 886645647 836098746 206106526 89446633 694858053 351605460 449009055 535527584 878182320 908192411 224848081 732118903 921966145 907766974 108971239 4304957 146060812 522302214 558112829 698404897 774971757 778753294 124365554 194438670 562649185 569196250 667792135 171857530 428474009 24086899 959302539 541349661 155611454 79286302 585033238 688683877 799995420 602914895 750724134 686524687 525213414 938833222 502114857 666083214 917181947 478700519 754049716 481208269 757019363 907001894 878990118 389266000 111021444 252506382 751453009 741671269 918420029 538344638 787298795 741967785 789011756 424509126 42337956 811498049 821534355 868707815 802126389 34185678 551985512 198067259 517457025 378846044 881373385 235183524 798024702 340833571 611261053 181311655 166154333 906795521 897318581 383084040 912511004 429527883 654073973 846393803 689498311 687108314 771187625 462912185 160932244 361768284 569544885 563827542 100863220 760718646 394650191 339455003 379231046 702924047 162323884 634574066 672114341 259892834 593688417 476294666 755321095 260283702 710092232 227718141 616300596 297983114 519908951 685136291 357229059 792325546 95441508 740554690 489407477 58312736 106620289 846886990 745415226 260445801 751179460 78204570 822529885 800178070 122792754 21443269 88913313 228543734 326859365 221385618 782893887 89802513 782695470 46796119 129876587 42318704 140175176 732741058 903174135 466265750 297162772 597410783 458347457 955724959 861083428 933660500 500850590 298529331 361053010 390109882 649573301 691370560 129668776 685501826 141552322 578491303 265707528 888990559 250153761 409376849 770658322 826564510 1021665 287728818 635579618 406308047 137030901 242082097 752880156 575160113 416846556 293938598 777311892 616269310 181502111 674876650 72827822 649379171 822555956 362015431 13552249 589763590 361639643 592091543 12684 180970739 230333578 613463850 799804845 720001473 83185661 5986565 925952899 662728059 510601716 296431138 230334951 728117362 239265302 337034573 86205185 893629817 912482487 672488863 879675393 225223452 444831355 289392213 306183037 239204000 361213218 3566456 412160398 890902195 474908959 816671688 388118736 195198115 342918167 452821585 86058000 766848435 597752853 329887684 571136030 557615415 678790148 152337069 904642256 380325493 909551025 180089295 368649897 290375580 450562965 211390723 163442043 572003129 626981101 331484444 416305248 637074100 747054208 120549306 326277138 50374618 386978961 883843956 698378700 195537867 161214484 855746483 254107120 319028357 598968536 591457216 713837926 795865858 130814060 121979020 440759637 118650723 486507143 422603584 435935771 455110775 73524616 736556960 437529545 749671898 510430178 264735580 888293946 575578970 270621611 888695443 726226700 796067183 765754451 10316131 148467993 341342853 890037109 237862273 400629812 932766128 902580074 750639263 479746526 805108830 191723340 14286792 800151881 560190564 152283498 486150184 197993413 808328548 498512331 377306396 652641609 513872855 272785767 12643456 925599895 456126383 784269152 697865637 643312221 154862158 251628243 505944439 443869329 393746337 419726220 425720027 712277612 107240741 417774291 195304335 133748507 380002484 55380646 18333080 890789181 849789337 172383131 933268249 595480411 347281891 151252819 204433325 83862065 301057333 351724427 463345312 470933706 658708921 624401134 285692057 794765185 823846342 789208648 400488737 286391799 799969721 752650589 583990467 837167181 407113778 415269399 175088068 26315800 717758665 231591326 224511059 221290478 710117596 516592156 878396699 695205657 61156498 62869796 843768224 129843806 300946315 768379942 316647603 181814626 468369126 591441314 895209785 804194343 760462701 372568655 6391643 326200916 469023193 248234027 664440517 523667918 480852923 581308429 417963715 1089614 160036664 546486506 69105131 163376625 845371188 416307539 498509133 425847116 610413958 306866788 38698856 107124781 394804631 899206587 108158230 750475373 55023775 732667594 740250213 535540514 640841948 5089114 659705499 581660766 950605160 627255763 954030471 438016178 519946117 803004498 227657337 508034955 369494376 839616875 948030641 475744487 448988527 919887753 423528340 237381632 437231603 828348611 838706990 1749885 823782094 931017516 945970327 173346182 804046439 229666178 391065168 295713598 332526668 458209596 774875333 625260345 804555627 430849957 517559181 241700987 724366891 779515020 42815634 818862319 661251661 478351047 627207193 91629506 80351725 112225275 729539707 641492915 273374253 515640536 74742411 225249619 119087237 558559285 772399548 911827637 729718194 748402185 212726488 92556398 323746537 336959420 528454700 115848831 207352264 673487477 932498390 826557762 731768823 335038334 680490145 611575449 40505330 795760391 305214385 766308232 254604197 814359183 279191233 272108623 711492184 402179219 345685750 417181847 18195101 382419795 56621455 442439385 821845515 463529105 940295869 598040188 55145371 339211197 710955310 859157904 401926537 471771421 657000876 405635251 819923857 480808106 428738508 939792743 926693774 180130805 539698856 734512207 876213490 283717626 329664922 197926991 3413677 625558667 567664977 606768693 211164366 384721328 201231630 630898753 411559149 884196116 436146849 307843704 799330393 347483608 747002787 732644237 864218211 927858118 835371772 196289102 429820904 374767254 853572017 408317014 347971656 562961169 496668280 518547328 275044479 610280058 946121511 824025706 383944299 133824800 602494982 172825358 205584308 608971009 611771939 943895995 625037511 584551330 725929943 640200595 483462447 22549958 147862038 376613795 293876988 295230745 951822149 201065556 60438436 754035016 242837669 243619778 77808691 292696913 67064555 326070756 545628710 532649830 751815754 437453535 952735886 450504148 707032814 90461171 808683534 922996236 626174880 115504500 406472004 369574451 641343946 574870254 579172389 244164061 406676827 230352569 782027085 849108050 274980117 556607908 391460439 957696538 889702035 541659097 769644561 575440392 214938494 809748948 358615473 299309583 557885416 903140846 171053516 422951487 794307105 813865588 666366314 606188228 391301332 845768680 354715966 200665525 199039716 208115746 87393346 614228368 874913775 583653854 593646490 903087660 914027383 859407121 783835226 729501621 622153195 702235534 253041823 580646591 473724918 708143708 961068544 447256413 840473650 726401015 800252103 39098610 949719657 400932510 898625591 144932373 273287828 440867591 458564104 634551616 345554009 620940481 788509044 894327566 747357275 864715448 297262520 313163189 502586093 934580136 334161214 473148333 716896789 477314891 770909844 530932189 30781838 641349961 78662250 29962256 442643725 246026515 909991379 406730620 36230768 708002215 953566867 511801305 770807994 501436664 592443430 953137722 607579501 393219263 412228196 682890765 832842346 506986349 222573679 826830986 424835361 442803650 186212399 407362970 330191982 737041329 101884209 684354648 875051173 349859373 311293685 102694084 893049938 917624927 637086088 667965655 184044214 53158927 512744757 850540994 347430979 327349553 355897689 210305204 776679733 528340980 116963629 328740626 358563336 212666381 162851397 64890649 391690116 634328927 178709090 882138755 770633858 519904652