800
SRRSSRSRSRRRSSSSRSSSSSRSSRSRRSSRSSSRRSSRSSSSSSSRRSRSSRSSRSSSSSSSRSSSRRSSRSRRRRRRRRRRSSRRSSSRRRSSSRRRRRRSRSRRSRRRSSRRRRSSSRSRSSSSRSSSRRRRSRSSRRSRRSRRRSRSSRSSRSSRSRRRRSRRSSSRSRRSRRSSSSSRSRSSRSRRSSSRSRRSRSSRSRRRSSSSRRSSSSRSRSRSSSSSRRSRSSSSRSRSRSRSSRSRSSRSRSRSSRRRSRRSRSRSRRRRSRSSRSRSSSRSSRSSRSSRRRSSRSSSRSSRSSRSSSRRRSRRRRSRRRRRRSRRRSRSSSSSRSSSSRSRSRRRSRRRSRSSSSRSSRRRRSRRRSRRRRSSRSSSSRRRSRRSSSRSRRRSRRRRRSRSRSRSSSRSRSSRRSSRRRSSRRRSRRSSRRSSSSRSSRRSSSRRRRSSRSSSRRRSRRSSSRSRRRRSSSSRRSRRSRRRSRSRRSRSRRSSRRRRSSSRSSSSRRSSSSSSRSSSRSRSSSRSSRRRSSRSSSSSRRRRRSSSRRSSSRSSRSRRRRRRRRSSSSSRRRSSSSSSRSRSRSSRRRSSRRRRSSRSRRRSRRSRSSRRSSRSSSRRSSSSRSRSRSRSSRSSRSRRSSRRRSSSSSRRRRRSSSSSRSRRSRSSSSRSSSRRRRSRRSRSSSRRSRSRSRRRRSRSSRRRSSRSSSSRRRRRSSRSSSRSRRRSRRRSRSSSRSRSRSSSRSSSRSRSRRRSSRRSSRRRRRSSRRSSSRSRRSSRSRRSSSRSSRSSSRRRSRRS
932673561 923821868 959907253 699451078 212157220 364618045 60801216 511555274 616315697 366475326 811862568 678097494 424012245 229723451 665601413 782447175 343469914 447972937 89261458 377160261 237411454 879475059 513230976 634012313 716073020 986705453 274140934 899608217 985029462 910806267 964122040 397165114 190136691 31702283 361515214 725328176 526370113 968525340 289719058 249858669 108963106 291786636 922373386 742747995 277561426 186593408 658838250 774479229 856375247 217347444 121413513 245447671 709488027 162776721 338147555 925438105 300939662 881505406 275334645 159435551 836797984 416883279 364052654 375444880 680990652 584740090 733438072 591871769 210793262 72096728 965131528 802519939 437610473 147909012 839441131 563748897 597722854 595057639 169235777 15519471 596138862 233024534 403889289 964625226 733418168 443724590 592659016 135320433 763945904 541947300 816557611 686338929 612245582 802326576 991335973 586917750 875108733 745249960 346889512 806530044 220570682 769972280 518670212 59466666 318132280 343811685 918872079 257760341 90802353 891885726 709695703 29070118 458409936 448398071 200465160 452991817 785916564 321289852 335683823 376489305 233239413 562386592 870581704 675107623 979642556 349474213 68807996 783768548 620668349 665213309 35574197 243123116 758876485 403850465 957333406 798935502 726909711 791278547 851076378 605729654 817253128 47088391 429175750 20165677 914443458 443016487 787751444 217734801 525453206 548684888 655451653 66648293 346189119 396432974 401753234 481726084 85510423 541237820 424198093 956007701 120426669 702376902 624503869 154305259 548915488 189615458 425163508 927293453 558693181 198483907 569889800 778592699 34733026 618431388 964838669 738904229 3829973 535155641 328050836 344344337 538864252 369147664 514206488 406653334 13083814 830244567 492597792 138790983 20616960 752253793 511447366 698374080 9496155 764754208 34178192 501829427 380462467 724794848 230930873 438199596 7192914 227587069 788504054 633653123 462166605 21970157 276361526 359191031 889754698 465054010 636964623 449097004 303923204 44640021 632511824 467185345 85969424 307489800 885019361 704183741 225653682 504625439 969826239 535619412 810677220 781747800 709153280 199752320 648421493 915855112 328155951 835187142 775916526 717597291 175174527 26785301 315760537 88372984 890214381 223255077 582707020 445100526 385479198 487215094 620428227 457354454 479817698 356809432 914683293 159941600 26855705 863277436 561667693 182639200 433148927 871719577 188436446 180109184 662957430 84092578 375571055 833705127 286055709 926246429 315971814 288284499 627485850 124784442 887049800 42413639 245427911 817144798 335225796 510161020 556604105 281288092 746827337 166325935 108813901 945830460 641492234 69072126 356799319 617753899 202366711 826174167 877842704 578189604 169424383 249143315 46430028 460066999 876676608 812602464 659369530 59983209 442585938 134091925 248071785 848489948 516410828 703662524 322414514 769452060 250059826 163095647 548614642 129641787 259684628 115528947 689263403 577217388 904071238 887655408 42662198 684186403 79880127 110054322 287305135 639337951 716917473 56820816 262708597 206042226 3591581 769456303 102640174 790453930 799599420 640348369 612202371 252905809 563667477 358590884 122444205 863467612 114741245 196326381 662381591 963553194 264531607 173947030 640753564 166298431 865874557 354271639 512853054 542195629 254692073 442495347 231486013 560734114 601542093 528851866 220509992 87237443 978781067 253050380 638299840 716214567 219158556 609275821 412541015 552022523 917875575 484195291 480558567 427455475 801050840 891560907 696899851 485461971 224607165 353935868 309350640 299761844 663253694 39466637 732897043 320545602 536347030 193557403 302936064 946514325 367701691 910752904 730281797 294606437 271127438 54236126 567042849 408060352 240028834 611223778 832998540 981917483 104472502 28071908 62298090 198001636 412168903 66534579 731721906 91628752 375765877 287550982 120582467 357089953 873237718 503657102 153658372 511419339 425928679 499639995 381913169 401868785 905979521 74785367 17163842 123723518 583528672 100164619 234324683 710506759 136359685 650273718 496080597 45352531 222547084 711562217 991172552 888456280 177624084 245819800 623588156 321180986 800279427 581708853 996754829 316957776 408495521 763500219 934533182 260243359 259137009 864336517 977848068 834427794 683710792 942004683 319736053 945364254 882185737 772291423 126900105 317161451 836890151 889869138 943518848 307875165 872850020 215243656 704244916 293593495 762084055 292525924 264048598 38576246 458532276 841723734 578804810 92698543 994972627 768839645 165340468 177750290 531335279 193153323 470040806 109551105 934312602 135059442 160763424 770040251 422504547 45918045 130266347 614593139 780311285 468492060 824071214 420766419 239426410 604952804 287323619 836691076 744729802 308898623 985744306 94595776 691453948 910322581 212401226 584310541 175420210 898185900 622955286 109650582 744010871 701451869 270086322 892350362 741839625 91473087 790835130 816974684 863092862 633801890 350637339 565540677 80653754 74257221 134778124 759485865 174178695 677722272 410581264 682187832 590918334 388090954 623067952 749314218 94045959 657085828 281984877 320571330 860307356 343907771 774018141 577909231 719861883 826169160 371644441 49498098 31687259 691170756 536652874 799628382 553240123 6048861 131302879 222159918 213396134 726238596 37321947 389232927 761467364 864530340 614522644 691366223 499810041 444543946 196782790 943738281 511523444 760735655 345913293 404704927 729839096 301579236 71310805 653781020 41044346 97701916 384577655 869281369 490732632 967440774 723059096 931467581 94294696 752817590 225122956 400447836 750341143 781491549 802361708 423345530 30551062 229515887 668548090 116139893 625493791 840546275 945985862 403908069 335985656 501640127 255997312 843283012 367759194 401123993 95234155 584696573 390536757 190362427 187426635 352336321 238976487 307108326 392336011 303653303 36344129 606692708 668093760 330397670 713547861 106185300 813431057 332189570 504732403 857698349 804888515 707333395 142216998 933412484 25408649 112569902 16206833 828253187 310542436 329669607 810480738 406487760 863449645 491836806 938755350 308334083 240779774 253536020 948147746 644747098 875680505 906579318 734066943 832987726 58959017 318375257 587946994 737245559 80311276 203454511 107277324 589024577 261859783 849158515 682480445 490856772 61980139 847106881 491078083 223505401 693236009 254652085 822687519 760474306 713142795 645941570 592049799 921105874 602483773 207643098 712114169 178466312 692204598 823181860 905477798 766961587 663959448 251540213 108667176 930338510 376768779 583038251 414447944 812817036 331571637 688147931 382914757 701033930 889877829 104325944 215663829 948585909 168412957 632990999 782042563 848446180 12286517 912682139 579111640 186234025 604281736 423726982 372271717 500528124 90858953 792483647 405190859 963778277 954181376 280742575 52985729 94095306 762763149 532849792 805286569 405109016 48305799 649902499 76040355 146594926 837883271 816128317 495920554 221774735 285203865 362896211 636461283 508464379 957230632 223316691 971488632 530605195 871285235 353948140 591244382 337927426 572484839 695215350 422092716 237910267 14131274 96501713 536320606 253814277 458812455 309462921 669388139 962879455 845614903 501957533 142296483 741347812 591610419 878841638 842470477 657284458 741772866 537206417 173882687 93931874 909701072 688063166 213764473 522415543 231727372 992485020 830433092 137363599 500654975 882443613 620251753 401065132 633697218 258861354 612247468 308799352 335185295 733349665 575939809 836776014 196613226 9986823 121189346 779630082 610742941 402451505 79053032 1017065 759946497 98982790 942369632 140471108 518835857 140440546 917106049 790337799 311599265 609118723
815293998 135482749 842313620 770933465 95243679 923675619 122121392 74372812 613648730 795013926 595627582 455134486 21038591 91521964 371549863 853206006 859191734 275970512 618083275 763817242 847299729 621052650 838434289 636956828 78420031 585103382 63325279 310297333 375753814 246671643 141624528 623585392 311289387 777753549 663342638 441099478 277111514 703476545 934661164 444936378 814221024 83112142 155028088 566551956 906637051 394909251 549680780 846215499 970265303 118612691 522214820 732155963 228388032 798605656 875243921 693664735 77936888 893360331 735116716 850144563 656852546 946591979 861040696 717137472 94119969 67420602 771581498 83963013 361736416 611025454 720442031 106941357 67209621 887251729 810499 779674815 644265193 358772278 855185721 996634420 327461943 111522182 911565219 324094290 150139676 14346842 581693361 599053137 229454946 379857980 245939894 345161262 324226749 922324633 706201226 86273233 179281979 716196075 699350860 779864232 352220158 352074859 379360574 689253050 684559556 130057265 395621318 631485779 720216897 332941804 477562391 311784090 316371843 238651485 773890192 806723304 147249231 732960 941644708 642143180 921483970 986567976 27088846 436859188 733070586 649168045 314502200 954277051 134262966 162869029 815887282 850384476 428857076 121245163 105366993 810146922 129197616 195363997 972304655 11171842 987168923 686864440 732591970 89991220 612998793 463212668 58779803 757738232 920258829 276235598 977048956 741752565 425683686 195229631 356317078 567378850 803491212 904127687 95225874 626847826 426543839 610208056 628091615 359767619 29816863 851654151 698268194 210355555 964689154 55631364 109569256 858162113 682020121 777604429 664454765 288004169 529510202 968552742 943104174 401593491 127915368 186845458 598806230 202962719 425467093 31434215 124727940 505100928 678716376 376596063 157188564 108650625 365566892 675465188 26332457 783332073 122513487 319010492 903134937 287433989 488181129 20337883 265515721 811389508 845070329 605618134 867846912 111925835 321438623 133385883 960320359 361204156 307220894 594100347 846245590 533298436 66403395 725173695 817632100 99998097 241175627 664847132 272169307 171406545 307447653 921072926 863009531 782301296 406312054 860021979 552873348 143258985 442678699 852484100 665336459 156460178 842458611 804363609 904253524 751632036 471207661 46789532 929100884 608407026 453996348 552779009 85832610 249145012 301387307 593451997 596057675 256595130 37151527 77608985 440817246 696504451 159680401 233615742 194824075 156928775 988328431 461459429 944046552 422620663 168933187 568501521 984693806 910883601 211879718 263908919 119914822 500372797 766725484 420971819 724707765 234200201 77084211 345850819 237968677 106006638 866432725 897292755 568312587 99777588 671079723 810174361 27241559 448590021 752237658 450335836 844359821 206619569 707990581 615403577 621322383 380745056 499185353 882445399 741484141 985418940 559503154 631296029 943321227 60780088 713775917 381621951 299003724 846902418 257233077 248401768 118994280 644329258 491515332 656176510 671399058 19372391 837557288 122189735 958026293 887371780 901214306 590157333 469453189 599208838 398424470 946774295 676468096 65561005 242213275 430982170 986664232 147038898 462890863 803098891 609489585 505583704 164811918 873262625 165650920 260589373 599997763 296908567 843709037 83038456 276545924 809583561 172689055 145614144 911920920 853945070 46529993 134697140 686753778 560779024 761826102 17841740 690122583 556121578 562137206 507389089 236178910 596344373 731673096 687561283 347704257 518036527 943473838 117783937 555148291 824684887 144290010 116830276 898468697 367230039 479453408 986097694 992556598 237645180 281096317 262624159 762745372 200292657 876649382 819108316 768368788 432531208 857231075 679424631 356804832 492040071 717846563 341205194 763334562 906161815 18935368 552177073 514296207 446854611 886922567 260899390 731909167 263137820 745559019 927588933 208096546 996807645 146141396 900697556 856989824 441470969 392011711 887620506 215883096 564488357 550962166 512335172 300227908 127128245 193196864 404394948 548462892 447556148 474902447 292068257 633435011 849820217 447646679 517049130 991090446 214195400 206539762 383469423 622539983 26722025 109683171 505303111 646085218 166292343 779589427 656560412 585773497 725150543 111335442 470726770 136281263 733745182 141714641 8084235 107923517 612672576 646160529 670928808 243276574 585087170 55634399 994637985 453481815 510865541 465450060 855363602 376658078 204091228 681544076 910859800 592717541 775122441 688564153 706763866 54253910 916258690 83652389 215231732 213669600 709654617 214879439 129963508 931873500 465876109 923795300 850128573 585897376 910843410 253880209 850308956 127458575 95643289 987060474 165919614 950254187 692472254 128211859 357883708 269316101 925976946 173956314 645727435 957558272 817659172 165198160 524553158 564866179 471282055 495991130 318116025 48685130 406489067 983663361 328006596 875667202 155369785 934492671 32202548 282936015 820123378 627617584 382196455 945856094 633364288 952523093 17916570 135785620 97498411 235798788 263256562 417278684 849651714 342898351 643605265 791942581 561581982 657037697 89032691 677807345 106188824 276101568 36796536 191294811 860171929 498037710 270022967 975625305 464583386 517073482 891018697 20784537 583244421 848621045 299987468 257883331 590350055 337954938 833407093 361625527 309443126 690803754 565872412 440059925 30160026 203265937 149557795 257172504 913562187 628073822 62991799 566567443 953893026 946930645 197267986 434158019 964884457 695839426 848544365 591312068 783827083 179742467 804215193 723656806 154930133 704071370 47902947 537727146 882017744 288669615 333452361 457060688 86974775 225478932 267173437 576198691 509362697 860085219 172917439 608270996 435894178 599817133 948858777 367736210 281881798 716117489 964214626 224602979 637206971 214660835 915140650 712043649 486538477 67841893 236016640 874898759 875143104 267738689 474087382 649216114 466641369 583995802 912039184 828581816 201445693 387384587 795209005 509398229 570760255 839207486 461170077 792017801 120831239 825353138 14056946 922979840 972373228 794914590 285825469 100857945 807279203 746073747 585029500 381122683 18105129 590894321 197376866 990675155 508962375 306523899 635445394 223994756 715550758 205339622 18447573 280050965 970046521 221142947 54359533 723942198 879162921 908424333 619718312 519700970 209868117 500032540 717033071 633242266 16059267 42697771 391949617 276228458 315285064 906618072 59939679 635159337 852936909 315899717 382427936 962357979 239471706 201716062 213485184 997741501 77516957 453720826 745699433 977590301 985312691 685957593 333703766 681026789 534858053 458505171 996972813 505655564 435032931 244184154 178537796 991326460 153349753 176131735 800628662 782823637 714991072 44119419 136643677 555824421 287171212 135358620 647218534 593868256 269372639 785467419 763894053 588969377 643496169 483560317 985339015 484570807 390865250 779476900 114075803 986339376 229564506 135001125 895055596 51862270 717065887 436628608 670973214 996850802 996402409 627152714 764285822 565852291 511369977 419696982 574073816 537439129 434199889 794642487 355308737 678452136 690517007 391476215 905010662 229558271 161414391 427146532 240337162 954175415 493343011 615747654 769859244 837469577 623297146 605850426 255370482 711009839 384611626 215904876 180828217 77091781 15082050 855846391 315787669 663716474 441534061 720072754 157538559 335440363 75351913 779629051 184114938 606889241 521957133 393179124 353820935 70170672 427081800 517096383 966628830 812361881 601599861 430744048 412951471 523876331 534738485 595527802 700250131 427817809 45084617 634980780 124647216 713091766 692330347 281209950 231759605 20686705 618872412 221716324 988811188 482364581 4625872 371153396