974
896979995 358307654 454124808 824834631 119399682 337290520 673397259 524343015 151454012 233271896 469201623 714655446 346032562 352045193 175770761 126945691 254776804 993659445 298240340 211553849 814938237 91254037 33673599 931575150 658935887 403057476 14619581 423844937 580331989 807105286 670369405 941106089 590125519 396472142 769341203 995893599 45838422 527396612 877095540 918518023 273623915 974021856 624831688 834883621 705590653 578346467 932771089 762076163 898405497 245712045 158664306 884331382 591919576 971635950 994974295 622684353 104480493 966887619 828676246 31806416 459294609 457173759 285509960 468819136 890579416 222376554 188700262 535437831 114005224 677373588 199238845 780653439 469824034 61223651 160966128 721632798 876148392 88788488 212623529 479633576 808524169 49426089 148632904 320175814 276237558 780623102 424959951 594299955 5984008 202937788 546252604 884693730 15600932 982142695 729522209 329986299 617804877 326270811 214206020 786342935 102614763 222583628 385830110 852433499 316282801 818158082 321567810 634728957 563240181 116219331 624447412 261624581 764190228 392746912 283326311 452296872 304514291 325287513 176737341 49723768 443040791 557270053 635808521 284564997 518949897 436151337 218243561 540621111 950333477 192578320 255640783 558478913 311533000 320617499 151897676 898186495 556567457 859859284 476042045 477254593 129767144 944280317 919867382 276451772 625534731 821579964 38865867 477309009 624557777 64965094 262156608 117912183 131406456 15599468 663634616 987526578 436931426 57902725 14959582 445108102 66189343 764849543 572674345 160763286 497822692 484491638 573233078 619721421 983214286 803264849 987295061 148257883 822478010 510699540 611388714 497995214 649866757 288757447 838498048 925012044 872603079 435526065 196165945 643501251 475172419 619949838 156265036 434884915 484207984 7605751 534573340 845955797 533089735 568617573 651479817 331985218 880947565 672955880 71108452 461058649 879981352 966352839 703367914 706729112 933244826 8111487 191041788 557570014 436314449 532534980 975056825 233369369 451349953 346396031 462656766 431053820 199463186 898743225 121856553 382046702 62832719 206479823 15007937 850244635 256693054 233830863 424892589 832865924 611607251 248657877 187237125 83372789 696799990 99781969 764100862 33281009 423176793 966843895 258846521 120511559 777009975 820248368 247248357 893197207 458206937 983814281 157551491 602953994 586836150 920462579 174668378 359646449 668910520 594993930 880334218 34077735 619437816 146599274 720540096 210464544 69337163 22042890 179012314 749666965 676277206 605605458 585169192 991592898 392487936 706382544 506895615 342115014 929268778 310202279 295705558 273370277 986349005 692171679 378699116 859588158 297032384 741760434 353970377 107116974 546574645 310098739 290724719 317895706 885048844 523978877 59334690 819654232 117951051 426815185 520640063 702394272 39286170 234313770 346434230 748647593 493476169 700412478 881232083 350674728 5549896 242847297 31285016 296178155 758883630 150738542 54965109 849977943 903803447 618809252 25976795 918807532 750848719 207021468 985900465 914730971 34026860 233631974 650461530 743278490 169271686 944038286 586626277 810493448 7714045 388299431 613859456 801498749 500393986 205226500 945194492 577838576 30782960 652605275 696545729 477714600 221289262 802804418 567256563 767573907 344140261 760711951 177436609 510123907 290193211 772104704 546031841 285473900 747305437 307263174 395756367 519071310 264687911 218148157 923988156 827293878 345200393 475689503 518021985 816338388 346322097 458992995 569019995 512196944 894450352 636085803 177247655 9042835 660753703 415274719 16522785 477170048 190684539 798890004 270561496 725763492 792548881 681167720 889889895 7072624 347581380 206612035 160907916 643680621 582378265 507624822 497142439 412275427 8939478 869316715 101331658 27198985 777721377 960008762 264192360 399581913 122264164 714272571 748498148 952694804 294877205 565934944 664238031 454456061 469744728 599384020 562776098 616733462 739455494 83094802 644552709 329688755 951885233 429540149 139001448 269731924 153861336 653794743 763664640 652968351 67019229 346875577 408651414 972541213 535951254 894041168 360831280 660155984 629858795 277440517 703534725 990573861 455030140 585584129 293835362 652305705 578742120 902747103 8819676 310923398 243578131 92552397 564816198 110568774 209829387 301286493 186292627 500358540 630565229 46212481 383634509 948599268 454343860 789638967 788214437 572043409 868945862 205368702 337144475 931784541 458748166 781987885 55872945 659141856 186268949 153191608 283165694 788985716 408662197 795466357 850117061 411207873 312655152 293442810 307186567 885188992 393898896 897594398 963492025 633323365 279079347 445625673 880847982 663776671 376693876 988541848 106700 600454775 462616411 362462320 330844662 804517147 635327615 741932993 656244998 339383306 267620620 178933570 260220144 570315993 436843347 177726908 291899131 421173529 72305062 300215723 312593682 363199391 295971705 433451689 58983287 679267646 795689113 283571567 486901230 919433481 113168298 15224581 624498381 470999699 693670108 182555940 143389054 520717010 26551625 338112761 823008475 624153751 408698749 986816851 371035023 222576632 594953739 238093182 392265425 85912575 101440115 469900864 885169267 111386667 906417889 641683096 451328141 950211016 597396507 558875573 70403942 801654109 944382779 305073498 167969428 374326836 804584449 73441681 74401898 280069558 611683669 359936658 281658835 874930049 855839212 15730047 290818401 978952297 491399396 838455512 58293353 42122374 694598600 598608640 528425772 400316659 455936233 146593092 838681825 396317585 12633067 945072097 422825357 757632615 864432940 732126101 480481381 282155421 350298536 694675922 678474462 98625749 649284509 592278131 669639668 504785922 838932041 342145675 395885703 744841935 522894228 477635486 809648 284237966 79289235 65809974 930594588 16293185 808211398 946591283 101146755 663137405 505314547 261114755 592762435 882462363 948950669 5033745 150277239 136034806 759035476 382366639 761229239 108524639 251517475 504034280 234477385 409072984 674255189 521654661 363785207 731614999 242465788 591404560 153236805 425988065 609411253 81822178 634528454 159448728 846634387 60982696 44933288 862402832 167969099 424958270 224667625 666196787 447268104 278734681 549206366 931211957 215918854 707554529 614342148 644314207 703840732 286262197 606140697 104512005 555134970 880366914 780086237 721422323 61165515 336160517 901680384 939190481 830399091 631982383 946658777 783107520 411293605 937127656 227805221 105155505 675468399 633951954 393830098 370986162 586175183 566346673 601292685 33801885 834528559 898106322 808893099 581248806 726823074 214954533 827706294 263102349 102875412 149849800 460365701 788027554 513016572 691104764 37141255 745453607 277795106 196752377 20751957 428779991 893548946 602632222 709436420 303793472 509261197 824814037 182567163 229283522 656311959 725413284 825418063 823848773 360247693 460642583 413289567 251500097 799577489 48754113 565388129 634285458 192763492 40134917 285546354 462227556 549845911 502801960 933807138 6750390 345597291 499204011 235789093 661597846 69215056 781138895 416319783 474556508 657832184 602154023 200888154 509948229 487399863 550953482 128434272 420755655 80651266 439712376 883969108 800692365 169853604 64324892 245229847 685886245 46994456 808344881 469075266 500010749 425030512 627454704 710695844 737737900 305963798 664863629 560788611 148996991 572842298 827369302 503852095 711700922 604472485 683523540 811946661 119196827 323950270 991153013 524648698 805948938 832537243 444200725 105269587 162473323 128217236 863783516 768918659 201354764 976724393 184828123 751310607 437579265 15723763 706882115 351901455 901463250 601084607 319487391 681977421 108013754 171714130 837486104 355795707 365356009 231022677 421737679 932067429 544658153 239378797 94314327 151452532 262743966 126128010 548687115 788303333 41796320 694009767 123587213 600441875 416153825 138318709 858861743 563392086 972466457 404521270 180758827 399778939 564774616 264943247 904686885 283129173 771962687 845300514 352717502 520677382 455143208 483246853 407150949 138299203 236990743 333735019 923176404 118757007 386208858 372934077 816563863 105858436 485133858 216102382 87531166 203335712 805025425 918056021 557764512 164392729 42268129 264237875 763268015 703049430 163371493 776164703 822713911 587669785 556113416 531462186 759993480 993003131 454505363 295127018 917442132 865020069 683081362 716840028 378006126 969422273 447703031 365450953 869695308 760052161 349883242 551452053 196249586 379820312 912559609 652479609 182200619 497939544 508628579 424360051 858968093 589080060 423959023 275591374 900172778 721013022 869216455 749295978 699170465 228205422 138844223 859225974 479350474 964595348 366364993 505607146 383212777 534284449 370520540 102787435 87292163 258058044 255850928 111476105 955921424 354855589 451315358 279218806 259001221 427140754 845663958 812079648 531094159 796872470 871356266 463139850 976109092 796100690 135679892 142575932 122460731 435275384 299592204 568463996 759292177 159598293 844415724 141393074 602308284 468882946 697607556 302033632 247599847 81612658 812539501 107147193 328002271 577598447 878508612 972595034 86796478 310671224 914053094 734393242 800055462 787960368 30819694 741266210 86076114 976192493 375795114 513622760 13470527 965491409 965249363 350441365 698842231 640793220 938673828 189748743 926491786 535066954 85699343 172540721 913344957