787 666 418
779210444 407626302 802470429 838107315 733749339 748750203 332550672 985907357 148392855 486204784 830045938 157596306 248737498 933903134 310261527 845227293 959995922 37184828 684402087 772469695 706707264 853722294 487066399 214851437 538821370 473387304 610728396 498769167 873527529 843646311 461164627 666161154 572119116 560385528 168623148 17326743 715396212 485477783 468057634 856499858 227821894 646689714 652117717 685289899 88036796 209432812 763430200 328081424 156235364 569733530 479415571 161735394 936340447 617989193 352279937 116783283 866071395 134439990 457616755 550439438 635293498 750793684 762366508 418853871 822881601 536867658 50280900 575821895 855645546 789524722 523013541 482141306 19863098 841484252 429850897 57953248 84982603 596784713 850008985 259083335 997923787 175636016 641354151 582581359 996359932 570998204 236181750 202043021 932692658 630761931 307196692 218988745 472459224 253566577 736455143 258524095 350778091 277498739 363654181 81602306 436754557 796692173 151917530 868966292 642843059 375223085 843403494 837944432 768463048 696758389 457000316 481147137 570923912 531483708 759026341 204106664 560331222 232797262 200973499 752047673 832388646 30449960 276559854 303151230 106612227 473817213 393542338 777364659 987653259 841189299 371449999 568770568 14345966 220713574 315038720 241747747 271431922 798779109 741666709 300425371 25986418 285523120 696487969 874514302 60706522 426269952 258940236 680327116 666852269 630751551 773309458 419088633 806358783 703104907 361976130 840853615 17741052 946266424 70741503 148711433 683399519 271225675 262542915 688828570 198894075 184978175 417485655 851005028 886974262 893332548 481881693 82785185 826488457 536004667 837171910 636371710 848661761 328548283 715480284 579126299 805797825 23566287 157927993 54393868 14583422 786134582 263137870 498182107 299463169 999424482 599170782 676774659 581314217 774204282 224558208 139494390 662269158 433306583 254230816 843108505 489718719 163034250 323483262 851251907 922051405 296511573 333544621 649073345 837368638 937021358 355397270 684677077 872896339 187511615 135227507 425610930 442676194 452492904 545166932 968274434 140338772 286255036 291087005 964037344 617114024 386471807 217587846 340553055 489576175 368656943 189850266 633221377 476741070 478918392 386271032 269384000 415830271 71381566 673072917 641647624 984085200 938112535 931693496 771067963 566004642 342021838 716595709 363937324 739446379 921728354 786445971 41218596 834866997 496214532 296414846 275092193 339995037 168122525 356803989 91363346 324898132 227749189 344288517 269822684 526067873 445923533 100605388 670707288 93489374 540348214 24815935 616764946 294899447 400786488 994016644 316296332 799458286 989703612 116413465 431895481 78562137 918136418 486328395 966793602 874316258 845245948 908948928 877883972 287476166 474436113 167036654 747771216 109099351 839866971 241409441 997175146 994181498 462895945 100188537 101634379 830841386 793484414 501810281 496738335 857156851 249697616 627864889 500065800 725544823 66993482 901802501 760432793 254928877 491394730 872813245 924776795 27629469 392815844 959034275 835687499 384962405 669013277 74460111 720216666 446108215 265774256 419889582 545420268 978506649 113711533 772295551 48328538 171430435 780660053 234816469 941861744 95439876 234882207 339016216 997613551 968365950 554588855 675687172 676913676 642755942 604876665 150411559 307850479 737765797 252003834 954962279 829830709 836094905 21299456 932036987 169785455 433223988 352547205 702448749 413141921 52678204 942855992 465104670 216288196 778472970 112319227 894407362 301034820 943194475 689330022 503791456 227285890 441340738 532589379 40647763 167418195 191012612 61727760 702823627 556785535 697024314 861350528 174658637 112847171 712727555 79564026 210212143 640996047 724900751 712647192 946829597 936922057 542035621 681740586 723379095 370802633 481252126 28076209 415520368 664197339 878170215 914767076 187206225 740325376 989626883 91920430 27685172 823802285 422164999 102836141 595102441 408084042 154513821 975294901 787497364 793097907 880541057 32716363 857994285 558400187 442888327 216994219 573844222 499476389 944341523 727808707 656084521 472374953 313980575 357779893 748235808 233563509 524581433 818103897 539894315 132808873 9060098 852879544 639464677 871830106 746700208 682103186 877253311 889450128 994932748 151155417 435888252 769848263 643246453 89310260 358969779 999456114 738066268 61405565 49612625 764016243 96203206 133123907 755980308 956750245 76814285 949883209 388284177 26862163 44385823 127893253 109790766 775591101 868035965 182958626 374596777 107690138 78023997 801079038 421147535 307729297 846587849 793794349 192284741 549965758 653136158 508241396 786429187 521360436 407123790 928550607 972798805 512101749 891771134 201587179 238617240 320186876 138493929 617444524 817794179 46994611 113359707 926224425 429468571 270988157 550550198 50140587 265299389 522087341 556431345 12923186 534152344 443830413 285816340 763722224 826222128 222779865 450733501 612875467 110046557 337961537 644807070 133336287 682491466 363384298 761316092 158456826 886029558 290411758 853640754 247428895 670036406 781304791 546472748 123996932 43398577 872690728 784619500 905084051 937386339 85509844 947983625 657004908 965369626 620499141 764516395 535353954 345234812 185782614 210537616 903705082 910849535 516873946 539475850 26489583 599737200 43107091 923510015 352563377 45576301 30446011 205110760 61258721 446444011 241075967 826240210 828008662 54615984 423309310 859165792 819730459 897707737 643187534 771013062 659337454 905230422 192826232 999576400 580942275 3078505 540097911 90259673 524719808 933157931 683061565 10357844 274623038 520871943 672200239 609706055 394640718 309714493 775977892 100167243 752734769 174887520 920574313 247235982 442315487 782585049 473294912 548467024 665075074 683010402 99880028 502461289 410452728 456025995 101401574 509921986 504733012 103982392 941824380 466467287 412214364 209000224 488324780 668868924 333726221 444434768 839849086 911291925 701822739 948119463 158186471 650083996 715448146 688010327 552122455 622807710 289616480 243588202 758710828 692819966 158776840 784627259 864986940 910479153 786374856 347079161 681890640 717003201 545009235 712891431 21605539 413981899 587314705 495573023 56067687 35771776 638234010 298665610 828199232 238066087 378664767 499473385 21602759 449129498 285255297 301085456 374286088 42118980 552326295 725125029 775407876 578245546 523791085 980219557 892730672 275828319 416978336 800277728 583064820 881362829 449430530 483819384 515876910 917422323 807355164 154398310 866875820 391951970 80543271 718711029 494511541 581681727 563076370 702522949 677024385 915041285 466627328 674260425 352127164 65876672 349214919 221112266 716569607 308662674 430538097 524813793 916652407 624446001 136608958 833674113 946660372 847285095 671565729 923874411 842204507 678708113 270863551 988304183 206295997 975994657 445340403 938928082 497373470 933352733 316999629 397010938 153542999 398685085 731920910 786887620 211294388 511992912 246832685 180126743 787184246 333830392 560019669 621742894 355114833 313722857 2663781 854646042 791826416 801001102 812065902 244206654 335085933 150240228 647371321 332083665 906696153 414351101 383536447 311274080 797408442 297519487 731601582 336623177 97745799 793270307 421127915 314388544 762830382 563327798 915540490 361214926 140970895 866710811 727363160 68937677 205641727 169551558 670896850 961989869 557734854 359125570 604582827 301953075 391641505 186636077 587466442 857843061 224692544 955066679 211470921 281076191 799134153 684426407 884229879 473759344 344811091 935076565 141625047 62357629 175877228 72489649 916320159 707778094
726040212 387310395 699235130 825384188 700642496 338952200 53641799 943121466 639277784 881532868 696211095 496374153 61128505 832650922 113848242 171242337 153362227 417085710 869783891 946091407 341571467 809238484 872808936 551940529 977997051 536256246 623178003 653456828 354316974 355028481 161872427 222963831 830449860 784657560 306841276 11128317 511782100 575357680 555918595 13348415 409651813 671879251 49497202 977146240 832400243 121643421 804780594 572541655 729317617 883752898 263733660 637273776 709941569 958976582 642634431 917249867 619833021 347833283 183081182 386647868 144087090 142916711 787780335 427460585 213175648 815454835 98533916 295370255 775100795 793259197 803565126 427106366 695184301 942790959 943421053 213898584 388226450 515809093 601237385 881531670 43926458 953110675 121146469 107551875 691664938 967019325 881570494 644322431 891129563 65392254 225323384 733673533 779729978 908931361 320146217 462072773 475823014 325890571 113542812 445733491 71213046 386630319 518986576 146434934 94391280 373112216 228674551 275301970 280666835 321693923 595353335 649315678 167434446 950538946 471933164 183392327 967378822 834779130 870945060 148334731 268003476 472495205 135374881 948511743 711173 945777009 309646363 754004298 947451608 925424288 574365564 710334055 554981252 174055942 529191266 193398055 946334831 292745422 983967776 789089197 502509688 885168565 571221949 113401072 384356206 664433037 717540467 767682876 288059542 656496060 211422001 291412657 5180201 83035834 11055642 834723267 63802579 693480599 40281860 553599928 21022774 69399410 9692666 283583789 775427429 13629955 326990779 637628050 861182569 29284882 208486456 625183913 27965375 470347005 699955481 274801419 436666072 73462839 325600825 796807331 34477720 811266499 363866150 878016560 93053912 146963645 440717986 823717064 240846309 34534865 404173605 58008656 929151230 966924738 627729752 412874244 21427417 900839909 358940059 74388214 656932638 914494115 255533440 80779398 977052139 131860986 190443085 142069999 914957390 532986365 112391551 558077882 730845390 801358672 23895874 348271177 666370531 964532140 359757049 991876174 792861305 972612705 309320636 396535376 205307506 263078607 488830677 728812589 600508705 730195180 755862594 592534931 45741519 873186241 145665847 739436677 687478329 412403181 918133401 763212764 627275536 441437728 609378691 566975939 913414264 380976545 859805637 852741179 206547081 232179401 609141344 370525589 925187025 165438342 18687499 939311354 574048721 833198553 248214961 927664358 875401595 946894936 101652209 251073961 730936251 662291117 921389725 450067941 219184619 284910612 86336827 711349523 279219292 427359713 155262855 105123838 188868308 563900408 236312815 579997509 204651787 175400787 460804629 821733853 772134189 739069056 54506321 387199886 8180827 784153632 189401901 620727665 476559657 464224618 728744679 493339256 163251233 944229029 869299954 611163110 526261311 11282353 305743733 455896019 797584756 91106943 231777994 86981545 199325476 771832724 501744640 756965034 888267943 349884043 412397914 507680871 159589835 317310096 497581262 91898186 843160400 118472933 456827527 407259405 75375979 590609248 900884836 198420801 722193476 849564907 435202422 531218889 245913720 222874628 510023814 132648284 401837463 930049850 471384204 812951558 29037223 87297974 277618745 132257191 201148575 480921007 352323950 203638386 261562093 569648885 984094147 719827312 263904241 831134055 304411905 799164667 115841919 800279421 960361384 379766595 302954337 941309119 701438314 336038604 60792787 520402507 495117742 994798830 531866629 452685651 33736718 356101204 975345309 592401821 60379353 385082750 63662642 818326017 348464018 720023359 577918418 750770415 112475503 296848703 745790845 853595878 796987355 103509625 377149095 132148478 709337844 362252734 38001338 283153247 445724173 539775537 707612562 664395208 665511469 269499338 144515583 687751689 141554831 979630035 700196934 691639945 431143712 999063918 413320864 995429568 370008325 566697996 949162426 742909886 524563218 383141879 624935732 905327779 210115155 737694409 967176738 889682212 196729991 760689651 613123470 748446221 440113312 497865527 529894131 184754617 738334020 12917039 600665796 202820252 933433679 379874244 610618083 94818746 762879567 121878711 784290090 69447469 514867974 915249691 531159526 37065890 801485804 927507672 469283926 568003548 391357355 940515626 268045617 674899760 681939873 856343329 773889821 52278792 794259041 577661727 56935737 30984033 184120370 170767453 373339028 149119564 129874318 713290597 631795635 996146288 949289893 202857625 948397839 451270790 651671256 916490411 59691924 854299868 580972350 132215587 880587812 707383251 795217186 258789597 585817362 188278369 958947202 786055816 813145256 177064080 978990738 806299432 375181217 517384189 201775671 100745876 518690735 824874074 405233805 68150776 265469942 845651436 682343010 939104341 965583247 24781837 632999864 770303228 743224838 61559211 32626247 767080471 313222621 836449223 103226872 448828192 285574407 427560440 736133995 823250280 686985581 198526694 65023090 386006162 452893037 372803279 393434260 666198805 168979029 910538756 163715467 843732157 664009453 885000557 306799558 642225962 393128938 471646465 226327272 310995535 169229436 468945999 105396295 895110900 177156801 213700857 644852590 286649141 76243023 502721331 851303067 837917954 570036910 956542536 81282369 342585501 513027035 670769941 919912071 593749278 914686151 581403789 377736648 715543282 194384854 442573875 562034962 323652696 837174625 337290403 857556391 408264163 92395060 124860425 722946174 150434555 12605968 555484840 973280450 949426267 566282794 344876884 649996370 866565268 744866218 557540856 363575872 415528585 365436974 475203090 155983698 983058929 300500036 313181490 97571460 354671065 310667251 74279806 601372548 93000479 116759859 628064305 707651381 622457592 44478576 483108376 311029805 804103019 11487499 93619731 335142198 332168659 282162137 741790618 321636816 877712224 190399394 382487861 828565166 606462871 725522339 738912515 999477813 573456078 969708045 975029044 929361152 698517681 230087811 825492623 504328798 617304768 5750944 228539629 185308882 689894094 722995311 908659132 123021970 713911171 42950385 434456701 296009226 538243803 430143131 130246981 712012886 146907302 610530773 731500352 51569099 404013830 903158652 275908394 693485678 208508659 683835744 279296980 216650875 744575674 244221127 709010597 636102880 384703098 861176040 569469974