2000
RRRSSRSRSSRRSSSSRSSRRSSSSRRSRSSSSSRSRRRSRRSSSSRRRRRSRRRSRRSSSSRSSSRRRRRRSRRSSRSRSSRSSRSRRRRSRRRSRRSSSRRSRRSRRRRRRRRRRSRRSRSRRRSRRSRSRSSRRRRSRRSSSSRRRRSSRRSSRSRSSSSRRRRRRSSSRSSSRRRRSSRSRRSRRSSRSSSRSSSRRRRRRRSRRRSRRSRSRSSRRSSRSRSSSRRRRSRSRSSSRRRSSSRRSRRRSRSSRSSSSSSSRRRRSRRRRRSSRRSSRSRSSSRRSRSSSRRSRSRSRSSSRSSRSRRSSRSRRSSSSSSRRSRSRRRSSRRRSSSSRSSSSRRSSSSSRRRSRRSRRRRRSSSRSSRSRRRRRSRRSRRRSRSSRRSSSSSRRSRSSSSRRRSSSRRRSRSRRRRSRRSSSRSSSRRSRSRRSRSSSRRSRRRRSSRRSSSRRRRSRRSSSSSRRRSSRSSSSSSSRSRRRSRSSRRSSRSRSRSSSSSRRSSRRRSSRSRSSRRSRRRSRSSSSRRSSSRSRSRRSSRSSRSRSSSSSSSRRRSSSSRRRSSSSSRRSRRRSRRRRRRSRSRSRRRRRRSRSSRRSRRRRSRRRSSRRSSSRSSRRRRSRRRRRRRRSSRRRRSRSSRSSSRSRRRRSSRRSSSSSRRSRRRRSSRRRSRSSSRSRRSRSSSRRSRRSRRRSRRRSSRSRSRRSSSSRRRSSSSRRSRRSRRSSRRSRRRSSRRSRSSRSRSSRRSRRRSSSSRRRRRRRSRRRSSRSRSSSSRRRSRSSRRSSRRRSSRRSRSRSRRRSSSSRRRSSSSRSRSSSSSSSSRRSRSRSRSSRRRRSRRRSSSRSSRSRRSRSRRSSSSSRRRRRSRRSSSSRRRSSRSRSSRSRSSSRRRRRRRSSRRRRRSRRSSSRSSSRSRRSSSSSRSRRSRSRSSSSSSSSSRRSRRSRRSRRSSSRRSRSSSSRSSSRRSRSRSRSRSSSSRSSSRRSSRRRRRRRSSSRRSSSRSRSSRSSRRRSRSRSRSRSRRSRRRRRSSRRSRSRSSRSSRSSRSRRRSRSRRRSRSSSRRSRSSRRSRRSSSRSSSRRSSSRSSSRSRSRRRRSRRRSSRSRRRRSRRRSRSSRRSSRSSRRRRRRSRRSSSSSRSSSRSSSRRRSRSRRRRSSRSSSRSRRSSRSSRSRRRRRSSSRSRSRSSRRSSSRRSSSSSRRSSRSRRSSRRRRSRSSSRRSRSRRSSSSSRSRRSSSRRSRSRRRRSSSSRSRSSRSSSRSSRSRRSRSSRRSRSRSRRRRSSSSRRSSRSRSRRSSRRSSRRRSSSSRSSRRRSRSRSRSRRRSRRSRRSRRSSRRSSRRRRSSSRRRRRRSSRRRSRSSRRRSRSSSSSSRSRSSSRSRRSSSSRRRRSRRRSSSSRRSSSSSSSRRSSSSSRSRRSSSSRRSSSRRSRSRRRRSSRSSRSSSSRRRRSRRSRSRSSRSSSSRRRRSSRRRRSSSSRSRSRSRRSSRRRSSSSRSSRSSSRSSRSRRRRRRSRRSSSSSRSSRRRRRSSSSRSRRSRRRSRRRRRRSRSRRRRRSRRSSSRRSRRSSSRSSRSSRSSSRSSRSRSRSRSRRRSSSSRSRRSRRRRRSRSRRRRRSRRSRSRSSRSSRRRRSRSRRSRRSSRSSSSRSSRRSSRSRRRRSSSRSSRSRRRSRSRRSRRSSSSSSRSRRRRSRSSSSRSSSRRSRSSSRRSSSRSSSSSRRSRSRRRSRSSSRRRSSSSSRRSSRSRRRSSRRSSSSSRSSSSSSSRRRRSRSRSSRSRRRRRRSRRRRRRRSRRRSSSRRSRSRRRSRRRSRSSSSRRSSRRRSRSSRSRRSSSRSRSSSRSSSRRSSSSRRRRSRSRSSSRSRSSRSSRRSRSSSSRSSSRSSRRSRRRRRRRSRRSRRRSSSSRRSRSSSRSSRRRSSRRRRRSSRSSRSSSRSSRRSRRSRRRRRRSSRRRRRSRSSSRSSSRRRSRSRRSRSRRSRRSRSSRRSRRSSRSS
574446058 158734469 429258829 61295441 552034926 464595325 890911511 145088039 232174122 987079403 840441942 382313667 684847907 883728421 695606359 50821228 294967652 310285568 168974808 973058426 23168244 931512533 499082364 38710528 322686064 851121340 570412287 126854100 739179791 161063258 504392800 209466308 168523972 616881320 728800101 784924836 548625493 679521603 28096970 373705997 243015553 831515966 898096070 875294853 14551135 940852322 675412798 369747655 188971092 490837094 561329676 126535449 145613397 993009198 556713623 293278551 782825407 82775942 101378892 302991244 737758231 294304476 134572809 590581171 300187328 331086647 292451282 791814177 321009293 549354864 912867690 878079787 215101276 594004309 461547691 259162914 163714349 104876597 113204557 377078587 672832218 553125659 299226554 379934986 858747902 168267577 18134743 169946817 780195112 259546208 690495792 93329194 713732101 942381704 787509146 70447943 245791563 937919477 46562892 529981080 889371665 235220774 143245705 386885418 243399226 218372341 400012116 992877956 502849809 686088145 526145298 1613369 750280678 647204939 389420241 328282061 717283000 143896260 243957322 957911276 514200709 750021986 572646538 838068151 766074169 312354786 26957100 558254363 126204127 664383423 312346898 526624119 253481895 977357233 129821720 574385087 141445965 961850817 136087109 182520586 922896899 505974410 345433254 186069520 20548236 888201795 486533771 538830054 291399942 908997762 170836870 947224406 913907281 502147380 159937222 750662956 95610142 373535797 755861189 241344523 127407461 130196608 766799600 927435245 73653277 328498043 487371801 6449566 796822969 496231785 267491293 752419564 52058058 623276823 525603182 880472431 845603409 152764291 315981641 264498630 760499822 441010131 576127200 460897190 282332486 229420258 88569323 492775270 288265262 390831094 134872966 315472638 691998532 207540944 901695848 392772345 394153609 898599846 896065624 827246119 396429149 402792420 584311355 213037142 224912258 754476384 38463749 672226247 696210478 177298851 483420596 614502428 81818241 368533604 349200638 639401231 372660694 647958857 508656347 642721942 36600740 359646643 891050406 106837576 404577422 518943473 416977473 654447903 432057949 77006505 630516553 994042606 750380977 942334978 861076292 15948835 965254261 983792420 663156151 635395366 877801131 487560119 568311498 633713285 67827802 776629620 673169132 500851643 184622579 149414435 136370970 234195475 58755374 708698288 274445133 754642131 26663984 888767891 924988049 947123319 578845743 116412611 636869447 198575919 908988830 901431344 336277303 923424632 419112101 213710858 300036565 367560879 908962289 481234100 462531607 696312515 401315479 256237496 839154855 787006609 969439297 695595952 618844906 663963982 635758933 509708881 606761411 762558660 513664860 704531378 390533967 332931124 481870130 753805157 54258808 43695530 617102192 486817810 590339614 90097637 690817956 932549036 451373086 589424603 827171721 215285911 921184293 471941921 61929953 312117680 933841731 304388299 248341281 20689532 534616160 860719203 627951967 612532935 668337737 769857560 649153738 432918857 186014814 116960862 461601986 486924323 504635659 690468210 23694283 399431940 471826262 808768936 381033415 806198965 803430597 560821162 866702811 540525858 557592397 5335654 340895829 210453505 945402498 290198349 711116574 163452136 965244010 480924590 984552764 39239182 205534524 625231816 463167674 981225759 494785879 389736179 166796891 892103869 86498030 969694708 214428430 594322478 817748607 664485642 933198703 478303167 57446701 79497544 972202716 957303247 370973411 39970255 459513990 167392034 881251968 172951160 335098317 684272423 914481846 855118389 516113476 967487087 197863962 620956666 677193939 653553802 922540201 604304687 176752848 283541788 782467558 100437890 489229636 618866441 121613564 988189951 987457355 302840585 871421071 931306943 260458075 790323314 831936013 12362629 726381137 97805503 763172279 656150161 485280213 13490149 183335328 667001958 249187322 528746222 389967739 738521332 285830429 403780314 647902874 882717323 754733830 481997547 754977898 657316313 213518802 915111419 814321043 148752329 826932110 608995821 159780793 481432635 47608474 175928510 612798956 560504432 275145981 530067532 254531741 118658526 327229462 569233953 117580875 661407215 542342519 926195318 960859170 374741253 351409513 597805548 412665186 297461012 672077388 23353021 317830213 891330341 44633543 3113727 243179595 342366135 360921297 852365906 797442135 537456658 922867198 464367459 546931958 44248344 572142032 509388918 910139240 166597082 911879873 485792733 75220633 209321084 56567633 62317003 155512879 974774837 778664349 769665624 5791114 308438584 300691169 457063490 81426497 223132730 92157412 212261858 327761659 142698412 854799904 645051356 712205129 834194673 595629760 741201604 135129615 481595727 736398412 707282031 763632521 595398285 808103469 140863097 423267212 74242269 874884153 618721499 757173147 920323123 757191231 36222703 700682892 48763596 285774848 167882741 313656195 442072467 49906751 108761861 99700557 757736626 524984032 862786736 735495880 958775858 510952024 63085919 477286868 510526655 550834240 28739875 942300443 53905262 169517534 224657542 608989471 549158190 176530397 568728125 481143287 162974701 753507595 98267586 847987328 948225459 469643939 978769059 633747047 303563240 303357295 279583965 869364703 389648177 39332621 50755189 370530507 990420695 575037391 973425514 979934540 338518233 650707657 835419349 602609789 933300109 138637752 737224857 73669683 93001507 329054926 986809020 879962488 834815078 343676213 253171829 341939427 276552614 36920550 936286165 711937535 913172996 807837379 811580952 967760989 311659841 238528767 936256908 657177780 378523291 648179847 194299251 977008988 372571671 324332734 150985250 888191903 190639291 971690710 65492225 462239386 76297273 690543082 635128451 768359041 513364366 50499057 808282236 745291016 370483481 960373492 971526976 977495744 653523870 774340797 39645709 972132422 697926768 949296100 226952257 941909726 521931312 160627222 818920237 746574631 33079504 284695148 865326777 651201473 223208193 470890322 132617780 568120219 392903998 827232949 927629674 501439464 325962855 328201290 579706481 380892727 970029432 136754758 544147948 76578861 844346279 899737869 732837740 609581990 898863037 518835350 800667366 445555789 855051147 566414688 273859910 962613669 603996833 492475868 569136382 733578737 612790307 873505185 372992608 324921013 317012394 639031551 633272259 867550573 588912581 25722394 676162221 976371669 313263331 67532018 380284175 376034887 907382219 739982798 98052633 665289178 836372168 568614905 166493963 623212258 479895717 964121242 537534115 607361758 740933208 790342813 81998624 966823801 947879860 588897717 263126427 693865992 24424965 73125915 761952434 640598980 6078355 689215300 769051134 809256440 262445908 93523004 760264738 690413969 201914583 16754550 349865891 53939649 394441299 921482476 469562100 65164958 132766695 990815765 807042486 809685948 400735984 837601090 112893651 710109462 833977361 561490294 949327718 516904936 815795711 215020153 824900485 852212144 972420843 929425612 640952185 931688704 94369561 490535090 219994257 525925771 670826446 898185127 503410708 689530852 199093817 823419017 2351087 894627328 623616763 849764336 666986354 651695244 890599811 677696288 480987194 9701516 918789677 412997171 453583536 446669160 804198653 372328457 843915744 778051452 847649595 988796060 67627968 510640340 224336269 191965452 590562963 444868563 29415849 800980573 753750716 941367442 566281775 840491958 605601438 371131391 974262728 475115095 714960186 543893552 335949792 860936847 62407003 438827139 807631026 846617922 268033786 894201482 727522851 99478144 83882305 219092683 757284698 531013029 770814108 619420129 628900585 817197055 376494750 677578021 70490096 853216828 10270151 273412730 22958869 326510311 149923154 74810139 921070364 843787101 18531589 115955493 394871639 809883780 856563565 886626939 996511273 73196840 373437688 738657988 318686643 182439850 953616070 880146001 699750261 555092801 499314591 112928857 148117003 889544603 90432199 552139606 682178712 528283663 573976149 228061004 797695431 116055921 680997223 477442670 900659468 716340207 97005590 192223032 36039487 518029950 904522767 136379747 106134442 253617271 939006437 479999547 824729807 464349785 451925658 911085708 873569363 883830267 134447834 418256508 594372958 927421630 179500796 810575129 637358030 44846184 380798416 123406312 342119345 29410367 67625157 216857008 106529031 884291096 343864594 756469772 696841999 656974307 288970568 261639348 546035606 118627439 984146078 252458994 920922855 847288384 571715892 117076011 38911196 627907810 111230291 543323900 110609205 803709746 97928649 992575427 186657375 162415278 589635517 774169399 513542820 579369930 968568748 145366751 26493898 419458134 580829259 247895074 231524349 140120725 644164020 315134389 616189295 401962830 593129635 353094466 401649343 647806423 20392873 356957506 651948248 667815536 769379466 504794811 445727789 72931769 582557493 697376123 386335275 623692179 446699457 403019393 246894346 317686911 859348764 74522343 314306638 374106989 720309582 663365490 247676089 252086322 900275683 3647313 510291732 438202183 124427221 801989254 914644101 217282885 593555545 207839541 177639379 438087078 47914992 912589198 930962847 344773362 224169873 265404181 140040482 485530445 731908684 886662086 473363129 525392075 720514840 996542021 117331355 449704292 664136881 732208211 70511479 527147599 221236281 124107471 684272663 778736281 945928779 651128155 129313259 370935930 809549877 764625204 675120595 576160786 212876286 27412633 849277142 892142570 595224662 945796496 149592657 904657548 423630678 937304336 807040028 871449482 465709945 265949136 527673445 208575862 690200158 185838199 991455243 811645631 650303970 904771305 747092490 998739622 97200681 93203833 305171316 951239326 762614065 501023890 971342349 783127045 511599026 353167365 413143744 398271909 546667439 589815813 483079739 178087709 503378751 381301500 93620209 463019011 162152370 338234174 240047254 919476644 385523341 603686928 973024739 11880471 911563893 36285967 968414794 927533240 867999715 976653228 538334655 676202679 957912860 840090404 324266668 103776594 227129373 205860516 461041723 562980173 546785203 173141997 351390105 485663286 159550266 770944260 252507370 138661388 263253512 881505023 584339388 482001520 287806056 23968448 178820190 705718156 120716744 518578858 959616420 483768358 783166685 425089401 635872194 441710645 985155015 252494339 86849845 409528013 803304322 977858933 390657290 316079419 740259318 303534215 497295537 355295155 34329452 20240119 830465830 121422033 9889771 635856748 197160426 119532441 675366777 529907551 816635763 329243087 752205938 94216231 219603309 123062859 120235330 233018996 671931341 562309168 799668027 452900892 650849080 321170673 659625782 788435491 157426821 445093768 577643697 753037099 700280164 925323888 890787126 44286603 79814010 4109719 908832016 509675128 72275271 884008307 771726198 871428967 991032489 269780651 589671433 692051485 58362694 631040452 626726382 192129560 433948381 687338156 917728354 551720890 813538777 263298717 185854375 122514492 499374480 179373838 951993181 208438779 375992624 96659172 71651694 238622471 573633145 213391191 504193 421090986 768469533 406586292 283974167 800537795 613251036 767194463 108389291 548208321 9276355 752959758 619896350 194819689 295632345 776669395 892397473 863643379 146296434 9238336 786731657 551432118 653341155 923858361 78019920 263071229 206837618 556851100 932083556 956430055 851830347 922230219 712537844 683123521 908454936 955989874 13355944 789754813 490220793 266129906 481349002 281678476 218494824 511224045 683222616 254387212 334121393 158690193 312633796 18579426 432172067 184340677 111928181 699196811 519177663 19592425 17967415 187913619 493469663 94904310 681533676 745150863 265623680 815322649 449426365 796198915 881024664 742876617 441431280 278310766 514861600 151180703 719570362 164097745 947455764 180178193 721584943 753570924 201299736 626753889 108213205 691241009 795199934 159906316 595215278 567645668 352194239 367074225 456148084 111313236 879081294 397363021 623273077 536122089 215401920 235849201 955563234 728377724 574621959 170335930 319800330 867067541 6655194 937802583 765888857 690672451 727572661 617923708 19574526 765585687 749912023 409546257 140046209 134777591 633540929 126673898 209748418 313385646 576062935 274979973 150764109 65206676 652989647 962680585 71031838 996340458 19788933 804542304 570421097 791886704 241404302 814112897 167922963 992375714 987415107 559097522 177474233 866684472 143572349 936786804 370989027 959865455 94669145 545546264 200288845 359974970 405475711 812239598 702152195 898822052 89279473 348186859 696082482 458560331 739721599 865834768 149208402 955091476 396069168 480128889 407719009 243581681 155113214 955542836 885154525 757395648 321562751 754228754 380646933 245457131 793471004 119488429 670333579 501738629 759946894 593681378 346093827 564270438 784358248 496926099 12626174 315840584 319866730 534119136 48239945 108753561 901406589 30727278 136273822 839615243 891963924 92126596 935113641 770311944 17937216 683568229 701785946 166746373 10167430 571824249 22264164 679741806 792383195 739969032 440049552 87926627 174679170 941775305 394731679 630828357 704917810 152379152 676151546 535391649 100266173 313532751 363320019 65719198 996789991 736154453 814470953 197438955 918409882 697499768 657721877 72153412 858331322 879328239 786506343 944098060 967931244 557624843 793903740 714494904 383515491 913966623 642255899 531266681 657198835 247017924 270413957 254248474 458261890 865773517 677098816 866211120 823554374 83500696 676380137 496397638 317233400 712589934 29264692 525424858 490110338 944040673 723547648 728056890 415740866 891454221 951797099 895442612 763885520 754256729 838898468 231988828 542839753 231289555 553047025 164705519 74107870 125135939 711770208 790302993 522193971 687902925 501218940 524401485 46664404 561368003 595353584 36869673 604056349 680043897 592562078 994985284 824604089 79353753 987345022 680584375 271225282 565337145 999459116 896366178 191291314 662151376 892620299 591569687 714752273 351975572 15783024 574955546 60338910 311971856 184980908 95388421 816718166 766758621 540298207 291861718 144655571 186735112 935523741 765980731 779150693 625202109 817780265 649694388 697099046 747003007 833857221 614068221 286985907 598663280 558565112 413293969 545249003 175068227 577507856 481895227 532868000 488714192 214071015 151827376 704951384 25992483 185232467 31236083 972888574 30576166 253832029 683373609 297896412 964310799 339053947 89361600 755949386 910672343 138568079 672410027 73410423 438720724 403725066 505646712 147510802 291624738 966351829 175456038 81649067 96188464 329053945 778385400 955725664 72731211 25709673 238913011 523387272 454459745 640148057 351786101 939766517 704167493 500925978 630991546 852313328 23488162 272826393 56362430 711641015 904610505 527920529 401626533 297737839 787486526 630768722 788802203 306980595 938539331 984572488 569353642 312483816 870315620 473692786 188079341 885550989 388285785 152730054 76270284 146662601 573438906 653333802 779418782 980052577 368363856 998532830 294953125 159231405 574598074 94542137 525123031 435485034 200051445 184879824 404211497 6268573 695629154 979466552 247734561 306262913 398013695 544150851 768853033 195607956 641879493 325822235 40113275 673902258 612226477 11597636 938372591 525281734 624069967 912268726 631981882 747405455 17270381 774317339 956822231 286665957 20030370 408457801 233151104 527103535 801755116 270763514 193018068 57041437 998623251 808906364 489589305 620967715 246897006 438150236 997653719 823643885 767226027 309098742 152688457 199752581 222986508 648912254 21899656 747607593 694480722 14375666 991041107 639543000 354671295 784543722 74648392 854028121 510843687 719723472 403986761 138626456 456517287 424745506 490840525 961122556 449755903 943023701 576873903 187726623 250636032 974963699 478176977 938971632 154824219 70398797 681141880 385695598 403403737 206653549 644340723 30232195 582496737 835292335 161843376 151625322 513692034 492223096 532108856 679995865 681948976 444066116 376917846 281097184 473710466 619603212 103646102 728560075 965669987 458996668 348436550 929196252 199642309 308854602 159419721 198327051 766051005 754988555 435864119 433460599 363446754 882292033 749310571 610898956 312530231 627984028 117970191 783267970 105307271 47553009 692359520 220586582 644292074 165827934 286642481 434056837 382354835 897559569 223287816 641962727 537959319 459517832 207737066 607459295 243847578 304765014 495306575 797859798 315776649 195206662 58909032 931344002 5818370 772462302 86407354 753292602 335916747 461921676 32695159 960442796 14281697 985994375 451080445 823210843 774049941 829393081 899988631 318344997 485129420 525308952 609448144 888789087 7038901 187735792 959316817 74057735 847345348 740144526 328076354 792753794 792674138 489251216 689759922 465766466 979653187 508946317 453290000 21730472 592587850 953076773 686598064 311234753 216230219 479235278 537158891 671980367 895854658 198781930 265561289 342871643 372368368 975121614 284716565 50904794 497242319 248595275 29620947 90247581 742075445 482353061 488793006 589330249 859587461 935073819 129582233 794593870 606733135 137823973 165254279 926815535 543001009 531221041 845715918 327074071 407816889 220492933 862476217 42844647 908595385 78548902 522083766 925958173 588767630 733312973 119416532 368846329 861969302 74644106 596060048 529286465 401551164 566184509 48361224 915453365 452282953 444811272 746057645 730640314 882612568 630546277 16744095 129166542 342255625 86956744 656999293 215884472 118121261 542916640 818814248 124282486 658286294 713493523 597045828 398387214 458810010 38228322 731841247 779193457 289371751 676899830 307039552 379233255 553247754 612095154 125250932 622777649 82819709 169811360 406870588 604191310 534418897 737189659 627979413 585819188 16549844 159042364 495517597 761302458 312149165 678099907 678771934 376763304 541888538 309282850 80363510 848201439 949929024 253228887 58956430 54953019 660889781 432925203 718703711 824765577 825231301 590153441 41354272 653602894 311164057 929849973 311935522 416870358 183748934 984279395 748129234 204169385 416419139 709824246 427528966 544948903 628372777 211949473 680104756 13382121 982825511 106921158 392404801 575023528 439498317 657878283 275406548 657480681 990944806 124740411 942288869 273440417 349333970 29533808 41754197 692439399 679431926 414220346 47469558 293435777 209694950 362619158 968305278 199764383 550480273 208800544 394531470 214762418 154603263 468508738 737975269 952530962 420100659 372341290 351886105 840544353 953543537 89063230 462793287 331742719 898104490 825897876 339988404 679767925 679343826 322040977 55271243 132964648 196401295 527426845 166349992 997682622 581886377 937823788 828368895 329006914 931872168 657205581 630348825 134974500 781054585 50792725 330677726 640800706 834767009 781786467 713345449 26893300 751196434 4949016 847293618 656068472 362163513 459860345 96212822 693598651 799621512 283456874 44576696 825675855 705597123 24508931 130860755 644768965 265490672 432608941 182349307 341620006 275061669 335891854 393996737 402035354 142933073 923887999 486192958 202675803 620473966 198007420 503189306 928375437 518189291 395636158 216454120 340469481 506550607 562262877 676930961 854225379
830281738 32446156 36307314 323219415 251939377 42435723 243583165 264223771 966734832 818353059 590764836 95301 320725004 406520504 149970526 747589689 244642693 875938352 390581117 359119579 149693102 523513210 651592061 277757879 515441453 534564861 408425036 95252876 357371956 914416528 88111294 256421214 553300751 52565235 189861347 743332700 125931818 162475165 508074865 268640213 947819737 233747870 795951863 963613832 191679987 568758053 72304398 913629919 206531618 467734257 139948982 665635863 563913406 729546666 796458695 502968149 800306121 955598734 755523002 293104564 246015660 305349281 485526651 494107652 220182898 934957190 803498487 552943821 143320330 561577192 979322298 887282574 94605922 849389117 750247773 319907811 651960248 470139582 869754246 456598486 851614202 240188070 730872067 843485120 825267566 757557526 753448260 608131713 947617028 526146868 516865598 452676549 405298910 39622870 705828738 64110630 486220463 238632786 707267724 927144101 632273215 706682492 216377821 683614951 963440975 494335103 579086599 343162427 777117453 674710921 921484337 715845904 162487205 592197117 783326532 917944865 206137975 126229651 679291097 212573367 49508736 340799445 6849625 256932898 374990727 988354899 84420464 729676372 157247960 118650592 743672751 963364543 353270281 328518802 270720519 979141744 515903051 531937704 676734258 727153322 769130327 974877029 48835486 737181347 180410873 189437589 746342273 214488459 613309778 869935177 847211110 583851437 115567379 633231257 416561045 176629651 931581089 132161398 844612164 423563374 524144003 664155995 666742941 65168835 795888685 827028904 441437962 967580672 874306752 367804925 408612209 802247158 153365616 486474578 34766074 605132625 636381778 221057479 667400277 751508094 210827123 331056689 485045558 999929537 417328587 14231732 636634501 332718558 625478589 297741820 966043912 295485638 220674463 298718975 417059541 695087960 424915494 531408272 264380190 348874452 588319254 662943832 95239102 542859453 668749468 360081851 881949863 142021987 848869422 875060695 899328748 247182193 797735296 970109082 974006073 595644772 751648183 647827177 995349034 148127865 210388665 521893626 242174251 461939653 587660548 221416237 105519174 35447374 41769505 563421028 111038162 747617443 29015497 176827070 249257067 390813640 868514433 471426111 933502676 852274064 474462814 151585829 924474556 510988080 746180245 480594724 763747513 487176308 572851083 90595966 958765457 309118323 843245632 949108954 363546827 621915405 301738418 77478354 92699223 684795130 736778739 681619246 145270513 51345344 269964121 863174090 550110470 85382238 189849198 193443087 76816607 566130271 313385475 219984688 353256465 507029779 245196010 151898891 667170898 803563159 509063003 891502753 793694898 808976418 449152163 338787919 171418046 166985535 77880634 204332643 100525242 523768879 622609905 670361152 712665595 657049808 33596213 362619479 832258054 769660652 746210979 845055972 876879752 573664332 13108548 431346660 211721791 245497125 689053623 808688660 54474675 512174614 574142562 327377439 86991611 31786931 43666385 197781165 993358353 811846301 846157236 269488653 394283594 925354783 783155180 354049224 775894172 230017421 693646627 283934260 370576558 283175918 263045778 42334463 118932532 987920405 552605681 213352205 541501733 152037857 431301383 426484182 466314848 856010313 970406350 826600970 147759040 508409330 552054009 240775323 953558009 58605850 277684569 315386918 533453700 536991214 811031457 94269831 491399960 191754234 300115728 83093842 868340579 77104212 408385392 732427630 813433458 997105591 153383281 568760961 401301543 639585919 744451645 992555742 392755171 454821498 299294687 480923034 663787738 810404618 810122858 76704528 515268994 737076303 393833597 512005384 311593380 98710003 656495660 104694452 35914170 28241338 435778469 108158122 699269903 434295033 501569734 375523662 322711831 264466740 276130394 9064462 395230423 980498152 149708073 211201514 127877185 343790629 507225865 493956465 264802697 683812690 830905291 246592536 197752585 790275858 744793342 910703663 332456542 164938749 494835282 208980716 801658631 957606516 661962962 55303549 134112760 434610325 534815170 414674661 353788661 218281441 769474389 549233130 787891950 358796655 132671045 343774455 319855035 862818164 312593479 855602649 254882119 140383658 244115585 758018997 101908274 110578500 419032498 768315139 644935651 228384653 642292701 711024726 190734626 357033890 405827052 400057340 916770617 14377924 714845439 924998834 576246629 496981523 700393651 59107195 336051111 714839083 19389149 371219825 951685549 980868497 330155327 490200092 139334856 254936889 811198753 162118654 637211253 448261367 620264003 400594669 728757299 189611244 438213885 451154111 175828015 309414594 719455461 851459784 260199469 878505328 587023405 522001576 941590051 899599805 953009248 461368945 327109767 928239871 635034089 10932925 319829708 551320667 210040145 111643998 718810785 431920863 39480132 600585625 820975173 230615815 869819456 404764767 983424421 391106117 913409165 417862459 54885837 373353510 388727939 543591211 68939360 422350784 277896613 437165801 876673725 492688586 68868230 262946163 585047396 989321575 77212969 151235506 289808647 733977651 655738107 224627479 710206722 66217815 335401914 845078444 494783948 927834292 572732784 61569479 281491460 765357924 657758931 409133066 43419076 654823725 170782496 689071594 802518823 941991503 9375574 623155629 157108309 180994188 163280753 677375709 619266581 502190533 591702939 792522227 126925959 38503251 383165473 751227029 115024574 943821459 284967855 548670247 591010666 561164026 250893370 63027975 904084396 877280676 113401901 223337055 692989646 516414531 792155641 249572520 599128084 939239259 486282425 882985260 489896673 888271331 877107764 62680350 211181780 324411633 184471212 529029578 954168924 171005262 901327916 722828005 840624629 216270944 66274260 847200630 465352341 125160376 93028526 704639600 917393156 344965715 733961998 720963201 155838017 64886371 154994738 3561359 405277509 439743912 143127439 495387616 664442108 541160995 284687998 643316095 582809443 53670436 656824471 916394703 425162719 289018670 646868399 391941942 798718449 297213341 887086071 861694589 94744417 399563487 253011426 114487818 762822744 715067719 480804298 967706951 497257860 622267698 186482450 503065560 980587760 696379784 643796112 822966495 43110722 354022664 800122258 549385144 347121043 809439473 884277042 875587391 349193807 598794350 12242982 402178537 292088550 291355718 959664025 168612184 204836686 188621180 255880366 966881915 880909161 622247361 57425890 139065097 819272155 717993356 557074731 951857177 553410209 510997025 775454655 69599507 660126887 265657692 991765668 508309836 101626641 458165102 427850759 922808881 776687241 841766904 571249454 143926481 265728002 70311973 235071536 610171836 666253666 528277761 850939447 765361485 646423895 857073953 634215235 584206852 503547398 95733679 271498343 499363770 475214989 62413701 202802988 729262373 226900442 339822509 267569789 932309141 654859339 213852193 981146049 702693915 248517215 542148666 729462496 697821811 954771563 111799393 400816035 81421059 19888608 83719471 531720320 723308124 52195799 803670700 124711075 264002661 202137868 23416500 829728307 999205013 236643848 450180533 387946147 247589448 317541835 547049886 618869173 223375322 140184388 23894349 69739903 435986388 59650362 877946529 803636965 538238345 125911562 716953213 597351903 194980601 752184090 571727698 278245910 170388327 476958611 642186265 518269625 932975059 560135378 293173479 529855549 175846011 60686311 648535459 538330656 417848977 723172138 236101647 486204137 797256943 250870133 321518413 979693767 550168768 782719979 715126278 571556211 975030409 901218322 633734337 337241539 139526058 640652082 719656480 994820536 566857406 679421284 57690692 475232936 401317621 983171143 6903823 358986305 880925449 277165721 417657338 186967810 109447264 380953380 529061178 323921797 293669620 758499643 444093719 528367438 865962843 271925963 342535002 301698183 578190258 322007059 762581522 352240746 74122320 801657434 172792927 434772729 191635759 754726896 132817587 44990997 439925420 961748270 921364592 600126909 489205666 743634779 732860310 448428389 393964283 853382510 637742233 805059376 930663659 761093899 281693744 282047271 636168228 802264557 773071944 466278627 798335549 752774179 95600257 710597373 87270296 413055336 204189093 208380850 844653776 556888763 568680598 635049411 192152145 620138072 742916842 36663948 998803145 364168419 501988880 683532169 859367170 948226883 825853805 646102466 421177294 793591033 201065640 892696492 288604528 940684025 435047854 625222125 152211092 953053778 500787674 781758960 621039377 646246457 10016738 590973023 368927922 413926968 900759287 734729913 41197642 340034335 431854049 786448529 985477365 81614626 878992869 353797115 139653590 578486641 597150433 383717698 434878417 581778831 47196691 961330203 906738132 145898854 570119464 935187145 5280115 266743579 794043103 923997680 744133223 620725883 357080630 605422572 789091737 807393162 758813236 92452470 429619293 416066023 706229285 786302078 613858732 756848799 138357511 99300767 98624191 671573552 968381521 392653517 145974808 707102529 970804195 78882659 211021947 54589102 924059132 953844795 942901519 624424750 724467324 328905759 989257644 61825450 909039157 958711077 380106958 828919720 799849982 211266232 259464486 137688563 452058636 765980795 476858142 225428126 479832262 181391003 598816311 463947204 659232542 92462783 139560524 841002847 525469964 522312731 49128790 764280752 777228694 510000450 532748452 269544849 445901698 136443049 196572559 376320634 514790036 30431543 311614011 999522729 188420966 26476461 204181878 530441606 337454577 104124243 675301020 486645353 537704510 761298749 600237355 932826076 15399214 865294565 370420313 491570007 782635596 338450522 436129195 882388127 842944617 534657401 343465273 372307314 990313004 491570713 400449982 868397926 301390656 950654516 618346913 748693556 171265456 780255885 771469725 461912137 164081376 683964237 826900621 96244856 609233103 75474625 717963091 864526245 803038829 340654045 498977786 888264118 40394906 207714491 93674961 417816503 444142854 668881840 900083763 159021443 439018135 732943266 93305688 132446093 280634865 785812428 975878249 526662109 926579132 846616288 489420483 668954412 557805501 509452591 289971872 603392138 757503526 62896055 193578747 814134478 260957280 434438367 32120945 318033006 427031932 356074159 764950222 92663042 177601805 302909471 465642567 209743916 227290662 794262074 49304778 355637335 314679544 323018698 72897577 423316841 415187277 574404508 369175636 341769119 5278537 394977621 864486223 356552659 215780795 642962880 623727362 750782606 624913196 111375663 695239724 908276093 738952827 882298985 518375308 198855233 970369127 990643069 553854533 693903706 224283820 92466397 603466683 742828588 405687712 820398562 747184792 680182324 248800432 95828252 338926482 402388196 964191294 119161320 335772346 944900059 374043057 649199561 787296474 351519257 624989285 13720603 982455797 296863976 985910651 288024331 804708685 525182048 697653655 254252829 77444510 322428816 527869086 165516877 280494715 580899105 876495694 627244614 729779052 486648778 21340935 92263482 148550201 445523075 764557550 518040551 946066389 74818470 149759239 144497223 446222202 791049914 576448682 802004976 610991659 466906653 124200596 754191701 38348740 903388252 156076886 988430808 163526358 687422992 232971535 95078221 373302246 338027290 918459508 721327993 299917656 970808314 589224184 247592497 288233967 139504245 681058651 749989007 258344940 728886726 358178079 99638126 264673137 626524797 923654339 864899860 587235064 187316672 987935817 713987561 258659388 757558734 449903928 783654961 205207942 806172247 383056694 865972395 963729750 460117861 867910987 193704718 418756860 369491296 762230675 434219562 579905761 954348679 655266712 556487093 889005230 621689612 447210574 182943880 789371642 738900065 497140097 321397876 80128804 264765311 131207777 64746838 612246770 327561836 942941167 171641819 493963500 107690313 313991582 270247664 996674262 340463075 299868925 801306337 764270864 254160882 169187787 171644520 976603676 698537788 529970238 985843760 894604119 574764734 624135855 881684162 579192582 934118512 123907527 733496424 225827725 748936280 492916703 355544974 201693135 42757449 801765119 495712287 889544067 595980690 478910842 740533111 848303047 57880674 847139329 865157628 283339235 162091462 800061951 217549507 795937318 175109392 840766684 310408542 582972128 639931961 987057009 6779407 672974135 42409441 610634977 904314985 28010656 737499709 336920553 869717065 561336094 484308573 450794303 908665083 902149403 914991725 121497504 806881193 351329280 711635502 926073176 787811247 599916168 527553378 439342648 719682907 26900280 538849124 433970679 130490162 818475305 326917341 137834414 813377685 306753439 978783180 295370356 164775292 346090761 207820709 764453621 422730118 141283386 38955096 229547445 43016705 619275839 888014859 246254502 262084670 492605439 579593513 247579517 727775012 284957058 706955766 225698586 368998954 738316520 149863729 105736186 307453100 711491542 112529691 345979455 558026863 326191721 334838652 172090932 510647014 318312606 611571435 575966267 782516535 51796899 266594970 587753252 155390003 472419840 403802164 756965056 958167415 817185830 962434143 357404927 726364614 779474234 678906281 668737617 578918588 592780094 184700923 302398188 902130256 433394008 828017960 222198817 637471554 755667780 603321179 674803670 28230926 672047054 687339280 860312961 887126245 541391994 907607833 553376672 346384991 262343480 500886417 961183969 894134551 83397249 373396842 102341687 334814264 551940657 775428780 192003052 280221785 541972138 338085837 206063095 742631841 875452951 756767656 844496425 872310433 185292901 774410223 323106748 238184438 99205279 322747394 799403135 613733581 623855071 35292645 428294156 395134941 704423236 962440563 645077431 881682218 330641397 138718487 94475436 460839804 925389862 692883882 871123192 588538561 733090680 201723892 625683428 623993151 882302719 194755009 817790321 631995817 480729527 439653314 118477337 648290902 717164469 785162935 644423046 326685245 799076443 710807024 580005546 134239712 930353769 244631838 649171582 953366334 925359822 460484962 260066753 907829309 492553239 578671041 714515624 795688819 75054764 529823275 649357881 419619855 766994414 362642512 331527572 714339869 307492889 305377912 264011210 282316291 957648206 293350587 391910136 99004818 436197161 158984285 973547308 671730891 784328015 4115718 996696396 546109134 998421358 939320163 537268904 975148637 65168495 950066336 320164516 269307528 168875805 159889989 676592711 594347681 920071874 305678816 783775510 284926872 726981323 993327401 231295499 320209221 632711616 385430787 356816062 25034504 899171830 523934847 929349779 324081386 91569003 981348998 306163867 886984060 135820806 864059868 90694232 56997419 664296277 783076704 650006570 359781450 777564476 98733373 144636068 865327010 909815513 324190425 547162458 118243369 264624602 694324845 926493324 13248152 718812164 407522096 786962418 63452581 384651915 232842814 172026579 178160516 218052589 100244728 36791410 600437056 188900254 905225628 943302719 353495078 104668926 126057567 100591881 828503949 86792204 602999475 74330923 391999694 137067818 863460597 513699618 896126606 636572196 371181999 956576240 782944903 394540530 495335488 672247695 285317789 503807113 939114798 91338929 585104593 429915779 860619050 935283991 296595161 298515368 302137749 680931331 100011518 852537562 460739534 58758867 828510666 242061991 109622169 258520911 775622087 277158357 30576388 363749258 960168920 408572550 569350456 888830755 995355378 579280984 875258207 58465755 911538595 960232755 498546848 600898458 521628298 128275035 79160732 120697479 390726194 868264033 354480051 566249937 207792300 864372620 401821051 285137739 297264351 923094162 360334157 134338734 140405115 649517871 966077014 623531317 933827029 345333440 589561430 293812348 654724405 370877569 121450742 932697031 132630076 18973626 798833197 67164484 378210894 559329142 571213167 675498374 340960570 709262245 93509886 381539498 96171507 580170578 69858801 588751474 518822260 195464315 540028912 442507517 697066618 783367753 875468940 539633036 638750494 343739452 498144241 572422815 341439981 265651078 113990690 143852150 210394258 551337957 607513046 977256966 937065329 545232389 549764166 600116677 364958244 278522068 740352344 162143018 780709027 379004064 647683039 22847331 204362468 910320052 75418753 104150370 488898003 275242377 805339201 974425127 244095005 611240390 258768736 721712339 761104441 75310430 874109282 589936962 700725604 964994901 877155039 502198388 713451703 59335513 724207264 82145528 261467639 269446328 700755405 780305787 526852624 776341671 729791477 97018785 380813879 205237039 244305036 81019082 450565023 391651021 833097272 309037696 35931678 252173533 903308843 754656198 45813942 211206693 944158691 594221204 715326684 46979717 865292737 457145040 808572179 840693793 597684874 206451287 94190152 477225425 316143993 137719807 70576191 339104288 767242789 743001811 655657803 388517078 619696994 435207605 857059851 211716972 942109907 83718917 323439043 57444318 102181520 341230832 608764101 148365704 10612031 285076303 115063378 183759437 204457193 957987611 542633967 59267626 662724340 465537631 95342363 254667582 807295123 443696024 660648428 821162012 380160029 886124709 853634316 236636050 104030596 560975717 985178559 900880720 101119617 423188763 398244566 260014793 335283674 854533233 74797540 464784535 322480314 342925911 287101630 929261059 678469209 836065116 982847872 281843427 255690273 673905644 979496354 763083352 285659430 705388544 696361111 88971287 231812931 834505113 670882988 620196702 756823033 372145645 711890235 357211151 778955750 251309550 386541033 707881977 305214532 295580528 298427661 946066498 162812762 396776762 422993533 546542911 973046136 776917205 392967601 62830200 69433467 710841242 379229084 543896627 875985644 763960449 78271750 228336017 543297932 394096811 267105017 215418360 359823467 59963880 68238554 495124385 91405599 384424360 741423176 822193603 889872728 467120080 832206343 73384491 124016269 177339474 161605780 164442355 565205925 466307989 91857204 54282518 459972744 431485490 703286993 975172524 602661594 826179661 531961695 283008894 670795269 494897198 299878832 404231264 631029607 672840726 731458223 738261008 909371090 127776675 689944497 415731662 915406397 503525940 395278770 399985600 54853414 895228091 800884266 506125352 166785852 197644621 333535547 487236186 618978110 351304039 865378783 784295596 513301114 673072797 783570464 74479427 175948058 669603307 34226013 180748786 31974493 12964486 61498583 64093967 729628328 330674223 380510429 970615423 516581338 100095388 92701631 68298101 766252774 40205628 159024888 914513052 377740196 31647471 122818453 219979693 297606579 707018532 398244989 378330500 592662460 715340401 630683592 858598690 184237249 558273862 796193638 648651967 414390265 274520731 697965354 492301792 533843393 176947002 46047346 439358162 596650397 733590847 349667425 491059231 760691095 792492034 127880711 899711270 558730423 553883201 521638807 297186738 398076568 833891095 469887641 985920275 719680536 45276768 236888420 493433869 839336914 437374666 150079863 12937411 476827414 418663416 333217452 86114780 408000616 210759940 871604375 511329581 685886643