539 307780695 307781301 890243451 775130671 775131384 360422382 611730603 611731536 792121371 752081717 752082118 808039115 485017681 485018130 703773485 985715516 985715837 504074360 229481576 229482136 595434789 729067500 729067627 506838656 240898965 240899622 378262957 595806141 595806394 649310099 644945805 644946029 892905361 106228571 106228977 342088466 760005692 760006269 676512420 410512790 410513039 632727540 258798161 258798386 632108992 860425720 860426233 286591884 405469315 405469980 394343247 838611623 838612311 919885171 966398298 966399134 715406542 549014017 549014673 281910365 417581609 417581963 397839083 657521172 657522088 212829120 769579037 769579752 998497710 792461685 792462354 214589789 68419585 68420277 98496931 476814389 476814979 326394629 855991463 855991506 730558060 682299153 682300050 524080887 143214482 143215049 629367039 244094072 244094208 509204276 876419850 876420341 441698928 963306670 963307107 886991732 917233 918039 406572043 213680046 213680382 446096648 834278877 834279469 230892246 854320916 854321649 779266338 871758465 871759151 292057913 238452347 238452549 683838225 382241719 382241725 215479660 817493437 817494206 132100685 772894534 772895186 902614442 795464148 795464804 984412788 691154473 691154746 187046756 301758382 301758985 525559378 87725537 87726049 791025025 964413864 964413864 516903933 396413896 396414468 435043408 738323187 738323433 300557988 550725802 550726274 942964654 49359974 49360027 281427071 568718014 568718304 812403555 645187000 645187409 473784695 940689385 940689789 373321288 768096187 768096831 466697458 188938427 188938675 661254030 275524237 275524892 300983323 997112452 997112859 370668785 770995681 770996452 599658027 193212770 193213380 400334350 9983208 9984075 209481383 778649536 778649803 487518863 567411019 567411915 210375570 61543812 61544432 84627106 443030706 443031185 240354089 203016172 203016960 861206028 189187544 189188266 933079611 881003228 881003850 885190773 74866840 74867010 689041569 70462991 70463781 126717700 295772865 295772935 898577227 525964903 525965294 974959657 282119583 282119948 958038699 928748804 928749202 217644238 136864954 136865214 795257540 833977662 833977752 926030417 84787105 84787707 576390074 254870355 254870856 880442886 476989108 476989253 465425749 762243924 762244283 859591121 863322551 863322880 541646220 467478026 467478749 545210079 26066720 26067128 614646066 796263076 796263981 873295991 932289793 932290345 929096541 628308820 628308888 611456732 586103491 586104315 648442132 698118745 698119036 838850795 128310835 128311013 298617238 995855451 995855605 265138055 594952858 594953730 813890886 838650645 838650696 996606693 361344781 361345184 663103146 499377931 499378477 377227914 234664367 234664973 856379379 813004438 813005141 29633972 152463890 152464450 75968188 494775186 494775664 313035868 330268409 330268716 524717477 667892855 667893200 47208335 719695254 719695440 822021742 294999043 294999510 345120850 554497407 554497867 895709539 966640104 966640416 507722285 670614725 670614889 796665833 894519285 894520111 355047646 148255128 148255787 910079651 509100709 509101073 939242976 744131087 744131742 59214416 19950413 19950926 282603585 31452652 31453495 472419492 911172282 911172902 540903409 633541145 633541978 508913512 456169504 456169771 881111927 447572647 447573496 741756031 688172735 688173450 559768959 677992397 677992868 599881689 395218010 395218926 78991381 37243495 37243860 596311486 792831790 792832067 714779106 633389106 633389552 332746694 911355250 911355426 561434646 943589899 943590180 585111614 867596812 867597485 904110713 466684044 466684877 173441097 31281134 31281319 447628700 486470440 486470921 93993775 560314991 560315792 980610576 169651012 169651942 128288892 242492236 242492637 316208369 746269899 746269951 669336005 294753824 294754217 702207319 120792107 120792210 643898114 472569124 472569321 646831472 195528694 195529630 472970533 64514440 64515131 961619411 23223971 23224490 416319760 296007433 296008210 427014664 320181783 320182564 196806464 437000253 437000541 164632650 527723933 527724169 49093899 358054635 358055619 216840984 631594745 631595281 12507690 143823301 143823801 696751398 364213373 364213932 770989345 899614786 899615781 150234331 99333908 99334769 46349778 353843454 353843765 632762303 297000240 297000506 737818837 467674526 467674956 127658572 143347184 143347269 261157138 948448581 948449465 59768068 513325466 513325822 325299579 594373048 594373671 124107575 892504911 892505587 732707377 96247294 96247623 378843549 296061676 296062257 150639877 311209590 311210183 211800205 162942695 162943110 542191254 257753870 257754343 350738080 466692678 466693347 8839891 307215014 307215439 149594763 642657414 642658202 195924966 335961477 335961776 581862555 724661512 724661514 897342965 790250195 790250756 736761911 756645680 756646335 996824858 63703923 63704077 334208794 176011473 176012298 502606243 986840281 986840773 736969897 468744846 468745476 859058318 972552675 972553234 463122224 99039840 99039960 609386236 860449049 860449837 914627478 421495947 421496552 89447219 782949710 782950032 121977442 647427346 647428037 151080092 129470965 129471630 980579008 99625450 99626321 331860451 550720616 550721075 529413943 536660938 536661436 192040779 786445013 786445870 588339426 771621902 771622882 407821237 113259134 113259713 182985679 767594683 767595108 263952128 117990662 117991128 160332734 63081033 63081055 475727226 704305959 704306117 384376340 118589703 118589970 765296096 822471425 822472235 811705833 958907215 958907837 200875108 347013742 347014544 411874950 952971278 952972000 399525047 574407536 574407723 515899542 740808466 740808468 812383455 658162063 658162346 778867634 811852422 811852740 352498597 300342296 300343096 715293340 831606078 831606318 825861164 421678213 421678521 312846707 44085145 44085882 894521357 426365446 426366172 80299602 661050111 661050504 108573757 677243154 677244072 225727951 696700659 696700700 75738111 461564452 461565177 45310272 777215871 777216346 514673016 824263928 824264040 88434807 9365358 9365558 337018535 899702229 899703201 320719348 554255005 554255066 949372508 209989672 209990629 38853962 716978708 716979588 725531982 494944341 494945009 525723172 938984221 938984788 648894558 740784473 740785412 969586129 334289656 334289750 243690736 687034109 687034241 665854147 969072116 969072285 668880879 718481353 718481706 708111335 903396023 903396501 624158142 37790244 37790312 862710049 834907112 834907779 608464065 596134605 596134948 388670453 32158789 32159698 565374350 179920946 179921943 676304891 130296293 130296459 972328266 98258414 98259134 239301159 863915912 863916476 550715857 962481436 962482155 769431131 313573442 313574382 964622398 600618671 600619004 812618784 910369678 910370139 617905006 264756919 264757206 837601723 286553562 286553602 803058519 292026061 292026290 862642165 85900807 85900885 847900583 598300123 598300195 915383948 272563412 272563906 121844275 182573536 182573851 990644350 683398817 683398865 248391913 678208143 678208674 959747540 853549390 853550216 274914786 712169226 712170178 243916708 972591557 972592189 76625868 314665685 314665958 492207904 244389869 244390156 482702392 529690476 529691102 939825026 192087387 192087889 553519448 618144933 618145490 218631030 21533344 21533419 122536414 511907456 511907954 17300787 479665679 479665914 121103265 655809787 655810525 192874075 233403931 233404038 392818726 330039942 330040035 461762332 466544445 466544606 234921400 675686327 675687044 124249817 479373613 479373774 273439726 32243098 32243670 493686412 3019618 3020303 553029806 664883154 664883993 278971504 687274092 687275027 595642053 638833551 638834004 487723707 338972261 338972509 434472133 124545882 124546085 435469668 564491263 564491316 547181268 982720001 982720466 267156946 324098476 324099006 14442594 764310641 764311260 566390719 644841390 644841664 930848056 346298030 346298138 863742720 349833492 349833807 830355160 942866745 942867489 678145324 360654418 360654692 340053262 351276644 351277637 65301214 189208524 189209088 989538826 658262428 658263208 20117709 619046461 619047445 196298659 583464090 583464464 903025950 322989572 322989936 845437634 332204120 332204697 124990562 226340274 226340525 52186111 698850869 698851421 871564255 174540460 174541075 154474302 850531279 850532135 621209505 406547763 406548431 250187582 54523197 54523664 600821409 226432741 226433408 52981508 341689738 341689895 691880071 308876299 308877066 644990624 819015007 819015356 911225957 686970635 686971476 355322265 778863392 778864308 27793177 467045725 467046321 936836861 290351747 290352418 270977565 101951435 101952111 141791427 244401593 244402214 350077533 934179566 934180354 741748490 59568446 59569318 442076802 870284050 870284673 133695434 933102509 933102715 388554601 392998347 392998823 824221753 539252851 539253200 597011983 770051615 770052152 916121665 529207587 529208475 967963500 771453762 771454560 23126061 990067367 990067752 733607659 946211516 946211899 537328579 329974831 329975317 99726491 315866616 315866628 131078912 466166022 466166257 592589399 886041734 886042574 392798308 503363970 503364301 594847947 226232632 226232649 710132157 827560166 827560931 375186110 236448642 236448967 886869554 109807950 109808202 777010860 650330566 650331240 953949816 934784395 934785348 481025346 792667232 792667262 623693145 722689198 722690197 185501358 405364307 405364760 167017917 478499074 478499236 683255980 608150695 608151445 136680514 495659 496256 651677950 971623339 971623846 881408053 636157710 636157774 884177032 595259388 595260245 162234164 819184541 819185283 173406071 916203645 916203783 887887354 539339741 539340476 406793642 696406638 696407496 553180062 199085462 199085804 511490519 493724696 493725225 227652083 843590817 843590965 251399017 137874330 137874501 88233616 33530381 33530769 787900425 710411460 710412204 197957563 926017438 926017880 413319566 678721285 678721583 983192888 517439376 517440208 518882678 661995553 661996230 854967882 227372220 227372659 430172271 154118404 154118838 38919478 94583690 94583997 625657513 832966954 832967322 708380568 633297527 633298388 43539493 890725578 890725615 63342669 823796154 823797056 256115253 969452337 969453183 70533156 593040147 593040533 38294563 348489703 348490115 660911667 354342473 354343415 378849818 224548826 224549699 798245991 72213573 72213757 425968024 284066077 284066662 385786003 782181371 782181667 762580436 47240787 47241769 667014512 478053849 478054010 646711359 81410685 81411514 427152569 675189483 675190420 726028455 875696227 875696893 160874588 337386664 337386996 375502559 570969263 570969283 706050166 482039484 482039528 678841381 395738918 395739523 505243442 984330433 984331374 23535527 565604717 565604880 977121266 120795225 120795697 400657498 290200386 290200982 568420714 819869163 819869980 389518501 128131526 128132381 141195385 181743722 181744255 284766590 700867265 700868076 651744957 931891525 931892089 466951093 853098852 853098973 653742435 757542451 757542552 274574000 130684698 130685010 796191644 963305629 963306465 113433129 919404050 919404276 851035949 5283133 5283582 564328827 86274177 86274340 2175381 244506162 244506764 989590646 190291181 190291236 824063204 235365815 235366470 727863857 744455042 744455185 391815030 694083661 694084191 521511326 930136327 930137169 895341809 479061640 479062082 298166605 183676217 183677143 450671351 632505431 632506229 740985191 131018329 131019197 74708352 667879232 667879646 72482205 31821848 31822696 742275820 344550205 344550874 180970086 160443785 160444480 965646403 413832640 413833450 438284256 132941618 132942153 447521169 407508047 407508922 758968151 170918179 170918821 663390239 966889008 966889192 16122474 763983819 763984162 958887640 849721467 849722088 270922989 32965723 32966455 350919567 483834189 483835000 475440946 152033155 152033340 442016246 793986490 793986822 411098364 702852658 702853648 435487563 198862585 198863179 609795795 331430716 331431267 149147327 864042353 864043066 483699340 483672323 483672620 101631059 479768161 479769136 405838369 182613836 182614647 281266016 281279724 281280207 707617947 872928265 872928442 117945573 118206955 118207319 330191324 89735455 89736343 98688271 689857751 689858175 571508166 927588364 927588777 99728165 100775862 100776336 262903066 90732584 90732996 499870957 558654873 558655850 746832693 957292701 957292999 935627763 325533676 325534280 486770774 338434885 338435172 615578462 244694559 244695397 182160138 696710329 696711092 983801037 88267106 88267276 167198069 123695662 123695745 549750465 338180111 338181095 159108130 52304415 52304516 648324439 783128207 783128685 482579871 423891407 423892197 733299880 406274659 406274749 313402330 40198858 40199623 110585730 870559387 870559801 211809721 849678183 849678630 728990250 102101464 102101763 806631578 428732442 428732548 211054235 570210574 570211121 484858378 15895685 15895755 252667955 54527689 54528127 394398389 803206395 803206521 235616175 870459530 870459574 892955897 17316031 17316280 264744219 697980525 697980808 424382057 359841413 359841875 166945942 123336902 123337902 626969432 478858300 478858758 649730341 106931672 106932441 62547684 889784414 889784725 997193876 598356904 598357887 729979810 119719207 119719430 108328228 494435801 494436758 793724620 521173835 521173873 96907345 931853017 931853996 335130510 803257546 803258494 945239979 112215060 112215740 175974555 80221761 80222033 883245652 903346440 903347021 473790361 405009632 405010579 193623570 62949540 62950377 62125791 291506448 291506725 872479026 252509636 252510541 601240447 959895182 959895642 552880264 174019596 174019896 780563991 99134169 99134317 470621870 651687558 651687911 401380770 912730809 912731255 512793159 508169464 508170080 824561023 681903077 681903372 214064610 141893800 141894345 792147469 423592533 423592679 664291605 772466860 772467641 667327647 244452511 244453246 276919825 845052013 845052449 741198948 444360034 444360979 216032804 411492803 411492958 881575489 186413503 186413633 245780655 242925170 242925688 251355629 895350446 895350544 758332781 21812911 21813050 309707348 17909097 17909371 515689588 217643473 217643799 291447052 245067992 245068572 596290541 557037757 557038425 861583113 108000251 108000981 611645202 663740631 663741269 389467659 379716426 379717157 616396970 962671217 962672175 835443367 28119430 28120311 495894743 900618692 900619154 542246382 346519549 346520485 325510239 609175097 609175582 994198135 80468247 80468594 159950795 804780985 804781193 839208211 115337185 115337463 857059782 585065598 585065682 440722427 670068610 670068782 786514393 137352843 137353510 590577898 515023108 515023258 726519322 560610118 560610771 984291103 360483015 360483206 247637456 601022564 601023089 38385858 962582583 962583108 169389745 686070651 686071191 765807180 839285533 839286430 175334859 332364360 332365277 40127360 291850220 291850423 324233532 258157355 258157920 538493490 557972027 557972116 19372755 890059998 890060280 181369335 773788131 773788767 976621013 652529483 652530320 940527516 402616743 402617353 402202299 941560606 941560762 715821635 251225444 251225806 419536518 320227730 320228429 895698238 47526463 47526895 839903687 250129489 250129575 535035487 492676148 492676958 28974663 807999358 807999483 196333902 940576256 940576485 286891900 106455781 106456133 693660818 6331016 6331991 959524170 557688079 557688981 307111204 264978346 264978683 310032141 45766466 45766779 635918001 217808325 217808555 786056664 863970455 863971082 963972753 820675730 820676686 331022322 934852081 934852939 222589351 263022176 263023047 359784968 221702568 221703548 502193632 790989183 790989847 127483472 875550400 875550970 694969024 466015073 466015973 681185655 462167655 462168084 374262034