882 393882408 325880404 771089950 84642180 839925229 595874368 437141542 553463969 697900471 396808231 98114498 308255577 42341918 861186837 735324975 812694135 441306749 342512220 590198665 272668414 692573070 433296450 502329899 512026323 388025199 756979437 302961950 521257382 131447741 621707752 469652700 497857286 317890308 975137367 324674396 607512367 465928271 34221584 803651218 519383163 713363862 756376671 125387588 387042861 377704159 385028061 928247350 607998827 275047122 262807845 114165009 49868497 652153039 865046149 451301356 360636425 794016841 274599165 807096369 662361148 583259533 877926252 169785679 832657732 574992346 772918749 943631448 724613560 692522739 649970435 203289186 591696628 240520209 945219856 803653303 81210722 101302010 237544262 727296232 924245858 494440433 25281206 49353419 675527808 760519207 202722645 637779651 58598212 456186053 960119373 792563854 471930016 689505858 114804218 613274244 745117637 150967847 264550536 386848532 26255563 676191505 664471055 783351444 486877054 984307160 318165050 345388304 363127470 360774151 660541961 383117299 645628880 531301622 350601570 697027167 750400521 602017109 506684792 949057697 470778035 559629805 908502090 533250078 679135515 570775382 464250834 949624889 532614623 126197124 736024551 186432485 17047770 548160917 292739621 262282791 832883747 98719960 791340182 238291006 250144151 833509719 35709159 519544027 137167715 803633489 648577093 962918166 585374003 417690022 258161182 346572785 580679256 34370564 908607725 658840019 579806091 477654043 563979465 677915696 331107591 669545419 550063371 414703692 456993212 471088475 65317684 252614180 195891689 728336103 795760900 584672370 209438037 475575726 81914133 773274997 49586198 48816883 506040388 998380583 728790254 545511390 611044445 194725127 404640298 716588575 162871394 256780263 701168092 38616531 963533243 727277355 95754162 581233394 623004964 653482344 60686344 532690555 779818635 934043354 748557016 777563929 722516554 244299580 848733663 469555597 852208724 560816728 49156488 833043146 536003817 971810386 681327313 343636836 961167777 161520876 755821333 910411501 725980987 356452735 810307128 212486783 108496260 461469021 463929800 433054631 854828600 892683986 407927739 824314951 312890492 872550542 158308503 95168518 298363315 530025773 217151786 700578398 569235807 949076793 826114427 371822482 735308564 726414214 427431802 759777028 840969947 817698327 798742521 217068670 762908795 556640485 28333253 794933400 563310230 406417977 854383849 719440966 125351186 934907428 308337762 168865353 84587537 220575638 95779392 798059471 566454100 554098256 775305735 526095178 107034945 958675494 925994725 698081444 321673838 935624382 180713391 497355275 444534695 167706166 31726684 112726303 666379354 634993447 784940570 970893342 563407509 733218996 745990635 541174922 272756810 690126084 695193434 904970724 973764435 74956777 800249958 948044989 573389137 574339691 459680549 379216839 778208985 346698480 870211377 4973970 11954028 247886914 387250376 701850510 257329496 572747189 140778036 303593116 873927102 609775102 997673947 864026498 540602048 916876133 375519096 178094571 886903137 932957505 200842838 448639812 576423802 92059251 632181306 808636122 622549131 815432425 630006033 3254303 480614117 634557891 883521013 372186218 574820727 571758086 682200763 861986069 484549261 831774846 40170814 83373830 247555771 303314867 382227902 537076520 277220457 441814790 806215921 450732877 769158997 590093208 733140679 511984419 283381103 332544533 398553776 607453814 86992826 286711792 546437530 526085547 201042576 292962695 104828594 701562386 650962624 250474438 342802187 831150185 471929275 267177984 483172765 295216782 964413911 42980829 204236134 554226960 587577290 861834341 110124873 614909260 102970693 491306772 708885854 10345815 870434648 876833136 346822024 486587943 584035244 359594529 686930815 552400727 698941502 58706482 905404232 80031987 534291077 668606485 346801131 676941438 500094870 384529704 508195190 967664669 885242840 974890560 148511931 371814081 853199509 472254181 216600339 31970234 665692255 999491017 303145949 667805468 346412038 105774619 807538666 210681761 329329706 228469904 731655926 144749072 274494940 823603228 159160409 194064714 881798165 137450755 684084017 321327932 805261368 814688810 576122799 283634620 690682551 716420091 308648534 316995055 874930254 424469959 83489840 249305894 13387724 696104071 222450901 928275449 740843990 95146258 403090037 493713218 563184574 667029623 227485641 25612162 193116490 758330967 807283939 126330562 238047391 15578039 296621648 347855504 750075605 127070512 558699566 946093136 263205202 773905345 793938879 672673887 747480674 333138736 3382875 912142965 191469526 751175075 149796864 438140383 298805731 607721130 699217245 214544519 71856333 999392415 543612380 457125730 65084693 453274408 992446126 298985365 316829576 464937316 873496216 352271798 609177969 329924270 312600047 98575053 330991702 691381744 540033211 870789022 71250224 476390922 367393088 101710510 167262561 68404809 771990124 67627119 732657690 410856766 552005078 341915303 288786239 265376828 202231270 737032916 560882005 328335919 736849794 259664566 282553891 43531104 96173165 906766036 831241903 695274504 245338715 945410563 452803246 839326721 478907075 535434619 906019445 618547554 867485927 88121225 43833852 853566981 568699739 359025278 227797422 76767533 76640866 648175514 466627144 933589817 129927662 945577359 937754368 770553069 944301825 180348927 254163715 445072054 479075341 572687104 896395413 102511375 558192108 605748278 350772265 983646374 454576131 401055072 963749603 853305152 833846188 592946409 815660068 366369561 236419353 717622585 565454987 272897894 377696750 365713717 61522970 707217412 28297975 695931576 503504324 941538741 879209324 105800436 999047678 180735421 288435502 278015645 737532266 525257026 720994885 752608802 218021391 567405187 314118204 953078444 652975719 714066820 912067957 154049113 756516914 980042489 730020177 280005293 25045859 694688669 91245705 475206033 75071929 872779663 722477516 111406937 544514098 899637032 433915746 999936743 515610855 339749712 716610214 386597658 424012898 589831788 680918740 376733898 592671853 8229557 183094278 647777023 12285744 820487695 168615931 496887111 361192704 607787476 979364567 321812683 282616486 466793228 449712245 775557661 315186474 347186888 398900919 887759983 208667031 466555668 259161045 329656687 582040522 829655542 392526059 113347128 848351987 524630864 86117489 820760277 518047033 705366430 401985029 306235004 164800313 325627103 367237063 104442125 966889987 299329926 720329411 537229908 554871210 208235786 876443327 475878906 307648542 535091797 912022217 610914914 492606046 645971438 37838081 845468166 931601429 361276241 975097916 390719312 308012065 241962996 617961941 333186839 690529119 290012414 171180095 295122093 73097811 106426348 67410584 329404513 919896878 152723590 87585801 360443355 191917355 119262457 43662226 848992584 91030075 128936152 558214699 357466628 309028629 461658687 865445068 988053053 745401519 154145297 228837876 131852114 518111855 642732477 257001939 382593554 59502504 978522001 501277033 103209850 164758336 856138380 10327238 79488978 283624268 353092818 110636463 807649489 810290930 323964872 427069680 957993274 557021186 645001839 484777423 355995964 6179130 364994534 723672511 934700052 589347089 269484161 730971873 580146995 735149250 97976480 631953600 364621244 419749710 694699916 499494615 347556831 698692941 84019035 813526296 410389917 325213204 641616708 740074575 247451501 682119559 141914589 890337761 295429916 202723167 954886639 65587724 663147201 951315900 161570447 82779149 279203040 172196686 338094292 510806745 642378442 143859013 935994589 669024893 351414540 404085570 717036665 96220778 627009312 538319662 36901361 737997709 221476159 923533770 971315786 735719736 808434409 628707419 383615007 426874950 242501244 98325572 725448542 650005206 639814920 15347040 447022936 992834510 65109229 945310792 649099192 303593334 265092417 862692674 455508853 900781064 807187107 506341228 986930796 452409876 792434753 973732002 663103116 984484763 931655418 911901678 382019093 948044643 202917143 622437134 330110721 111888278 735049824 668450529 967420603 475135756 202908323 461662941 44115535 639688334 883424237 702071954 721143150 345616390 14101213 110302394 94114971 275927024 858623793 720270932 55529720 654345297 635747206 495663527 650949309 84670661 265489810 35042295 646413193 982459373 889732198 73450962 668048578 770044431 88267434 952937151 363253444 523596791 69790406 291071005 245698400 983561990 271586280 653500874 575729467 288331749 701565858 379521521 955299899 595798827 674571470 262666908 452147713 675734885 888132280 461977202 547151506 589266057 577220605 982840435 238921940 550922578 725194262 88981309 484099517 326335308 144647764 323875058 269856980 612381977 935963311 309519560 962627133 830086839 856111769 230289045 586611556 809232150 175713838 530209052 773170088 115696940 74983625 333053826 258444532 945231660 85393624 149054759 546103740 892317548 569362652 735312239 772647731 745099677 60513975 782167786 542168751 142792437 160682437 65365093 56202011 480047551 624039403 354757356 473050062 316169432 134932440 445530838 757956158 671935299 2165897 798349918 367274088 767267928 132949625 85082413 796119357 447922410 723317479 950618757 467182915 715284469 636893264 195435398 687211699 910699228 978167069 342653430 363613930 489682119 634059114 565855248 242794738 264842913 110073523 866517678 522187984 633698064 887362796 378311005 415177603 880949396 565604884 731074697 35762901 17821472 17417302 178980532 943558284 432868127 486723915 982195777 160622636 235904263 577292635 449208679 539857883 338130111 582084641 864808757 726388912 465319897 921123379 6054055 851965535 67036784 909253926 231696420 345347690 399681916 383746038 708591697 860418573 697752097 357913468 847480148 517829710 946596949 280288759 122707969 425906750 404582128 685786150 799013825 19288927 799984688 104757317 432448970 553468760 945152221 984972518 311901522 743142943 737540440 408699672 629835002 234523901 115321650 341552182 745800431 876810018 709531801 226373865 710241211 136591077 854343736 810921320 135917810 61883835 558273126 238501836 418449667 655788404 657075250 914641886 792833203 913115469 451765492 107626807 599690053 367878986 157634710 917797137 694698554 728035074 363043786 174364967 360294425 617610902 730255212 39620955 436254245 649277428 768043421 995027683 86451491 303216016 653324119 341025787 738989029 279080262 948757953 844431917 393430434 618506933 241293133 717806887 250779820 371084649 649708247 502350905 373468753 784759865 912416900 363141424 628691610 117787722 4783546 838362883 749669056 959436465 45877685 353403799 402354729 985028178 300021519 460138420 848112181 530146358 241597820 872543726 75226778 322954884 653399733 883737739 633092634 57098697 61790255 360235104 426600913 507045975 602738659 91350814 682147646 307984170 353443925 257976272 970049747 640978768 827378069 487065781 3827903 932185661 215344151 42724055 741473532 553869652 25217582 151073850 819320123 639199593 65814293 216625233 600372178 413551741 538089135 952675894 754981173 637112233 20407643 802523318 884354289 121181796 379608544 480832459 915638558 616557256 939376070 973660065 534020314 210939839 128264832 565211190 710264501 739580936 983105079 378829809 155032316 42671881 646598494 582506905 263196941 600887073 312119809 186726887 84209907 259972749 634389825 444964600 420124011 360199738 532003565 697530831 595150933 213695600 60697878 786264730 767196558 987890729 314218329 491123818 924908686 393032031 822429333 885904022 337870453 750562686 934084574 153455526 631935639 72452048 747455989 594690280 378454052 256846902 678562137 547529401 6084724 304833604 709442617 143163865 42303087 507358773 125965903 414042393 57720015 234836756 498704877 36520210 226992481 775555037 314606278 432997876 161692960 215746394 802722049 213783647 810817848 926574943 728235450 609979711 270292301 320059206 765087404 566381598 394840266 209368464 697509279 48456229 725007304 806389561 551311131 777694106 990506774 221553224 822371082 535119832 548033760 676485614 516127062 675692109 431330278 352089050 832396100 950148958 838322336 923474403 205248210 545009732 46480826 215123245 842906036 499395852 819883492 363973581 395673645 573944390 474822410 865685606 74768851 261318719 332899210 53628236 808577042 85233384 190252953 518994027 706162661 355526352 389178017 651131451 2934450 107259853 93132588 530923326 668958527 56622648 314221323 983964724 772781305 341396018 574799990 37266442 779421370 141143111 75748847 484948925 66553694 999130188 216346192 26056191 334624523 90604034 770297578 917075575 451477753 550116734 676643849 51106186 629988893 301998539 972992298 37617898 6997987 783159812 160789318 850435480 152858895 458050034 149902743 934126440 25998114 808521780 417394890 882985002 305286419 441523648 366350961 957857963 368677222 582494747 655974142 730471752 416690399 527406823 831464548 517495025 598636033 599074566 43296508 338846031 632184761 606987006 850426090 613759750 688436231 86997368 344219686 753590727 615405440 834385204 554266765 764994419 19020402 978221666 165123065 969049966 660960729 792776109 668870608 805116737 980728307 103176523 446408358 341791330 733725458 516401043 214268950 479101611 433874716 418051700 988077554 852689268 233171381 44836592 607672514 806907424 53481637 177483258 908990665 70324998 550375632 664298921 802343014 7060236 954770580 834519063 142887593 932377670 651085868 319646117 735702943 115001051 44385990 113221499 67999020 369867228 130912726 204409521 734737652 220065824 88063626 374999055 657334411 928962533 923139764 157498228 405368049 426177416 750963791 975460387 950338060 893631756 148801970 735983363 284617801 951450914 548003597 394328530 290736046 223603620 366776605 644380625 783037963 743597808 165846769 750741722 597881612 227877351 572832792 753839880 106056242 291725598 619486409 967765419 917443739 977791635 762992848 542050771 268788911 607417438 296938730 538650422 513548066 623772882 617087216 413345263 505298637 887389016 426235555 931391672 146818579 218477518 24881330 814423691 225614978 476935698 996438603 403494637 62675062 578293116 810475877 799854578 330040662 274294351 600046059 319141302 394073977 758138690 31296483 574034755 292910825 772744878 560380473 518434557 311851400 713961326 391699869 16490441 414142166 163949845 963282445 475468954 720232433 329535729 411014676 540139103 655504055 352006437 998527643 218266239 950841510 108622333 984853529 958597479 286683732 254802627 68889829 817871580 681887436 78565598 911141172 253834465 676247850 686094607 319074612 978675285 49691504 592369682 765705329 144245068 560574321 524128107 441162603 881868642 595050450 810064563 372981006 661083897 447929365 639508444 898203464 996710073 141040591 859815795 647967022 102577721 8785890 122891100 103332547 768534363 739121925 104616998 697473943 190758234 570176210 385020516 262749607 195262965 101216336 554363259 485712566 1427550 104828316 658763910 188320890 234400975 789437627 474953071 459465184 15471913 846029693 44747034 903925653 486686811 284907275 666169906 610801504 439402880 722550378 685520331 674608826 408031484 545182977 32831868 146707355 941649986 505513708 282205884 714218042 157193915 466359093 938269707 286962996 556813359 538492063 153927793 916751808 89946178 410710718 144335036 754891584 581131083 968613357 785045489 209893413 306491435 925641064 404584676 176838503 189972343 588522414 890013633 40598017 372715526 614308068 75899644 174780988 350753012 750913138 751353756 438038349 66636916 22229137 298922017 700608236 328512681 562630545 935880150 323811754 610242285 243180402 894484212 519762072 14395582 802052674 324625266 411798677 186711916 854868571 253456371 926928568 663927186 447741600 226244985 377018212 843933301 121976004 899597188 531547185 852655492 197731256 612227610 730942846 149259900 52007762 374105348 684820619 439643691 739485659 475716156 875905255 299661009 8373582 169512491 613633844 873575645 829219636 555609491 794144880 772394947 223177936 262162889 447415521 628979291 710923207 543533373 321313213 127973439 119222981 527254697 932337311 100171617 477719166 294664480 352363134 894499260 978960231 169305330 121589698 156174753 264797822 326669195 2822341 161038767 479677445 94751290 402920959 231858316 855311672 731857973 632627664 479998134 850546358 491452944 567477735 868413274 310292962 302584867 832474911 148492481 35723111 540490931 751145710 177652271 48755974 827430253 535494188 862734584 826816681 375817442 394263579 431961582 424199259 490346480 500498114 213932941 456777260 272303095 353024841 851576745 553825216 974114612 326363383 347596864 601862746 309103367 568579740 153084409 193938776 813568824 326330235 224388925 6601663 399287565 819366755 579578648 490602214 232662727 363889677 38555174 137716970 721541200 649672351 318393174 978076209 462633854 47126689 155377221 131222843 389310283 27863393 512670444 542003751 415536417 769476855 176196612 475777469 922781685 349618269 825198263 512613595 117145326 872185378 714561268 942022947 257501314 61771572 993418981 431235829 334628504 877520801 352681825 929519147 231202606 720100315