822
910737269 716472968 977953810 365339054 698675636 153790624 759216350 219882228 745671116 189371306 492712465 38077283 494262996 323689822 951112491 716238264 586770246 533438606 895671239 767903536 320072756 729522629 795872283 81323218 97940065 294081561 684124213 412584768 525716318 306022709 171220900 908103436 764253486 755927141 32910770 22642201 230448007 175554636 245432936 652610618 476272534 719437607 908007535 230489412 942598188 990334470 214066677 835187131 354838535 857062492 931698847 473161767 120441950 959185132 925664252 842466151 510683229 925749515 774279595 331473617 999151175 425020412 393143364 238569262 768078214 696088417 834684657 568215091 998143830 841643033 12474234 776035647 41008860 106310013 283283745 426607703 613742742 352408494 355578561 810225424 770466937 508293085 65680644 157476003 323473338 336211594 50662315 488220276 314325578 898278634 607901450 162910038 597642454 71610627 18378151 368737728 530698242 341224595 938864041 804322527 782685747 542414788 475584109 851286853 70805342 321553609 489302715 217880167 119870519 642199396 144369690 625636804 344096952 448951185 385357006 279305620 874654997 99629264 510378932 760860840 552243133 741909904 886796684 848294106 85043448 410602874 638482021 384539475 671802400 250830936 317247680 696934501 451372613 87276356 741856658 686787826 686090031 159679624 800009390 63458111 499781656 141054865 280865037 144095111 401531476 470021347 455358727 173203056 692964218 562444973 195613459 824567328 988544624 739968259 243582223 710319434 781357627 601781251 937926552 889598860 374544106 298261773 916417312 262989997 94118322 208172018 569175983 773258745 131625244 757650261 492108301 171622286 414811143 97824694 132002320 311083029 877761972 958315406 32846371 533811620 225013868 717808616 826721491 901460701 734062142 230238428 528993109 636810670 958210504 843341382 385370845 164649157 95186045 640851005 332664593 829660311 239479141 795109850 149981757 498129097 158803276 396523269 156515721 728032401 438418093 270245993 915260834 348891249 428040282 673743081 935358879 380286896 262797463 724615931 253219154 540810256 60280753 807090389 759796997 622844579 421703562 19506386 475574597 683453200 661601333 89658615 583355066 844189956 868904994 855497664 698953611 951807870 277784806 419508377 863152977 235632612 858617328 274292904 693283269 614867282 728436222 678725927 973980230 954995247 323950297 947825450 50272999 155399467 882199783 252933393 936714536 53432863 712502099 639397524 506601408 702878181 921502675 349423969 326875159 71333952 191934321 719878546 277060941 559302755 920959607 14595039 520383980 454241264 907890378 916286160 547253041 728676473 142829305 928933026 583693590 132210367 621966161 807485276 495623207 248073083 313023839 824784751 448940228 877237018 798827815 210866580 148749303 85161540 61157972 578932277 743236256 17799620 126477874 480108959 637095292 715656761 491993887 312319076 42233519 434326788 802347088 776606859 564571892 18669756 84715460 402526611 75801095 527330522 648543791 99459689 789842855 273002877 872565690 889911347 281498697 74970436 339646280 863845307 886442242 209584206 246432536 397353200 919681386 54430139 790302712 571197800 454146756 817613869 51731787 529482040 785182334 22763689 884700101 860544598 188514500 862418403 458161843 943212717 66005083 229913130 723964455 492516195 333986570 991460946 948500315 624756626 832227655 458089238 994251712 29499510 428126808 912319192 915905923 776113434 667756999 298899221 190341535 550849169 383129496 958154602 738530054 613513314 489678633 708378418 425794404 665093695 499700414 552269872 948313663 563452844 720122913 570833321 235992492 522512262 522525007 782541545 324333827 641928538 927675810 635308204 831141365 646411120 70594656 54285361 528165054 386853029 71038810 247678008 551222757 530278761 397309154 668837514 725759968 486288011 65256605 71437854 230093356 821930582 896640284 985038715 740580831 490480464 81042717 279832144 219710309 989352858 331809808 572567036 356748605 459200947 328955213 838070687 163145458 662473272 323206499 439894892 908165264 603536439 45110109 309030759 584308816 679187106 547510107 8661121 863788139 903045805 732268612 263441762 589311672 142163503 619682554 957429758 552803846 163066788 851546667 603800872 256919236 494232772 227218852 687333095 196246803 996627434 366721015 513714222 308652084 736991031 120162327 129147332 136578046 427252458 305432717 85297823 151434246 225699470 766880830 817707219 820313972 371079163 144704592 611744130 681052364 738809935 843643634 799537406 736533821 656086161 502535657 343410827 675222268 581337499 936742369 50949990 383282159 830114233 207806666 318568310 462322445 40968179 778634009 760823089 929920193 167076510 207101026 635061450 348181566 742304818 968389875 772625707 816077818 490624185 821819645 796043453 775492238 488092293 719086277 663526081 961064104 812810241 564696681 255399169 780906925 438003507 223767755 891115163 969549691 463926198 296231341 724072000 727502075 201744095 696534369 734331306 810576765 99424700 447908019 721857864 385562189 226709814 740759561 224789955 16663732 179894403 829561850 594567203 582641895 427677560 925180681 687093864 917476013 469280851 570462242 264151462 446898646 437024717 380064078 751067019 270209093 326467226 861083188 998866287 409274168 379389596 701380629 175312173 295139641 78531867 604194478 748255244 315386055 328590747 696908321 56699058 939704901 718648392 612044764 320930185 776919086 91894455 726115677 344451681 642412759 660252201 859557539 646409574 637348730 49153047 887993464 405903114 225975497 785711754 205946978 827040253 999935348 285419612 999836068 459773046 223149142 562761213 568911451 690308263 134655566 685604950 629282980 950150975 770412505 935754646 250091787 117735827 909284683 692080268 678886871 898437000 208323148 468806495 625978107 794014262 6504391 901160537 862077534 118463134 617677176 898060462 892772519 445967311 564458889 56796474 496507711 766181602 567135433 600674394 349992780 932105213 547778683 255388931 153829682 435505007 563427031 322669000 351464529 759818091 134577449 460628817 213871174 43288483 488951112 90506873 383731273 143154480 807442379 645605321 563899989 657946493 240662653 413570231 596200469 571267886 580808126 623155694 162919746 871138380 550535766 526551187 672344501 114371668 124869159 589400778 180342987 276794468 627349165 665239857 683415908 325152737 568395233 930371574 31564176 324598720 461404390 281869779 565433467 523609666 571892253 838166189 65215737 927027381 575681926 705268469 877733866 238117902 272851590 195069414 933857195 497035284 901692658 356099727 60258353 46621175 189007166 438732578 818068268 723431007 934700023 222272830 124816811 769842433 544485509 258627557 810328094 705634858 485713974 37496688 101292791 581502749 888943456 557493661 870910244 417254362 782441133 780439634 374348311 982807562 463503569 435263181 23672288 688462244 304192063 764956997 201859463 156783734 190397272 659226706 639366667 218284872 375856428 505770755 521602272 208331087 742487689 390934307 814069391 979690324 413529252 998704968 528911923 513024247 826823852 982434451 604404683 450849675 733419775 902102518 822864923 437090971 416663004 515340467 656460537 386984423 13333165 969477426 864781794 725159051 392165910 444573245 634846186 945679558 367817708 465503250 927459820 59782077 654537851 984680824 430885031 962809839 255645755 570502162 844474685 418093419 216228346 321194613 260984388 809370039 66784529 122091587 450761345 384836388 128840902 416064153 517753818 369554682 979094462 927715934 732055359 892893563 279183116 205839239 371347398 797069213 374811009 11030553 176496916 667042519 241576616 967624833 799692637 44722854 914676183 909631192 425548035 998167981 40310660 727839268 692371289 719198447 790317749 976013786 127454884 318571448 902101938 726446177 677024935 69881232 566987601 700473508 263582964 682655865 152742661 297616819 82986034 129154911 143369083 795165052 855980038 862591906 764384252 61230850 66792158 263229990 421774035 963118067 572739198 412564432 579158700 334016823